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

Let $f\text{\hspace{0.17em}⁣}:\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{p}\mathrm{o}\mathrm{l}\mathrm{y}(d)\log ({\epsilon }^{-1}))$ subgradient queries to find a point with target accuracy $\epsilon$, and (b) requires only $O(\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(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.