PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentially Private Federated Learning on Heterogeneous Data

Maxence Noble, Aurélien Bellet, Aymeric Dieuleveut

arXiv:2111.09278v3cs.LGcs.CRmath.ST

TL;DR

Federated learning needs to handle heterogeneous user data while protecting privacy from both servers and outsiders. The paper introduces DP-SCAFFOLD, analyzes its privacy-utility behavior, and reports superiority over DP-FedAvg as local updates and heterogeneity increase. Experiments support these theoretical findings.

  • Problem

    Existing federated-learning methods addressed data heterogeneity and differential privacy separately, leaving their combined privacy-utility trade-off insufficiently studied.

  • Method

    DP-SCAFFOLD augments SCAFFOLD with noisy local updates and analyzes privacy and convergence for convex and non-convex objectives.

  • Results

    DP-SCAFFOLD outperforms DP-FedAvg under high data heterogeneity and many local updates, with experiments confirming significant practical gains.

  • Takeaways & Limitations

    Control variates remain effective under differential privacy and help DP-SCAFFOLD overcome DP-FedAvg’s limitations under heterogeneity and many local updates.

  • Takeaways & Limitations

    The privacy analysis using strong composition can be sub-optimal, while the paper’s experiments use tighter RDP bounds for noise calibration.

Abstract

from arXiv · show

Federated Learning (FL) is a paradigm for large-scale distributed learning which faces two key challenges: (i) efficient training from highly heterogeneous user data, and (ii) protecting the privacy of participating users. In this work, we propose a novel FL approach (DP-SCAFFOLD) to tackle these two challenges together by incorporating Differential Privacy (DP) constraints into the popular SCAFFOLD algorithm. We focus on the challenging setting where users communicate with a "honest-but-curious" server without any trusted intermediary, which requires to ensure privacy not only towards a third-party with access to the final model but also towards the server who observes all user communications. Using advanced results from DP theory, we establish the convergence of our algorithm for convex and non-convex objectives. Our analysis clearly highlights the privacy-utility trade-off under data heterogeneity, and demonstrates the superiority of DP-SCAFFOLD over the state-of-the-art algorithm DP-FedAvg when the number of local updates and the level of heterogeneity grow. Our numerical results confirm our analysis and show that DP-SCAFFOLD provides significant gains in practice.

1 INTRODUCTION

Federated learning must address heterogeneous user data and privacy simultaneously, yet prior work largely treated these challenges separately. DP-SCAFFOLD combines differential privacy with SCAFFOLD to protect against both curious servers and third parties while improving performance under heterogeneity.

  • Heterogeneous user data can prevent convergence or require many communication rounds, creating a major federated-learning bottleneck.
  • Prior methods addressed heterogeneity and differential privacy separately, leaving their combined privacy-utility trade-off insufficiently studied.
  • DP-SCAFFOLD adds noise to SCAFFOLD local model updates to protect user data from an honest-but-curious server and a third party.
  • The paper provides privacy and utility analysis for DP-SCAFFOLD and DP-FedAvg in both convex and non-convex regimes.
  • DP-SCAFFOLD outperforms DP-FedAvg when local updates or data heterogeneity are large, with experiments confirming significant practical gains.

2 RELATED WORK

Federated-learning research has developed separate responses to heterogeneity and privacy, but the combined setting remains underexplored. Differential privacy formalizes information leakage, while existing DP-FL methods leave important heterogeneity trade-offs unresolved.

  • Federated learning & heterogeneity: FedAvg can suffer instability and convergence problems under heterogeneous or non-identically distributed user data because of user-drift.
  • Federated learning & heterogeneity: SCAFFOLD corrects user-drift using control variates, while related methods such as MIME and FedDyn involve costly or nontrivial adaptations.
  • Federated learning & differential privacy: Differential privacy quantifies information leakage with respect to neighboring datasets, which may differ by one user or one record.
  • Federated learning & differential privacy: Gaussian mechanisms add noise calibrated to sensitivity, and privacy guarantees for iterative procedures are obtained through composition.
  • Federated learning & differential privacy: Server-side noise protects against third parties in DP-FedAvg and DP-FedSGD, but prior work did not fully characterize utility-privacy trade-offs with multiple local updates.
  • Summary: The paper identifies no prior FL approach designed for data heterogeneity under differential privacy or for analyzing that trade-off.

