EUVIMEDEUVIMED entdecken
Crossref

Benefit of Interpolation in Nearest Neighbor Algorithms

Yue Xing, Qifan Song, Guang Cheng

SIAM Journal on Mathematics of Data Science · 2022-06 · 4 (2) · 935-956

DOI: 10.1137/21m1437457 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 30.06.2022. Verfasst von Yue Xing und 2 weiteren Autor:innen. Die Arbeit wurde bisher 40-mal zitiert (Crossref) und nennt 43 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In some studies (e.g., [C. Zhang et al. in Proceedings of the 5th International Conference on Learning Representations, OpenReview.net, 2017]) of deep learning, it is observed that overparametrized deep neural networks achieve a small testing error even when the training error is almost zero. Despite numerous works toward understanding this so-called double-descent phenomenon (e.g., [M. Belkin et al., Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 15849--15854; M. Belkin, D. Hsu, and J. Xu, SIAM J. Math. Data Sci., 2 (2020), pp. 1167--1180]), in this paper, we turn to another way to enforce zero training error (without overparametrization) through a data interpolation mechanism. Specifically, we consider a class of interpolated weighting schemes in the nearest neighbors (NN) algorithms. By carefully characterizing the multiplicative constant in the statistical risk, we reveal a U-shaped performance curve for the level of data interpolation in both classification and regression setups. This sharpens the existing result [M. Belkin, A. Rakhlin, and A. B. Tsybakov, in Proceedings of Machine Learning Research 89, PMLR, 2019, pp. 1611--1619] that zero training error does not necessarily jeopardize predictive performances and claims a counterintuitive result that a mild degree of data interpolation actually strictly improves the prediction performance and statistical stability over those of the (uninterpolated) $k$-NN algorithm. In the end, the universality of our results, such as change of distance measure and corrupted testing data, will also be discussed.

Zitieren

APA

Xing, Y., Song, Q., & Cheng, G. (2022). Benefit of Interpolation in Nearest Neighbor Algorithms. SIAM Journal on Mathematics of Data Science, 4(2), 935-956. https://doi.org/10.1137/21m1437457

Vancouver

Xing Y, Song Q, Cheng G. Benefit of Interpolation in Nearest Neighbor Algorithms. SIAM Journal on Mathematics of Data Science. 2022;4(2):935-956. doi:10.1137/21m1437457

BibTeX
@article{Xing2022,
  author = {Xing, Yue and Song, Qifan and Cheng, Guang},
  title = {Benefit of Interpolation in Nearest Neighbor Algorithms},
  journal = {SIAM Journal on Mathematics of Data Science},
  year = {2022},
  volume = {4},
  number = {2},
  pages = {935--956},
  doi = {10.1137/21m1437457}
}
Kostenlos starten →