Riemannian EXTRA: Communication-efficient decentralized optimization over compact submanifolds with data heterogeneity

Jiayuan Wu, Zhanwang Deng, Jiang Hu, Weijie Su, Zaiwen WenarXiv 2025 · DOI · arXiv

TL;DR

The authors introduce REXTRA, a new algorithm for decentralized optimization on Riemannian manifolds that handles data heterogeneity with half the communication cost of previous state-of-the-art methods. It is the first manifold-constrained algorithm to achieve a global sublinear convergence rate of $\mathcal{O}(1/k)$ using a constant step size and only a single round of iterate communication per iteration.

What Problem Does This Paper Address?

In decentralized optimization, a network of agents (like mobile phones or distributed sensors) tries to solve a global problem without a central server. Each agent has its own local data and objective function. Two major hurdles often arise:

  1. Manifold Constraints: Many real-world problems (like PCA or low-rank matrix completion) require solutions to lie on a specific geometric shape, such as a sphere or a set of orthogonal matrices (a Stiefel manifold). These "manifolds" are inherently non-convex and non-linear, making standard Euclidean math fail.
  2. Data Heterogeneity: If Agent A’s data is very different from Agent B’s, simple averaging techniques (like Decentralized Gradient Descent) with a constant step size will never reach the exact global solution—they just hover around it.

Existing "exact" methods solve this by "gradient tracking," but this requires agents to send twice as much data (both their current guess and a tracking direction) every single step. The authors sought a way to achieve exact convergence while communicating only the current guess.

Methods

The paper proposes REXTRA, a Riemannian extension of the well-known EXTRA algorithm used in Euclidean spaces.

  • The Innovation: Unlike gradient tracking methods that communicate two variables per iteration, REXTRA uses local historical information to correct the bias caused by data heterogeneity. This allows agents to communicate only their local variables ($x_i$), cutting communication volume by 50%.
  • Proximal Smoothness: To handle the non-convexity of the manifold, the authors leverage the concept of "proximal smoothness." This property ensures that, within a small enough neighborhood, the manifold behaves enough like a convex set that the projection operator remains well-behaved (Lipschitz continuous).
  • Algorithm Structure: In each step, agents perform a local update using a Riemannian gradient, aggregate their neighbors' guesses via a mixing matrix, and then project the result back onto the manifold to ensure feasibility.

Datasets

The authors evaluated REXTRA on two primary tasks:

  1. Decentralized Principal Component Analysis (PCA):
    • Synthetic Dataset: Randomly generated matrices with controlled singular value distributions to test convergence under varying conditions.
  2. MNIST Dataset: The classic collection of 60,000 handwritten digit images (28x28 pixels). The goal was to compute the top 5 principal components across 8 agents.
  3. Decentralized Low-Rank Matrix Completion (LRMC):
    • Synthetic Dataset: Agents collaborated to reconstruct a low-rank matrix from a subset of observed entries, modeled over a "Ring" network topology.

Key Insights and Ideas

  • Communication Efficiency is King: By adapting the EXTRA framework to manifolds, the authors proved that you don't need to track gradients explicitly to handle heterogeneous data. This is a significant "aha moment" for decentralized manifold optimization, where communication is often the primary bottleneck.
  • Stability with Constant Step Sizes: A major practical advantage of REXTRA is its support for larger, constant step sizes. Many competing algorithms require "diminishing" step sizes (which slow down over time) or become unstable if the step size is too large. REXTRA remains robust, leading to faster real-world wall-clock time.
  • Theoretical Bridge: The paper successfully bridges the gap between Euclidean primal-dual analysis and Riemannian geometry. They show that by keeping iterates within a "favorable neighborhood" (guaranteed by proximal smoothness), they can establish convergence rates that match the best-known results for much more complex algorithms.

Key Results

  • Convergence Rate: REXTRA achieves a global sublinear convergence rate of $\mathcal{O}(1/k)$, matching the theoretical "gold standard" for decentralized non-convex optimization.
  • 50% Communication Reduction: In experiments, REXTRA reached the target accuracy while communicating less than half the total number of entries compared to methods like DPRGT or DRGTA.
  • Superior Performance: On the MNIST PCA task, REXTRA not only converged faster but also supported step sizes that caused competing algorithms to diverge.
  • Network Robustness: The algorithm performed well across different network topologies (Erdos–Rényi and Ring graphs), with denser networks naturally leading to faster consensus.

Limitations and Future Work

  • Projection Costs: REXTRA relies on a projection operator ($\mathcal{P}_{\mathcal{M}}$) to stay on the manifold. For some complex manifolds, calculating this projection is computationally expensive. The authors suggest that future versions could use "retractions"—cheaper geometric approximations of projections.
  • Stochastic Settings: The current work assumes "full" gradients (using all local data at once). In very large-scale machine learning, agents usually use "stochastic" gradients (mini-batches). Extending REXTRA to the stochastic regime is a logical next step.
  • Compression: While REXTRA reduces the number of messages, it doesn't yet incorporate communication compression (like quantization or sparsification), which could further reduce the size of each message.

Summary updated

Abstract

We consider decentralized optimization over a compact Riemannian submanifold in a network of $n$ agents, where each agent holds a smooth, nonconvex local objective defined by its private data. The goal is to collaboratively minimize the sum of these local objective functions. In the presence of data heterogeneity across nodes, existing algorithms typically require communicating both local gradients and iterates to ensure exact convergence with constant step sizes. In this work, we propose REXTRA, a Riemannian extension of the EXTRA algorithm [Shi et al., SIOPT, 2015], to address this limitation. On the theoretical side, we leverage proximal smoothness to overcome the challenges of manifold nonconvexity and establish a global sublinear convergence rate of $\mathcal{O}(1/k)$, matching the best-known results. To our knowledge, REXTRA is the first algorithm to achieve a global sublinear convergence rate under a constant step size while requiring only a single round of local iterate communication per iteration. Numerical experiments show that REXTRA achieves superior performance compared to state-of-the-art methods, while supporting larger step sizes and reducing total communication by over 50\%.
BibTeX
@misc{wu2025riemannian,
  author = {Jiayuan Wu and Zhanwang Deng and Jiang Hu and Weijie Su and Zaiwen Wen},
  title = {{Riemannian EXTRA: Communication-efficient decentralized optimization over compact submanifolds with data heterogeneity}},
  year = {2025},
  eprint = {2505.15537},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.15537},
  howpublished = {arXiv},
}
Figure