- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The authors study weakly convex optimization on a compact embbedded manifold assuming an unbiased subgradient oracle with a finite -moment. They prove high probability convergence the unclipped Riemannian stochastic subgradient descent (RSSG) as well as two variants: GeoClip and GeoNorm RSSG. They provide iterations and oracle complexity bounds recovering the classical result when .
Critical strengths
The high probability guarantee for the unclipped RSSG under finite -th moment is a nice contribution. The idea of controlling the proximal value increment in the high probability theorem was intersting. The experimental part is quite substantial.
Critical weaknesses
My main concerns is about the novelty of the analysis: besides the idea of controlliong the proximal value increments the proof techniques seem pretty standard to me. In particular equation (4) seems to follow directly from the local retraction estimates and the compactness. The high probability argument using Freedman's inequality is also pretty standard I think. I would be greatfull if the authors could give a clearer explanation of the main mathematical difficulty.
Questions for authors
- What distinguishes the proof from existing analysis, what is the main technical novelty of the paper ?
- Equation (4) seems to hold in a generic case, as long as the domain is compact. Would it be possible to extend the proof techniques to projected stochastic subgadient descent on a compact convex domain?
- I wonder if we can prove almost sure convergence for RSSG? I wonder if we could combine a borel cantelli argument with VIlle's maximal inequality.
2 comments
I thank the authors for the clarifications and their detailled answers. I will however keep my score as I think that the contribution is slightly below the standard of the conference
Thank you for recognizing the high-probability guarantee and proximal-value argument.
1. Technical novelty and Equation (4)
Equation (4) follows from local retraction estimates and compactness; Freedman's inequality is established. Our contribution is joint control of proximal descent and proximal-value variance, giving high-probability convergence of unclipped RSSG despite infinite oracle variance.
Two uses of geometry. For every tangent-step magnitude, Equation (4) gives
\leq2\langle\xi,x-y\rangle+C\|\xi\|^p.$$ The signed linear term preserves conditional unbiasedness in proximal descent. Setting $y=x$ bounds squared displacement by $C\|\xi\|^p$, without requiring nonexpansiveness.A variance-controlled martingale. The raw noise inner product may have infinite variance; the random p-order remainder is only integrable. We first take conditional expectations in the descent bound, then center the actual proximal value, with Φ=Φρˉ:
\mathbb E_t Z_t^2\leq L_\Phi^2\mathbb E_t\|x_{t+1}-x_t\|^2\leq K\eta^p.$$ Writing $\Theta_t=\Theta_{\bar\rho}(x_t)$, this gives the pathwise bound $$c\eta\sum_{t=1}^T\Theta_t^2 \leq\Phi(x_1)-\Phi(x_{T+1})+KT\eta^p+\sum_{t=1}^T Z_t,$$ for constants $c>0,K\geq0$ independent of $T,\eta$. Thus **concentrating the proximal-value increments controls the original stationarity statistic**. Compactness bounds the increments, while geometry supplies their stepsize-dependent variance.Why the variance order matters. At η≍T−1/p, range-only concentration contributes 1/(ηT)≍T1/p−1/2, which does not vanish for 1<p≤2. Our variance bound gives Tηp/(ηT)≍T−(p−1)/p. Freedman's bounded-increment term is O(log(1/δ)/(ηT)), yielding the same rate with logarithmic confidence factors.
Li et al. (2021) analyze second-moment manifold noise. Zhu et al. (2026, ICML, Theorem 4.2) give a finite-moment expectation guarantee for unclipped projected SGD on compact convex sets; their high-probability results require sub-Weibull noise for unclipped SGD or clipping under finite moments. Our result provides finite-moment high-probability guarantees without clipping under the stated manifold assumptions. Section 5.2 and Lemmas 5.1/F.3 detail the argument.
2. Extension to compact convex domains
Yes. Corollary O.2 proves the corresponding high-probability guarantee for unclipped projected subgradients.
Setting. Let C be nonempty, compact and convex, with diameter D>0. Use xt+1=ΠC(xt−ηgt) from fixed x1∈C. Assume f:Rd→R is lower semicontinuous and ρ-weakly convex, its subgradients on C are bounded by G, and gt is conditionally unbiased with central p-th moment at most σp, 1<p≤2.
Geometric input. Nonexpansiveness and bounded diameter supply the signed distance comparison and ∥xt+1−xt∥≤min{η∥gt∥,D}. For ρˉ>ρ, the constrained proximal value is ρˉD-Lipschitz, giving EtZt2≤ρˉ2D4−pηp(G+σ)p. Thus projection supplies the geometric input, and proximal-value concentration carries over.
Rate. With η=η0T−1/p, η0>0, probability at least 1−δ gives
\leq KT^{-(p-1)/p}(1+\sqrt\ell+\ell),\qquad\ell=\log(1/\delta).$$ Here $\Theta_{\bar\rho,C}$ is the constrained proximal residual; $K$ depends on problem parameters and $\eta_0$, not $T,\delta$. Appendix O.2 (pp. 37–38) gives constants and proof.3. Almost-sure convergence
Your Borel-Cantelli/Ville suggestion leads to an infinite-horizon result: Corollary O.3 uses a direct supermartingale proof.
Schedule. Under the RSSG theorem's assumptions, choose deterministic ηt>0 with ∑tηt=∞ and ∑tηtp<∞, e.g. ηt=η0t−a for 1/p<a≤1.
Proof. The bound EtΦ(xt+1)≤Φ(xt)−cηtΘt2+Kηtp makes
\qquad f_\star=\min_{x\in\mathcal M}f(x),$$ an integrable nonnegative supermartingale. Its convergence and the vanishing tail imply finite convergence of $\Phi(x_t)$. Telescoping expectations gives $c\,\mathbb E\sum_t\eta_t\Theta_t^2\leq\mathbb E Y_1<\infty$.Stationarity. Consequently, almost surely,
\frac{\sum_{t=1}^T\eta_t\Theta_t^2}{\sum_{t=1}^T\eta_t}\to0, \qquad\liminf_{t\to\infty}\Theta_t=0.$$ These give weighted-average and subsequential stationarity along one RSSG run. Appendix O.3 (pp. 38–39) gives the full proof.