Reproduce “Instance-optimal Mean Estimation Under Differential Privacy” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ziyue Huang, Yuting Liang, Ke Yi
This paper presents an instance-optimal differentially private mean estimation mechanism, bridging the gap between theoretical worst-case bounds and practical utility. It introduces a 'Shifted-Clipped-Mean' estimator that automatically determines the optimal clipping threshold, outperforming prior state-of-the-art methods on synthetic and real-world datasets across central, local, and shuffle differential privacy models.
Key insights
- A novel R_in-nbr(D) notion of instance optimality provides a meaningful and achievable target for DP mechanisms, addressing limitations of stricter definitions by focusing on 'in-neighbors'.
- The optimal clipping threshold for differentially private mean estimation is directly linked to a specific quantile (the (n - sqrt(2d/ρ))-th) of the squared L2 norms of the data, enabling a principled, data-adaptive approach.
- Applying random rotations combined with private shifting allows the error of private mean estimation to depend on the dataset diameter w(D) rather than the potentially much larger maximum norm r(D), leading to tighter bounds and improved utility.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.