No Access

Robust randomized optimization with $k$ $k$ nearest neighbors

Henry W. J. Reeve

School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK

E-mail Address: henrywjreeve@gmail.com

Corresponding author.

Search for more papers by this author

and

Ata Kabán

School of Computer Science, University of Birmingham, Birmingham B15 2TT, UK

E-mail Address: ata.x.kaban@gmail.com

Search for more papers by this author

https://doi.org/10.1142/S0219530519400086Cited by:2 (Source: Crossref)

This article is part of the issue:

Special Issue on Mathematics of Big Data: Deep Learning, Approximation and Optimization
Guest Editors: Charles Chui, Shao-Bo Lin and Yiming Ying

Abstract

Modern applications of machine learning typically require the tuning of a multitude of hyperparameters. With this motivation in mind, we consider the problem of optimization given a set of noisy function evaluations. We focus on robust optimization in which the goal is to find a point in the input space such that the function remains high when perturbed by an adversary within a given radius. Here we identify the minimax optimal rate for this problem, which turns out to be of order $𝒪 (n^{- λ / (2 λ + 1)})$ , where $n$ is the sample size and $λ$ quantifies the smoothness of the function for a broad class of problems, including situations where the metric space is unbounded. The optimal rate is achieved (up to logarithmic factors) by a conceptually simple algorithm based on $k$ -nearest neighbor regression.

Keywords:

AMSC: 68Txx, 62Gxx, 62Pxx

References

