Adaptive Methods Are Preferable in High Privacy Settings: An SDE Perspective

AI summary

Overview

Research area: Machine learning / differentially private optimization — specifically, how privacy noise interacts with adaptive versus non-adaptive optimizers, analyzed through stochastic differential equations (SDEs).

Technical level: Advanced. The paper relies on SDE weak approximations, (ε, δ)-differential privacy, μ-PL and L-smoothness assumptions, per-example clipping, and heavy-tailed (Student-t) noise models with explicit convergence bounds.

Scope: A theoretical and empirical comparison of DP-SGD and DP-SignSGD (used as a proxy for DP-Adam) under per-example clipping, characterizing how the privacy budget ε controls convergence speed and the privacy-utility trade-off under two hyperparameter-tuning protocols.

What This Paper Is About

Training with differential privacy injects calibrated noise into gradients, which changes optimization dynamics in ways that are not fully understood. The paper asks which privacy regimes favor adaptive optimizers over non-adaptive ones, and whether the noise added for privacy damages them differently. Using SDE approximations — which prior work applied only to non-private optimizers — the authors derive how the privacy budget ε enters the decay rate and the asymptotic loss floor of DP-SGD versus DP-SignSGD.

Key Contributions

1. First SDE-based analysis of DP optimizers. The authors derive SDE models for DP-SGD (Theorem B.9) and DP-SignSGD (Theorem B.14), and provide what they describe as the first stationary distributions for these optimizers (Theorem B.13 and Theorem B.21). The framework exposes how DP noise interacts with adaptivity and batch noise.

2. Protocol A (fixed hyperparameters), non-adaptive case. DP-SGD converges at a speed independent of ε, with a privacy-utility trade-off scaling as O(1/ε²). This holds for both the loss (Theorem 4.1, μ-PL and L-smooth, in clipped and unclipped phases) and the expected gradient norm (Theorem 4.2, L-smooth).

3. Protocol A, adaptive case. DP-SignSGD has convergence speed scaling linearly in ε, with a privacy-utility trade-off of O(1/ε) in both loss (Theorem 4.3) and gradient norm (Theorem 4.4). Theorem 4.5 shows DP-SignSGD always dominates when σ_γ² ≥ B, and for σ_γ² < B there exists a critical privacy level ε* below which DP-SignSGD is preferable.

4. Protocol B (best-tuned per ε). The optimal learning rate of DP-SGD scales linearly with ε (η* ∝ ε), while that of DP-SignSGD is ε-independent. Under these choices the two methods reach comparable asymptotic performance, but the adaptive method's hyperparameters transfer across privacy levels.

5. Empirical validation. All theoretical insights are tested on real tasks, and the qualitative behavior is shown to extend from training to test loss, and from DP-SignSGD to DP-Adam.

Main Findings

• Speed of DP-SGD is privacy-independent. In Theorem 4.1, the decay terms do not contain ε; the paper notes that when DP-SGD does not diverge, its convergence speed is unaffected by ε (Figure 2).

• DP-SGD's utility degrades as O(1/ε²). The privacy-utility term scales as 1/ε² in the high-privacy regime in both Phase 1 (all gradients clipped) and Phase 2 (no gradients clipped), and the same O(1/ε²) scaling appears in the gradient norm bound (Theorem 4.2).

• DP-SignSGD's speed scales linearly in ε. Unlike DP-SGD, the decay rate of DP-SignSGD is proportional to ε in both phases (Eq. 8 and Eq. 9), but its privacy-utility term scales as O(1/ε).

• A critical privacy threshold ε*. Theorem 4.5 states that if σ_γ² ≥ B, DP-SignSGD always achieves a better privacy-utility trade-off than DP-SGD. If σ_γ² < B, there is a critical level ε* = sqrt(C²TB / (n²(B − σ_γ²)) · log(1/δ)) such that DP-SignSGD outperforms DP-SGD whenever ε < ε*.

• Larger batch noise shifts the threshold. Figure 3 shows that as batch size B increases, ε* shifts to the left — less privacy noise is needed for DP-SignSGD to become preferable.

• Optimal learning rates differ sharply. Theorem 4.6 gives the optimal learning rate for DP-SGD, whose ε-dependent branch scales linearly in ε; DP-SignSGD's is essentially ε-independent (Theorem 4.7, referenced in Figure 4).

• Hyperparameter sweeps can hurt DP-SGD. Figure 4 reports that failing to sweep over the "best" range of learning rates causes DP-SGD to severely underperform, because the optimal η flattens out at small ε; re-running the sweep with a larger grid (DP-SGD Tuned) recovers the scaling law and matches adaptive methods.

• Empirical scaling validation. On a quadratic convex function f(x) = ½xᵀHx, empirical loss values match the theoretical predictions of Eq. 6 and Eq. 9. Logistic regressions on IMDB and StackOverflow confirm that DP-SGD utility scales as 1/ε² while DP-SignSGD scales as 1/ε.

• The insights transfer. The same patterns are observed for DP-Adam and on test loss (Figures C.7 and C.8).

Methodology in Plain English

Rather than analyzing the discrete optimizer steps directly, the authors replace each optimizer with a continuous-time SDE that behaves like the original in distribution, up to an error that shrinks as the learning rate is raised to a power (Definition 3.1). This "weak approximation" approach — adapted from numerical analysis of SDEs and previously used for non-private optimizers — makes it tractable to write down how the drift (deterministic descent) and diffusion (noise) terms depend on the privacy budget.

