Improved Utility Analysis of Private CountSketch
Improved Utility Analysis of Private CountSketch
复制标题
改进的 Private CountSketch 效用分析
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Thorup
中科院分区：
文献类型：
--
作者：
R. Pagh;M. Thorup
草图绘制是处理稀疏高维向量（或通过稀疏向量很好地近似）的重要工具，在分布式、并行和流式设置中特别有用。众所周知，可以通过根据草图的敏感性添加噪声来使草图具有差分隐私性，这已用于私有分析和联邦学习设置中。差异隐私的后处理特性意味着根据草图计算的所有估计都可以在给定的隐私预算内发布。在本文中，我们考虑使用高斯机制进行差分隐私的经典 CountSketch，并对其估计误差进行改进的分析。也许令人惊讶的是，隐私与实用性的权衡本质上是最好的，与 CountSketch 中的重复次数无关：该错误几乎与非私有 CountSketch 的错误加上在原始高维域中使向量私有所需的噪声相同。
Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approximated by a sparse vector), especially useful in distributed, parallel, and streaming settings. It is known that sketches can be made differentially private by adding noise according to the sensitivity of the sketch, and this has been used in private analytics and federated learning settings. The post-processing property of differential privacy implies that all estimates computed from the sketch can be released within the given privacy budget. In this paper we consider the classical CountSketch, made differentially private with the Gaussian mechanism, and give an improved analysis of its estimation error. Perhaps surprisingly, the privacy-utility trade-off is essentially the best one could hope for, independent of the number of repetitions in CountSketch: The error is almost identical to the error from non-private CountSketch plus the noise needed to make the vector private in the original, high-dimensional domain.
差分私有线性草图：高效的实现和应用
DOI：
--
发表时间：
2022
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Zhao, Fuheng;Qiao, Dan;Redberg, Rachel;Agrawal, Divyakant;Abbadi, Amr El;Wang, Yu-Xiang
通讯作者：
Wang, Yu-Xiang