# Minimum ℓ1-norm interpolators: Precise asymptotics and multiple descent

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 81 references that are in the map.
- First posted on arXiv 18 Oct 2021.

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

- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Deep learning: a statistical viewpoint](https://mlsanity.com/paper/2103.09177/) (2021)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Optimal Regularization Can Mitigate Double Descent](https://mlsanity.com/paper/2003.01897/) (2020)
- [Triple descent and the two kinds of overfitting: Where & why do they appear?](https://mlsanity.com/paper/2006.03509/) (2020)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Multiple Descent: Design Your Own Generalization Curve](https://mlsanity.com/paper/2008.01036/) (2020)
- [A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-ℓ1-Norm Interpolated Classifiers](https://mlsanity.com/paper/2002.01586/) (2020)
- [Estimation of Low-Rank Matrices via Approximate Message Passing](https://mlsanity.com/paper/1711.01682/) (2017)
- [A framework to characterize performance of LASSO algorithms](https://mlsanity.com/paper/1303.7291/) (2013)
- [The Lasso with general Gaussian designs with applications to hypothesis testing](https://mlsanity.com/paper/2007.13716/) (2020)
- [Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation](https://mlsanity.com/paper/1906.03667/) (2019)
- [Finite Sample Analysis of Approximate Message Passing Algorithms](https://mlsanity.com/paper/1606.01800/) (2016)
- [On the robustness of minimum norm interpolators and regularized empirical risk minimizers](https://mlsanity.com/paper/2012.00807/) (2020)
- [Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization](https://mlsanity.com/paper/2110.02318/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing](https://mlsanity.com/paper/1907.07502/) (2019)
- [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, 7 of 7)

- [Mitigating multiple descents: A model-agnostic framework for risk monotonization](https://mlsanity.com/paper/2205.12937/) (2022)
- [A New Central Limit Theorem for the Augmented IPW Estimator: Variance Inflation, Cross-Fit Covariance and Beyond](https://mlsanity.com/paper/2205.10198/) (2022)
- [A non-asymptotic distributional theory of approximate message passing for sparse and robust regression](https://mlsanity.com/paper/2401.03923/) (2024)
- [Approximate Leave-one-out Cross Validation for Regression with ℓ1 Regularizers (extended version)](https://mlsanity.com/paper/2310.17629/) (2023)
- [Revisiting Optimism and Model Complexity in the Wake of Overparameterized Machine Learning](https://mlsanity.com/paper/2410.01259/) (2024)
- [How abundant are good interpolators?](https://mlsanity.com/paper/2606.06469/) (2026)
- [Grokking through the Lens of Minimum-Norm Interpolation](https://mlsanity.com/paper/2609.38453/) (2026)

## Abstract (arXiv)

An evolving line of machine learning works observe empirical evidence that suggests interpolating estimators -- the ones that achieve zero training error -- may not necessarily be harmful. This paper pursues theoretical understanding for an important type of interpolators: the minimum ℓ1-norm interpolator, which is motivated by the observation that several learning algorithms favor low ℓ1-norm solutions in the over-parameterized regime. Concretely, we consider the noisy sparse regression model under Gaussian design, focusing on linear sparsity and high-dimensional asymptotics (so that both the number of features and the sparsity level scale proportionally with the sample size). We observe, and provide rigorous theoretical justification for, a curious multi-descent phenomenon; that is, the generalization risk of the minimum ℓ1-norm interpolator undergoes multiple (and possibly more than two) phases of descent and ascent as one increases the model capacity. This phenomenon stems from the special structure of the minimum ℓ1-norm interpolator as well as the delicate interplay between the over-parameterized ratio and the sparsity, thus unveiling a fundamental distinction in geometry from the minimum ℓ2-norm interpolator. Our finding is built upon an exact characterization of the risk behavior, which is governed by a system of two non-linear equations with two unknowns.