论文标题
改进了私人countsketch的公用事业分析
Improved Utility Analysis of Private CountSketch
论文作者
论文摘要
素描是处理稀疏（或稀疏矢量良好及其备受抗衡的高维矢量）的重要工具，在分布式，平行和流设置中特别有用。众所周知，可以通过根据草图的敏感性添加噪音来差异化的草图，并且已在私人分析和联合学习设置中使用。差异隐私的后处理属性意味着，从草图计算出的所有估计都可以在给定的隐私预算内发布。 在本文中，我们考虑了经典的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.
