Research map / Federated learning and privacy / Differential privacy
Banded Square Root Matrix Factorization for Differentially Private Model Training
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 banded square root (BSR) matrix factorization for DP-SGD with momentum and weight decay, giving closed-form coefficients that avoid the costly SDP-based optimal factorization while matching its accuracy on CIFAR-10.
Problem
Differentially private SGD via matrix factorization requires solving an expensive SDP to find an approximately optimal factorization before training, which is computationally intractable for large numbers of steps and must be redone for every change in hyperparameters.
Approach
Take the matrix square root of the SGD-with-momentum/weight-decay workload matrix (a lower-triangular Toeplitz matrix), truncate it to a band of width p matching the participation separation b, and derive closed-form Toeplitz coefficients and sensitivity, so no numerical optimization is needed.
Key results
- BSR's expected approximation error is typically within a few percent of AOF's (e.g., n=1000, alpha=1, beta=0: 12.1 vs 11.3), and clearly better than square root and identity baselines.
- On CIFAR-10 with (eps,delta)=(4,1e-5) and single participation, BSR accuracy is close to AOF (e.g., 36.3% vs 37.9% at n=500) and far above the identity baseline (27.7%).
- BSR computes its factorization in closed form in O(p log p) time, versus hours to days of CPU time for AOF at n>=500 and numerical instability at large n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use BSR instead of the square-root factorization | SGD workload factorization · Single participation, α=1, β=0, n=1000 | expected factorization error: 15.7 -> 12.1 | Helped |
| Use BSR instead of AOF | SGD workload factorization · Single participation, α=1, β=0, n=1000 | expected factorization error: 11.3 -> 12.1 | Hurt |
| Use BSR instead of identity or workload baseline factorization | SGD workload factorization · Single participation, α=1, β=0, n=1000 | expected factorization error: 70.7 -> 12.1; 196.2 -> 12.1 | Helped |
| Use BSR instead of AOF | ConvNet trained privately on CIFAR-10 · Single participation, 1000 updates, (ε,δ)=(4,10^-5) | accuracy: 35.674 -> 36.158 | No clear effect |
| Use BSR instead of identity or workload baseline factorization | ConvNet trained privately on CIFAR-10 · Single participation, 1000 updates, (ε,δ)=(4,10^-5) | accuracy: 27.24 -> 36.158; 13.6 -> 36.158 | Helped |
| Use BSR instead of AOF | ConvNet trained privately on CIFAR-10 · Repeated participation, 20 epochs, (ε,δ)=(4,10^-5) | accuracy: 46.988 -> 53.141999999999996 | Helped |
| Use BSR instead of identity or workload baseline factorization | ConvNet trained privately on CIFAR-10 · Repeated participation, 20 epochs, (ε,δ)=(4,10^-5) | accuracy: 35.04 -> 53.141999999999996; 17.728 -> 53.141999999999996 | Helped |
Surprising findings
- BSR sometimes slightly outperforms AOF in error and accuracy at large n, which the authors attribute to AOF being solved with reduced numerical precision.
Limitations
- Asymptotic optimality without weight decay (alpha=1) is not matched between upper and lower bounds for repeated participation.
- Theoretical guarantees are only analytic for SGD with momentum/weight decay and constant learning rate; varying learning rates break Toeplitz structure.
- Experiments use a small ConvNet on CIFAR-10 and hyperparameters tuned on validation with repeated experiments that weaken the privacy guarantee.
Experimental setup
Datasets: CIFAR-10
Benchmarks: CIFAR-10
Metrics: expected approximation error test classification accuracy
Baselines: AOF (approximately optimal factorization) square root factorization DP-SGD (identity factorization) DP-FTRL-style identity-noise baseline (A·Id)
Builds on: matrix factorization mechanism approximately optimal factorization (AOF) DP-SGD b-min-separated participation
Closest papers by meaning
- Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML (ICLR 2025 · similarity 0.88)
- Federated Binary Matrix Factorization Using Proximal Optimization (AAAI 2025 · similarity 0.88)
- In-depth Analysis of Low-rank Matrix Factorisation in a Federated Setting (AAAI 2025 · similarity 0.86)
- Creating Coherence in Federated Non-Negative Matrix Factorization (AAAI 2025 · similarity 0.86)
- DMM: Distributed Matrix Mechanism for Differentially-Private Federated Learning Based on Constant-Overhead Linear Secret Resharing (ICML 2025 · similarity 0.84)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.84)
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.