Improving the communication in decentralized manifold optimization through single-step consensus and compression

Jiang Hu, Kangkang DengarXiv 2024 · DOI · arXiv

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

Abstract

We are concerned with decentralized optimization over a compact submanifold, where the loss functions of local datasets are defined by their respective local datasets. A key challenge in decentralized optimization is mitigating the communication bottleneck, which primarily involves two strategies: achieving consensus and applying communication compression. Existing projection/retraction-type algorithms rely on multi-step consensus to attain both consensus and optimality. Due to the nonconvex nature of the manifold constraint, it remains an open question whether the requirement for multi-step consensus can be reduced to single-step consensus. We address this question by carefully elaborating on the smoothness structure and the asymptotic 1-Lipschitz continuity associated with the manifold constraint. Furthermore, we integrate these insights with a communication compression strategy to propose a communication-efficient gradient algorithm for decentralized manifold optimization problems, significantly reducing per-iteration communication costs. Additionally, we establish an iteration complexity of $\mathcal{O}(ε^{-1})$ to find an $ε$-stationary point, which matches the complexity in the Euclidean setting. Numerical experiments demonstrate the efficiency of the proposed method in comparison to state-of-the-art approaches.
BibTeX
@misc{hu2024improving,
  author = {Jiang Hu and Kangkang Deng},
  title = {{Improving the communication in decentralized manifold optimization through single-step consensus and compression}},
  year = {2024},
  eprint = {2407.08904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.08904},
}
Figure