# Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 76 references that are in the map.
- First posted on arXiv 24 Mar 2023.

## Builds on (most cited first, 30 of 32)

- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks](https://mlsanity.com/paper/1810.02281/) (2018)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning](https://mlsanity.com/paper/2012.09839/) (2020)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Implicit Regularization in Deep Learning May Not Be Explainable by Norms](https://mlsanity.com/paper/2005.06398/) (2020)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [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)
- [A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1702.05575/) (2017)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Gradient Descent for Deep Matrix Factorization: Dynamics and Implicit Bias towards Low Rank](https://mlsanity.com/paper/2011.13772/) (2020)
- [Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing](https://mlsanity.com/paper/2301.11500/) (2023)
- [Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent](https://mlsanity.com/paper/2207.04036/) (2022)
- [Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorization](https://mlsanity.com/paper/2203.02839/) (2022)
- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Sharp Restricted Isometry Bounds for the Inexistence of Spurious Local Minima in Nonconvex Matrix Recovery](https://mlsanity.com/paper/1901.01631/) (2019)
- [More is Less: Inducing Sparsity via Overparameterization](https://mlsanity.com/paper/2112.11027/) (2021)
- [Convergence of gradient descent for learning linear neural networks](https://mlsanity.com/paper/2108.02040/) (2021)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [On the Global Convergence of Gradient Descent for multi-layer ResNets in the mean-field regime](https://mlsanity.com/paper/2110.02926/) (2021)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensing](https://mlsanity.com/paper/2204.11516/) (2022)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations](https://mlsanity.com/paper/1712.09203/) (2017)

## Abstract (arXiv)

Recently, there has been significant progress in understanding the convergence and generalization properties of gradient-based methods for training overparameterized learning models. However, many aspects including the role of small random initialization and how the various parameters of the model are coupled during gradient-based updates to facilitate good generalization remain largely mysterious. A series of recent papers have begun to study this role for non-convex formulations of symmetric Positive Semi-Definite (PSD) matrix sensing problems which involve reconstructing a low-rank PSD matrix from a few linear measurements. The underlying symmetry/PSDness is crucial to existing convergence and generalization guarantees for this problem. In this paper, we study a general overparameterized low-rank matrix sensing problem where one wishes to reconstruct an asymmetric rectangular low-rank matrix from a few linear measurements. We prove that an overparameterized model trained via factorized gradient descent converges to the low-rank matrix generating the measurements. We show that in this setting, factorized gradient descent enjoys two implicit properties: (1) coupling of the trajectory of gradient descent where the factors are coupled in various ways throughout the gradient update trajectory and (2) an algorithmic regularization property where the iterates show a propensity towards low-rank models despite the overparameterized nature of the factorized model. These two implicit properties in turn allow us to show that the gradient descent trajectory from small random initialization moves towards solutions that are both globally optimal and generalize well.