Private ERM and private online learning

By induction on $t$, each $w_{t,j}$ is finite and strictly positive: this holds initially since $w_{1,j}=1$, and each update multiplies such a weight by the finite positive number $\exp (-\eta {\mathrm{\ell }}_t(j))$ from [F1]. Since $[k]$ is finite and nonempty, $Z_t:={\sum }_{r=1}^k{w}_{t,r}$ is finite and strictly positive, so every $p_{t,j}$ is defined and nonnegative.

The finite sum of the action probabilities is ${\sum }_{j=1}^k{p}_{t,j}=Z_t\mathrm{/}{Z}_t=1$. For each history $h$, define ${\mu }_t^h(A)={\sum }_{j\in A}{p}_{t,j}(h)$ for $A\subseteq [k]$. This is countably additive because a pairwise disjoint family of subsets of the finite set $[k]$ has only finitely many nonempty members, and ${\mu }_t^h([k])=1$. For each event $A$, the map $h\mapsto {\mu }_t^h(A)$ is measurable since $H_t$ has its power-set sigma-algebra. Hence $K_t$ is a probability kernel by [F3] and [F4].

For each $h\in \mathcal{C}$, its mismatch set is $(h^{-1}\{0\}\times \{1\})\cup (h^{-1}\{1\}\times \{0\})$, a finite union of measurable rectangles by [F1]. Thus each sample loss indicator and the finite average ${\widehat{L}}_S(h)$ are measurable in the ordered sample. By [F2]–[F4], the weight $w_S(h)$ is finite, positive, and measurable in $S$.

Since $\mathcal{C}$ is finite and nonempty, $Z_S:={\sum }_{g\in \mathcal{C}}{w}_S(g)$ is finite, measurable, and strictly positive. For $a\le 0$, $\{S:1\mathrm{/}{Z}_S>a\}$ is the whole sample space; for $a>0$, it is $\{S:Z_S<1\mathrm{/}a\}$, which is measurable by [F5]. Hence $1\mathrm{/}{Z}_S$, and then each $p_S(h):=w_S(h)\mathrm{/}{Z}_S$, is measurable by [F4]. These probabilities sum to one. Define $K(S,A)={\sum }_{h\in A}{p}_S(h)$ for $A\subseteq \mathcal{C}$; it is countably additive because a disjoint family of subsets of finite $\mathcal{C}$ has only finitely many nonempty members, and $K(S,\mathcal{C})=1$. For each $A$, $S\mapsto K(S,A)$ is measurable as a finite sum of measurable functions; on the power-set private-database domain every event evaluation is also measurable. Thus [F6] gives the probability-kernel conditions.

First suppose $0<\eta \le 1$. Write $W_t={\sum }_{j=1}^k{w}_{t,j}$ and ${\mu }_t={\sum }_{j=1}^k{p}_{t,j}{\mathrm{\ell }}_t(j)$. By [F2] with $\rho =\eta$ and $x={\mathrm{\ell }}_t(j)$, $W_{t+1}\mathrm{/}{W}_t={\sum }_j{p}_{t,j}{e}^{-\eta {\mathrm{\ell }}_t(j)}\le 1-\eta {\mu }_t+{\eta }^2$. Both sides are positive: the left side is positive by [F9], and it is at most the right side. Applying the increasing logarithm and then [F4] gives $\ln (W_{t+1}\mathrm{/}{W}_t)\le -\eta {\mu }_t+{\eta }^2$. Summing over $t$ and using $W_1=k$ yields $\ln (W_{T+1}\mathrm{/}k)\le -\eta {\sum }_t{\mu }_t+T{\eta }^2$.

Fix two adjacent loss sequences and a common prior action history. Before round $t$, their cumulative losses differ coordinatewise by at most one, because only one full loss vector was replaced and each coordinate belongs to $[0,1]$. By [F1], [F3], and [F9], the positive unnormalized weights for each action have ratio between $e^{-\eta }$ and $e^{\eta }$. Summing over actions gives the same two-sided bounds for their normalizers. Dividing the weight ratios by the normalizer ratios bounds each action-probability ratio by $e^{2\eta }$ in either order; summing over any event proves the ordered $(2\eta ,0)$ round-kernel inequalities.

For every expert $j$, $W_{T+1}\ge w_{T+1,j}=\exp (-\eta {\sum }_t{\mathrm{\ell }}_t(j))$. The finite set of cumulative losses has a minimizer. Taking logarithms and combining with step 1.1 gives ${\sum }_t{\mu }_t-{\min }_j{\sum }_t{\mathrm{\ell }}_t(j)\le (\ln k)\mathrm{/}\eta +\eta T$. This is a pathwise inequality for every realized sequence, including one selected adaptively from earlier actions.

