Dimension Reduction for Large-Scale Federated Data: Statistical Rate and Asymptotic Inference

In light of the rapidly growing large-scale data in federated ecosystems, the traditional principal component analysis (PCA) is often not applicable due to privacy protection considerations and large computational burden. Algorithms were proposed to lower the computational cost, but few can handle both high dimensionality and massive sample size under distributed settings. In this article, we propose the FAst DIstributed (FADI) PCA method for federated data when both the dimension <i>d</i> and the sample size <i>n</i> are ultra-large, by simultaneously performing parallel computing along <i>d</i> and distributed computing along <i>n</i>. Specifically, we use <i>L</i> parallel copies of <i>p</i>-dimensional fast sketches to divide the computing burden along <i>d</i> and aggregate the results distributively along the split samples. We present a general framework applicable to multiple statistical problems, and establish comprehensive theoretical results under the general framework. We show that FADI accelerates the computation while enjoying the same non-asymptotic error rate as the traditional PCA when Lp≥d. We also derive inferential results that characterize the asymptotic distribution of FADI, and show a phase-transition phenomenon as <i>Lp</i> increases. We perform extensive simulations to empirically validate our theoretical findings, and apply FADI to the 1000 Genomes data to study the population structure. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.

鉴于联邦学习生态系统中大规模数据的快速增长，传统主成分分析（PCA）因隐私保护需求与高昂计算负担，往往难以适用。已有算法虽可降低计算成本，但鲜有能够在分布式场景下同时处理高维度与超大规模样本量的方案。本文提出面向维度$d$与样本量$n$均为超大规模的联邦数据场景下的快速分布式（FADI）主成分分析方法，通过同时沿维度$d$开展并行计算、沿样本量$n$开展分布式计算的策略。具体而言，我们采用$p$维快速草图的$L$份并行副本，沿维度$d$拆分计算负载，并沿拆分后的样本分布式聚合结果。我们构建了适用于多类统计问题的通用框架，并在该框架下建立了完备的理论结果。我们证明，当$Lp≥d$时，FADI可在加速计算的同时，保持与传统PCA一致的非渐近误差率。我们还推导了刻画FADI渐近分布的推断结果，并揭示了随$Lp$增大时的相变现象。我们开展了大规模模拟实验以实证验证理论发现，并将FADI应用于千人基因组数据以研究群体结构。本文补充材料可在线获取，包含可复现研究的标准化材料说明。