# Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 40 references that are in the map.
- First posted on arXiv 24 Feb 2021.

## Builds on (most cited first, 28 of 28)

- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Essentially No Barriers in Neural Network Energy Landscape](https://mlsanity.com/paper/1803.00885/) (2018)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Deep Learning without Poor Local Minima](https://mlsanity.com/paper/1605.07110/) (2016)
- [Gradient descent aligns the layers of deep linear networks](https://mlsanity.com/paper/1810.02032/) (2018)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks](https://mlsanity.com/paper/1907.04595/) (2019)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Matrix Completion has No Spurious Local Minimum](https://mlsanity.com/paper/1605.07272/) (2016)
- [Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process](https://mlsanity.com/paper/1904.09080/) (2019)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Shape Matters: Understanding the Implicit Bias of the Noise Covariance](https://mlsanity.com/paper/2006.08680/) (2020)
- [The loss surface of deep and wide neural networks](https://mlsanity.com/paper/1704.08045/) (2017)
- [Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees](https://mlsanity.com/paper/1509.03025/) (2015)
- [Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets](https://mlsanity.com/paper/1906.06247/) (2019)
- [Towards Understanding Regularization in Batch Normalization](https://mlsanity.com/paper/1809.00846/) (2018)
- [On Connected Sublevel Sets in Deep Learning](https://mlsanity.com/paper/1901.07417/) (2019)
- [Dropping Convexity for Faster Semi-definite Optimization](https://mlsanity.com/paper/1509.03917/) (2015)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [Understanding the Loss Surface of Neural Networks for Binary Classification](https://mlsanity.com/paper/1803.00909/) (2018)
- [Spurious Valleys in Two-layer Neural Network Optimization Landscapes](https://mlsanity.com/paper/1802.06384/) (2018)
- [Towards Understanding the Importance of Noise in Training Neural Networks](https://mlsanity.com/paper/1909.03172/) (2019)
- [Optimization Landscape and Expressivity of Deep CNNs](https://mlsanity.com/paper/1710.10928/) (2017)

## Built on by (most cited first, 15 of 15)

- [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)
- [How Much Data Are Augmentations Worth? An Investigation into Scaling Laws, Invariance, and Implicit Regularization](https://mlsanity.com/paper/2210.06441/) (2022)
- [Flat minima generalize for low-rank matrix recovery](https://mlsanity.com/paper/2203.03756/) (2022)
- [Explicit Regularization in Overparametrized Models via Noise Injection](https://mlsanity.com/paper/2206.04613/) (2022)
- [Uniform-in-time propagation of chaos for mean field Langevin dynamics](https://mlsanity.com/paper/2212.03050/) (2022)
- [Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Models](https://mlsanity.com/paper/2410.06441/) (2024)
- [Statistical limits of dictionary learning: random matrix theory and the spectral replica method](https://mlsanity.com/paper/2109.06610/) (2021)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [Generalization Bounds for Markov Algorithms through Entropy Flow Computations](https://mlsanity.com/paper/2502.07584/) (2025)
- [Sharpness of Minima in Deep Matrix Factorization](https://mlsanity.com/paper/2509.25783/) (2025)
- [On subdifferential chain rule of matrix factorization and beyond](https://mlsanity.com/paper/2410.05022/) (2024)
- [SGD Jittering: A Training Strategy for Robust and Accurate Model-Based Architectures](https://mlsanity.com/paper/2410.14667/) (2024)
- [Unpacking the Implicit Norm Dynamics of Sharpness-Aware Minimization in Tensorized Models](https://mlsanity.com/paper/2508.10435/) (2025)
- [A Saddle Point Remedy: Power of Variable Elimination in Non-convex Optimization](https://mlsanity.com/paper/2511.01234/) (2025)

## Abstract (arXiv)

Numerous empirical evidences have corroborated the importance of noise in nonconvex optimization problems. The theory behind such empirical observations, however, is still largely unknown. This paper studies this fundamental problem through investigating the nonconvex rectangular matrix factorization problem, which has infinitely many global minima due to rotation and scaling invariance. Hence, gradient descent (GD) can converge to any optimum, depending on the initialization. In contrast, we show that a perturbed form of GD with an arbitrary initialization converges to a global optimum that is uniquely determined by the injected noise. Our result implies that the noise imposes implicit bias towards certain optima. Numerical experiments are provided to support our theory.