FedFask：一种用于大规模联邦数据的快速分布式PCA算法

《IEEE Transactions on Pattern Analysis and Machine Intelligence》：FedFask: Fast Sketching Distributed PCA for Large-Scale Federated Data

大规模联邦数据中分布式主成分分析研究，提出FedFask算法通过快速sketching、正交投影修正和Stiefel流形技术，降低通信复杂度至O(d)和计算复杂度至O(d(np/m + p + r2))，支持更多计算节点并行加速，实验验证其精度高、方差小且能有效表征多维投影特征空间。

　　

摘要：

我们研究了在大规模联邦数据下的分布式主成分分析（PCA），其中样本量n和维度d都极大。这类数据目前非常常见，但在PCA学习过程中面临许多挑战，如通信开销和计算复杂性。我们开发了一种新算法FFas（用于联邦学习的快速草图算法），其通信成本为O(dr)，计算复杂度为O(d(n/p+m+2r2)。其中，m是工作节点的数量，r是矩阵的秩，p是草图列空间的维度，并且满足r≤p?d。在FaSk算法中，我们采用了快速草图技术、与正交Procrustes Fixing的对齐方法以及通过Kolmogorov-Nagumo型平均得到的矩阵Stiefel流形。因此，该算法具有更高的精度、更低的随机波动性，并能更好地表示多个随机投影的特征空间，同时避免了特征空间的正交歧义。我们证明了FaSk算法能够达到与集中式PCA相同的学习速率O(κrλr?n?√r)，并且能够支持更多的工作节点进行并行加速计算。我们通过大量实验验证了该算法的有效性。