Foundations — Privacy (differential privacy, membership inference)

Before we can read a single line of the parent privacy note, we need to earn every symbol it fires at us. Below, each idea is built from nothing, drawn as a picture, and then justified — why does the topic need this? Nothing is assumed.

1. A dataset $D$ — the pile of records

Plain words. Think of a filing cabinet. Each drawer is a person. $D$ is the whole cabinet.

The picture.

Why the topic needs it. Every privacy question is "what does removing one drawer do?" You cannot ask that until you have named the cabinet $D$ and its drawers $x_i$.

The subscript $i$ is just a counter: $x_1$ is the first record, $x_7$ the seventh. The symbol $n=|D|$ (read "the size of $D$") counts the drawers.

2. Neighboring datasets $D_1$ and $D_2$ — the cabinet with one drawer changed

Privacy is about one person's influence. So we compare two cabinets that differ by exactly one drawer.

The picture.

Why two flavours? Look at the figure. Under replace-one, a sum can move by two records' worth (one leaves, one enters), so any change caused by a person is potentially doubled versus add/remove. The parent note pins down which one it uses in every derivation for exactly this reason.

3. Probability $\mathrm{Pr}[\cdot ]$ — how often something happens

The symbol $\mathrm{Pr}[A]$ reads "the probability of event $A$": a number from $0$ (never) to $1$ (always).

$\mathrm{Pr}[\mathcal{M}(D)\in S]$ reads: "the probability that the mechanism's output lands inside the set of outputs $S$." Here $\in$ means "is a member of," and $S$ is just "some collection of outputs we care about" (e.g. "all answers above 50").

4. A mechanism $\mathcal{M}$ — the noisy answer machine

The picture.

Why "randomized"? A deterministic machine (same input → same output every time) would leak: change one drawer, watch the single answer flip, and you'd know that drawer mattered. Randomness hides the flip inside noise. That is the whole trick.

Examples of $\mathcal{M}$ in ML: computing a gradient, releasing a mean, publishing model weights.

5. The exponential $e^{\epsilon }$ — the "how much closer" dial

Two new symbols: $e$ and $\epsilon$.

• $\epsilon$ (Greek "epsilon") is a small positive number we choose. It is the privacy budget: small $\epsilon$ = strong privacy, large $\epsilon$ = weak privacy.
• $e\approx 2.718$ is a fixed constant, the base of natural growth. $e^{\epsilon }$ means "$e$ raised to the power $\epsilon$."

The key small-number fact. For tiny $\epsilon$, $e^{\epsilon }\approx 1+\epsilon .$ So $\epsilon =0.1$ means output probabilities differ by at most $\approx 10\%$. That is how you read an epsilon.

The picture.

Now the parent's central inequality is readable: $\mathrm{Pr}[\mathcal{M}(D_1)\in S]\le e^{\epsilon }\cdot \mathrm{Pr}[\mathcal{M}(D_2)\in S].$ It says: for neighbors, no output becomes more than an $e^{\epsilon }$ factor more likely. Whether your drawer is in or out, every answer keeps almost the same chance.

6. A query $f(D)$ and its sensitivity $\Delta f$ — how loud is one person?

$f(D)$ is a query: a plain function that reads the dataset and returns a number (e.g. "the mean age"). No randomness yet — that's the mechanism's job.

Reading the symbols. $\max$ means "the largest over all choices." The vertical bars $|\cdot |$ mean absolute value — distance from zero, always non-negative, so $|-3|=3$. So $\Delta f$ is "the worst-case wobble one person can cause."

Why the topic needs it. To hide one person, we must add enough noise to drown out that person's worst-case wobble. If a person can move the answer by $\Delta f=100$, whispering $\pm 0.1$ of noise is useless. Sensitivity tells the mechanism how loud to be.

7. Laplace noise $\text{Lap}(b)$ — the noise shaped for the exponential

Why this exact shape? Its formula already has an exponential of an absolute value, $e^{-|x|/b}$. Because the DP promise is about a ratio of exponentials, dividing one Laplace density by a shifted one gives another clean exponential — which lands you exactly at $e^{\epsilon }$. Gaussian noise (the bell curve) has $e^{-x^2}$ instead, and the squared term breaks the clean bound — that's why Gaussian gives only approximate DP, needing an extra symbol $\delta$.

Set $b=\Delta f/\epsilon$: louder person (big $\Delta f$) ⇒ wider noise; stricter budget (small $\epsilon$) ⇒ wider noise. Both directions match intuition.

8. Gradients ${\nabla }_{\theta }\ell$, clipping norm $C$, and the model $\theta$

The parent applies all this to training. Three final symbols:

• $\theta$ (theta): the model's parameters — the pile of numbers being learned.
• $\ell (\theta ,x_i)$: the loss on record $x_i$ — a number scoring "how wrong" the model is on that one example.
• ${\nabla }_{\theta }\ell$ (nabla): the gradient — the arrow pointing in the direction that increases the loss fastest. Training steps against it. Crucially, this arrow is computed from one person's data, so it can carry that person's fingerprint.

Why clip? An uncapped gradient can be arbitrarily long, so one person's wobble $\Delta f$ is unbounded → infinite noise required → useless. Clipping forces each person's contribution to length $\le C$, so under add/remove the sum of gradients has sensitivity exactly $C$. Now we know how loud to whisper.

The prerequisite map

Read it top-down: records build neighbors, neighbors build sensitivity, sensitivity plus the exponential and Laplace noise build the DP guarantee, and gradients-with-clipping feed that whole machine into training.

Equipment checklist

Cover the right side and answer aloud before opening the parent note.