acceptodds
Under review as a conference paper at ICLR 2027

Complexity and Last-Iterate Convergence of Inexact Riemannian Proximal Momentum Shuffling with Variance Reduction

Abstract

We develop a pathwise convergence and complexity theory for inexact Riemannian proximal methods that combine full-pass shuffling, variance reduction, projected momentum, and inexact tangent-space proximal solves. The main difficulty is that gradient estimators within a shuffled epoch are dependent, so standard one-step conditional variance recursions do not directly apply. We introduce an epochwise estimator error–memory condition and a projected-momentum lifting principle, and verify them for projection-based SVRG, projection-based SARAH/SPIDER, projected ambient SAGA, and projected ambient SAG. Combined with a prescribed Fenchel-dual residual criterion for the tangent proximal subproblems, this yields a deterministic epochwise descent estimate that controls estimator error, momentum memory, shuffling, and inner inexactness simultaneously. For fixed finite-sum size, we obtain epoch and retraction complexity and total proximal-evaluation complexities of , , and for FISTA, NFG, and accumulative-regularization inner solvers, respectively. Unlike stochastic analyses that guarantee stationarity in expectation, these bounds hold along every admissible shuffling trajectory. We further establish epochwise nonmonotone descent and relative-error estimates for the natural tangent-bundle lift of the objective. Under its ordinary Kurdyka–\Lojasiewicz property, the complete within-epoch trajectory has finite length and converges to a single critical point, without requiring a common deterministic limiting objective value across trajectories. Under a KL exponent, we obtain explicit last-iterate rates and a pathwise best-iterate outer complexity.

Primary area:
optimization
Keywords:
Riemannian optimization, variance reduction, full-pass shuffling, inexact proximal methods, Kurdyka--{\L}ojasiewicz analysis, last-iterate 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_DNp9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes iRPMS, a framework that combines full-pass shuffling, variance reduction, projected momentum, and inexact Riemannian proximal steps for nonconvex finite-sum composite optimization over compact embedded manifolds. The authors establish pathwise complexity bounds through a unified estimator-error and memory condition, and further prove whole-sequence convergence and last-iterate rates under the Kurdyka–Łojasiewicz (KL) property.

Critical strengths
  1. The paper addresses the dependence induced by random reshuffling and establishes pathwise convergence guarantees without relying on conditional variance recursions for fresh random sampling.
  2. The proposed estimator-error and memory condition covers four variance-reduction estimators, providing a common framework for analyzing their convergence.
  3. The analysis accounts for both outer iteration complexity and the computational cost of inexact proximal subproblems, and further establishes whole-sequence convergence and last-iterate rates under KL assumptions.
Critical weaknesses
  1. The complexity analysis does not fully account for the finite-sum size. The paper treats (n)(n) as a fixed constant and primarily reports complexity in terms of the target accuracy. As a result, the scalability of the method for large finite-sum problems remains unclear. Explicit bounds on component-gradient evaluations and their dependence on (n)(n) would provide a more complete picture.
  2. The lack of numerical experiments leaves the practical implications of the theoretical results unclear. The paper does not demonstrate the convergence behavior of the different estimators on concrete problems or compare the actual computational costs of FISTA, NFG, and AR. Such experiments would help illustrate how estimator errors evolve in practice and whether the observed computational costs are consistent with the theoretical bounds.
  3. Assumption 2.1 restricts the class of admissible regularizers. The paper requires (R) to be globally Lipschitz continuous over the ambient space, which excludes the standard quadratic regularizer R(x)=λ2∥x∥2R(x)=\frac{\lambda}{2}\|x\|^2. The authors should clarify whether the theory can be extended by relaxing this assumption to Lipschitz continuity on a relevant bounded region, thereby covering a broader class of regularizers.
  4. The applicability of the KL convergence results remains insufficiently characterized. Theorem 4.6 requires the lifted objective (Φ0)(\Phi_0) to satisfy the KL property at every cluster point, while Theorem 4.7 additionally assumes the existence of a KL exponent. Although Appendix A provides a sufficient condition based on semialgebraicity, Assumption 2.1 does not guarantee that (Φ0)(\Phi_0) is semialgebraic. The authors should specify concrete conditions under which these convergence results apply and explain how the corresponding KL exponent can be determined.
  5. The overlap with Zhang (2026) and the scope of the original contributions need further clarification. This paper is closely related to Zhang (2026) in its research problem, algorithmic components, and some technical formulations. If the abstract, introduction, and Eqs. (1), (3)–(5) contain substantial textual or technical overlap, the authors should clearly identify the sources of the reused or adapted material and better distinguish the new theoretical results and proof techniques introduced in this work.
  6. The paper lacks a dedicated conclusion section. The manuscript does not provide a concluding summary of its main theoretical contributions, assumptions, and limitations. A brief conclusion would help clarify the scope of the results and outline potential directions for future work.
