Minimum ${\ell }_1$-norm interpolators: Precise asymptotics and multiple descent

Abstract

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 ${\ell }_1$-norm interpolator, which is motivated by the observation that several learning algorithms favor low ${\ell }_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 ${\ell }_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 ${\ell }_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 ${\ell }_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.

References in corpus (16)

• Simultaneous analysis of Lasso and Dantzig selector
• Message Passing Algorithms for Compressed Sensing
• Reconciling modern machine learning practice and the bias-variance trade-off
• Universality in polytope phase transitions and message passing algorithms
• Optimal Errors and Phase Transitions in High-Dimensional Generalized Linear Models
• A framework to characterize performance of LASSO algorithms
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Optimal Regularization Can Mitigate Double Descent
• The Lasso with general Gaussian designs with applications to hypothesis testing
• Asymptotic Mutual Information for the Two-Groups Stochastic Block Model
• The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization
• Understanding overfitting peaks in generalization error: Analytical risk curves for $l_2$ and $l_1$ penalized interpolation
• Multiple Descent: Design Your Own Generalization Curve
• Overfitting Can Be Harmless for Basis Pursuit, But Only to a Degree
• Approximate Message Passing for orthogonally invariant ensembles: Multivariate non-linearities and spectral initialization
• Local convexity of the TAP free energy and AMP convergence for Z2-synchronization

Cited by in corpus (2)

• Multiple Descent: Design Your Own Generalization Curve
• Tight bounds for minimum l1-norm interpolation of noisy data