Pith. sign in

REVIEW 4 minor 29 references

The Blessing and Curse of Curvature in Higher-Order Optimization: Horospherical versus Geodesic Convexity

T0 review · 0 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Negative curvature is a blessing for one convexity and a curse for another

desk verdict First higher-order oracle-complexity theory for h- vs g-convexity on Hadamard manifolds; the separation is real, the proofs are careful, and the only serious caveat is the free-Busemann oracle model. read the letter →

arxiv 2608.06719 v1 pith:T6332HFS submitted 2026-08-07 math.OC

Andi Han This is my paper · ORCID
classification math.OC MSC 90C4852A4168Q17
keywords higher-orderoptimizationHadamardmanifoldshorosphericalconvexitygeodesicoraclecomplexityhyperbolicspaceBusemannfunctionsnegativecurvature
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that in higher-order ($p \ge 2$) optimization on Hadamard manifolds—complete, simply connected spaces of non-positive curvature—the sign of curvature's effect is governed by which notion of convexity the objective satisfies. For strongly horospherically convex functions, the author proves the Euclidean-optimal oracle complexity $Q_p^{2/(3p+1)}$ on every Hadamard manifold, where $Q_p = L_p R^{p-1}/\mu$ is the dimensionless $p$-th-order condition parameter; on hyperbolic space the same guarantee improves to $Q_p \min\{1, 4/(\kappa R)\}^{p-1}$ after a logarithmic localization cost, so growing negative curvature makes the problem easier. For strongly geodesically convex functions with bounded curvature–radius product, the Euclidean exponent remains optimal; but when $\kappa R$ grows, the paper constructs a hard family on the hyperbolic plane requiring $\widetilde\Omega_p(Q_p^{1/p})$ queries. If these bounds are right, curvature is a blessing exactly for the class that carries global horospherical information, and a curse for the larger geodesically convex class that lacks it.

What carries the argument

For the horospherically convex upper bounds, the central objects are Busemann functions $b_\gamma(z) = \lim_{t\to\infty}(d(z,\gamma(t)) - t)$ associated with geodesic rays; a Busemann function is a 1-Lipschitz convex height whose level sets are horospheres. The key identity is the Busemann minorant of Lemma 4.1: at a queried point $y$, the gradient defines a ray whose Busemann function gives an affine-in-intrinsic-coordinates lower support $m_y(z) = f(y) + \|\nabla f(y)\| b_y(z) \le f(z)$, replacing the Euclidean affine minorants inside an estimate-sequence argument. On hyperbolic space, the supporting horoball containing the minimizer is intersected with a second horoball, and hyperbolic divergence makes the intersection contract to radius $O(1/\kappa)$. For the geodesically convex upper bound, the machinery is an accelerated projected regularized tensor method whose step distortion is quantified by $\zeta_\kappa(s) = \kappa s \coth(\kappa s)$; for the growing-curvature lower bound, the machinery is a local interpolation lemma that matches all Riemannian derivatives through order $p$ at queried points while pruning candidate minimizers by volume counting.

What would settle it

Run Algorithm 1 on $\mathbb{H}^2_\kappa$ for $f(x) = \frac{\mu}{2} d(x, x^\star)^2$ with $\kappa R$ large and count oracle calls; exceeding $\widetilde O_p(1 + [Q_p/(\kappa R)^{p-1}]^{2/(3p+1)})$ would refute Theorem 3.2. For the geodesically convex side, exhibit any deterministic exact Riemannian $p$-th-order method that solves every instance of the Theorem 3.6 family with $\kappa R$ large in $o(\kappa R/\log(2+\kappa R))$ queries; that would break the growing-curvature lower bound.

Watch

Extended reading notes

Core claim

The central claim is a separation theorem about the information available from an exact Riemannian $p$-th-order oracle, which returns the function value and its covariant derivatives through order $p$ at each query point. On any Hadamard manifold, every strongly horospherically convex smooth objective can be minimized in $\widetilde O_p(1 + Q_p^{2/(3p+1)})$ oracle calls (Theorem 3.1), and this exponent is tight at fixed curvature (Theorem 3.3). On hyperbolic space of curvature $-\kappa^2$, the gradient part of the oracle localizes the minimizer to scale $1/\kappa$ in $O(\log(1+\kappa R))$ queries, so the effective condition parameter shrinks from $Q_p$ to $Q_p\min\{1, 4/(\kappa R)\}^{p-1}$ (Theorem 3.2). For the larger class of strongly geodesically convex objectives, the same exponent is optimal when $\kappa R = O(1)$ (Theorems 3.4 and 3.5), but when $\kappa R$ grows there is a hard family with $Q_p \asymp_p (1+\kappa R)^p$ for which every deterministic exact method needs $\widetilde\Omega_p(Q_p^{1/p})$ queries (Theorem 3.6). The paper's conclusion is that the same hyperbolic divergence—fast separation of geodesics—yields a contracting horoball geometry that helps horospherical convexity and an exponentially rich set of hiding directions that obstructs the full geodesically convex class.

