Stochasticity of Deterministic Gradient Descent: Large Learning Rate for Multiscale Objective Function

Abstract

This article suggests that deterministic Gradient Descent, which does not use any stochastic gradient approximation, can still exhibit stochastic behaviors. In particular, it shows that if the objective function exhibit multiscale behaviors, then in a large learning rate regime which only resolves the macroscopic but not the microscopic details of the objective, the deterministic GD dynamics can become chaotic and convergent not to a local minimizer but to a statistical distribution. A sufficient condition is also established for approximating this long-time statistical limit by a rescaled Gibbs distribution. Both theoretical and numerical demonstrations are provided, and the theoretical part relies on the construction of a stochastic map that uses bounded noise (as opposed to discretized diffusions).

arXiv commentNeurIPS 2020. v1->v2: Weakened conditions needed for the theory. Added connections to neural network. Corrected typo

References in corpus (17)

• A Convergence Theory for Deep Learning via Over-Parameterization
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Three Factors Influencing Minima in SGD
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Essentially No Barriers in Neural Network Energy Landscape
• Sharp Minima Can Generalize For Deep Nets
• A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Norm-Based Capacity Control in Neural Networks
• The large learning rate phase of deep learning: the catapult mechanism
• Is There an Analog of Nesterov Acceleration for MCMC?
• On the Local Minima of the Empirical Risk
• Two results on entropy, chaos, and independence in symbolic dynamics