DP-SGD (Differentially Private Stochastic Gradient Descent)

This is the first critical step to bound the sensitivity of the learning process. For each data point in a training batch, the algorithm computes its individual gradient (the vector pointing in the direction of steepest ascent for the loss). The L2 norm of each per-example gradient is then clipped to a pre-defined maximum value, the clip threshold (C). This ensures no single training example can exert an unbounded influence on the model update, which is a prerequisite for adding meaningful noise.

• Purpose: Limits the maximum contribution of any single data point.
• Hyperparameter: The clip threshold C trades off bias (from aggressive clipping) and convergence speed.
• Impact: Clipped gradients are less accurate but have a finite, known sensitivity.

After clipping, the batch of per-example gradients is averaged. To provide (ε, δ)-differential privacy, calibrated Gaussian noise is added to this averaged gradient. The scale (standard deviation) of this noise is proportional to the clip threshold (C) and inversely proportional to the batch size and the desired privacy parameters (ε, δ). The Gaussian mechanism is used here because it is well-suited for the high-dimensional, iterative nature of SGD and enables tighter privacy analysis under composition compared to the Laplace mechanism.

• Mechanism: Noise ~ N(0, σ²I), where σ is calibrated for (ε, δ)-DP.
• Role: Obscures the specific contribution of any individual in the batch.
• Trade-off: More noise strengthens privacy but slows convergence and harms final model utility.

Training a model with DP-SGD involves hundreds or thousands of noisy update steps. Privacy accounting is the process of tracking the cumulative privacy loss (ε, δ) across all these steps to ensure the total does not exceed a pre-defined privacy budget. DP-SGD typically employs the moment accountant, an advanced method that provides tighter, more efficient bounds on the total privacy cost than basic composition theorems. It works by bounding the log moments of the privacy loss random variable.

• Function: Precisely calculates the total (ε, δ) spent after T training steps.
• Necessity: Allows practitioners to set a total budget and stop training before it is exhausted.
• Output: The final, provable privacy guarantee for the trained model.

A powerful technique that strengthens the privacy guarantee in DP-SGD. Because each training step operates on a randomly sampled mini-batch (a small subset of the full dataset), the privacy cost per step is reduced. Intuitively, an adversary is uncertain if a particular individual's data was even in the batch for a given step. This amplification by sampling means the effective privacy parameter ε for each step is smaller than if the mechanism were applied to the entire dataset. This allows for a better utility-privacy trade-off.

• Principle: Random sampling amplifies (improves) the privacy guarantee.
• Requirement: The batch must be a uniform random sample (e.g., Poisson sampling).
• Benefit: Enables stronger final privacy guarantees or less noise for the same guarantee.

DP-SGD introduces new, interdependent hyperparameters that must be tuned carefully, often in tension with standard SGD parameters:

• Noise Multiplier (σ): Directly controls the noise scale; larger σ means stronger privacy but lower accuracy.
• Clip Threshold (C): Bounds gradient norms; too small introduces bias, too large requires more noise.
• Batch Size: Larger batches reduce the relative noise variance per update but can weaken privacy amplification.
• Learning Rate: Typically must be lowered to account for the variance introduced by clipping and noise.

Tuning is non-trivial, as changing one parameter (e.g., increasing batch size for stability) affects the optimal values for the others and the final privacy cost.

DP-SGD's principles are directly applied in federated learning to provide client-level differential privacy. In DP-FedAvg, each client device performs the core DP-SGD operations locally on its own data:

1. Computes a local model update (e.g., gradient).
2. Clips the update's norm to a threshold C.
3. Adds Gaussian noise calibrated to a client-level privacy budget.
4. Sends the noised, clipped update to the server.

The server then aggregates these updates (often via secure aggregation) to update the global model. This ensures the released global model does not reveal the participation or data of any specific client.

Correctly tracking the cumulative privacy loss (ε, δ) across thousands of training steps is critical. Standalone libraries specialize in this complex mathematics:

• TensorFlow Privacy's RDP Accountant: Computes Rényi differential privacy guarantees.
• PyTorch's Opacus Accountants: Implements RDP and Gaussian Differential Privacy (GDP) accountants.
• Google's DP Accounting Library: A language-agnostic library (Python/C++) that provides multiple accounting methods, including RDP, zCDP, and PLD (Privacy Loss Distribution).
• Core Function: These libraries take hyperparameters—noise multiplier (σ), sampling probability (q = batch_size / dataset_size), and number of steps—and output the final (ε, δ) guarantee.