3 DP-SCAFFOLD

The paper studies record-level privacy in federated empirical-risk minimization with independently sampled, heterogeneous local datasets. Its framework combines user and data subsampling, clipping, and Gaussian noise to protect shared updates.

  • Federated Learning Framework: The framework has a central server and M users, each holding a private local dataset sampled from a distinct distribution.
  • Federated Learning Framework: Training minimizes an empirical-risk objective built from user-specific losses and averaged mini-batch gradients.
  • Privacy setting: Privacy is defined at record level, with neighboring federated datasets differing by at most one record.
  • Privacy setting: The analysis protects against both a third party observing the final model and an honest-but-curious server observing exchanged updates.
  • DP-SCAFFOLD: The algorithm begins from server and user control-variate inputs and applies user subsampling, data subsampling, and noisy local gradients.

17 User i sends to server (∆yt

DP-SCAFFOLD performs multiple private local updates per communication round while maintaining server- and user-side control variates. Its transmitted updates provide privacy through composition and postprocessing, and warm-starting adapts initialization to the DP setting.

  • DP-SCAFFOLD: Each round samples users, who download the global model and perform K local updates before communicating with the server.
  • Control variates: Server- and user-side control variates correct user-drift by balancing local stochastic gradients.
  • Privacy: Privacy analysis uses composition across rounds, while RDP bounds calibrate σg more tightly in experiments.
  • Private local updates: Users sample mini-batches, clip gradients, and add Gaussian noise calibrated to sensitivity and the privacy scale σg.
  • Privacy: The transmitted model and control-variate updates are private, making the resulting global state private by postprocessing.
  • Warm-start variant: The warm-start variant initializes control variates with perturbed information and requires randomly sampled users for privacy.

4 THEORETICAL ANALYSIS

The analysis establishes privacy guarantees and utility bounds for DP-SCAFFOLD and DP-FedAvg, then characterizes how heterogeneity, local updates, privacy accounting, and initialization affect convergence. It shows that DP-SCAFFOLD is advantageous under heterogeneous data and benefits from more local updates without degrading its privacy bound.

  • Privacy guarantees: DP-SCAFFOLD and DP-FedAvg have the same privacy level at each round after server aggregation for a fixed noise scale.Theorem 4.1 gives the same noise-scale order for both algorithms toward the server and a third party.
  • Privacy guarantees: The privacy analysis uses subsampled Gaussian mechanisms, Rényi DP, composition across local iterations and communication rounds, and parameter inversion to calibrate noise for a target privacy budget.The analysis accounts for both data subsampling and user subsampling before converting the bound into a noise scale.
  • Utility bounds: The utility bounds separate classical optimization, a heterogeneity penalty for DP-FedAvg, and an additional differential-privacy term.The privacy term grows with the number of iterations, decreases with the total number of records, grows sublinearly with model dimension, and increases inversely with ε.
  • Utility bounds: DP-SCAFFOLD outperforms DP-FedAvg when the number of local updates is large and/or data heterogeneity is high.The DP-FedAvg heterogeneity term does not decrease with the number of local iterations, whereas the corresponding DP-SCAFFOLD optimization bound improves with local updates.
  • Utility bounds: Increasing local updates K benefits DP-SCAFFOLD by improving its dominant optimization bound without degrading the privacy bound.The paper reports that this theoretical behavior is confirmed numerically.
  • Scope and limitations: The theoretical result for DP-SCAFFOLD requires the warm-start version, although experiments observed the same results for standard DP-SCAFFOLD with zero initial control variates.The authors also note that directly using the prior initialization result would require allocating a large fraction of the privacy budget to initialization and performed poorly experimentally.

5 EXPERIMENTS

Experiments evaluate DP-SCAFFOLD across synthetic and real-world federated classification settings, varying heterogeneity, local updates, privacy, and sampling. DP-SCAFFOLD consistently outperforms private FedAvg baselines under heterogeneous data, while its utility depends on the trade-off among communication rounds, local updates, and noise.

  • Experimental setup: Experiments use logistic regression for synthetic and real-world data, plus a one-hidden-layer DNN on real-world data.Synthetic heterogeneity is controlled by α and β; EMNIST/FEMNIST heterogeneity is controlled by γ.
  • Superiority of DP-SCAFFOLD: DP-SCAFFOLD clearly outperforms DP-FedAvg and DP-FedSGD in both convex and non-convex settings under heterogeneous data.The performance gap increases as the number K of local updates grows.
  • Parameter trade-offs: 22% accuracy is reached with K = 40 because T cannot exceed 90 under the privacy constraint.Conversely, too few local updates prevent DP-SCAFFOLD from converging despite a high T.
  • Parameter trade-offs: Lower σg can improve performance, but it requires choosing a smaller T; σg = 10 and σg = 20 yield similar accuracy because σg and T compensate.The experiments examine these trade-offs under a fixed privacy budget.

6 CONCLUSION

The paper concludes that DP-SCAFFOLD improves over DP-FedAvg theoretically and empirically for heterogeneous federated learning under differential privacy. It identifies parameter trade-offs and several directions for extending the method and experiments.

  • Conclusion: DP-SCAFFOLD addresses data heterogeneity under differential privacy and improves over DP-FedAvg from theoretical and empirical perspectives.The paper’s analysis identifies a heterogeneity term in DP-FedAvg’s rate that does not appear in DP-SCAFFOLD’s rate.
  • Future work: Future work includes more deep-learning experiments, varied local-dataset sizes, momentum, improved tuning of T, K, and subsampling, and personalized federated learning.The paper also notes that formal privacy guarantees have seldom been studied in personalized FL.
  • Experiments: Figure 1 reports synthetic-data train loss for ϵ = 13, with K = 50 in the first row and K = 100 in the second.The figure is part of the empirical comparison of algorithms under varying local updates.
  • Experiments: Figure 2 reports test accuracy with K = 50 for FEMNIST logistic regression at ϵ = 11.4 and MNIST DNN at ϵ = 7.2.The caption distinguishes the FEMNIST and MNIST settings by row.

Supplementary Material: Differentially Private Federated Learning on Heterogeneous Data

The supplementary material supplies notation, privacy background, algorithms, and proof resources for the paper’s differential-privacy analysis. It reviews composition, subsampling amplification, RDP, Gaussian mechanisms, and conversions between RDP and standard DP.

  • Supplement organization: The supplement organizes notation, DP-FedAvg details, privacy analysis, utility proofs, and additional experiments across appendices A–D.Appendix C covers convex, strongly convex, and non-convex utility proofs.
  • Privacy background: Differential privacy supports adaptive composition, allowing privacy guarantees to be tracked across iterative mechanisms run on the same dataset.The sequence of mechanisms may choose auxiliary inputs based on previous outputs.
  • Privacy amplification: Subsampling without replacement amplifies privacy guarantees when a private mechanism is applied to a uniformly selected subset.The supplement states the corresponding amplification lemma for a mechanism composed with subsampling.
  • Privacy analysis: The privacy analysis uses composition and subsampled Gaussian-mechanism results, with the cumulant generating function providing a route to RDP bounds.The supplement relates the CGF to RDP and uses Gaussian and subsampled Gaussian mechanisms as supporting results.
  • Rényi differential privacy: RDP generalizes differential privacy using Rényi divergence, and RDP guarantees can be converted into standard (ϵ, δ)-DP guarantees.The conversion adds log(1/δ)/(α−1) to the RDP parameter.

B.3 Proof of Claim 4.1

The proof of Claim 4.1 establishes that DP-SCAFFOLD and DP-FedAvg have matching privacy levels toward both the server and a third party. The argument uses adaptive composition and post-processing across communication rounds.

  • Claim setup: For any communication round t, the formal claim compares privacy of truncated DP-SCAFFOLD and DP-FedAvg outputs.The subalgorithms reveal outputs either to the server or to a third party.
  • Privacy toward the server: DP-SCAFFOLD and DP-FedAvg have the same level of privacy toward the server.The proof proceeds by induction over communication rounds and accounts for the server-known sampling and control variates.
  • Privacy toward a third party: DP-SCAFFOLD and DP-FedAvg have the same level of privacy toward a third party.The third-party outputs are analyzed through the corresponding truncated algorithms and adaptive composition.
  • Proof strategy: The induction starts at t = 1, where DP-SCAFFOLD’s privacy is determined by the privacy of the DP-FedAvg user updates.The argument then extends the equality through later rounds using post-processing and the privacy of DP-noised stochastic-gradient averages.
  • Proof strategy: DP-SCAFFOLD’s control-variate updates depend on DP-noised local gradients, so they do not introduce additional privacy loss beyond the analyzed user updates.This is the key post-processing step in the server-side induction.

B.4 Proof of Theorem 4.1

The privacy proof composes local data subsampling, noisy aggregation, user subsampling, and repeated communication to establish differential-privacy guarantees for both an external observer and the honest-but-curious server.

  • Privacy toward the server: The analysis first bounds privacy loss from each user’s K adaptively subsampled local mechanisms and then composes these contributions through server aggregation.Local gradient sensitivity and Gaussian noise calibration determine the per-user RDP bound; aggregation reduces sensitivity relative to an individual contribution.
  • Privacy toward a third party: The aggregation mechanism obtains an (ϵa(α, δ′), δ′)-DP guarantee with respect to the joint dataset D.The bound follows after converting the aggregated RDP result into a differential-privacy bound.
  • Privacy toward a third party: User subsampling amplifies privacy, after which composition over T rounds yields the final privacy bound (O(ϵT), Tlδ′ + δ′′)-DP.The amplification and composition steps use classical privacy tools, although the resulting bounds are described as sub-optimal for practical implementations.
  • Privacy toward a third party: The noise scale can be chosen from a target privacy budget to prove (O(ϵ), δ)-DP toward a third party observing only the final output.The proof fixes δ′ and δ′′ as portions of the final privacy budget before inverting the bound.
  • Approximation: Without approximation, the third-party privacy minimization problem must be solved numerically rather than through the simpler analytic bound.The exact minimization is explicitly identified as much more complex.
  • Privacy toward the server: Removing aggregation and user-subsampling amplification gives (O(ϵs), δs)-DP toward the honest-but-curious server.This distinction reflects that the server observes individual contributions and knows which users are sampled.

C.2 Theorem of Convergence for DP-SCAFFOLD-warm

The theorem establishes utility rates for DP-SCAFFOLD-warm under strongly convex, convex, and non-convex local objectives, using weighted or randomized outputs under stated step-size conditions.

  • Theorem C.1: Theorem C.1 analyzes DP-SCAFFOLD-warm with arbitrary Gaussian-gradient noise under the paper’s regularity assumptions and initialization conditions.The result is parameterized by T, K, l, s, σg, and C.
  • Strongly convex objectives: For strongly convex objectives, a weighted average of iterates has an expected excess-loss guarantee under suitable global and local step sizes.The theorem assumes µ-strong convexity and specifies ηg and an upper bound on ηl.
  • Non-convex objectives: For non-convex objectives, a randomized iterate has a bound on the expected squared gradient of the loss under suitable step-size and iteration conditions.The randomized output selects x_t with probabilities given by the theorem’s weights.
  • Convex objectives: The convex-objective result is recovered by selecting σg = σ∗M, with numerical constants omitted from the asymptotic expression.This specializes the arbitrary-noise theorem to the paper’s preferred noise choice.

C.3 Proof of Theorem C.1 (Convex case)

The convex-case proof builds a contraction inequality by controlling update variance, control-variate lag, and user drift, then derives convergence for DP-SCAFFOLD-warm and compares it with DP-FedAvg rates.

  • Proof strategy: The proof combines squared distance to the optimum, excess loss, and control-variate lag rather than the control deviation used in the original SCAFFOLD proof.The authors state that this choice avoids a worse utility upper bound caused by privacy noise or heterogeneity.
  • Proof strategy: The contraction analysis controls server-update variance, control lag across communication rounds, and user drift.These components are assembled into a contraction inequality involving the main optimization and noise terms.
  • DP-SCAFFOLD-warm convergence: Lemma C.8 establishes convergence of DP-SCAFFOLD-warm for convex local loss functions, with separate strongly convex and merely convex cases.The proof unrolls a contraction in the strongly convex case and averages the contraction inequality when µ = 0.
  • Comparison baselines: The analysis also derives convergence for non-convex loss functions and utility rates for DP-FedAvg under the same general framework.The DP-FedAvg result combines a prior convergence theorem with the variance bound for DP-noised stochastic gradients.

D.3.1 Results with other metrics and different heterogeneity levels

Additional experiments evaluate accuracy, gradient dissimilarity, and training loss across heterogeneity settings, datasets, and privacy budgets. DP-SCAFFOLD-warm consistently outperforms DP-FedAvg, while fixed-budget performance depends on the balance among communication rounds, local updates, noise, and sampling.

  • Synthetic data: DP-SCAFFOLD-warm averages 10% higher accuracy than DP-FedAvg across synthetic-data heterogeneity settings.Its accuracy variance is also unaffected by heterogeneity, whereas DP-FedAvg’s variance grows.
  • Synthetic data: DP-SCAFFOLD-warm converges better than DP-FedAvg on synthetic data according to train gradient dissimilarity.
  • Synthetic data: DP-SCAFFOLD-warm consistently performs better when either model heterogeneity α or data heterogeneity β varies.The comparisons use train loss on synthetic data under ϵ = 13.
  • FEMNIST data: DP-SCAFFOLD-warm again shows superior performance on FEMNIST for both test accuracy and train gradient dissimilarity.The comparison includes K = 50 and K = 100 local updates.
  • Trade-offs: Under a fixed privacy budget, choosing K too low or too large makes DP-SCAFFOLD performance sub-optimal.Few local updates make control variates inefficient, while large K forces T to be too low.
  • Trade-offs: Increasing σg does not necessarily increase communication rounds, because the privacy bound can stop improving at high noise levels.For σg above 80 in the reported setting, lower sampling ratios would be needed to obtain different T values.

D.3.3 Experiments under higher privacy regime and role of sampling parameters

Experiments under higher privacy examine DP-SCAFFOLD against DP-FedAvg across datasets and sampling choices. DP-SCAFFOLD retains a substantial advantage under high heterogeneity, while lower sampling ratios can improve accuracy by permitting more communication rounds.

  • Higher privacy: The advantage of DP-SCAFFOLD is especially strong as heterogeneity and the number K of local updates increase.This pattern preserves the non-private SCAFFOLD-over-FedAvg hierarchy within the differentially private setting.
  • Higher privacy: DP-SCAFFOLD outperforms DP-FedAvg in high-privacy regimes across synthetic, FEMNIST, and MNIST experiments.The reported accuracy gaps reach 20% for synthetic and FEMNIST settings and 10% for MNIST under specified heterogeneity conditions.
  • User sampling: A user-sampling ratio l = 0.08 produced the best reported performance while allowing a larger number of communication rounds.This was the lowest sampling ratio considered, and accuracy evolved similarly across the tested l values.
  • Data sampling: DP-SCAFFOLD remains better than DP-FedAvg across data-sampling ratios s ∈ {0.2, 0.1, 0.05} under heterogeneity.For FEMNIST with 10% similarity, the accuracy gap fell from 30% at s = 0.2 to less than 20% at s = 0.1.
Loading 2111.09278v3…