Asymptotic Analysis via Stochastic Differential Equations of Gradient Descent Algorithms in Statistical and Computational Paradigms

Abstract

This paper investigates asymptotic behaviors of gradient descent algorithms (particularly accelerated gradient descent and stochastic gradient descent) in the context of stochastic optimization arising in statistics and machine learning where objective functions are estimated from available data. We show that these algorithms can be computationally modeled by continuous-time ordinary or stochastic differential equations. We establish gradient flow central limit theorems to describe the limiting dynamic behaviors of these computational algorithms and the large-sample performances of the related statistical procedures, as the number of algorithm iterations and data size both go to infinity, where the gradient flow central limit theorems are governed by some linear ordinary or stochastic differential equations like time-dependent Ornstein-Uhlenbeck processes. We illustrate that our study can provide a novel unified framework for a joint computational and statistical asymptotic analysis, where the computational asymptotic analysis studies dynamic behaviors of these algorithms with the time (or the number of iterations in the algorithms), the statistical asymptotic analysis investigates large sample behaviors of the statistical procedures (like estimators and classifiers) that the algorithms are applied to compute, and in fact the statistical procedures are equal to the limits of the random sequences generated from these iterative algorithms as the number of iterations goes to infinity. The joint analysis results based on the obtained gradient flow central limit theorems can identify four factors - learning rate, batch size, gradient covariance, and Hessian - to derive new theory regarding the local minima found by stochastic gradient descent for solving non-convex optimization problems.

arXiv comment102 pages 2 figure2

References in corpus (20)

• An overview of gradient descent optimization algorithms
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• SLOPE - Adaptive variable selection via convex optimization
• How to Escape Saddle Points Efficiently
• Three Factors Influencing Minima in SGD
• Computational and Statistical Tradeoffs via Convex Relaxation
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• A geometric alternative to Nesterov's accelerated gradient descent
• From Averaging to Acceleration, There is Only a Step-size
• Bridging the Gap between Stochastic Gradient MCMC and Stochastic Optimization
• A Variational Analysis of Stochastic Gradient Algorithms
• On the diffusion approximation of nonconvex stochastic gradient descent
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Stochastic modified equations and adaptive stochastic gradient algorithms
• Online ICA: Understanding Global Dynamics of Nonconvex Optimization via Diffusion Processes
• Statistical inference using SGD
• Diffusion Approximations for Online Principal Component Estimation and Global Convergence

Cited by in corpus (4)

• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• A Diffusion Approximation Theory of Momentum SGD in Nonconvex Optimization
• How Many Factors Influence Minima in SGD?
• SGD Distributional Dynamics of Three Layer Neural Networks