Communication-Efficient Distributed SVD via Local Power Iterations

Xiang Li, Shusen Wang, Kun Chen, Zhihua Zhang

TL;DR

LocalPower is a communication-efficient distributed algorithm for truncated Singular Value Decomposition (SVD) that performs multiple local power iterations between global synchronizations. By using Orthogonal Procrustes Transformation (OPT) to align local subspaces and a decaying communication interval, it achieves significantly faster convergence and higher precision than standard distributed methods.

What Problem Does This Paper Address?

Truncated SVD is a cornerstone of machine learning, used for everything from dimensionality reduction to matrix completion. However, as datasets grow, they no longer fit on a single machine, necessitating distributed computing.

The standard approach, Distributed Power Iteration (DPI), requires worker nodes to communicate with a central server after every single iteration. In large-scale systems, the time spent on communication and waiting for "stragglers" (slow nodes) often outweighs the actual computation time. This leads to "anti-scaling," where adding more machines actually makes the process slower. The challenge is to reduce communication frequency without losing the accuracy of the final solution.

Overview of standard Distributed Power Iteration (DPI)

Methods

The authors introduce LocalPower, an algorithm inspired by the Federated Averaging (FedAvg) technique commonly used in deep learning. Instead of synchronizing every step, each worker node performs $p$ local power iterations using its own portion of the data before sending its results to the server for aggregation.

Key technical innovations include:

  • Orthogonal Procrustes Transformation (OPT): Simply averaging local eigenvector matrices doesn't work well because different nodes might find different orthonormal bases for the same subspace. OPT aligns these local matrices before they are averaged, ensuring stability.
  • Sign-Fixing: Since OPT can be computationally expensive ($O(dk^2)$), the authors propose "sign-fixing" as a faster surrogate. It generalizes a technique previously only used for $k=1$ to higher dimensions, simply flipping the signs of columns to align them.
  • Decaying $p$ Strategy: The authors observed that while a large $p$ (many local steps) leads to fast initial progress, it eventually hits an error floor. By gradually decreasing $p$ over time until it reaches 1, LocalPower can achieve the high precision of standard DPI with far fewer total communications.

Datasets

The algorithm was evaluated on 15 datasets from the LIBSVM repository, including A9a, Abalone, Acoustic, Combined, Connect-4, Covtype, and MSD. The data was randomly partitioned among $m$ nodes, with each node typically holding 1,000 samples.

Key Insights and Ideas

  • The Stability Gap: A "naive" implementation of local power iterations is unstable and can even diverge. This is because local updates can cause the signs or rotations of the estimated singular vectors to "flip" or drift apart across different nodes.
  • OPT as a Stabilizer: Theoretical analysis shows that using OPT makes the residual error independent of the number of local iterations $p$. Without it, the error grows exponentially with $p$.
  • Precision vs. Communication Trade-off: There is a fundamental trade-off where more local updates ($p > 1$) speed up the start but prevent perfect convergence. The "decaying $p$" strategy resolves this, providing the benefits of both fast initial progress and high final precision.
  • Local Data Size Matters: The algorithm performs better when each node has a larger local sample size (smaller $m$), as the local matrices better approximate the global data matrix.

Key Results

  • Communication Efficiency: LocalPower can reach a constant accuracy with $p$ times fewer communications than standard DPI.
  • Superior Accuracy: On 12 out of 15 datasets, LocalPower variants achieved the smallest mean error and standard deviation compared to baselines like one-shot SVD or other distributed averaging methods.
  • Stability: As shown in the experiments, the vanilla version of the algorithm often fluctuates or diverges, while OPT and sign-fixing provide smooth, stable convergence curves.
Convergence and stability of LocalPower variants

Limitations and Future Work

  • Theoretical Assumptions: The current convergence proof relies on an assumption that local approximation errors are uniformly small, which might be stringent in highly heterogeneous data environments.
  • Future Extensions: The authors suggest that LocalPower could be extended to decentralized settings (where there is no central server) or streaming settings where data arrives continuously.
  • Sketching: Combining LocalPower with matrix sketching techniques could further reduce the size of the data being communicated, pushing efficiency even further.

Summary updated

Abstract

We study distributed computing of the truncated singular value decomposition (SVD). We develop an algorithm that we call \texttt{LocalPower} for improving communication efficiency. Specifically, we...
BibTeX
@inproceedings{li2021communication,
  author = {Xiang Li and Shusen Wang and Kun Chen and Zhihua Zhang},
  title = {{Communication-Efficient Distributed SVD via Local Power Iterations}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=b_crsKt2Ch},
}
Figure