Load-bearing premise

The load-bearing premise is that geometric subproblems are free: the oracle model charges nothing for evaluating Busemann functions, solving the Busemann subproblem in Algorithm 1, or carrying out other finite-dimensional computation, so the horospherically convex upper bounds are oracle-complexity statements rather than end-to-end computational guarantees if those subproblems are hard.

Editorial extensions

If this is right

  • Strongly horospherically convex objectives inherit the full Euclidean higher-order rate: on every Hadamard manifold, $p$-th-order methods reach accuracy $\varepsilon$ in $\widetilde O_p(1 + Q_p^{2/(3p+1)})$ oracle calls plus a doubly logarithmic accuracy term.
  • On hyperbolic space the horospherically convex rate improves with curvature: for $\kappa R \ge 4$, the effective condition parameter becomes $4^{p-1}Q_p/(\kappa R)^{p-1}$, so larger negative curvature lowers the oracle count after only $O(\log(1+\kappa R))$ localization queries.
  • For strongly geodesically convex objectives with bounded curvature ($\kappa R = O(1)$), no deterministic exact method can beat the Euclidean exponent $Q_p^{2/(3p+1)}$ up to constants depending on the curvature bound.
  • For strongly geodesically convex objectives with growing $\kappa R$, deterministic exact higher-order methods provably cannot accelerate: at least $\Omega_p(\kappa R/\log(2+\kappa R))$ queries are necessary, rewritten as $\widetilde\Omega_p(Q_p^{1/p})$ for the hard family.
  • The horospherically convex upper bound and the geodesically convex lower bound coexist because the hard geodesically convex family is not contained in the strongly horospherically convex class; the separation is a property of the class, not a contradiction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's oracle model charges nothing for geometric subproblems; if evaluating Busemann functions or solving the Busemann subproblem in Algorithm 1 becomes expensive at scale, the horospherically convex upper bounds describe oracle calls rather than wall-clock time, a gap the author explicitly flags and leaves open.
  • A natural testable extension is variable negative curvature: the localization mechanism is proved for constant-curvature hyperbolic space, and the paper leaves open whether manifolds with curvature bounded above by $-\kappa^2$ but not constant still admit the same $Q_{p,\kappa}$ improvement.
  • The growing-curvature geodesically convex lower bound is one-sided; if a matching upper bound exists, the true minimax rate in that regime would reveal where the $Q_p^{2/(3p+1)}$ plateau breaks and whether randomization can bypass the deterministic obstruction.
  • Because the lower-bound construction rests on exact $p$-th-order derivative replies and deterministic queries, perturbing the model with gradient noise or stochastic oracles could change the picture; that extension is not addressed in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. This paper studies deterministic exact Riemannian p-th-order oracle complexity (p≥2) for strongly convex optimization on Hadamard manifolds, comparing strong horospherical (h-) convexity with strong geodesic (g-) convexity. It proves Euclidean-optimal rates for the h-convex class on every Hadamard manifold (Theorem 3.1), a curvature-adaptive improvement on hyperbolic space via horoball localization (Theorem 3.2), a matching fixed-curvature lower bound (Theorem 3.3), matching bounded-curvature upper and lower bounds for the g-convex class (Theorems 3.4 and 3.5), and a growing-curvature lower bound showing an information-theoretic obstruction for the full g-convex class (Theorem 3.6). The proofs combine a Busemann estimate-sequence framework, a localized parameter search, a curvature-distortion potential, product-manifold transfers of Euclidean hard instances, and an interpolation-based resisting oracle for higher-order derivative data. The manuscript is a theorem paper with no fitted parameters; its proofs are detailed and, in my reading, internally consistent.

