  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.
