Private online learning regret under composition

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.