Communication-Efficient Distributed SVD via Local Power Iterations

Abstract

We study distributed computing of the truncated singular value decomposition problem. We develop an algorithm that we call \texttt{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 \texttt{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 \texttt{LocalPower}.

arXiv comment9 pages, 7 figures, accepted by 2021 ICML

References in corpus (19)

• Communication-Efficient Learning of Deep Networks from Decentralized Data
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Local SGD Converges Fast and Communicates Little
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Optimal Client Sampling for Federated Learning
• The Noisy Power Method: A Meta Algorithm with Applications
• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• First Analysis of Local GD on Heterogeneous Data
• Improved Distributed Principal Component Analysis
• Stochastic Optimization of PCA with Capped MSG
• Fast and Simple PCA via Convex Optimization
• Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGD
• Federated Principal Component Analysis
• SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation

Cited by in corpus (1)

• FedPower: Privacy-Preserving Distributed Eigenspace Estimation