Decentralized projected Riemannian stochastic recursive momentum method for nonconvex optimization

Kangkang Deng, Jiang Hu

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^{-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.

Introduction

Modern machine learning often relies on decentralized systems where data is distributed across various sensors or servers. A critical challenge in this domain is optimizing functions over Riemannian manifold constraints, such as spheres or Stiefel manifolds (sets of orthogonal matrices). These constraints are common in tasks like Principal Component Analysis (PCA) and deep learning with batch normalization.

Standard optimization tools typically assume a flat Euclidean space. When combined with decentralized communication and noisy "online" data streams, the geometric constraints of a manifold significantly complicate the optimization process. Existing algorithms were relatively slow, requiring $\mathcal{O}(\epsilon^{-2})$ samples to reach a desired accuracy. The challenge addressed in this work is achieving higher accuracy faster, without the need for massive data restarts or large batch sizes.

The DPRSRM Method

The authors introduce the Decentralized Projected Riemannian Stochastic Recursive Momentum (DPRSRM) method. This approach integrates three core components to overcome the limitations of previous methods:

  1. Gradient Tracking: Nodes communicate to maintain an estimate of the global gradient, allowing the network to stay synchronized despite only having local information.
  2. Stochastic Recursive Momentum (SRM): This variance-reduction technique maintains a momentum term that incorporates historical gradient data. This reduces noise in streaming data without the computational overhead of large batches.
  3. Projection-Based Consensus: To ensure all nodes agree on a single solution while remaining on the manifold, the algorithm utilizes a projection operator, which is often more robust than traditional "retractions."

Crucially, DPRSRM is a single-loop algorithm. It avoids the periodic "full gradient" calculations required by many other variance-reduced methods, making it ideal for true online learning where data cannot be stored.

Performance and Complexity

The headline result of this research is the improvement in oracle complexity. By moving from $\mathcal{O}(\epsilon^{-2})$ to $\mathcal{O}(\epsilon^{-3/2})$, DPRSRM requires significantly fewer data samples to reach high precision.

Comparison of DPRSRM with state-of-the-art decentralized Riemannian methods.

As shown in the table above, DPRSRM is the first method to combine gradient tracking and variance reduction (VR) in a single-loop framework for compact submanifolds, achieving superior theoretical complexity compared to existing literature.

Experimental Validation

The method was evaluated on three primary benchmarks:

  • Synthetic PCA: Testing performance across different network topologies like Ring and Erdos-Renyi graphs.
  • MNIST Dataset: Performing decentralized PCA to reduce 784-dimensional images to 5 principal components.
  • Low-Rank Matrix Completion (LRMC): Reconstructing large, partially observed matrices.

In all tests, DPRSRM converged faster and achieved lower error levels than existing state-of-the-art methods like DRSGD and DRPGD, demonstrating robustness to various network structures.

Conclusion

DPRSRM provides a significant advancement in decentralized manifold optimization by breaking the $\mathcal{O}(\epsilon^{-2})$ complexity barrier. While the current theory focuses on compact submanifolds, its efficiency and single-loop nature make it highly practical for real-world online learning applications. Future research may focus on extending these results to non-compact manifolds and improving communication efficiency.

Summary updated

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}(ε^{-\frac{3}{2}})\), outperforming existing methods that have at most \(\mathcal{O}(ε^{-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.
BibTeX
@inproceedings{deng2025decentralized,
  author = {Kangkang Deng and Jiang Hu},
  title = {{Decentralized projected Riemannian stochastic recursive momentum method for nonconvex optimization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i11.33218},
}
Figure