DP-FedAvg (Differentially Private Federated Averaging)

This is the first critical step to bound sensitivity. Before sending its local model update (e.g., the gradient or weight delta) to the server, each client clips the L2 norm of its update vector to a pre-defined clip threshold C. This ensures no single client's update can have an arbitrarily large influence, which is necessary to calibrate the noise addition. The operation is: update_clipped = update * min(1, C / ||update||_2).

After clipping, each client adds noise sampled from a Gaussian (Normal) distribution to its update. The scale (standard deviation) of this noise is proportional to the clip threshold C and the privacy parameters (ε, δ). This mechanism provides (ε, δ)-differential privacy at the client level. The noise ensures that from the server's perspective, the aggregated update is statistically indistinguishable whether any single client participated or not.

DP-FedAvg's formal guarantee protects the entire data contribution of a single client (device/user), not individual data points within that client's dataset. The guarantee states that the probability of any output (the final global model or an intermediate aggregate) changes by at most a factor of e^ε (plus a small δ) if any one client's local dataset is added or removed. This granularity is natural for federated learning, where each device is considered a single privacy entity.

Training a model requires hundreds of communication rounds. DP-FedAvg uses composition theorems (like Rényi DP or the Moment Accountant) to track the cumulative privacy loss (ε, δ) across all training rounds. This ensures the total privacy budget is not exceeded. The accounting is typically managed by the central server, which informs clients of the noise scale required for each round to stay within the overall budget.

DP-FedAvg is fundamentally compatible with cryptographic secure aggregation protocols. The sequence is: 1) Clients clip updates locally, 2) Clients add differential privacy noise locally, 3) Clients encrypt their noised updates, 4) The server performs secure aggregation to decrypt only the sum of all noised updates. This combination provides a defense-in-depth privacy approach: cryptography protects against a malicious server, while DP protects against inference from the final model.

The algorithm exposes key hyperparameters that directly control the trade-off between final model accuracy (utility) and privacy strength:

• Clip Threshold (C): A low C increases bias but allows for less noise; a high C reduces clipping bias but requires more noise.
• Privacy Budget (ε, δ): A smaller ε (stronger privacy) requires more noise, typically reducing model convergence speed and final accuracy.
• Number of Clients per Round: Sampling more clients per round can provide privacy amplification, allowing for less noise per client for the same overall guarantee.

Differential privacy is a rigorous mathematical framework for quantifying and limiting the privacy loss incurred by an individual when their data is used in a computation. It provides a strong, worst-case guarantee: the presence or absence of any single data point in the input dataset must not substantially change the probability distribution of the algorithm's output.

• Formal Guarantee: An algorithm M is (ε, δ)-differentially private if for any two adjacent datasets D and D' differing by one element, and for any subset of outputs S: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S] + δ.
• Key Property: It offers post-processing immunity—any analysis performed on a differentially private output cannot weaken the original guarantee.

Federated Averaging is the foundational algorithm for federated learning, enabling model training across decentralized devices without exchanging raw data. Clients perform multiple steps of local stochastic gradient descent on their private data and send only the resulting model updates (e.g., weight deltas) to a central server for secure averaging.

• Core Process: 1) Server broadcasts global model. 2) Selected clients train locally. 3) Clients send model updates. 4) Server aggregates updates via weighted average. 5) Server updates global model.
• Key Challenge: It operates under system constraints like partial client participation, non-IID data distributions, and unbalanced datasets across devices.

The Gaussian mechanism is the primary algorithm used in DP-FedAvg to achieve (ε, δ)-differential privacy. It adds calibrated Gaussian noise to a function's output, where the noise scale (standard deviation) is proportional to the function's L2 sensitivity and the desired privacy parameters (ε, δ).

• Mathematical Form: For a function f with L2 sensitivity Δ₂f, the mechanism releases f(D) + N(0, σ²I), where σ = Δ₂f * √(2log(1.25/δ)) / ε.
• Application in DP-FedAvg: After gradient clipping bounds the L2 sensitivity of the client's model update, Gaussian noise is added to the clipped update before it is sent to the server for noisy aggregation.

Gradient clipping is a mandatory preprocessing step in differentially private optimization that bounds the influence of any individual training example or client. It enforces a maximum norm (L2 or L1) on the computed gradient or model update, which directly defines the sensitivity required for noise addition.

• Process: For an update vector g, the clipped update is g / max(1, ||g||₂ / C), where C is the clip threshold. This ensures ||g_clipped||₂ ≤ C.
• Trade-off: The clip threshold C is a critical hyperparameter. A small C increases privacy (less noise needed) but introduces bias; a large C reduces bias but requires more noise to maintain the same privacy guarantee, harming utility.

Client-level differential privacy is the specific granularity of protection guaranteed by DP-FedAvg. An adjacent dataset in this context is defined as two sets of participating clients that differ by the addition or removal of one entire client's data. The algorithm ensures that the released global model does not reveal whether any specific client participated in the training.

• Contrast with Example-Level DP: Standard DP-SGD often provides example-level privacy within a centralized dataset. Client-level DP is stronger and more appropriate for federated learning, as it protects all data points belonging to a single user or device.
• Implication: The sensitivity calculation and noise addition in DP-FedAvg are scaled to the maximum possible contribution from one client, not one data point.

Privacy accounting is the process of precisely tracking the cumulative privacy loss (ε, δ) across multiple training rounds in DP-FedAvg. Because each communication round consumes a portion of the total privacy budget, advanced composition theorems are required to compute the final guarantee.

• Methods: Simple sequential composition provides a loose bound. Tighter accounting is achieved using the moment accountant (used in DP-SGD) or frameworks like Rényi Differential Privacy (RDP) and Zero-Concentrated DP (zCDP).
• Amplification by Subsampling: In DP-FedAvg, privacy amplification can occur because each round uses a randomly sampled subset of clients. This allows for a stronger effective privacy guarantee than analyzing the full client set.