First-order Methods for Geodesically Convex Optimization
This work addresses the underdeveloped area of geodesically convex optimization, providing foundational theoretical results for researchers in optimization and differential geometry.
The paper tackled the problem of geodesically convex optimization by developing iteration complexity analysis for first-order algorithms on Hadamard manifolds, proving upper bounds for deterministic and stochastic methods with and without strong convexity, and showing how manifold geometry affects convergence rates.
Geodesic convexity generalizes the notion of (vector space) convexity to nonlinear metric spaces. But unlike convex optimization, geodesically convex (g-convex) optimization is much less developed. In this paper we contribute to the understanding of g-convex optimization by developing iteration complexity analysis for several first-order algorithms on Hadamard manifolds. Specifically, we prove upper bounds for the global complexity of deterministic and stochastic (sub)gradient methods for optimizing smooth and nonsmooth g-convex functions, both with and without strong g-convexity. Our analysis also reveals how the manifold geometry, especially \emph{sectional curvature}, impacts convergence rates. To the best of our knowledge, our work is the first to provide global complexity analysis for first-order algorithms for general g-convex optimization.