Research map / Federated learning and privacy / Differential privacy
A Generalized Shuffle Framework for Privacy Amplification: Strengthening Privacy Guarantees and Enhancing Utility
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 GSPA, a generalized shuffle-model privacy amplification framework for personalized (ε_i,δ_i)-LDP that bounds shuffled outputs by approximate μ-Gaussian DP, tightened via hypothesis testing, and applies it to mean/frequency estimation and DP-SGD.
Problem
Existing shuffle-model privacy amplification analyses mostly assume uniform (ε0,0)-LDP randomizers, with limited treatment of (ε0,δ0)-LDP and personalized LDP, and bounds are loose.
Approach
Analyze the shuffled personalized-LDP process by reducing it to a distance between two multinomial/Bernoulli count distributions, then use Berry-Esseen approximation and f-DP hypothesis testing to derive an approximate μ-GDP bound with μ depending on each user's (ε_i,δ_i), giving tighter amplification than Chernoff/Hoeffding-based bounds.
Key results
- The GSPA bound outperforms Liu23, FMT22 and Erlingsson19 baselines across the evaluated LDP budget distributions, including extreme budgets near zero where Liu23 fails.
- DP-SGD on MNIST with GSPA reaches 96.78% test accuracy after about 50 epochs.
- The paper claims GSPA keeps at least 33% privacy loss compared to existing methods while achieving higher accuracy.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use hypothesis testing instead of rough Chernoff-bound or Hoeffding-inequality estimates | GSPA privacy amplification analysis · Shuffle model privacy amplification | central privacy guarantee | Helped |
| Use GSPA bounds instead of existing privacy-amplification bounds | Shuffle model privacy amplification · Uniform and personalized privacy-budget scenarios | central privacy guarantee | Helped |
| Increase the proportion of conservative users | GSPA mean estimation · Synthetic data | estimation accuracy | Hurt |
| Increase conservative users’ privacy budget | GSPA mean estimation · Synthetic data | estimation accuracy | Helped |
| Increase the proportion of conservative users | GSPA frequency estimation · Synthetic binary records | estimation accuracy | Hurt |
| Increase conservative users’ privacy budget | GSPA frequency estimation · Synthetic binary records | estimation accuracy | Helped |
| Use constant ε=0.5 instead of budgets drawn from U(0.01,2) | GSPA shuffled SGD · MNIST test | accuracy: 93.5% -> 94.8% | Helped |
| Use budgets drawn from U(0.5,1) | GSPA shuffled SGD · MNIST test | accuracy | Helped |
Surprising findings
- A constant local budget of 0.5 gives stronger privacy yet higher test accuracy (94.8%) than the varying U(0.01,2) setting (93.5%) in DP-SGD experiments.
- Mean/frequency estimation accuracy decreases as the fraction of conservative users increases.
Limitations
- Bound is approximate, relying on Berry-Esseen error terms with unspecified constant C and an O(1/n) convergence rate.
- Experiments are small-scale (synthetic data and MNIST with a simple feed-forward classifier) on a single workstation CPU.
- Analysis is restricted to the shuffle model with the stated personalized-LDP randomizers; other privacy definitions such as Renyi DP are left to future work.
Experimental setup
Datasets: MNIST synthetic normal data for mean estimation synthetic binary records for frequency estimation
Benchmarks: MNIST
Metrics: privacy parameter mu (GDP) MAE test accuracy
Baselines: Liu23 FMT22 Erlingsson19
Builds on: Functional Differential Privacy (f-DP) Gaussian differential privacy Liu23 personalized shuffle bound Feldman2022hiding Erlingsson2019amplification
Closest papers by meaning
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.91)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.89)
- Learning from End User Data with Shuffled Differential Privacy over Kernel Densities (ICLR 2025 · similarity 0.88)
- Universal Exact Compression of Differentially Private Mechanisms (NeurIPS 2024 · similarity 0.88)
- The Last Iterate Advantage: Empirical Auditing and Principled Heuristic Analysis of Differentially Private SGD (ICLR 2025 · similarity 0.88)
- Leveraging Randomness in Model and Data Partitioning for Privacy Amplification (ICML 2025 · 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.