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:
- 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.
- 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.
- 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.
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.
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