A fast ellipsoid-like method for geodesically convex optimization

The ellipsoid method minimizes any Lipschitz convex function on a ball in $\mathbb{R}^d$ to accuracy $\epsilon$ with $O(d^2 \log(1/\epsilon))$ subgradient queries and $O(d^2)$ arithmetic per query. On a curved Riemannian manifold, with convexity measured along geodesics, no method is known that has both a query count growing like $\log(1/\epsilon)$ and cheap iterations.

Problem

Let $\mathcal{M}$ be a complete $d$-dimensional Riemannian manifold whose sectional curvatures lie in $[-K, K]$. Let $B = \bar B(x_{\mathrm{ref}}, r)$ be a closed geodesic ball that is geodesically convex: any two of its points are joined by a unique minimizing geodesic, which stays in $B$. Let $f : B \to \mathbb{R}$ be geodesically convex, meaning convex along every geodesic segment in $B$, and $L$-Lipschitz for the Riemannian distance. A first-order oracle, queried at $x$, returns $f(x)$ and a subgradient $g \in T_x\mathcal{M}$, that is, $f(y) \ge f(x) + \langle g, \log_x y \rangle$ for all $y \in B$. Write $f^\star = \min_B f$ and $\zeta = r\sqrt{K} / \tanh(r\sqrt{K})$; some dependence on $\zeta$ is unavoidable [4].

Question. Is there a deterministic first-order algorithm with both of the following properties?

1. For every $\epsilon \in (0, 1)$ it finds $x$ with $f(x) - f^\star \le \epsilon L r$ using $O(\mathrm{poly}(\zeta, d) \log(1/\epsilon))$ oracle queries.
2. Apart from the oracle calls, it spends only $\mathrm{poly}(\zeta, d)$ arithmetic operations per query.

Background

The ellipsoid method of Shor and of Yudin and Nemirovskii, which Khachiyan used to solve linear programs in polynomial time, has exactly these two properties in Euclidean space. Geodesic convexity is a generalization of convexity that arises in operator scaling, which in turn covers robust covariance estimation, matrix normal models and a variant of polynomial identity testing [5]; there one wants a deterministic method with a linear rate. The question was raised informally by Allen-Zhu et al. [5] and by Rusciano [2], and stated precisely by Criscitiello, Martínez-Rubio and Boumal at COLT 2023 [1].

What is known

• One property at a time. Subgradient methods have cheap iterations but no linear rate without further assumptions (Zhang and Sra, 2016) [3]. Rusciano's centerpoint method meets property 1, but each step needs a Riemannian centerpoint, which is not known to be efficiently computable [1, 2]. Riemannian interior-point methods converge quickly, but only under extra assumptions on the objective [1].
• Constant curvature. On the hemisphere and in hyperbolic space the posers give an ellipsoid-like method with $O(\zeta d^2 \log^2(1/\epsilon))$ queries and $O(d^2)$ work per query, by pulling the problem back to Euclidean space with geodesic maps (the Beltrami–Klein model) [1]. By Beltrami's theorem, only spaces of constant curvature admit such maps, so the trick does not extend.
• Hyperbolic space, sharper. A 2026 preprint gives a deterministic cutting-plane method in hyperbolic space with $O(d^2(r\sqrt{K} + \log(e/\epsilon)))$ queries and $O(d^2)$ work per step, and states that the general problem on Hadamard manifolds remains open [6].
• Obstacles. There is no convenient notion of ellipsoid on a manifold. Even in hyperbolic space, the maps that preserve both geodesic halfspaces and volume appear to be just the isometries, which only move geodesic balls around [1].

What would count as progress

• An algorithm, with a proof, that has both properties on the manifold of positive definite matrices with the affine-invariant metric, the most common setting in applications.
• A randomized algorithm with both properties on a general manifold, as an intermediate step.
• A lower bound showing that no algorithm can have both properties on some family of manifolds.

References

1. C. Criscitiello, D. Martínez-Rubio and N. Boumal, Open problem: Polynomial linearly-convergent method for g-convex optimization?, COLT 2023, PMLR 195 (2023), 5950–5956. arXiv:2307.12743
2. A. Rusciano, A Riemannian corollary of Helly's theorem, preprint (2018). arXiv:1804.10738
3. H. Zhang and S. Sra, First-order methods for geodesically convex optimization, COLT 2016, PMLR 49 (2016), 1617–1638. PMLR
4. C. Criscitiello and N. Boumal, Curvature and complexity: better lower bounds for geodesically convex optimization, COLT 2023, PMLR 195 (2023). arXiv:2306.02959
5. Z. Allen-Zhu, A. Garg, Y. Li, R. Oliveira and A. Wigderson, Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing, STOC (2018). doi:10.1145/3188745.3188942
6. Y. Zhang, Y. Yang, Y. Zhu and W. Zhang, One-shot Klein cutting planes for Lipschitz geodesically convex optimization in hyperbolic space, preprint (2026). arXiv:2605.17540

Source

Imported from COLT open problems, COLT 2023, curated by the Conference on Learning Theory (COLT). Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.