Minimax rates on manifolds with approximate nearest neighbours

Henry Reeve*, Gavin Brown

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

9 Downloads (Pure)


We study the approximate nearest neighbour method for cost-sensitive classification on lowdimensional 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.
Original languageEnglish
Pages (from-to)11-56
Number of pages46
JournalProceedings of Machine Learning Research
Publication statusPublished - 17 Oct 2017
EventInternational Conference on Algorithmic Learning Theory - Kyoto, Japan
Duration: 1 Oct 20173 Oct 2017
Conference number: 28

Fingerprint Dive into the research topics of 'Minimax rates on manifolds with approximate nearest neighbours'. Together they form a unique fingerprint.

Cite this