Pith. sign in

REVIEW 3 major objections 3 minor 8 references

The Intrinsic Riemannian Proximal Gradient Method for Convex Optimization

T0 review · 3 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read An intrinsic proximal gradient step on curved spaces converges at O(1/k), and linearly for strongly convex costs.

desk verdict Genuinely new intrinsic proximal-gradient method, but both headline rate theorems are stated without hypotheses their proofs actually need; a serious revision could fix it. read the letter →

arxiv 2507.16055 v2 pith:QKBP3ND2 submitted 2025-07-21 math.OC cs.NAmath.DGmath.NA

Ronny Bergmann , Hajg Jasa , Paula John , Max Pfeffer This is my paper
classification math.OCcs.NAmath.DGmath.NA MSC 90C2549Q9949M3065K10
keywords proximalgradientmethodRiemannianoptimizationHadamardmanifoldsgeodesicconvexitystrongmapsplittingmethodsconvergencerate
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

The paper introduces a proximal gradient method that works directly on a Riemannian manifold, for problems whose objective splits into a smooth part $g$ and a possibly nonsmooth part $h$. On Hadamard manifolds (complete, simply connected spaces of nonpositive curvature), it claims a sublinear $O(1/k)$ rate in function values for geodesically convex objectives (Theorem 4.4), an $O(1/\varepsilon)$ iteration bound for reaching $\varepsilon$-stationary points (Theorem 4.5), and a linear rate when $f=g+h$ is strongly geodesically convex (Theorem 4.7). The construction's point is that the nonsmooth proximal step is taken by the manifold's own proximal map rather than by a Euclidean proxy in a tangent space or an embedding. If the rates hold, an intrinsic splitting method matches the guarantees of the Euclidean proximal gradient method.

What carries the argument

The central object is the intrinsic proximal map $\mathrm{prox}_{\lambda h}(\cdot) = \arg\min_{q\in\mathcal{M}} h(q) + \frac{1}{2\lambda}d^2(\cdot,q)$, applied after a gradient step $z(p)=\exp_p(-\lambda\,\mathrm{grad}\,g(p))$. The iteration $p^{k+1}=\mathrm{prox}_{\lambda(k)h}(z(p(k)))$ keeps both steps on the manifold, avoiding tangent-space or embedding formulations. The convergence analysis is carried by Riemannian cosine inequalities with curvature-dependent constant $\zeta_{1,\kappa_l}$, which replace the Euclidean law of cosines, together with the sufficient decrease condition coming from $L_g$-smoothness of $g$ and the proximal characterization $\frac{1}{\lambda}\log_{T_\lambda(q)} z(q)\in\partial h(T_\lambda(q))$.

What would settle it

Check the derivation of inequality (16) on a nonconvex perturbation: on $\mathbb{H}^2$ take $h$ as the indicator of a geodesic ball and $g(p)=-c\,d(p,q)^2$ so that $f$ is strongly convex for small $c$ while $g$ is not geodesically convex; if the claimed linear bound (25) still holds for Algorithm 1, the missing Assumption 4.3 is a repairable gap, and if the rate deteriorates or fails, Theorem 4.7 as stated is not supported.

Watch

Extended reading notes

Core claim

The central claim is that Algorithm 1, whose update is $p^{k+1} = \mathrm{prox}_{\lambda(k) h}(\exp_{p(k)}(-\lambda(k)\,\mathrm{grad}\, g(p(k))))$, converges in function values at rate $O(1/k)$ when $g$ is geodesically convex, and linearly when $f$ is $\mu_f$-strongly geodesically convex. The proof separates into two regimes governed by the ratio $\lambda(k)\Delta(k)/(\zeta_{1,\kappa_l}(D(k))\,d^2(p(k),p^*))$: when the ratio is at least one the function error halves each step, and otherwise a $1/k$ shrinkage follows. The same machinery yields an $O(1/\varepsilon)$ complexity for $\varepsilon$-stationarity. The paper also derives Riemannian analogues of the fundamental prox-grad inequality of the Euclidean theory and shows that, unlike in Euclidean space, these inequalities alone do not yield Fejér monotonicity or a convergence rate for the composite method.

Load-bearing premise

