Dissipativity Theory for Nesterov’s Accelerated Method

Bin Hu, Laurent Lessard
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:1549-1557, 2017.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-hu17a, title = {Dissipativity Theory for {N}esterov's Accelerated Method}, author = {Bin Hu and Laurent Lessard}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {1549--1557}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/hu17a/hu17a.pdf}, url = {https://proceedings.mlr.press/v70/hu17a.html}, 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.} }
Endnote
%0 Conference Paper %T Dissipativity Theory for Nesterov’s Accelerated Method %A Bin Hu %A Laurent Lessard %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-hu17a %I PMLR %P 1549--1557 %U https://proceedings.mlr.press/v70/hu17a.html %V 70 %X 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.
APA
Hu, B. & Lessard, L.. (2017). Dissipativity Theory for Nesterov’s Accelerated Method. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:1549-1557 Available from https://proceedings.mlr.press/v70/hu17a.html.

Related Material