acceptodds
Under review as a conference paper at ICLR 2027

Weakly Convex Optimization on Manifolds with Heavy-Tailed Oracles

Abstract

Weakly convex optimization on manifolds underlies nonsmooth learning problems with orthogonality constraints. Existing Riemannian stochastic subgradient guarantees rely on bounded second moments; we study unbiased oracles with only a finite -th central moment, . Our main result is high-probability convergence of Riemannian stochastic subgradient descent (RSSG) on compact embedded manifolds with globally defined smooth retractions. Heavy-tailed steps can leave the region where local retraction bounds apply. We overcome this mismatch by controlling the iterates' actual movement on the compact manifold, without clipping or assuming finite oracle variance. Its oracle complexity is , recovering the classical order at . Two complementary variants bound every tangent step. GeoClip-RSSG couples clipping and stepsize selection to attain the same oracle exponent within a prescribed retraction neighborhood. GeoNorm-RSSG normalizes mini-batch subgradients, attaining the same iteration-rate order with parameter choices independent of , at an additional sample cost. Experiments support the predicted convergence trends and demonstrate the methods' value for subspace recovery from heavy-tailed data.

Primary area:
optimization
Keywords:
Riemannian optimization, Weakly convex optimization, Heavy-tailed noise, Stochastic subgradient methods, High-probability convergence.

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_9Wd9OpenReview ↗
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 pp-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 p=2p=2.

Critical strengths

The high probability guarantee for the unclipped RSSG under finite pp-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
  1. What distinguishes the proof from existing analysis, what is the main technical novelty of the paper ?
  2. 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?
  3. 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

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.

  1. 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.
  2. A variance-controlled martingale. The raw noise inner product may have infinite variance; the random pp-order remainder is only integrable. We first take conditional expectations in the descent bound, then center the actual proximal value, with Φ=Φρˉ\Phi=\Phi_{\bar\rho}:

    \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.
  3. Why the variance order matters. At η≍T−1/p\eta\asymp T^{-1/p}, range-only concentration contributes 1/(ηT)≍T1/p−1/21/(\eta\sqrt T)\asymp T^{1/p-1/2}, which does not vanish for 1<p≤21<p\leq2. Our variance bound gives Tηp/(ηT)≍T−(p−1)/p\sqrt{T\eta^p}/(\eta T)\asymp T^{-(p-1)/p}. Freedman's bounded-increment term is O(log⁡(1/δ)/(ηT))O(\log(1/\delta)/(\eta 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.

  1. Setting. Let CC be nonempty, compact and convex, with diameter D>0D>0. Use xt+1=ΠC(xt−ηgt)x_{t+1}=\Pi_C(x_t-\eta g_t) from fixed x1∈Cx_1\in C. Assume f:Rd→Rf:\mathbb R^d\to\mathbb R is lower semicontinuous and ρ\rho-weakly convex, its subgradients on CC are bounded by GG, and gtg_t is conditionally unbiased with central pp-th moment at most σp\sigma^p, 1<p≤21<p\leq2.

  2. Geometric input. Nonexpansiveness and bounded diameter supply the signed distance comparison and ∥xt+1−xt∥≤min⁡{η∥gt∥,D}\|x_{t+1}-x_t\|\leq\min\{\eta\|g_t\|,D\}. For ρˉ>ρ\bar\rho>\rho, the constrained proximal value is ρˉD\bar\rho D-Lipschitz, giving EtZt2≤ρˉ2D4−pηp(G+σ)p\mathbb E_t Z_t^2\leq\bar\rho^2D^{4-p}\eta^p(G+\sigma)^p. Thus projection supplies the geometric input, and proximal-value concentration carries over.

  3. Rate. With η=η0T−1/p\eta=\eta_0T^{-1/p}, η0>0\eta_0>0, probability at least 1−δ1-\delta 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.

  1. Schedule. Under the RSSG theorem's assumptions, choose deterministic ηt>0\eta_t>0 with ∑tηt=∞\sum_t\eta_t=\infty and ∑tηtp<∞\sum_t\eta_t^p<\infty, e.g. ηt=η0t−a\eta_t=\eta_0t^{-a} for 1/p<a≤11/p<a\leq1.

  2. Proof. The bound EtΦ(xt+1)≤Φ(xt)−cηtΘt2+Kηtp\mathbb E_t\Phi(x_{t+1})\leq\Phi(x_t)-c\eta_t\Theta_t^2+K\eta_t^p 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$.
  3. 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.

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

