TL;DR
This paper introduces DR-ProxGT, a novel decentralized algorithm for optimizing composite functions (smooth + nonsmooth) on Riemannian manifolds. By combining gradient tracking with a proximal gradient approach, the authors achieve a theoretical iteration complexity of $\mathcal{O}(\epsilon^{-2})$, a significant leap over the $\mathcal{O}(\epsilon^{-4})$ complexity of existing subgradient or smoothing-based methods.
What Problem Does This Paper Address?
Many modern machine learning and engineering problems—like sparse PCA, matrix completion, and dictionary learning—require optimizing functions over non-Euclidean spaces called Riemannian manifolds (e.g., the set of matrices with orthonormal columns).
The challenge is three-fold:
- Manifold Constraints: The search space is non-convex, making standard Euclidean optimization techniques inapplicable.
- Nonsmoothness: The objective often includes a "regularizer" (like the $\ell_1$-norm) to promote sparsity, which isn't differentiable.
- Decentralization: Data is often spread across multiple agents (servers or devices) that can only talk to their immediate neighbors. Agents must reach a consensus on the solution without a central coordinator.
Existing decentralized Riemannian methods typically rely on subgradients (which are slow) or smoothing techniques (which approximate the nonsmooth part but lose efficiency). This paper aims to exploit the "composite" structure of the problem to find a faster, more exact solution.
Methods
The authors propose DR-ProxGT (Decentralized Riemannian Proximal Gradient Tracking). The algorithm operates in three main steps at each iteration for every agent:
- The $S$-update (Search Direction): Instead of a simple gradient step, agents solve a proximal subproblem restricted to the tangent space of the manifold. This step handles the nonsmooth regularizer $r(X)$ while using a local estimate of the global gradient.
- The $X$-update (Variable Update): Agents perform a local update along the search direction, combine it with a consensus step (averaging with neighbors), and then use a retraction (projection) to pull the result back onto the manifold.
- The $D$-update (Gradient Tracking): This is the "secret sauce." Each agent maintains a tracker $D_i$ to estimate the average Euclidean gradient across the entire network. Crucially, the authors track the Euclidean gradient rather than the Riemannian one, which reduces the computational overhead of frequent projections.
The theoretical backbone of the paper is the construction of a merit function that combines the objective value, consensus error, and tracking error to prove that the algorithm consistently "descends" toward a stationary point.
Datasets
The algorithm was evaluated on two primary tasks using real-world data:
- MNIST: The classic handwritten digit dataset ($m=60,000$ samples, $n=784$ features) was used for Coordinate-Independent Sparse Estimation (CISE).
- Global Health Estimates (WHO): A dataset containing mortality rates across 19 age groups over 20 years from 50 European countries. This was used to test the algorithm's performance on Sparse PCA, a common task in demographic forecasting.
Key Insights and Ideas
- Complexity Breakthrough: Moving from $\mathcal{O}(\epsilon^{-4})$ to $\mathcal{O}(\epsilon^{-2})$ is a major theoretical win. In optimization terms, this means that to get twice as close to the solution, you need significantly fewer additional iterations than before.
- Euclidean Tracking on Manifolds: A common pitfall in Riemannian optimization is the high cost of geometric operations. By tracking the Euclidean gradient and only projecting when necessary, DR-ProxGT remains computationally lean.
- Exploiting Structure: By using the proximal mapping of the regularizer $r(X)$ directly rather than smoothing it, the algorithm preserves the "sharpness" of the nonsmooth term, leading to better sparsity in the results.
- Consensus via Induced Means: On a manifold, the "average" of several points isn't just their arithmetic mean. The authors utilize the concept of an induced arithmetic mean to manage consensus errors effectively.
Key Results
The authors compared DR-ProxGT against two state-of-the-art baselines: DRSM (subgradient-based) and THANOS (smoothing-based).
- Convergence Speed: In CISE tests on the MNIST dataset, DR-ProxGT reached lower stationarity violations and consensus errors much faster than competitors, exhibiting an almost linear convergence rate in practice.
- Sparsity and Accuracy: In Sparse PCA experiments, DR-ProxGT consistently achieved lower function values and higher sparsity levels. For example, at $\lambda = 0.15$, DR-ProxGT achieved a sparsity level of 64.21%, compared to roughly 33-35% for the other methods, while maintaining a lower consensus error.
- Robustness: The performance gains were consistent across different network topologies, including ring, grid, and Erdős-Rényi graphs.
Limitations and Future Work
- Compactness Requirement: The current convergence proof relies on the manifold being compact. While many common manifolds (like the Stiefel manifold) are compact, extending this to non-compact manifolds remains an open theoretical challenge.
- Consensus Steps: The theory currently assumes multiple consensus steps ($t \geq 1$) per iteration to guarantee convergence. However, numerical results showed the algorithm works excellently with just a single consensus step. The authors explicitly note that proving convergence for the $t=1$ case is a promising direction for future research.
- Communication Overhead: While iteration complexity is improved, the per-iteration communication cost (exchanging matrices) could be high for very large-scale problems. Exploring communication-compressed versions of this algorithm could be a logical next step.
Summary updated