Communication-Efficient Distributed Eigenspace Estimation
From MaRDI portal
Computational methods for problems pertaining to statistics (62-08) Factor analysis and principal components; correspondence analysis (62H25) Inference from stochastic processes and spectral analysis (62M15) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
Abstract: Distributed computing is a standard way to scale up machine learning and data science algorithms to process large amounts of data. In such settings, avoiding communication amongst machines is paramount for achieving high performance. Rather than distribute the computation of existing algorithms, a common practice for avoiding communication is to compute local solutions or parameter estimates on each machine and then combine the results; in many convex optimization problems, even simple averaging of local solutions can work well. However, these schemes do not work when the local solutions are not unique. Spectral methods are a collection of such problems, where solutions are orthonormal bases of the leading invariant subspace of an associated data matrix, which are only unique up to rotation and reflections. Here, we develop a communication-efficient distributed algorithm for computing the leading invariant subspace of a data matrix. Our algorithm uses a novel alignment scheme that minimizes the Procrustean distance between local solutions and a reference solution, and only requires a single round of communication. For the important case of principal component analysis (PCA), we show that our algorithm achieves a similar error rate to that of a centralized estimator. We present numerical experiments demonstrating the efficacy of our proposed algorithm for distributed PCA, as well as other problems where solutions exhibit rotational symmetry, such as node embeddings for graph data and spectral initialization for quadratic sensing.
Recommendations
- Distributed estimation of principal eigenspaces
- Distributed Estimation for Principal Component Analysis: An Enlarged Eigenspace Analysis
- Communication-efficient distributed covariance sketch, with application to distributed PCA
- Efficient distributed estimation of high-dimensional sparse precision matrix
- A communication-efficient and privacy-aware distributed algorithm for sparse PCA
- Communication-efficient distributed estimation for high-dimensional large-scale linear regression
- Distributed estimation of Laplacian eigenvalues via constrained consensus optimization problems
- Communication-efficient distributed multi-task learning with matrix sparsity regularization
- Communication-efficient distributed statistical inference
- Distributed solution of Laplacian eigenvalue problems
Cites work
- scientific article; zbMATH DE number 6982986 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- A dual approach for optimal algorithms in distributed optimization over networks
- Communication-efficient algorithms for statistical optimization
- Communication-efficient distributed statistical inference
- Distributed Estimation for Principal Component Analysis: An Enlarged Eigenspace Analysis
- Distributed Subgradient Methods for Multi-Agent Optimization
- Distributed estimation of principal eigenspaces
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming
- Frequent directions: simple and deterministic matrix sketching
- High-dimensional probability. An introduction with applications in data science
- High-dimensional statistics. A non-asymptotic viewpoint
- Low rank matrix recovery from rank one measurements
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- On a perturbation bound for invariant subspaces of matrices
- On the optimality of averaging in distributed statistical learning
- Optimal convergence rates for convex distributed optimization in networks
- Phase retrieval via Wirtinger flow: theory and algorithms
- Principal component analysis.
- Second order accurate distributed eigenvector computation for extremely large matrices
- Spectral algorithms
- The Byzantine generals problem
- The symmetric Procrustes problem
- Turning big data into tiny data: constant-size coresets for k-means, PCA and projective clustering
- Uniform Bounds for Invariant Subspace Perturbations
Cited in
(9)- Communication-Efficient Distributed Linear Discriminant Analysis for Binary Classification
- A communication-efficient and privacy-aware distributed algorithm for sparse PCA
- \texttt{FedPower}: privacy-preserving distributed eigenspace estimation
- Distributed Estimation for Principal Component Analysis: An Enlarged Eigenspace Analysis
- Robust covariance estimation for distributed principal component analysis
- Distributed estimation of principal eigenspaces
- Distributed Tensor Principal Component Analysis with Data Heterogeneity
- Communication-efficient distributed covariance sketch, with application to distributed PCA
- Privacy-preserving communication-efficient spectral clustering for distributed multiple networks
This page was built for publication: Communication-Efficient Distributed Eigenspace Estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5162627)
