Research map / Federated learning and privacy / Differential privacy
Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML
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.
Scales DP-BandMF to very large numbers of training iterations and model parameters via implicit strategy optimization (O(n^2 b) time, O(nb) space), banded Toeplitz strategies (O(nb) time, O(n) space, scaling beyond 10^7 iterations), and distributed sharded noise generation.
Problem
DP-BandMF, the best correlated-noise matrix factorization mechanism for DP training, does not scale: strategy optimization needs O(n^3) time and O(n^2) memory (limiting n to about 10^4), and training needs O(b·d) memory for noise state, which is prohibitive for large models.
Approach
Compute the expected-error objective implicitly by streaming rows of AC^{-1} rather than materializing n×n matrices, restrict to banded Toeplitz strategies for even larger n, and shard the correlated-noise state across machines so each machine generates its own coordinates of the noise with no communication until noise is added.
Key results
- Implicitly optimized banded strategies scale to n > 10^5 iterations, and banded Toeplitz strategies scale beyond n > 10^7, with Toeplitz strategies within 0-2% of the best strategy in expected error.
- Amplified DP-BandMF gives lower RMSE than all other scalable mechanisms across tested settings, with about 19% better RMSE than the best competitor at epsilon = 8 (n=16384, k=8).
- Distributed noise generation keeps correlated-noise generation time small; with 100M-parameter BertBase on 32 TPU v3 cores, noise generation is not the bottleneck up to b=128 bands (1.6 GB per accelerator).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use amplified DP-BandMF instead of the competing scalable mechanisms | Differentially private training on the Prefix workload · n=16384, k=8; varying ε | RMSE: 19% better RMSE than the best competitor for ε as large as 8 | Helped |
| Use amplified DP-BandMF instead of DP-SGD or Buffered Toeplitz | Differentially private training on the Prefix workload · ε=1, n=16384, k=8 | RMSE: ≈ 2× worse RMSE | Helped |
| Use unamplified DP-BandMF instead of Buffered Toeplitz | Non-amplified training on the Prefix workload · Varying ε | RMSE: ∼ 5% lower RMSE | Helped |
| Restrict the strategy to banded Toeplitz matrices rather than arbitrary banded strategies (ablation) | DP-BandMF · Prefix workload; large n ≥ 16384 and small b ≤ 32 | RMSE suboptimality: ≤ 0.25% | Hurt |
| Replace the optimized strategy with Banded Sqrt | DP-BandMF · Prefix workload; varying settings tested | Expected error: suboptimality approaches up to 25% | Hurt |
| Set the number of bands to the optimal value rather than using DP-SGD's one band (ablation) | Amplified DP-BandMF · Prefix workload; fixed ε=1, n=16384 | RMSE: < 2× worse with only two epochs; < 18% worse with only eight epochs | Helped |
| Increase training epochs (ablation) | DP-BandMF · Prefix workload | RMSE | Helped |
| Use amplified DP-BandMF rather than unamplified DP-BandMF (ablation) | DP-BandMF · Prefix workload; ε up to 8 | RMSE: ≈ 15% | Helped |
| Use correlated noise with DP-BandMF rather than uncorrelated DP-SGD noise (ablation) | DP-BandMF · Prefix workload; most extreme setting | RMSE: 9× lower than DP-SGD | Helped |
| Use fewer bands at the same RMSE (ablation) | DP-BandMF with an adaptive optimizer · BertTiny on StackOverflow | Evaluation cross entropy | Helped |
| Use 1, 8, 64, or 512 bands rather than more bands (ablation) | DP-BandMF with a non-adaptive optimizer · BertTiny on StackOverflow | Evaluation cross entropy | No clear effect |
| Apply the min-separation robustness heuristic to banded Toeplitz coefficients (ablation) | Banded Toeplitz DP-BandMF · Federated training; min-separation 200–400 | RMSE | Mixed |
Surprising findings
- For an adaptive optimizer, strategies with fewer bands give better learning performance than strategies with the same RMSE, so RMSE is not a perfect proxy for learning performance.
- Banded Sqrt baseline is up to 25% suboptimal in expected error across tested settings.
Experimental setup
Datasets: StackOverflow
Benchmarks: StackOverflow
Metrics: RMSE RMSE suboptimality ratio evaluation cross entropy wall clock time
Baselines: DP-SGD Dense-DP-MF Banded Sqrt BLT-DP-MF Tree Aggregation Stamping FHU Buffered Toeplitz
Builds on: DP-BandMF DP-FTRL Matrix Mechanism DP-SGD
Closest papers by meaning
- Correlated Noise Provably Beats Independent Noise for Differentially Private Learning (ICLR 2024 · similarity 0.89)
- Banded Square Root Matrix Factorization for Differentially Private Model Training (NeurIPS 2024 · similarity 0.88)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.87)
- Privacy Amplification for Matrix Mechanisms (ICLR 2024 · similarity 0.86)
- Near-Exact Privacy Amplification for Matrix Mechanisms (ICLR 2025 · similarity 0.86)
- DOPPLER: Differentially Private Optimizers with Low-pass Filter for Privacy Noise Reduction (NeurIPS 2024 · similarity 0.86)
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.