提出一种更优的差分隐私主成分分析方法，误差仅依赖于矩阵秩和谱隙。
Tight Differentially Private PCA via Matrix Coherence
- 基于SVD与扰动机制，利用秩-r相干性控制隐私误差
- 在稠密场景下达到非私有最优算法性能，显著优于现有方法
- 适用于低相干性图问题，如私有Max-Cut求解
我们重新研究在差分隐私约束下计算矩阵前r个奇异向量张成空间的问题。提出一种简单高效的算法——基于奇异值分解与标准扰动机制——其私有秩-r近似误差仅取决于前r个奇异向量的秩-r相干性及谱隙σ_r - σ_{r+1}。该结果解决了Hardt和Roth提出的开放问题。我们的估计器性能超越当前最优方法，在某些场景下表现尤为突出：在稠密设置中，单峰型主成分分析（Wishart模型）的保障效果与最优非私有算法一致，而此前的私有算法无法达到此水平。此外，我们证明了（秩-r）相干性在高斯扰动下不增加，这意味着基于高斯机制的所有估计器（包括本文方法）均保持输入相干性。我们还推测该性质对其他结构化模型（如图中植根问题）也成立。最后，我们探讨了相干性在图问题中的应用，提出在低相干性假设下，可用于实现差分隐私的Max-Cut及其他约束满足问题算法。
原文摘要 · Abstract (English)
We revisit the task of computing the span of the top $r$ singular vectors $u_1, \ldots, u_r$ of a matrix under differential privacy. We show that a simple and efficient algorithm -- based on singular value decomposition and standard perturbation mechanisms -- returns a private rank-$r$ approximation whose error depends only on the \emph{rank-$r$ coherence} of $u_1, \ldots, u_r$ and the spectral gap $σ_r - σ_{r+1}$. This resolves a question posed by Hardt and Roth~\cite{hardt2013beyond}. Our estimator outperforms the state of the art -- significantly so in some regimes. In particular, we show that in the dense setting, it achieves the same guarantees for single-spike PCA in the Wishart model as those attained by optimal non-private algorithms, whereas prior private algorithms failed to do so. In addition, we prove that (rank-$r$) coherence does not increase under Gaussian perturbations. This implies that any estimator based on the Gaussian mechanism -- including ours -- preserves the coherence of the input. We conjecture that similar behavior holds for other structured models, including planted problems in graphs. We also explore applications of coherence to graph problems. In particular, we present a differentially private algorithm for Max-Cut and other constraint satisfaction problems under low coherence assumptions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。