Differential Privacy: Mathematical Guarantees

In 2026, a consortium of government hospitals training a shared tumor-detection model under India's Digital Personal Data Protection Act faces a question no single epsilon-delta definition answers: the model isn't trained by asking the patient database one question. Stochastic gradient descent asks it thousands of questions, one per minibatch step, for every epoch over the training set. Each of those questions is answered under differential privacy, and each answer is a differentially private mechanism in its own right. The Data Protection Board, when it audits the released model, wants a single number: the total privacy loss guaranteed across the entire training run, not the privacy loss of one gradient step. Getting from "each step is (ε₀, δ₀)-DP" to "the trained model is (ε, δ)-DP" is the job of a composition theorem, and getting the noise calibrated correctly at every one of those thousands of steps is the job of an algorithm called DP-SGD. Both are the subject of this chapter.

Recap: what one query costs

You already know that a mechanism M satisfies (ε, δ)-differential privacy if, for any two datasets differing in one record and any measurable output set S, Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D′) ∈ S] + δ. That single inequality bounds how much one release can shift an observer's belief about whether any one person's record was in the data. This chapter asks the harder question a production system actually has to answer: what happens to that guarantee when the same private dataset is queried not once, but k times, or T times inside a training loop?

Composition: privacy is a spending account, not a coupon

