{"id":"ffc3aa0a-bf4e-4b52-8ab9-ac654cd9c491","arxiv_id":"2608.06719","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For strongly horospherically convex functions, negative curvature preserves or improves the Euclidean-optimal higher-order oracle rate; for strongly geodesically convex functions, growing negative curvature forces a strictly worse rate.","lead":"This paper studies how many rounds of higher-order derivative queries are needed to minimize smooth convex functions on curved spaces. It shows that one notion of convexity makes negative curvature helpful, while another makes it an obstacle, with matching upper and lower bounds.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the only substantive caveat is the disclosed oracle-model assumption that Busemann subproblems incur no oracle cost.","rationale":"The paper's central claim is a statement about deterministic exact Riemannian p-th-order oracle complexity, and every theorem is scoped in those terms. The reader's weakest assumption, the free Busemann subproblem in Section 2.4, is indeed the most exposed modeling choice, but it is disclosed and is not an internal inconsistency. The formal upper bounds hold within the stated oracle model, and the lower bounds are constructed within the same model. I checked the main proof mechanisms: the Busemann minorant in Lemma 4.1, the estimate-sequence invariant in Lemma 4.4, the epoch growth bound in Proposition 4.5, the curvature-scale localization in Lemma 4.6, the distorted potential in Lemma 5.3, and the interpolation/volume-counting adversary in Lemma 7.2. Each step has the assumptions needed for the subsequent conclusion. The one place I would ask for extra care is the claim in Lemma 7.2 that perturbations vanish near active minimizers, which ensures local minimality but global minimality also requires a sup-norm bound on the accumulated perturbation; this is readily supplied by the derivative bounds and a large r_p, so it is a presentational gap rather than a load-bearing error. Given the explicit scope limitation and the absence of a found correctness error, the reader's ACCEPT verdict remains appropriate.","tokens_in":28327,"tokens_out":34396,"duration_ms":316638,"concrete_test":"Worth running as a scope check: implement Algorithm 1 on H^2_kappa for the h-convex objective f(x)=d(x,x*)^2/2, and solve the Busemann subproblem min_x { d(x,omega)^2/2 + a||v|| b(x) } with a certified convex solver. Record both the number of Riemannian p-th-order f-oracle calls and the solver iteration count as functions of Q_p and kappa R. If the subproblem solver requires f-oracle accesses or its iteration count grows faster than O(log(1/epsilon)), the upper bound should be restated as an oracle-complexity result with an explicit computational caveat; if the solver is oracle-free and efficient, the caveat is immaterial.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I reviewed the central separation claim and its supporting proofs in good faith. The h-convex upper bound (Theorem 3.1), the curvature-adaptive localization (Lemma 4.6 and Theorem 3.2), the fixed-curvature transfer lower bound (Theorem 3.3), the bounded-curvature g-convex upper and lower bounds (Theorems 3.4 and 3.5), and the growing-curvature resisting oracle (Lemma 7.2 and Theorem 3.6) are internally consistent. The estimate-sequence algebra in Section 4, the xi_D-distorted potential in Section 5, and the interpolation plus volume-counting argument in Section 7 all appear to match the stated assumptions. The single most exposed point is Section 2.4's oracle model, which charges no cost for evaluating Busemann functions or for solving the Busemann subproblem in Algorithm 1, and likewise treats all finite-dimensional computation as free. This is a genuine scope limitation: if those subproblems are computationally hard or require additional f-oracle accesses, the h-convex results are oracle-complexity statements rather than end-to-end iterative guarantees. However, the paper explicitly states this limitation in Section 2.4 and in the Discussion, and the theorems are framed as exact Riemannian p-th-order oracle complexity, following the standard convention in the cited Euclidean and Riemannian lower-bound literature. I found no internal inconsistency and no unstated assumption that would invalidate the stated theorems.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28626,"tokens_out":39564,"duration_ms":349779,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Section 2.4 and Discussion"},{"comment":"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.","section":"Lemma 4.6"},{"comment":"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.","section":"Proposition 4.5 and Section 4.1"},{"comment":"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.","section":"Table 1"}],"recommendation":"minor_revision","confidential_remarks":"For the editor: the manuscript is well within the scope of math.OC and the result is significant. I found no internal inconsistency or unstated assumption that would invalidate the stated theorems. The only substantive caveat is that the h-convex upper bounds are oracle-complexity results conditional on free geometric computation, which the authors disclose; I recommend the revision ask them to keep that caveat visible in the abstract-level statements. The paper's engagement with the prior literature and its explicit acknowledgment of the open problems are appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the paper in one line: it gives the first higher-order oracle-complexity treatment of strongly convex optimization on Hadamard manifolds, and the h-versus-g convexity separation is genuine. I read the main arguments carefully and the claims hold up. What's new: the authors extend Criscitiello and Kim's first-order h-convex framework to p-th order oracles. Theorem 3.1 gets the Euclidean-optimal Q_p^{2/(3p+1)} rate on every Hadamard manifold; Theorem 3.2 shows that on hyperbolic space the effective condition parameter improves to Q_p min{1,4/(kappa R)}^{p-1} after O(log(1+kappa R)) localization queries; Theorem 3.3 gives a matching fixed-curvature lower bound. For g-convex objectives, Theorems 3.4 and 3.5 recover the same Euclidean exponent when kappa R = O(1), and Theorem 3.6 builds a growing-curvature hard family requiring Omega_p(Q_p^{1/p}) queries. That last construction, using local interpolation to preserve derivative data, is the most technically novel part. The proof structure is consistent: the estimate sequence with Busemann minorants, the curvature localization lemma, the product-manifold transfer, and the volume-counting adversary all check out. The lower bounds reduce to the Kornowski-Shamir Euclidean hard instance, which is the right external benchmark. The citation pattern is careful and the paper is honest about what it does and does not claim. Soft spots: the main one is the oracle model in Section 2.4. Geometric primitives, Busemann evaluations, and solving the Busemann subproblem in Algorithm 1 are treated as free, so the h-convex upper bounds are oracle-complexity statements, not end-to-end computational guarantees. This is disclosed, and it follows the standard convention in the lower-bound literature, but it is a real scope limit. The bounded-curvature upper bound's dependence on xi_D is not claimed optimal, and the growing-curvature results are one-sided; both are minor relative to the core contribution. I did not machine-check all algebra, but I found no load-bearing error or unstated assumption. This paper is for optimization theorists working on Riemannian optimization or oracle complexity. It deserves a serious referee; I would send it out. The caveats are modeling assumptions, not internal contradictions.","headline":"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.","tokens_in":29090,"tokens_out":2416,"would_cite":true,"duration_ms":21488,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C48","52A41","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Negative curvature is a blessing for one convexity and a curse for another","keywords":["higher-order optimization","Hadamard manifolds","horospherical convexity","geodesic convexity","oracle complexity","hyperbolic space","Busemann functions","negative curvature"],"falsifier":"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.","tokens_in":28146,"feed_emoji":"🧮","tokens_out":9075,"duration_ms":82398,"temperature":0.7,"pith_summary":"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.","feed_headline":"Negative curvature is a blessing for one convexity and a curse for another","feed_subtitle":"On hyperbolic space, horospherically convex problems beat the Euclidean rate while geodesically convex ones provably get harder.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Introduces horospherical convexity, the Busemann-subgradient machinery, and the hyperbolic localization procedure that Theorem 3.2 reuses and rescales.","marker":"Criscitiello and Kim, 2025"},{"why":"Supplies the Euclidean strongly convex higher-order lower bound and hard instance whose exponent and transfer regime anchor Theorems 3.1, 3.3, and 3.5.","marker":"Kornowski and Shamir, 2021"},{"why":"Provides the accelerated regularized tensor method whose estimate-sequence framework the horospherically convex upper bound adapts to manifolds.","marker":"Nesterov, 2021"},{"why":"Gives the exact value-and-gradient resisting oracle on the hyperbolic plane that Theorem 3.6 extends to full $p$-th-order derivative replies.","marker":"Criscitiello and Boumal, 2022"},{"why":"Supplies the projected accelerated Riemannian scheme and distortion inequalities used in the bounded-curvature geodesically convex upper bound.","marker":"Martínez-Rubio and Pokutta, 2023"},{"why":"Provides the Riemannian $p$-th-order Taylor remainder and pullback regularity apparatus used to license oracle queries.","marker":"Gutman and Lobo, 2026"},{"why":"Is the source of resolvent nonexpansiveness in Hadamard spaces used in the horospherically convex regularized step.","marker":"Bačák, 2014"},{"why":"Gives the curvature distortion factor $\\zeta_\\kappa(s)$ that quantifies the bounded-curvature regime for geodesically convex optimization.","marker":"Zhang and Sra, 2016"}],"fun_headline_variants":["Curvature's double edge: helps h-convex, hurts g-convex","On curved space, horospherical convexity outruns geodesic","Hyperbolic divergence: speeds up one optimizer, blocks another","Why negative curvature boosts h-convex but cripples g-convex"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Curvature's double edge: helps h-convex, hurts g-convex","On curved space, horospherical convexity outruns geodesic","Hyperbolic divergence: speeds up one optimizer, blocks another","Why negative curvature boosts h-convex but cripples g-convex"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00069,"raw_usage":{"total_tokens":3257,"prompt_tokens":1212,"completion_tokens":2045,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":828,"completion_tokens_details":{"reasoning_tokens":1968}},"tokens_in":828,"tokens_out":2045,"duration_ms":13913,"temperature":1.0,"reasoning_tokens":1968,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:52:27.267524+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}