Differentially Private Fractional Frequency Moments Estimation with Polylogarithmic Space

Lun Wang · Iosif Pinelis · Dawn Song

Keywords: [ differential privacy ]

[ Abstract ]
[ Visit Poster at Spot I2 in Virtual World ] [ OpenReview
Thu 28 Apr 10:30 a.m. PDT — 12:30 p.m. PDT

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.

Chat is not available.