Reproduce “Understanding the Sparse Vector Technique for 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
Min Lyu, Dong Su, Ninghui Li
Many existing Sparse Vector Technique (SVT) implementations for differential privacy are clarified to be non-private or suboptimal; the authors propose a new, more accurate SVT and demonstrate that the Exponential Mechanism significantly outperforms SVT for non-interactive top-k selection tasks.
Key insights
- Outputting noisy query answers directly or failing to cap positive outcomes leads to non-private Sparse Vector Technique (SVT) variants, resulting in infinite privacy loss.
- Optimizing the privacy budget allocation between threshold and query noise (e.g., a ratio of 1:c^(2/3) for monotonic queries) significantly improves the utility of SVT.
- For non-interactive top-k selection tasks, the Exponential Mechanism consistently offers superior accuracy compared to even optimized SVT.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.