The load-bearing premise is that the smooth part $g$ is geodesically convex and that the initial sublevel set has finite diameter and contains a minimizer; in the proof of Theorem 4.7 the convexity of $g$ is inherited from inequality (16), which was proved in Theorem 4.4 under Assumption 4.3, but Assumption 4.3 is not restated among the theorem's hypotheses.

Editorial extensions

If this is right

  • For convex $f$, reaching $\varepsilon$-accuracy in function value costs at most $O(\max\{\log(\Delta(0)/\varepsilon), 1/(\varepsilon\delta)\})$ iterations, where $\delta$ is the explicit shrinkage constant of Theorem 4.4.
  • For strongly convex $f$, the function values and iterates converge linearly to the unique minimizer, with complexity $\frac{4L_g\zeta_{1,\kappa_l}(R_\alpha)}{\beta\mu_f}\log(\Delta(0)/\varepsilon)$ up to a factor of two.
  • The prox-grad inequalities reproduce the known rate for the Riemannian proximal point method when $g=0$ and a comparable Hadamard gradient descent rate when $h=0$.
  • Because the nonsmooth step uses the manifold proximal map, the method applies to Hadamard manifolds such as $\mathbb{P}(n)$ and $\mathbb{H}^n$ without embedding assumptions; the experiments on these spaces show convergence times comparing favorably with CPPA and a projected gradient method.
  • The new inequalities generalize Beck's fundamental prox-grad inequality to uniquely geodesic manifolds with upper curvature bound, but the paper shows they are insufficient on their own to prove Fejér monotonicity or a rate for Algorithm 1.

Reading between the lines

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

  • The two-regime character of Theorem 4.4 suggests an accelerated variant might be built by alternating halving steps with slow shrinkage steps; the paper does not propose such an acceleration, but its proof structure is compatible with an epoch-based analysis.
  • The curvature constant $\zeta_{1,\kappa_l}(R_\alpha)$ grows with the diameter of the initial sublevel set, so a testable prediction is that the observed linear-rate constant degrades as data spread increases on a fixed hyperbolic space; plotting iteration counts against $R_\alpha$ would check this.
  • The fixed-point formula for the $\ell^1$-prox on $\mathbb{H}^n$ (Theorems 6.1 and 6.2) is self-contained; it can be plugged into other manifold first-order methods whose only manifold-specific ingredient is a prox.
  • An interesting open direction is whether the $O(1/\varepsilon)$ stationarity complexity remains valid under the weaker assumption that only $f$, not $g$, is geodesically convex, since the proofs currently use convexity of $g$ in inequality (16).
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper introduces an intrinsic Riemannian proximal gradient method (CRPG) on Hadamard manifolds for minimizing f = g + h, where g is L-smooth and h is convex and possibly nonsmooth, using the manifold proximal map for the nonsmooth step. The main theoretical contributions are an O(1/k) sublinear convergence rate in function values for geodesically convex objectives (Theorem 4.4), an O(1/ε) iteration complexity for reaching ε-stationary points (Theorem 4.5), and a linear convergence rate for strongly geodesically convex objectives (Theorem 4.7). The paper also derives Riemannian generalizations of the Euclidean prox-grad inequalities and reports numerical experiments on SPD matrices and hyperbolic spaces, comparing constant and backtracking step sizes against existing algorithms.

Significance. If the main results are correct, the paper offers a genuinely intrinsic Riemannian proximal gradient method and a useful generalization of the fundamental prox-grad inequality, with rates that account for curvature through the quantity ζ1,κl. The numerical experiments are well chosen and support the practical value of the method. However, the theoretical core currently has several load-bearing hypothesis gaps: Theorem 4.7 inherits an inequality proved under an assumption it does not state, and the main rates depend on finiteness and existence conditions that are not part of the standing assumptions. These issues are fixable within the scope of the manuscript, so the paper does not warrant outright rejection, but it needs a substantial revision.