Questions for authors
  1. The paper appears to overlap with Zhang (2026) in several places, including the abstract, introduction, and Eqs. (1), (3)–(5). Could the authors clarify the sources of these similarities and distinguish the novel contributions of this work?
  2. Under what conditions can the KL property and KL exponent of the lifted objective (Φ0)(\Phi_0) be verified, yielding explicit last-iterate convergence rates?
  3. Could the authors compare FISTA, NFG, and AR numerically and examine how residual tolerances affect computational costs and convergence?
  4. Could the authors provide complexity bounds that explicitly depend on �0��0�, including component-gradient evaluations, to clarify scalability?
1 comment
AuthorsOpenReview ↗

Response to Reviewer DNp9

We thank the reviewer for the constructive comments.

1. Dependence on nn.

For all four verified estimators, Tε≤Cε−2T_\varepsilon\le C\varepsilon^{-2} with nn-independent CC under the stated uniform assumptions. Each epoch uses O(n)O(n) component gradients and exactly nn retractions and tangent solves, plus O(n)O(n) table initialization for SAGA/SAG. Total IFO, retraction, and tangent-solve bounds are therefore O(nε−2)O(n\varepsilon^{-2}) with nn-independent hidden constants. Zhang's SARAH/SPIDER bounds, O(n+n,ε−2)O(n+\sqrt n\\,\varepsilon^{-2}) expected IFO and O(ε−2)O(\varepsilon^{-2}) retractions, are smaller; iRPMS provides a pathwise full-pass guarantee. The computable-output corollary retains the ε−2\varepsilon^{-2} epoch exponent for fixed nn, but its certificate constant may depend on nn; KL constants may depend on nn and the trajectory.

2. Inner solvers, tolerance effects, and numerical comparisons.

With qt=LDDλ/Δtq_t=L_DD_\lambda/\Delta_t, the per-subproblem proximal-evaluation bounds for FISTA, NFG, and AR are, respectively, O(1+qt),O(1+qtlog⁡(2+qt)),O(1+qt).O(1+q_t),\quad O(\sqrt{1+q_t}\log(2+q_t)),\quad O(1+\sqrt{q_t}). For fixed dual data, the high-accuracy bounds scale as Δt−1\Delta_t^{-1}, Δt−1/2log⁡(1/Δt)\Delta_t^{-1/2}\log(1/\Delta_t), and Δt−1/2\Delta_t^{-1/2}. Thus a tighter tolerance increases the certified inner work. Conversely, it reduces the O(Δt)O(\Delta_t) perturbation in the descent inequality and the O(Δt)O(\sqrt{\Delta_t}) contribution to the stationarity bound. These bounds explain the accuracy/work tradeoff; they do not predict actual wall-clock time or imply that tighter solves always improve total efficiency. A fixed positive tolerance alone does not guarantee exact convergence. Our schedules control the history-dependent term through descent, while the floor bounds inner work; the KL regime uses a vanishing polynomial tail with exponent r>2r>2.

For the stated accuracy-dependent floor and α=α0/n\alpha=\alpha_0/n, qt=O(ε−2)q_t=O(\varepsilon^{-2}) uniformly in nn, yielding total bounds n,O(ε−4)n\\,O(\varepsilon^{-4}), n,O(ε−3log⁡(2/ε))n\\,O(\varepsilon^{-3}\log(2/\varepsilon)), and n,O(ε−3)n\\,O(\varepsilon^{-3}).

The experiments use the same SSN tangent solver to isolate shuffling and momentum; they do not compare FISTA/NFG/AR or validate tolerance dependence. We could not complete a controlled ablation within the rebuttal period. If given the opportunity to revise, we will add a three-solver comparison and residual-tolerance sweep, using matched residual schedules and reporting both prox⁡R\operatorname{prox}_R counts and wall-clock time.

3. Lipschitz assumption on RR.

