# Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours

arXiv: https://arxiv.org/abs/1803.00310 · HTML: https://mlsanity.com/paper/1803.00310/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Mar 2018.

## Built on by (most cited first, 3 of 3)

- [Adaptive transfer learning](https://mlsanity.com/paper/2106.04455/) (2021)
- [Statistical optimality conditions for compressive ensembles](https://mlsanity.com/paper/2106.01092/) (2021)
- [Nonparametric active learning for cost-sensitive classification](https://mlsanity.com/paper/2310.00511/) (2023)

## Abstract (arXiv)

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.