Decentralized Projected Riemannian Stochastic Recursive Momentum Method for Nonconvex Optimization

Kangkang Deng, Jiang Hu

Introduction

Decentralized optimization has emerged as a critical paradigm for large-scale machine learning, enabling multiple nodes to collaboratively solve global problems without centralizing raw data. This is particularly vital in sensor networks and privacy-sensitive applications. However, many practical problems, such as principal component analysis (PCA) and low-rank matrix completion, involve constraints that require solutions to lie on specific geometric structures known as manifolds.

Optimizing non-convex functions over manifolds in a decentralized, online setting presents significant challenges. Nodes must maintain consensus while satisfying non-convex manifold constraints, all while processing a continuous stream of noisy, stochastic data. Existing methods often suffer from slow convergence rates ($O(\epsilon^{-2})$) or require computationally expensive periodic full-gradient computations. This paper introduces DPRSRM (Decentralized Projected Riemannian Stochastic Recursive Momentum), a single-loop algorithm that achieves a state-of-the-art oracle complexity of $O(\epsilon^{-3/2})$.

The DPRSRM Algorithm

The proposed DPRSRM method integrates three core techniques to overcome the limitations of previous approaches:

  1. Gradient Tracking: To ensure nodes move toward the global optimum despite only seeing local data, each node maintains an estimate of the global gradient by communicating with its immediate neighbors.
  2. Recursive Momentum (Variance Reduction): Inspired by Euclidean variance-reduction techniques like SARAH, DPRSRM employs a hybrid stochastic gradient estimator. By combining current noisy gradients with previous estimates, it effectively "cancels out" noise over time, allowing for constant step sizes and faster convergence without large minibatches.
  3. Projection-Based Consensus: Rather than using computationally intensive Riemannian retractions, the algorithm utilizes a simple projection operator to keep iterates on the manifold. The authors demonstrate that a single communication step per iteration is sufficient to maintain consensus and ensure convergence.

Experimental Evaluation

The researchers evaluated DPRSRM against standard baselines, including Decentralized Riemannian SGD (DRSGD) and Decentralized Projected Riemannian Gradient Descent (DPRGD), using synthetic PCA datasets and the MNIST handwritten digit dataset.

Comparison of DPRSRM against baselines across consensus error, optimality gap, gradient norm, and distance to optimum.

As shown in the experimental results, DPRSRM consistently outperforms existing methods. It reaches lower optimality errors and achieves consensus significantly faster. The momentum-based variance reduction is particularly effective at suppressing the noise inherent in stochastic gradients, which typically disrupts consensus in traditional SGD-based decentralized methods.

Key Insights and Theoretical Contributions

The primary contribution of this work is the theoretical leap in efficiency for decentralized Riemannian optimization. By successfully porting momentum-based variance reduction to the manifold setting, the authors improved the oracle complexity from $O(\epsilon^{-2})$ to $O(\epsilon^{-3/2})$, matching the best-known rates for centralized Euclidean methods.

Consensus error performance of the algorithm across different network topologies, including Ring and Erdos-Renyi (ER) graphs.

Furthermore, the algorithm's "single-loop" nature makes it highly efficient, requiring only one gradient evaluation and one communication step per iteration. The study also highlights the geometric robustness of the approach; the proximal smoothness of compact submanifolds allows for stable consensus even on sparse network topologies like Ring graphs, as illustrated in the consensus error analysis across different graph types.

Conclusion and Future Work

DPRSRM represents a significant advancement in online decentralized optimization on manifolds. By achieving $O(\epsilon^{-3/2})$ complexity with a single-loop structure, it provides a practical and theoretically grounded solution for complex constrained problems.

Future research directions include extending the theoretical framework to non-compact manifolds, such as the space of positive definite matrices, and developing versions of the algorithm that are more communication-efficient for high-latency network environments. Additionally, handling non-smooth objectives remains an important open challenge in this domain.

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 O(epsilon^(-3/2)), outperforming existing methods that have at most O(epsilon^(-2)) complexity. Our method requires only 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