Significance. If correct, this is the first higher-order oracle-complexity study for strongly convex optimization on Hadamard manifolds, and the curvature-induced separation between the h-convex and g-convex classes is a substantial conceptual contribution. The paper's strengths include explicit algorithms, a clean Busemann-minorant estimate sequence, a curvature-scale localization lemma, and lower bounds that rest on the external Euclidean hard instance of Kornowski and Shamir rather than on circular reasoning. The main caveat is the disclosed oracle model in Section 2.4, which charges zero cost for geometric primitives, Busemann evaluations, and the Busemann subproblem in Algorithm 1; the h-convex upper bounds are therefore oracle-complexity statements, exactly as the paper states. This is a genuine scope limitation, but it is acknowledged openly and does not invalidate the theorems as formulated.

minor comments (4)
  1. [Section 2.4 and Discussion] The zero-cost treatment of the Busemann subproblem in Algorithm 1 is the most exposed modeling assumption. Since the h-convex upper bounds are the paper's headline results, please state in the abstract or introduction that these are oracle-complexity guarantees, not end-to-end computational guarantees, even though the limitation is already correctly recorded in Section 2.4 and in the Discussion.
  2. [Lemma 4.6] The proof of the horoball intersection is compressed: in the upper-half-plane model there are two horoballs tangent to B(zk,rk) at the indicated point, and the calculation implicitly selects the one with finite ideal point (the disk x^2+y^2≤a^2 y). Please add one sentence explaining why this is the intended horoball 'containing B(zk,rk)' and why the alternative parallel horoball is excluded.
  3. [Proposition 4.5 and Section 4.1] The notation in the parameter search is not fully introduced: the ratio λL/λH is used to describe the low–high bracket, but λL and λH are never explicitly defined. Please define these symbols when the first-step band is introduced.
  4. [Table 1] The rows labeled 'This work' would be easier to check if they referenced the corresponding theorem numbers, as the other rows do; currently the reader must infer the mapping from the table to Theorems 3.1–3.6.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper's rates are derived from explicit proofs and external lower bounds, not from its own assumptions by construction.

full rationale

Walked the derivation chain. Theorem 3.1 is proved from Lemma 4.1 (Busemann minorant derived directly from strong h-convexity), Lemma 4.2 (relative-error condition from the covariant Taylor remainder), and Proposition 4.5 (estimate-sequence epoch), all explicit and internally consistent. Theorem 3.2's curvature improvement is supported by Lemma 4.6, whose horoball-intersection contraction proof is given in the paper, and then by re-running the h-convex upper bound at the localized radius. The fixed-curvature lower bounds (Theorems 3.3 and 3.5) transfer the external Euclidean hard instance of Kornowski and Shamir, an independent benchmark, rather than restating the paper's own claims. The growing-curvature g-convex lower bound (Theorem 3.6) is an explicit interpolation/resisting-oracle construction adapted from Criscitiello and Boumal; it does not assume the conclusion it proves. No fitted parameter is renamed as a prediction; no load-bearing self-citation is present; no uniqueness theorem is imported from the authors. The only substantive caveat is the disclosed oracle model in Section 2.4, which charges no oracle cost for evaluating Busemann functions or solving the Busemann subproblem; the paper states this limitation explicitly and frames all results as oracle-complexity statements. That is a scope limitation, not circularity.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No data-fitting parameters are present; all constants are explicit p-dependent universal constants. The central claims rest on standard differential geometry, imported prior lower-bound constructions, and the oracle-model assumption that Busemann-related computations are free.

assumptions (6)
  • standard math Hadamard manifold geometry: complete, simply connected, nonpositive sectional curvature; global exponential map; unique geodesics.
    Section 2.1 fixes this background for all theorems.
  • standard math Riemannian p-th-order smoothness controls the covariant Taylor remainder (Gutman and Lobo 2026, Proposition 4.12).
    Used in Lemmas 4.2 and 5.1; if the remainder bound is invalid, the relative-error and regularized-step arguments break.
  • domain assumption Euclidean hard instance of Kornowski and Shamir 2021 with the stated transfer regime in Appendix A.
    Theorems 3.3 and 3.5 reduce to this lower-bound source.
  • domain assumption Horospherical convexity machinery and curvature-scale localization of Criscitiello and Kim 2025, including their Proposition 8.
    Definitions 2.2 and Lemma 4.6 import these first-order results; Theorem 3.2's localization step relies on it.
  • domain assumption Distortion and translation inequalities of Martinez-Rubio and Pokutta 2023 for bounded-curvature Hadamard manifolds.
    Theorem 3.4's accelerated potential argument uses these inequalities (equations 5.25 and 5.26).
  • ad hoc to paper Geometric primitives, Busemann evaluations, and the Busemann subproblem in Algorithm 1 cost zero oracle queries.
    Stated in Section 2.4; this modeling choice is necessary for the h-convex upper bounds to be oracle-complexity results rather than computational-complexity results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Blessing and Curse of Curvature in Higher-Order Optimization: Horospherical versus Geodesic Convexity." pith.science (2026). https://pith.science/paper/T6332HFS

