Privacy (differential privacy, membership inference): Exercises

This page is a self-test ladder for Privacy (differential privacy, membership inference). Work each problem first, then open the solution. Every symbol used here was built in the parent note; where a formula reappears we restate it in one line so you never have to scroll back.

Level 1 — Recognition

Exercise 1.1

State, in words, what the inequality $Pr [M (D_{1}) \in S] \leq e^{ε} Pr [M (D_{2}) \in S]$ guarantees, where $D_{1}, D_{2}$ differ in one record.

Recall Solution

$M$ is a randomized mechanism (an algorithm whose output is random). $D_{1}$ and $D_{2}$ are neighboring datasets — identical except one person's row. The line says: for any set of outputs $S$ you might look at, the probability of landing in $S$ changes by at most a multiplicative factor of $e^{ε}$ when one individual is added or removed. Consequence: an adversary watching the output cannot tell "was this person in the data?" with much confidence, because both worlds produce nearly the same output distribution.

Exercise 1.2

For the Laplace mechanism $M (D) = f (D) + Lap (b)$ , which quantity do you plug into $b$ : $ε$ , $Δ f$ , or the ratio $Δ f / ε$ ? Explain why the ratio and not just $Δ f$ .

Recall Solution

You set $b = Δ f / ε$ . Why the ratio: the noise must be big enough to hide the biggest one-person change $Δ f$ , and how thoroughly we hide it is governed by our budget $ε$ . A tight budget (small $ε$ ) demands more blur, so $b$ grows. A large tolerable change $Δ f$ also demands more blur. Dividing puts both pressures in one number.

Exercise 1.3

True/False: Gaussian noise gives pure $ε$ -DP. Justify.

Recall Solution

False. The pure-DP bound needs the ratio of the two noise densities to be capped by $e^{ε}$ everywhere. The Laplace density decays like $e^{- ∣ x ∣/ b}$ , so the log-ratio is a bounded straight line — capped. The Gaussian density decays like $e^{- x^{2} /2 σ^{2}}$ ; its log-ratio grows linearly without bound as $x \to \infty$ , so no finite $e^{ε}$ caps it. Gaussian therefore only gives $(ε, δ)$ -DP (approximate DP), where a small failure probability $δ$ absorbs the uncontrolled tail. See the figure.

Figure — Privacy (differential privacy, membership inference)

Level 2 — Application

Exercise 2.1

Release the mean of $n = 500$ salaries, each in $[0,\$ 200{,}000] $, u n d er * * a dd / r e m o v e * *, w i t h$ \varepsilon=2.0 $. F in d$ \Delta f $an d t h e L a pl a cesc a l e$ b$.

Recall Solution

Sensitivity. Adding/removing one salary moves the sum by at most $200{,}000. The mean divides by $n$ , so $Δ f = \frac{200 , 000}{500} = 400.$ Scale. $b = \frac{Δ f}{ε} = \frac{400}{2.0} = 200.$ So $\tilde{μ} = μ + Lap (200)$ — noise of a few hundred dollars on a salary mean: negligible, strong privacy.

Exercise 2.2

A counting query "how many patients have diabetes?" is released with $ε = 0.5$ . Sensitivity of any count under add/remove is $Δ f = 1$ . What is $b$ , and roughly how large is the typical noise?

Recall Solution

$b = \frac{Δ f}{ε} = \frac{1}{0.5} = 2.$ The Laplace mean absolute deviation equals $b$ , so typical error is about $\pm 2$ people. For a large hospital count this is tiny — counts are cheap to privatize because $Δ f = 1$ .

Exercise 2.3

Same diabetes count, but now you release it twice (two separate noisy answers), each with $ε = 0.5$ . What total $ε$ does an adversary who sees both face? (Use basic composition.)

Recall Solution

