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

Henry W. J. Reeve, Gavin Brown
Proceedings of the 28th International Conference on Algorithmic Learning Theory, PMLR 76:11-56, 2017.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v76-reeve17a, title = {Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours}, author = {Reeve, Henry W. J. and Brown, Gavin}, booktitle = {Proceedings of the 28th International Conference on Algorithmic Learning Theory}, pages = {11--56}, year = {2017}, editor = {Hanneke, Steve and Reyzin, Lev}, volume = {76}, series = {Proceedings of Machine Learning Research}, month = {15--17 Oct}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v76/reeve17a/reeve17a.pdf}, url = {https://proceedings.mlr.press/v76/reeve17a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours %A Henry W. J. Reeve %A Gavin Brown %B Proceedings of the 28th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2017 %E Steve Hanneke %E Lev Reyzin %F pmlr-v76-reeve17a %I PMLR %P 11--56 %U https://proceedings.mlr.press/v76/reeve17a.html %V 76 %X 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.
APA
Reeve, H.W.J. & Brown, G.. (2017). Minimax rates for cost-sensitive learning on manifolds with approximate nearest neighbours. Proceedings of the 28th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 76:11-56 Available from https://proceedings.mlr.press/v76/reeve17a.html.

Related Material