major comments (3)
  1. [§4.2, Theorem 4.7] The proof of Theorem 4.7 begins by invoking inequality (16), which is established in the proof of Theorem 4.4 under Assumption 4.3(i), i.e., g geodesically convex. Theorem 4.7 is stated only under Assumptions 4.1 and 4.6, and µf-strong convexity of f does not imply convexity of g. The derivation of (16) uses the convexity of g in an essential way, when g(p(n)) is replaced by g(p) − (grad g(p(n)), log_{p(n)} p); this step has no counterpart under the stated assumptions. The linear rate (25) is therefore unsupported as written. The theorem should either explicitly add the assumption that g is geodesically convex, or the proof should supply a direct derivation of (16) that does not rely on convexity of g.
  2. [§4, Lemma 3 and Theorem 4.4] Lemma 3 requires the existence of q* ∈ arg min_M g and a finite diameter of the sublevel set L_{p(0)}, but neither condition is stated in Assumptions 4.1 or 4.3; Assumption 4.1(v) only guarantees that the minimizer set of f is nonempty. Moreover, the set L_{p(0)} is never defined in the paper. The quantities R := diam(L_{p(0)}) and Rα appear in the central rates (13), (14), (22), and (25), so if L_{p(0)} is unbounded or g has no minimizer, the rates become vacuous or the bound (11) is undefined. These are load-bearing hypotheses and should be stated explicitly, with L_{p(0)} properly defined.
  3. [§4.1, Theorem 4.5] The proof of the ε-stationarity complexity invokes Lemma 4.8 of the authors' prior nonconvex paper (Bergmann, Jasa, John, Pfeffer, 2025) without stating the lemma or its hypotheses. The paper itself notes that the step-size conditions in that lemma differ from those used here and asserts that the result remains valid because sufficient decrease is already guaranteed by Lemma 1; this assertion is not demonstrated. Since this lemma is the bridge from the decrease bound (24) to the subgradient-norm bound, the complexity claim in (22) is not self-contained. The lemma should be stated and its conditions verified under Assumptions 4.1 and 4.3.
minor comments (3)
  1. [Assumption 4.1(i)] A Hadamard manifold is a complete, simply connected manifold with nonpositive sectional curvature, not nonnegative as written. This appears to be a typo but should be corrected because the subsequent analysis and the experiments rely on nonpositive curvature.
  2. [§4.1, before Lemma 3] Please define L_{p(0)} explicitly as the sublevel set (e.g., {p ∈ M : f(p) ≤ f(p(0))}) and state the boundedness condition needed for the diameter R = diam(L_{p(0)}) to be finite.
  3. [Theorem 4.5] The statement uses a bound g+ ≥ ∥grad g(p)∥ for all p ∈ L_{p(0)}; this should be listed as an explicit assumption, since L_{p(0)} is not known to be compact under the standing assumptions.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the convergence rates are derived from first principles plus external geometric inequalities; the minor self-citations are auxiliary, and the Theorem 4.7 hypothesis gap is a correctness issue, not a circular reduction.

full rationale

The paper's central claims, Theorem 4.4 (sublinear O(1/k) convergence for geodesically convex objectives), Theorem 4.7 (linear convergence for strongly geodesically convex objectives), and Theorem 4.5 (O(1/ε) complexity for ε-stationarity), are proven by direct derivation rather than by importing the target rates as assumptions. The sufficient-decrease Lemma 1 is proved from Lg-smoothness of g, convexity of h, the proximal subgradient condition, and the Riemannian cosine law of Martínez-Rubio–Pokutta. The distance bound in Lemma 3 follows from g-smoothness and the triangle inequality. The θ-interpolation step leading to Eq. (16) is adapted from an external result (Roux, Martínez-Rubio, Pokutta 2025) and is not an input to the method. None of these ingredients is the paper's own convergence rate, and the rates are not used to define Algorithm 1 or its stepsize rules. Self-citations to the authors' nonconvex companion paper (Bergmann, Jasa, John, Pfeffer 2025) appear when Lemma 1 is said to improve that paper's Lemma 4.4, and when Theorem 4.5 uses that paper's Lemma 4.8 to bound the subgradient norm in terms of consecutive iterate distance. These are auxiliary technical lemmas, not the paper's central claims, and Theorem 4.5 explicitly notes that the nonconvex stepsize conditions in Lemma 4.8 are replaced by the paper's own Lemma 1. This is ordinary reuse rather than load-bearing circularity. The one flagged weakness is not circularity but a stated-hypothesis gap: Theorem 4.7 is stated under Assumption 4.1 and Assumption 4.6 only, yet its proof begins by citing Eq. (16), which was derived in the proof of Theorem 4.4 under Assumption 4.3 (g geodesically convex). The gap is repairable because Assumption 4.6, strong convexity of f, implies f is geodesically convex, which is the property actually used to derive Eq. (16); however, the proof as written does not state this, and Lemma 3 additionally requires existence of a minimizer of g and finite diameter of the initial sublevel set, neither of which appears in Assumption 4.1. These are missing hypotheses that affect correctness of the written proof, not reductions of the conclusion to the assumptions. The numerical experiments are benchmarked against CPPA and PGA and are not used as proof of the rates. Overall, the derivation chain is self-contained modulo standard external geometric inequalities, so the circularity score is low.

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

