Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space
Abstract
We prove that $\mathbb{F}_p$ sketch, a well-celebrated streaming algorithm for frequency moments estimation, is differentially private as is when $p\in(0, 1]$. $\mathbb{F}_p$ sketch uses only polylogarithmic space, exponentially better than existing DP baselines and only worse than the optimal non-private baseline by a logarithmic factor. The evaluation shows that $\mathbb{F}_p$ sketch can achieve reasonable accuracy with strong privacy guarantees. The code for evaluation is included in the supplementary material.
Cite
Text
Wang et al. "Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space." International Conference on Learning Representations, 2022.Markdown
[Wang et al. "Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space." International Conference on Learning Representations, 2022.](https://mlanthology.org/iclr/2022/wang2022iclr-differentially/)BibTeX
@inproceedings{wang2022iclr-differentially,
title = {{Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space}},
author = {Wang, Lun and Pinelis, Iosif and Song, Dawn},
booktitle = {International Conference on Learning Representations},
year = {2022},
url = {https://mlanthology.org/iclr/2022/wang2022iclr-differentially/}
}