One-Shot Klein Cutting Planes for Lipschitz Geodesically Convex Optimization in Hyperbolic Space

We solve the negative constant-curvature case of the COLT 2023 open problem of Criscitiello, Martínez-Rubio, and Boumal on deterministic first-order methods for Lipschitz geodesically convex optimization. Let \[ \HH^d_{-\kappaC^2}=\{X\in\R^{d+1}:\ipL{X}{X}=-1,\ X_0>0\}, \qquad \ip{U}{V}_{X}=\kappaC^{-2}\ipL{U}{V}, \] so the sectional curvature is $-\kappaC^2$. If \[ f:\bar B_{\HH}(x_0,r)\to\R \] is geodesically convex and $M$-Lipschitz, and $s=\kappaC r$, our one-shot Klein cutting-plane method returns a queried point $\hat x$ with \[ f(\hat x)-\min_{\bar B_{\HH}(x_0,r)}f\le \eps Mr \] using at most \[ \left\lceil 2d(d+1) \log\!\left(\frac{16\sinh s\cosh s}{s\eps}\right)\right\rceil \] oracle calls. For $d\ge2$ each localization update costs $O(d^2)$ arithmetic operations; for $d=1$ an interval variant satisfies the same bound. Consequently \[ N=O\bigl(d^2(s+\log(e/\eps))\bigr) =O\bigl(d^2ζ_s\log(e/\eps)\bigr), \qquad ζ_s=s/\tanh s . \] The argument is not a convex coordinate pullback: in the Beltrami--Klein chart the objective is generally only quasiconvex. The key point is that every Riemannian subgradient halfspace becomes an exact Euclidean central cut. For \[ θ=\kappaC\dist(X,Y), \] \[ \ip{g}{\log_XY}_{X} =\fracθ{\kappaC^2\sinhθ}\ipL{g}{Y}, \] and tangency at $X$ turns $\ipL{g}{Y}\le0$ into \[ \gbar^{\mathsf T}(u-c)\le0, \qquad u=Φ(Y),\quad c=Φ(X). \] Thus a fixed Euclidean ellipsoid localizes the whole hyperbolic ball. The only curvature payment is the Klein distortion factor \[ \log\left(\frac{\sinh s\cosh s}{s\eps}\right) =\log(1/\eps)+2s-\log(4s)+O(e^{-4s}). \]