No new entities are introduced. The core assumptions are standard Riemannian convexity and smoothness, but two internal assumptions (minimizer existence/bounded sublevel set, and g convexity in the strongly convex theorem) are not stated in the standing assumptions and are needed for the proofs.

assumptions (8)
  • domain assumption M is a Hadamard manifold, i.e. complete, simply connected, nonpositive sectional curvature
    Assumption 4.1(i), though the text says 'nonnegative' which is a typo. All rates require nonpositive curvature via the cosine inequalities.
  • domain assumption Sectional curvature of M is bounded below by κ_l
    Assumption 4.1(ii); the factor ζ_{1,κ_l} appears in every rate and complexity bound.
  • domain assumption g is L_g-smooth over int dom(g) and h is proper, closed, geodesically convex
    Assumption 4.1(iii)-(iv); needed for the sufficient decrease and for the proximal map stationarity.
  • standard math Riemannian cosine inequalities of Martínez-Rubio-Pokutta 2023, Corollary 15 and Remark 16
    Used in Lemma 1 and throughout Theorem 4.4; cited, not proved.
  • standard math Lemma 4.8 of Bergmann-Jasa-John-Pfeffer 2025
    Used in Theorem 4.5 to bound subgradients; cited from authors' prior nonconvex work, not proved here.
  • ad hoc to paper q* ∈ arg min_M g exists and L_{p(0)} has finite diameter
    Assumed implicitly in Lemma 3 for bounding d(p(k), z(p(k))); not part of Assumption 4.1 or 4.3; without it, R and R_α are infinite.
  • ad hoc to paper g is geodesically convex
    Needed in the proof of Theorem 4.7 through equation (16), but Theorem 4.7 states only Assumption 4.6 (f strong convexity), not Assumption 4.3.
  • domain assumption f is µ_f-strongly geodesically convex
    Assumption 4.6; used to convert distance terms into function-value gaps.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Intrinsic Riemannian Proximal Gradient Method for Convex Optimization." pith.science (2026). https://pith.science/paper/QKBP3ND2

@misc{pith2026250716055,
  author       = {Pith},
  title        = {Pith review of: The Intrinsic Riemannian Proximal Gradient Method for Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QKBP3ND2}},
  note         = {Machine review of arXiv:2507.16055}
}
read the original abstract

We consider a class of (possibly strongly) geodesically convex optimization problems on Hadamard manifolds, where the objective function splits into the sum of a smooth and a possibly nonsmooth function. We introduce an intrinsic convex Riemannian proximal gradient (CRPG) method that employs the manifold proximal map for the nonsmooth step, without operating in the embedding or tangent space. A sublinear convergence rate for convex problems and a linear convergence rate for strongly convex problems is established, and we derive fundamental proximal gradient inequalities that generalize the Euclidean case. Our numerical experiments on hyperbolic spaces and manifolds of symmetric positive definite matrices demonstrate substantial computational advantages over existing methods.

Figures

Figures reproduced from arXiv: 2507.16055 by the authors.

Figure 1
Figure 1. Error of the cost function f(p (k) ) − fopt on P(2) for CRPG with a constant and backtracked stepsizes. Example from Section 6.1. Discussion. The results of the numerical experiment are shown in [PITH_FULL_IMAGE:figures/full_fig_p018_1.png] view at source ↗
Figure 2
Figure 2. Comparison of CRPG with PGA for the constrained mean problem on Hn from Section 6.3. seen from the plots, CRPG with constant stepsize converges faster in time than the PGA except for one case. The PGA in turn converges faster than CRPG with backtracking except a handful of cases. The number of iterations is similar for CRPG in both variants, with the CRPG with constant stepsize requiring slightly fewer iterations th… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

