A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization

Foivos Alimisis, Antonio Orvieto, Gary Becigneul, Aurelien Lucchi
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1297-1307, 2020.

Abstract

We propose a novel second-order ODE as the continuous-time limit of a Riemannian accelerated gradient-based method on a manifold with curvature bounded from below. This ODE can be seen as a generalization of the ODE derived for Euclidean spaces, and can also serve as an analysis tool. We analyze the convergence behavior of this ODE for different types of functions, such as geodesically convex, strongly-convex and weakly-quasi-convex. We demonstrate how such an ODE can be discretized using a semi-implicit and Nesterov-inspired numerical integrator, that empirically yields stable algorithms which are faithful to the continuous-time analysis and exhibit accelerated convergence.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-alimisis20a, title = {A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization}, author = {Alimisis, Foivos and Orvieto, Antonio and Becigneul, Gary and Lucchi, Aurelien}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1297--1307}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/alimisis20a/alimisis20a.pdf}, url = {https://proceedings.mlr.press/v108/alimisis20a.html}, abstract = {We propose a novel second-order ODE as the continuous-time limit of a Riemannian accelerated gradient-based method on a manifold with curvature bounded from below. This ODE can be seen as a generalization of the ODE derived for Euclidean spaces, and can also serve as an analysis tool. We analyze the convergence behavior of this ODE for different types of functions, such as geodesically convex, strongly-convex and weakly-quasi-convex. We demonstrate how such an ODE can be discretized using a semi-implicit and Nesterov-inspired numerical integrator, that empirically yields stable algorithms which are faithful to the continuous-time analysis and exhibit accelerated convergence.} }
Endnote
%0 Conference Paper %T A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization %A Foivos Alimisis %A Antonio Orvieto %A Gary Becigneul %A Aurelien Lucchi %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-alimisis20a %I PMLR %P 1297--1307 %U https://proceedings.mlr.press/v108/alimisis20a.html %V 108 %X We propose a novel second-order ODE as the continuous-time limit of a Riemannian accelerated gradient-based method on a manifold with curvature bounded from below. This ODE can be seen as a generalization of the ODE derived for Euclidean spaces, and can also serve as an analysis tool. We analyze the convergence behavior of this ODE for different types of functions, such as geodesically convex, strongly-convex and weakly-quasi-convex. We demonstrate how such an ODE can be discretized using a semi-implicit and Nesterov-inspired numerical integrator, that empirically yields stable algorithms which are faithful to the continuous-time analysis and exhibit accelerated convergence.
APA
Alimisis, F., Orvieto, A., Becigneul, G. & Lucchi, A.. (2020). A Continuous-time Perspective for Modeling Acceleration in Riemannian Optimization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1297-1307 Available from https://proceedings.mlr.press/v108/alimisis20a.html.

Related Material