mlsanityData to 7 Oct 2026

Optimistic Rates: A Unifying Theory for Interpolation Learning and Regularization in Linear Regression

arXiv 2112.04470 ↗First posted 8 Dec 2021stat.ML cs.LG math.STcited by 17

Not on the map. Why?

Abstract (arXiv)

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 logarithmic factor in existing results, which are known to be crucial in high-dimensional settings, especially for understanding interpolation learning. As a special case, our analysis recovers the guarantee from Koehler et al. (2021), which tightly characterizes the population risk of low-norm interpolators under the benign overfitting conditions. Our optimistic rate bound, though, also analyzes predictors with arbitrary training error. This allows us to recover some classical statistical guarantees for ridge and LASSO regression under random designs, and helps us obtain a precise understanding of the excess risk of near-interpolators in the over-parameterized regime.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 22 of its 52 references that are in the map. First posted on arXiv 8 Dec 2021.

Builds on

22 of 52 references.

References · 22

  1. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
  6. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  7. 2019Two models of double descent for weak featurescited by 194
  8. 2020Benign overfitting in ridge regressioncited by 152
  9. 2019Harmless interpolation of noisy data in regressioncited by 121
  10. 2018Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolatecited by 99
  11. 2019A Model of Double Descent for High-dimensional Binary Linear Classificationcited by 81
  12. 2021Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfittingcited by 54
10 more
  1. 2014Learning without Concentrationcited by 50
  2. 2019In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictorscited by 44
  3. 2020A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifierscited by 44
  4. 2013A framework to characterize performance of LASSO algorithmscited by 38
  5. 2020Failures of model-dependent generalization bounds for least-norm interpolationcited by 26
  6. 2020On Uniform Convergence and Low-Norm Interpolation Learningcited by 24
  7. 2021Foolish Crowds Support Benign Overfittingcited by 24
  8. 2015Universality laws for randomized dimension reduction, with applicationscited by 21
  9. 2021On the Power of Preconditioning in Sparse Linear Regressioncited by 15
  10. 2020Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degreecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 6; 2024: 3; 2025: 2; 2026: 1.

17 papers.

Sort:

By area:

  1. 2022The Implicit Bias of Benign Overfittingcited by 38
  2. 2022Pre-trained Perceptual Features Improve Differentially Private Image Generationcited by 28
  3. 2022Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Biascited by 21
  4. 2023From Tempered to Benign Overfitting in ReLU Neural Networkscited by 16
  5. 2023Regularization and Optimal Multiclass Learningcited by 15
  6. 2022A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Modelscited by 11
  7. 2023Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuroncited by 8
  8. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  9. 2023Feature Adaptation for Sparse Linear Regressioncited by 6
  10. 2023An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regressioncited by 5
  11. 2024Optimistic Rates for Learning from Label Proportionscited by 5
  12. 2024Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gapscited by 4
5 more
  1. 2025Beyond Benign Overfitting in Nadaraya-Watson Interpolatorscited by 2
  2. 2024Generalizability of Memorization Neural Networkscited by 1
  3. 2022Tight bounds for maximum ℓ1-margin classifierscited by 0
  4. 2025Sparse Linear Regression is Easy on Random Supportscited by 0
  5. 2026Tail-Aware Information-Theoretic Bounds for LLM Alignment under Heavy-Tailed Rewardscited by 0