2022-06-28-criscitiello22a.md

title	abstract	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles	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.	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	criscitiello22a	0	Negative curvature obstructs acceleration for strongly geodesically convex optimization, even with exact first-order oracles	496	542	496-542	496	false	Criscitiello, Christopher and Boumal, Nicolas	given family Christopher Criscitiello given family Nicolas Boumal	2022-06-28		Proceedings of Thirty Fifth Conference on Learning Theory	178	inproceedings	date-parts 2022 6 28	https://proceedings.mlr.press/v178/criscitiello22a/criscitiello22a.pdf