Reproduce “Differentially Private Quantiles with Smaller Error” 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
Jacob Imola, Fabrizio Boninsegna, Hannah Keller, Anders Aamand, Amrita Roy Chowdhury, Rasmus Pagh
Imola et al. developed SliceQuantiles, a new mechanism for differentially private multiple quantile estimation that significantly reduces maximum rank error. For pure ε-DP, it achieves an O((log(b) + log²(m)) / ε) error, while for (ε, δ)-DP, it offers an error bound independent of the privacy parameter δ, providing superior accuracy for very strong privacy guarantees.
Key insights
- Leveraging continual counting for correlated noise addition to ranks is more efficient for privacy budgeting across multiple quantiles than applying independent noise to each.
- A precise mapping of noisy rank vectors between adjacent datasets is critical for achieving tight privacy bounds, preventing an 'm'-dependent blow-up in privacy cost.
- The rank error for approximate (ε, δ)-DP can be made independent of `δ` by carefully managing the privacy analysis, thereby improving utility for practically relevant, very small `δ` values.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.