Open Problem: Polynomial linearly-convergent method for g-convex optimization?

Christopher Criscitiello, David Martínez-Rubio, Nicolas Boumal
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5950-5956, 2023.

Abstract

Let f:M→R be a Lipschitz and geodesically convex function defined on a d-dimensional Riemannian manifold M. Does there exist a first-order deterministic algorithm which (a) uses at most O(poly(d)log(ϵ−1)) subgradient queries to find a point with target accuracy ϵ, and (b) requires only O(poly(d)) arithmetic operations per query? In convex optimization, the classical ellipsoid method achieves this. After detailing related work, we provide an ellipsoid-like algorithm with query complexity O(d2log2(ϵ−1)) and per-query complexity O(d2) for the limited case where M has constant curvature (hemisphere or hyperbolic space). We then detail possible approaches and corresponding obstacles for designing an ellipsoid-like method for general Riemannian manifolds.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-criscitiello23b, title = {Open Problem: Polynomial linearly-convergent method for g-convex optimization?}, author = {Criscitiello, Christopher and Mart{\'i}nez-Rubio, David and Boumal, Nicolas}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {5950--5956}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/criscitiello23b/criscitiello23b.pdf}, url = {https://proceedings.mlr.press/v195/criscitiello23b.html}, abstract = {Let $f \colon \mathcal{M} \to \mathbb{R}$ be a Lipschitz and geodesically convex function defined on a $d$-dimensional Riemannian manifold $\mathcal{M}$. Does there exist a first-order deterministic algorithm which (a) uses at most $O(\mathrm{poly}(d) \log(\epsilon^{-1}))$ subgradient queries to find a point with target accuracy $\epsilon$, and (b) requires only $O(\mathrm{poly}(d))$ arithmetic operations per query? In convex optimization, the classical ellipsoid method achieves this. After detailing related work, we provide an ellipsoid-like algorithm with query complexity $O(d^2 \log^2(\epsilon^{-1}))$ and per-query complexity $O(d^2)$ for the limited case where $\mathcal{M}$ has constant curvature (hemisphere or hyperbolic space). We then detail possible approaches and corresponding obstacles for designing an ellipsoid-like method for general Riemannian manifolds.} }
Endnote
%0 Conference Paper %T Open Problem: Polynomial linearly-convergent method for g-convex optimization? %A Christopher Criscitiello %A David Martínez-Rubio %A Nicolas Boumal %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-criscitiello23b %I PMLR %P 5950--5956 %U https://proceedings.mlr.press/v195/criscitiello23b.html %V 195 %X Let $f \colon \mathcal{M} \to \mathbb{R}$ be a Lipschitz and geodesically convex function defined on a $d$-dimensional Riemannian manifold $\mathcal{M}$. Does there exist a first-order deterministic algorithm which (a) uses at most $O(\mathrm{poly}(d) \log(\epsilon^{-1}))$ subgradient queries to find a point with target accuracy $\epsilon$, and (b) requires only $O(\mathrm{poly}(d))$ arithmetic operations per query? In convex optimization, the classical ellipsoid method achieves this. After detailing related work, we provide an ellipsoid-like algorithm with query complexity $O(d^2 \log^2(\epsilon^{-1}))$ and per-query complexity $O(d^2)$ for the limited case where $\mathcal{M}$ has constant curvature (hemisphere or hyperbolic space). We then detail possible approaches and corresponding obstacles for designing an ellipsoid-like method for general Riemannian manifolds.
APA
Criscitiello, C., Martínez-Rubio, D. & Boumal, N.. (2023). Open Problem: Polynomial linearly-convergent method for g-convex optimization?. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:5950-5956 Available from https://proceedings.mlr.press/v195/criscitiello23b.html.

Related Material