# Implicit Regularization for Optimal Sparse Recovery

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

## Key facts

- Cited by 80 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2019.

## Built on by (most cited first, 30 of 80)

- [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022)
- [Label Noise SGD Provably Prefers Flat Global Minimizers](https://mlsanity.com/paper/2106.06530/) (2021)
- [Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity](https://mlsanity.com/paper/2106.09524/) (2021)
- [What Happens after SGD Reaches Zero Loss? --A Mathematical Framework](https://mlsanity.com/paper/2110.06914/) (2021)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Transformers as Support Vector Machines](https://mlsanity.com/paper/2308.16898/) (2023)
- [On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent](https://mlsanity.com/paper/2102.09769/) (2021)
- [SGD with Large Step Sizes Learns Sparse Features](https://mlsanity.com/paper/2210.05337/) (2022)
- [Max-Margin Token Selection in Attention Mechanism](https://mlsanity.com/paper/2306.13596/) (2023)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Powerpropagation: A sparsity inducing weight reparameterisation](https://mlsanity.com/paper/2110.00296/) (2021)
- [Early Stopping for Deep Image Prior](https://mlsanity.com/paper/2112.06074/) (2021)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [(S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability](https://mlsanity.com/paper/2302.08982/) (2023)
- [Implicit Sparse Regularization: The Impact of Depth and Early Stopping](https://mlsanity.com/paper/2108.05574/) (2021)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisation](https://mlsanity.com/paper/2206.09841/) (2022)
- [Incremental Learning in Diagonal Linear Networks](https://mlsanity.com/paper/2208.14673/) (2022)
- [Explicit Regularization in Overparametrized Models via Noise Injection](https://mlsanity.com/paper/2206.04613/) (2022)
- [More is Less: Inducing Sparsity via Overparameterization](https://mlsanity.com/paper/2112.11027/) (2021)
- [The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods](https://mlsanity.com/paper/2111.07167/) (2021)
- [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024)
- [Mask in the Mirror: Implicit Sparsification](https://mlsanity.com/paper/2408.09966/) (2024)
- [Deep Weight Factorization: Sparse Learning Through the Lens of Artificial Symmetries](https://mlsanity.com/paper/2502.02496/) (2025)
- [Regularize implicit neural representation by itself](https://mlsanity.com/paper/2303.15484/) (2023)
- [Robust Implicit Regularization via Weight Normalization](https://mlsanity.com/paper/2305.05448/) (2023)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Provable Acceleration of Heavy Ball beyond Quadratics for a Class of Polyak-Lojasiewicz Functions when the Non-Convexity is Averaged-Out](https://mlsanity.com/paper/2206.11872/) (2022)

## Abstract (arXiv)

We investigate implicit regularization schemes for gradient descent methods applied to unpenalized least squares regression to solve the problem of reconstructing a sparse signal from an underdetermined system of linear measurements under the restricted isometry assumption. For a given parametrization yielding a non-convex optimization problem, we show that prescribed choices of initialization, step size and stopping time yield a statistically and computationally optimal algorithm that achieves the minimax rate with the same cost required to read the data up to poly-logarithmic factors. Beyond minimax optimality, we show that our algorithm adapts to instance difficulty and yields a dimension-independent rate when the signal-to-noise ratio is high enough. Key to the computational efficiency of our method is an increasing step size scheme that adapts to refined estimates of the true solution. We validate our findings with numerical experiments and compare our algorithm against explicit ℓ1 penalization. Going from hard instances to easy ones, our algorithm is seen to undergo a phase transition, eventually matching least squares with an oracle knowledge of the true support.