Research map / Federated learning and privacy / Differential privacy
Privacy Amplification for Matrix Mechanisms
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 MMCC, the first privacy amplification-by-sampling analysis for generic matrix mechanisms (correlated noise, DP-FTRL), via a conditional composition theorem and reduction to mixture-of-Gaussians PLD accounting.
Problem
Privacy amplification via sampling is not applicable to matrix mechanisms with correlated noise (DP-FTRL), since prior analyses only handle banded encoder matrices with restricted sampling schemes.
Approach
Conditions each round's correlated-noise output on prior outputs so it can be treated as a mixture-of-Gaussians mechanism with high-probability bounds on participation probabilities, then composes via a conditional composition theorem; enables i.i.d. sampling in all rounds for arbitrary lower-triangular encoders.
Key results
- MMCC gives significantly tighter epsilon than prior analysis for DP-FTRL-TreeRestart on CIFAR-10 (n=512, p=1/16, height 4), with gains growing as epsilon becomes small.
- Binary-tree mechanism with shuffling needs noise O(sqrt(log(1/delta) loglog(1/delta))) rather than sqrt(log n) scaling, matching DP-SGD amplified noise asymptotically.
- For n=128, p=1/128, sigma=1, MoG last-iterate analysis gives (0.291, 1e-6)-DP versus (0.806, 1e-6)-DP from composition of subsampled Gaussians.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Analyze the last iterate as a mixture-of-Gaussians mechanism instead of composing subsampled Gaussian mechanisms | DP-SGD with linear losses · Linear-loss DP-SGD, n = 128, p = 1 / 128, σ = 1 | ε at δ = 10^{-6}: .806 -> .291 | Helped |
| Use MMCC privacy analysis instead of the prior analysis | Binary-tree-DP-FTRL · CIFAR-10 | privacy-utility tradeoff | Helped |
| Use i.i.d. sampling with probability p in all n rounds instead of b-min-sep sampling | DP-FTRL-TreeRestart · n = 512, p = 1/16, h = 4 | ε | Helped |
| Combine correlated noise with MMCC amplification rather than using independent-noise mechanisms | Matrix mechanism for prefix sums · All prefix sums | ℓ₂²-error | Helped |
| Apply MMCC amplification to the binary tree mechanism with subsampling probability 1/n | Binary tree mechanism · Binary tree mechanism, n a power of 2 | ε | Helped |
| Increase the noise multiplier c | MMCC analysis of the binary tree mechanism · Binary tree mechanism | tightness of ε improvement relative to a linear fit in √(log(n) + 1) | Helped |
| Increase the noise multiplier c | MMCC analysis of the optimal continual-counting matrix mechanism · Optimal continual counting | tightness of ε improvement relative to a linear fit in √(log(n) + 1) | Helped |
Surprising findings
- Conjecture that with amplification the optimal encoder matrix is never the identity (DP-SGD) for epsilon > 0 outside full-batch settings.
Limitations
- Adaptivity proven only for lower-triangular encoder matrices; non-lower-triangular (e.g., efficient binary tree) only analyzed non-adaptively.
- Tail bounds on conditional sampling probabilities are pessimistic for finite sigma, so reported epsilon can be loose.
- Computationally expensive: several hours for n approx 2000 and requires binary search for calibration.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: epsilon (privacy) test accuracy l2^2 error for prefix sums
Baselines: DP-SGD b-min-sep sampling analysis (Choquette-Choo et al. 2023) binary tree DP-FTRL independent-noise mechanisms
Builds on: DP-FTRL matrix mechanism DP-SGD moments accountant privacy loss distribution accounting amplification by shuffling
Closest papers by meaning
- Near-Exact Privacy Amplification for Matrix Mechanisms (ICLR 2025 · similarity 0.93)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.92)
- Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification (NeurIPS 2024 · similarity 0.91)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.88)
- Rényi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration via Shift Reduction Lemmas (ICML 2024 · similarity 0.88)
- Differentially Private Relational Learning with Entity-level Privacy Guarantees (NeurIPS 2025 · similarity 0.87)
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.