Abstract
In this paper, we focus on subspace learning problems on the Grassmann manifold. Interesting applications in this setting include low-rank matrix completion and low-dimensional multivariate regression, among others. Motivated by privacy concerns, we aim to solve such problems in a decentralized setting where multiple agents have access to (and solve) only a part of the whole optimization problem. The agents communicate with each other to arrive at a consensus, i.e., agree on a common quantity, via the gossip protocol. We propose a novel cost function for subspace learning on the Grassmann manifold, which is a weighted sum of several sub-problems (each solved by an agent) and the communication cost among the agents. The cost function has a finite sum structure. In the proposed modeling approach, different agents learn individual local subspace but they achieve asymptotic consensus on the global learned subspace. The approach is scalable and parallelizable. Numerical experiments show the efficacy of the proposed decentralized algorithms on various matrix completion and multivariate regression benchmarks.
Introduction
Subspace learning—identifying low-dimensional structures within high-dimensional data—is a fundamental task in machine learning, powering applications from recommendation systems to multi-task regression. Traditionally, these problems are solved in a centralized manner, requiring all data to be aggregated on a single server. However, real-world data is often distributed across various locations, and privacy concerns frequently prohibit the sharing of raw data.
This paper addresses the challenge of enabling multiple independent agents to converge on a shared global subspace without a central coordinator and without exposing their private datasets. We propose a framework that leverages the natural geometry of subspaces—the Grassmann manifold—combined with a communication-efficient gossip protocol.
Methodology
The Grassmann Manifold and Riemannian Optimization
Rather than treating subspaces as flat matrices in Euclidean space, we model the set of all $r$-dimensional subspaces in $\mathbb{R}^m$ as a Grassmann manifold, $Gr(r, m)$. This geometric perspective allows the use of specialized Riemannian optimization tools, which are inherently more stable and accurate for subspace-related tasks than standard Euclidean methods.
Riemannian Gossip Protocol
To minimize communication overhead, we employ a gossip protocol. Instead of broadcasting updates to the entire network, a randomly selected agent communicates with only one neighbor at each time step. They exchange their current subspace estimates and move toward a consensus.
Cost Function and Stochastic Gradient Gossip
We define a global objective function as a weighted sum of local task-specific losses and a consensus term representing the Riemannian distance between neighboring agents' subspaces. We derive a stochastic gradient descent (SGD) algorithm that operates directly on the manifold. Key technical variants include:
- Preconditioning: Designed to handle ill-conditioned data where noise levels vary across dimensions.
- Parallelization: A "red-black" ordering strategy that enables multiple pairs of agents to update simultaneously without interference.
Experimental Evaluation
The proposed approach was evaluated across several standard benchmarks:
- Synthetic Data: Used for controlled testing of noise and ill-conditioning.
- Matrix Completion: Evaluated on the Netflix Prize (100 million ratings) and MovieLens-10M datasets.
- Multi-task Regression: Tested on the Parkinsons dataset (predicting symptom scores for 42 patients) and the School dataset (exam score predictions across 139 schools).
Key Insights
- Geometric Efficiency: Utilizing Riemannian distance for consensus is significantly more effective than Euclidean distance. Exploiting the manifold's curvature leads to faster and more reliable convergence.
- Soft Consensus: The framework uses "soft" consensus, allowing agents to balance local task optimization with neighbor alignment, providing robustness and flexibility.
- Privacy Preservation: Agents share only their current basis vectors (subspace estimates) rather than raw data points, providing an inherent layer of abstraction and privacy for the underlying data.
Results
Numerical experiments demonstrate that the decentralized Stochastic Gossip algorithm achieves Root Mean Square Error (RMSE) scores nearly identical to state-of-the-art centralized batch algorithms (e.g., RTRMC) on the Netflix and MovieLens datasets. Furthermore, it significantly outperforms existing decentralized methods like D-LMaFit in terms of convergence speed and accuracy. The approach also scales effectively, maintaining performance as the number of agents increases (tested up to $N=20$).
Conclusion and Future Work
This work presents a scalable, parallelizable framework for decentralized subspace learning on the Grassmann manifold. Future research will focus on relaxing the "universal clock" assumption for learning rates, exploring more complex and dynamic network topologies, and implementing decoupled learning rates to better handle heterogeneous data distributions across agents.
Summary updated