@misc{pith2026260806719,
  author       = {Pith},
  title        = {Pith review of: The Blessing and Curse of Curvature in Higher-Order Optimization: Horospherical versus Geodesic Convexity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T6332HFS}},
  note         = {Machine review of arXiv:2608.06719}
}
abstract

We study deterministic Riemannian $p$-th-order oracle complexity (for $p\ge2$) on Hadamard manifolds, under strong horospherical ($h$)-convexity and strong geodesic ($g$)-convexity. The two notions agree in the Euclidean space. On a curved Hadamard manifold, $h$-convexity is a stronger notion than $g$-convexity and supplies global horospherical information. Writing the $p$-th-order condition parameter $Q_p=L_pR^{p-1}/\mu$, we obtain the Euclidean-optimal rate $Q_p^{2/(3p+1)}$ for strongly $h$-convex objectives on every Hadamard manifold, with a matching fixed-curvature lower bound. On hyperbolic space, the resulting horoball supports enable localization to the curvature scale. This replaces the condition parameter $Q_p$ by $Q_p \min\{1, 4/(\kappa R) \}^{p-1}$, subject to a logarithmic localization cost. Thus growing negative curvature ($\kappa R \rightarrow \infty$) can further improve the optimal Euclidean rate under $h$-convexity. For strongly $g$-convex objectives, matching upper and lower bounds recover the same Euclidean exponent when $\kappa R=O(1)$. In contrast, with growing $\kappa R$, we construct a hard family on the hyperbolic space with $Q_p\asymp_p(1+\kappa R)^p$ that requires $\widetilde{\Omega}_p(Q_p^{1/p})$ queries. This reveals a fundamental separation: the same hyperbolic divergence that sharpens horoball localization yields an information-theoretic obstruction for the full $g$-convex class.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 24 canonical work pages

  1. [1]

    Proceedings of the 36th Conference on Learning Theory , series =

    Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties , author =. Proceedings of the 36th Conference on Learning Theory , series =. 2023 , verified =

    work page 2023

  2. [2]

    Proceedings of the 35th Conference on Learning Theory , series =

    Understanding Riemannian Acceleration via a Proximal Extragradient Framework , author =. Proceedings of the 35th Conference on Learning Theory , series =. 2022 , verified =

    work page 2022

  3. [3]

    arXiv preprint arXiv:2010.06642 , year =

    High-Order Oracle Complexity of Smooth and Strongly Convex Optimization , author =. arXiv preprint arXiv:2010.06642 , year =

    arXiv 2010

  4. [4]

    arXiv preprint arXiv:2601.22126 , year =

    An Invitation to Higher-Order Riemannian Optimization: Optimal and Implementable Methods , author =. arXiv preprint arXiv:2601.22126 , year =

    work page arXiv

  5. [5]

    2016 , doi =

    Riemannian Geometry , author =. 2016 , doi =

    work page 2016

  6. [6]

    Proceedings of the 35th Conference on Learning Theory , series =

    Negative Curvature Obstructs Acceleration for Strongly Geodesically Convex Optimization, Even with Exact First-Order Oracles , author =. Proceedings of the 35th Conference on Learning Theory , series =. 2022 , verified =

    work page 2022

  7. [7]

    arXiv preprint arXiv:2505.16970 , year =

    Horospherically Convex Optimization on Hadamard Manifolds Part I: Analysis and Algorithms , author =. arXiv preprint arXiv:2505.16970 , year =

    arXiv

  8. [8]

    2023 , doi =

    An Introduction to Optimization on Smooth Manifolds , author =. 2023 , doi =

    2023

