Privacy (differential privacy, membership inference): Visual walkthrough

This page builds one central result from nothing: why adding Laplace noise of the right size hides any single person. We start from the picture of a query, meet the ratio-of-densities that privacy really means, and watch — step by step — how the shape of the Laplace distribution forces the guarantee $e^{ε}$ into existence.

New here? Read the Hinglish version of the parent topic alongside this.

Step 1 — What is a "query" and why does one person move it?

Now the key move: take one person out of the spreadsheet. The average shifts a little. Two spreadsheets that differ by exactly one person are called neighboring datasets.

Figure — Privacy (differential privacy, membership inference)

WHAT we did: named the query and its neighbor. WHY: privacy is about hiding one person, so we must measure how much one person can move the answer. PICTURE: in the figure the two spreadsheets sit side by side; the yellow bracket is the tiny gap $f (D_{1}) - f (D_{2})$ that one person opens up.

Step 2 — Sensitivity: the biggest one person can ever move the answer

If we want to hide any individual, we must prepare for the worst individual — the one who moves the answer the most.

WHY the maximum, not a typical case: DP is a guarantee, not an average. If the loudest possible person is hidden, everyone quieter is hidden too. PICTURE: the figure fans out several possible one-person changes; the longest arrow is $Δ f$ .

Step 3 — What "private" actually means: a ratio of two chances

Here is the whole idea in one sentence: an attacker who sees the released number must not be able to tell $D_{1}$ from $D_{2}$ . If the number looks equally likely under both, the attacker learns nothing about that one person.

Because we will add randomness, the mechanism $M$ does not output one fixed number — it outputs a spread of possible numbers. For discrete outputs we compare their probabilities; for continuous outputs (like Laplace noise) we compare their probability densities — the height of the curve at $z$ , written $p_{M (D)} (z)$ . The definition below is stated for densities; for discrete mechanisms just read "density" as "probability."

WHAT: turned "can't tell them apart" into a bounded ratio of densities, quantified over all neighbors and all outputs. WHY the ratio: an attacker's confidence is a likelihood ratio; capping it caps their confidence. PICTURE: two bell-ish curves for $D_{1}$ and $D_{2}$ ; at any observed $z$ their heights must stay within a factor $e^{ε}$ .

Step 4 — Why the Laplace shape is the exact tool for this

We need a noise distribution whose density at any value falls off in a way that produces a constant ratio bound. The magic property we want is: when you shift the whole curve sideways by $δ$ , the ratio of heights is capped no matter where you look.

PICTURE: on a log scale the Laplace becomes a tent — two straight lines. Sliding the tent sideways keeps the straight sides parallel; the vertical gap between them is constant. That constant is the guarantee.

Step 5 — The derivation: force the ratio below $e^{ε}$

Now we glue Steps 2–4 together. The mechanism draws a random noise sample $η$ from the Laplace distribution and adds it to the true answer: $M (D) = f (D) + η, η \sim Lap (b) meaning η has density p (η) = \frac{1}{2 b} e^{- ∣ η ∣/ b} .$ Here " $η \sim Lap (b)$ " is just shorthand for " $η$ is drawn at random with the Laplace density above." Consequently the output $M (D)$ has density $p_{M (D)} (z) = \frac{1}{2 b} e^{- ∣ z - f (D) ∣/ b}$ — the same tent, recentered on $f (D)$ .

Write $δ = f (D_{1}) - f (D_{2})$ , so $∣ δ ∣ \leq Δ f$ by Step 2. Plug both datasets into the density and divide:

