Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles

Christopher Criscitiello, Nicolas Boumal
Proceedings of Thirty Fifth Conference on Learning Theory, PMLR 178:496-542, 2022.

Abstract

Hamilton and Moitra (2021) showed that, in certain regimes, it is not possible to accelerate Riemannian gradient descent in the hyperbolic plane if we restrict ourselves to algorithms which make queries in a (large) bounded domain and which receive gradients and function values corrupted by a (small) amount of noise. We show that acceleration remains unachievable for any deterministic algorithm which receives exact gradient and function-value information (unbounded queries, no noise). Our results hold for a large class of Hadamard manifolds including hyperbolic spaces and the symmetric space $\mathrm{SL}(n) / \mathrm{SO}(n)$ of positive definite $n \times n$ matrices of determinant one. This cements a surprising gap between the complexity of convex optimization and geodesically convex optimization: for hyperbolic spaces, Riemannian gradient descent is optimal on the class of smooth and strongly geodesically convex functions (in the regime where the condition number scales with the radius of the optimization domain). The key idea for proving the lower bound consists of perturbing squared distance functions with sums of bump functions chosen by a resisting oracle.

Cite this Paper

BibTeX
@InProceedings{pmlr-v178-criscitiello22a, title = {Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles}, author = {Criscitiello, Christopher and Boumal, Nicolas}, booktitle = {Proceedings of Thirty Fifth Conference on Learning Theory}, pages = {496--542}, year = {2022}, editor = {Loh, Po-Ling and Raginsky, Maxim}, volume = {178}, series = {Proceedings of Machine Learning Research}, month = {02--05 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v178/criscitiello22a/criscitiello22a.pdf}, url = {https://proceedings.mlr.press/v178/criscitiello22a.html}, abstract = {Hamilton and Moitra (2021) showed that, in certain regimes, it is not possible to accelerate Riemannian gradient descent in the hyperbolic plane if we restrict ourselves to algorithms which make queries in a (large) bounded domain and which receive gradients and function values corrupted by a (small) amount of noise. We show that acceleration remains unachievable for any deterministic algorithm which receives exact gradient and function-value information (unbounded queries, no noise). Our results hold for a large class of Hadamard manifolds including hyperbolic spaces and the symmetric space $\mathrm{SL}(n) / \mathrm{SO}(n)$ of positive definite $n \times n$ matrices of determinant one. This cements a surprising gap between the complexity of convex optimization and geodesically convex optimization: for hyperbolic spaces, Riemannian gradient descent is optimal on the class of smooth and strongly geodesically convex functions (in the regime where the condition number scales with the radius of the optimization domain). The key idea for proving the lower bound consists of perturbing squared distance functions with sums of bump functions chosen by a resisting oracle.} }
Endnote
%0 Conference Paper %T Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles %A Christopher Criscitiello %A Nicolas Boumal %B Proceedings of Thirty Fifth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2022 %E Po-Ling Loh %E Maxim Raginsky %F pmlr-v178-criscitiello22a %I PMLR %P 496--542 %U https://proceedings.mlr.press/v178/criscitiello22a.html %V 178 %X Hamilton and Moitra (2021) showed that, in certain regimes, it is not possible to accelerate Riemannian gradient descent in the hyperbolic plane if we restrict ourselves to algorithms which make queries in a (large) bounded domain and which receive gradients and function values corrupted by a (small) amount of noise. We show that acceleration remains unachievable for any deterministic algorithm which receives exact gradient and function-value information (unbounded queries, no noise). Our results hold for a large class of Hadamard manifolds including hyperbolic spaces and the symmetric space $\mathrm{SL}(n) / \mathrm{SO}(n)$ of positive definite $n \times n$ matrices of determinant one. This cements a surprising gap between the complexity of convex optimization and geodesically convex optimization: for hyperbolic spaces, Riemannian gradient descent is optimal on the class of smooth and strongly geodesically convex functions (in the regime where the condition number scales with the radius of the optimization domain). The key idea for proving the lower bound consists of perturbing squared distance functions with sums of bump functions chosen by a resisting oracle.
APA
Criscitiello, C. & Boumal, N.. (2022). Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles. Proceedings of Thirty Fifth Conference on Learning Theory, in Proceedings of Machine Learning Research 178:496-542 Available from https://proceedings.mlr.press/v178/criscitiello22a.html.

Related Material