8 extracted references · 5 canonical work pages

  1. [1]

    Manifolds.Jl: An Exten- sible Julia Framework for Data Analysis on Manifolds

    Axen, S. D.; M. Baran; R. Bergmann; K. Rzecki (2023). “Manifolds.Jl: An Exten- sible Julia Framework for Data Analysis on Manifolds”. ACM Transactions on Mathematical Software 49.4. doi: 10.1145/3618296. Baˇ c´ ak, M. (2014a). “Computing medians and means in Hadamard spaces”.SIAM Journal on Optimization 24.3, pp. 1542–1566. doi: 10.1137/140953393. 24 REFE...

    doi:10.1145/3618296 2023

  2. [22]

    A fast iterative shrinkage-thresholding algorithm for linear inverse problems

    De Gruyter Series in Nonlinear Analysis and Applications. De Gruyter, Berlin. doi: 10.1515/9783110361629. Beck, A. (2017). First-Order Methods in Optimization . Philadelphia, PA: Society for Industrial and Applied Mathematics. doi: 10.1137/1.9781611974997. Beck, A.; M. Teboulle (2009). “A fast iterative shrinkage-thresholding algorithm for linear inverse ...

    arXiv 2017

  3. [49]

    First-order Methods for Geodesically Convex Optimization

    Proceedings of Machine Learning 26 REFERENCES Research, pp. 1617–1638. arXiv: 1602.06053. url: https: / /proceedings.mlr. press/v49/zhang16b.html. (R. Bergmann) Norwegian University of Science and Technology, Department of Mathematical Sciences, NO-7041 Trondheim, Norway Email address : ronny.bergmannn@ntnu.no URL: https://www.ntnu.edu/employees/ronny.ber...

    work page Pith review arXiv

  4. [195]

    Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point

    Proceedings of Machine Learning Research. PMLR, pp. 359–393. url: https: / /proceedings.mlr.press/v195/martinez-rubio23a.html. Mart ´ ınez-Rubio, D.; C. Roux; S. Pokutta (2024). “Convergence and Trade-Offs in Riemannian Gradient Descent and Riemannian Proximal Point”. Proceedings of the 41st International Conference on Machine Learning . Ed. by R. Salakhu...

    work page 2024

  5. [235]

    Implicit Riemannian Optimism with Applications to Min-Max Problems

    Proceedings of Machine Learning Research. PMLR, pp. 34920–34948. url: https: / /proceedings.mlr.press/v235/marti-nez-rubio24a.html. Roux, C.; D. Mart ´ ınez-Rubio; S. Pokutta (2025).Implicit Riemannian Optimism with Applications to Min-Max Problems . arXiv: 2501.18381. Schiela, A.; R. Herzog; R. Bergmann (2024). Nonlinear Fenchel conjugates. arXiv: 2409.0...

    work page Pith review arXiv 2025

  6. [297]

    On some basic results related to affine functions on Riemannian manifolds

    Mathematics and its Applications. Kluwer Academic Pub- lishers Group, Dordrecht. doi: 10.1007/978-94-015-8390-9 . Wang, X.; C. Li; J.-C. Yao (2016). “On some basic results related to affine functions on Riemannian manifolds”. Journal of Optimization Theory and Applications 170.3, pp. 783–803. doi: 10.1007/s10957-016-0979-x. Weinmann, A.; L. Demaret; M. St...

    doi:10.1007/978-94-015-8390-9 2016

  7. [319]

    An accelerated first-order method for non-convex optimization on manifolds

    Grundlehren der Mathematischen Wissenschaften [Fundamental Prin- ciples of Mathematical Sciences]. Springer, Berlin. doi: 10.1007/978- 3- 662- 12494-9. Chambolle, A.; T. Pock (2011). “A first-order primal-dual algorithm for convex problems with applications to imaging”. Journal of Mathematical Imaging and Vision 40.1, pp. 120–145. doi: 10.1007/s10851-010-...

    work page Pith review arXiv 2011

  8. [3866]

    Fenchel Duality Theory and A Primal-Dual Algorithm on Riemannian Manifolds

    doi: 10.21105/joss.03866. Bergmann, R.; O. P. Ferreira; S. N´ emeth; J. Zhu (2025). On projection mappings and the gradient projection method on hyperbolic space forms . arXiv: 2504 . 11815. Bergmann, R.; R. Herzog; M. Silva Louzeiro; D. Tenbrinck; J. Vidal-N´ u˜ nez (2021). “Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds”. Fou...

    work page Pith review arXiv 2025

Pith tools

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