Timezone: »
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.
Summary/NotesAuthor Information
Bin Hu (University of Wisconsin)
Laurent Lessard (University of Wisconsin-Madison)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: Dissipativity Theory for Nesterov's Accelerated Method »
Tue. Aug 8th 08:30 AM -- 12:00 PM Room Gallery #78
More from the Same Authors
-
2018 Poster: Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees »
Adrien Taylor · Bryan Van Scoy · Laurent Lessard -
2018 Poster: Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs »
Bin Hu · Stephen Wright · Laurent Lessard -
2018 Oral: Lyapunov Functions for First-Order Methods: Tight Automated Convergence Guarantees »
Adrien Taylor · Bryan Van Scoy · Laurent Lessard -
2018 Oral: Dissipativity Theory for Accelerating Stochastic Variance Reduction: A Unified Analysis of SVRG and Katyusha Using Semidefinite Programs »
Bin Hu · Stephen Wright · Laurent Lessard