Global Lipschitz continuity was used to state uniform constants concisely. The proof only needs convex subgradients uniformly bounded on the relevant compact set, which follows if RR is convex and Lipschitz on an open neighborhood of that set. This local formulation includes quadratic regularizers when trial points remain bounded; ℓ1\ell_1 is already globally Lipschitz. We added this clarification.

4. KL applicability and exponent.

For sparse PCA, the Stiefel manifold, its tangent bundle, quadratic loss, and ℓ1\ell_1 regularizer are semialgebraic. For sparse CCA, the bilinear loss and ℓ1\ell_1 penalties are semialgebraic, while the product of generalized Stiefel manifolds and its tangent bundle have polynomial equality descriptions. The covariance matrices Cx,Cy≻0C_x,C_y\succ0 may be ridge regularized. Thus, in both examples, Φ0(x,η)=Φ(x+η)+ιTM(x,η)\Phi_0(x,\eta)=\Phi(x+\eta)+\iota_{T\mathcal M}(x,\eta) is proper, lower-semicontinuous, and semialgebraic, hence KL. This verifies the qualitative theorem's KL hypothesis; other algorithmic and estimator assumptions still apply. Its exponent need not equal that of the original constrained objective. Semialgebraicity guarantees KL but generally does not give a numerical exponent in advance; explicit rates are conditional on the exponent of Φ0\Phi_0.

5. Relation to Zhang (2026).

We identify inherited ingredients and new analysis. The exact tangent model is standard ManPG; the prescribed dual-residual test, inexact primal step, and projected-momentum/retraction update are adapted from Zhang. This provenance is stated in the method discussion and appendix, which also attributes reused residual lemmas to Zhang. New contributions are deterministic aggregate epochwise lifting for full-pass shuffling, four estimator-specific verifications, a pathwise feasible-iterate certificate, and complete-trajectory KL analysis. Lifting yields the nn-uniform non-KL epoch bound and O(nε−2)O(n\varepsilon^{-2}) retractions/tangent solves; the revised comparison table summarizes the distinctions.

6. Conclusion and scope.

We added a conclusion covering the unified pathwise theory, nn-uniform non-KL complexity, computable certificate, KL last-iterate analysis, and targeted shuffling/momentum experiments. It distinguishes these results from inherited VR recursions and Zhang's fresh-sampling work bounds; KL and certificate constants may depend on nn.

Reviewer_7jzqOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies nonsmooth finite-sum optimization on a compact embedded manifold: min⁡x∈M  Φ(x)=1n∑j=1nfj(x)+R(x)\min_{x\in\mathcal M}\;\Phi(x)=\frac1n\sum_{j=1}^n f_j(x)+R(x). The proposed iRPMS method performs a shuffled full pass in each epoch, combining variance reduction, projected momentum, and an inexact tangent proximal step. Its main analytical device is a pathwise epochwise error-memory condition, verified for full-pass variants of SVRG, SARAH/SPIDER, SAGA, and SAG. This yields deterministic descent along each admissible permutation sequence and, for fixed nn, an O(ε−2)O(\varepsilon^{-2}) best-iterate epoch bound. The proximal-evaluation bounds for FISTA, NFG, and accumulative regularization are O(ε−4)O(\varepsilon^{-4}), O(ε−3log⁡ε−1)O(\varepsilon^{-3}\log\varepsilon^{-1}), and O(ε−3)O(\varepsilon^{-3}), respectively.

Under a KL assumption on a tangent-bundle lifted objective, the paper also proves finite length, convergence of all within-epoch iterates to one critical point, and explicit last-iterate rates. Relative to Zhang (2026), the main advance is the pathwise theory for without-replacement full-pass shuffling and the extension of KL rates from the deterministic n=1n=1 setting to shuffled full passes with n>1n>1, rather than a new proximal-momentum-VR architecture.

Critical strengths
  • The paper isolates a real difficulty absent from fresh-sampling analyses: within an epoch, the current iterate and the remaining permutation indices are dependent.
  • It develops a deterministic/pathwise epochwise framework rather than proving only an expectation guarantee over permutations.
  • The estimator-agnostic condition separates the common convergence proof from the verification of individual estimators.
  • Four representative variance-reduction mechanisms are covered in one framework.
  • The paper simultaneously handles changing tangent spaces, projected momentum, estimator memory, and inexact tangent proximal solves.
  • The dual-gradient stopping rule is prescribed before solving the current subproblem and is implementable under the stated proximal-oracle assumptions.
  • The KL analysis proves finite length and convergence of all within-epoch iterates to a single critical point along each trajectory.
  • Relative to Zhang (2026), the paper removes the need for a common deterministic limiting objective value across shuffling trajectories and extends explicit last-iterate rates to the full-pass n>1n>1 setting.
