提出首个支持任意维度k的私有化PCA算法，实现高效低噪估计。
An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
- 通过自适应噪声迭代算法，动态调整隐私保护强度。
- 当n≈O(d)时，对k=1达到近最优统计误差，且适用于任意k≤d。
- 适合需要高维数据隐私保护的机器学习场景，如医疗或金融分析。
给定n个独立同分布的随机矩阵 $A_i \in \mathbb{R}^{d \times d}$，它们共享共同期望 $Σ$，差分隐私随机PCA的目标是识别出能捕捉 $Σ$ 最大方差方向的k维子空间，同时保证每个 $A_i$ 的差分隐私。现有方法要么要求样本量n随维度d超线性增长（即使在高斯假设下），要么在 $A_i$ 内部随机性较小时仍引入过量噪声。Liu等（2022a）针对亚高斯数据提出了仅用于估计主特征向量（k=1）的DP-PCA算法，解决了上述问题。我们提出首个可估计任意k ≤ d的主特征向量的算法，同时克服了前述两个缺陷。当k=1时，本算法在统计效用上与DP-PCA相当，在n = Õ(d)时即可实现近最优误差。我们进一步为k > 1提供了下界，其与上界相差至多因子k，实验表明该算法优于现有基线方法。
原文摘要 · Abstract (English)
Given $n$ i.i.d. random matrices $A_i \in \mathbb{R}^{d \times d}$ that share a common expectation $Σ$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $Σ$, while preserving differential privacy (DP) of each individual $A_i$. Existing methods either (i) require the sample size $n$ to scale super-linearly with dimension $d$, even under Gaussian assumptions on the $A_i$, or (ii) introduce excessive noise for DP even when the intrinsic randomness within $A_i$ is small. Liu et al. (2022a) addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ($k=1$) using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top $k$ eigenvectors for arbitrary $k \leq d$, whilst overcoming both limitations above. For $k=1$ our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when $n = \tilde{\!O}(d)$. We further provide a lower bound for general $k > 1$, matching our upper bound up to a factor of $k$, and experimentally demonstrate the advantages of our algorithm over comparable baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。