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.

References in corpus (3)

• Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences
• Private False Discovery Rate Control
• Differentially private anonymized histograms