FedFask: Fast Sketching Distributed PCA for Large-Scale Federated Data.

Abstract

We study distributed principal component analysis (PCA) for large-scale federated data when the sample size $n$n and dimension $d$d are both ultra-large. This type of data is currently very common, but faces numerous challenges in PCA learning, such as communication overhead and computational complexity. We develop a new algorithm ${\mathsf {FedFask}}$FedFask (Fast Sketching for Federated learning) with lower communication cost $O(dr)$O(dr) and lower computational complexity $O(d(np/m+p^{2}+r^{2}))$O(d(np/m+p2+r2)), where $m$m is the number of workers, $r$r is the rank of matrix, $p$p is the dimension of sketched column space, and $r\leq p\ll d$r≤p≪d. In ${\mathsf {FedFask}}$FedFask, we adopt and develop technologies such as fast sketching, alignments with orthogonal Procrustes Fixing, and matrix Stiefel manifold via Kolmogorov-Nagumo-type average. Thus, ${\mathsf {FedFask}}$FedFask has a higher accuracy, lower stochastic variation, and best representation of multiple randomly projected eigenspaces, and avoids the orthogonal ambiguity of eigenspaces. We show that ${\mathsf {FedFask}}$FedFask achieves the same rate of learning $O\left(\frac{\kappa _{r}r}{\lambda _{r}}\sqrt{\frac{r^{*}}{n}}\right)$Oκrrλrr*n as the centralized PCA uses all data, and tolerates more workers to parallel acceleration computation. We conduct extensive experiments to demonstrate the effectiveness of ${\mathsf {FedFask}}$FedFask.