A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
arXiv:2106.07644
Abstract
We introduce the continuized Nesterov acceleration, a close variant of Nesterov acceleration whose variables are indexed by a continuous time parameter. The two variables continuously mix following a linear ordinary differential equation and take gradient steps at random times. This continuized variant benefits from the best of the continuous and the discrete frameworks: as a continuous process, one can use differential calculus to analyze convergence and obtain analytical expressions for the parameters; and a discretization of the continuized process can be computed exactly with convergence rates similar to those of Nesterov original acceleration. We show that the discretization has the same structure as Nesterov acceleration, but with random parameters. We provide continuized Nesterov acceleration under deterministic as well as stochastic gradients, with either additive or multiplicative noise. Finally, using our continuized framework and expressing the gossip averaging problem as the stochastic minimization of a certain energy function, we provide the first rigorous acceleration of asynchronous gossip algorithms.
arXiv commentarXiv admin note: substantial text overlap with arXiv:2102.06035
References in corpus (13)
- A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
- Geographic Gossip: Efficient Averaging for Sensor Networks
- Optimal algorithms for smooth and strongly convex distributed optimization in networks
- Optimized first-order methods for smooth convex minimization
- A Lyapunov Analysis of Momentum Methods in Optimization
- A geometric alternative to Nesterov's accelerated gradient descent
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- Accelerating Stochastic Gradient Descent For Least Squares Regression
- The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
- Acceleration via Symplectic Discretization of High-Resolution Differential Equations
- On Symplectic Optimization
- Analysis of Stochastic Gradient Descent in Continuous Time
- Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives