Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
arXiv:2102.12430
Abstract
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.
References in corpus (14)
- A Convergence Theory for Deep Learning via Over-Parameterization
- On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
- Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
- Essentially No Barriers in Neural Network Energy Landscape
- Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
- Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
- Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
- Gradient descent aligns the layers of deep linear networks
- Understanding the Loss Surface of Neural Networks for Binary Classification
- Spurious Valleys in Two-layer Neural Network Optimization Landscapes
- Shape Matters: Understanding the Implicit Bias of the Noise Covariance
- On Connected Sublevel Sets in Deep Learning