REVIEW 2 major objections 4 minor 1 cited by
Decentralized projected Riemannian stochastic recursive momentum method for nonconvex optimization
T0 review · 2 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read This paper proposes a decentralized single-loop stochastic recursive momentum method for smooth nonconvex optimization over compact submanifolds and proves an oracle complexity of $O(\epsilon^{-3/2})$ per node in the online setting.
desk verdict DPRSRM is a sensible combination of known ingredients, but the advertised O(ε^{-3/2}) oracle complexity is unsupported: a dropped term from Lemma 4.5 leaves a K^{-1/3} error, and Assumption 3.4 is too weak for several lemmas. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the DPRSRM update, which combines three components. The hybrid estimator $q_{i,k} = \operatorname{grad} f_i(x_{i,k}, \xi_{i,k}) + (1-\tau)(d_{i,k-1} - \operatorname{grad} f_i(x_{i,k-1}, \xi_{i,k}))$ is a recursive momentum variance-reduction step; it is clipped to norm $B$ to form $d_{i,k}$. The gradient tracker $s_{i,k} = \sum_j W_{ij} s_{j,k-1} + d_{i,k} - d_{i,k-1}$ propagates information about the global gradient through the network. The iterate is updated by tangent-space projection of $s$ onto the tangent bundle and then manifold projection: $x_{i,k+1} = P_{\mathcal M}(\sum_j W_{ij}x_{j,k} - \alpha v_{i,k})$. Proximal smoothness of the compact submanifold supplies the Lipschitz property of the projection operator $P_{\mathcal M}$ that controls the consensus error.
What would settle it
Run DPRSRM on a compact submanifold with a smooth nonconvex objective and a stochastic gradient oracle that is unbiased and has bounded variance but unbounded support, such as Gaussian noise, so that the printed Assumption 3.4 holds but the almost-sure bound fails; if the consensus error or the gradient-norm bound in Corollary 3.8 is violated, or if the clipping constant must grow with $1/\epsilon$, then the claimed $O(\epsilon^{-3/2})$ rate depends on the unstated stronger assumption.
Extended reading notes
Core claim
On its own terms, the paper establishes that combining a hybrid stochastic recursive momentum estimator with gradient tracking and projection onto a compact submanifold yields an oracle complexity of $O(\epsilon^{-3/2})$ for decentralized online nonconvex manifold optimization. Corollary 3.8 states that with step size $\alpha = K^{-1/3}$ and momentum parameter $\tau = K^{-2/3}$, after $K = O(\max\{(C+\Gamma_1)^{3/2}\epsilon^{-3/2},\ \Gamma_2\epsilon^{-1},\ (6\rho_2\nu^2)^{3/4}\epsilon^{-3/4}\})$ iterations the iterates are $\epsilon$-stationary; the dominant term is the $\epsilon^{-3/2}$ oracle complexity. The result applies to general compact submanifolds, not just the Stiefel manifold, and needs only one consensus step per iteration, whereas earlier projection and retraction methods required $O(\log(1/\sigma_2))$ consensus rounds. The paper further shows numerically on decentralized principal component analysis and low-rank matrix completion that DPRSRM beats the stochastic decentralized Riemannian gradient descent and projected gradient baselines considered.
Load-bearing premise
The load-bearing premise is that every stochastic gradient is almost surely bounded by a fixed constant and that the average squared difference of two stochastic gradients grows at most linearly with the distance between their inputs, while the assumptions stated in the paper only guarantee bounded variance and a first-moment Lipschitz condition; if the stronger premise is not added, the consensus and optimality bounds do not follow.
Editorial extensions
If this is right
- Each node reaches an $\epsilon$-stationary point with $O(\epsilon^{-3/2})$ stochastic gradient oracle calls, up to the smaller $\epsilon^{-1}$ and $\epsilon^{-3/4}$ terms in Corollary 3.8.
- Only one consensus communication round is needed per iteration, removing the $O(\log(1/\sigma_2))$ consensus-factor inflation of earlier projection and retraction methods on the Stiefel manifold.
- The method is single-loop and online: no restarting with a large batch is required, and each node uses only $O(1)$ gradient evaluations per iteration.
- The convergence guarantee covers general compact submanifolds, using projection $P_{\mathcal M}$, not just Stiefel and orthogonality constraints.
- Numerical tests on decentralized PCA and low-rank matrix completion show faster decrease of consensus error, objective gap, and gradient norm than the DRSGD and DRPGD baselines tested.
Reading between the lines
- The $O(\epsilon^{-3/2})$ rate matches the known single-machine recursive-momentum rate, which suggests that the decentralized manifold constraint and one-round consensus need not add oracle overhead in this parameter regime.
- Because the proof uses only projection Lipschitzness and a quadratic upper bound on the local objectives, the same estimator-and-consensus scheme should transfer to other proximally smooth constraint sets, such as sphere products or rank-constrained sets.
- The clipping constant $B$ is a free user parameter; a data-dependent or adaptive choice of $B$ might preserve the rate while allowing larger practical steps, though this is not analyzed in the paper.
- Since the method uses one communication round per iteration, it is a natural candidate for combining with gradient compression or quantization; whether the $O(\epsilon^{-3/2})$ oracle complexity survives communication compression is left open.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes DPRSRM, a decentralized projected Riemannian stochastic recursive momentum method for minimizing the average of smooth nonconvex functions over a compact submanifold in an online setting. The algorithm combines a clipped hybrid stochastic gradient estimator (3.6)-(3.8), gradient tracking (3.9), tangent-space projection, and a single consensus step. The main theoretical claims are Theorem 3.6 (consensus error), Theorem 3.7 (optimality error), and Corollary 3.8, which asserts that with alpha = K^{-1/3} and tau = K^{-2/3} the method reaches an epsilon-stationary point (Definition 2.1) with oracle complexity O(epsilon^{-3/2}) per node, improving on existing O(epsilon^{-2}) rates. Numerical experiments on decentralized PCA and low-rank matrix completion are reported.
Significance. If the O(epsilon^{-3/2}) rate were valid, this would be a meaningful advance for online decentralized manifold optimization: the method is single-loop, uses O(1) stochastic gradients per iteration per node, has no large-batch restart, and uses one consensus step for general compact submanifolds. The paper is clearly structured and the appendix contains a detailed proof attempt. However, the central rate is not established by the submitted proof. The proof of Theorem 3.7 drops a term of order nu^2/(tau K), which with the claimed parameter choices is K^{-1/3}, and the proof relies on bounded stochastic gradients and a second-moment Lipschitz property that are not present in Assumption 3.4. Because the main contribution is precisely the improved oracle complexity, these issues are load-bearing.
major comments (2)
- [3.3, Theorem 3.7 and Corollary 3.8; proof in Section 4.2 and Lemma 4.5] Substituting Lemma 4.5 into the inequality (4.7) and dividing by alpha K / 4 yields an additional term 6(1+rho2 tau^2) nu^2 / (tau K). The displayed Theorem 3.7 instead contains 12/n (1+rho2 tau^2)(nu^2 tau + rho3 n alpha^4/tau), which replaces nu^2/(tau K) with nu^2 tau and introduces an unexplained factor 1/n. With the Corollary 3.8 choices alpha = K^{-1/3} and tau = K^{-2/3}, the omitted term is 6(1+rho2 tau^2) nu^2 K^{-1/3}, not O(K^{-2/3}). Therefore the bound in (4.8), the O(epsilon^{-3/2}) oracle complexity in (3.18), and Corollary 3.8 are not supported by the supplied proof. Making the omitted term below epsilon would require K = O(epsilon^{-3}), not K = O(epsilon^{-3/2}). A repair would need a time-varying tau or an initial large batch, neither of which is present in Algorithm 3.1.
- [3.1, Assumption 3.4 and Lemmas 4.1, 4.3, 4.5] The proof requires stronger stochastic assumptions than Assumption 3.4 provides. Lemma 4.1 uses ||d_0|| <= sqrt(n) L for the unclipped initial stochastic gradient; Lemma 4.3 uses deterministic bounds such as ||grad f(bar x_k)|| <= L; and Lemma 4.5, specifically equation (B.24), requires a second-moment Lipschitz condition E||grad f(x_k, xi_k) - grad f(x_{k-1}, xi_k)||^2 <= L^2 ||x_k - x_{k-1}||^2. Assumption 3.4 only contains the unbiasedness condition (3.3), the variance bound (3.4), and the first-moment condition (3.5). Moreover, (3.5) is labeled 'mean-squared' but is written with first moments. As written, the consensus and optimality bounds are unsupported. The proof also uses ||d_k|| <= sqrt(n) L for the clipped estimator, whereas Algorithm 3.1 clips at B >= L, so the bound should involve B unless B = L is imposed.
minor comments (4)
- [3.3, Corollary 3.8] The stated condition K >= max{4L, sqrt(n)D/delta, R sqrt(n)D / ((R(1-sigma2)-2delta)delta)} does not imply the step-size condition (3.13) when alpha = K^{-1/3}; the correct lower bounds would be of the form K >= (4L)^3, K >= (sqrt(n)D/delta)^3, and K >= (R sqrt(n)D / ((R(1-sigma2)-2delta)delta))^3.
- [3.1, Assumption 3.4] If the intended condition in (3.5) is indeed a mean-squared Lipschitz property, it should be written as E||grad f_i(x,xi) - grad f_i(y,xi)||^2 <= Lbar^2 ||x-y||^2 (or with squared norms on both sides), and this strengthening should appear in the assumptions used by Theorems 3.7 and 3.8.
- [Title and throughout] There are typographical errors, including the title 'OPTIMIZA TION' and 'Lispchitz' in the proof of Theorem 3.6, and the figure legends in Figures 1-3 render the step size as '=0.1' without displaying the symbol alpha.
- [6, Conclusions and Limitations] The section is titled 'Conclusions and Limitations' but contains no limitations statement; the paper should either add a limitations paragraph or rename the section.
Circularity Check
No significant circularity: the O(epsilon^{-3/2}) rate is derived from explicit assumptions and parameter choices; self-citations to the authors' earlier work are technical geometry/smoothness lemmas that do not presuppose the target oracle complexity.
full rationale
The claimed O(epsilon^{-3/2}) oracle complexity in Corollary 3.8 is obtained by substituting alpha = K^{-1/3} and tau = K^{-2/3} into Theorem 3.7 and then inverting the resulting epsilon-bounds (K1 proportional to epsilon^{-3/2}, K2 proportional to epsilon^{-1}, K3 proportional to epsilon^{-3/4}). No displayed equation assumes the conclusion: Lemmas 4.3-4.5 and Theorem 3.6 are derived from Assumptions 3.1-3.4 (unbiased stochastic gradients, bounded variance, mean-squared Lipschitz stochastic gradients, mixing matrix assumptions) through standard algebraic inequalities (Lemmas A.1 and A.2). The cited results from the authors' earlier work, e.g. [12, Lemma 2] and Lemmas A.3-A.4, are parameter-free geometry and smoothness lemmas about projections onto compact submanifolds and Riemannian gradients; their stated assumptions do not include the target O(epsilon^{-3/2}) rate, so citing them is not load-bearing circularity in the sense of presupposing the main result. The numerical experiments compare against external baselines and do not fit any parameter to the claimed rate. The apparent algebraic inconsistency in Theorem 3.7 (the displayed bound omits the nu^2/(tau K) term carried from Lemma 4.5, which with alpha = K^{-1/3} and tau = K^{-2/3} contributes K^{-1/3}) is a correctness concern about whether the stated rate is actually proven, not a circularity: the derivation chain does not reduce the conclusion to its own inputs.
Assumptions & free parameters
free parameters (4)
- Step size α =
K^{-1/3}
- Momentum parameter τ =
K^{-2/3}
- Clipping constant B =
B ≥ L, e.g., 10^8 in experiments
- Experimental step-size coefficient β̂ =
Grid-searched per algorithm and dataset
assumptions (6)
- domain assumption M is an R-proximally smooth compact submanifold of Euclidean space.
- domain assumption Each local function f_i is gradient Lipschitz on conv(M) and f has a finite optimal value f* over M^n.
- domain assumption The communication graph is connected and W is doubly stochastic with second singular value σ2 in [0,1).
- domain assumption Stochastic gradients are unbiased with bounded variance, as in (3.3)-(3.4).
- ad hoc to paper The proof also needs stochastic gradients to be almost surely bounded and to satisfy a second-moment Lipschitz condition.
- standard math Standard projection and recursion lemmas from [12, 36] are valid.
Cite this review
Pith. "Pith review of Decentralized projected Riemannian stochastic recursive momentum method for nonconvex optimization." pith.science (2026). https://pith.science/paper/FRO7E45K
@misc{pith2026241202382,
author = {Pith},
title = {Pith review of: Decentralized projected Riemannian stochastic recursive momentum method for nonconvex optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/FRO7E45K}},
note = {Machine review of arXiv:2412.02382}
}
abstract
This paper studies decentralized optimization over a compact submanifold within a communication network of $n$ nodes, where each node possesses a smooth non-convex local cost function, and the goal is to jointly minimize the sum of these local costs. We focus particularly on the online setting, where local data is processed in real-time as it streams in, without the need for full data storage. We propose a decentralized projected Riemannian stochastic recursive momentum (DPRSRM) method that employs local hybrid stochastic gradient estimators and uses the network to track the global gradient. DPRSRM achieves an oracle complexity of \(\mathcal{O}(\epsilon^{-\frac{3}{2}})\), outperforming existing methods that have at most \(\mathcal{O}(\epsilon^{-2})\) complexity. Our method requires only $\mathcal{O}(1)$ gradient evaluations per iteration for each local node and does not require restarting with a large batch gradient. Furthermore, we demonstrate the effectiveness of our proposed methods compared to state-of-the-art ones through numerical experiments on principal component analysis problems and low-rank matrix completion.
Forward citations
Cited by 1 Pith paper
-
Distributed Stochastic Proximal Algorithm on Riemannian Submanifolds for Weakly-convex Functions
A retraction-based distributed stochastic proximal framework reaches consensus and a nearly stationary point at rate O((1+κ_g)/√k) for weakly-convex costs on compact embedded submanifolds.
Reference graph
Works this paper leans on
-
[1]
R. K. Ando, T. Zhang, and P. Bartlett, A framework for learning predictive structures from multiple tasks and unlabeled data , Journal of Machine Learning Research, 6 (2005), pp. 1871– 1853
work page 2005
-
[2]
M. Balashov and R. Kamalov, The gradient projection method with Armijo’s step size on man- ifolds, Computational Mathematics and Mathematical Physics, 61 (2021), pp. 1776–1786
work page 2021
-
[3]
P. Bianchi and J. Jakubowicz, Convergence of a multi-agent projected stochastic gradient al- gorithm for non-convex optimization , IEEE Transactions on Automatic Control, 58 (2012), pp. 391–405
work page 2012
-
[4]
N. Boumal and P.-A. Absil, Low-rank matrix completion via preconditioned optimization on the Grassmann manifold, Linear Algebra and its Applications, 475 (2015), pp. 200–239
work page 2015
-
[5]
H. Cardot and D. Degras, Online principal component analysis in high dimension: Which algo- rithm to choose? , International Statistical Review, 86 (2018), pp. 29–50
work page 2018
-
[6]
J. Chen, H. Ye, M. W ang, T. Huang, G. Dai, I. Tsang, and Y. Liu, Decentralized riemannian conjugate gradient method on the stiefel manifold , in The Twelfth International Conference on Learning Representations, 2024, https://openreview.net/forum?id=PQbFUMKLFp
work page 2024
-
[7]
S. Chen, A. Garcia, M. Hong, and S. Shahrampour, Decentralized Riemannian gradient de- scent on the Stiefel manifold , in International Conference on Machine Learning, PMLR, 2021, pp. 1594–1605
work page 2021
- [8]
Show all 41 references
-
[9]
F. H. Clarke, R. J. Stern, and P. R. Wolenski, Proximal smoothness and the lower-C2 property, Journal of Convex Analysis, 2 (1995), pp. 117–144
1995
-
[10]
Cutkosky and F
A. Cutkosky and F. Orabona, Momentum-based variance reduction in non-convex sgd, Advances in neural information processing systems, 32 (2019)
2019
-
[11]
Davis, D
D. Davis, D. Drusvyatskiy, and Z. Shi, Stochastic optimization over proximally smooth sets , arXiv:2002.06309, (2020)
2020 arXiv
-
[12]
Deng and J
K. Deng and J. Hu, Decentralized projected riemannian gradient method for smooth optimization on compact submanifolds , arXiv preprint arXiv:2304.08241, (2023)
2023 arXiv
-
[13]
K. Deng, J. Hu, and H. W ang, Decentralized douglas-rachford splitting methods for smooth opti- mization over compact submanifolds , arXiv preprint arXiv:2311.16399, (2023). 16 KANGKANG DENG, JIANG HU
2023 arXiv
-
[14]
K. Deng, J. Hu, and Z. Wen, Oracle complexity of augmented lagrangian methods for nonsmooth manifold optimization , arXiv preprint arXiv:2404.05121, (2024)
2024 arXiv
-
[15]
Di Lorenzo and G
P. Di Lorenzo and G. Scutari, NEXT: In-network nonconvex optimization , IEEE Transactions on Signal and Information Processing over Networks, 2 (2016), pp. 120–136
2016
-
[16]
Han and J
A. Han and J. Gao, Improved variance reduction methods for riemannian non-convex optimiza- tion, IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 (2021), pp. 7610– 7623
2021
-
[17]
Han and J
A. Han and J. Gao, Riemannian stochastic recursive momentum method for non-convex optimiza- tion, in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, Z.-H. Zhou, ed., 8 2021, pp. 2505–2511, https://doi.org/10.24963/ijcai.2021/34...
2021 doi
-
[18]
M. Hong, D. Hajinezhad, and M.-M. Zhao, Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks, in International Conference on Machine Learning, PMLR, 2017, pp. 1529–1538
2017
-
[19]
J. Hu, R. Ao, A. M.-C. So, M. Yang, and Z. Wen, Riemannian natural gradient methods, SIAM Journal on Scientific Computing, 46 (2024), pp. A204–A231
2024
-
[20]
Hu and K
J. Hu and K. Deng, Improving the communication in decentralized manifold optimization through single-step consensus and compression , arXiv preprint arXiv:2407.08904, (2024)
2024 arXiv
-
[21]
J. Hu, K. Deng, N. Li, and Q. Li, Decentralized Riemannian natural gradient methods with Kronecker-product approximations, arXiv:2303.09611, (2023)
2023 arXiv
-
[22]
Kasai, P
H. Kasai, P. Jawanpuria, and B. Mishra, Riemannian adaptive stochastic gradient algorithms on matrix manifolds , in International Conference on Machine Learning, PMLR, 2019, pp. 3262– 3271
2019
-
[23]
LeCun, The mnist database of handwritten digits, http://yann
Y. LeCun, The mnist database of handwritten digits, http://yann. lecun. com/exdb/mnist/, (1998)
1998
-
[24]
Mishra, H
B. Mishra, H. Kasai, P. Jawanpuria, and A. Saroop, A Riemannian gossip approach to subspace learning on Grassmann manifold , Machine Learning, 108 (2019), pp. 1783–1803
2019
-
[25]
Qu and N
G. Qu and N. Li, Harnessing smoothness to accelerate distributed optimization, IEEE Transactions on Control of Network Systems, 5 (2017), pp. 1245–1260
2017
-
[26]
Sarlette and R
A. Sarlette and R. Sepulchre, Consensus optimization on manifolds , SIAM Journal on Control and Optimization, 48 (2009), pp. 56–76
2009
-
[27]
Scutari and Y
G. Scutari and Y. Sun, Distributed nonconvex constrained optimization over time-varying di- graphs, Mathematical Programming, 176 (2019), pp. 497–544
2019
-
[28]
S. M. Shah , Distributed optimization on Riemannian manifolds for multi-agent networks , arXiv:1711.11196, (2017)
2017 arXiv
-
[29]
W. Shi, Q. Ling, G. Wu, and W. Yin, EXTRA: An exact first-order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, 25 (2015), pp. 944–966
2015
-
[30]
H. Sun, S. Lu, and M. Hong, Improving the sample and communication complexity for decentral- ized non-convex optimization: Joint gradient estimation and tracking , in International Confer- ence on Machine Learning, PMLR, 2020, pp. 9217–9228
2020
-
[31]
Y. Sun, S. Chen, A. Garcia, and S. Shahrampour, Global convergence of decentralized retraction- free optimization on the stiefel manifold , arXiv preprint arXiv:2405.11590, (2024)
2024 arXiv
-
[32]
Tatarenko and B
T. Tatarenko and B. Touri, Non-convex distributed optimization , IEEE Transactions on Auto- matic Control, 62 (2017), pp. 3744–3757
2017
-
[33]
H.-T. W ai, J. Lafond, A. Scaglione, and E. Moulines, Decentralized frank–wolfe algorithm for convex and nonconvex problems , IEEE Transactions on Automatic Control, 62 (2017), pp. 5522–5537
2017
-
[34]
W ang and X
L. W ang and X. Liu, Decentralized optimization over the Stiefel manifold by an approximate augmented Lagrangian function, IEEE Transactions on Signal Processing, 70 (2022), pp. 3029– 3041
2022
-
[35]
W ang and X
L. W ang and X. Liu, A variance-reduced stochastic gradient tracking algorithm for decentralized optimization with orthogonality constraints , Journal of Industrial and Management Optimiza- tion, 19 (2023), pp. 7753–7776
2023
-
[36]
J. Xu, S. Zhu, Y. C. Soh, and L. Xie, Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes , in IEEE Conference on Decision and Control, 2015, pp. 2055–2060
2015
-
[37]
Ye and T
H. Ye and T. Zhang, DeEPCA: Decentralized exact PCA with linear convergence rate, The Journal of Machine Learning Research, 22 (2021), pp. 10777–10803
2021
-
[38]
K. Yuan, B. Ying, X. Zhao, and A. H. Sayed, Exact diffusion for distributed optimization and DECENTRALIZED PROJECTED RIEMANNIAN GRADIENT METHOD 17 learning Part II: Convergence analysis , IEEE Transactions on Signal Processing, 67 (2018), pp. 724–739
2018
-
[39]
Zeng and W
J. Zeng and W. Yin, On nonconvex decentralized gradient descent , IEEE Transactions on Signal Processing, 66 (2018), pp. 2834–2848
2018
-
[40]
J. Zhao, X. W ang, and J. Lei, Distributed riemannian stochastic gradient tracking algorithm on the stiefel manifold , arXiv preprint arXiv:2405.16900, (2024)
2024 arXiv
-
[41]
Zhou, X.-T
P. Zhou, X.-T. Yuan, and J. Feng, Faster first-order methods for stochastic non-convex optimiza- tion on riemannian manifolds , in The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 138–147. 18 KANGKANG DENG, JIANG HU Appendix A. T ech...
2019
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.