# More is Less: Inducing Sparsity via Overparameterization arXiv: https://arxiv.org/abs/2112.11027 · HTML: https://mlsanity.com/paper/2112.11027/ ## Key facts - Cited by 24 papers in the map (data through 14 Oct 2026). - Builds on 23 of its 35 references that are in the map. - First posted on arXiv 21 Dec 2021. ## Builds on (most cited first, 23 of 23) - [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016) - [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017) - [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019) - [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014) - [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017) - [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020) - [On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization](https://mlsanity.com/paper/1802.06509/) (2018) - [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018) - [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019) - [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020) - [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019) - [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021) - [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) - [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021) - [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021) - [Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank](https://mlsanity.com/paper/2011.13772/) (2020) - [Geometry of Optimization and Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1705.03071/) (2017) - [Implicit Sparse Regularization: The Impact of Depth and Early Stopping](https://mlsanity.com/paper/2108.05574/) (2021) - [Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent](https://mlsanity.com/paper/2004.01025/) (2020) - [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021) - [A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval](https://mlsanity.com/paper/2010.10168/) (2020) - [Hadamard Wirtinger Flow for Sparse Phase Retrieval](https://mlsanity.com/paper/2006.01065/) (2020) ## Built on by (most cited first, 24 of 24) - [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022) - [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022) - [Incremental Learning in Diagonal Linear Networks](https://mlsanity.com/paper/2208.14673/) (2022) - [Implicit Regularization in Hierarchical Tensor Factorization and Deep Convolutional Neural Networks](https://mlsanity.com/paper/2201.11729/) (2022) - [Implicit Regularization of Gradient Flow on One-Layer Softmax Attention](https://mlsanity.com/paper/2403.08699/) (2024) - [Robust Implicit Regularization via Weight Normalization](https://mlsanity.com/paper/2305.05448/) (2023) - [Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization](https://mlsanity.com/paper/2307.03571/) (2023) - [Implicit Regularization for Group Sparsity](https://mlsanity.com/paper/2301.12540/) (2023) - [Balance is Essence: Accelerating Sparse Training via Adaptive Gradient Correction](https://mlsanity.com/paper/2301.03573/) (2023) - [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023) - [FTMixer: Frequency and Time Domain Representations Fusion for Time Series Modeling](https://mlsanity.com/paper/2405.15256/) (2024) - [Diagonal Linear Networks and the Lasso Regularization Path](https://mlsanity.com/paper/2509.18766/) (2025) - [Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solution](https://mlsanity.com/paper/2207.07612/) (2022) - [From NeurODEs to AutoencODEs: a mean-field control framework for width-varying Neural Networks](https://mlsanity.com/paper/2307.02279/) (2023) - [Implicit Bias of Mirror Flow in Homogeneous Neural Networks: Sparse and Dense Feature Learning](https://mlsanity.com/paper/2605.19458/) (2026) - [Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks](https://mlsanity.com/paper/2406.02769/) (2024) - [Optimization Insights into Deep Diagonal Linear Networks](https://mlsanity.com/paper/2412.16765/) (2024) - [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023) - [Convex optimization over a probability simplex](https://mlsanity.com/paper/2305.09046/) (2023) - [Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias](https://mlsanity.com/paper/2505.02614/) (2025) - [Tuning-Free Structured Sparse Recovery of Multiple Measurement Vectors using Implicit Regularization](https://mlsanity.com/paper/2512.03393/) (2025) - [Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate](https://mlsanity.com/paper/2605.25134/) (2026) - [Mind the Drift: Diagonal Linear Networks Under Large Learning Rates](https://mlsanity.com/paper/2610.06120/) (2026) - [From Parallel to Sequential: Small-Batch Noise Restores Simplicity Bias of Muon](https://mlsanity.com/paper/2610.16868/) (2026) ## Abstract (arXiv) In deep learning it is common to overparameterize neural networks, that is, to use more parameters than training samples. Quite surprisingly training the neural network via (stochastic) gradient descent leads to models that generalize very well, while classical statistics would suggest overfitting. In order to gain understanding of this implicit bias phenomenon we study the special case of sparse recovery (compressed sensing) which is of interest on its own. More precisely, in order to reconstruct a vector from underdetermined linear measurements, we introduce a corresponding overparameterized square loss functional, where the vector to be reconstructed is deeply factorized into several vectors. We show that, if there exists an exact solution, vanilla gradient flow for the overparameterized loss functional converges to a good approximation of the solution of minimal ℓ1-norm. The latter is well-known to promote sparse solutions. As a by-product, our results significantly improve the sample complexity for compressed sensing via gradient flow/descent on overparameterized models derived in previous works. The theory accurately predicts the recovery rate in numerical experiments. Our proof relies on analyzing a certain Bregman divergence of the flow. This bypasses the obstacles caused by non-convexity and should be of independent interest.