Privacy-preserving ML (federated, DP)

The central server in FedAvg receives locally-trained model weight updates (deltas) from participating clients, averages them weighted by each client's dataset size, and broadcasts the updated global model. In a standard deployment the server DOES see the weight-update vectors — FedAvg is NOT private from the server by default. Raw weight differences can leak training data via gradient inversion attacks. True privacy requires an additional layer such as Secure Aggregation (SecAgg) or DP noise before aggregation.

(ε, δ)-DP guarantees that for any two datasets D and D' differing in one record and any output event S, P[M(D)∈S] ≤ e^ε · P[M(D')∈S] + δ. ε bounds the privacy loss in the typical case, while δ is an additive failure probability — the probability that the ε-bound does not hold at all. A small δ (typically ≪ 1/n) means the guarantee fails only with negligible probability, making the mechanism nearly pure-DP.

The Laplace mechanism adds noise Lap(Δf/ε) to the query output, achieving pure (ε,0)-DP with L1 sensitivity Δf. The Gaussian mechanism adds N(0, σ²) with σ ≥ Δf·√(2ln(1.25/δ))/ε, achieving (ε,δ)-DP with L2 sensitivity. Gaussian is preferred when composing many mechanisms (e.g., many training steps in DP-SGD) because Rényi DP / moments-accountant analysis gives tighter privacy accounting than the Laplace mechanism under repeated composition, despite the weaker (ε,δ) guarantee.

import numpy as np
def laplace_mech(true_val, sensitivity, epsilon):
    return true_val + np.random.laplace(0, sensitivity / epsilon)

def gaussian_mech(true_val, sensitivity, epsilon, delta):
    sigma = sensitivity * np.sqrt(2 * np.log(1.25 / delta)) / epsilon
    return true_val + np.random.normal(0, sigma)

DP-SGD makes stochastic gradient descent private by (1) per-sample gradient clipping: each sample's gradient is clipped to L2-norm ≤ C, bounding the per-step L2 sensitivity to C; and (2) noise addition: Gaussian noise N(0, σ²C²I) is added to the summed clipped gradients before the parameter update. Privacy cost across all T steps is tracked using the moments accountant (Rényi DP), giving a final (ε,δ) guarantee that tightens further with subsampled mini-batches via privacy amplification.

# PyTorch Opacus (v1.x) sketch
from opacus import PrivacyEngine
engine = PrivacyEngine()
model, optimizer, loader = engine.make_private(
    module=model,
    optimizer=optimizer,
    data_loader=train_loader,
    noise_multiplier=1.1,   # σ (noise multiplier relative to C)
    max_grad_norm=1.0,      # C (per-sample clipping norm)
)

