Analysis of Stochastic Gradient Descent in Continuous Time
arXiv:2004.07177 · doi:10.1007/s11222-021-10016-8
Abstract
Stochastic gradient descent is an optimisation method that combines classical gradient descent with random subsampling within the target functional. In this work, we introduce the stochastic gradient process as a continuous-time representation of stochastic gradient descent. The stochastic gradient process is a dynamical system that is coupled with a continuous-time Markov process living on a finite state space. The dynamical system -- a gradient flow -- represents the gradient descent part, the process on the finite state space represents the random subsampling. Processes of this type are, for instance, used to model clonal populations in fluctuating environments. After introducing it, we study theoretical properties of the stochastic gradient process: We show that it converges weakly to the gradient flow with respect to the full target function, as the learning rate approaches zero. We give conditions under which the stochastic gradient process with constant learning rate is exponentially ergodic in the Wasserstein sense. Then we study the case, where the learning rate goes to zero sufficiently slowly and the single target functions are strongly convex. In this case, the process converges weakly to the point mass concentrated in the global minimum of the full target function; indicating consistency of the method. We conclude after a discussion of discretisation strategies for the stochastic gradient process and numerical experiments.
References in corpus (18)
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- The Loss Surfaces of Multilayer Networks
- The Zig-Zag Process and Super-Efficient Sampling for Bayesian Analysis of Big Data
- Ensemble Kalman Inversion: A Derivative-Free Technique For Machine Learning Tasks
- Exponential ergodicity for Markov processes with random switching
- Quantitative ergodicity for some switched dynamical systems
- Invariant densities for dynamical systems with random switching
- Piecewise Deterministic Markov Processes for Continuous-Time Monte Carlo
- A Variational Analysis of Stochastic Gradient Algorithms
- Strong error analysis for stochastic gradient descent optimization algorithms
- The promises and pitfalls of Stochastic Gradient Langevin Dynamics
- Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundations
- SGD: General Analysis and Improved Rates
- Evolutionary dynamics of competing phenotype-structured populations in periodically fluctuating environments
- Accelerated Sampling on Discrete Spaces with Non-Reversible Markov Processes
- Generalized Parallel Tempering on Bayesian Inverse Problems
- Approximation methods for piecewise deterministic Markov processes and their costs
- Accelerating Natural Gradient with Higher-Order Invariance
Cited by in corpus (9)
- Classification and image processing with a semi-discrete scheme for fidelity forced Allen--Cahn on graphs
- Subsampling in ensemble Kalman inversion
- Covariance Operator Estimation via Adaptive Thresholding
- A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
- Noise Balance and Stationary Distribution of Stochastic Gradient Descent
- Gradient flows and randomised thresholding: sparse inversion and classification
- Learning Gradient Flow: Using Equation Discovery to Accelerate Engineering Optimization
- How to beat a Bayesian adversary
- Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization