COMP90073 · Trustworthy Machine Learning · Workshop Week 4

From hiding the row
to bounding the difference

Last week we hid which row is Alice — and the secret leaked anyway.
This week the question changes to would the output look different if Alice had stayed home?

Scan to run the labs on your own device hesamasad.github.io/week-4-dp-workshop

← → or space to navigate · S facilitator notes · O overview · F fullscreen

WEEK 3 RECAP · THE CORE IDEA

k-anonymity hides each row in a crowd of at least \(k\)

1 Remove direct identifiers Name · Student ID Necessary—but not enough.

→

2 Declare the quasi-identifiers \(Q\) Postcode · age · income Values an attacker may already know.

→

3 Make every \(Q\)-pattern repeat

same \(Q\)same \(Q\)same \(Q\)

At least \(k\) rows form one equivalence class.

What the attacker sees: the released quasi-identifiers alone leave at least \(k\) candidate rows. If those candidates are equally likely, a row guess succeeds with probability at most \(1/k\).

WEEK 3 RECAP · THE FORMAL TEST

The smallest equivalence class decides the result

\[ \min_{r \in D}\left|\left\{r' \in D : r'[Q] = r[Q]\right\}\right| \ge k \]

1Pick a row \(r\)from the released dataset \(D\)

→

2Collect its matches \(r'\)identical values across every column in \(Q\)

→

3Count the groupthe smallest such count must be at least \(k\)

In plain language: no released quasi-identifier pattern may occur fewer than \(k\) times.

We will solve the worksheet in order

Q1Incognitoprotect the supplied quasi-identifiers

Q2Randomised responsesolve for \(p\)

Q3Sum and averagecalibrate Laplace noise

Q4One wider valuerecompute sensitivity

Q5Large \(\varepsilon\)interpret the guarantee

Q6Random recordfind a counterexample

Q7Unbounded incomeclip before averaging

Q8Membership inferenceuse post-processing

Q9Compositionadd privacy costs

For every mechanism: name the neighbouring datasets, the possible outputs, and the worst one-person change.

For every guarantee: ask what it forbids after all releases and all attacker knowledge are considered.

WEEK 3 · K-ANONYMITY RECAP

Four matching rows can still reveal one secret

PostcodeAgeLoan

30*21–30Y

equivalence class size \(=4\)identity is ambiguous

If Alice matches this class, what have we learned about her loan?

The homogeneity attack: Alice's row stays ambiguous, but her sensitive value is certain. This limitation motivates stronger table-release models such as \(l\)-diversity and \(t\)-closeness.

THE PIVOT · LECTURE 5

Differential privacy protects the decision to participate

Alice joinsthe study reports that smoking raises cancer risk

≈

Alice stays homethe study reports the same population-level finding

The simple promise: the public result should look almost the same with or without Alice's row. Seeing the result reveals very little about whether she took part. Population-wide facts can still be learned.

The table you generalise

Finding a 3-anonymous table with respect to postcode, age and income is a search problem. Incognito's job is to avoid searching.

Worksheet question 1 · Lecture 4

Week 3 recap · column roles

Removing names does not remove the join key

Namedirect identifierremove before release

\(+\)

Postcode · age · incomequasi-identifiersan attacker may already know these

→

Loan taken?sensitive attributewhat the join can reveal

public or auxiliary datasame quasi-identifiersreleased table

Quasi-identifiers are defined by the outside world. A field need not be unique by itself; a combination can still link a person to a released row.

Week 3 recap · equivalence classes

k-anonymity counts matching groups—not secrets

PostcodeAgeLoan

30*21–30Yes

30*21–30No

30*21–30Yes

31*31–40Yes

class size 3same quasi-identifiers

3-anonymous w.r.t. postcode + age?Yes: every postcode–age pattern appears in at least 3 rows.Attribute-private?Not necessarily: the second class reveals “Yes” in the Loan column.

QUESTION 1 PREREQUISITE · HOW CLASSES GROW

Generalise common values; suppress the stubborn exceptions

GENERALISATION

ZIP 53715→537**

Age 24→20–29

Keep the rows, but replace precise values with broader categories so more \(Q\)-patterns match.

SUPPRESSION

Income 73K→*

rare outlier row→omit

Hide a difficult value—or remove a rare row. After deleting rows, recompute the class sizes.

more specificgeneralise or mask values → classes mergecoarser

Monotonicity: coarsening quasi-identifiers can merge classes, never split them, so the minimum class size cannot decrease. Row deletion is different: it can shrink a class, so recheck \(k\).

Question 1 · the search space

Each attribute has a ladder of coarser values

Postcode30* · 31* · 3[2,4,5]*finest supplied level · P03[0,1]* · 3[2,4,5]*P13*P2

Age21–30 · 31–40 · 41+finest supplied level · A021–30 · 31+A1*A2

Income0–49K · 50–99K · 100K+finest supplied level · I0*I1

Question 1 searches \(3 \times 3 \times 2 = 18\) combinations. Level 0 means the finest values supplied by the worksheet—not the original raw values.

Incognito prunes in two different directions

More attributes →

Income fails

⇒

anything containing Income fails

subset property · failure travels sideways

More generalisation ↑

⟨P0,A2⟩ passes

⇒

coarser versions also pass

rollup property · success travels upward

Keep the directions separate: failure prunes larger attribute sets; success prunes coarser versions of the same set.

Question 1 lab A · Start with the worksheet's original table

These are the exact 12 rows supplied in Question 1. The first three columns are the quasi-identifiers to generalise.

#	Postal code	Age	Income (K)	Loan taken
1	3000	29	100	Y
2	3100	39	70	N
3	3022	22	60	Y
4	3001	46	80	Y
5	3140	41	110	Y
6	3101	27	40	N
7	3200	25	55	Y
8	3516	33	80	N
9	3097	40	30	Y
10	3482	52	50	N
11	3561	41	55	Y
12	3000	25	45	Y

\(Q\)Postcode · age · incomeGeneralise these values until every released pattern has at least 3 rows.

SECRETLoan takenKeep this useful column, but remember that k-anonymity does not protect it from homogeneity.

STARTExact rows are not the releaseIncognito tests the supplied generalisation levels before choosing a safe table.

Target: after applying the supplied hierarchies, every postcode–age–income pattern must occur at least \(k=3\) times.

Question 1 lab B · Run Incognito on those 12 rows

At every step, the right panel shows every current equivalence-class size and tests the smallest one against the chosen \(k\).

Question 1 lab C · Compare the two minimal releases

Two incomparable answers. Both are 3-anonymous over the released postcode–age–income patterns; neither protects the sensitive column.

Where this approach runs out

IT PROTECTS IDENTITY, NOT ATTRIBUTES

A class of \(k\) records that all took the loan tells you the answer without telling you the row. Week 3's homogeneity attack, still working.

IT DEPENDS ON NAMING THE QUASI-IDENTIFIERS

Which columns are “identifying” depends on what external data exists — today and in five years. The guarantee is only as good as that guess.

IT DOES NOT COMPOSE

Two releases can each be 3-anonymous with respect to their chosen quasi-identifiers and still be intersected. Nothing in the definition bounds what happens next.

So change the object being protected. Not “which row is you”, but “whether you are here at all” — a property of the mechanism, which composes, needs no quasi-identifier list, and holds against any auxiliary knowledge.

The guarantee you claim

One inequality, quantified over every neighbouring pair and every output. Both quantifiers do real work.

Question 2 first · Questions 5 and 6 reuse this definition

Prerequisite · neighbouring datasets

A neighbour changes one person's participation

Dataset \(D\)Bob · Chen · Alice · DeeAlice participates

− Aliceone record

Dataset \(D'\)Bob · Chen · DeeAlice stays out

Convention for this workshop: neighbours differ by adding or removing one record. The guarantee must hold for every such pair, not only the dataset we happened to collect.

Prerequisite · what does \(M(\cdot)\) mean?

\(M\) is the randomised algorithm; \(D\) is its input dataset

\(M(D)\)means “run algorithm \(M\) on dataset \(D\)”→one random outputRun it again with fresh randomness and the output may change.

blue area represents \(\Pr[M(D)\in O]\) purple area represents \(\Pr[M(D')\in O]\)

DP requires the two shaded probabilities to stay within an \(e^\varepsilon\) factorfor every region \(O\)

Lecture 6 intuition

Why the mechanism has to be random at all

EXACT AND USEFUL

Unless \(f\) ignores the data entirely, some neighbouring pair gives two different answers. Take \(O\) to be one of them: probability 1 under one dataset, 0 under the other.

not DP for any \(\varepsilon\)

DATA-INDEPENDENT AND PRIVATE

A fixed constant—or noise unrelated to \(D\)—has the same distribution on every dataset. The ratio is 1, but it carries no information about \(f(D)\).

0-DP — and useless

The useful middle: stay near \(f(D)\), while making neighbouring output distributions similar enough that no outcome certifies Alice's participation.

The definition, and where each piece bites

\[ \Pr[M(D_1) \in O] \;\le\; e^{\varepsilon}\, \Pr[M(D_2) \in O] \qquad \text{for all } \|D_1 - D_2\| \le 1 \text{ and all } O \subseteq \mathcal{O} \]

FOR ALL NEIGHBOURING PAIRS

Not the pair you have — every pair differing in one record. This is what makes the guarantee independent of what the adversary already knows.

FOR ALL OUTPUT SETS

A single output set that violates the inequality is a counterexample. Question 6 is exactly this: find one \(O\).

RANDOMNESS OF \(M\) ONLY

The data is fixed; the probability is over the mechanism's coins. So \(M\) may be public, and only the noise draw must stay secret.

Read \(\varepsilon\) as a price, not a probability: it is the privacy cost of a query, and higher \(\varepsilon\) means less noise, more accuracy, and a weaker promise.

QUESTION 5 · READING A LARGE PRIVACY COST

Question 5 lab · What does \(\varepsilon = 50\) actually forbid?

The inequality is satisfied at every \(\varepsilon\). The question is what it still rules out.

QUESTION 6 · A PROOF OBLIGATION, BACKWARDS

“Draw a record at random and return it.” Show this is not \(\varepsilon\)-DP.

WHAT YOU HAVE TO PRODUCE

To prove DP you must show the inequality for every neighbouring pair and every \(O\). To disprove it you need one pair and one \(O\).

\[ \Pr[M(D)=\{d\}] = \tfrac{1}{|D|}, \qquad \Pr[M(D')=\{d\}] = 0 \]

WHY NO \(\varepsilon\) RESCUES IT

The requirement becomes \(\tfrac{1}{|D|} \le e^{\varepsilon} \cdot 0 = 0\), which is false for every finite \(\varepsilon\).

The failure is support, not scale: \(D\) can produce an output that \(D'\) simply cannot. Any mechanism that returns a genuine record has this shape.

Reusable counterexample recipe: choose a neighbouring pair, find one distinguishing output, write its two probabilities, then substitute them into the definition.

Question 6 lab · Find the output that breaks it

Pick which record the neighbouring dataset drops, then compare the two output distributions.

Concept check · what the guarantee does not say

Question 2 prerequisite · who sees the raw data?

Central and local DP move the randomisation point

Central DPpeople → trusted curator → one noisy aggregateThe curator sees raw records.

Local DPperson → randomise locally → curatorThe curator sees only perturbed reports.

Question 2 is local DP. Each respondent protects one bit before sending it; the next slide derives the privacy loss of that local mechanism.

QUESTION 2 · NO TRUSTED CURATOR

Follow the two ways a “Yes” can appear

IF THE TRUE ANSWER IS YES

Report Yes by telling the truth, or by taking the random branch and flipping Yes.

\[ \Pr[\mathsf{Yes}\mid\mathsf{Y}] = p + \tfrac12(1-p) \]

IF THE TRUE ANSWER IS NO

A reported Yes is possible only on the random branch.

\[ \Pr[\mathsf{Yes}\mid\mathsf{N}] = \tfrac12(1-p) \]

ratio\(\frac{1+p}{1-p}=e^\varepsilon\)set \(e^\varepsilon=7\)\(p=\frac34\)

Direction check: a larger \(p\) means more truthful reports, easier inference, and therefore a larger \(\varepsilon\).

Question 2 lab · Turn the privacy dial and watch utility pay

The estimator stays unbiased at every \(p\). Only its interval moves — that is the entire trade.

The noise you calibrate

The mechanism is fixed. All the design work is in one number.

Question 3 · sum and average queries

Prerequisite · measure one person's influence

Sensitivity asks for the largest neighbouring change

Choose neighbours\(D\) and \(D' = D - \{v\}\)

→

Run the query\(f(D)\) and \(f(D')\)

→

Take the worst gap\(\Delta f = \max \|f(D)-f(D')\|_1\)

Prediction:does adding more records reduce sensitivity for a sum, an average, both, or neither?

Worst case means one unusual allowed value sets the scale for everyone. It is a maximum over valid neighbouring pairs, never an average over typical records.

Lecture 6 · turn influence into noise

The Laplace mechanism needs only \(\Delta f\) and \(\varepsilon\)

exact query\(f(D)\) \(+\) fresh random noise\(Y \sim \mathrm{Lap}(\Delta f/\varepsilon)\) \(=\) released answer\(M(D)\)

MORE INFLUENCE

Larger \(\Delta f\) → wider noise.

MORE PRIVACY BUDGET

Larger \(\varepsilon\) → narrower noise and a weaker guarantee.

Why Laplace helps: both neighbouring datasets can produce every real-valued output; their density ratio is controlled by the scale \(\Delta f/\varepsilon\).

QUESTION 3 · WORKED CALIBRATION

Change one record, then divide only if the query does

Q3 · SUM OVER \([l, h]\)

Adding or removing one record moves the sum by at most \(h\).
\(\Delta f = h\), \(b = h/\varepsilon\)

Q3 · AVERAGE OVER \([l, h]\)

The same change, divided by \(n\).
\(\Delta f = h/n\), \(b = h/(n\varepsilon)\)

Worksheet assumption: \(0 \le l < h\). If negative values were allowed, the largest absolute endpoint would matter.

Question 3 lab · Calibrate a sum and an average

Switch the query and sample size; the curve centres stay \(\Delta f\) apart.

QUESTION 4 · CHANGE ONE ASSUMPTION

One wider value doubles the sum's sensitivity

QUESTION 3 BASELINE

Every value lies in \([l,h]\), so one record contributes at most \(h\).

\(\Delta f=h\)

QUESTION 4 CHANGE

Now \(v_1\in[l,2h]\). Removing that one allowed value can change the sum by \(2h\).

\(\Delta f=2h\), so \(b=2h/\varepsilon\)

Sensitivity follows the largest permitted contribution. The maximum is over neighbouring pairs, so one exceptional range sets the noise scale for every release.

QUESTION 4 · CHECK THE CONSEQUENCE

Concept check · one wide value

QUESTION 7 · AN UNBOUNDED DOMAIN

Income starts at 0 and has no upper bound. Now what?

WHY LAPLACE CANNOT BE APPLIED AS IT STANDS

The mechanism needs \(\Delta f\), and \(\Delta f\) is a maximum over what one record can contribute. With no upper bound that maximum is infinite, so the scale \(\Delta f / \varepsilon\) is undefined. There is nothing to calibrate to.

CLIP FIRST, THEN COMPUTE

Choose a bound \(C\) in advance, clip every value to \([0, C]\), then compute. Now \(\Delta f = C/n\) for the mean.

42K88K310K → 100K

Example with a public bound \(C=100\text{K}\).

What clipping costs: a downward bias on everyone above \(C\). Choose \(C\) too high and the noise swamps the answer; too low and the bias does. And bias, unlike noise, does not shrink as \(n\) grows.

Question 7 lab · Choose \(C\): too low biases, too high adds noise

Move the public clipping bound and find the lowest simulated RMSE.

The budget you spend

One release is a calculation. Many releases is an accounting problem.

Optional worksheet question 9 · composition

QUESTION 9 · COMPOSITION

Composition turns repeated releases into a ledger

Query 1\(\varepsilon_1 = 0.2\)

\(+\)

Query 2\(\varepsilon_2 = 0.3\)

\(=\)

Sequence\(\varepsilon_{total} = 0.5\)

\[ M(D)=\big(M_1(D),M_2(D)\big) \text{ is } (\varepsilon_1+\varepsilon_2)\text{-DP}. \]

Question 9: privacy loss degrades predictably. Set a total budget, charge each release, and stop—or redesign—when the ledger is empty.

Question 9 lab · Under one fixed budget, repetition stops helping

Split the same total \(\varepsilon\) across repeated answers, then average them.

Prerequisite for Question 8 · post-processing

Once the release is DP, later computation spends no new privacy

Private dataset\(D\)

→

DP mechanism\(M(D)\)

→

Any data-independent analysischart · threshold · model query · attack

\[ M \text{ is } \varepsilon\text{-DP} \;\Longrightarrow\; g\!\circ\!M \text{ is } \varepsilon\text{-DP}. \]

Processing cannot improve an attack beyond the original guarantee. It also cannot repair a non-private release.

Week 3 recap · membership inference

The attack asks which training world produced the model

World 0Alice is not in training data

trained model
loss or confidence

World 1Alice is in training data

Week 3 best accuracy73%advantage over balanced guessing\(2(0.73)-1=0.46\)

Question 8: if training itself is DP under add/remove neighbours, these two worlds are exactly the pair the guarantee compares.

QUESTION 8 · DOES DP TRAINING STOP THE WEEK 3 ATTACK?

Treat the trained model as the mechanism's output

THE ARGUMENT

If training is \(\varepsilon\)-DP under add/remove neighbours, then models trained with and without Alice have bounded output-distribution ratios.

A membership attack only queries or analyses the released model, so it is post-processing.

THE BOUND, AND ITS SMALL PRINT

\[ \text{membership advantage} \;\le\; e^{\varepsilon} - 1 \]

This is the worksheet's cited bound. Because advantage is at most 1, the expression becomes non-binding once \(\varepsilon \ge \ln 2 \approx 0.69\).

Core answer: yes, DP training bounds membership inference. Then inspect the numerical bound: a theorem can be correct yet non-binding at the chosen \(\varepsilon\).

QUESTION 8 · OPTIONAL NUMERICAL EXTENSION

Question 8 lab · When is the membership bound numerically binding?

The green curve is the bound. The dashed line is week 3's lab 5: 73% attack accuracy at the best threshold, i.e. advantage \(2(0.73)-1=0.46\).

Retrieval map · all nine questions

Nine answers, in worksheet order

Q1Generaliseminimum class size \(3\)

Q2Set \(p\)\(p=3/4\)

Q3Calibrate\(h\) for sum, \(h/n\) for mean

Q4Use \(2h\)one wider value sets the maximum

Q5Read \(e^{50}\)the bound is extremely permissive

Q6Find one \(O\)positive probability versus zero

Q7Clip firstpublish \(C\), then add noise

Q8Use DP trainingmembership attacks are post-processing

Q9Add costs\(\varepsilon_1+\varepsilon_2\)

Self-check: can you explain each answer before moving to the next question?

Take-home principles

01Define the neighbouring worlds.Without a precise adjacency relation, “private” has no testable meaning.

02Bound one person's influence before adding noise.Clip unbounded values using a public, pre-chosen bound.

03Account for the complete release sequence.An \(\varepsilon\) value is meaningful only with the mechanism and the total budget.

Next: \((\varepsilon, \delta)\)-DP, Gaussian noise and DP-SGD reuse the same neighbouring-world and accounting ideas.

Sources

COMP90073 Lecture 4 — K-Anonymity: generalisation, the subset property, Basic Incognito.
Workshop Week 3 — record linkage, equivalence classes, homogeneity and membership inference.
COMP90073 Lecture 5 — Differential Privacy: definition and properties (intuition).
COMP90073 Lecture 6 — Differential Privacy: mathematical definition and mechanisms.
Workshop Week 4 — questions 1–9.
LeFevre, DeWitt & Ramakrishnan (SIGMOD 2005) · Meyerson & Williams (PODS 2004) · Dwork, McSherry, Nissim & Smith (TCC 2006) · Dwork & Naor (2010) · Warner (JASA 1965) · Dwork & Roth (2014), Theorem 3.14 · Yeom, Giacomelli, Fredrikson & Jha (CSF 2018) · Abadi et al. (CCS 2016).

Note: every number on these slides is computed in your browser — the Incognito run counts real equivalence classes in the worksheet's twelve rows, and all other data is synthetic. Nothing is collected.

End of Workshop Week 4

A guarantee that composes
requires three trade-offs.

give up exact answersgive up unlimited queriesgive up hiding population truths

Press O to revisit any lab · S for facilitator notes