Set $L=\ln (1\mathrm{/}\delta )>0$. Apply [F8] with ${\epsilon }_r=2\eta >0$, ${\delta }_r=0$, and ${\delta }^{\mathrm{\prime }}=\delta \in (0,1)$; its remaining parameter condition holds since $T{\delta }_r+{\delta }^{\mathrm{\prime }}=\delta <1$. The composed privacy parameter is $2\eta \sqrt{2TL}+2T\eta (e^{2\eta }-1)$. The first cap in $\eta$ bounds the first summand by $\epsilon \mathrm{/}2$. The second cap gives $2\eta \le 1$; [F2] with $\rho =2\eta$ and $x=-1$ gives $e^{2\eta }-1\le 2\eta +4{\eta }^2\le 4\eta$. The third cap therefore bounds the second summand by $8T{\eta }^2\le \epsilon \mathrm{/}2$. Their sum is at most $\epsilon$, and the composed failure probability is $T\cdot 0+\delta =\delta$. This proves transcript $(\epsilon ,\delta )$-privacy under [A1].

Under the filtration in the Statement, ${\mathrm{\ell }}_t$ and $p_{t,j}$ are measurable before the draw and the conditional law of $a_t$ is $p_t$. All losses and their conditional averages are bounded by one. For every event $B\in {\mathcal{F}}_{t-1}$ and action $j$, [F1] gives $\mathrm{Pr}(B\cap \{a_t=j\})=\mathbb{E}[{\mathbf{1}}_B{p}_{t,j}]$. Summing over the finite action set gives $\mathbb{E}[{\mathbf{1}}_B{\mathrm{\ell }}_t(a_t)]=\mathbb{E}[{\mathbf{1}}_B{\sum }_j{p}_{t,j}{\mathrm{\ell }}_t(j)]=\mathbb{E}[{\mathbf{1}}_B{\mu }_t]$. Thus [F5] makes ${\mu }_t$ a conditional-expectation version and $X_t={\mathrm{\ell }}_t(a_t)-{\mu }_t$ has conditional mean zero. Taking $B=\mathrm{\Omega }$ gives $\mathbb{E}[{\mathrm{\ell }}_t(a_t)]=\mathbb{E}[{\mu }_t]$. Taking expectations in step 2.1 therefore proves the expected-regret inequality when $\eta \le 1$. If $\eta >1$, then $R_T\le 1<\eta$, since each average loss lies in $[0,1]$; this proves the same expected bound for every $\eta >0$.

Each $X_t$ is ${\mathcal{F}}_t$-measurable, and step 3.1 shows its conditional mean given ${\mathcal{F}}_{t-1}$ is zero. Since $0\le {\mu }_t\le 1$, it lies in the finite predictable interval $[-{\mu }_t,1-{\mu }_t]\subseteq [-1,1]$, so $X_t$ is integrable and this interval has length one. By [F6] under AC [A1], $(X_t)$ is a martingale-difference sequence; its partial sums are a martingale by the conditional-mean-zero property. Apply [F7] with the predictable endpoints $A_t=-{\mu }_t$, $B_t=1-{\mu }_t$ and $c_t=1$ to obtain $\mathrm{Pr}({\sum }_t{X}_t\ge s)\le e^{-2s^2\mathrm{/}T}$ for $s>0$. The realized regret numerator equals ${\sum }_t{X}_t+{\sum }_t{\mu }_t-{\min }_j{\sum }_t{\mathrm{\ell }}_t(j)$; step 2.1 bounds its second term. Taking $s=\sqrt{T\ln (1\mathrm{/}\beta )\mathrm{/}2}$ gives the displayed tail bound for $\eta \le 1$. If $\eta >1$, then $R_T\le 1<\eta$ deterministically, so the asserted tail bound also holds. When $k=1$, the only action is the comparator, hence $R_T=0$.

For $k\ge 2$, substituting $\eta =\sqrt{\ln k\mathrm{/}T}$ in the expected bound of step 3.1 gives $\eta +\ln k\mathrm{/}(\eta T)=2\sqrt{\ln k\mathrm{/}T}$. For the privacy choice, since $\eta$ is the minimum of three positive numbers, $1\mathrm{/}\eta =\max \{\sqrt{32TL}\mathrm{/}\epsilon ,2,4\sqrt{T\mathrm{/}\epsilon }\}$. Substitution in the high-probability bound of step 4.1 gives the stated exact capped expression. The first cap alone is attained by ${\eta }_0$ exactly when the other two hold: ${\eta }_0\le 1\mathrm{/}2$ is equivalent to $\epsilon \le \sqrt{8TL}$, and ${\eta }_0\le \sqrt{\epsilon \mathrm{/}(16T)}$ is equivalent to $\epsilon \le 2L$. In that region, substitution gives the stated specialization. Finally, for adjacent interactive strategies, their stated common-history ordered kernel inequalities are precisely the roundwise hypothesis of [F8]; applying it with the same parameters and the estimates in step 2.2 proves the same transcript guarantee.