In federated learning, DP-SGD is adapted to the client-level privacy setting. Frameworks like TensorFlow Federated (TFF) and Flower provide building blocks for DP-FedAvg:

• Client-side clipping: Each device clips its local model update (e.g., the difference between initial and final model weights) to a maximum L2 norm.
• Client-side noising: Calibrated Gaussian noise is added to the clipped update before it is sent to the server.
• Secure Aggregation: Often combined with cryptographic protocols to ensure the server only sees the noisy aggregate, not individual noised updates.
• Privacy Accounting: The server tracks the privacy cost across federated learning rounds, considering the client sampling rate and the noise added by each participating device.

Sensitivity is the maximum possible change in the output of a function (e.g., a query, gradient, or model update) when a single data point is added or removed from a dataset. It is the foundational concept that determines the scale of noise required for differential privacy.

• L2 Sensitivity (Δ₂): The maximum Euclidean (ℓ₂) norm by which the function's output can change. This is used with the Gaussian Mechanism.
• L1 Sensitivity (Δ₁): The maximum Manhattan (ℓ₁) norm change, used with the Laplace Mechanism.

In DP-SGD, the core operation is bounding the sensitivity of per-example gradients via gradient clipping before noise addition. The chosen clip norm C directly becomes the sensitivity for the aggregation step.

Gradient clipping is a preprocessing step in differentially private optimization where the norm of individual data point gradients is bounded by a predefined threshold C. This operation is essential for DP-SGD because it limits the sensitivity of the batch gradient aggregation.

• Process: For each training example in a batch, compute its gradient g_i, then project it onto an ℓ₂ ball: g_i ← g_i / max(1, ||g_i||₂ / C).
• Purpose: Without clipping, a single outlier example with a massive gradient could have unbounded influence, requiring prohibitively large noise to hide it. Clipping bounds this influence, making the privacy guarantee feasible.
• Trade-off: Aggressive clipping (small C) introduces bias but allows for less noise. Lenient clipping (large C) preserves accuracy but requires more noise, harming utility.

The moment accountant is an advanced privacy accounting method that provides tight, composable bounds on the cumulative privacy loss (ε, δ) of iterative algorithms like DP-SGD. It improves upon basic composition theorems.

• Mechanism: Instead of tracking the final (ε, δ) directly, it bounds the log moments of the privacy loss random variable across all training steps.
• Advantage: For Gaussian noise and subsampling (as in DP-SGD's mini-batches), it yields a much tighter privacy bound than sequential composition, allowing for more training steps within a fixed privacy budget.
• Output: Given a noise multiplier σ, sampling rate q (batch size / dataset size), and number of steps T, the moment accountant computes the final (ε, δ) guarantee.

Client-level differential privacy is the standard privacy granularity in federated learning. The guarantee ensures that the participation or data of any single client (device or user) cannot be reliably inferred from the released global model or any aggregated statistics.

• Distinction: Contrasts with example-level DP, which protects individual data points within a client's dataset. Client-level DP is a stronger, more appropriate guarantee for FL, where each device's entire local dataset is considered a single unit.
• Application to DP-SGD: In federated settings, DP-FedAvg adapts DP-SGD principles. Each client's model update is treated as a single "gradient"—it is clipped to bound sensitivity and noised, or noise is added during secure aggregation on the server.

Privacy amplification by sampling is a crucial technique that strengthens the privacy guarantee of a mechanism when it is applied to a random subset of the data. It is a key reason DP-SGD can achieve non-trivial utility.

• Principle: Applying a differentially private mechanism to a randomly sampled mini-batch provides a stronger privacy guarantee (a smaller effective ε) than if the same mechanism were applied to the entire dataset.
• Role in DP-SGD: The standard algorithm uses Poisson sampling (each data point included independently with probability q). The moment accountant leverages this subsampling to compute the amplified privacy cost per iteration.
• Implication: It allows for the addition of less noise per step while still achieving a strong overall privacy guarantee, directly improving model utility.

DP-FedAvg is the direct federated learning analogue to DP-SGD. It provides client-level differential privacy by integrating clipping and noise addition into the federated averaging protocol.

• Client-Side DP: Each client clips their local model update (e.g., the difference between initial and final weights) to a maximum L2 norm C. They then add Gaussian noise scaled to C and a chosen noise multiplier σ before sending the noised update to the server.
• Server-Side DP: Alternatively, the server can perform noisy aggregation after receiving clipped updates via a secure aggregation protocol. The server adds calibrated Gaussian noise to the sum or average of updates.
• Goal: To prevent the server from learning whether any specific client participated in a training round, thereby protecting the client's entire local dataset.