pith. sign in

arxiv: 2604.27078 · v1 · submitted 2026-04-29 · 🧮 math.OC

Nonsmooth Riemannian optimization with inexact manifold primitives via bundle methods

Mateo D\'iaz , Benjamin Grimmer , Ian McPherson This is my paper

Pith reviewed 2026-05-07 08:54 UTC · model grok-4.3

classification 🧮 math.OC MSC 90C2590C3053C22
keywords nonsmooth optimizationRiemannian optimizationbundle methodsgeodesic convexityHadamard manifoldsoracle complexityinexact retractions
0
0 comments X

The pith

A proximal bundle method delivers the first non-asymptotic rates for nonsmooth geodesically convex optimization on Hadamard manifolds using only subgradients and inexact retractions.

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

The paper introduces a proximal bundle algorithm that minimizes nonsmooth functions whose level sets are geodesically convex on Hadamard manifolds. It proves that the method attains sublinear oracle complexity when only subgradient information and approximate manifold operations are available, and improves to linear convergence when the objective satisfies a sharp growth condition. This matters because standard Riemannian solvers rely on expensive exact exponential maps and parallel transports, while practical code uses cheaper first-order approximations; the new bounds remove the need for exact primitives while still guaranteeing progress. The analysis adapts Euclidean bundle techniques by controlling the errors introduced by inexact retractions and vector transports at each step.

Core claim

The central claim is that a proximal bundle method, built from subgradient oracles and inexact first-order retractions together with vector transports, solves nonsmooth geodesically convex problems on Hadamard manifolds at sublinear rates in general and at optimal linear rates under sharp function growth. The rates are the first non-asymptotic bounds that do not require exact manifold primitives.

What carries the argument

A proximal bundle method that maintains a cutting-plane lower model of the objective and solves proximal subproblems on the manifold, with error tolerances on the inexact retractions and vector transports explicitly folded into the convergence analysis.

If this is right

  • Sublinear rates hold for any nonsmooth geodesically convex objective when only subgradients and inexact primitives are supplied.
  • Linear convergence is recovered under a sharp growth condition without tightening the inexactness tolerances.
  • The complexity bounds depend explicitly on the accuracy parameters of the retractions and transports.
  • The method remains well-defined even when the exponential map is replaced by any first-order retraction that satisfies the given error model.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same error-control strategy might let bundle methods handle stochastic subgradients on manifolds without losing the non-asymptotic guarantees.
  • Hyperbolic space and the manifold of positive-definite matrices are immediate test beds where the inexact primitives are already implemented in software.
  • Relaxing the Hadamard assumption to local geodesic convexity would require replacing global proximal subproblems with local ones and tracking curvature effects.
  • The explicit dependence on retraction accuracy suggests a practical trade-off: cheaper but coarser approximations can be used early and refined later to preserve the overall rate.

Load-bearing premise

The manifold must be Hadamard so that geodesic convexity holds globally, and the inexact retractions and vector transports must obey explicit error bounds that the convergence proofs require.

What would settle it

Numerical runs on a Hadamard manifold in which the retraction error exceeds the paper's stated tolerance and the observed convergence rate exceeds the predicted sublinear bound.

Figures

Figures reproduced from arXiv: 2604.27078 by Benjamin Grimmer, Ian McPherson, Mateo D\'iaz.

Figure 1
Figure 1. Figure 1: Minimizing Riemannian median objective (5.3) for S 55 + , for 20 random data points. Solid lines correspond with using exponential maps, the dashed with the first order retraction (5.2). Projection transports are used by all bundle methods. given by PY ←-X(ξX) = X 1 2 exp( X− 1 2 ηXX− 1 2 2 )X− 1 2 ξXX− 1 2 exp( X− 1 2 ηXX− 1 2 2 )X 1 2 , where ηX = logX(Y ), is the parallel transport. Both expressions req… view at source ↗
Figure 2
Figure 2. Figure 2: Minimizing total variation denoising objective view at source ↗
read the original abstract

