Riemannian Momentum Tracking: Distributed Optimization with Momentum on Compact Submanifolds

Jun Chen, Tianyi Zhu, H. Ye, Lina Liu, Guang Dai, Yong Liu, Yizhang Jiang, Ivor W. TsangIEEE Transactions on Control of Network Systems 2026 · DOI

TL;DR

This paper introduces "Riemannian Momentum Tracking" (RMTracking), a novel decentralized optimization algorithm designed for problems with constraints on compact submanifolds (like orthogonal matrices). RMTracking effectively combines gradient tracking with momentum to achieve faster convergence than existing methods, particularly when using small step sizes.

What Problem Does This Paper Address?

Many real-world machine learning and signal processing tasks involve optimizing functions where the variables are constrained to lie on specific geometric shapes, known as manifolds. These manifolds, like the Stiefel manifold (used for orthogonal matrices), are often non-convex, making standard optimization techniques challenging. Furthermore, when these tasks involve multiple agents (e.g., in a distributed system) where data is spread out, a decentralized approach is needed. While gradient descent with momentum is a well-established technique for speeding up optimization in unconstrained settings, its application to distributed optimization problems on Riemannian manifolds has been limited. Existing methods often struggle with the geometric constraints of these manifolds, leading to slower convergence or requiring complex steps. This paper aims to bridge this gap by developing a momentum-based distributed optimization algorithm that respects the geometry of compact submanifolds.

Methods

The core contribution is the Riemannian Momentum Tracking (RMTracking) algorithm. It builds upon existing gradient tracking techniques, which allow distributed agents to collectively estimate the global gradient without a central server. The novelty lies in the integration of a momentum term into this framework, specifically adapted for Riemannian manifolds.

Key aspects of the method include:

  • Riemannian Geometry: The algorithm operates on compact submanifolds, meaning updates must respect the manifold's curvature. This is handled using projection operators (like $P_M$) and tangent space projections to ensure updates stay within the manifold.
  • Gradient Tracking: Agents use a communication protocol (defined by a graph's adjacency matrix $W$) to track the average of local gradients, effectively achieving consensus on the gradient information.
  • Momentum: A momentum term ($\beta$) is incorporated to accelerate convergence. Unlike some prior work that applied momentum after gradient tracking, RMTracking strategically reorders these steps to mitigate potential biases and improve efficiency.
  • Lipschitz Continuity: The paper establishes Lipschitz-type inequalities for the momentum term on compact submanifolds, which is crucial for the theoretical analysis of convergence.

The paper also briefly discusses a related algorithm, Distributed Riemannian Gradient Tracking with Momentum (DRGTM), but focuses its theoretical analysis on RMTracking due to its improved structure.

Datasets

The paper does not introduce new datasets. Instead, it uses synthetic data generated for an eigenvalue problem to evaluate the performance of the proposed RMTracking algorithm against existing methods. The synthetic data is generated based on a standard multi-variate Gaussian distribution, with specific parameters for the number of agents ($n$), sample sizes ($m_i$), matrix dimensions ($d$), and manifold rank ($r$).

Key Insights and Ideas

  • Momentum on Manifolds is Tricky: Simply applying Euclidean momentum techniques to Riemannian manifolds doesn't work due to the geometric constraints. The paper shows how to adapt momentum to respect these constraints.
  • Order Matters: The sequence in which gradient tracking and momentum are applied significantly impacts performance. RMTracking's approach of integrating momentum before the final manifold projection appears to be more effective than applying it afterwards.
  • Faster Convergence with Momentum: The theoretical analysis and numerical results strongly suggest that incorporating momentum, even on compact submanifolds, can lead to substantial speedups in convergence.
  • Small Step-Size Advantage: The convergence rate of RMTracking becomes particularly impressive when a small step-size is used, achieving a rate that is $\frac{1}{1-\beta}$ times faster than other related algorithms. This suggests a trade-off between step-size and convergence speed that RMTracking leverages effectively.

Key Results

The paper presents both theoretical convergence guarantees and empirical validation:

  • Theoretical Convergence: RMTracking achieves an $\mathcal{O}(\frac{1-\beta}{K})$ convergence rate for the Riemannian gradient average with a constant step-size, where $K$ is the number of iterations and $\beta$ is the momentum weight. Crucially, when the step-size is sufficiently small, it achieves an $\mathcal{O}(\frac{1-\beta}{K})$ convergence rate to an $\epsilon$-stationary point.
  • Speedup: The authors claim RMTracking is the first decentralized algorithm to achieve exact convergence that is $\frac{1}{1-\beta}$ times faster than other related algorithms, especially when the step-size is small.
  • Numerical Experiments: Figures 1 and 2 demonstrate that RMTracking consistently outperforms existing methods (DRGTA and DPRGT) in terms of convergence speed across various momentum weights and step-sizes. The plots show that RMTracking reaches lower error levels in fewer iterations. For instance, Figure 2 shows RMTracking requiring significantly fewer iterations than DRGTA/DPRGT to reach a similar level of accuracy, especially with larger step-sizes.

Limitations and Future Work

  • Neighborhood Restriction: The theoretical analysis of RMTracking is restricted to agents operating within a specific neighborhood of the manifold. The paper acknowledges that extending this to global convergence without such restrictions would be a valuable future direction.
  • Parameter Tuning: While the convergence rate depends on parameters like $\alpha$ (step-size) and $\beta$ (momentum), the paper's theoretical improvements are constrained by these parameters. Future work could explore adaptive strategies for these parameters to further enhance performance.
  • Broader Applications: The current work focuses on eigenvalue problems. Investigating the applicability and performance of RMTracking on a wider range of distributed optimization problems on compact submanifolds would be beneficial.
  • Acceleration Mechanisms: The authors explicitly state their future plan to investigate further acceleration mechanisms for distributed Riemannian optimization to achieve even better convergence rates.

Summary updated

Abstract

Gradient descent with momentum has been widely applied in various signal processing and machine learning tasks, demonstrating a notable empirical advantage over standard gradient descent. However, momentum-based distributed Riemannian algorithms have been only scarcely explored. In this paper, we propose Riemannian Momentum Tracking (RMTracking), a decentralized optimization algorithm with momentum over a compact submanifold. Given the non-convex nature of compact submanifolds, the objective function, composed of a finite sum of smooth (possibly non-convex) local functions, is minimized across agents in an undirected and connected network graph. With a constant step-size, we establish an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\frac{1-\beta }{K})$</tex-math></inline-formula> convergence rate of the Riemannian gradient average for any momentum weight <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\beta \in [0,1)$</tex-math></inline-formula>. Especially, RMTracking can achieve a convergence rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\frac{1-\beta }{K})$</tex-math></inline-formula> to a stationary point when the step-size is sufficiently small. To best of our knowledge, RMTracking is the first decentralized algorithm to achieve exact convergence that is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\frac{1}{1-\beta }$</tex-math></inline-formula> times faster than other related algorithms. Finally, we verify these theoretical claims through numerical experiments on eigenvalue problems.
BibTeX
@article{chen2026riemannian,
  author = {Jun Chen and Tianyi Zhu and H. Ye and Lina Liu and Guang Dai and Yong Liu and Yizhang Jiang and Ivor W. Tsang},
  title = {{Riemannian Momentum Tracking: Distributed Optimization with Momentum on Compact Submanifolds}},
  journal = {IEEE Transactions on Control of Network Systems},
  year = {2026},
  doi = {10.1109/tcns.2026.3667761},
}
Figure