Reproduce “Optimal partition selection with Rényi 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
Charlie Harrison, Pasin Manurangsi
Researchers at Google extended optimal partition selection algorithms to the more flexible δ-approximate R´enyi Differential Privacy (RDP) framework and introduced SNAPS, a new mechanism that boosts the utility of existing adaptive partition selection algorithms by 10-20% across various datasets. They also quantified an inherent privacy cost associated with simultaneously releasing noisy partition counts compared to only selecting partitions under RDP.
Key insights
- The optimality of partition selection can be extended to δ-approximate RDP for single-user contributions, providing tighter privacy accounting for compositional settings.
- A general optimal mechanism does not exist for partition selection when users contribute multiple items, highlighting the inherent complexity of this scenario.
- There is a quantifiable numerical separation in privacy between optimal additive noise mechanisms (which release counts) and optimal non-additive mechanisms (which only select partitions) under RDP, indicating a cost for releasing additional information.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.