Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature

Navin Goyal, Abhishek Shetty
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:1519-1561, 2019.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-goyal19a, title = {Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature}, author = {Goyal, Navin and Shetty, Abhishek}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {1519--1561}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/goyal19a/goyal19a.pdf}, url = {https://proceedings.mlr.press/v99/goyal19a.html}, 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.} }
Endnote
%0 Conference Paper %T Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature %A Navin Goyal %A Abhishek Shetty %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-goyal19a %I PMLR %P 1519--1561 %U https://proceedings.mlr.press/v99/goyal19a.html %V 99 %X 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.
APA
Goyal, N. & Shetty, A.. (2019). Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:1519-1561 Available from https://proceedings.mlr.press/v99/goyal19a.html.

Related Material