Reviewer_H63HOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies stochastic weakly convex optimization on a compact C2C^2 embedded submanifold M⊂Rd\mathcal{M}\subset\mathbb R^d. Weak convexity is imposed on the objective in the ambient Euclidean space. The stochastic tangent subgradient is unbiased, and the noise is assumed to have only a finite conditional central moment of order pp, where 1<p≤21<p\leq2. The main contribution is a high-probability convergence guarantee for unclipped RSSG under a globally defined smooth retraction, while retaining the existing RSSG update and proximal stationarity measure.

The key analysis combines local quadratic distance control with compactness to obtain a global pp-order distance remainder, and then controls the conditional variance of proximal-value increments through the actual iterate displacement. This does not require a finite second moment of the stochastic subgradient. Theorem 5.2 provides a high-probability bound on the trajectory-averaged squared proximal stationarity residual. The stochastic oracle complexity for reducing this quantity to at most ε2\varepsilon^2 is

O~(ε−2p/(p−1)),\tilde{\mathcal{O}} \left(\varepsilon^{-2p/(p-1)}\right),

where O~\tilde{\mathcal{O}} suppresses logarithmic confidence factors and the associated problem constants. For p=2p=2, this recovers the ε−4\varepsilon^{-4} order. The guarantee concerns an average over the trajectory; it does not establish global optimality of the final iterate.

The paper also analyzes two variants that bound tangent-step lengths: GeoClip couples the clipping threshold with the step size, while GeoNorm normalizes a mini-batch subgradient mean. With B=TB=T, the latter uses parameter choices independent of pp and σ\sigma, but requires T2T^2 stochastic oracle calls. Experiments cover a linear Stiefel problem with an exactly computable proximal residual, DPCP subspace recovery, Hopkins155, and diagnostics comparing QR and polar retractions.

Critical strengths
  • The central result makes a discernible theoretical advance.

Li et al. established the relevant manifold subgradient and proximal stationarity framework. The finite-moment analysis of Zhu et al. includes expectation guarantees for unclipped methods on bounded convex constraint sets, and high-probability guarantees for clipped methods. The present paper gives a finite-moment, high-probability guarantee for unclipped RSSG on compact manifolds, extending beyond what those results explicitly cover. This comparison identifies the added guarantee; it does not claim that prior work proves clipping is necessary for high-probability convergence.

  • The key analysis is explanatory and preserves a simple update.

Local quadratic accuracy and global boundedness jointly handle unbounded tangent steps, while the analysis of proximal-value increments avoids the need for a second oracle moment. The main theorem therefore has analytical value in its own right, without relying on additional algorithmic components.

  • The geometric examples clarify the limits of the analytical tools. Appendix K presents a positive distance defect for QR and a second-order retraction example on the circle, showing that general retractions do not automatically inherit the zero-defect comparison available for polar retractions. These examples provide geometric intuition, but should not be interpreted as proving nonconvergence of QR-RSSG.

  • The experimental protocol and cost reporting are reasonably thorough. Exact proximal stationarity tests, paired random runs, tuning with independent validation seeds, 10,000 bootstrap resamples, and Holm correction help interpret the results. The paper reports both fixed sampling budgets and actual runtimes. The GPU timing advantage of batch implementations in Appendix M.4 illustrates why sample complexity and wall-clock time should be evaluated separately.

Critical weaknesses
  • Scope and practical use of fixed-batch GeoNorm.