Critical weaknesses
  • The algorithmic novelty is limited: the problem class, projected momentum, inexact tangent proximal step, dual-residual test, estimator families, and inner-solver bounds largely follow Zhang (2026). The main novelty is the pathwise analysis for full-pass shuffling.
  • The O(ε−2)O(\varepsilon^{-2}) result fixes nn and counts epochs. No joint (n,ε)(n,\varepsilon) oracle bound is given, and the hidden constants may depend strongly on nn. Thus the result cannot be compared directly with Zhang's explicit IFO bounds, such as O(n+n ε−2)O(n+\sqrt n\,\varepsilon^{-2}) for SARAH/SPIDER.
  • Although the pathwise KL result is meaningful, the paper does not sharply identify which conclusions cannot be obtained from Zhang (2026) by fixing a sampling trajectory or applying a deterministic specialization.
  • The best-iterate certificate uses the unavailable exact model step η^it\widehat\eta_i^t, and no computable output rule is supplied. Its relation to a standard stationarity measure at a feasible iterate is also unclear.
  • There are no experiments or sharper theoretical results demonstrating a concrete benefit from shuffling, nonzero momentum, or the frozen-table SAGA/SAG design.
Questions for authors
  1. Which results in this paper provably cannot be derived from Zhang (2026) by fixing a sampling realization or specializing its abstract convergence framework? A theorem-level comparison could materially change my novelty assessment.

  2. Can the authors provide joint (n,ε)(n,\varepsilon) bounds for component-gradient evaluations, retractions, and proximal evaluations, including the nn-dependence hidden in the stepsize and other constants? How do these bounds compare with Zhang's explicit IFO complexities?

  3. Is the removal of the deterministic limiting-objective-value assumption due to a genuinely new KL argument, or mainly to conditioning on a fixed permutation trajectory? Please identify the precise obstruction in Zhang (2026) and how it is resolved here.

  4. Can the authors provide concrete verifiable conditions under which the lifted function Φ0\Phi_0 satisfies the assumed KL property, and clarify how its KL exponent relates to that of the original constrained objective?

  5. Can the authors provide either theoretical or empirical evidence that shuffling, nonzero momentum, and the frozen-table SAGA/SAG variants improve over the Zhang (2026) methods or a full-gradient baseline?

3 comments
AuthorsOpenReview ↗

Response to Reviewer 7jzq

We thank the reviewer for the detailed and constructive questions. The general response supplies a theorem-level comparison with Zhang (2026).

1. What does not follow by fixing a trajectory in Zhang (2026)?

Zhang's estimator recursion is a conditional-expectation inequality under fresh sampling. Under full-pass shuffling, xitx_i^t depends on previously visited indices and the next index is restricted to the remaining set. The fresh-sampling conditional distribution is absent, and fixing a realization cannot turn an expectation inequality into a realization-wise one. Our epochwise error-memory bound, aggregate projected-momentum lifting lemma, and four full-pass estimator verifications supply the missing deterministic estimates.

2. Dependence on nn.

For all four estimators, the revised proof uses ν=n2νˉ\nu=n^2\bar\nu and α=α0/n\alpha=\alpha_0/n, with νˉ,α0\bar\nu,\alpha_0 independent of nn. Under the stated uniform assumptions, the theoretical best-iterate horizon satisfies Tε≤Cε−2,C independent of n,ε.T_\varepsilon\le C\varepsilon^{-2},\qquad C\text{ independent of }n,\varepsilon. Each realization uses O(n)O(n) component gradients per epoch, plus O(n)O(n) initialization for SAGA/SAG. Hence IFO, retraction, and tangent-solve counts are O(nε−2)O(n\varepsilon^{-2}). Zhang's SARAH/SPIDER result gives O(n+n,ε−2)O(n+\sqrt n\\,\varepsilon^{-2}) expected IFO calls and O(ε−2)O(\varepsilon^{-2}) retractions: smaller fresh-sampling counts, while iRPMS gives a pathwise shuffled guarantee and feasible-iterate certificate. The computable-output corollary retains the ε−2\varepsilon^{-2} epoch exponent for fixed nn, but its certificate constant may depend on nn; KL constants may depend on both nn and the trajectory.