1. S. Arora, R. Ge, B. Neyshabur and Y. Zhang, Stronger generalization bounds for deep nets via a compression approach, in Int. Conf. Machine Learning (PMLR, 2018), pp. 254–263. Google Scholar
2. Y. Bengio, Practical recommendations for gradient-based training of deep architectures, in Neural Networks: Tricks of the Trade (Springer, 2012), pp. 437–478. Google Scholar
3. A. Ben-Tal, L. El Ghaoui and A. Nemirovski, Robust Optimization, Vol 28 (Princeton University Press, 2009). Google Scholar
4. A. Ben-Tal and A. Nemirovski, Robust optimization — methodology and applications, Math. Program. 92(3) (2002) 453–480. Web of Science, Google Scholar
5. J. Bergstra and Y. Bengio, Random search for hyper-parameter optimization, J. Mach. Learn. Res. 13(February) (2012) 281–305. Google Scholar
6. D. Bertsimas, O. Nohadani and K. M. Teo, Nonconvex robust optimization for problems with constraints, INFORMS J. Comput. 22(1) (2010) 44–58. Web of Science, Google Scholar
7. H.-G. Beyer and B. Sendhoff, Robust optimization — a comprehensive survey, Comput. Methods Appl. Mech. Eng. 196(33–34) (2007) 3190–3218. Web of Science, Google Scholar
8. I. Bogunovic, S. Mitrović, J. Scarlett and V. Cevher, Robust submodular maximization: A non-uniform partitioning approach, in Proc. 34th Int. Conf. Machine Learning, Vol. 70 (2017), pp. 508–516. Google Scholar
9. I. Bogunovic, J. Scarlett, S. Jegelka and V. Cevher, Adversarially robust optimization with gaussian processes, in Advances in Neural Information Processing Systems (Curran Associates Inc., 2018), pp. 5765–5775. Google Scholar
10. K. Chaudhuri and S. Dasgupta, Rates of convergence for nearest neighbor classification, in Advances in Neural Information Processing Systems (Curran Associates Inc., 2014), pp. 3437–3445. Google Scholar
11. M. Döring, L. Györfi and H. Walk, Rate of convergence of $k$ -nearest-neighbor classification rule, J. Mach. Learn. Res. 18 (2017) 227. Web of Science, Google Scholar
12. S. Gadat, T. Klein and C. Marteau, Classification in general finite dimensional spaces with the $k$ nearest neighbour rule, Ann. Statist. 44(3) (2016) 982–1009. Web of Science, Google Scholar
13. I. Goodfellow, Y. Bengio and A. Courville, Deep Learning (MIT Press, 2016), http://www.deeplearningbook.org. Google Scholar
14. L.-A. Gottlieb and A. Kontorovich, Efficient classification for metric data, IEEE Trans. Inform. Theory 60(9) (2014) 5750–5759. Web of Science, Google Scholar
15. L.-A. Gottlieb, A. Kontorovich and P. Nisnevitch, Near-optimal sample compression for nearest neighbors, in Advances in Neural Information Processing Systems (Curran Associates Inc., 2014), pp. 370–378. Google Scholar
16. W. R. Huang, Z. Emam, M. Goldblum, L. Fowl, J. K. Terry, F. Huang and T. Goldstein, Understanding generalization through visualizations, preprint (2019), arXiv:1906.03291. Google Scholar
17. H. Jiang, Non-asymptotic uniform rates of consistency for k-nn regression, in Proc. 33rd AAAI Conf. Artificial Intelligence (AAAI, 2019). Google Scholar
18. A. Kontorovich and R. Weiss, Maximum margin multiclass nearest neighbors, in Int. Conf. Machine Learning (2014), pp. 892–900. Google Scholar
19. A. Kontorovich and R. Weiss, A bayes consistent 1-nn classifier, in Artificial Intelligence and Statistics (PMLR, 2015), pp. 480–488. Google Scholar
20. S. Kpotufe, $k$ -nn regression adapts to local intrinsic dimension, in Advances in Neural Information Processing Systems (Curran Associates Inc., 2011), pp. 729–737. Google Scholar
21. A. Locatelli and A. Carpentier, Adaptivity to smoothness in $x$ -armed bandits, in Conf. Learning Theory (2018), pp. 1463–1492. Google Scholar
22. H. N. Mhaskar and T. Poggio. Deep vs. shallow networks: An approximation theory perspective, Anal. Appl. 14(6) (2016) 829–848. Link, Web of Science, Google Scholar
23. Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, 2005). Google Scholar
24. M. A. Osborne, R. Garnett and S. J. Roberts, Gaussian processes for global optimization, in Bayesian Optimization (Springer-Verlag, Berlin, Germany, 2009), pp. 1–15. Google Scholar
25. H. W. J. Reeve and A. Kabán, Classification with unknown class-conditional label noise on non-compact feature spaces, in Proc. 32nd Conf. Learning Theory, Pheonix, Arizona, July 25–28, Vol. 99, Proceedings of Machine Learning Research (PMLR, 2019), pp. 2624–2651. Google Scholar
26. H. W. J. Reeve and A. Kabán, Fast rates for a $k$ nn classifier robust to unknown asymmetric label noise, in Proc. 36th Int. Conf. Machine Learning, Long Beach, California, July 10–15, Vol. 80, Proceedings of Machine Learning Research (PMLR, 2019), pp. 5401–5409. Google Scholar
27. C. Schwab and J. Zech, Deep learning in high dimension: Neural network expression rates for generalized polynomial chaos expansions in UQ, Anal. Appl. 17(1) (2019) 19–55. Link, Web of Science, Google Scholar
28. H. Shimodaira, Improving predictive inference under covariate shift by weighting the log-likelihood function, J. Statist. Plann. Infer. 90(2) (2000) 227–244. Web of Science, Google Scholar
29. A. B. Tsybakov, Optimal aggregation of classifiers in statistical learning, Annals of Statist. 32(1) (2004) 135–166. Web of Science, Google Scholar
30. M. Xu, Q. Fang and Y. Ying, Faster convergence of a randomized coordinate descent method for linearly constrained optimization problems, Anal. Appl. 16(5) (2018) 741–755. Link, Web of Science, Google Scholar
31. D.-X. Zhou, Deep distributed convolutional neural networks: Universality, Anal. Appl. 16(6) (2018) 895–919. Link, Web of Science, Google Scholar