First-order Methods for Geodesically Convex Optimization

Abstract

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.

arXiv comment21 pages

References in corpus (2)

• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Multivariate Generalized Gaussian Distribution: Convexity and Graphical Models

Cited by in corpus (16)

• Global rates of convergence for nonconvex optimization on manifolds
• Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifolds
• Averaging Stochastic Gradient Descent on Riemannian Manifolds
• Gradient descent algorithms for Bures-Wasserstein barycenters
• Towards Riemannian Accelerated Gradient Methods
• R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Escaping from saddle points on Riemannian manifolds
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Fast, asymptotically efficient, recursive estimation in a Riemannian manifold
• Solving general elliptical mixture models through an approximate Wasserstein manifold
• A scaled Bregman theorem with applications
• Identifiability, the KL property in metric spaces, and subgradient curves
• A Particle-Based Algorithm for Distributional Optimization on \textit{Constrained Domains} via Variational Transport and Mirror Descent
• Optimization on Product Submanifolds of Convolution Kernels
• Iteration-complexity of gradient, subgradient and proximal point methods on Riemannian manifolds