Abstract
We study distributed computing of the truncated singular value decomposition problem. We develop an algorithm that we call LocalPower for improving communication efficiency. Specifically, we uniformly partition the dataset among $m$ nodes and alternate between multiple (precisely $p$) local power iterations and one global aggregation. In the aggregation, we propose to weight each local eigenvector matrix with orthogonal Procrustes transformation (OPT). As a practical surrogate of OPT, sign-fixing, which uses a diagonal matrix with $\pm 1$ entries as weights, has better computation complexity and stability in experiments. We theoretically show that under certain assumptions LocalPower lowers the required number of communications by a factor of $p$ to reach a constant accuracy. We also show that the strategy of periodically decaying $p$ helps obtain high-precision solutions. We conduct experiments to demonstrate the effectiveness of LocalPower.
Introduction
Singular Value Decomposition (SVD) is a cornerstone of machine learning, essential for dimensionality reduction, matrix completion, and latent factor analysis. However, as datasets grow to massive scales, they often exceed the memory capacity of a single machine, necessitating distributed computation. Standard distributed power iteration (DPI) algorithms suffer from a significant communication bottleneck: worker nodes must synchronize with a central server after every single matrix multiplication. In large-scale systems, the time spent on network communication and handling straggler nodes often outweighs the actual computation time. This paper introduces LocalPower, a method designed to reduce communication frequency by allowing nodes to perform multiple local updates before synchronizing.
Methods: The LocalPower Algorithm
LocalPower is inspired by local-update strategies common in Federated Learning, such as FedAvg. Instead of a single local step per synchronization, each of the $m$ worker nodes performs $p$ local power iterations on its subset of the data matrix $\mathbf{A}$.
A primary technical challenge in this approach is that local eigenvector estimates can "drift" or experience sign flips, rendering simple averaging ineffective. To address this, we propose two alignment techniques for the global aggregation step:
- Orthogonal Procrustes Transformation (OPT): Finds the optimal rotation to align local eigenvector matrices with a reference matrix.
- Sign-Fixing: A computationally efficient surrogate for OPT that adjusts the signs of columns to ensure consistency across nodes.
Additionally, we introduce a decaying $p$ strategy. While a large $p$ (many local steps) facilitates rapid initial error reduction, it can eventually lead to an error floor. By gradually reducing $p$ to 1 over time, the algorithm achieves the best of both worlds: fast initial progress and high-precision convergence.
Experimental Results
We evaluated LocalPower on 15 diverse datasets from the LIBSVM repository, including A9a, Covtype, and the Million Song Dataset (MSD). These datasets vary in sample size ($n$) and feature count ($d$), providing a robust test of the algorithm's scalability and performance.
Key Findings
- Communication Efficiency: LocalPower significantly reduces the number of communication rounds required to reach a target accuracy. Theoretically and empirically, the communication cost is reduced by a factor of approximately $p$.
- Stability and Alignment: The use of OPT or sign-fixing is crucial for stability. As shown in the experiments, vanilla local power (without alignment) often fluctuates or hits a high error floor, whereas alignment strategies ensure smooth convergence.
- High Precision: By employing the decaying $p$ strategy, LocalPower can achieve high-precision solutions (errors as low as $10^{-14}$) while maintaining a low communication footprint in the early stages of training.
Conclusion and Future Work
LocalPower offers a communication-efficient framework for distributed SVD, bridging the gap between local computation and global convergence. While highly effective in server-client architectures, future work will explore its application in decentralized peer-to-peer networks, streaming data environments, and integration with matrix sketching techniques to further minimize data transmission costs.
Summary updated