FedFask: Fast Sketching Distributed PCA for Large-Scale Federated Data
Lists
Only you see this
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.
BibTeX
@article{zhou2025fedfask,
author = {Xingcai Zhou and Guang Yang and Haotian Zheng and Linglong Kong and Jinde Cao},
title = {{FedFask: Fast Sketching Distributed PCA for Large-Scale Federated Data}},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = {2025},
doi = {10.1109/tpami.2025.3639635},
}Loading related content...