Research map / Federated learning and privacy / Differential privacy
Correlated Noise Provably Beats Independent Noise for Differentially Private Learning
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.
Characterizes asymptotic utility of correlated-noise DP-FTRL versus DP-SGD via frequency-domain analysis, proves separation for linear regression, and proposes the efficient nu-DP-FTRL with closed-form Toeplitz noise coefficients that nearly matches state-of-the-art on CIFAR-10 and StackOverflow.
Problem
Correlated noise in DP-FTRL can improve over DP-SGD, but it was unclear whether this improvement is provable, and the best noise coefficients require an expensive O(T^3) semidefinite program.
Approach
Analyze noisy FTRL as a linear time-invariant system in the Fourier domain to derive asymptotic suboptimality for any Toeplitz noise coefficients, yielding closed-form near-optimal coefficients (1-nu)^t-damped binomial series that are anytime and O(T) per step.
Key results
- On CIFAR-10 at epsilon=10, nu-DP-FTRL reaches 69.26% vs 70.83% for the Multi-Epoch mechanism, which needs O(T^3) precomputation.
- nu-DP-FTRL outperforms DP-SGD for epsilon>=4 on CIFAR-10 (63.02% vs 62.02%) and around epsilon≈2 on StackOverflow (23.6% vs 22.6%).
- For linear regression, nu-Noisy-FTRL achieves suboptimality O(eta^2 rho^-1 d_eff log^2) versus Theta(eta rho^-1 d) for Noisy-SGD, a gap up to d/log d.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use damped correlated noise instead of independent noise | DP-SGD versus ν-DP-FTRL · CIFAR-10, ε≥4 | accuracy: 62.02% vs. 63.02% | Helped |
| Use damped correlated noise instead of independent noise | DP-SGD versus ν-DP-FTRL · StackOverflow, ε≈2 | accuracy: 22.6% versus 23.6% | Helped |
| Use ν-DP-FTRL instead of ME | CIFAR-10 · CIFAR-10, ε=10 | accuracy: 69.26% vs. 70.83% | Hurt |
| Use correlated noise with ν-DP-FTRL | StackOverflow · StackOverflow, ε=8 | validation accuracy | Helped |
| Use damped correlated noise | DP-FTRL versus DP-SGD · Private image and text classification | accuracy: average 3pp improvement | Helped |
| Set ν to 0, removing exponential damping from the correlations (ablation) | ν-DP-FTRL · CIFAR-10 and StackOverflow | accuracy | Hurt |
| Use correlated noise rather than independent noise | Noisy-FTRL versus Noisy-SGD · Linear regression, asymptotic | suboptimality: Noisy-SGD: Θ(η ρ^{-1} d); ν-Noisy-FTRL: O(η^2 ρ^{-1} d_eff log^2(1/(ημ))) | Helped |
| Use optimal anti-correlated noise rather than independent noise | DP-FTRL versus DP-SGD · Mean estimation, asymptotic | suboptimality: Θ(ηρ^{-1} + η σ_SGD^2) -> Θ(η^2 ρ^{-1} log^2(1/η) + η σ_SGD^2) | Helped |
| Use prior-work correlations without damping (ν=0) (ablation) | Noisy-FTRL for linear regression · Linear regression, asymptotic | suboptimality: \infty | Hurt |
| Add damping to anti-PGD correlations (ablation) | Anti-PGD · Linear regression, asymptotic | suboptimality: \infty -> \eta^{3/2} G^2 \rho^{-1} \sqrt{d \, \tr{\bfH}} | Helped |
Surprising findings
- The optimal noise coefficients are anti-correlated, so the algorithm cancels previously injected noise.
- Noisy-FTRL's advantage over Noisy-SGD is exponential when the effective dimension is small.
Limitations
- Theoretical separation is proven for linear regression with Gaussian inputs; general convex case is only numerical via a convex program.
- Gradient clipping bias is handled only through a high-probability argument for finite horizon.
- DP-SGD can outperform DP-FTRL at small epsilon due to privacy amplification by sampling, which correlated-noise methods do not use.
Experimental setup
Datasets: CIFAR-10 StackOverflow
Benchmarks: CIFAR-10 StackOverflow
Metrics: accuracy asymptotic suboptimality
Baselines: DP-SGD Honaker/TreeAgg Optimal CC Multi-Epoch (ME) FFT Full Honaker
Builds on: DP-FTRL matrix mechanism DP-SGD Optimal CC (anytime correlated noise)
Closest papers by meaning
- Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML (ICLR 2025 · similarity 0.89)
- Certification for Differentially Private Prediction in Gradient-Based Training (ICML 2025 · similarity 0.88)
- The Privacy Power of Correlated Noise in Decentralized Learning (ICML 2024 · similarity 0.88)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.87)
- Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimization (AAAI 2025 · similarity 0.87)
- Differentially Private Stochastic Gradient Descent with Fixed-Size Minibatches: Tighter RDP Guarantees with or without Replacement (NeurIPS 2024 · 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.