3. Why is a common deterministic limiting value unnecessary?

We first prove an actual pathwise epochwise descent inequality. For each trajectory, its own lifted-objective values therefore converge. The KL inequality is then uniformized on that trajectory's cluster set. Different trajectories may have different limiting values. This is not a conditioning of Zhang's stochastic KL proof: the new deterministic descent input permits the trajectory-wise argument.

4. Verifiable KL conditions and examples.

For centered data aj∈Rpa_j\in\mathbb R^p, standard sparse PCA is min⁡X⊤X=Ir−12n∑j=1n∥X⊤aj∥2+λ∥X∥1.\min_{X^\top X=I_r}-\frac1{2n}\sum_{j=1}^n\lVert X^\top a_j\rVert^2+\lambda\lVert X\rVert_1. The Stiefel manifold, its tangent bundle, quadratic finite-sum loss, and ℓ1\ell_1 regularizer are semialgebraic. For paired data aj∈Rp,bj∈Rqa_j\in\mathbb R^p,b_j\in\mathbb R^q, sparse CCA is min⁡U⊤CxU=Ir\V⊤CyV=Ir−1n∑j=1n⟨U⊤aj,V⊤bj⟩+λu∥U∥1+λv∥V∥1,\min_{\substack{U^\top C_xU=I_r\\\V^\top C_yV=I_r}}-\frac1n\sum_{j=1}^n\langle U^\top a_j,V^\top b_j\rangle+\lambda_u\lVert U\rVert_1+\lambda_v\lVert V\rVert_1, where Cx,Cy≻0C_x,C_y\succ0; ridge-regularized covariances may be used in high dimensions. The product of generalized Stiefel manifolds and its tangent bundle have polynomial equality descriptions; the loss and regularizer are semialgebraic. Consequently, in both cases Φ0(x,η)=Φ(x+η)+ιTM(x,η)\Phi_0(x,\eta)=\Phi(x+\eta)+\iota_{T\mathcal M}(x,\eta) is proper, lower-semicontinuous, and semialgebraic, hence KL. This verifies the qualitative convergence theorem's KL hypothesis; other algorithmic and estimator assumptions remain in force. The exponent of Φ0\Phi_0 need not equal that of the constrained objective. Semialgebraicity ensures KL, but generally does not supply a numerical exponent in advance; the explicit rate theorem is conditional on the exponent of Φ0\Phi_0.

5. Computable output and stopping.

We replaced the unavailable exact-model certificate by Gα(x)=α−1∥pα(x)∥G_\alpha(x)=\alpha^{-1}\lVert p_\alpha(x)\rVert, whose zeros characterize criticality. For the four estimators, max⁡0≤i<nGα(xit)≤CcertCt,Ct=St2+St−12+Δt.\max_{0\le i<n}G_\alpha(x_i^t)\le C_{\rm cert}C_t,\qquad C_t=\sqrt{S_t^2+S_{t-1}^2+\Delta_t}. All terms in CtC_t are computed or prescribed. Return the epoch minimizing CtC_t, or stop when CcertCt≤εC_{\rm cert}C_t\le\varepsilon if a valid upper bound on CcertC_{\rm cert} is available. No exact surrogate step, exact true-gradient model step, estimator error, or memory variable must be evaluated. The computable-output corollary is O(ε−2)O(\varepsilon^{-2}) epochs for fixed nn; its certificate constant is not asserted uniform in nn, unlike the theoretical best-iterate bound.

6. Experiments.

The new CIFAR-10 sparse PCA study directly tests sampling and momentum. Under FDA and cumulative retractions, shuffling is competitive across all four VR realizations: SPIDER is closely matched, shuffled SVRG slightly favorable, and SAGA/SAG budget dependent. For shuffled SPIDER, χ=0.2,0.4\chi=0.2,0.4 improve on χ=0\chi=0 under both measures; χ=0.8\chi=0.8 gives no further final gain. The baselines are the corresponding with-replacement realizations, so this study directly addresses sampling policy and momentum.

Thank you for the detailed response. The rebuttal has addressed most of my major concerns. In particular, the authors explain why Zhang's conditional-expectation analysis cannot be converted into a realization-wise result simply by fixing a sampling trajectory. The new epochwise estimates therefore represent a genuine pathwise contribution.

