Acceleration via Symplectic Discretization of High-Resolution Differential Equations
arXiv:1902.03694
Abstract
We study first-order optimization methods obtained by discretizing ordinary differential equations (ODEs) corresponding to Nesterov's accelerated gradient methods (NAGs) and Polyak's heavy-ball method. We consider three discretization schemes: an explicit Euler scheme, an implicit Euler scheme, and a symplectic scheme. We show that the optimization algorithm generated by applying the symplectic scheme to a high-resolution ODE proposed by Shi et al. [2018] achieves an accelerated rate for minimizing smooth strongly convex functions. On the other hand, the resulting algorithm either fails to achieve acceleration or is impractical when the scheme is implicit, the ODE is low-resolution, or the scheme is explicit.
arXiv commentPublished in Neurips 2019
Cited by in corpus (11)
- Is There an Analog of Nesterov Acceleration for MCMC?
- Heavy Ball Neural Ordinary Differential Equations
- Nesterov Acceleration for Equality-Constrained Convex Optimization via Continuously Differentiable Penalty Functions
- Accelerated Learning with Robustness to Adversarial Regressors
- Why resampling outperforms reweighting for correcting sampling bias with stochastic gradients
- A Control-Theoretic Perspective on Optimal High-Order Optimization
- Reverse engineering learned optimizers reveals known and novel mechanisms
- A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
- A Continuized View on Nesterov Acceleration for Stochastic Gradient Descent and Randomized Gossip
- Continuous-time Models for Stochastic Optimization Algorithms
- Meta Learning in the Continuous Time Limit