Let $D,D^{\mathrm{\prime }}$ be neighboring databases in the restricted domain and orient them so $D^{\mathrm{\prime }}$ is obtained from $D$ by adding one record $z=(x,y)$. Since both databases are in the domain, $m:=\mathrm{\mid }D\mathrm{\mid }\ge n$. For $q_h=\mathbf{1}\{h(x)\mathrm{\ne }y\}\in \{0,1\}$, ${\widehat{L}}_{D^{\mathrm{\prime }}}(h)-{\widehat{L}}_D(h)=(m{\widehat{L}}_D(h)+q_h)\mathrm{/}(m+1)-{\widehat{L}}_D(h)=(q_h-{\widehat{L}}_D(h))\mathrm{/}(m+1)$. As $q_h,{\widehat{L}}_D(h)\in [0,1]$, this difference has absolute value at most $1\mathrm{/}(m+1)\le 1\mathrm{/}n$; reversing the pair gives the same bound.

For a fixed sample $S$, let ${\widehat{L}}_{\ast }={\min }_{h\in \mathcal{C}}{\widehat{L}}_S(h)$, which exists because the class is finite and nonempty. For any $t>0$, the selector's probability that ${\widehat{L}}_S(H)>{\widehat{L}}_{\ast }+t$ is at most $\mathrm{\mid }\mathcal{C}\mathrm{\mid }\exp (-\epsilon n({\widehat{L}}_{\ast }+t)\mathrm{/}2)\mathrm{/}\exp (-\epsilon n{\widehat{L}}_{\ast }\mathrm{/}2)=\mathrm{\mid }\mathcal{C}\mathrm{\mid }{e}^{-\epsilon nt\mathrm{/}2}$: each event weight is bounded by the numerator term and the normalizer includes a minimizer's weight. With $t=\frac{2}{\epsilon n}(\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }+\ln (2\mathrm{/}\beta ))>0$, this probability is at most $\beta \mathrm{/}2$.

Apply [F3] with $\gamma =\beta \mathrm{/}2$. With probability at least $1-\beta \mathrm{/}2$, all $h\in \mathcal{C}$ satisfy $\mathrm{\mid }{L}_P(h)-{\widehat{L}}_S(h)\mathrm{\mid }\le a$, where $a=\sqrt{(\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }+\ln (4\mathrm{/}\beta ))\mathrm{/}(2n)}$.

Write $w_D(h)=\exp (-\epsilon n{\widehat{L}}_D(h)\mathrm{/}2)$ and $Z_D={\sum }_{g\in \mathcal{C}}{w}_D(g)$. By [F5] and step 1.1, $e^{-\epsilon \mathrm{/}2}\le w_D(h)\mathrm{/}{w}_{D^{\mathrm{\prime }}}(h)\le e^{\epsilon \mathrm{/}2}$ for each $h$. Summing gives the same two-sided bounds for $Z_D\mathrm{/}{Z}_{D^{\mathrm{\prime }}}$. Each weight and normalizer is positive and finite because the class is finite nonempty and [F5] makes every exponential weight positive. The normalized finite weights therefore form a probability measure on the output class; because the restricted database domain has the power-set sigma-algebra, every event-evaluation function is measurable, so this is a probability kernel. Therefore $(w_D(h)\mathrm{/}{Z}_D)\mathrm{/}(w_{D^{\mathrm{\prime }}}(h)\mathrm{/}{Z}_{D^{\mathrm{\prime }}})\le e^{\epsilon }$. Summing over any event $A\subseteq \mathcal{C}$ proves $K(D,A)\le e^{\epsilon }K(D^{\mathrm{\prime }},A);$ interchanging $D,D^{\mathrm{\prime }}$ proves the reverse ordered inequality. By [F1] this is pure $\epsilon$-DP.

For every fixed sample, step 1.2 bounds the conditional selector failure probability by $\beta \mathrm{/}2$, so averaging over the sample gives the same joint failure bound. Intersect that utility event with the deviation event from step 1.3; [F4] gives probability at least $1-\beta$. On the intersection, ${\widehat{L}}_S(H)\le {\min }_g{\widehat{L}}_S(g)+t$, $L_P(H)\le {\widehat{L}}_S(H)+a$, and for every $h\in \mathcal{C}$, ${\min }_g{\widehat{L}}_S(g)\le {\widehat{L}}_S(h)\le L_P(h)+a$. Taking the infimum over $h$ in the last inequality and combining yields $L_P(H)-{\inf }_h{L}_P(h)\le 2a+t$, which is the displayed excess-risk bound.

Suppose $\mathrm{\mid }\mathcal{C}\mathrm{\mid }\ge 2$ and write $Q=\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }+\ln (1\mathrm{/}\beta )\ge \ln 2$. Then $\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }+\ln (4\mathrm{/}\beta )=Q+\ln 4\le 3Q$ and $\ln \mathrm{\mid }\mathcal{C}\mathrm{\mid }+\ln (2\mathrm{/}\beta )=Q+\ln 2\le 2Q$. The sample-size condition gives $2\sqrt{3Q\mathrm{/}(2n)}\le \alpha \mathrm{/}2$ and $4Q\mathrm{/}(\epsilon n)\le \alpha \mathrm{/}6$, so the bound in step 2.2 is at most $2\alpha \mathrm{/}3\le \alpha$. If $\mathrm{\mid }\mathcal{C}\mathrm{\mid }=1$, its only classifier is always selected and minimizes population risk over that class, so its excess is zero.