First-order Methods for Geodesically Convex Optimization
By Hongyi Zhang, Suvrit Sra. Annual Conference Computational Learning Theory, 2016
338 citations recorded by the source corpus.
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.
Subfields: Applied Mathematics, Computational Mechanics, Numerical Analysis
View Paper: https://www.semanticscholar.org/paper/a0a2ad6d3225329f55766f0bf332c86a63f6e14e
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Applied Mathematics
In Computational Mechanics
In Numerical Analysis
Citations in the corpus
- Riemannian Adaptive Optimization Methods (2018, methodology): “In Riemannian manifolds, this step is generalized using the analogue lemma 6 introduced by Zhang & Sra (2016), valid in all Alexandrov spaces, which includes our setting of geodesically convex subsets of Riemannian manifolds with lower bounded sectional curvature.”
- Global rates of convergence for nonconvex optimization on manifolds (2016, neutral): “Zhang and Sra (2016) treat geodesically convex problems over Hadamard manifolds.”