The moments accountant tracks the Rényi divergence D_α(M(D)||M(D')) at multiple orders α, then converts to (ε,δ)-DP by optimizing over α via a tail bound. Under composition of T mechanisms, Rényi divergences add exactly (no slack from union bounds), giving tighter final (ε,δ) than: (1) the basic composition theorem which gives O(T·ε) linear growth; and (2) the advanced composition theorem (Dwork et al. 2010) which gives O(√T·ε) but with larger constants from its probabilistic tail argument. In practice the moments accountant is 2–3× tighter than advanced composition at the same noise level, enabling significantly more training steps per fixed privacy budget.

When a mechanism M is applied to a random subsample of size m from a dataset of size n (sampling rate q = m/n), an amplification theorem shows the effective privacy parameter reduces from ε to approximately ln(1 + q(e^ε − 1)) ≈ q·ε for small ε. In DP-SGD, using mini-batches means only a fraction q of records are at risk each step, so each step's ε is amplified down by ~q. Combined with the moments accountant over T steps, the final budget grows as O(q√T·ε) rather than O(T·ε).

In Central DP, a trusted curator collects raw data and applies noise before releasing aggregate results; individuals must trust the server (e.g., a census bureau publishing DP-protected statistics, or a hospital running DP analytics on its patient database before sharing results). In LDP, each user randomizes their own data locally before sending it — the server never sees true values — trading higher utility loss for eliminating the need to trust the server. Canonical LDP deployments: Google's RAPPOR in Chrome to collect browser histogram data, and Apple's keyboard emoji/health data collection using Count Mean Sketch-based LDP.

PATE trains an ensemble of 'teacher' models on disjoint partitions of sensitive data, then labels public (unlabeled) data by aggregating teacher votes through a noisy argmax — adding Laplace or Gaussian noise to vote counts before taking the argmax. A student model is then trained on these noisy-labeled public samples. Privacy is analyzed via the moments accountant: queries where teachers strongly agree cost little privacy budget because agreement makes the argmax robust to noise, so fewer budget-consuming queries are needed.

import numpy as np
def noisy_argmax(vote_counts, epsilon):
    # Laplace noise added to each class count
    noisy = vote_counts + np.random.laplace(0, 1/epsilon, size=vote_counts.shape)
    return np.argmax(noisy)

SecAgg (Bonawitz et al. 2017) allows a server to compute the sum of client model updates without seeing any individual update in plaintext. Clients pair-wise negotiate random seeds over authenticated Diffie-Hellman key exchange, then each client adds a pseudorandom mask derived from those seeds; the masks cancel when the server sums all updates. Client dropout is tolerated via secret sharing (e.g., Shamir's) so surviving clients can reconstruct dropped clients' mask contributions. The server sees only the aggregate sum — never individual updates.

In an MIA (Shokri et al. 2017), an adversary trains shadow models on known-membership datasets, then trains a meta-classifier on the difference in confidence scores between members (high, peaked confidence on training classes) and non-members (lower, more uniform confidence). Overfit models have a larger train–test confidence gap, making MIA easier. Defenses include DP training, confidence masking/label smoothing, and regularization to reduce the exploitable signal.

DLG (Zhu et al. 2019) shows that a server or honest-but-curious aggregator can reconstruct training inputs from shared gradients by iteratively optimizing dummy inputs to minimize the L2 distance between dummy gradients and true gradients. It is possible when full-precision individual gradients are shared (as in naive FL). Effective defenses include: gradient clipping + DP noise (makes reconstruction ill-posed), Secure Aggregation (server never sees individual gradients), gradient compression/quantization (reduces reconstruction resolution), and gradient perturbation.

The shuffle model interposes an anonymous shuffler (a cryptographic mix-net or trusted shuffler) between users and the analyzer. Each user applies an LDP mechanism locally, but the shuffler randomly permutes messages so the analyzer cannot link a message to its sender. This unlinkability provides additional amplification: an ε_L-LDP mechanism fed through a shuffler with n users yields a central-equivalent guarantee of roughly ε_C = O(ε_L · e^{ε_L} · √(log(1/δ)/n)), bridging the utility gap between LDP and central DP without requiring a trusted data curator.

Basic composition: k applications of ε-DP mechanisms gives kε-DP (linear growth). Advanced composition (Dwork et al. 2010): for k mechanisms each (ε,δ)-DP, composition gives approximately (ε√(2k ln(1/δ')), kδ+δ')-DP, giving O(√k) growth with larger constants. Rényi DP (moments accountant) is tighter still: Rényi divergences add exactly at each order α, and conversion to (ε,δ)-DP optimizes over α — giving smaller constants than advanced composition at the same O(√k) asymptotic, often 2–3× tighter in practice for DP-SGD.

When client data distributions differ, local SGD steps move each client's model toward its own local optimum, causing 'client drift' — the weighted average of locally-biased models diverges from the true global optimum, slowing convergence or causing oscillation. Key mitigations: FedProx adds a proximal regularization term μ/2‖w − w^t‖² to each client's local objective, keeping local models near the global model. SCAFFOLD uses control variates to estimate and correct the drift direction on each client. MOON uses contrastive learning on model representations to align local features with the global model.

In split learning, the neural network is partitioned: clients run forward/backward passes up to a 'cut layer' and send intermediate activations ('smashed data') to the server, which completes the computation and returns gradients of the cut layer. Unlike FL — where clients share full model weight updates — in split learning clients never share model weights and the server holds the deeper layers. Privacy risks remain: smashed activations can be inverted to reconstruct raw inputs (activation inversion attacks), making additional DP noise on activations or data-independent perturbation necessary.

DP-GAN applies DP-SGD to the discriminator (which directly processes real data) and trains the generator using normal backpropagation through the discriminator. The challenge is that GAN training is already unstable (mode collapse, non-convergence), and DP noise added to discriminator gradients significantly worsens this instability — larger noise multipliers narrow the gradient signal the generator can use. Mitigations include pre-training the discriminator on public data before applying DP, limiting DP noise to sensitive layers only, and using stronger architectures.

Federated Learning trains model parameters collaboratively across devices. Federated Analytics computes aggregate statistics (histograms, counts, means) over device data without training a model. Since FA queries are simple and non-iterative, privacy accounting is straightforward: the Laplace mechanism or randomized response is typically applied locally per query (LDP), with global sensitivity often equal to 1 for counting queries. Examples include Google's histogram estimation for Chrome metrics and Apple's emoji frequency collection using Count Mean Sketch with LDP.

C is the maximum L2 norm to which each per-sample gradient is clipped before noise addition; the Gaussian noise standard deviation is σ·C per coordinate. A smaller C reduces noise magnitude (improving utility) but clips more gradients, biasing the update direction. A larger C better preserves gradient directions but requires proportionally more noise to maintain the same (ε,δ) guarantee. Practitioners typically initialize C at the median or a high percentile of unclipped gradient norms (adaptive clipping) and tune the noise multiplier σ to meet the privacy budget.

# Adaptive clipping (Opacus / Google DP library approach)
# Target: keep ~fraction p of gradients unclipped
# Estimate quantile of gradient norms online and set C = quantile
# This balances clipping bias vs noise magnitude automatically

Byzantine-robust FL addresses malicious (Byzantine) clients that send arbitrary updates to poison the global model. Attacks include label-flipping, backdoor injection, and gradient manipulation. Defenses replace naive averaging with robust aggregators: coordinate-wise median (Yin et al.) rejects outlier coordinates; Krum selects the update closest to its k-nearest neighbors; FLTrust scores client updates against a small trusted root dataset held by the server. These mechanisms are complementary to DP — DP protects individual privacy from the server, while Byzantine robustness protects the model from adversarial clients.

Each DP-SGD step consumes Rényi DP budget that accumulates over T steps; the final (ε,δ) is computed after all training steps using the moments accountant (e.g., via Google DP library or Opacus). Practical constraints: (1) per-sample gradient computation requires O(B) memory overhead for batch size B (each sample needs its own backward pass); (2) achieving useful utility on LLMs typically requires ε in the range 3–8, giving weaker privacy than theoretical ideals; (3) parameter-efficient fine-tuning (LoRA + DP-SGD) dramatically reduces memory by limiting per-sample gradients to the adapter parameters only, with the frozen backbone contributing zero sensitivity.

# LoRA + DP-SGD (conceptual)
# Only LoRA adapter parameters get per-sample gradients
# Frozen backbone has no sensitivity contribution
# => lower memory, same (ε,δ) accounting scoped to adapter params

Randomized Response (Warner 1965) privatizes a binary answer x ∈ {0,1}: report x with probability p = e^ε/(1+e^ε) and flip with probability 1−p. This achieves ε-LDP. For frequency estimation over n users reporting binary attribute b, the server collects noisy reports y_i and unbiases: f̂ = (mean(y_i) − (1−p)) / (2p−1). For k-ary answers, RAPPOR and Optimal Local Hashing (OLH) extend this: each user hashes their value to a random binary vector and applies RR per bit (or a more efficient local hash), then the server inverts to estimate frequency marginals.

import numpy as np
def rr_report(x, epsilon):
    p = np.exp(epsilon) / (1 + np.exp(epsilon))
    return x if np.random.rand() < p else 1 - x

def rr_estimate(reports, epsilon):
    p = np.exp(epsilon) / (1 + np.exp(epsilon))
    return (np.mean(reports) - (1 - p)) / (2*p - 1)

PFL trains client-specific models rather than a single global model, addressing heterogeneous data and tasks. Ditto adds a regularization term λ/2‖w_i − w*‖² to each client's local objective, pulling the local model toward the global model w* while allowing personalization. Per-FedAvg treats FL as a meta-learning problem (MAML-style): the global model is optimized to be a good initialization for fast local fine-tuning with one or a few gradient steps. The tradeoff is that heavier personalization benefits clients with more local data but reduces cross-client knowledge sharing.

SecAgg uses lightweight pseudorandom masking (pairwise masks cancel in the sum) to hide individual gradients from the server while allowing it to compute the sum; it is efficient but limited to linear aggregation (sum/average). HE (e.g., CKKS, BFV) allows the server to evaluate arbitrary polynomial functions on ciphertexts without decrypting, enabling richer operations such as non-linear aggregation or private inference. The bottleneck is ciphertext size (~100× larger than plaintext) and computation overhead (CKKS arithmetic is 1000×+ slower than plaintext), making end-to-end HE training of large models currently impractical.

In a model inversion attack (Fredrikson et al. 2015), an adversary with white-box or API access reconstructs a representative input for a target class by optimizing an input to maximize model confidence on that class — recovering average-face reconstructions in facial recognition. DP provides a formal defense: if the model is (ε,δ)-DP, the attacker's ability to distinguish whether any specific individual's record was used in training is bounded by e^ε + δ. This limits how precisely the reconstruction can correspond to any individual's private data (though DP bounds individual-level leakage, not reconstruction of class-average prototypes).

Gboard FL sends model updates from millions of mobile devices with limited uplink bandwidth. Three key techniques: (1) Structured updates — restrict updates to a parameterized low-rank or random-rotation subspace, reducing bits per update; (2) Sketched updates — compress gradients using count sketch before transmission; (3) Gradient quantization — quantize float32 parameters to 1-bit (SignSGD) or 8-bit integers, reducing per-parameter size by 4–32×. These are combined with SecAgg to maintain privacy while dramatically cutting uplink bandwidth.

A privacy odometer (Rogers et al. 2016) is a running tracker of privacy loss that can answer 'how much budget has been consumed so far?' after each query or training step. Unlike static pre-analysis (where all queries must be fixed before analysis), an odometer supports adaptive composition — the analyst can decide whether to issue the next query based on the current remaining budget without voiding the overall DP guarantee. This is enabled by the Rényi DP framework where divergences compose additively, allowing online accumulation of the privacy cost.

Standard mini-batch backprop averages gradients across the batch before any clipping, so individual sample gradients are never materialized — DP clipping per sample is impossible. DP-SGD requires computing each sample's gradient independently before clipping and summing. PyTorch's standard backward computes the average directly; Opacus (via hooks) or JAX (via vmap) materialize per-sample gradients, leading to O(B) times the memory of standard backprop for batch size B. Ghost clipping (storing only gradient norms, not full gradients) and per-layer book-keeping reduce this overhead in practice.

# JAX per-sample gradient using vmap
from jax import vmap, grad
per_sample_grads = vmap(grad(loss_fn), in_axes=(None, 0, 0))(params, x_batch, y_batch)
# Each element of per_sample_grads is one sample's full gradient tree
norms = jnp.array([sum(jnp.linalg.norm(g)**2 for g in jax.tree_util.tree_leaves(gs))**0.5
                   for gs in per_sample_grads])
clipped = [jax.tree_util.tree_map(lambda g: g / jnp.maximum(1, norms[i]/C), gs)
           for i, gs in enumerate(per_sample_grads)]

Semi-private (or label-private) learning assumes access to a small public (non-sensitive) unlabeled dataset alongside a large private labeled dataset. Algorithms like PATE or DP pre-training + private fine-tuning exploit the public data to learn feature representations without any privacy cost, then apply DP only to the private labeling or fine-tuning step. This can reduce noise by orders of magnitude because the model's memorization capacity is pre-consumed by public pre-training, and only a small private query (e.g., PATE teacher votes) consumes the privacy budget.

The L2 (or L1) sensitivity Δf = max_{D,D'} ‖f(D)−f(D')‖₂ over neighboring datasets directly controls the noise scale: Gaussian σ = Δf·√(2 ln(1.25/δ))/ε. Bounding sensitivity is hard because: (1) for complex functions (e.g., deep network outputs) sensitivity is often theoretically unbounded, requiring explicit clipping to enforce a finite bound; (2) tight bounds require careful algorithm analysis; and (3) loose bounds lead to excessive noise and poor utility. In DP-SGD, per-sample gradient clipping is precisely the operation that enforces a finite L2 sensitivity of C.

zCDP (Bun & Steinke 2016) requires that for all α > 1, the α-Rényi divergence satisfies D_α(M(D)‖M(D')) ≤ ρα for some ρ. It is strictly between pure ε-DP (which implies ρ-zCDP with ρ = ε²/2) and (ε,δ)-DP (given ρ-zCDP, for any δ > 0, M is (ρ + 2√(ρ ln 1/δ), δ)-DP). Rényi DP at all orders subsumes zCDP. zCDP's clean linear-in-α form makes composition trivial: ρ-zCDP composed T times gives Tρ-zCDP, with straightforward conversion to (ε,δ)-DP — cleaner than tracking divergences order-by-order in Rényi DP.

SVT (Dwork & Roth 2014) allows answering a long sequence of threshold queries (is f_i(D) ≥ t?) while charging privacy budget only for the queries that exceed the threshold (the 'above-threshold' answers). Below-threshold answers are returned as ⊥ at near-zero additional cost. A canonical ML use case: private hyperparameter selection over many candidates — SVT identifies the first configuration whose validation metric exceeds a threshold while consuming O(1) privacy budget per above-threshold answer rather than O(k) for k candidates, enabling efficient DP model selection.

Gradient compression (e.g., top-k sparsification, random-k) transmits only the largest-magnitude or randomly selected gradient components to save bandwidth, accumulating the compression error locally and adding it to the next step's gradient (error feedback / error correction). Interaction with DP is non-trivial: top-k selection is data-dependent (it selects the largest components), so if DP noise is added after compression the selection itself leaks information. Correct DP integration requires either (a) adding noise before compression with sensitivity re-analysis, or (b) using data-independent random projections that are inherently DP-compatible.

Apple's iOS DP pipeline uses local differential privacy: each device applies a Count Mean Sketch (CMS) / Hadamard Response variant to report emoji usage — hashing the emoji to a random binary vector and applying randomized response per bit, keeping ε ≤ 4 per day. High-dimensionality is handled by sketching: instead of reporting over thousands of emoji types, users report into a compact random hash table (CMS bins), and the server inverts the sketch to estimate frequency marginals. Multiple queries per day are managed by a hard daily privacy budget cap.

Standard DP defines neighboring datasets by the addition/removal of one row. For graphs, two neighboring notions exist: node-DP (add/remove one node and all its edges — stronger privacy but higher noise) and edge-DP (add/remove one edge — weaker privacy, better utility). Applying DP to GNNs is complicated because neighborhood aggregation creates correlated gradients across many nodes: removing a single node's data affects the gradient computation of all its k-hop neighbors, inflating effective sensitivity by a factor related to the graph degree.

DP-FTRL (Kairouz et al. 2021) replaces SGD with online FTRL using a tree-aggregation protocol to add correlated (rather than i.i.d.) Gaussian noise across rounds. Tree aggregation sums noise from a binary tree of partial sums, so each gradient update is influenced by at most O(log T) independent noise terms rather than accumulating T independent noise additions as in DP-SGD. This reduces effective noise variance while maintaining the same (ε,δ) DP guarantee. DP-FTRL is particularly valuable in federated/continual settings where there is no natural epoch structure and subsampling amplification is unavailable.

Post-processing immunity states that applying any (possibly randomized) function to the output of a DP mechanism cannot increase privacy loss: if M is (ε,δ)-DP and g is any function, then g∘M is also (ε,δ)-DP. For ML deployment, this means that after training with DP-SGD, any downstream operation — inference on new inputs, applying softmax, exporting to ONNX, fine-tuning on public data, or aggregating predictions — does not require additional noise or privacy accounting. The privacy guarantee is 'baked in' to the model weights at training time.

Amplification by subsampling with sampling rate q gives effective ε ≈ q·ε per step (linear reduction in q); with moments accounting over T steps the final bound is O(q√T·ε). Amplification by shuffling with n users each applying ε_0-LDP gives a central-equivalent guarantee of roughly ε_central = O(ε_0 · e^{ε_0} · √(log(1/δ)/n)) ≈ O(ε_0/√n) for small ε_0. These are fundamentally different scaling laws: subsampling achieves linear reduction in q (O(1/n) per step when q=1/n), while shuffling achieves O(1/√n) reduction. Subsampling's amplification is stronger per record but requires a trusted curator, whereas shuffling achieves O(1/√n) without any trusted data collector.

Confident-GNMax (Papernot et al. 2018) extends PATE with a two-stage query: first, Gaussian noise is added to vote counts and the query is only forwarded to the full NoisyMax aggregator if the noisy winning vote count exceeds a confidence threshold (using a mechanism analogous to SVT). Non-confident queries return ⊥ at nearly zero privacy cost, and only confident queries — where teachers strongly agree — are answered and charged privacy budget. This drastically reduces the effective number of budget-consuming queries, enabling labeling of larger student training sets for the same total ε.