Dissipativity Theory for Nesterov's Accelerated Method
arXiv:1706.04381
Abstract
In this paper, we adapt the control theoretic concept of dissipativity theory to provide a natural understanding of Nesterov's accelerated method. Our theory ties rigorous convergence rate analysis to the physically intuitive notion of energy dissipation. Moreover, dissipativity allows one to efficiently construct Lyapunov functions (either numerically or analytically) by solving a small semidefinite program. Using novel supply rate functions, we show how to recover known rate bounds for Nesterov's method and we generalize the approach to certify both linear and sublinear rates in a variety of settings. Finally, we link the continuous-time version of dissipativity to recent works on algorithm analysis that use discretizations of ordinary differential equations.
to appear in the International Conference on Machine Learning 2017
References in corpus (2)
Cited by in corpus (12)
- Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
- Direct Runge-Kutta Discretization Achieves Acceleration
- Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
- Accelerated Linear Convergence of Stochastic Momentum Methods in Wasserstein Distances
- Accelerating Greedy Coordinate Descent Methods
- A Unified Analysis of Stochastic Optimization Methods Using Jump System Theory and Quadratic Constraints
- Accelerated Gradient Methods with Memory
- Acceleration in First Order Quasi-strongly Convex Optimization by ODE Discretization
- Fast symplectic integrator for Nesterov-type acceleration method
- Provably Correct Learning Algorithms in the Presence of Time-Varying Features Using a Variational Perspective
- Boosting First-Order Methods by Shifting Objective: New Schemes with Faster Worst-Case Rates
- Convergence Analysis and Design of Multi-block ADMM via Switched Control Theory