# Implicit Regularization Leads to Benign Overfitting for Sparse Linear Regression

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 1 Feb 2023.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (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)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [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)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Harmless interpolation of noisy data in regression](https://mlsanity.com/paper/1903.09139/) (2019)
- [On the Implicit Bias in Deep-Learning Algorithms](https://mlsanity.com/paper/2208.12591/) (2022)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [A Unifying View on Implicit Bias in Training Linear Neural Networks](https://mlsanity.com/paper/2010.02501/) (2020)
- [On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent](https://mlsanity.com/paper/2102.09769/) (2021)
- [The Implicit Bias of Depth: How Incremental Learning Drives Generalization](https://mlsanity.com/paper/1909.12051/) (2019)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting](https://mlsanity.com/paper/2106.09276/) (2021)
- [Implicit Regularization Towards Rank Minimization in ReLU Networks](https://mlsanity.com/paper/2201.12760/) (2022)
- [Implicit Bias in Leaky ReLU Networks Trained on High-Dimensional Data](https://mlsanity.com/paper/2210.07082/) (2022)
- [In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors](https://mlsanity.com/paper/1912.04265/) (2019)
- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [Implicit Sparse Regularization: The Impact of Depth and Early Stopping](https://mlsanity.com/paper/2108.05574/) (2021)

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

- [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024)
- [FTMixer: Frequency and Time Domain Representations Fusion for Time Series Modeling](https://mlsanity.com/paper/2405.15256/) (2024)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [Implicit Regularization for Multi-label Feature Selection](https://mlsanity.com/paper/2411.11436/) (2024)

## Abstract (arXiv)

In deep learning, often the training process finds an interpolator (a solution with 0 training loss), but the test loss is still low. This phenomenon, known as benign overfitting, is a major mystery that received a lot of recent attention. One common mechanism for benign overfitting is implicit regularization, where the training process leads to additional properties for the interpolator, often characterized by minimizing certain norms. However, even for a simple sparse linear regression problem y = β*top x +xi with sparse β^*, neither minimum ℓ1 or ℓ2 norm interpolator gives the optimal test loss. In this work, we give a different parametrization of the model which leads to a new implicit regularization effect that combines the benefit of ℓ1 and ℓ2 interpolators. We show that training our new model via gradient descent leads to an interpolator with near-optimal test loss. Our result is based on careful analysis of the training dynamics and provides another example of implicit regularization effect that goes beyond norm minimization.