The DP setup follows the standard recipe: at each iteration, a mini-batch is drawn, per-example gradients are clipped to a norm bound C, and Gaussian noise scaled by σ_DP is added to the averaged clipped gradients. The privacy noise multiplier is written as σ_DP = √T Φ / ε, where Φ := q√(log(1/δ)) and q = B/n, so ε enters the analysis explicitly. Because a batch may mix clipped and unclipped examples, the authors first analyze two idealized phases — all clipped, then none clipped — and then treat the mixed case in Theorem B.12. Unclipped batch noise is modeled as Gaussian scaled by σ_γ/√B; per-example (B = 1) noise is modeled as Student-t with ν degrees of freedom, recovering the Gaussian as ν → ∞.

The sign operator is approximated analytically in Lemma A.2 under two conditions: parameter dimension d = Ω(10⁴) and a signal-to-noise ratio ‖∇f(x)‖²/(2σ_γ²) ≪ d that prior empirical work reports never exceeds O(10²). Experiments use the DP2 GitHub repository released with Li et al. (2023), and cover a quadratic convex function, plus logistic regression on IMDB and StackOverflow, with batch sizes B ∈ {48, 56, 64, 72, 80} in the threshold experiment (Figure 3).

The two protocols structure the comparison. Protocol A fixes hyperparameters (η, C, B, …) chosen by grid search at one ε and then varies ε, isolating its effect. Protocol B re-tunes (η, C) for every ε, isolating the intrinsic scaling of the optimal learning rates.

Why This Matters

Impact on research. Prior work has left open which of DP-SGD and DP-Adam performs best and in which regimes, with conflicting observations: the performance gap narrows under DP constraints and essentially vanishes when both optimizers are carefully tuned (as reported for large-scale LLM fine-tuning in Li et al., 2022b, App. S), while non-adaptive methods are sometimes still preferred in vision tasks. This paper offers a structural explanation — the two families respond to privacy noise differently, so the answer depends on ε and on batch noise — and it introduces SDEs as a tool for private optimization analysis.

Real-world applications:

• Private training of models on sensitive records in healthcare, where the paper notes even disclosing a single training example can have serious consequences.
• Conversational agents and other user-data-driven systems subject to privacy regulation.
• LLM fine-tuning under differential privacy, where hyperparameter search itself consumes privacy budget (Papernot and Steinke, 2022) and re-tuning per privacy level is costly.
• Deployment contexts where regulators require a specified privacy budget, making it valuable that adaptive methods' hyperparameters transfer across ε.

Industry relevance. Privacy regulation is tightening — the US Executive Order of October 30, 2023, NIST draft guidance SP 800-226 and the AI RMF 1.0, the EU AI Act, and ENISA recommendations are all cited. The practical argument is that DP-SGD needs an ε-dependent learning rate tuned ad hoc and is brittle if the sweep grid misses the right value, whereas adaptive methods need little or no re-tuning and each avoided sweep also saves privacy budget.

Future Directions

• Extending the SDE analysis to more advanced DP optimizers. The paper explicitly leaves this to future work, noting each optimizer would require a separate technical treatment, and develops the theory for DP-SignSGD as a tractable proxy for DP-Adam.
• Formally analyzing DP-Adam rather than only validating it empirically, since the empirical extension from DP-SignSGD to DP-Adam is reported but not derived.
• Relaxing the standing assumptions — the large-dimension condition d = Ω(10⁴), the signal-to-noise restriction ‖∇f(x)‖²/(2σ_γ²) ≪ d, and the μ-PL / L-smoothness requirements — to test how far the conclusions extend.
• Understanding the remaining gap in tuning practice: identifying how to select the sweep range for DP-SGD so the ε-dependent optimal learning rate is not missed, given the paper's finding that a missed grid causes severe underperformance.

Target Audience

Researchers and graduate students in optimization theory and privacy-preserving machine learning; practitioners implementing DP-SGD or DP-Adam at scale who must decide how much hyperparameter tuning budget to spend; and readers familiar with differential privacy and stochastic optimization who want a rigorous, SDE-based account of when adaptivity pays off.

Note: The provided paper content is truncated mid-sentence within the statement of Theorem 4.6, so the full optimal-learning-rate results of Protocol B — including the complete statements of Theorem 4.7 and the final asymptotic expressions — are not fully reported in the available text.

Authors’ abstract

Differential Privacy (DP) is becoming central to large-scale training as privacy regulations tighten. We revisit how DP noise interacts with adaptivity in optimization through the lens of stochastic differential equations, providing the first SDE-based analysis of private optimizers. Focusing on DP-SGD and DP-SignSGD under per-example clipping, we show a sharp contrast under fixed hyperparameters: DP-SGD converges at a Privacy-Utility Trade-Off of $\mathcal{O}(1/\varepsilon^2)$ with speed independent of $\varepsilon$, while DP-SignSGD converges at a speed linear in $\varepsilon$ with an $\mathcal{O}(1/\varepsilon)$ trade-off, dominating in high-privacy or large batch noise regimes. By contrast, under optimal learning rates, both methods achieve comparable theoretical asymptotic performance; however, the optimal learning rate of DP-SGD scales linearly with $\varepsilon$, while that of DP-SignSGD is essentially $\varepsilon$-independent. This makes adaptive methods far more practical, as their hyperparameters transfer across privacy levels with little or no re-tuning. Empirical results confirm our theory across training and test metrics, and empirically extend from DP-SignSGD to DP-Adam.