Theorem 3.11 — an ε-DP mechanism (α, δ)-useful for C on databases of size n ≤ VCDIM(C)/2 has α ≥ Ω(1/(4+16ε))

The paper writes $\Omega(\cdot)$; here it is an absolute constant. There is a constant $c > 0$ with the following property. Let $X$ be any data universe, $C$ any class of predicates $\varphi : X \to \{0,1\}$ (identified with their counting queries), and $n \ge 1$ with

Let $0 \le \epsilon \le 1$ and $0 < \delta \le 1/4$. Let $M$ be a mechanism mapping each input database $z \in X^n$ to a probability distribution on an output space $O$, with a readout $\mathrm{ans}$ that is measurable in the output for every $\varphi \in C$. If $M$ is $\epsilon$-differentially private and $(\alpha,\delta)$-useful for $C$, then

In words: on databases smaller than half the VC-dimension of $C$, no differentially private mechanism can answer every query of $C$ to within a constant error. Together with the paper's upper bound (the net mechanism, useful once $n$ grows linearly in $\mathrm{VCDIM}(C)$), this shows that the dependence of the sample size on the VC-dimension is necessary.

Formalization Note The constant $c$ is quantified before the universe, the class, the size and the mechanism, so it is absolute. The paper's hypothesis "$0 < \delta < 1$ bounded away from $1$ by a constant" is not what its proof supports: keeping the failure probability $\delta$, the proof gives $(1-\delta)(1-2\alpha) \le e^{\epsilon}(\delta+2\alpha)$, which bounds $\alpha$ away from $0$ only when $\delta < 1/(1+e^{\epsilon})$ (about $0.27$ at $\epsilon = 1$). The explicit threshold $\delta \le 1/4$ is used instead. Neighbouring databases differ in exactly one entry (the paper's "$|D\Delta D'| \le 1$" read as replace-one). Mechanisms are arbitrary measurable-output randomized maps (the paper's synthetic-database mechanisms are a special case). $n \ge 1$ excludes the empty database, on which every mechanism is private. VC-dimension is $\mathbb N \cup \{\infty\}$-valued.