Technical Summary: Convergent Differential Privacy Analysis for General Federated Learning

1. Problem Statement

Federated Learning (FL) combined with Differential Privacy (DP) offers a paradigm for training models on large-scale private client data without direct data leakage. However, existing theoretical analyses of FL-DP frameworks rely heavily on the composition theorem (e.g., $(\epsilon, \delta)$-DP or Rényi-DP). These traditional approaches typically yield privacy bounds that diverge (become arbitrarily loose) as the number of communication rounds $T$ increases.

This divergence implies a counterintuitive and empirically unsupported conclusion: that FL-DP frameworks may eventually lose all privacy protection capabilities under constant-level noisy perturbations during long-term training. This creates a significant discrepancy between theoretical predictions (suggesting inevitable privacy failure) and experimental results (which often show stable privacy). The core challenge lies in analyzing the privacy of FL methods with non-convex objectives and heterogeneous local updates, where multi-step local training introduces biased models that complicate standard sensitivity analysis.

2. Methodology

The authors propose a comprehensive analysis based on $f$-Differential Privacy ($f$-DP), specifically utilizing Gaussian Differential Privacy (GDP), which offers an information-theoretically lossless definition of privacy via the trade-off between Type I and Type II errors in hypothesis testing.

Key methodological components include:

• Shifted Interpolation Technique: To avoid the loose bounds associated with standard privacy amplification by iteration, the paper adopts a shifted interpolation sequence. Instead of analyzing the direct relationship between global models on adjacent datasets over $T$ rounds, the authors define an auxiliary sequence $\tilde{w}_t$ that interpolates between the trajectories of the two adjacent datasets. This allows for a tighter privacy amplification analysis over a specific interval $[t_0, T]$.
• Decomposition of Global Sensitivity: The global sensitivity term $\|\phi(w_t) - \phi'(\tilde{w}_t)\|$ is decomposed into two components:
  1. Data Sensitivity: The error resulting from training on different datasets starting from the same initialization.
  2. Model Sensitivity: The error resulting from training on the same dataset starting from different initializations.
     The authors derive specific bounds for these sensitivities under both Noisy-FedAvg and Noisy-FedProx algorithms.
• Optimization of Interpolation Coefficients: The privacy bound is formulated as a minimization problem over interpolation coefficients $\lambda_t$ and a starting round $t_0$. To ensure convergence, the authors relax the problem by setting $t_0 = 0$, eliminating the divergence caused by the initial stability gap while maintaining a tight bound on the accumulated sensitivity.
• Learning Rate Strategies: The analysis covers four distinct learning rate decay strategies: constant, cyclically decaying, stage-wise decaying, and iteratively decaying.

3. Key Contributions

The paper provides the first convergent privacy analysis for general FL-DP methods under non-convex and smooth objectives. The specific contributions are:

• Convergent Privacy for Noisy-FedAvg: The authors prove that the worst-case privacy of Noisy-FedAvg does not diverge with respect to the number of communication rounds $T$. They provide tight convergent bounds for four different learning rate decay strategies. This challenges the long-standing belief that privacy budgets must increase indefinitely with training duration.
• Stable Privacy for Noisy-FedProx: By analyzing the proximal term in Noisy-FedProx, the authors demonstrate that the worst privacy converges to a general constant lower bound. They show that the proximal coefficient $\alpha$ acts as a regularizer that can decouple privacy from the local training interval $K$, provided $\alpha > L$ (where $L$ is the smoothness constant).
• Framework Agnosticism: The derived $f$-DP bounds can be losslessly converted to other standard frameworks, including $(\epsilon, \delta)$-DP and Rényi-DP (RDP), providing fine-grained understandings for existing FL-DP systems.
• Theoretical Resolution of Discrepancy: The analysis resolves the gap between theoretical divergence and empirical stability, demonstrating that constant-level noise is sufficient to maintain convergent privacy guarantees in FL.

4. Results

The theoretical findings are summarized in Table 1 and Table 3 of the paper:

• Noisy-FedAvg:
  • Under constant learning rates, the privacy bound converges to a value dependent on $K$, $m$ (client scale), and $\sigma$ (noise), but remains bounded as $T \to \infty$.
  • Under stage-wise and iteratively decaying learning rates, the privacy bound converges to a form proportional to $\sqrt{2 - 1/T}$, ensuring convergence.
  • The bounds are tighter than previous works which often required noise variance $\sigma^2$ to scale with $T$ or $TK$.
• Noisy-FedProx:
  • The privacy bound converges to a constant lower bound independent of $T$ and $K$.
  • The bound is inversely proportional to $\sqrt{\alpha}$, indicating that a larger proximal coefficient $\alpha$ significantly improves privacy (reduces sensitivity) without requiring increased noise.
• Empirical Validation:
  • Experiments on MNIST and CIFAR-10 with LeNet-5 and ResNet-18 confirm that global sensitivity stabilizes as training progresses, regardless of $T$ or $K$.
  • Sensitivity studies show that increasing the number of clients ($m$) reduces sensitivity ($O(1/\sqrt{m})$), while the local interval $K$ affects the convergence rate but not the asymptotic bound.
  • Membership inference and gradient inversion attacks confirm that attack success rates stabilize rather than approaching 100% under constant noise, validating the convergent privacy theory.

5. Significance

The paper claims to establish a solid theoretical foundation for the reliability of privacy in FL-DP frameworks. Its significance lies in:

1. Correcting Theoretical Misconceptions: It refutes the inference that FL-DP inevitably loses privacy protection over long-term training under constant noise, aligning theory with empirical observations.
2. Enabling Long-Term Training: By proving convergent bounds, the work suggests that FL systems can operate for extended periods without requiring unbounded increases in noise intensity, which would otherwise degrade model utility.
3. Optimization-Privacy Trade-off: The analysis of Noisy-FedProx reveals that local regularization (the proximal term) can serve as a mechanism to achieve a "win-win" solution, improving both optimization stability and privacy guarantees simultaneously.
4. Design Guidance: The results provide actionable insights for designing FL systems, such as the benefits of larger client scales and the strategic selection of learning rate decay and proximal coefficients to maximize privacy without compromising convergence.

The authors conclude that their work fills a critical theoretical gap, demonstrating that properly structured local and global interactions in FL can preserve rigorous privacy assurances without fundamentally compromising the learning framework.