Show all 29 references
  1. [9]

    2014 , verified =

    Convex Analysis and Optimization in Hadamard Spaces , author =. 2014 , verified =

    2014

  2. [10]

    Mathematical Programming , volume =

    Implementable Tensor Methods in Unconstrained Convex Optimization , author =. Mathematical Programming , volume =. 2021 , doi =

    2021

  3. [11]

    SIAM Journal on Optimization , volume =

    An Accelerated Hybrid Proximal Extragradient Method for Convex Optimization and Its Implications to Second-Order Methods , author =. SIAM Journal on Optimization , volume =. 2013 , doi =

    2013

  4. [12]

    Proceedings of the 32nd Conference on Learning Theory , series =

    Near-Optimal Method for Highly Smooth Convex Optimization , author =. Proceedings of the 32nd Conference on Learning Theory , series =. 2019 , verified =

    2019

  5. [13]

    Proceedings of the 32nd Conference on Learning Theory , series =

    Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization , author =. Proceedings of the 32nd Conference on Learning Theory , series =. 2019 , verified =

    2019

  6. [14]

    Proceedings of the 32nd Conference on Learning Theory , series =

    An Optimal High-Order Tensor Method for Convex Optimization , author =. Proceedings of the 32nd Conference on Learning Theory , series =. 2019 , verified =

    2019

  7. [15]

    Advances in Neural Information Processing Systems , volume =

    The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization , author =. Advances in Neural Information Processing Systems , volume =. 2022 , verified =

    2022

  8. [16]

    Proceedings of the 31st Conference on Learning Theory , series =

    Lower Bounds for Higher-Order Convex Optimization , author =. Proceedings of the 31st Conference on Learning Theory , series =. 2018 , verified =

    2018

  9. [17]

    Mathematical Programming , volume =

    Oracle Complexity of Second-Order Methods for Smooth Convex Optimization , author =. Mathematical Programming , volume =. 2019 , doi =

    2019

  10. [18]

    Advances in Neural Information Processing Systems , volume =

    Near-Optimal Lower Bounds for Convex Optimization for All Orders of Smoothness , author =. Advances in Neural Information Processing Systems , volume =. 2021 , verified =

    2021

  11. [19]

    Mathematical Programming , volume =

    Adaptive Regularization with Cubics on Manifolds , author =. Mathematical Programming , volume =. 2021 , doi =

    2021

  12. [20]

    Riemannian Adaptive Regularized Newton Methods with

    Zhang, Chenyu and Jiang, Rujun , journal =. Riemannian Adaptive Regularized Newton Methods with. 2025 , note =

    2025

  13. [21]

    Proceedings of the 29th Annual Conference on Learning Theory , series =

    First-Order Methods for Geodesically Convex Optimization , author =. Proceedings of the 29th Annual Conference on Learning Theory , series =. 2016 , verified =

    2016

  14. [22]

    Proceedings of the 31st Conference on Learning Theory , series =

    An Estimate Sequence for Geodesically Convex Optimization , author =. Proceedings of the 31st Conference on Learning Theory , series =. 2018 , verified =

    2018

  15. [23]

    Ahn, Kwangjun and Sra, Suvrit , booktitle =. From. 2020 , verified =

    2020

  16. [24]

    Proceedings of the 33rd International Conference on Algorithmic Learning Theory , series =

    Global Riemannian Acceleration in Hyperbolic and Spherical Spaces , author =. Proceedings of the 33rd International Conference on Algorithmic Learning Theory , series =. 2022 , verified =

    2022

  17. [25]

    Proceedings of the 39th International Conference on Machine Learning , series =

    Accelerated Gradient Methods for Geodesically Convex Optimization: Tractable Algorithms and Convergence Analysis , author =. Proceedings of the 39th International Conference on Machine Learning , series =. 2022 , verified =

    2022

  18. [26]

    Advances in Neural Information Processing Systems , volume =

    A No-Go Theorem for Robust Acceleration in the Hyperbolic Plane , author =. Advances in Neural Information Processing Systems , volume =. 2021 , verified =

    2021

  19. [27]

    Proceedings of the 36th Conference on Learning Theory , series =

    Curvature and Complexity: Better Lower Bounds for Geodesically Convex Optimization , author =. Proceedings of the 36th Conference on Learning Theory , series =. 2023 , verified =

    2023

  20. [28]

    arXiv preprint arXiv:2403.15749 , year =

    Horoballs and the Subgradient Method , author =. arXiv preprint arXiv:2403.15749 , year =

    arXiv

  21. [29]

    arXiv preprint arXiv:2412.06730 , year =

    A Subgradient Splitting Algorithm for Optimization on Nonpositively Curved Metric Spaces , author =. arXiv preprint arXiv:2412.06730 , year =

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.