Uniform-in-Time Weak Error Analysis for Stochastic Gradient Descent Algorithms via Diffusion Approximation

Abstract

Diffusion approximation provides weak approximation for stochastic gradient descent algorithms in a finite time horizon. In this paper, we introduce new tools motivated by the backward error analysis of numerical stochastic differential equations into the theoretical framework of diffusion approximation, extending the validity of the weak approximation from finite to infinite time horizon. The new techniques developed in this paper enable us to characterize the asymptotic behavior of constant-step-size SGD algorithms for strongly convex objective functions, a goal previously unreachable within the diffusion approximation framework. Our analysis builds upon a truncated formal power expansion of the solution of a stochastic modified equation arising from diffusion approximation, where the main technical ingredient is a uniform-in-time weak error bound controlling the long-term behavior of the expansion coefficient functions near the global minimum. We expect these new techniques to greatly expand the range of applicability of diffusion approximation to cover wider and deeper aspects of stochastic optimization algorithms in data science.

22 pages, 3 figures. To appear in Comm. Math. Sci. (2019+)

References in corpus (14)

• Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translation
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Improving Generalization Performance by Switching from Adam to SGD
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Sparse Recovery via Differential Inclusions
• Strong error analysis for stochastic gradient descent optimization algorithms
• Adding One Neuron Can Eliminate All Bad Local Minima
• A globally convergent incremental Newton method
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)
• Gaussian Approximations for Probability Measures on ${\mathbf{R}}^d$

Cited by in corpus (5)

• The Implicit Regularization of Stochastic Gradient Flow for Least Squares
• Neural Mechanics: Symmetry and Broken Conservation Laws in Deep Learning Dynamics
• Convergence rates and approximation results for SGD and its continuous-time counterpart
• Random Lie Brackets that Induce Torsion: A Model for Noisy Vector Fields
• Continuous-time Models for Stochastic Optimization Algorithms