= \frac{\tfrac{1}{2b}e^{-|z - f(D_1)|/b}}{\tfrac{1}{2b}e^{-|z - f(D_2)|/b}} = e^{\bigl(|z - f(D_2)| - |z - f(D_1)|\bigr)/b}$$ - $z - f(D_1)$ ::: how far the observed value $z$ is from the *true* answer under $D_1$ - the $\tfrac{1}{2b}$ cancels ::: the normalizers are identical, so only the exponents survive - the exponent ::: a **difference of two distances** — this is where the triangle inequality strikes Now the crucial bound. We use the **reverse triangle inequality**, which in its exact form says $$|a| - |c| \;\le\; |a - c| \qquad \text{for any real } a, c.$$ Setting $a = z - f(D_2)$ and $c = z - f(D_1)$, note $a - c = f(D_1) - f(D_2)$, so $$\bigl|\,z-f(D_2)\,\bigr| - \bigl|\,z-f(D_1)\,\bigr| \;\le\; \bigl|\,f(D_1)-f(D_2)\,\bigr| = |\delta| \le \Delta f.$$ So the exponent is at most $\Delta f / b$, giving $$\frac{p_{\mathcal{M}(D_1)}(z)}{p_{\mathcal{M}(D_2)}(z)} \;\le\; e^{\Delta f / b}.$$ Finally **choose** $b = \dfrac{\Delta f}{\varepsilon}$, and $\Delta f / b = \varepsilon$: $$\boxed{\;\frac{p_{\mathcal{M}(D_1)}(z)}{p_{\mathcal{M}(D_2)}(z)} \;\le\; e^{\varepsilon}\;}$$ ![[deepdives/dd-ai-ml-6.4.10-d2-s05.png]] **WHAT**: reduced the ratio to one exponent, bounded that exponent by sensitivity, then set $b$ to hit exactly $\varepsilon$. **WHY the triangle inequality**: it is the tool that converts "distance to $z$" (which we don't control) into "distance between answers" (which is at most $\Delta f$). **PICTURE**: the figure overlays the two shifted tents; the vertical gap of the two straight sides is $\Delta f / b$, and we tune $b$ until that gap equals $\varepsilon$. --- ## Step 6 — Edge and degenerate cases (never leave the reader stranded) > [!formula] All the corner cases in one place > - **$\delta = 0$ (query unchanged by that person)**: exponent $=0$, ratio $=1 \le e^{\varepsilon}$. Fine — no noise even needed. > - **$\delta$ negative (person *lowers* the answer)**: absolute values make the bound symmetric, so it holds identically. The tent slides the other way; same flat gap. > - **$z$ far in the tail**: because both sides are *straight* on the log plot with the *same* slope, the gap does **not** grow. This is exactly why Gaussian fails and Laplace does not. > - **$\varepsilon \to 0$ (perfect privacy)**: then $b = \Delta f/\varepsilon \to \infty$ — infinite noise, useless answer. Privacy and accuracy trade off. > - **$\varepsilon \to \infty$ (no privacy)**: $b \to 0$, no noise, exact answer released. > - **Replace-one neighbors instead of add/remove**: one person can change *two* records' worth, so $\Delta f$ doubles → noise doubles. State your definition every time. ![[deepdives/dd-ai-ml-6.4.10-d2-s06.png]] **WHY this step exists**: a guarantee that only works for "nice" $z$ or positive $\delta$ is no guarantee. The absolute values and the straight-line tails are precisely what make it universal. --- ## Step 7 — Worked number: DP mean of 1000 ages > [!example] Putting the machine to work > **Task**: release the mean of $n=1000$ ages in $[0,100]$ at $\varepsilon = 1.0$ (add/remove). > - **Sensitivity** (Step 2): $\Delta f = 100/1000 = 0.1$ > - **Scale** (Step 5): $b = \Delta f / \varepsilon = 0.1 / 1.0 = 0.1$ > - **Release**: $\tilde\mu = \mu + \eta$, with $\eta \sim \text{Lap}(0.1)$ > - **Spread**: the Laplace with $b=0.1$ has standard deviation $b\sqrt{2} \approx 0.141$ years, and $95\%$ of the noise lies within $\pm b\ln(1/0.05)\approx \pm 0.30$ years. > > A tenth-of-a-year wobble buys full $\varepsilon = 1$ privacy over a thousand people. **That** is why DP is beloved for population statistics. > [!mistake] Two traps > - Forgetting to divide the sum's sensitivity ($100$) by $n$ — you'd add $10\times$ too much noise. > - Using replace-one but plugging in add/remove sensitivity — half the noise you need, guarantee broken. --- ## The one-picture summary ![[deepdives/dd-ai-ml-6.4.10-d2-s07.png]] > [!recall]- Feynman retelling — the whole walkthrough in plain words > We started with a question you ask a spreadsheet — like "average age." Take one person out, and the answer twitches. The biggest that twitch can *ever* be, over the worst possible person, is a single number called **sensitivity**, $\Delta f$. > > "Private" means: someone watching the released number cannot tell whether that one person was in or out. We made that precise as a **ratio of two densities** — the chance-density of seeing this number if the person was in, over the chance-density if they were out — and we demand that ratio stay below $e^{\varepsilon}$ *for every neighbor pair and every observable value*. > > To force it, we draw random noise shaped like a **tent** ($\eta \sim \text{Lap}(b)$) and add it, because on a log plot a tent is two straight lines. Sliding a tent sideways (which is what removing a person does) keeps the sides parallel, so the gap between the two curves is a **flat cap** everywhere — even far out in the tails. The reverse triangle inequality ($|a|-|c|\le|a-c|$) tells us that cap is at most $\Delta f / b$, and we simply dial the tent's width to $b = \Delta f/\varepsilon$ so the cap lands exactly on $e^{\varepsilon}$. > > Corner cases all fall out: zero change needs no noise; negative changes are symmetric; tails stay bounded; tiny $\varepsilon$ means huge noise (max privacy), huge $\varepsilon$ means no noise. One tent, tuned by one number, hides one person. > [!recall]- > What single number caps how much one person can move a query? ::: The sensitivity $\Delta f$ > Over what must the $\varepsilon$-DP bound hold? ::: All neighboring datasets $D_1,D_2$ and all outputs $z$ > What must the ratio $p_{\mathcal{M}(D_1)}(z)/p_{\mathcal{M}(D_2)}(z)$ stay below? ::: $e^{\varepsilon}$ > Why Laplace and not Gaussian for pure $\varepsilon$-DP? ::: Its log is a straight line ($-|x|/b$), so shifting keeps a constant ratio in every tail > What scale $b$ achieves $\varepsilon$-DP? ::: $b = \Delta f / \varepsilon$ > Which inequality (exact form) converts distance-to-$z$ into distance-between-answers? ::: The reverse triangle inequality, $|a|-|c|\le|a-c|$