Advanced composition and the exponential mechanism

Before ThisWhere Lecture 13 Left Off

Lecture 13 opened Chapter 5. It defined differential privacy as a bound on the ratio of output probabilities over neighboring datasets, and established the three properties that price everything later: postprocessing is free, groups cost $k\eps$ and parallel mechanisms add their epsilons. It built two mechanisms. Randomized response perturbs each row with coins and achieves $\ln 3$-DP with error $O(1/\sqrt{n})$. The Laplace mechanism perturbs the answer with noise scaled to sensitivity and achieves error $O(1/(\eps n))$. It closed with the relaxation to $(\eps, \delta)$-DP and the Gaussian mechanism. Basic composition was the only composition theorem on the table. Its cost is $k\eps$ for $k$ runs.

This LectureWhat It Adds

This lecture replaces that linear cost. Advanced composition bounds the cumulative loss of $k$ mechanisms by about $\eps\sqrt{2k\ln(1/\delta')}$ plus a second-order term, at the price of a slack $\delta'$, and holds even when queries are chosen adaptively. The proof reduces every mechanism to a binary(ish) pair of random variables, then controls two bad events with a union bound and Hoeffding's inequality. The second half generalizes the output type. The exponential mechanism takes a score function on candidate objects and samples proportionally to $\exp(\eps \cdot s/(2\Delta s))$, with privacy from the score sensitivity and accuracy within $O((\Delta s/\eps)\ln|\mathcal{H}|)$ of the best score, where $\mathcal{H}$ is the set of candidate objects. The applications follow in a chain: the Laplace mechanism as a special case, the digital auction with its near-optimal private price, private Probably Approximately Correct (PAC) learning with its extra sample-complexity term and batch query answering, where the Gaussian mechanism plus advanced composition answers $o(n^2)$ queries accurately and sets up the Small Database (SmallDB) lecture.

Study PlanWhat to Read, in Lecture Order

1. Chapter 5 §7: Advanced composition. The theorem, the binary(ish) reduction, the two events $E_1$ and $E_2$ and the Hoeffding inequality step. Step through the composition stage, then compare budgets in the lab at three epsilons.
2. §8: The exponential mechanism. The auction motivation, the definition, the two-factor privacy proof and the accuracy theorem. The stage sweeps epsilon over the output distribution.
3. §9: Applications. Laplace as a score sampler, the digital auction's sensitivity calculation, private Probably Approximately Correct (PAC) learning and the two batch-answering error bounds.

PracticeExercises for This Lecture

• Basic versus advanced composition, computing both totals for $10^4$ mechanisms at $\eps = 0.01$ and reading off the saving.
• The auction sensitivity, proving $\Delta s \le 1$ for the revenue score and stating the resulting privacy.