Private ERM and private online learning — Examples

The sequences agree at rounds one and three and differ only at round two, where $(0,0)$ is replaced by $(1,0)$, so they are adjacent by [F2]. Both start with weights $(1,1)$, and the common first loss vector $(0,0)$ leaves those weights unchanged; hence the first- and second-round kernels are uniform.

After the second loss vector, the all-zero input still has weights $(1,1)$, while the replaced input has weights $(e^{-\eta },1)$. Dividing by their normalizers yields $(1\mathrm{/}2,1\mathrm{/}2)$ and $(e^{-\eta }\mathrm{/}(1+e^{-\eta }),1\mathrm{/}(1+e^{-\eta }))=(1\mathrm{/}(1+e^{\eta }),e^{\eta }\mathrm{/}(1+e^{\eta }))$.

For the event $\{1\}$ at round three, the all-zero probability divided by the replaced-input probability is $(1\mathrm{/}2)\mathrm{/}(1\mathrm{/}(1+e^{\eta }))=(1+e^{\eta })\mathrm{/}2$. Thus the third-round kernels differ, while their ordered ratios remain covered by the theorem's $(2\eta ,0)$ bound from [F2]; this calculation makes no claim that a transcript-level privacy bound fails.

For $r=0$, the predictions on $0,1,2$ are $(1,1,1)$, which disagree with labels $(0,1,0)$ twice. For $r=1$, predictions are $(0,1,1)$ and disagree once; for $r=2$, predictions are $(0,0,1)$ and disagree twice; for $r=3$, predictions are $(0,0,0)$ and disagree once. Dividing by the three records gives risks $(2\mathrm{/}3,1\mathrm{/}3,2\mathrm{/}3,1\mathrm{/}3)$.

By [F1] with $n=3$, a risk $2\mathrm{/}3$ gives weight $\exp (-3\epsilon (2\mathrm{/}3)\mathrm{/}2)=e^{-\epsilon }$ and a risk $1\mathrm{/}3$ gives weight $\exp (-3\epsilon (1\mathrm{/}3)\mathrm{/}2)=e^{-\epsilon \mathrm{/}2}$. Therefore the normalizer is $Z=2e^{-\epsilon }+2e^{-\epsilon \mathrm{/}2}$.

Dividing the weights by $Z=2e^{-\epsilon \mathrm{/}2}(1+e^{-\epsilon \mathrm{/}2})$ gives probability $1\mathrm{/}[2(1+e^{\epsilon \mathrm{/}2})]$ for each risk-$2\mathrm{/}3$ threshold and probability $e^{\epsilon \mathrm{/}2}\mathrm{/}[2(1+e^{\epsilon \mathrm{/}2})]$ for each risk-$1\mathrm{/}3$ threshold. The four probabilities sum to one, since the two groups have total masses $1\mathrm{/}(1+e^{\epsilon \mathrm{/}2})$ and $e^{\epsilon \mathrm{/}2}\mathrm{/}(1+e^{\epsilon \mathrm{/}2})$.

There are two independent choices for each of the $d$ coordinates of a point in $\{0,1{\}}^d$, so $\mathrm{\mid }\mathcal{X}\mathrm{\mid }=2^d$.

A map $h:\mathcal{X}\to \{0,1\}$ is determined by one binary value at each of the $2^d$ domain points, and every such assignment defines a map. Hence there are $2^{2^d}$ maps, so $\mathrm{\mid }\mathcal{C}\mathrm{\mid }=2^{2^d}$ and $\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }=2^d\ln 2$.

Since $d\ge 1$, $\mathrm{\mid }\mathcal{C}\mathrm{\mid }\ge 2$. Substituting $\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }=2^d\ln 2$ into [F1] gives exactly the displayed sufficient sample-size condition.

By [F2], the normalizer contains $\mathrm{\mid }\mathcal{C}\mathrm{\mid }=2^{2^d}$ terms. Directly computing one empirical risk by evaluating its loss on each of the $m$ records takes $m$ loss evaluations; doing this for every hypothesis uses $m\mathrm{\mid }\mathcal{C}\mathrm{\mid }=m{2}^{2^d}$ such evaluations. This is the cost of that exhaustive procedure; the count alone does not rule out an implementation that exploits structure or samples from the same distribution without explicitly listing every hypothesis.