Direct Runge-Kutta Discretization Achieves Acceleration

Abstract

We study gradient-based optimization methods obtained by directly discretizing a second-order ordinary differential equation (ODE) related to the continuous limit of Nesterov's accelerated gradient method. When the function is smooth enough, we show that acceleration can be achieved by a stable discretization of this ODE using standard Runge-Kutta integrators. Specifically, we prove that under Lipschitz-gradient, convexity and order-$(s+2)$ differentiability assumptions, the sequence of iterates generated by discretizing the proposed second-order ODE converges to the optimal solution at a rate of $\mathcal{O}(N^{-2\frac{s}{s+1}})$, where $s$ is the order of the Runge-Kutta numerical integrator. Furthermore, we introduce a new local flatness condition on the objective, under which rates even faster than $\mathcal{O}(N^{-2})$ can be achieved with low-order integrators and only gradient information. Notably, this flatness condition is satisfied by several standard loss functions used in machine learning. We provide numerical experiments that verify the theoretical rates predicted by our results.

arXiv comment24 pages. 4 figures

References in corpus (8)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• A geometric alternative to Nesterov's accelerated gradient descent
• The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods
• On Symplectic Optimization
• Dissipativity Theory for Nesterov's Accelerated Method
• Integration Methods and Accelerated Optimization Algorithms

Cited by in corpus (21)

• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Beyond Convexity -- Contraction and Global Convergence of Gradient Descent
• Is There an Analog of Nesterov Acceleration for MCMC?
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced
• The Role of Memory in Stochastic Optimization
• A Control-Theoretic Perspective on Optimal High-Order Optimization
• Implicit Gradient Regularization
• Continuous vs. Discrete Optimization of Deep Neural Networks
• Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• The Search direction Correction makes first-order methods faster
• A Contraction Theory Approach to Optimization Algorithms from Acceleration Flows
• On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
• Inducing Uniform Asymptotic Stability in Non-Autonomous Accelerated Optimization Dynamics via Hybrid Regularization
• On the stability of optimization algorithms given by discretizations of the Euler-Lagrange ODE
• Continuous-time Models for Stochastic Optimization Algorithms
• Achieving Acceleration in Distributed Optimization via Direct Discretization of the Heavy-Ball ODE
• Online Algorithms and Policies Using Adaptive and Machine Learning Approaches
• Robust Hybrid Zero-Order Optimization Algorithms with Acceleration via Averaging in Time