Optimization on Hadamard manifolds -- the natural Riemannian setting for globally geodesically convex problems -- relies on exponential maps to retract tangent vectors and parallel transport to connect tangent spaces across the manifold. These primitives are often computationally expensive, leading software packages to rely on approximations: first-order retractions and vector transports. However, existing results for optimization on Hadamard manifolds either require exact primitives or lack non-asymptotic rates. We bridge this gap by introducing a proximal bundle method for nonsmooth geodesically convex optimization and establishing the first oracle-complexity bounds that rely only on subgradients and inexact primitives. We obtain sublinear rates for general objectives and optimal linear convergence under sharp function growth.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper introduces a proximal bundle method for nonsmooth geodesically convex optimization on Hadamard manifolds. It establishes the first oracle-complexity bounds that depend only on subgradient information together with inexact first-order retractions and vector transports, yielding sublinear rates for general objectives and optimal linear convergence under sharp function growth.

Significance. If the stated rates hold, the work is significant because it supplies the first non-asymptotic guarantees for this class of problems while explicitly accounting for the approximation errors that arise in practical software implementations of manifold primitives. The explicit error propagation analysis from inexact retractions and transports into the bundle subgradient model, together with the recovery of optimal linear rates under growth conditions, constitutes a clear technical advance over prior Riemannian bundle methods that required exact primitives.

minor comments (3)
  1. [Abstract] Abstract: the phrase 'the first oracle-complexity bounds' should be qualified by the precise dependence on the inexactness tolerances of the retraction and transport oracles.
  2. The paper should include a short table or remark comparing the obtained rates with the corresponding Euclidean proximal bundle rates to highlight the additional factors introduced by the manifold setting.
  3. Notation for the inexactness parameters (e.g., the constants controlling retraction and transport errors) should be introduced once in a dedicated subsection and used consistently thereafter.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript, the accurate summary of its contributions, and the recommendation for minor revision. We are pleased that the significance of establishing the first non-asymptotic oracle complexity bounds for nonsmooth geodesically convex optimization on Hadamard manifolds, relying only on subgradients and inexact first-order retractions and vector transports, has been recognized.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper introduces a proximal bundle method for nonsmooth geodesically convex optimization on Hadamard manifolds, controlling errors from inexact retractions and vector transports to derive sublinear and linear oracle-complexity bounds. These rates follow from adapting standard Euclidean bundle-method analysis (with explicit error propagation) to the Riemannian setting under geodesic convexity and Hadamard assumptions. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the central claims rest on independent modeling of inexact primitives and convexity exploitation rather than renaming or smuggling ansatzes. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the manifold being Hadamard and on controlled inexactness of the retraction and transport operations; these are standard domain assumptions rather than new free parameters or invented entities.

axioms (2)
  • domain assumption The manifold is Hadamard, enabling global geodesic convexity for the objective.
    Stated directly in the abstract as the natural setting for globally geodesically convex problems.
  • domain assumption Inexact manifold primitives (retractions and vector transports) satisfy bounded-error conditions sufficient for the bundle analysis.
    Required for the oracle-complexity bounds to hold with approximate operations.

