Research map / Federated learning and privacy / Differential privacy
Near-Exact 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 Monte Carlo accounting plus a balls-in-bins batching scheme to compute near-exact privacy amplification for matrix-mechanism correlated noise, enabling optimization of the correlation matrix under amplification.
Problem
Computing tight privacy parameters when combining privacy amplification via random batching with noise correlated across rounds through a correlation matrix (the matrix mechanism / DP-FTRL), where prior analyses were limited to banded matrices or gave loose composition-based bounds.
Approach
Use Monte Carlo accounting on the whole matrix mechanism (bypassing composition) with a balls-in-bins batching scheme that is easier to analyze than Poisson sampling and closer to shuffling in implementation; gradients via implicit differentiation let the correlation matrix be optimized for RMSE under amplification.
Key results
- Optimizing the correlation matrix under balls-in-bins amplification reduces prefix-sum RMSE by up to about 10% relative to the prior SOTA banded matrix with Poisson sampling.
- On CIFAR-10 with a VGG model, banded matrix factorization with balls-in-bins batching is at least as good as the Poisson-sampling baseline and gives up to 1% absolute accuracy improvement.
- A practical fixed-batch-size variant of balls-in-bins with BLT matrices still improves over unamplified MEMF baseline on CIFAR-10.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize the correlation matrix while accounting for amplification | Correlated noise mechanisms with balls-in-bins batching · Prefix sums | RMSE: up to a 10% reduction in RMSE | Helped |
| Use banded matrices with balls-in-bins batching instead of the banded-matrix Poisson-sampling baseline | VGG training · CIFAR-10 | test accuracy: up to 1% absolute accuracy improvements | Helped |
| Optimize BLT matrices for RMSE under balls-in-bins batching | VGG training · CIFAR-10 | test accuracy | Helped |
| Use BLT matrices instead of the banded-matrix Poisson-sampling baseline | Correlated noise training · CIFAR-10 | memory efficiency: up to 4x more memory efficient | Helped |
| Optimize general Toeplitz matrices under balls-in-bins batching | VGG training · CIFAR-10 | test accuracy | Mixed |
| Use balls-in-bins batching rather than Poisson sampling for fixed 64-banded matrices | Banded matrix factorization · RMSE amplification, up to ε=16 | RMSE reduction from amplification | Helped |
| Use Poisson sampling rather than balls-in-bins batching for fixed identity matrices at larger ε | DP-SGD · RMSE amplification | RMSE reduction from amplification | Helped |
| Optimize the choice of band count for each amplification method | Banded matrix factorization · RMSE, ε ≤ 4 | RMSE | Helped |
| Use Poisson-sampling amplification rather than the unamplified baseline at ε=16 | Banded matrix factorization · RMSE | RMSE | Hurt |
| Use balls-in-bins batching with the best correlation matrix rather than the unamplified baseline | Correlated noise mechanisms · RMSE | RMSE | Helped |
| Use approximately 2^9 rather than 2^20 Monte Carlo samples per optimization iteration | Correlation-matrix optimization · RMSE at ε = 0.5, 1, 2 | RMSE: ≈ 2^9 samples per iteration; 2^20 samples per iteration | No clear effect |
| Use approximately 2^9 rather than 2^20 Monte Carlo samples per optimization iteration | Correlation-matrix optimization · RMSE at ε = 4 | RMSE increase: ≈ 10% increase in RMSE | Hurt |
Surprising findings
- Poisson sampling amplification is better than balls-in-bins for small epsilon but the banded-matrix benefit of amplification disappears at epsilon=16, where the unamplified baseline wins.
- Shuffling-based implementations assumed as Poisson sampling in prior CIFAR work give lower accuracy than the properly analyzed balls-in-bins variant in some settings.
Limitations
- Monte Carlo sample complexity scales as 1/delta, which may be prohibitive for small delta.
- Optimization restricted to Toeplitz matrices for efficiency; optimized Toeplitz matrices underperform banded baselines on CIFAR-10.
- Practical balls-in-bins implementation only tested at small scale.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10 prefix sums RMSE
Metrics: RMSE of prefix sums test accuracy epsilon at fixed delta
Baselines: BandMF with Poisson sampling amplification unamplified DP-SGD / MEMF shuffling BLT matrices
Builds on: DP-FTRL banded matrix factorization Poisson sampling privacy amplification privacy loss distribution BLT matrices
Closest papers by meaning
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · 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.89)
- 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.87)
- Privacy Amplification Persists under Unlimited Synthetic Data Release (NeurIPS 2026 · 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.