Equation (18) explains the benefit of single-sample normalization under positive radial scaling. Beyond this structure, what problem or noise characteristics would favor fixed-batch GeoNorm? Could the authors use the existing fixed-budget and runtime results to clarify when they would recommend B=1B=1 over the batched variants? A discussion of the available evidence would suffice.

  • Effect of the tangent-step cap across retractions.

Would polar retraction exhibit a similar improvement when the same tangent-step cap is imposed? A matched-cap comparison in the existing linear Stiefel experiment would help clarify whether the benefit observed for QR is specific to that retraction.

  • Empirical tail behavior of unclipped RSSG.

Using the existing online-oracle settings with finite pp-th central moments for 1<p<21<p<2 and infinite variance, could the authors report empirical (1−δ)(1-\delta)-quantiles of RSSG's trajectory-averaged squared proximal stationarity residual over a range of TT and δ\delta, together with exceedance probabilities at prespecified residual thresholds? Please report the number of runs and uncertainty in these estimates, using confidence levels supported by the sample size. The aim is to assess the empirical tail behavior relevant to Theorem 5.2, without requiring the theoretical bounds to be tight in the experiments.

Questions for authors

See citical weaknesses.

3 comments

Thank you for the experimental questions. We address all three concerns below.

1. When to favor fixed-batch GeoNorm

For the radial-contamination DPCP setting tested here, small batches improve recovery per sample; larger vectorized batches reduce runtime.

  1. Matched-budget results. For Pareto DPCP with p=1.5p=1.5, 50% outliers, and Q=218Q=2^{18}, recovery and synchronized A800 timings are:

    GeoNorm batchMedian projector errorTime
    B=1B=10.0119150.2 s
    B=64B=640.08533.2 s
    B=T=512B=T=5120.09101.1 s
  2. Why single-sample normalization works here. It exactly cancels positive radial multipliers:

    \operatorname{nrm}(v_X(cy))=\operatorname{nrm}(v_X(y)),\quad c>0,$$ with $\operatorname{nrm}(0)=0$. Thus $B=1$ removes radial amplitude variability and permits more updates at the same sample budget.
  3. Batching for general noise. Under our oracle assumptions,

    Et∥vˉt−vt∥≤2σB−(p−1)/p.\mathbb E_t\|\bar v_t-v_t\|\leq2\sigma B^{-(p-1)/p}.

    Averaging helps estimate the mean when samples vary in direction as well as amplitude; normalized-direction accuracy also depends on the mean's magnitude. Larger batches trade fewer updates for better mean estimation and vectorization. We recommend selecting small fixed batches on independent validation runs at the intended sample or time budget. The schedule B=TB=T supplies the general-oracle asymptotic guarantee.

Section 6 (p. 9), Table 2, and Appendix M.5 give results and timing details.

2. Does polar benefit from the same tangent-step cap?

Yes. Both polar and QR benefit; their cap effects differ much less than the size of either effect.

  1. Four matched arms. We compare QR/polar with and without the cap on the linear St(32,4)\mathrm{St}(32,4) problem. All use statistical clipping with Λ=10\Lambda=10, η=0.1\eta=0.1, matched initializations and underlying random streams, 50 paired seeds per setting, and 1,024 oracle calls. Capped arms impose ∥ξt∥≤0.3\|\xi_t\|\leq0.3. All 100 added polar-capped trajectories completed with the original parameters.

  2. Measured cap effects. Paired mean decreases in final exact proximal residual Θ\Theta, with pointwise 95% intervals from 10,000 paired bootstrap resamples, are:

    ppQR: uncapped minus cappedPolar: uncapped minus capped
    1.20.2052 [0.1917, 0.2178]0.2042 [0.1908, 0.2169]
    1.80.1656 [0.1534, 0.1776]0.1649 [0.1526, 0.1770]

    Mean residuals fall by approximately 25% to 30%. QR-minus-polar differences are 0.000917 and 0.000690, versus individual cap effects of approximately 0.16 to 0.21.

  3. Relation to theory. Polar's global distance comparison gives a descent estimate for every tangent-step magnitude. The experiment shows an additional finite-budget benefit of step control for both retractions. At ηΛ=0.2<0.3\eta\Lambda=0.2<0.3, replay confirms identical capped and uncapped polar updates. Unclipped RSSG's guarantee covers both polar and QR; the active cap improves their measured performance here.

