mlsanityData to 7 Oct 2026

Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization

arXiv 2102.12430 ↗First posted 24 Feb 2021cs.LG stat.MLcited by 15

Not on the map. Why?

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.

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

Builds on

28 of 40 references.

References · 28

  1. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNscited by 585
  4. 2018Essentially No Barriers in Neural Network Energy Landscapecited by 328
  5. 2017How to Escape Saddle Points Efficientlycited by 284
  6. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  7. 2016Deep Learning without Poor Local Minimacited by 233
  8. 2018Gradient descent aligns the layers of deep linear networkscited by 182
  9. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  10. 2019Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networkscited by 162
  11. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  12. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
16 more
  1. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  2. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  3. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  4. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  5. 2017The loss surface of deep and wide neural networkscited by 74
  6. 2015Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guaranteescited by 68
  7. 2019Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Netscited by 63
  8. 2018Towards Understanding Regularization in Batch Normalizationcited by 56
  9. 2019On Connected Sublevel Sets in Deep Learningcited by 51
  10. 2015Dropping Convexity for Faster Semi-definite Optimizationcited by 40
  11. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 37
  12. 2013Understanding Alternating Minimization for Matrix Completioncited by 32
  13. 2018Understanding the Loss Surface of Neural Networks for Binary Classificationcited by 27
  14. 2018Spurious Valleys in Two-layer Neural Network Optimization Landscapescited by 20
  15. 2019Towards Understanding the Importance of Noise in Training Neural Networkscited by 10
  16. 2017Optimization Landscape and Expressivity of Deep CNNscited by 2

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 4; 2023: 0; 2024: 4; 2025: 4.

15 papers.

Sort:

By area:

  1. 2021Large Learning Rate Tames Homogeneity: Convergence and Balancing Effectcited by 48
  2. 2021Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorizationcited by 44
  3. 2022How Much Data Are Augmentations Worth? An Investigation into Scaling Laws, Invariance, and Implicit Regularizationcited by 40
  4. 2022Flat minima generalize for low-rank matrix recoverycited by 28
  5. 2022Explicit Regularization in Overparametrized Models via Noise Injectioncited by 25
  6. 2022Uniform-in-time propagation of chaos for mean field Langevin dynamicscited by 23
  7. 2024Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Modelscited by 11
  8. 2021Statistical limits of dictionary learning: random matrix theory and the spectral replica methodcited by 10
  9. 2024Demystifying SGD with Doubly Stochastic Gradientscited by 2
  10. 2025Generalization Bounds for Markov Algorithms through Entropy Flow Computationscited by 2
  11. 2025Sharpness of Minima in Deep Matrix Factorizationcited by 2
  12. 2024On subdifferential chain rule of matrix factorization and beyondcited by 0
3 more
  1. 2024SGD Jittering: A Training Strategy for Robust and Accurate Model-Based Architecturescited by 0
  2. 2025Unpacking the Implicit Norm Dynamics of Sharpness-Aware Minimization in Tensorized Modelscited by 0
  3. 2025A Saddle Point Remedy: Power of Variable Elimination in Non-convex Optimizationcited by 0