Implicit Regularization for Optimal Sparse Recovery

Abstract

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 ${\ell }_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.

arXiv commentTo appear in NeurIPS 2019

Cited by in corpus (18)

• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• High-Dimensional Linear Regression via Implicit Regularization
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Powerpropagation: A sparsity inducing weight reparameterisation
• Label Noise SGD Provably Prefers Flat Global Minimizers
• On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
• Hadamard Wirtinger Flow for Sparse Phase Retrieval
• Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticity
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Reparameterizing Mirror Descent as Gradient Descent
• Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent
• Iterative regularization for convex regularizers
• Implicit Sparse Regularization: The Impact of Depth and Early Stopping
• Implicit Regularization in Matrix Sensing via Mirror Descent
• A Continuous-Time Mirror Descent Approach to Sparse Phase Retrieval
• Depth Without the Magic: Inductive Bias of Natural Gradient Descent