Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours
This work provides theoretical guarantees for cost-sensitive learning on manifolds, generalizing a classic result and offering insights for high-dimensional data analysis, though it is incremental as it builds upon existing frameworks.
The paper tackles the problem of determining minimax learning rates for cost-sensitive classification on low-dimensional manifolds using approximate nearest neighbors, proving that these rates are achieved by an algorithm with random projections and providing a dimension bound based on manifold properties.
We study the approximate nearest neighbour method for cost-sensitive classification on low-dimensional manifolds embedded within a high-dimensional feature space. We determine the minimax learning rates for distributions on a smooth manifold, in a cost-sensitive setting. This generalises a classic result of Audibert and Tsybakov. Building upon recent work of Chaudhuri and Dasgupta we prove that these minimax rates are attained by the approximate nearest neighbour algorithm, where neighbours are computed in a randomly projected low-dimensional space. In addition, we give a bound on the number of dimensions required for the projection which depends solely upon the reach and dimension of the manifold, combined with the regularity of the marginal.