Section 6 and Figure 3 (pp. 9–10) summarize the results; Appendix M.3, Table 6, and Figure 7 (pp. 29–31) give trajectories, paired estimates, and protocol.

3. Empirical tails of unclipped RSSG

From T=64T=64 to 2,048, the empirical 90% quantile falls by about 81% at p=1.5,1.8p=1.5,1.8 and 39% at p=1.2p=1.2.

  1. The theorem's statistic. We measure

    AT=1T∑t=1TΘρˉ(xt)2,A_T=\frac1T\sum_{t=1}^T\Theta_{\bar\rho}(x_t)^2,

    before every update, as in Theorem 5.2. We use 900 existing online-oracle records on St(32,4)\mathrm{St}(32,4): 50 runs for each p∈{1.2,1.5,1.8}p\in\{1.2,1.5,1.8\} and T∈{64,128,256,512,1024,2048}T\in\{64,128,256,512,1024,2048\}. Pareto shape p+0.2p+0.2 gives finite pp-th moments and infinite variance in all three settings.

  2. Upper quantiles. Empirical 90% quantiles and binomial order-statistic intervals are:

    ppT=64T=64T=2048T=2048Pointwise 95% interval at T=2048T=2048
    1.20.46420.2828[0.2686, 0.3706]
    1.50.45970.0872[0.0862, 0.1003]
    1.80.45940.0855[0.0838, 0.1071]

    Figure 4 includes the 50%, 80%, and 90% quantiles at all six horizons.

  3. Exceedance probabilities. We retain every count at thresholds 0.25,0.5,1.00.25,0.5,1.0, fixed before retrospective analysis and shared across settings. At T=2048T=2048, 28/50 runs exceed 0.25 for p=1.2p=1.2, versus 0/50 for p=1.5,1.8p=1.5,1.8. Wilson intervals quantify uncertainty; 0/50 gives [0, 0.0713]. Each seed generates the objective, initialization, and oracle stream, so the statistics describe their joint distribution.

Figure 4 (p. 10) and Appendix M.3, Table 5 (pp. 29–30), give complete results and statistical details.

I thank the authors for their detailed responses. My concerns have all been addressed. I would like to keep my current score rather than raise it, since — as reflected in my confidence score above — I am not very familiar with this field of ``heavy-tailed oracles”.

Thank you for confirming that all your concerns have been addressed. We appreciate your careful review and constructive questions.

Reviewer_Z8eYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes an extension of weakly convex Riemannian stochastic subgradient methods to heavy-tailed noise. It provides a convergence analysis (rate and oracle complexity) and illustrative experiments.

Critical strengths
  • Overall well written and structured, and easy to follow.
  • Careful and detailed mathematical analysis. The parts that I checked seem correct.
  • The experiments include synthetic data and more realistic tasks, and are overall well done and well documented.
Critical weaknesses
  • The mathematical analysis mostly uses standard tools.
  • The objectives in the experiments are convex in the ambient matrix space. It would strengthen the paper to investigate an ambient nonconvex example; sparse PCA may be one example.
Questions for authors

Could the authors include, or comment on, an example that is nonconvex in the ambient space, such as sparse PCA?

2 comments

Thank you for your positive assessment of the analysis and experiments. We address both concerns below.

1. The analysis mostly uses standard tools

