Instance-Optimal Mean Estimation Under Differential Privacy

Abstract

Mean estimation under differential privacy is a fundamental problem, but worst-case optimal mechanisms do not offer meaningful utility guarantees in practice when the global sensitivity is very large. Instead, various heuristics have been proposed to reduce the error on real-world data that do not resemble the worst-case instance. This paper takes a principled approach, yielding a mechanism that is instance-optimal in a strong sense. In addition to its theoretical optimality, the mechanism is also simple and practical, and adapts to a variety of data characteristics without the need of parameter tuning. It easily extends to the local and shuffle model as well.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Huang et al. "Instance-Optimal Mean Estimation Under Differential Privacy." Neural Information Processing Systems, 2021.

Markdown

[Huang et al. "Instance-Optimal Mean Estimation Under Differential Privacy." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/huang2021neurips-instanceoptimal/)

BibTeX

@inproceedings{huang2021neurips-instanceoptimal,
  title     = {{Instance-Optimal Mean Estimation Under Differential Privacy}},
  author    = {Huang, Ziyue and Liang, Yuting and Yi, Ke},
  booktitle = {Neural Information Processing Systems},
  year      = {2021},
  url       = {https://mlanthology.org/neurips/2021/huang2021neurips-instanceoptimal/}
}