Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction

Abstract

Recently there has been significant theoretical progress on understanding the convergence and generalization of gradient-based methods on nonconvex losses with overparameterized models. Nevertheless, many aspects of optimization and generalization and in particular the critical role of small random initialization are not fully understood. In this paper, we take a step towards demystifying this role by proving that small random initialization followed by a few iterations of gradient descent behaves akin to popular spectral methods. We also show that this implicit spectral bias from small random initialization, which is provably more prominent for overparameterized models, also puts the gradient descent iterations on a particular trajectory towards solutions that are not only globally optimal but also generalize well. Concretely, we focus on the problem of reconstructing a low-rank matrix from a few measurements via a natural nonconvex formulation. In this setting, we show that the trajectory of the gradient descent iterations from small random initialization can be approximately decomposed into three phases: (I) a spectral or alignment phase where we show that that the iterates have an implicit spectral bias akin to spectral initialization allowing us to show that at the end of this phase the column space of the iterates and the underlying low-rank matrix are sufficiently aligned, (II) a saddle avoidance/refinement phase where we show that the trajectory of the gradient iterates moves away from certain degenerate saddle points, and (III) a local refinement phase where we show that after avoiding the saddles the iterates converge quickly to the underlying low-rank matrix. Underlying our analysis are insights for the analysis of overparameterized nonconvex optimization schemes that may have implications for computational problems beyond low-rank reconstruction.

arXiv comment83 pages; published in NeurIPS 2021; corrected inaccuracies in the proofs of Lemma 9.5 and Theorem 9.6

References in corpus (15)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• An overview of low-rank matrix recovery from incomplete observations
• On Lazy Training in Differentiable Programming
• Global Optimality of Local Search for Low Rank Matrix Recovery
• How to Escape Saddle Points Efficiently
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• When Are Nonconvex Problems Not Scary?
• A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks
• When Do Neural Networks Outperform Kernel Methods?
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Implicit Bias of Gradient Descent on Linear Convolutional Networks
• Fast Global Convergence for Low-rank Matrix Recovery via Riemannian Gradient Descent with Random Initialization
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK

Cited by in corpus (4)

• Quantum State Tomography for Matrix Product Density Operators
• Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent
• Robust Implicit Regularization via Weight Normalization
• Neural Networks as Kernel Learners: The Silent Alignment Effect