The explicit O(nϵ−2)O(n\epsilon^{-2}) IFO, retraction, and tangent-solve bounds clarify the computational tradeoff. Although these bounds remain weaker than Zhang's expected IFO complexity for SARAH/SPIDER, they accompany a stronger pathwise guarantee. The trajectory-wise KL argument, semialgebraic sparse PCA/CCA examples, and new computable stationarity certificate also address my concerns about the limiting-value assumption, applicability of the KL hypothesis, and unavailable exact-step certificate. The added experiment provides useful, though still limited, evidence for shuffling and momentum.

My remaining reservations concern the incremental algorithmic novelty, the higher full-pass cost, and the limited experimental scope. Nevertheless, assuming these revisions are incorporated into the manuscript, I believe the rebuttal sufficiently strengthens the contribution, and I will raise my rating from 2 to 3.

AuthorsOpenReview ↗

Confirmation of manuscript revisions

Thank you for your careful reassessment and constructive feedback. We confirm that the revisions described in our response to your review have already been incorporated into the current manuscript on OpenReview.

Reviewer_AU8xOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents a Riemannian proximal method with momentum, throwing in a combination of shuffling, variance reduction and proximal components, with an aim to understand last iterate convergence (which is enabled by KL assumptions). It permits several VR schemes, and allows the tangent space proximal steps to be inexact. It proves deterministic bounds. There are no experiments.

