揭示高维隐私协方差估计中维度诅咒的根源，提出有效解法。
On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA
- 在主成分向量也稀疏的前提下，实现多项式样本复杂度的私有PCA。
- 证明当k= polylog(d)时，私有与非私有方法存在指数级样本差距。
- 首次在稀疏估计中建立隐私统计的理论分离，适合关注隐私机制的研究者。
我们研究了在协方差矩阵满足k-行列稀疏性（k-RCS）条件下，高维差分隐私（DP）协方差估计和主成分分析（PCA）在算子范数下的性质。非私有情形下，仅需poly(k, log d)个样本即可解决这两类问题。然而，目前已知的私有结果（Wang等，2021）在标准参数化下要求Ω(d)样本。我们探究了这种维度诅咒是否对私有稀疏协方差估计是固有的。上界方面，若额外假设主特征向量稀疏，则私有PCA可实现poly(k, log d)样本复杂度。我们进一步给出DP下稀疏协方差估计和PCA的poly(d)下界，当k = polylog(d)时，私有与非私有版本间存在指数级差距。据我们所知，这是首个在任意稀疏估计问题中展示此类分离的结果。技术手段足够灵活，亦可导出无需稀疏假设的典型私有PCA更强下界。
原文摘要 · Abstract (English)
We study high-dimensional differentially private (DP) covariance estimation in the operator norm, and principal component analysis (PCA), under $k$-row-column sparsity ($k$-RCS) of the covariance matrix. In the non-private setting, it is known that $\mathsf{poly}(k, \log d)$ samples suffice to solve both of these problems. However, the only comparable result known under DP (Wang et al. 2021) requires $Ω(d)$ samples under standard parameterizations of the problem. We investigate when this curse of dimensionality is inherent for sparse covariance estimation tasks under DP. On the upper bound front, we show that a $\mathsf{poly}(k, \log d)$ sample complexity for PCA is possible under DP, if we also posit sparsity of the leading eigenvector. We complement this result with $\mathsf{poly}(d)$ lower bounds under DP for both sparse covariance estimation and PCA, establishing an exponential gap between the private and non-private variants of these problems when $k = \mathsf{polylog}(d)$. To our knowledge, no such separation has previously been demonstrated for any sparse estimation problems in private high-dimensional statistics. Our techniques are flexible enough that they imply stronger lower bounds even for the well-studied problem of standard DP PCA, without sparsity assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。