Improved Utility Analysis of Private CountSketch

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

  • Fulltext

    Final published version, 455 KB, PDF document

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 \emph{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.
Original languageEnglish
Title of host publicationAdvances in Neural Information Processing Systems 35 (NeurIPS 2022)
Number of pages13
PublisherNeurIPS Proceedings
Publication date2022
ISBN (Electronic)9781713871088
Publication statusPublished - 2022
Event36th Conference on Neural Information Processing Systems (NeurIPS 2022). - New Orleans/ Virtual, United States
Duration: 28 Nov 20229 Dec 2022

Conference

Conference36th Conference on Neural Information Processing Systems (NeurIPS 2022).
LandUnited States
ByNew Orleans/ Virtual
Periode28/11/202209/12/2022
SeriesAdvances in Neural Information Processing Systems
Volume35
ISSN1049-5258

ID: 340885528