Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
arXiv:1907.10531
Abstract
The Euclidean space notion of convex sets (and functions) generalizes to Riemannian manifolds in a natural sense and is called geodesic convexity. Extensively studied computational problems such as convex optimization and sampling in convex sets also have meaningful counterparts in the manifold setting. Geodesically convex optimization is a well-studied problem with ongoing research and considerable recent interest in machine learning and theoretical computer science. In this paper, we study sampling and convex optimization problems over manifolds of non-negative curvature proving polynomial running time in the dimension and other relevant parameters. Our algorithms assume a warm start. We first present a random walk based sampling algorithm and then combine it with simulated annealing for solving convex optimization problems. To our knowledge, these are the first algorithms in the general setting of positively curved manifolds with provable polynomial guarantees under reasonable assumptions, and the first study of the connection between sampling and optimization in this setting.
arXiv commentAppeared at COLT 2019
References in corpus (11)
- A Conceptual Introduction to Hamiltonian Monte Carlo
- Bakry-Émery curvature-dimension condition and Riemannian Ricci curvature bounds
- Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
- Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions
- Geodesic Convex Optimization: Differentiation on Manifolds, Geodesics, and Convexity
- Towards Riemannian Accelerated Gradient Methods
- R-SPIDER: A Fast Riemannian Stochastic Optimization Algorithm with Curvature Independent Rate
- Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
- Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
- Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier
- A Cubic Regularized Newton's Method over Riemannian Manifolds