We agree that Freedman's inequality and local retraction estimates are established tools. Our contribution is high-probability convergence of unclipped RSSG with infinite oracle variance, obtained by controlling the proximal-value process under our compact-manifold assumptions.

  1. What the guarantee adds. Li et al. (2021) assume bounded second moments. 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 concern unclipped SGD under sub-Weibull noise and clipped SGD under finite-moment noise. We establish finite-moment high-probability stationarity with logarithmic confidence factors for unclipped RSSG under the stated manifold and retraction assumptions.

  2. Why additional control is needed. The oracle-noise inner product may have infinite variance, while the random pp-order remainder is only guaranteed to be integrable. Concentration using only the bounded proximal-value range contributes

    \qquad \eta\asymp T^{-1/p},$$ omitting confidence factors. This does not vanish for $1<p\leq2$. Applying Markov's inequality to an expectation bound instead introduces $1/\delta$ dependence. We therefore establish a variance bound that shrinks with the stepsize.
  3. How geometry provides this control. General retractions need not be nonexpansive. For every tangent-step magnitude, we establish

    \leq 2\langle\xi,x-y\rangle+C\|\xi\|^p.$$ The signed linear term preserves conditional unbiasedness in proximal descent; setting $y=x$ controls the squared displacement. We first establish descent in conditional expectation, then center the actual proximal value: $Z_t=\Phi(x_{t+1})-\mathbb E_t\Phi(x_{t+1})$, where $\Phi=\Phi_{\bar\rho}$. Its Lipschitz property yields $$\mathbb E_t Z_t^2 \leq L_\Phi^2\mathbb E_t\|x_{t+1}-x_t\|^2 \leq C\eta^p.$$ Taking conditional expectations first bounds the random $p$-order remainder deterministically. Summing the descent inequalities leaves $\sum_t Z_t$ as the fluctuation to control. Freedman's inequality then gives the $T^{-(p-1)/p}$ rate for the average squared proximal residual, with logarithmic confidence factors and **no clipping**.

Section 5.2 (pp. 5–6) explains the argument; Lemmas 5.1 and F.3 give the geometric and variance estimates.

2. An ambient-nonconvex example, such as sparse PCA

We added multi-component Stiefel sparse PCA with an ambient-nonconvex objective and an infinite-variance oracle, verifying the paper's assumptions.

  1. Nonconvexity and weak convexity. We consider

    =-\tfrac12\operatorname{tr}(X^\top\Sigma X)+0.1\|X\|_1, \qquad \Sigma=I+U\operatorname{diag}(4,3,2)U^\top.$$ Here $U$ has three orthonormal sparse columns (Appendix O.1). The objective is ambient nonconvex and nonsmooth. Since $\|\Sigma\|_{\mathrm{op}}=5$, adding $(5/2)\|X\|_F^2$ makes it convex, establishing global 5-weak convexity.
  2. Finite moments and infinite tangent variance. We use

    [-aa^\top X+0.1\operatorname{sign}(X)], \qquad \operatorname{sign}(0)=0.$$ Fresh Student observations with $\nu=3.5$ and covariance $\Sigma$ give a conditionally unbiased oracle with finite $p=1.5$ moments and **infinite variance after tangent projection at every feasible point**. Proposition O.1 proves these properties and bounded population subgradients; Appendix O.1 specifies sampling. Covariance-matched Gaussian observations provide a control.
  3. Independent confirmation results. Each method uses Q=16,384Q=16{,}384 observations with matched initial points and ordered observations. Parameters are selected on five validation seeds and frozen before 20 independent confirmation seeds. RSSG and GeoClip use single-sample updates; GeoNorm uses B=T=128B=T=128. Mean final exact population objectives are:

    NoiseInitial meanRSSGGeoClipGeoNorm
    Student, ν=3.5\nu=3.5−0.0716−4.8275−4.7473−4.8581
    Gaussian−0.0716−5.0452−5.0216−5.0599

    All 120 confirmation runs reduce their initial objective and maintain feasibility (maximum orthogonality error 4.94×10−154.94\times10^{-15}). The four paired 95% intervals against RSSG span zero. Under Student noise, RSSG also captures 96.5% of the maximum unregularized three-component explained variance, with mean tr⁡(X⊤ΣX)/12=0.9651\operatorname{tr}(X^\top\Sigma X)/12=0.9651, complementing the objective results on this ambient-nonconvex example.

Thanks to the authors for the response and the additional example, which strengthens the paper. However, my concerns regarding level of mathematical novelty remain, so I will keep my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.