Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization

Peiyuan Zhang, Antonio Orvieto, Hadi Daneshmand, Thomas Hofmann, Roy S. Smith
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:3979-3987, 2021.

Abstract

Viewing optimization methods as numerical integrators for ordinary differential equations (ODEs) provides a thought-provoking modern framework for studying accelerated first-order optimizers. In this literature, acceleration is often supposed to be linked to the quality of the integrator (accuracy, energy preservation, symplecticity). In this work, we propose a novel ordinary differential equation that questions this connection: both the explicit and the semi-implicit (a.k.a symplectic) Euler discretizations on this ODE lead to an accelerated algorithm for convex programming. Although semi-implicit methods are well-known in numerical analysis to enjoy many desirable features for the integration of physical systems, our findings show that these properties do not necessarily relate to acceleration.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-zhang21m, title = { Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization }, author = {Zhang, Peiyuan and Orvieto, Antonio and Daneshmand, Hadi and Hofmann, Thomas and S. Smith, Roy}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {3979--3987}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/zhang21m/zhang21m.pdf}, url = {https://proceedings.mlr.press/v130/zhang21m.html}, abstract = { Viewing optimization methods as numerical integrators for ordinary differential equations (ODEs) provides a thought-provoking modern framework for studying accelerated first-order optimizers. In this literature, acceleration is often supposed to be linked to the quality of the integrator (accuracy, energy preservation, symplecticity). In this work, we propose a novel ordinary differential equation that questions this connection: both the explicit and the semi-implicit (a.k.a symplectic) Euler discretizations on this ODE lead to an accelerated algorithm for convex programming. Although semi-implicit methods are well-known in numerical analysis to enjoy many desirable features for the integration of physical systems, our findings show that these properties do not necessarily relate to acceleration. } }
Endnote
%0 Conference Paper %T Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization %A Peiyuan Zhang %A Antonio Orvieto %A Hadi Daneshmand %A Thomas Hofmann %A Roy S. Smith %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-zhang21m %I PMLR %P 3979--3987 %U https://proceedings.mlr.press/v130/zhang21m.html %V 130 %X Viewing optimization methods as numerical integrators for ordinary differential equations (ODEs) provides a thought-provoking modern framework for studying accelerated first-order optimizers. In this literature, acceleration is often supposed to be linked to the quality of the integrator (accuracy, energy preservation, symplecticity). In this work, we propose a novel ordinary differential equation that questions this connection: both the explicit and the semi-implicit (a.k.a symplectic) Euler discretizations on this ODE lead to an accelerated algorithm for convex programming. Although semi-implicit methods are well-known in numerical analysis to enjoy many desirable features for the integration of physical systems, our findings show that these properties do not necessarily relate to acceleration.
APA
Zhang, P., Orvieto, A., Daneshmand, H., Hofmann, T. & S. Smith, R.. (2021). Revisiting the Role of Euler Numerical Integration on Acceleration and Stability in Convex Optimization . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:3979-3987 Available from https://proceedings.mlr.press/v130/zhang21m.html.

Related Material