Research map / Federated learning and privacy / Differential privacy
Privacy amplification by random allocation
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.
Analyzes privacy amplification for random k-out-of-t allocation (each user's data used in k random steps) and shows it is upper bounded by Poisson subsampling at rate ~k/t, with numerical bounds for Gaussian noise.
Problem
Privacy amplification for the random allocation sampling scheme (each element used in k uniformly random steps out of t), used in DP-SGD and communication-efficient private aggregation; prior analyses were either shuffling-based (loose) or Monte Carlo (computationally prohibitive).
Approach
Shows random allocation's privacy is asymptotically upper bounded by Poisson subsampling at rate ~k/t via a dominating-randomizer reduction and posterior-sampling decomposition; adds a Poisson-decomposition bound (mixture over k), and a direct RDP analysis for the remove direction and an approximate bound for the add direction, all giving efficiently computable bounds.
Key results
- Main theorem: random allocation privacy profile is bounded by Poisson subsampling at rate about (1+gamma)k/t plus t*delta_0 + delta, so the two are asymptotically equivalent.
- Poisson decomposition gives an epsilon for k=1 within a factor about 1.6 of Poisson subsampling at rate 1/t for the same delta.
- Numerically, random allocation bounds for Gaussian noise are typically within about 10% of Poisson subsampling bounds at rate k/t.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use random allocation instead of Poisson subsampling at rate k/t | Gaussian mechanism privacy bounds · Gaussian noise addition | privacy bound: within 10% | Mixed |
| Use the direct RDP analysis for random allocation rather than the Poisson PLD-based bound | Gaussian mechanism · large ε parameter regimes | privacy bound | Helped |
| Use random allocation rather than Poisson subsampling | mean estimation · low-dimensional regime | privacy-utility trade-off | Helped |
| Use random allocation rather than Poisson subsampling | Bernoulli mean estimation · sufficiently large sample size | mean square error | Helped |
| Compare random allocation with Poisson sampling at λ = 1/t | privacy amplification · k = 1 | privacy bound factor: ≈ 1.6 | Mixed |
| Use random allocation rather than Poisson subsampling | mean estimation · one-dimensional regime, p approaching 1 | mean square error | Helped |
| Use random allocation rather than Poisson subsampling | high-dimensional mean estimation · high-dimensional regime | privacy-utility trade-off | Mixed |
Surprising findings
- In some large-epsilon regimes the RDP-based bound for random allocation is lower than PLD-based bounds for Poisson subsampling.
Limitations
- Bounds are analytic/RDP-based and lose some tightness versus PLD accounting, especially for composition in the (eps, delta) conversion (10-20% loss).
- The RDP-based exact expression is restricted to integer alpha >= 2 and becomes computationally costly at large alpha and in the very high privacy regime.
- Main asymptotic result has lower-order terms that can be loose for small t/k or large epsilon_0.
Experimental setup
Metrics: epsilon for fixed delta rényi divergence mean square error
Baselines: Poisson subsampling Monte Carlo balls-and-bins analysis (Choquette-Choo et al.) shuffling amplification (Feldman et al.)
Builds on: DP-SGD shuffle amplification dominating pairs of distributions Rényi differential privacy advanced joint convexity
Closest papers by meaning
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.92)
- A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility (AAAI 2024 · similarity 0.91)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · similarity 0.89)
- Optimal Survey Design for Private Mean Estimation (ICML 2025 · similarity 0.88)
- Locally Optimal Private Sampling: Beyond the Global Minimax (NeurIPS 2025 · similarity 0.88)
- Privacy Guarantees in Posterior Sampling under Contamination (NeurIPS 2026 · similarity 0.88)
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.