REVIEW 2 major objections 6 minor 1 cited by
Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives
T0 review · 2 major / 6 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read This paper establishes curvature-independent O(√T) and O(log T) regret bounds for Riemannian online gradient descent on Hadamard manifolds, provided the losses are h-convex or strongly h-convex, respectively.
desk verdict A short, mostly sound paper that gives the first online regret analysis for h-convex functions, but the headline O(√T) bound rides on two unproven imports from a preprint; worth refereeing, not desk-rejecting. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the Busemann function B_{p,v}(x)=lim_{t→∞}(d(γ(t),x)−t), which generalizes affine functions to Hadamard manifolds. A function is h-convex if at every point y it is bounded below by some scaled Busemann function B_{y,v}, and it is µ-strongly h-convex if it is bounded below by a quadratic expression Q_{y,v}^µ(x)=−‖v‖²/(2µ)+(µ/2)d²(Exp_y(−v/µ),x). These definitions let the regret proof replace the Euclidean inner-product expansion with Busemann-function identities and a quadratic inequality from the cited preprint [9]. For the strong case, a newly proved Stewart-type inequality for geodesic triangles (Lemma 2.4) is used to telescope the distance terms. The ROGD update itse
What would settle it
Take a known h-convex function on a Hadamard manifold, such as f(Σ)=log(a^T Σ^{-1}a) on SPD(n), and directly verify whether the inequality f(x)−f(y) ≥ B_{y,grad f(y)}(x) holds for all x,y in the feasible set; a single counterexample would invalidate the first step of Theorem 3.3's proof. More generally, one could search for an h-convex function whose Busemann subgradient at some point is not collinear with the Riemannian gradient.
Extended reading notes
Core claim
The paper's central claim is that the Riemannian Online Gradient Descent algorithm achieves Euclidean-level static regret guarantees on Hadamard manifolds when the loss functions are h-convex. Theorem 3.3 gives O(√T) regret for h-convex losses with step size 1/√T, and Theorem 3.5 gives O(log T) regret for µ-strongly h-convex losses with step size 1/(µt). Both bounds are independent of the sectional curvature, unlike earlier g-convex analyses in [31] that carried curvature-dependent constants. The proof uses the outer characterization of convexity via Busemann functions: the defining inequality f(x)−f(y) ≥ B_{y,v}(x) is combined with a quadratic estimate for Busemann functions (Lemma 2 of [9]
Load-bearing premise
The load-bearing premise is that the tangent vector appearing in the definitions of h-convexity and strong h-convexity is always the Riemannian gradient of the loss; the paper relies on a cited preprint for this identification and does not prove it itself.
Editorial extensions
If this is right
- If h-convexity holds, online Riemannian optimization on Hadamard manifolds achieves O(√T) static regret with no curvature-dependent constants, matching the Euclidean baseline.
- For µ-strongly h-convex objectives, the same algorithm achieves O(log T) regret, matching the Euclidean strongly-convex rate.
- The results apply directly to concrete problems on the SPD manifold: online Tyler's M-estimation (h-convex) and online Fréchet mean estimation (1-strongly h-convex), both demonstrated numerically.
- Since no lower bound on sectional curvature is assumed, the guarantees hold uniformly across all Hadamard manifolds, including those with unbounded negative curvature.
- The curvature-free bound suggests that curvature was an artifact of the g-convexity analysis rather than an intrinsic obstacle to fast online learning on manifolds.
Reading between the lines
- The paper's proof structure suggests that extending ROGD to stochastic or decentralized settings is likely to preserve the curvature-independent rates, because the curvature terms were removed via Busemann-function inequalities rather than gradient clipping or projection weighting.
- If h-convexity is indeed the right lens, then the practical bottleneck shifts to computing Busemann-type subgradients for a given loss; for many problems such as Tyler's M-estimator these have simple closed forms, but for general losses the gradient identification remains a nontrivial geometric question.
- The Stewart-type triangle inequality (Lemma 2.4) may find independent use in other geometric optimization and convex analysis proofs on Hadamard spaces, as a clean substitute for curvature-dependent comparison theorems.
- A concrete testable extension would be to check whether the same curvature-free regret bounds survive under bandit (gradient-free) feedback, where one must estimate Busemann subgradients from function values; the paper does not address this case.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies Riemannian online gradient descent (ROGD) on Hadamard manifolds under a notion of horospherical convexity (h-convexity) defined via Busemann functions. It claims O(√T) static regret for h-convex losses and O(log T) static regret for µ-strongly h-convex losses, with constants that do not depend on sectional curvature. The proof of Theorem 3.3 imports a quadratic Busemann inequality from the preprint [9], and the proof of Theorem 3.5 uses an in-paper Stewart-type inequality for Hadamard triangles (Lemma 2.4). Experiments on SPD(n) with the affine-invariant metric test online Tyler M-estimation and online Fréchet mean computation.
Significance. If the imported technical results hold, the paper provides a meaningful extension of online Riemannian optimization from geodesic convexity to h-convexity, removing curvature-dependent constants from the regret bounds and matching Euclidean rates. The in-paper algebra is sound: Lemma 2.4 is correctly proved, and the telescoping argument in Theorem 3.5 checks out. The strong h-convexity definition is a natural Busemann-analogue of Euclidean strong convexity. The main weakness is not the internal derivation but a load-bearing dependence on two unstated results from the unpublished preprint [9] and an implicit identification of the subgradient vector with the Riemannian gradient. These issues are fixable within the scope of the paper.
major comments (2)
- [Section III.C, proof of Theorem 3.3] The proof uses two results from [9] without stating them: (i) Proposition 2(iii), which identifies the vector in Definition 2.2 with the Riemannian gradient g_t, and (ii) Lemma 2, which gives the quadratic estimate -B_{x_t,g_t}(x*) = -B_{x_t,ηg_t}(x*)/η ≤ (|x̃_{t+1}x_t|^2 + |x*x_t|^2 - |x*x̃_{t+1}|^2)/(2η). The entire O(√T) guarantee depends on these imported statements. Since [9] is an arXiv preprint and the lemma is not reproduced, the bound cannot be verified from the manuscript. If Lemma 2 of [9] has any additional hypothesis (e.g., a restriction on η||g_t||, a differentiability assumption, or a requirement on x*), the displayed inequality may fail. Please state Lemma 2 in full with its hypotheses and either prove it or give a precise, verifiable reference; do the same for the gradient-identification result.
- [Section II.B / Algorithm 1 and Assumption 3.2] Algorithm 1 requires the Riemannian gradient g_t = grad f_t(x_t), but Assumption 3.2 only assumes Lipschitz continuity. Definitions 2.2 and 2.3 guarantee only the existence of some tangent vector v at each point y satisfying the relevant inequality, not differentiability or uniqueness. The proofs of Theorems 3.3 and 3.5 implicitly set v = g_t and use ||g_t|| ≤ L without stating or proving that this is the vector supplied by the h-convexity definition. Either add differentiability to Assumption 3.2, or reformulate the update in terms of a horospherical subgradient v_t and prove that the chosen v_t satisfies the same norm bound. As written, the chain from definitions to regret bounds has a gap.
minor comments (6)
- [Section II.A] The regret definition is written as Regret_T := ∑ f_t(x_t) − argmin_{x∈X} ∑ f_t(x); the argmin should be inside the sum, i.e., Regret_T := ∑ f_t(x_t) − min_{x∈X} ∑ f_t(x), or introduce x* = argmin and write Regret_T := ∑ (f_t(x_t) − f_t(x*)).
- [Section III.C, proof of Theorem 3.5] The proof divides by |x_t x̃_{t+1}| = η_t ||g_t||. When ||g_t|| = 0, this factor is zero. The case g_t = 0 should be handled separately or by a continuity argument.
- [Definition 2.3] The parameter µ is used without stating µ > 0. It should be stated explicitly, as the strong-convexity inequality only makes sense for positive µ.
- [Section IV] The theory for h-convex losses (Theorem 3.3) uses a constant step-size η = 1/√T, whereas the experiments use the decreasing schedule η_t = η/√t. No regret bound is proved for this schedule. For the strongly h-convex experiment, values of η larger than 1 violate the condition η_t ≤ 1/µ at early rounds if µ = 1. Please either extend the theory to the schedules used or adjust the experiments/statements to match the proved step-size conditions.
- [Section IV] The paper states that the Tyler loss and the squared-distance loss are h-convex / 1-strongly h-convex, citing [9] informally. Since these claims are used to interpret the experiments, please give precise statements or exact references (proposition numbers) in [9], or prove them in an appendix.
- [General] The text says 'h-convexity forms a subclass of g-convexity' but gives no proof or precise statement. A citation to [9] is given, but the exact proposition would be helpful, especially because the paper relies on this relationship for motivation.
Circularity Check
No circularity: the regret bounds follow from the h-convexity definitions plus external Busemann-function lemmas; no fitted parameter is relabeled as a prediction.
full rationale
The derivation chain is not circular. Theorem 3.3 uses Definition 2.2 plus imported facts from the external preprint [9] (Proposition 2(iii) and Lemma 2) to convert Busemann-function lower bounds into a quadratic telescope; the rest of the proof is standard non-expansiveness of projection and the Lipschitz bound. Theorem 3.5 uses Definition 2.3, the in-paper Lemma 2.4 (proved from the Hadamard cosine law), a triangle-inequality argument, and a telescoping sum with step size η_t=1/(µt). None of these steps assumes the target regret bound. The constants L, D, and µ are assumptions, not fitted parameters, and no computed quantity is renamed as a prediction. The self-citation [20] appears only in a literature-review sentence and is not load-bearing. The main external dependencies are technical lemmas from [9] about Busemann functions and gradients; they are not equivalent to the regret conclusion, and their unproved status is a robustness/correctness concern, not circularity. Therefore no circularity pattern is present.
Assumptions & free parameters
assumptions (7)
- domain assumption Each loss f_t is h-convex (Definition 2.2) or µ-strongly h-convex (Definition 2.3)
- domain assumption The decision set X is a g-convex subset with bounded diameter D (Assumption 3.1)
- domain assumption Each f_t is L-Lipschitz (Assumption 3.2)
- domain assumption Differentiability of each f_t and existence of the Riemannian gradient g_t
- standard math Busemann subgradient inequality and homogeneity B_{x,cv}=cB_{x,v}, and the quadratic potential estimate in Lemma 2 of [9]
- standard math Non-expansiveness of the metric projection onto a g-convex set in a Hadamard manifold
- standard math Cosine law for Hadamard spaces (cited to [2])
Cite this review
Pith. "Pith review of Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives." pith.science (2026). https://pith.science/paper/B7JAEDXD
@misc{pith2026250911236,
author = {Pith},
title = {Pith review of: Online Optimization on Hadamard Manifolds: Curvature Independent Regret Bounds on Horospherically Convex Objectives},
year = {2026},
howpublished = {\url{https://pith.science/paper/B7JAEDXD}},
note = {Machine review of arXiv:2509.11236}
}
abstract
We study online Riemannian optimization on Hadamard manifolds under the framework of horospherical convexity (h-convexity). Prior work mostly relies on the geodesic convexity (g-convexity), leading to regret bounds scaling poorly with the manifold curvature. To address this limitation, we analyze Riemannian online gradient descent for h-convex and strongly h-convex functions and establish $O(\sqrt{T})$ and $O(\log(T))$ regret guarantees, respectively. These bounds are curvature-independent and match the results in the Euclidean setting. We validate our approach with experiments on the manifold of symmetric positive definite (SPD) matrices equipped with the affine-invariant metric. In particular, we investigate online Tyler's $M$-estimation and online Fr\'echet mean computation, showing the application of h-convexity in practice.
Figures
Forward citations
Cited by 1 Pith paper
-
Decentralized Online Riemannian Optimization for Strongly Geodesically Convex Functions
Decentralized online Riemannian gradient descent with a decaying step size achieves O(log T) static regret for strongly geodesically convex losses on manifolds with bounded sectional curvature, under full and two-poin...
Reference graph
Works this paper leans on
-
[9]
Horospherically convex optimization on hadamard manifolds part i: Analysis and algorithms
Christopher Criscitiello and Jungbin Kim. Horospherically convex optimization on hadamard manifolds part i: Analysis and algorithms. arXiv preprint arXiv:2505.16970, 2025
arXiv 2025
-
[1]
Optimization algorithms on matrix manifolds
P-A Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization algorithms on matrix manifolds. InOptimization Algorithms on Matrix Manifolds. Princeton University Press, 2009
2009
-
[2]
A continuous-time perspective for modeling acceleration in riemannian optimization
Foivos Alimisis, Antonio Orvieto, Gary B ´ecigneul, and Aurelien Lucchi. A continuous-time perspective for modeling acceleration in riemannian optimization. InInternational Conference on Artificial Intelligence and Statistics, pages 1297–1307. PMLR, 2020
2020
-
[3]
Walter de Gruyter GmbH & Co KG, 2014
Miroslav Bac ´ak.Convex analysis and optimization in Hadamard spaces, volume 22. Walter de Gruyter GmbH & Co KG, 2014
2014
-
[4]
Stochastic gradient descent on riemannian manifolds
Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217–2229, 2013
2013
-
[5]
Cambridge University Press, 2023
Nicolas Boumal.An introduction to optimization on smooth manifolds. Cambridge University Press, 2023
2023
-
[6]
Hengchao Chen and Qiang Sun. Decentralized online riemannian opti- mization with dynamic environments.arXiv preprint arXiv:2410.05128, 2024
arXiv 2024
-
[7]
Decentralized riemannian gradient descent on the stiefel manifold
Shixiang Chen, Alfredo Garcia, Mingyi Hong, and Shahin Shahrampour. Decentralized riemannian gradient descent on the stiefel manifold. InInternational Conference on Machine Learning, pages 1594–1605. PMLR, 2021
2021
Show all 34 references
-
[8]
Riemannian dictionary learning and sparse coding for positive definite matrices.IEEE transactions on neural networks and learning systems, 28(12):2859–2871, 2016
Anoop Cherian and Suvrit Sra. Riemannian dictionary learning and sparse coding for positive definite matrices.IEEE transactions on neural networks and learning systems, 28(12):2859–2871, 2016
2016
-
[10]
The geometry of algorithms with orthogonality constraints.SIAM journal on Matrix Analysis and Applications, 20(2):303–353, 1998
Alan Edelman, Tom ´as A Arias, and Steven T Smith. The geometry of algorithms with orthogonality constraints.SIAM journal on Matrix Analysis and Applications, 20(2):303–353, 1998
1998
-
[11]
A subgradient splitting algorithm for optimization on nonpos- itively curved metric spaces.arXiv preprint arXiv:2412.06730, 2024
Ariel Goodwin, Adrian S Lewis, Genaro L ´opez-Acedo, and Adriana Nicolae. A subgradient splitting algorithm for optimization on nonpos- itively curved metric spaces.arXiv preprint arXiv:2412.06730, 2024
2024
-
[12]
Introduction to online convex optimization.Founda- tions and Trends® in Optimization, 2(3-4):157–325, 2016
Elad Hazan et al. Introduction to online convex optimization.Founda- tions and Trends® in Optimization, 2(3-4):157–325, 2016
2016
-
[13]
Convex analysis on hadamard spaces and scaling problems.Foundations of Computational Mathematics, 24(6):1979– 2016, 2024
Hiroshi Hirai. Convex analysis on hadamard spaces and scaling problems.Foundations of Computational Mathematics, 24(6):1979– 2016, 2024
1979
-
[14]
Riemannian projection-free online learning.Advances in Neural Information Pro- cessing Systems, 36:41980–42014, 2023
Zihao Hu, Guanghui Wang, and Jacob D Abernethy. Riemannian projection-free online learning.Advances in Neural Information Pro- cessing Systems, 36:41980–42014, 2023
2023
-
[15]
Horoballs and the subgradient method.arXiv preprint arXiv:2403.15749, 2024
Adrian S Lewis, Genaro Lopez-Acedo, and Adriana Nicolae. Horoballs and the subgradient method.arXiv preprint arXiv:2403.15749, 2024
2024 arXiv
-
[16]
Cheap orthogonal constraints in neural networks: A simple parametrization of the or- thogonal and unitary group
Mario Lezcano-Casado and David Martınez-Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the or- thogonal and unitary group. InInternational Conference on Machine Learning, pages 3794–3803. PMLR, 2019
2019
-
[17]
Tracking and regret bounds for online zeroth-order euclidean and riemannian optimization.SIAM Journal on Optimization, 32(2):445–469, 2022
Alejandro I Maass, Chris Manzie, Dragan Nesic, Jonathan H Manton, and Iman Shames. Tracking and regret bounds for online zeroth-order euclidean and riemannian optimization.SIAM Journal on Optimization, 32(2):445–469, 2022
2022
-
[18]
A differential geometric approach to the geometric mean of symmetric positive-definite matrices.SIAM journal on matrix analysis and applications, 26(3):735–747, 2005
Maher Moakher. A differential geometric approach to the geometric mean of symmetric positive-definite matrices.SIAM journal on matrix analysis and applications, 26(3):735–747, 2005
2005
-
[19]
Poincar ´e embeddings for learning hierarchical representations.Advances in neural information processing systems, 30, 2017
Maximillian Nickel and Douwe Kiela. Poincar ´e embeddings for learning hierarchical representations.Advances in neural information processing systems, 30, 2017
2017
-
[20]
Decentralized online rie- mannian optimization beyond hadamard manifolds.arXiv preprint arXiv:2509.07779, 2025
Emre Sahinoglu and Shahin Shahrampour. Decentralized online rie- mannian optimization beyond hadamard manifolds.arXiv preprint arXiv:2509.07779, 2025
2025 arXiv
-
[21]
Consensus optimization on manifolds.SIAM journal on Control and Optimization, 48(1):56–76, 2009
Alain Sarlette and Rodolphe Sepulchre. Consensus optimization on manifolds.SIAM journal on Control and Optimization, 48(1):56–76, 2009
2009
-
[22]
Hiroyuki Sato.Riemannian optimization and its applications, volume
-
[23]
Riemannian optimization on unit sphere with p-norm and its applications.Computational Optimization and Applications, 85(3):897–935, 2023
Hiroyuki Sato. Riemannian optimization on unit sphere with p-norm and its applications.Computational Optimization and Applications, 85(3):897–935, 2023
2023
-
[24]
Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport.SIAM Journal on Optimization, 29(2):1444–1472, 2019
Hiroyuki Sato, Hiroyuki Kasai, and Bamdev Mishra. Riemannian stochastic variance reduced gradient algorithm with retraction and vector transport.SIAM Journal on Optimization, 29(2):1444–1472, 2019
2019
-
[25]
Riemannian optimal identification method for linear systems with symmetric positive-definite matrix.IEEE Transactions on Automatic Control, 65(11):4493–4508, 2019
Kazuhiro Sato, Hiroyuki Sato, and Tobias Damm. Riemannian optimal identification method for linear systems with symmetric positive-definite matrix.IEEE Transactions on Automatic Control, 65(11):4493–4508, 2019
2019
-
[26]
Retraction-free decentralized non-convex optimization with orthogonal constraints.arXiv preprint arXiv:2405.11590, 2024
Youbang Sun, Shixiang Chen, Alfredo Garcia, and Shahin Shahrampour. Retraction-free decentralized non-convex optimization with orthogonal constraints.arXiv preprint arXiv:2405.11590, 2024
2024 arXiv
-
[27]
Policy optimization over subman- ifolds for linearly constrained feedback synthesis.IEEE Transactions on Automatic Control, 69(5):3024–3039, 2023
Shahriar Talebi and Mehran Mesbahi. Policy optimization over subman- ifolds for linearly constrained feedback synthesis.IEEE Transactions on Automatic Control, 69(5):3024–3039, 2023
2023
-
[28]
Low-rank matrix completion by riemannian opti- mization.SIAM Journal on Optimization, 23(2):1214–1236, 2013
Bart Vandereycken. Low-rank matrix completion by riemannian opti- mization.SIAM Journal on Optimization, 23(2):1214–1236, 2013
2013
-
[29]
Geodesic convex optimization: Differentiation on manifolds, geodesics, and convexity.arXiv preprint arXiv:1806.06373, 2018
Nisheeth K Vishnoi. Geodesic convex optimization: Differentiation on manifolds, geodesics, and convexity.arXiv preprint arXiv:1806.06373, 2018
2018 arXiv
-
[30]
Riemannian online learning.Foundations and Trends® in Optimization, 9(3):248–406, 2025
Xi Wang and Guodong Shi. Riemannian online learning.Foundations and Trends® in Optimization, 9(3):248–406, 2025
2025
-
[31]
Online optimization over riemannian manifolds.Journal of Machine Learning Research, 24(84):1–67, 2023
Xi Wang, Zhipeng Tu, Yiguang Hong, Yingyi Wu, and Guodong Shi. Online optimization over riemannian manifolds.Journal of Machine Learning Research, 24(84):1–67, 2023
2023
-
[32]
Riemannian online optimistic algorithms with dynamic regret.IEEE Transactions on Automatic Control, 2025
Xi Wang, Deming Yuan, Yiguang Hong, Zihao Hu, Lei Wang, and Guodong Shi. Riemannian online optimistic algorithms with dynamic regret.IEEE Transactions on Automatic Control, 2025
2025
-
[33]
Riemannian svrg: Fast stochastic optimization on riemannian manifolds.Advances in Neural Information Processing Systems, 29, 2016
Hongyi Zhang, Sashank J Reddi, and Suvrit Sra. Riemannian svrg: Fast stochastic optimization on riemannian manifolds.Advances in Neural Information Processing Systems, 29, 2016
2016
-
[34]
First-order methods for geodesically convex optimization
Hongyi Zhang and Suvrit Sra. First-order methods for geodesically convex optimization. InConference on learning theory, pages 1617–
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.