Reproduce “Boosting the Accuracy of Differentially-Private Histograms Through Consistency” 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
Michael Hay, Vibhor Rastogi, Gerome Miklau, Dan Suciu
Researchers from UMass Amherst and the University of Washington developed a method to significantly boost the accuracy of differentially private histogram queries by applying consistency constraints as a post-processing step to noisy outputs. This approach achieves at least an order of magnitude reduction in error for unattributed histograms and uniform error reduction for universal histograms across various range sizes, without compromising privacy guarantees.
Key insights
- Post-processing differentially private outputs using consistency constraints can significantly improve accuracy without compromising the original privacy guarantees.
- Carefully structured query sets, like sorted sequences or hierarchical counts, possess inherent constraints that can be leveraged to reduce the impact of added noise.
- The constrained inference process effectively 'removes' excess noise that might have been added by standard differentially private mechanisms, leading to higher utility.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.