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

arXiv: https://arxiv.org/abs/2112.04470 · HTML: https://mlsanity.com/paper/2112.04470/

## Key facts

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

## Builds on (most cited first, 22 of 22)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate](https://mlsanity.com/paper/1806.05161/) (2018)
- [A Model of Double Descent for High-dimensional Binary Linear Classification](https://mlsanity.com/paper/1911.05822/) (2019)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Learning without Concentration](https://mlsanity.com/paper/1401.0304/) (2014)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [Failures of model-dependent generalization bounds for least-norm interpolation](https://mlsanity.com/paper/2010.08479/) (2020)
- [On Uniform Convergence and Low-Norm Interpolation Learning](https://mlsanity.com/paper/2006.05942/) (2020)
- [Foolish Crowds Support Benign Overfitting](https://mlsanity.com/paper/2110.02914/) (2021)
- [Universality laws for randomized dimension reduction, with applications](https://mlsanity.com/paper/1511.09433/) (2015)
- [On the Power of Preconditioning in Sparse Linear Regression](https://mlsanity.com/paper/2106.09207/) (2021)
- [Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree](https://mlsanity.com/paper/2002.00492/) (2020)

## Built on by (most cited first, 17 of 17)

- [The Implicit Bias of Benign Overfitting](https://mlsanity.com/paper/2201.11489/) (2022)
- [Pre-trained Perceptual Features Improve Differentially Private Image Generation](https://mlsanity.com/paper/2205.12900/) (2022)
- [Fast Rates for Noisy Interpolation Require Rethinking the Effects of Inductive Bias](https://mlsanity.com/paper/2203.03597/) (2022)
- [From Tempered to Benign Overfitting in ReLU Neural Networks](https://mlsanity.com/paper/2305.15141/) (2023)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models](https://mlsanity.com/paper/2210.12082/) (2022)
- [Finite-Sample Analysis of Learning High-Dimensional Single ReLU Neuron](https://mlsanity.com/paper/2303.02255/) (2023)
- [Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimization](https://mlsanity.com/paper/2303.10758/) (2023)
- [Feature Adaptation for Sparse Linear Regression](https://mlsanity.com/paper/2305.16892/) (2023)
- [An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression](https://mlsanity.com/paper/2306.13185/) (2023)
- [Optimistic Rates for Learning from Label Proportions](https://mlsanity.com/paper/2406.00487/) (2024)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Beyond Benign Overfitting in Nadaraya-Watson Interpolators](https://mlsanity.com/paper/2502.07480/) (2025)
- [Generalizability of Memorization Neural Networks](https://mlsanity.com/paper/2411.00372/) (2024)
- [Tight bounds for maximum ℓ1-margin classifiers](https://mlsanity.com/paper/2212.03783/) (2022)
- [Sparse Linear Regression is Easy on Random Supports](https://mlsanity.com/paper/2511.06211/) (2025)
- [Tail-Aware Information-Theoretic Bounds for LLM Alignment under Heavy-Tailed Rewards](https://mlsanity.com/paper/2604.10727/) (2026)

## 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.