Research map / Federated learning and privacy / Differential privacy
Faster Differentially Private Top-$k$ Selection: A Joint Exponential Mechanism with Pruning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes FastJoint, a pruned "group by" exponential-mechanism sampler that reproduces the Joint top-k mechanism's output distribution in O(d + k^2/ε · ln d) time instead of Õ(dk), running 10-100x faster with similar accuracy.
Problem
Differentially private top-k selection: identifying k items with approximately the highest scores among d items; the existing Joint mechanism samples from all d^Θ(k) length-k sequences but costs Õ(dk) time and space.
Approach
Partition length-k sequences into loss-consistent groups indexed by (loss r, first-hitting position i), count group sizes via closed-form products of histogram counts, and truncate the loss at tau so only O(k^2) groups matter; sample a group by Gumbel-max and then a uniform sequence within it, giving a Joint-equivalent (truncated) exponential mechanism with linear-in-d cost.
Key results
- FastJoint runs roughly 10 to 100 times faster than Joint across the tested datasets while matching its solution quality (l_inf and l_1 error).
- FastJoint's running time decreases as epsilon increases, consistent with the theoretical bound, and its accuracy is stable across beta because tau barely changes with beta.
- FastJoint is slower than the O(d) CDP-Peel but outperforms the O(dk) PNF-Peel on large datasets such as Foods, and beats PNF-Peel in accuracy for all k.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use FastJoint instead of Joint | Joint top-k selection · Six real-world datasets | running time: 10 to 100 times faster | Helped |
| use pruning in FastJoint | Joint-style top-k selection · Six real-world datasets | ℓ∞ error | No clear effect |
| use FastJoint instead of PNF-Peel | top-k selection · All tested datasets and values of k | ℓ∞ error | Helped |
| use FastJoint instead of CDP-Peel | top-k selection · All tested datasets | ℓ∞ error | Helped |
| use FastJoint instead of CDP-Peel | top-k selection · Six real-world datasets | running time | Hurt |
| increase ε | FastJoint · Real-world datasets | running time | Helped |
| vary β | FastJoint · Medium-sized dataset | ℓ∞ error | No clear effect |
| use FastJoint instead of PNF-Peel and CDP-Peel | top-k selection · Games dataset | ℓ∞ error | Mixed |
Surprising findings
- FastJoint's accuracy does not change with beta, which is surprising given that beta governs the failure probability; the pruning threshold tau is dominated by the log of binom(d,k)k!, so it barely varies with beta.
- The Joint baseline's Python sequence-sampling step has worst-case O(dk^2) cost, which causes running-time jumps on some datasets.
Limitations
- The theoretical speedup holds only when k is not too large (k in O(sqrt d) gives Õ(d)); the bound grows as k^2.
- FastJoint is not fully vectorized and can be slower than the vectorized PNF-Peel on small datasets.
- Accuracy advantage over CDP-Peel holds only for at least moderately large k; the method underperforms on datasets with small score gaps.
Experimental setup
Datasets: Games (Steam) Books (Goodreads) News (Mashable) Tweets Movies Foods (Amazon)
Benchmarks: Games Books News Tweets Movies Foods
Metrics: running time l_infinity error l_1 error
Baselines: Joint mechanism PNF-Peel (permute-and-flip peeling) CDP-Peel (peeling exponential mechanism)
Builds on: Joint mechanism (Gillenwater et al. 2022) exponential mechanism peeling exponential mechanism
Closest papers by meaning
- Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph (NeurIPS 2025 · similarity 0.86)
- Privately Counting Partially Ordered Data (ICLR 2025 · similarity 0.85)
- Sort, Partition, Randomize: Optimal Binary Hypothesis Testing under Local Differential Privacy (NeurIPS 2026 · similarity 0.85)
- Scalable Private Partition Selection via Adaptive Weighting (ICML 2025 · similarity 0.85)
- Private Prediction via Shrinkage (NeurIPS 2026 · similarity 0.85)
- Perturb-and-Project: Differentially Private Similarities and Marginals (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.