Abstract
Decentralized optimization over compact submanifolds is a critical task in distributed machine learning and signal processing, where local datasets are distributed across a network of agents. A significant challenge in this domain is the communication bottleneck, typically addressed through consensus-building and communication compression. While existing projection-type algorithms often rely on multi-step consensus to maintain feasibility and optimality on non-convex manifolds, this paper investigates whether single-step consensus is sufficient. By leveraging the smoothness structure and asymptotic 1-Lipschitz continuity of manifold constraints, we introduce the Decentralized Projected Riemannian Gradient tracking with Communication compression (DPRGC) algorithm. Our method achieves an iteration complexity of $\mathcal{O}(\epsilon^{-1})$, matching the optimal rates found in Euclidean settings, while significantly reducing per-iteration communication costs. Numerical experiments on Principal Component Analysis (PCA) tasks demonstrate that DPRGC maintains high accuracy while cutting communication volume by over 50% compared to state-of-the-art methods.
Introduction
In decentralized optimization, a network of agents collaborates to minimize a global objective function without a central coordinator. When the optimization domain is a manifold—such as the Stiefel manifold used in PCA or orthogonal neural networks—the geometry of the space introduces unique complexities. Specifically, the standard Euclidean average of two points on a curved manifold typically lies outside the manifold.
To maintain feasibility, traditional decentralized manifold algorithms often employ "multi-step consensus," requiring agents to exchange multiple messages per gradient update to stay close to the manifold surface. This process creates a massive communication overhead. This paper addresses two pivotal questions: Can we achieve convergence with only a single communication step per iteration? And can we further reduce the load by using lossy communication compression?
The DPRGC Framework
We propose the DPRGC (Decentralized Projected Riemannian Gradient tracking with Communication compression) algorithm to solve these challenges. The framework integrates three core components:
1. Single-Step Consensus
Previously, it was an open question whether single-step consensus could support projection-type manifold algorithms. We prove that by utilizing the "proximal smoothness" of compact submanifolds, the projection operator behaves as an "asymptotically 1-Lipschitz" mapping. This theoretical insight allows us to demonstrate that if agents are initialized within a specific neighborhood, they will not drift away from the manifold even with minimal communication.
2. Gradient Tracking with Error Compensation
To handle the heterogeneity of local data across agents, we employ gradient tracking. However, simply compressing the tracked gradients can introduce noise that prevents convergence to an exact solution. DPRGC utilizes an error-compensated compression strategy, where the differences between iterations are compressed rather than the raw variables. This ensures that the compression error vanishes as the algorithm approaches a stationary point.
3. Projection and Retraction
The algorithm remains computationally efficient by using standard manifold tools—projections or retractions—to map iterates back to the manifold surface, ensuring feasibility throughout the optimization process.
Theoretical Contributions
Our analysis establishes that DPRGC achieves an iteration complexity of $\mathcal{O}(\epsilon^{-1})$ to find an $\epsilon$-stationary point. This is a significant result because it matches the best-known complexity for decentralized optimization in standard Euclidean space, implying that the manifold constraint does not impose a theoretical performance penalty. Furthermore, we prove that the iterates converge linearly to a consensus set, ensuring that agents quickly reach an agreement on the solution even while global optimization is ongoing.
Experimental Validation
We evaluated DPRGC against state-of-the-art methods like DPRGT (uncompressed) and DRGTA (Decentralized Riemannian Gradient Tracking Algorithm) across two primary benchmarks:
- Synthetic PCA: Tested on various network topologies, including Erdos-Renyi and Ring networks. The results showed that DPRGC is robust to network sparsity, maintaining stability even on low-connectivity graphs.
- MNIST Dataset: We performed decentralized PCA on the MNIST dataset ($d=784, r=5$) distributed across 8 agents.
In both scenarios, DPRGC achieved the same level of accuracy as uncompressed methods while transmitting 50% or less of the total data. This demonstrates a clear advantage in communication-constrained environments.
Conclusion and Future Work
DPRGC provides a rigorous and efficient solution for decentralized manifold optimization. By proving the sufficiency of single-step consensus and integrating error-compensated compression, we significantly lower the barrier for distributed tasks on non-convex surfaces.
While our current theory focuses on compact submanifolds (like Stiefel or oblique manifolds), future research could extend these insights to non-compact manifolds. Additionally, exploring stochastic gradient variants would further enhance the algorithm's applicability to large-scale deep learning tasks.
Summary updated