Differential privacy composes, and it composes in a specific, provable way. If mechanism M₁ is (ε₁, δ₁)-DP and mechanism M₂ is (ε₂, δ₂)-DP, and both are run on overlapping or identical data (M₂ may even be chosen adaptively after seeing M₁'s output), then releasing both outputs together is (ε₁ + ε₂, δ₁ + δ₂)-DP. This is the basic sequential composition theorem, essentially immediate from the definition (Dwork, McSherry, Nissim, and Smith, "Calibrating Noise to Sensitivity in Private Data Analysis," TCC 2006). Extended to k mechanisms each (ε₀, δ₀)-DP, the guarantee for the whole sequence is (kε₀, kδ₀)-DP. Every query you run against the same private data spends privacy budget, and the spending is additive. There is no free lookup after the first one.

There's a second theorem people confuse with this one. If the k mechanisms are run on disjoint partitions of the data (hospital A's records go to query 1, hospital B's to query 2, and so on, with no patient appearing in two partitions), the composed guarantee is (max ε₀, max δ₀)-DP, not the sum. This is parallel composition (McSherry, "Privacy Integrated Queries," SIGMOD 2009): because no individual's record can influence more than one of the outputs, an adversary learns at most what the worst single query reveals, not the accumulated total. The distinction between "same rows, asked repeatedly" (sequential, budget adds) and "different rows, asked once each" (parallel, budget doesn't add) is the first thing to check before you compose anything.

Worked example: naive versus advanced composition

Suppose a data analytics team runs k = 100 statistical queries against the same patient table, each individually calibrated to (ε₀, δ₀)-DP with ε₀ = 0.05 and δ₀ = 10⁻⁶. Basic sequential composition gives:

ε_naive = k · ε₀ = 100 × 0.05 = 5.0, and δ_naive = k · δ₀ = 100 × 10⁻⁶ = 1.0 × 10⁻⁴.

An ε of 5.0 is a weak guarantee: e^5 ≈ 148, meaning the presence or absence of one patient's record can shift the odds of any outcome by roughly two orders of magnitude. Linear-in-k composition is provably tight in the worst case, but it is pessimistic for the typical case, because it assumes every query's privacy loss points in the same adversarial direction simultaneously. The advanced composition theorem (Dwork, Rothblum, and Vadhan, "Boosting and Differential Privacy," FOCS 2010) exploits the fact that privacy loss behaves like a bounded random walk across independent queries, and a random walk of k steps typically travels only O(√k), not O(k). For any additional slack δ′ > 0, k-fold composition of (ε₀, δ₀)-DP mechanisms satisfies (ε′, kδ₀ + δ′)-DP with:

ε′ = √(2k · ln(1/δ′)) · ε₀ + k · ε₀ · (e^ε₀ − 1)

Plugging in k = 100, ε₀ = 0.05, and choosing δ′ = 10⁻⁵:

import math

def advanced_composition(k, eps0, delta0, delta_prime):
    """Dwork-Rothblum-Vadhan (2010) advanced composition theorem."""
    term1 = math.sqrt(2 * k * math.log(1 / delta_prime)) * eps0
    term2 = k * eps0 * (math.exp(eps0) - 1)
    eps_total = term1 + term2
    delta_total = k * delta0 + delta_prime
    return eps_total, delta_total, term1, term2

k, eps0, delta0, delta_prime = 100, 0.05, 1e-6, 1e-5
naive_eps = k * eps0
naive_delta = k * delta0
adv_eps, adv_delta, t1, t2 = advanced_composition(k, eps0, delta0, delta_prime)

print(f"naive:    eps={naive_eps:.3f}  delta={naive_delta:.1e}")
print(f"advanced: eps={adv_eps:.3f}  delta={adv_delta:.1e}  (term1={t1:.3f}, term2={t2:.3f})")

Tracing the arithmetic by hand: term1 = √(2 × 100 × ln(10⁵)) × 0.05 = √(200 × 11.5129) × 0.05 = √2302.59 × 0.05 = 47.985 × 0.05 = 2.399. term2 = 100 × 0.05 × (e^0.05 − 1) = 5 × 0.05127 = 0.256. So ε′ = 2.399 + 0.256 = 2.656, and δ_total = 100 × 10⁻⁶ + 10⁻⁵ = 1.1 × 10⁻⁴. The printed output is exactly naive: eps=5.000 delta=1.0e-04 and advanced: eps=2.656 delta=1.1e-04 (term1=2.399, term2=0.256). Advanced composition delivers ε = 2.656 instead of 5.0 for the same 100 queries, paying only a small extra sliver of δ (10⁻⁵) to buy it. That gap between "naive" and "advanced" is exactly the budget headroom that lets real systems run far more queries than a naive sum would ever permit, and it is the same mathematical idea, pushed much further, that makes training a neural network under DP possible at all.

DP-SGD: composing privacy across a training run

A neural network trained by stochastic gradient descent touches the private training set once per minibatch, for potentially tens of thousands of steps. If each step were released as its own uncalibrated statistic, the composed privacy loss would be unusable. DP-SGD (Abadi, Chu, Goodfellow, McMahan, Mironov, Talwar, and Zhang, "Deep Learning with Differential Privacy," ACM CCS 2016) makes each step a calibrated, boundedly-sensitive Gaussian mechanism, so that composition theorems can be applied to the whole run. The modification to ordinary SGD has exactly two moving parts:

Per-example gradient clipping. Ordinary SGD averages the gradient of the loss over a minibatch. In DP-SGD, the gradient gᵢ = ∇L(θ; xᵢ) is computed per example, then each one is individually rescaled to have L2 norm at most C: ĝᵢ = gᵢ / max(1, ||gᵢ||₂ / C). This is the step that makes sensitivity analysis possible at all. Without it, a single unusual patient record (an outlier tumor scan with an enormous loss gradient) could dominate the batch sum without bound, and no fixed amount of noise could mask its contribution for every possible dataset. Clipping caps that one record's maximum possible influence on the sum at C, which is exactly what "sensitivity" means in the Gaussian mechanism.

Calibrated Gaussian noise. Once every per-example gradient is clipped to norm C, the batch sum Σᵢ ĝᵢ has L2 sensitivity exactly C (adding or removing one record changes the sum by at most one clipped gradient's worth). The mechanism adds noise drawn from N(0, σ²C²I) to that sum, then divides by the batch size B to form the update. Here σ is the noise multiplier: a unitless dial, independent of C, that the Gaussian mechanism bound turns directly into a per-step privacy guarantee. The standard result (Dwork and Roth, The Algorithmic Foundations of Differential Privacy, 2014, Theorem A.1 (Appendix A)) states that for sensitivity Δf and target (ε₀, δ₀), the Gaussian mechanism is (ε₀, δ₀)-DP whenever σ ≥ √(2 ln(1.25/δ₀)) / ε₀. Every one of the T minibatch steps is now an instance of this same calibrated mechanism, touching the private data once, and the whole training run is exactly the k-fold composition problem from the previous section, with k = T.

The chart traces both composition laws for T up to 1000 steps at a fixed per-step budget of ε₀ = 0.01, δ₀ = 10⁻⁶, with δ′ = 10⁻⁵ set aside for the advanced-composition slack. Naive composition is a straight line, reaching ε = 10.0 at T = 1000 because it simply sums. Advanced composition bends: its dominant term scales with √T, so it reaches only ε ≈ 1.62 at the same T, a 6.2× improvement bought at the cost of one fixed extra δ′. That square-root behavior is what makes DP-SGD trainable at all, but as the next section shows, even advanced composition is still too loose for a real training run, which is precisely why production accountants go further still.

Worked example: the same training run at two privacy budgets

Consider the hospital consortium's model, trained for T = 1000 steps, with clip norm C = 1.0 and batch size B = 256. The consortium's counsel wants to compare two release options against the DPDP Act's Data Protection Board: a strict budget of ε_total = 1 and a looser budget of ε_total = 8, both at δ_total ≈ 1.0 × 10⁻⁴ (built from δ₀ = 10⁻⁷ per step over 1000 steps, plus δ′ = 10⁻⁶ slack: 1000 × 10⁻⁷ + 10⁻⁶ = 1.01 × 10⁻⁴).

Step 1: find the per-step ε₀ that composes (via the same advanced composition formula, applied in reverse) to each target after T = 1000 steps. Solving ε′(ε₀) = 1 and ε′(ε₀) = 8 numerically gives ε₀ ≈ 0.00581 for the strict budget and ε₀ ≈ 0.03886 for the loose budget. (You can verify either forward: plugging ε₀ = 0.00581, T = 1000, δ′ = 10⁻⁶ into the composition formula from the previous section reproduces ε′ = 1.000 to three decimals.)

Step 2: convert each per-step ε₀ into a noise multiplier using the Gaussian mechanism bound σ = √(2 ln(1.25/δ₀)) / ε₀, with δ₀ = 10⁻⁷ fixed: √(2 ln(1.25 × 10⁷)) = √(2 × 16.34) = √32.68 = 5.717.

Step 3: compare against a signal. Take a synthetic (illustrative, not measured) true average per-coordinate gradient magnitude of g = 0.02, typical of the small gradients seen deep in a well-conditioned network. The noise-to-signal picture: at ε_total = 1, noise std (3.844) swamps the signal (0.02) by roughly 192×, giving SNR ≈ 0.0052. At ε_total = 8, noise std (0.575) still swamps the signal, but by only about 29×, giving SNR ≈ 0.0348, a 6.69× improvement. That factor of 6.69 is exactly the ratio of the two noise multipliers (984.0 / 147.1 ≈ 6.69), because SNR scales as 1/σ once C and B are fixed. This is the privacy-utility tradeoff in numbers: tightening ε from 8 to 1 does not cost a little utility, it multiplies the noise the gradient signal must survive by nearly 7×.

Notice, too, how large both noise multipliers are: σ ≈ 984.0 and σ ≈ 147.1 are far outside the range (typically σ ≈ 0.5 to 4) reported in practical DP-SGD deployments. That gap is not an error in the arithmetic; it is the point. Generic advanced composition, applied to a full, non-subsampled Gaussian mechanism at every one of 1000 steps, is still far too pessimistic to train anything useful. What makes real DP-SGD systems work is two refinements this worked example deliberately left out: subsampling amplification (each step touches only a random q = B/N fraction of the data, and mechanisms that subsample leak proportionally less per step than ones that see the whole dataset every time) and the moments accountant itself, which composes Rényi divergences rather than (ε, δ) pairs directly and converts back to (ε, δ) only once, at the end. Abadi et al. (2016) built the moments accountant specifically because advanced composition, even with subsampling folded in loosely, was still too loose to make DP-SGD practical: the accountant is not an optimization on top of composition theorems, it is what makes the theorems in this chapter usable at production scale.

Common misconception

Misconception: "My training loop touches patient data at every one of the T steps, but I only publish the final model weights once, so my privacy cost should be a single (ε₀, δ₀) release, not T of them." This feels intuitive because the analyst only ever sees one artifact. It is wrong. Differential privacy is closed under post-processing: any function applied to a differentially private output, including "train 999 more steps and then throw away everything except the final weights," cannot leak more than the composed mechanisms that produced the intermediate noisy sums already leaked. Post-processing lets you discard information for free; it never lets you retroactively reduce the privacy cost of the queries that generated it. The budget is consumed at the moment each step touches the raw per-example gradients, not at the moment something is shown to a human. A model trained for T = 10,000 steps and released once has spent exactly the same composed privacy budget as if all 10,000 noisy gradient sums had been published individually; the accountant has to track every step whether or not the intermediate results ever leave the training job.

Active recall

Attempt each question before reading its answer.

1. Why does DP-SGD clip the gradient of each individual example rather than clipping the already-averaged batch gradient?
2. In the k = 100, ε₀ = 0.05, δ₀ = 10⁻⁶ example, the analyst switches the advanced-composition slack from δ′ = 10⁻⁵ to δ′ = 10⁻⁴. Does ε′ go up or down, and by how much? What happens to δ_total?
3. The consortium doubles its query load from k = 100 to k = 400 queries (same ε₀ = 0.05, δ₀ = 10⁻⁶, δ′ = 10⁻⁵ per query). Recompute both the naive and the advanced composed ε and δ. Does advanced composition's advantage over naive grow or shrink as k grows?
4. In the DP-SGD worked example (T = 1000, ε_total = 8, σ ≈ 147.1, C = 1.0), the engineering team quadruples the batch size from B = 256 to B = 1024, keeping σ, C, and T fixed. What happens to the noise-to-signal ratio? Is this an unqualified improvement?
5. Five hospitals each run one query on their own, non-overlapping patient records, each mechanism calibrated to (0.1, 10⁻⁶)-DP. What is the total guarantee for releasing all five outputs together? How would the answer change if all five queries had instead been run against one shared, overlapping database?

Answers:

1. Sensitivity has to be bounded for every possible dataset, including one where a single record has an enormous, unbounded gradient (an outlier scan, a mislabeled example). If you sum first and clip the average afterward, one such record can still dominate the sum before clipping ever touches it; the clip only rescales the already-corrupted total, and its influence on that total was never bounded. Clipping each gᵢ to norm C before summing guarantees that no single example can move the sum by more than C, regardless of how extreme its true gradient is, which is exactly the sensitivity bound the Gaussian mechanism formula requires.

2. Larger δ′ shrinks ln(1/δ′), which shrinks term1 = √(2k ln(1/δ′)) · ε₀. With δ′ = 10⁻⁴: ln(1/10⁻⁴) = 9.210, term1 = √(2×100×9.210) × 0.05 = √1842.1 × 0.05 = 42.92 × 0.05 = 2.146. term2 is unchanged at 0.256 (it doesn't depend on δ′). So ε′ = 2.146 + 0.256 = 2.402, down from 2.656: a looser δ′ buys a tighter ε′. But δ_total also changes: δ_total = kδ₀ + δ′ = 10⁻⁴ + 10⁻⁴ = 2.0 × 10⁻⁴, up from 1.1 × 10⁻⁴. There's no free lunch: the analyst traded a smaller ε for a larger δ, spending down a different part of the privacy budget.

3. Naive: ε = 400 × 0.05 = 20.0, δ = 400 × 10⁻⁶ = 4.0 × 10⁻⁴. Advanced: term1 = √(2×400×ln(10⁵)) × 0.05 = √(800×11.513) × 0.05 = √9210.3 × 0.05 = 95.97 × 0.05 = 4.799; term2 = 400 × 0.05 × 0.05127 = 1.025; ε′ = 4.799 + 1.025 = 5.824, δ_total = 400×10⁻⁶ + 10⁻⁵ = 4.1 × 10⁻⁴. The naive-to-advanced ratio grew from 5.0/2.656 ≈ 1.88× at k=100 to 20.0/5.824 ≈ 3.43× at k=400: advanced composition's advantage over naive widens as k grows, because the naive bound is linear in k while advanced composition's dominant term grows only as √k.

4. Noise std after averaging is σC/B, so quadrupling B quarters the noise std: 147.1 × 1.0 / 1024 ≈ 0.1437, versus 0.575 at B = 256, a 4× drop, giving SNR ≈ 0.02/0.1437 ≈ 0.139, a 4× improvement over the earlier 0.0348. But it is not unqualified: this calculation held σ fixed and only asked what happens to the noise-to-signal ratio, ignoring that the underlying privacy accounting also depends on the sampling probability q = B/N. Quadrupling B quadruples q, and the (subsampled) mechanism's actual ε for the same σ and T would come out larger (privacy amplification by subsampling weakens as q grows) than the accountant reported at the old batch size. To honestly keep ε_total = 8 fixed after the batch-size change, you'd need to re-run the accountant and likely raise σ to compensate, which claws back part of that 4× SNR gain. Bigger batches buy SNR at fixed σ, not at fixed privacy.

5. Disjoint records: by parallel composition, the guarantee for the combined release is (max, max) = (0.1, 10⁻⁶)-DP, not five times that: no patient's record appears in more than one query, so no adversary can accumulate evidence about any one person across queries. If instead the same five queries had run against one shared, overlapping database, sequential composition would apply: ε = 5 × 0.1 = 0.5, δ = 5 × 10⁻⁶ = 5.0 × 10⁻⁶. The five-fold difference (0.1 versus 0.5) is entirely explained by whether a single patient's record could have influenced more than one of the five outputs.

Think About It

Think about this: How would you explain differential privacy: mathematical guarantees to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Practice Exercises

Now it is time to practice! Complete these challenges to solidify your understanding:

• Exercise 1: Write a short program that demonstrates the core concept from this chapter. Test it with at least 3 different inputs.
• Exercise 2: Find a real-world example where differential privacy: mathematical guarantees is used in an Indian company (like TCS, Infosys, Flipkart, or ISRO). Write a paragraph explaining the connection.
• Exercise 3: Create a mind-map connecting differential privacy: mathematical guarantees to at least 3 other topics you have studied.