Federated Principal Component Analysis

Abstract

We present a federated, asynchronous, and $(\epsilon ,\delta )$-differentially private algorithm for PCA in the memory-limited setting. Our algorithm incrementally computes local model updates using a streaming procedure and adaptively estimates its $r$ leading principal components when only $\mathcal{O}(dr)$ memory is available with $d$ being the dimensionality of the data. We guarantee differential privacy via an input-perturbation scheme in which the covariance matrix of a dataset $\mathbf{X}\in {\mathbb{R}}^{d\times n}$ is perturbed with a non-symmetric random Gaussian matrix with variance in $\mathcal{O}\left({\left(\frac{d}{n}\right)}^2\log d\right)$, thus improving upon the state-of-the-art. Furthermore, contrary to previous federated or distributed algorithms for PCA, our algorithm is also invariant to permutations in the incoming data, which provides robustness against straggler or failed nodes. Numerical simulations show that, while using limited-memory, our algorithm exhibits performance that closely matches or outperforms traditional non-federated algorithms, and in the absence of communication latency, it exhibits attractive horizontal scalability.

arXiv comment36 pages, 13 figures, 1 table. Accepted for publication at Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada

References in corpus (12)

• UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Differentially Private Federated Learning: A Client Level Perspective
• The Noisy Power Method: A Meta Algorithm with Applications
• Beating Randomized Response on Incoherent Matrices
• Improved Distributed Principal Component Analysis
• Memory Limited, Streaming PCA
• A Distributed and Incremental SVD Algorithm for Agglomerative Data Analysis on Large Networks
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• Robust Frequent Directions with Application in Online Learning

Cited by in corpus (8)

• Federated PCA on Grassmann Manifold for IoT Anomaly Detection
• FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Privacy Preserving PCA for Multiparty Modeling
• Communication-Efficient Distributed SVD via Local Power Iterations
• Analog MIMO Communication for One-shot Distributed Principal Component Analysis
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• Pronto: Federated Task Scheduling