Unverified

Polynomial Linearly-Convergent Method for Geodesically Convex Optimization?

Assume that $\mathcal M$ has sectional curvatures in $[-K,K]$ , that the closed ball $\overline B(x_{\mathrm{ref}},r)$ is geodesically convex, and that $f\colon\overline B(x_{\mathrm{ref}},r)\to\mathbb R$ is geodesically convex and $M$ -Lipschitz. Define

\zeta_{r\sqrt K}=\frac{r\sqrt K}{\tanh(r\sqrt K)}, \qquad f^*=\min_{x\in\overline B(x_{\mathrm{ref}},r)}f(x).

Is there a deterministic first-order algorithm such that:

for every $\epsilon\in(0,1)$ , it returns $x$ with $f(x)-f^*\leq\epsilon Mr$ after at most

O(\operatorname{poly}(\zeta_{r\sqrt K},d)\log(1/\epsilon))

subgradient-oracle queries; and

each iteration uses only $\operatorname{poly}(\zeta_{r\sqrt K},d)$ arithmetic operations, in addition to its oracle query?

Download

Abstract

Let $f$ be a Lipschitz geodesically convex function on a $d$ -dimensional Riemannian manifold. Does there exist a deterministic first-order algorithm using only $O(\operatorname{poly}(d)\log(1/\epsilon))$ subgradient queries and $O(\operatorname{poly}(d))$ arithmetic operations per query? The Euclidean ellipsoid method has these properties. An ellipsoid-like method is known for constant-curvature spaces, but the question remains open for general Riemannian manifolds.

Background and progress

Let $\mathcal M$ be a complete $d$ -dimensional Riemannian manifold with distance $\operatorname{dist}$ , exponential map, and logarithm map. A set is geodesically convex if every pair of its points is joined by a unique minimizing geodesic contained in the set. A function is geodesically convex if its restriction to each such geodesic is convex. A vector $g\in T_x\mathcal M$ is a subgradient of $f$ at $x$ if $f(y)\geq f(x)+\langle g,\log_x(y)\rangle$ for all $y$ in the domain.

The Euclidean ellipsoid method needs $O(d^2\log(1/\epsilon))$ subgradient queries and $O(d^2)$ arithmetic operations per query. On a hemisphere or hyperbolic space, geodesic maps reduce sufficiently small subproblems to Euclidean convex optimization and give an ellipsoid-like method with $O(\zeta_{r\sqrt K}d^2\log^2(1/\epsilon))$ queries and $O(d^2)$ work per query [Mart'inez-Rubio, 2023]. Here $K$ bounds the magnitude of sectional curvature and $\zeta_t=t/\tanh t$ . For general manifolds, the subgradient method is cheap per iteration but not linearly convergent, while a Riemannian center-of-gravity method converges linearly but lacks an efficient implementation [Rusciano, 2019].

Reference papers

Global Riemannian Acceleration in Hyperbolic and Spherical SpacesDavid Mart\'inez-Rubio2023 ↗
A Riemannian Corollary of Helly's TheoremA. RuscianoarXiv:1804.10738 · 2019

Polynomial Linearly-Convergent Method for Geodesically Convex Optimization?

Coming soon

Organizer