Basic composition rule: running mechanisms with budgets $ε_{1}, ε_{2}$ and combining their outputs costs at most $ε_{1} + ε_{2}$ . Here $0.5 + 0.5 = 1.0$ . Why additive and not multiplicative: the log of the probability ratio is what adds. Two independent releases multiply their $e^{ε}$ factors ( $e^{0.5} \cdot e^{0.5} = e^{1.0}$ ), and multiplying $e$ -powers means adding exponents.

Level 3 — Analysis

Exercise 3.1

Prove the Laplace mechanism achieves $ε$ -DP for a scalar query with sensitivity $Δ f$ , by bounding the density ratio at an arbitrary output $z$ .

Recall Solution

Let neighbors give $f (D_{1}), f (D_{2})$ with $∣ f (D_{1}) - f (D_{2}) ∣ \leq Δ f$ . The Laplace density is $p (x) = \frac{1}{2 b} e^{- ∣ x ∣/ b}$ , so at output $z$ : $\frac{p _{D_{1}} ( z )}{p _{D_{2}} ( z )} = \frac{e ^{- ∣ z - f (D_{1}) ∣/ b}}{e ^{- ∣ z - f (D_{2}) ∣/ b}} = exp (\frac{∣ z - f ( D _{2} ) ∣ - ∣ z - f ( D _{1} ) ∣}{b}) .$ By the reverse triangle inequality, $∣ z - f (D_{2}) ∣ - ∣ z - f (D_{1}) ∣ \leq ∣ f (D_{1}) - f (D_{2}) ∣ \leq Δ f$ . Hence the exponent $\leq Δ f / b$ . Choose $b = Δ f / ε$ : $\frac{p _{D_{1}} ( z )}{p _{D_{2}} ( z )} \leq e^{Δ f / b} = e^{ε} . ■$ The bound holds at every $z$ , so integrating over any set $S$ preserves it. Figure shows the two shifted densities and the largest gap between their logs.

Exercise 3.2

Under replace-one neighbors, a summed query can change by two records. If a single record moves the sum by at most $C$ , what is $Δ f$ , and how does $b$ compare to the add/remove case?

Recall Solution

Replace = remove old (up to $C$ ) + add new (up to $C$ ) $\Rightarrow Δ f = 2 C$ . Then $b = \frac{2 C}{ε}$ — twice the noise of add/remove ( $b = C / ε$ ). Same $ε$ , but replace-one is the stricter neighbor definition, so it costs more blur. Always state which definition you use.

Exercise 3.3

In DP-SGD the per-example gradient is clipped to norm $C$ and Gaussian noise of std $σ C$ is added to the sum of a batch of $B$ clipped gradients, then divided by $B$ . Show that the noise on the averaged gradient has std $σ C / B$ per coordinate. Why does the sensitivity of the sum equal $C$ (add/remove)?

Recall Solution

Sensitivity of the sum: removing one clipped gradient (norm $\leq C$ ) from $\sum_{i} \overset{g}{ˉ}_{i}$ changes it by a vector of length $\leq C$ , so $Δ = C$ . Noise on the average: we add $N (0, σ^{2} C^{2} I)$ to the sum, then multiply the whole thing by $1/ B$ . Scaling a Gaussian by constant $1/ B$ scales its std by $1/ B$ : $std_{avg} = \frac{σ C}{B} per coordinate .$ This is the same mechanism described two ways — noise calibrated to the sum's sensitivity $C$ , then averaged.

Level 4 — Synthesis

Exercise 4.1

Run the parent's DP-SGD accounting formula $ε (T) \approx \frac{q 2 T l n ( 1/ δ )}{σ}$ with $q = 0.25$ , $T = 400$ , $σ = 4.0$ , $δ = 1 0^{- 5}$ . Report $ε$ .

Recall Solution

