Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect

Abstract

Recent empirical advances show that training deep models with large learning rate often improves generalization performance. However, theoretical justifications on the benefits of large learning rate are highly limited, due to challenges in analysis. In this paper, we consider using Gradient Descent (GD) with a large learning rate on a homogeneous matrix factorization problem, i.e., ${\min }_{X,Y}\Vert A-X{Y}^{\top }{\Vert }_{\mathsf{F}}^2$. We prove a convergence theory for constant large learning rates well beyond $2/L$, where $L$ is the largest eigenvalue of Hessian at the initialization. Moreover, we rigorously establish an implicit bias of GD induced by such a large learning rate, termed 'balancing', meaning that magnitudes of $X$ and $Y$ at the limit of GD iterations will be close even if their initialization is significantly unbalanced. Numerical experiments are provided to support our theory.

arXiv comment45 pages

References in corpus (18)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decay
• On the Variance of the Adaptive Learning Rate and Beyond
• Three Factors Influencing Minima in SGD
• A Comparison of Optimization Algorithms for Deep Learning
• 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
• Towards Explaining the Regularization Effect of Initial Large Learning Rate in Training Neural Networks
• Gradient descent aligns the layers of deep linear networks
• The Non-convex Geometry of Low-rank Matrix Optimization
• A Closer Look at Deep Learning Heuristics: Learning rate restarts, Warmup and Distillation
• Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning
• An Exponential Learning Rate Schedule for Deep Learning
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Learning Rate Annealing Can Provably Help Generalization, Even for Convex Problems
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• The Landscape of Matrix Factorization Revisited
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization

Cited by in corpus (1)

• Catapult Dynamics and Phase Transitions in Quadratic Nets