Critical strengths
  • Dropping the common limiting value assumption might be a potential strength of this paper (but it is not really a "critical" strength.
Critical weaknesses
  • The net novelty of the paper is extremely limited (gradient cost matches ManPG, and retraction cost is much worse)
  • The theory has a few hidden gotchas (regarding number of prox calls).

The Zhang (2026) paper cited by the current authors also tackles projected momentum, VR estimators, inexact tangent solves and KL based analysis. The net new contribution on top of that work is quite minimal, and to be honest, should have fit in a couple of pages of work (conceptually speaking, because the rest of the details are in the appendix, which seems to be mostly correct, at a first read).

Questions for authors

I tried to compute the number of "full-gradient" evaluations and the number of retractions and prox-solves. Is the assessment below accurate:

  • ManPG takes O(ϵ−2)O(\epsilon^{-2}) full-gradient equivalents, with O(ϵ−2)O(\epsilon^{-2}) retraction/prox-solve cost.
  • iRPMS (this paper) does approximately O(ϵ−2)O(\epsilon^{-2}) full-gradient equivalents, but it does O(nϵ−2)O(n \epsilon^{-2}) retract/prox calls
  • Zhang (2026) does 1+ϵ−2/n1 + \epsilon^{-2}/\sqrt{n} full-gradient equivalents, and just O(ϵ−2)O(\epsilon^{-2}) retracts/prox calls.

So that the authors' presented work, which says: we'll assume nn is a constant, and hence drop it from the complexity bounds, is rather misleading. It is worse than existing work, and trying to hide the nn away by calling it a constant is misleading, especially when studying incremental gradient / shuffling etc. settings.

1 comment
AuthorsOpenReview ↗

Response to Reviewer AU8x

We thank the reviewer for the careful assessment. We address the concerns in their original order.

1. Novelty relative to Zhang (2026).

We agree that VR, projected momentum, and prescribed inexact tangent solves are inherited ingredients. The revision no longer presents iRPMS as a new VR architecture. Its contribution is unified convergence and complexity analysis for complete without-replacement passes, valid pathwise for every fixed permutation sequence.

This does not follow by fixing a realization in Zhang's analysis. Zhang's estimator recursion uses conditional expectations under fresh sampling. Within a shuffled epoch, the iterate depends on the indices already visited and the next index is restricted to the remaining set. The fresh-sampling recursion therefore does not provide the required pathwise bound; an expectation inequality also does not imply a realization-wise inequality. Our deterministic epochwise error-memory bound, aggregate projected-momentum lifting, and separate full-pass verifications for SVRG, SARAH/SPIDER, SAGA, and SAG supply these missing estimates.

With ν=n2νˉ\nu=n^2\bar\nu and α=α0/n\alpha=\alpha_0/n, aggregate lifting gives Tε≤Cε−2T_\varepsilon\le C\varepsilon^{-2} with nn-independent CC under the uniform assumptions, hence O(nε−2)O(n\varepsilon^{-2}) retractions and tangent solves. The ε\varepsilon exponent matches Zhang, but our operation counts have larger nn dependence. The added guarantee is deterministic validity for every full-pass sequence under feasible-iterate criticality.

Zhang bounds expected squared model-criticality Θ(xk,η^k)\Theta(x^k,\widehat\eta^k) at an exact surrogate step not computed by the inexact method. We instead use Gα(x)=α−1∥pα(x)∥,Gα(x)=0  ⟺  x is critical,G_\alpha(x)=\alpha^{-1}\lVert p_\alpha(x)\rVert,\qquad G_\alpha(x)=0\iff x\text{ is critical}, with the pathwise certificate max⁡0≤i<nGα(xit)≤CcertCt,Ct=St2+St−12+Δt.\max_{0\le i<n}G_\alpha(x_i^t)\le C_{\rm cert}C_t,\qquad C_t=\sqrt{S_t^2+S_{t-1}^2+\Delta_t}. All terms in CtC_t are computed or prescribed. It selects the returned epoch and gives a certified stopping rule when a valid upper bound on CcertC_{\rm cert} is available. This constant need not be uniform in nn. Our KL result covers the complete n>1n>1 shuffled trajectory and allows trajectory-dependent limiting values; its constants may depend on nn and the trajectory.

2. Dependence on nn and actual work.

We strengthened and corrected the dependence statement. For all four estimators, ν=n2νˉ\nu=n^2\bar\nu and α=α0/n\alpha=\alpha_0/n, with νˉ,α0\bar\nu,\alpha_0 independent of nn. Under uniform data, geometry, momentum, and strict-margin assumptions, Tε≤Cε−2,C independent of n,ε,0<ε≤1.T_\varepsilon\le C\varepsilon^{-2},\quad C\text{ independent of }n,\varepsilon,\quad 0<\varepsilon\le1. The reviewer's three-bullet accounting is correct at the level of orders once work units and stationarity notions are distinguished:

MethodComponent-gradient workRetractions and tangent solves
ManPGO(nε−2)O(n\varepsilon^{-2}); O(ε−2)O(\varepsilon^{-2}) full gradientsO(ε−2)O(\varepsilon^{-2}); exact tangent solves
iRPMSO(nε−2)O(n\varepsilon^{-2}); O(ε−2)O(\varepsilon^{-2}) full-gradient equivalentsO(nε−2)O(n\varepsilon^{-2})
Zhang, SARAH/SPIDERO(n+n,ε−2)O(n+\sqrt n\\,\varepsilon^{-2}) expected IFO; O(1+ε−2/n)O(1+\varepsilon^{-2}/\sqrt n) full-gradient equivalentsO(ε−2)O(\varepsilon^{-2})

Thus Zhang has smaller fresh-sampling IFO and retraction orders. iRPMS supplies an nn-uniform theoretical epoch constant, a pathwise full-pass guarantee, and a feasible-iterate certificate. KL bounds remain Oω,n(⋅)O_{\omega,n}(\cdot).

3. Number of primitive proximal calls.

One inner iteration uses one retraction and one tangent proximal subproblem: exactly nTεnT_\varepsilon subproblems. In contrast, \\#\operatorname{prox}_R counts primitive Euclidean proximal evaluations by the dual solver. Under the same uniform assumptions:

Dual solverTotal \\#\operatorname{prox}_R
FISTAn,O(ε−4)n\\,O(\varepsilon^{-4})
NFGn,O(ε−3log⁡ε−1)n\\,O(\varepsilon^{-3}\log\varepsilon^{-1})
Accumulative regularizationn,O(ε−3)n\\,O(\varepsilon^{-3})

The hidden constants are independent of nn: α=α0/n\alpha=\alpha_0/n and Δt≥ε2/(2nCˉcomp)\Delta_t\ge\varepsilon^2/(2n\bar C_{\rm comp}) yield LDDλ/Δt=O(ε−2)L_DD_\lambda/\Delta_t=O(\varepsilon^{-2}) uniformly in nn. The revised caption and text define the counted unit.

4. Experiments.

We added CIFAR-10 sparse PCA experiments for all four VR realizations. Under FDA and cumulative retractions, shuffling is competitive: SPIDER is closely matched, shuffled SVRG slightly favorable, and SAGA/SAG budget dependent. In shuffled SPIDER, χ=0.2,0.4\chi=0.2,0.4 outperform χ=0\chi=0 under both work measures, showing a material momentum effect.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response and revision summary for the AC and reviewers

We thank the reviewers for their careful reading and constructive comments on novelty relative to Zhang (2026), dependence on nn, the stationarity certificate, and experiments. We have substantially revised the manuscript to make its scope and contribution precise.

The contribution is a unified pathwise convergence and complexity theory for full-pass without-replacement shuffling with VR, projected momentum, and inexact tangent solves. The algorithmic mechanisms are inherited or adapted; the new contribution is their deterministic epochwise analysis along every complete permutation sequence. For all four verified VR estimators, under the stated uniform problem-data, geometry, momentum, and positive-margin assumptions, Tε≤Cε−2,C independent of n.T_\varepsilon\le C\varepsilon^{-2},\qquad C\text{ independent of }n. Here TεT_\varepsilon is the theoretical best-iterate horizon in completed epochs.

AspectZhang (2026), iRPMVRThis paper, iRPMS
IngredientsVR, projected momentum, prescribed inexact tangent solvesExisting mechanisms instantiated with full-pass shuffling under a common pathwise analysis
SamplingFresh stochastic sampling; one-step conditional expectationsComplete without-replacement permutations; within-epoch dependence
Estimator analysisConditional error-dissipation recursionDeterministic epochwise error-memory inequality and aggregate momentum lifting, verified for SVRG, SARAH/SPIDER, SAGA, SAG
ComplexityExpected squared model-criticalityPathwise feasible-iterate criticality for every permutation sequence; Tε≤Cε−2T_\varepsilon\le C\varepsilon^{-2} with nn-independent CC under uniform assumptions
StationarityModel-based Θ(xk,η^k)\Theta(x^k,\widehat\eta^k) at an exact surrogate stepGα(x)=α−1∥pα(x)∥G_\alpha(x)=\alpha^{-1}\lVert p_\alpha(x)\rVert, with Gα(x)=0G_\alpha(x)=0 iff xx is critical
OutputExact surrogate step is not computed by the inexact methodmax⁡iGα(xit)≤CcertCt\max_iG_\alpha(x_i^t)\le C_{\rm cert}C_t, where Ct=St2+St−12+ΔtC_t=\sqrt{S_t^2+S_{t-1}^2+\Delta_t} uses computed steps and prescribed tolerances
KLAlmost-sure convergence with a common deterministic limiting shifted-objective value; explicit rates for deterministic n=1n=1Pathwise finite length, convergence of the complete n>1n>1 trajectory, and last-iterate rates without a common limiting value across trajectories

This is not obtained by fixing a realization in Zhang's expectation argument. Conditional on the within-epoch history, the next shuffled index is restricted to the remaining set, rather than freshly sampled from the full set. A conditional-expectation inequality also does not imply its realization-wise counterpart. Our epochwise lifting and four full-pass verifications provide the missing deterministic input.

Main revisions.

  1. The title, abstract, introduction, contributions, comparison table, and conclusion now explicitly position this as an analysis paper. The table distinguishes deterministic, expected, and pathwise guarantees.
  2. All four estimators have the nn-uniform theoretical epoch bound above. Each epoch contains exactly nn inner steps, giving O(nε−2)O(n\varepsilon^{-2}) component gradients, retractions, and tangent solves with nn-independent hidden constants under the uniform assumptions.
  3. The feasible-iterate measure and computable certificate give an output rule: return the epoch minimizing CtC_t, or stop at CcertCt≤εC_{\rm cert}C_t\le\varepsilon when a valid upper bound on CcertC_{\rm cert} is available. This certificate constant need not be uniform in nn; the certified bound retains the ε−2\varepsilon^{-2} epoch exponent for each fixed nn.
  4. We clarify the lifted-objective KL assumption and the local Lipschitz requirement on RR. Standard sparse PCA and ridge-regularized sparse CCA have semialgebraic lifted objectives and hence the KL property. KL constants may depend on nn and the trajectory.
  5. We add CIFAR-10 sparse PCA experiments comparing shuffling and with-replacement sampling for all four estimators, plus a shuffled-SPIDER momentum sweep.

On this instance, shuffling is competitive under both FDA and cumulative retractions: SPIDER is closely matched, shuffled SVRG is slightly favorable, and SAGA/SAG are budget dependent. For shuffled SPIDER, χ=0.2,0.4\chi=0.2,0.4 outperform χ=0\chi=0 under both measures; χ=0.8\chi=0.8 gives no further final gain. FDA is the figures' normalized empirical data-pass convention, not an IFO count. The competitive behavior is consistent with complete within-epoch coverage, which avoids repeated or omitted components.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.