$ln (1/ δ) = ln (1 0^{5}) = 5 ln 10 \approx 11.5129$ . $2 T ln (1/ δ) = 2 \cdot 400 \cdot 11.5129 \approx 9210.3$ ; square root $\approx 95.97$ . $ε \approx \frac{0.25 \times 95.97}{4.0} \approx \frac{23.99}{4.0} \approx 6.00.$ So this run spends roughly $ε \approx 6.0$ — a moderate budget. (In the parent example this is why $σ = 4$ was chosen rather than $σ = 1$ : bigger $σ$ shrinks $ε$ .)

Exercise 4.2

Using the same formula, you want to halve $ε$ (from $6.0$ to $3.0$ ) while keeping $q, T, δ$ fixed. What must $σ$ become? Then explain qualitatively what that does to model accuracy.

Recall Solution

$ε \propto 1/ σ$ at fixed $q, T, δ$ . To halve $ε$ , double $σ$ : $σ = 8.0$ . Check: $ε \approx \frac{0.25 \times 95.97}{8.0} \approx 3.00$ . ✓ Accuracy cost: noise std on the average gradient is $σ C / B$ , so doubling $σ$ doubles the gradient noise. Training is noisier, convergence slower, final accuracy lower. This is the fundamental privacy–utility trade-off.

Exercise 4.3

The formula scales as $T$ , not $T$ . If you train for $4 \times$ as many steps (same $q, σ, δ$ ), by what factor does $ε$ grow? Contrast with what basic composition (linear) would predict.

Recall Solution

Advanced composition: $ε \propto T$ , so $4 \times$ steps $\Rightarrow 4 = 2 \times$ the budget. Basic composition would predict $ε \propto T$ , i.e. $4 \times$ . The savings come because privacy losses of independent steps partly cancel (like a random walk: $T$ steps travel distance $\sim T$ , not $T$ ). Subsampling ( $q$ ) amplifies this further since each person appears in only a $q$ fraction of batches.

Level 5 — Mastery

Exercise 5.1

A hospital releases: (a) a diabetes count at $ε_{1} = 0.5$ ( $Δ f = 1$ ), and (b) a mean age at $ε_{2} = 1.0$ ( $Δ f = 0.1$ , since ages in $[0, 100]$ , $n = 1000$ , add/remove). Give the total budget under basic composition, and the two Laplace scales.

Recall Solution

Scales: count $b_{1} = Δ f / ε_{1} = 1/0.5 = 2$ ; mean age $b_{2} = 0.1/1.0 = 0.1$ . Total budget: basic composition adds $ε$ : $0.5 + 1.0 = 1.5$ . Interpretation: an adversary seeing both noisy answers faces at most a $1.5$ -DP guarantee overall.

Exercise 5.2

You have a fixed total budget $ε_{tot} = 1.0$ and must answer $k = 4$ identical count queries ( $Δ f = 1$ each). Under basic composition you split the budget evenly. Find the per-query $ε$ , the per-query Laplace scale $b$ , and comment on the noise growth as $k$ increases.

Recall Solution

Even split: $ε_{each} = ε_{tot} / k = 1.0/4 = 0.25$ . Scale: $b = Δ f / ε_{each} = 1/0.25 = 4$ . As $k$ grows, $ε_{each} = 1/ k \to 0$ , so $b = k \to \infty$ : noise grows linearly in the number of queries. This is the pressure that motivates advanced composition and subsampling — basic splitting is wasteful.

Exercise 5.3

Membership-inference sanity check. An attacker guesses "was record $r$ in the training set?" by thresholding the model's confidence. Suppose the mechanism is truly $ε$ -DP with $ε = 0$ . What is the maximum advantage (accuracy above random guessing 50%) the attacker can achieve? Explain via the DP inequality.

Recall Solution

With $ε = 0$ , $e^{ε} = 1$ , so for every output set $S$ : $Pr [M (D_{with r}) \in S] = Pr [M (D_{without r}) \in S] .$ The two worlds are identical distributions — no observation distinguishes them. The attacker's best strategy is a coin flip: 50% accuracy, 0% advantage. DP directly caps membership-inference success; larger $ε$ loosens this cap monotonically.