- 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
- The paper addresses the dependence induced by random reshuffling and establishes pathwise convergence guarantees without relying on conditional variance recursions for fresh random sampling.
- The proposed estimator-error and memory condition covers four variance-reduction estimators, providing a common framework for analyzing their convergence.
- 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
- The complexity analysis does not fully account for the finite-sum size. The paper treats 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 would provide a more complete picture.
- 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.
- 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 . 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.
- The applicability of the KL convergence results remains insufficiently characterized. Theorem 4.6 requires the lifted objective 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 is semialgebraic. The authors should specify concrete conditions under which these convergence results apply and explain how the corresponding KL exponent can be determined.
- 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.
- 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
- 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?
- Under what conditions can the KL property and KL exponent of the lifted objective be verified, yielding explicit last-iterate convergence rates?
- Could the authors compare FISTA, NFG, and AR numerically and examine how residual tolerances affect computational costs and convergence?
- Could the authors provide complexity bounds that explicitly depend on , including component-gradient evaluations, to clarify scalability?
Response to Reviewer DNp9
We thank the reviewer for the constructive comments.
1. Dependence on n.
For all four verified estimators, Tε≤Cε−2 with n-independent C under the stated uniform assumptions. Each epoch uses O(n) component gradients and exactly n retractions and tangent solves, plus O(n) table initialization for SAGA/SAG. Total IFO, retraction, and tangent-solve bounds are therefore O(nε−2) with n-independent hidden constants. Zhang's SARAH/SPIDER bounds, O(n+n,ε−2) expected IFO and O(ε−2) retractions, are smaller; iRPMS provides a pathwise full-pass guarantee. The computable-output corollary retains the ε−2 epoch exponent for fixed n, but its certificate constant may depend on n; KL constants may depend on n and the trajectory.
2. Inner solvers, tolerance effects, and numerical comparisons.
With qt=LDDλ/Δ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). For fixed dual data, the high-accuracy bounds scale as Δt−1, Δt−1/2log(1/Δt), and Δt−1/2. Thus a tighter tolerance increases the certified inner work. Conversely, it reduces the O(Δt) perturbation in the descent inequality and the O(Δ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>2.
For the stated accuracy-dependent floor and α=α0/n, qt=O(ε−2) uniformly in n, yielding total bounds n,O(ε−4), n,O(ε−3log(2/ε)), and n,O(ε−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 proxR counts and wall-clock time.
3. Lipschitz assumption on R.
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 R is convex and Lipschitz on an open neighborhood of that set. This local formulation includes quadratic regularizers when trial points remain bounded; ℓ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 regularizer are semialgebraic. For sparse CCA, the bilinear loss and ℓ1 penalties are semialgebraic, while the product of generalized Stiefel manifolds and its tangent bundle have polynomial equality descriptions. The covariance matrices Cx,Cy≻0 may be ridge regularized. Thus, in both examples, Φ0(x,η)=Φ(x+η)+ιTM(x,η) 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.
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 n-uniform non-KL epoch bound and O(nε−2) retractions/tangent solves; the revised comparison table summarizes the distinctions.
6. Conclusion and scope.
We added a conclusion covering the unified pathwise theory, n-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 n.