We develop a novel approach for supervised learning based on adaptively
partitioning the feature space into different regions and learning local
region-specific classifiers. We pose an empirical risk minimization problem that
incorporates both partitioning and classification in to a single global
objective. We show that this problem can be reformulated as a supervised
learning problem and consequently any discriminative learning method can be
utilized. We consider locally linear schemes by learning linear partitions and
linear region classifiers. These schemes approximate complex decision boundaries
and ensure low training error while providing tight control on over-fitting and
generalization error. We present experimental results showing improved
performance and robustness to label noise.