Reproduce “Missing Mass for Differentially Private Domain Discovery” 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

Travis Dick, Matthew Joseph, Vinod Raman

Researchers at Google Research and the University of Michigan established the first absolute utility guarantees for differentially private set union, employing the "missing mass" metric rather than item cardinality. They demonstrate that the Weighted Gaussian Mechanism achieves near-optimal performance on Zipfian data and extends its applicability to differentially private top-k selection and k-hitting set in unknown domains, often outperforming existing methods empirically.

Key insights

  • The Weighted Gaussian Mechanism offers near-optimal ℓ1 missing mass bounds for Zipfian data and distribution-free ℓ∞ missing mass guarantees, addressing a critical gap in theoretical understanding for DP set union.
  • Combining WGM for initial domain discovery with known-domain private algorithms provides a robust and provably private solution for complex tasks like top-k selection and k-hitting set in previously challenging unknown domain scenarios.
  • Despite its simplicity, WGM-based methods are empirically competitive with, or superior to, more complex and computationally intensive baselines across diverse real-world datasets.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.