Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
We consider interpolation learning in high-dimensional linear regression with Gaussian data, and prove a generic uniform convergence guarantee on the generalization error of interpolators in an arbitrary hypothesis class in terms of the class's Gaussian width. Applying the generic bound to Euclidean norm balls recovers the consistency result of Bartlett et al. (2020) for minimum-norm interpolators, and confirms a prediction of Zhou et al. (2020) for near-minimal-norm interpolators in the special case of Gaussian data. We demonstrate the generality of the bound by applying it to the simplex, obtaining a novel consistency result for minimum l1-norm interpolators (basis pursuit). Our results show how norm-based generalization bounds can explain and be used to analyze benign overfitting, at least in some settings.
Code (0)
등록된 구현이 없습니다.
Tasks
Generalization BoundsregressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds and Benign Overfitting
We consider interpolation learning in high-dimensional linear regression with Gaussian data, and prove a generic uniform convergence guarantee on the generalization error of interpolators in an arbitrary hypothesis class…
Generalization BoundsregressionExact Gap between Generalization Error and Uniform Convergence in Random Feature Models
Recent work showed that there could be a large gap between the classical uniform convergence bound and the actual test error of zero-training-error predictors (interpolators) such as deep neural networks. To better under…
Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression
We study a localized notion of uniform convergence known as an "optimistic rate" (Panchenko 2002; Srebro et al. 2010) for linear regression with Gaussian data. Our refined analysis avoids the hidden constant and logarith…
regressionUniform convergence for Gaussian kernel ridge regression
This paper establishes the first polynomial convergence rates for Gaussian kernel ridge regression (KRR) with a fixed hyperparameter in both the uniform and the $L^{2}$-norm. The uniform convergence result closes a gap i…
A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models
We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss $\ell$ can control the test err…
LEMMA