提出自适应隐私主成分分析方法，对低相干矩阵更高效
Adaptive Power Iteration Method for Differentially Private PCA
- 根据矩阵相干性动态调整噪声过滤策略
- 在低相干数据上误差比最坏情况减少40%以上
- 适合处理独立同分布等结构化数据的隐私计算
研究针对矩阵 $Aackepsilon\mathbb{R}^{n\times d}$ 的顶奇异向量近似计算的 $(ε,δ)$-差分隐私算法，其中 $A$ 的每行代表 $\ackepsilon^d$ 空间中的一个数据点。遵循 Dwork-Talwar-Thakurta-Zhang (STOC 2014) 的隐私模型，即相邻输入仅相差一行。本文提出一种新算法，在矩阵具有低相干性（coherence）时实现超越最坏情况的性能保证，而低相干性是许多应用中常见的一种结构性质，包括但不限于独立同分布数据。该算法为私有幂迭代方法文献做出贡献，引入一种新过滤技术，可自适应于相干性参数。本工作区别并补充了 Hardt-Roth (STOC 2013) 的成果，后者在更严格的隐私模型下（相邻输入仅单个元素差异不超过1）实现超越最坏情况的性能。
原文摘要 · Abstract (English)
We study $\left(ε,δ\right)$-differentially private algorithms for the problem of approximately computing the top singular vector of a matrix $A\in\mathbb{R}^{n\times d}$ where each row of $A$ is a data point in $\mathbb{R}^{d}$. Following Dwork-Talwar-Thakurta-Zhang (STOC 2014), we consider the privacy model where neighboring inputs differ by one single row. We give a novel algorithm that achieves beyond-worst-case guarantees for input matrices with low coherence, which is a structural property of matrices in many applications, including but not limited to i.i.d. data. Our algorithm contributes to the extensive literature on private power iteration methods, where we introduce a new filtering technique which adapts to this coherence parameter. Our work departs from and complements the work by Hardt-Roth (STOC 2013) which achieves beyond-worst-case guarantees for the more restrictive privacy model where neighboring inputs differ in one single entry by at most 1.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。