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.
Introduction
In modern deep learning, Stochastic Gradient Descent (SGD) is the standard optimization tool. While noise is often viewed as a byproduct of data sampling, empirical evidence suggests it is a critical component for achieving good generalization. A central question in optimization theory is why this noise helps the algorithm find "better" solutions. This paper addresses this by examining rectangular matrix factorization, a nonconvex problem characterized by scaling invariance. In such landscapes, standard Gradient Descent (GD) is highly sensitive to initialization, often converging to "unbalanced" and "sharp" minima that generalize poorly. We demonstrate that injecting noise into the iterates—a process known as Perturbed GD—implicitly biases the algorithm toward "balanced" global minima, which correspond to flatter and more stable regions of the loss landscape.
The Implicit Bias of Perturbed Gradient Descent
The authors analyze Perturbed GD, where independent Gaussian noise is added to the iterates at each step. Their theoretical framework decomposes the convergence into three distinct phases:
- Phase I (Escape): Noise enables the algorithm to move away from unstable strict saddle points.
- Phase II (Convergence): The algorithm behaves similarly to standard GD, rapidly decreasing the training loss toward zero.
- Phase III (Balancing): Once the loss is minimized, noise becomes the dominant force, "shaking" the iterates along the manifold of global minima until they reach a balanced state where the norms of the factor matrices are proportional to the noise variances.
Mathematically, this process is shown to be equivalent to optimizing a "smoothed" version of the original objective function, where sharp, unbalanced minima are effectively destabilized.
Geometry of Flatness and Noise Regularization
A key insight of this work is that noise acts as an implicit regularizer. Unlike explicit $L_2$ regularization, noise naturally pushes the system toward solutions with a lower Hessian condition number. In these "flat" regions, the bottom of the loss valley is wider, making the solution more robust to perturbations. Sharp minima are inherently unstable under noise because the steep curvature generates large gradients that push the iterates away. Conversely, flat minima are "quieter," allowing the algorithm to settle.
Numerical Results
The researchers validated their theory using synthetic datasets, including rank-1 and rank-10 matrix factorization. The experiments confirmed that while standard GD's final solution is a "slave to its initialization," Perturbed GD consistently converges to the same balanced target regardless of where it starts. This robustness is a direct consequence of the noise-induced implicit bias.
Conclusion
This work provides a rigorous theoretical link between algorithmic noise and the convergence to flat minima in nonconvex optimization. By showing that noise uniquely determines the global optimum in matrix factorization, the authors offer a compelling explanation for why the inherent messiness of stochastic optimization is a feature that promotes stability and generalization. Future work remains to extend these findings to more complex architectures like Transformers and non-linear networks.
Summary updated