Property 3.4 — the Net mechanism is (2α, δ)-useful once α ≥ (2Δ/ε) log(|N_α(C)|/δ)

Let $X$ be a finite data universe, $n\ge1$ the input size, and $\mathcal Q$ any class of real-valued queries on databases (not necessarily counting queries). Let $\Delta$ be an upper bound on the global sensitivities, $GS_Q\le\Delta$ for every $Q\in\mathcal Q$; the paper takes $\Delta=\max_{Q\in\mathcal Q}GS_Q$. Let $N$ be a minimum $\alpha$-net for $\mathcal Q$, and assume the Net mechanism's quality score $q(z,D')=-\max_{Q\in\mathcal Q}|Q(z)-Q(D')|$ is real-valued (the family $|Q(z)-Q(D')|$, $Q\in\mathcal Q$, is bounded for each input $z$ and each $D'\in N$) and has positive sensitivity. If $\varepsilon>0$, $0<\delta\le1$ and

then the Net mechanism run on $N$ is $(2\alpha,\delta)$-useful for $\mathcal Q$: for every input $z\in X^n$, with probability at least $1-\delta$ its output $\hat D$ satisfies $|Q(\hat D)-Q(z)|\le 2\alpha$ for all $Q\in\mathcal Q$.

This is the paper's general reduction: the accuracy of the Net mechanism is governed only by the sensitivity of the queries and the size of the smallest α-net.

Formalization Note The paper's "$\log N_\alpha(C)/\delta$" is the logarithm of $|N_\alpha(C)|/\delta$. Stating the result for every common upper bound $\Delta$ of the sensitivities contains the paper's case $\Delta=\max_Q GS_Q$ and avoids a junk supremum when the class is infinite. The boundedness hypothesis is the paper's typing $q:X^*\times R\to\mathbb R$; the hypothesis $GS_q>0$ is where the exponential mechanism's formula is defined. Neighbours differ in exactly one entry.