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