Harmless interpolation in regression and classification with structured features

Andrew D. Mcrae, Santhosh Karnik, Mark Davenport, Vidya K. Muthukumar
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:5853-5875, 2022.

Abstract

Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-mcrae22a, title = { Harmless interpolation in regression and classification with structured features }, author = {Mcrae, Andrew D. and Karnik, Santhosh and Davenport, Mark and Muthukumar, Vidya K.}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {5853--5875}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/mcrae22a/mcrae22a.pdf}, url = {https://proceedings.mlr.press/v151/mcrae22a.html}, abstract = { Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features. } }
Endnote
%0 Conference Paper %T Harmless interpolation in regression and classification with structured features %A Andrew D. Mcrae %A Santhosh Karnik %A Mark Davenport %A Vidya K. Muthukumar %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-mcrae22a %I PMLR %P 5853--5875 %U https://proceedings.mlr.press/v151/mcrae22a.html %V 151 %X Overparametrized neural networks tend to perfectly fit noisy training data yet generalize well on test data. Inspired by this empirical observation, recent work has sought to understand this phenomenon of benign overfitting or harmless interpolation in the much simpler linear model. Previous theoretical work critically assumes that either the data features are statistically independent or the input data is high-dimensional; this precludes general nonparametric settings with structured feature maps. In this paper, we present a general and flexible framework for upper bounding regression and classification risk in a reproducing kernel Hilbert space. A key contribution is that our framework describes precise sufficient conditions on the data Gram matrix under which harmless interpolation occurs. Our results recover prior independent-features results (with a much simpler analysis), but they furthermore show that harmless interpolation can occur in more general settings such as features that are a bounded orthonormal system. Furthermore, our results show an asymptotic separation between classification and regression performance in a manner that was previously only shown for Gaussian features.
APA
Mcrae, A.D., Karnik, S., Davenport, M. & Muthukumar, V.K.. (2022). Harmless interpolation in regression and classification with structured features . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:5853-5875 Available from https://proceedings.mlr.press/v151/mcrae22a.html.

Related Material