pith-pipeline@v0.9.0 · 5410 in / 1403 out tokens · 29161 ms · 2026-05-07T08:54:42.688870+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Absil and J

    P.-A. Absil and J. Malick,Projection-like retractions on matrix manifolds, SIAM Journal on Optimization, 22 (2012), pp. 135–158

    work page 2012

  2. [2]

    Alimisis, A

    F. Alimisis, A. Orvieto, G. B´ecigneul, and A. Lucchi,Momentum improves optimization on Riemannian manifolds, in Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 130, PMLR, 2021, pp. 1351–1359

    work page 2021

  3. [3]

    Arnaudon, F

    M. Arnaudon, F. Barbaresco, and L. Yang,Riemannian medians and means with applications to radar signal processing, IEEE Journal of Selected Topics in Signal Processing, 7 (2013), pp. 595–604

    work page 2013

  4. [4]

    Baˇc´ak,Computing medians and means in hadamard spaces, SIAM Journal on Optimization, 24 (2014), pp

    M. Baˇc´ak,Computing medians and means in hadamard spaces, SIAM Journal on Optimization, 24 (2014), pp. 1542–1566

    work page 2014

  5. [5]

    G. C. Bento, O. P. Ferreira, and J. G. Melo,Iteration-complexity of gradient, subgradient and proximal point methods on riemannian manifolds, Journal of Optimization Theory and Applications, 173 (2017), pp. 548–562

    work page 2017

  6. [6]

    The riemannian convex bundle method.arXiv preprint arXiv:2402.13670, 2024

    R. Bergmann, R. Herzog, and H. Jasa,The riemannian convex bundle method, 2025. arXiv preprint: 2402.13670

    work page arXiv 2025

  7. [7]

    Boumal,An introduction to optimization on smooth manifolds, Cambridge University Press, 2023

    N. Boumal,An introduction to optimization on smooth manifolds, Cambridge University Press, 2023

    work page 2023

  8. [8]

    Boumal, P.-A

    N. Boumal, P.-A. Absil, and C. Cartis,Global rates of convergence for nonconvex optimization on manifolds, IMA Journal of Numerical Analysis, 39 (2019), pp. 1–33

    work page 2019

  9. [9]

    Boumal, B

    N. Boumal, B. Mishra, P.-A. Absil, and R. Sepulchre,Manopt, a Matlab toolbox for optimization on manifolds, Journal of Machine Learning Research, 15 (2014), pp. 1455–1459

    work page 2014

  10. [10]

    S. Chen, S. Ma, A. Man-Cho So, and T. Zhang,Proximal gradient method for nonsmooth optimization over the stiefel manifold, SIAM Journal on Optimization, 30 (2020), pp. 210–239

    work page 2020

  11. [11]

    K. Deng, J. Jin, J. Hu, and H. Wang,Adaptive riemannian ADMM for nonsmooth optimization: Optimal complexity without smoothing, in The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025

    work page 2025

  12. [12]

    D´ıaz and B

    M. D´ıaz and B. Grimmer,Optimal convergence rates for the proximal bundle method, SIAM Journal on Optimization, 33 (2023), pp. 424–454

    work page 2023

  13. [13]

    Du and A

    Y. Du and A. Ruszczy´nski,Rate of convergence of the bundle method, Journal of Optimization Theory and Applications, 173 (2017), pp. 908–922

    work page 2017

  14. [14]

    O. P. Ferreira, D. S. Gon c ¸alves, M. S. Louzeiro, S. Z. N ´emeth, and J. Zhu,A subdifferential characterization via busemann functions and applications to dc optimization on hadamard manifolds, 2026. 22

    work page 2026

  15. [15]

    O. P. Ferreira and P. R. Oliveira,Subgradient algorithm on riemannian manifolds, Journal of Optimization Theory and Applications, 97 (1998), pp. 93–104

    work page 1998

  16. [16]

    ,Proximal point algorithm on riemannian manifolds, Optimization, 51 (2002), pp. 257–270

    work page 2002

  17. [17]

    Goodwin, A

    A. Goodwin, A. S. Lewis, G. L ´opez-Acedo, and A. Nicolae,A subgradient splitting algorithm for optimization on nonpositively curved metric spaces, 2024

    work page 2024

  18. [18]

    Goodwin, A

    A. Goodwin, A. S. Lewis, G. L ´opez-Acedo, and A. Nicolae,Stochastic and incremental subgradient methods for convex optimization on hadamard spaces, Mathematical Programming, (2026)

    work page 2026

  19. [19]

    Hoseini Monjezi, S

    N. Hoseini Monjezi, S. Nobakhtian, and M. R. Pouryayevali,A proximal bundle algorithm for nonsmooth optimization on riemannian manifolds, IMA Journal of Numerical Analysis, 43 (2023), pp. 293–325

    work page 2023

  20. [20]

    Huang and K

    W. Huang and K. Wei,Riemannian proximal gradient methods, Mathematical Programming, 194 (2022), pp. 371–413

    work page 2022

  21. [21]

    Jeuris, R

    B. Jeuris, R. Vandebril, and B. Vandereycken,A survey and comparison of contemporary algorithms for computing the matrix geometric mean, Electronic Transactions on Numerical Analysis, 39 (2012), pp. 379–402

    work page 2012

  22. [22]

    K. C. Kiwiel,Efficiency of proximal bundle methods, Journal of Optimization Theory and Applications, 104 (2000), pp. 589–603. [23]J. M. Lee,Introduction to Riemannian Manifolds, Springer, 2nd ed., 2018

    work page 2000

  23. [23]

    Lemar´echal,An extension of davidon methods to nondifferentiable functions, in Mathe- matical Programming Study, vol

    C. Lemar´echal,An extension of davidon methods to nondifferentiable functions, in Mathe- matical Programming Study, vol. 3, Springer, 1975, pp. 95–109

    work page 1975

  24. [24]

    A. S. Lewis, G. Lopez-Acedo, and A. Nicolae,Horoballs and the subgradient method, 2024

    work page 2024

  25. [25]

    J. Li, K. Balasubramanian, and S. Ma,Zeroth-order riemannian averaging stochastic approximation algorithms, SIAM Journal on Optimization, 34 (2024), pp. 3314–3341

    work page 2024

  26. [26]

    Liang and R

    J. Liang and R. D. C. Monteiro,A proximal bundle variant with optimal iteration- complexity for a large range of prox stepsizes, SIAM Journal on Optimization, 31 (2021), pp. 2955–2986

    work page 2021

  27. [27]

    Mifflin,An algorithm for constrained optimization with semismooth functions, Mathematics of Operations Research, 2 (1977), pp

    R. Mifflin,An algorithm for constrained optimization with semismooth functions, Mathematics of Operations Research, 2 (1977), pp. 191–207

    work page 1977

  28. [28]

    R. D. Mill ´an, O. P. Ferreira, M. S. Louzeiro, and J. Ugon,A busemann hybrid projection-proximal point algorithm for optimization problems on hadamard manifolds, 2026

    work page 2026

  29. [29]

    Nickel and D

    M. Nickel and D. Kiela,Poincar´ e embeddings for learning hierarchical representations, Advances in neural information processing systems, 30 (2017)

    work page 2017

  30. [30]

    Orban and G

    D. Orban and G. Leconte,RipQP.jl: Regularized interior point solver for quadratic problems, Dec. 2020. 23

    work page 2020

  31. [31]

    Pennec, P

    X. Pennec, P. Fillard, and N. Ayache,A riemannian framework for tensor computing, International Journal of Computer Vision, 66 (2006), pp. 41–66

    work page 2006

  32. [32]

    Pischke,On busemann subgradient methods for stochastic minimization in hadamard spaces, 2026

    N. Pischke,On busemann subgradient methods for stochastic minimization in hadamard spaces, 2026

    work page 2026

  33. [33]

    A. P. Ruszczy ´nski,Nonlinear Optimization, Princeton University Press, Princeton, N.J., 2006

    work page 2006

  34. [34]

    Sahinoglu, Y

    E. Sahinoglu, Y. Sun, and S. Shahrampour,Finite-time analysis of stochastic nonconvex nonsmooth optimization on the riemannian manifolds, in The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [36]L. W. Tu,An introduction to manifolds, Springer, New York, 2nd ed. ed., 2011

    work page 2025

  35. [35]

    Wiesel,Geodesic convexity and covariance estimation, IEEE Transactions on Signal Processing, 60 (2012), pp

    A. Wiesel,Geodesic convexity and covariance estimation, IEEE Transactions on Signal Processing, 60 (2012), pp. 6182–6189

    work page 2012

  36. [36]

    Wolfe,A method of conjugate subgradients for minimizing nondifferentiable functions, in Springer Berlin Heidelberg, Springer, Berlin, Heidelberg, 1975, pp

    P. Wolfe,A method of conjugate subgradients for minimizing nondifferentiable functions, in Springer Berlin Heidelberg, Springer, Berlin, Heidelberg, 1975, pp. 145–173

    work page 1975

  37. [37]

    Zhang and S

    H. Zhang and S. Sra,First-order methods for geodesically convex optimization, in Proceedings of the 29th Annual Conference on Learning Theory (COLT), vol. 49, PMLR, 2016, pp. 1617– 1638. A Proof of Lemma 3.1 The following lemma bounds the error arising from sectional curvature when using parallel transport. Lemma A.1.Suppose M is Hadamard with sectional c...

    work page 2016