标题： 一种用于差分隐私$k$-PCA 的迭代算法及自适应噪声 显示英文标题

标题： An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise

摘要： 给定 $n$个独立同分布的随机矩阵 $A_i \in \mathbb{R}^{d \times d}$，它们具有共同的期望 $\Sigma$，差分隐私随机主成分分析的目标是找到一个维度为 $k$的子空间，该子空间捕捉 $\Sigma$的最大方差方向，同时保持每个个体 $A_i$的差分隐私（DP）。 现有的方法要么（i）要求样本量$n$与维度$d$超线性增长，即使在对$A_i$做高斯假设的情况下也是如此，要么（ii）在差分隐私下引入过多噪声，即使在$A_i$内部的固有随机性较小时也是如此。 Liu 等人 (2022a) 解决了针对子高斯数据的这些问题，但仅限于使用他们的算法 DP-PCA 来估计顶级特征向量 ($k=1$) 。 我们提出了第一个能够估计任意$k \leq d$的顶部$k$特征向量的算法，同时克服了上述两个限制。 对于$k=1$，我们的算法达到了 DP-PCA 的效用保证，在$n = \tilde{\!O}(d)$时也能实现接近最优的统计误差。我们进一步提供了通用$k > 1$的下界，该下界与我们的上界相差一个因子$k$，并且实验上展示了我们的算法相比可比基线的优势。 显示英文摘要

摘要： Given $n$ i.i.d. random matrices $A_i \in \mathbb{R}^{d \times d}$ that share a common expectation $\Sigma$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $\Sigma$, 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.