mlsanityData to 14 Oct 2026

Implicit Regularization in Matrix Sensing via Mirror Descent

arXiv 2105.13831 ↗First posted 28 May 2021stat.ML cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

We study discrete-time mirror descent applied to the unregularized empirical risk in matrix sensing. In both the general case of rectangular matrices and the particular case of positive semidefinite matrices, a simple potential-based analysis in terms of the Bregman divergence allows us to establish convergence of mirror descent -- with different choices of the mirror maps -- to a matrix that, among all global minimizers of the empirical risk, minimizes a quantity explicitly related to the nuclear norm, the Frobenius norm, and the von Neumann entropy. In both cases, this characterization implies that mirror descent, a first-order algorithm minimizing the unregularized empirical risk, recovers low-rank matrices under the same set of assumptions that are sufficient to guarantee recovery for nuclear-norm minimization. When the sensing matrices are symmetric and commute, we show that gradient descent with full-rank factorized parametrization is a first-order approximation to mirror descent, in which case we obtain an explicit characterization of the implicit bias of gradient flow as a by-product.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 21 of its 56 references that are in the map. First posted on arXiv 28 May 2021.

Builds on

21 of 56 references.

References · 21

  1. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  2. 2017Implicit Regularization in Matrix Factorizationcited by 322
  3. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  4. 2018Characterizing Implicit Bias in Terms of Optimization Geometrycited by 266
  5. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 160
  6. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  7. 2020Implicit Regularization in Deep Learning May Not Be Explainable by Normscited by 119
  8. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  9. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 82
  10. 2019Implicit Regularization for Optimal Sparse Recoverycited by 80
  11. 2020A Unifying View on Implicit Bias in Training Linear Neural Networkscited by 75
  12. 2020Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracycited by 71
9 more
  1. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 70
  2. 2021On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descentcited by 70
  3. 2019The Implicit Bias of Depth: How Incremental Learning Drives Generalizationcited by 64
  4. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 39
  5. 2019Exponentiated Gradient Meets Gradient Descentcited by 32
  6. 2020The Statistical Complexity of Early-Stopped Mirror Descentcited by 19
  7. 2016Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descentcited by 15
  8. 2020A Continuous-Time Mirror Descent Approach to Sparse Phase Retrievalcited by 9
  9. 2021Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descentcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 0; 2023: 3; 2024: 1; 2025: 2; 2026: 3.

11 papers.

  1. 2021More is Less: Inducing Sparsity via Overparameterizationcited by 24
  2. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  3. 2025Mirror, Mirror of the Flow: How Does Regularization Shape Implicit Bias?cited by 12
  4. 2024Implicit Bias of Mirror Flow on Separable Datacited by 9
  5. 2021Implicit Regularization of Bregman Proximal Point Algorithm and Mirror Descent on Separable Datacited by 6
  6. 2023Combining Explicit and Implicit Regularization for Efficient Learning in Deep Networkscited by 4
  7. 2026Implicit Bias of Mirror Flow in Homogeneous Neural Networks: Sparse and Dense Feature Learningcited by 3
  8. 2026The Spectral Dynamics and Noise Geometry of Muoncited by 3
  9. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  10. 2023Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensingcited by 0
  11. 2025Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Biascited by 0