$\displaystyle+\left(\frac{n-kb}{n-b}\right)\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2r}\mid\mathcal{\mathcal{H}}\setminus\mathcal{G}\right].$
(B.14)

Define the sets

$\hat{\mathsf{s}}_{i}=\mathsf{s}(i)\setminus
i\quad\text{and}\quad\overline{\mathsf{s}}=\tilde{\mathsf{s}}(B)\cap\tilde{\mathsf{s}}(C).$

With an abuse of notation, we let

$\displaystyle\psi(D_{i},\hat{\eta}(D_{j},D_{\hat{\mathsf{s}}_{k}}))$
$\displaystyle=\psi(D_{i},\hat{\eta}(D_{j}\cap D_{\hat{\mathsf{s}}_{k}}\cap
D_{\overline{\mathsf{s}}}))\quad\text{and}$ $\displaystyle
h(D_{i},D_{j},D_{\hat{\mathsf{s}}_{k}})$
$\displaystyle=\psi(D_{i},\hat{\eta}(D_{j},D_{\hat{\mathsf{s}}_{k}}))-\psi(D_{j},\hat{\eta}(D_{i},D_{\hat{\mathsf{s}}_{k}})).$

Observe that

$\displaystyle\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2r}\mid\mathcal{\mathcal{H}}\setminus\mathcal{G}\right]$
$\displaystyle=\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2r}\mid\mathcal{\mathcal{H}}\setminus\mathcal{G}\right]=\left(\frac{1}{gkb}\right)^{2r}\mathbb{E}\left[h(D_{B},D_{C},D_{\tilde{s}_{C}})^{2r}\right]\leavevmode\nobreak\
.$ (B.15)

On the other hand, we can decompose

$\displaystyle\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2}\mid\mathcal{G}\right]$
$\displaystyle=\left(\frac{1}{gkb}\right)^{2r}\mathbb{E}\left[\left(h(D_{B},D_{C},D_{\hat{\mathsf{s}}_{C}})+h(D_{C},D_{B},D_{\hat{\mathsf{s}}_{B}})\right)^{2r}\right]$
$\displaystyle=\left(\frac{1}{gkb}\right)^{2r}\mathbb{E}\left[\left(h(D_{B},D_{C},D_{\hat{\mathsf{s}}_{C}})-h(D_{B},D_{B},D_{\hat{\mathsf{s}}_{B}})\right)^{2r}\right]\leavevmode\nobreak\
.$ (B.16)

Consequently, by (B.14), (B.15), and (B.16), it suffices to express suitable
bounds for the expectations

$\displaystyle\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]\quad\text{and}$
$\displaystyle\mathbb{E}\Bigg{[}\bigg{(}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)$
(B.17)
$\displaystyle\quad\quad\quad-\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{B}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{B}}))\right)\bigg{)}^{2r}\Bigg{]}$

respectively. To this end, recall that $\tilde{D}_{i}$ are independent copies
of $D_{i}$ for each $i$. Observe that

$\displaystyle\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]$
$\displaystyle=\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))+\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]$
$\displaystyle=\sum_{q=0}^{2r}{2r\choose
q}\mathbb{E}\bigg{[}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r-q}$
$\displaystyle\quad\quad\quad\quad\quad\quad\left(\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)^{q}\bigg{]}$
$\displaystyle\leq
2^{2r}\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]$
(B.18)

where the inequality follows from the fact that $B$ and $C$ are exchangeable
and the Hölder inequality. Similarly, we have that

$\displaystyle\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r-q}\right]$
$\displaystyle=\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))+\psi(D_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]$
$\displaystyle=\sum_{q=0}^{2r}{2r\choose
q}\mathbb{E}\bigg{[}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r-q}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\left(\psi(D_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(\tilde{D}_{B},\hat{\eta}(\tilde{D}_{C},D_{\hat{\mathsf{s}}_{C}}))\right)^{q}\bigg{]}$
$\displaystyle\leq\sum_{q=0}^{2r}{2r\choose q}\left(\sigma_{\mathsf{va\ell
id}}^{(2r)}\right)^{\frac{2r-q}{2r}}\left(\sigma_{\mathsf{train}}^{(2r,1)}\right)^{\frac{q}{2r}}$
$\displaystyle\leq 2^{2r}\sigma_{\mathsf{max}}^{(2r)},$ (B.19)

where the last inequality follows by the definitions of
$\sigma_{\mathsf{va\ell id}}^{(2r)}$ and $\sigma_{\mathsf{train}}^{(2r,1)}$.
Thus, we have that

$\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)^{2r}\right]\leq
2^{4r}\sigma_{\mathsf{max}}^{(2r)}$ (B.20)

by (B.18) and (B.19).

Next, we consider the double difference term (B.17). In this case, we have
that

$\displaystyle\mathbb{E}\Bigg{[}\bigg{(}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))\right)$
$\displaystyle\quad\quad\quad-\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{B}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{B}}))\right)\bigg{)}^{2r}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\bigg{(}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{B}}))\right)$
$\displaystyle\quad\quad\quad-\left(\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{B}}))\right)\bigg{)}^{2r}\Bigg{]}$
$\displaystyle=\sum_{q=0}^{2r}{2r\choose
q}\mathbb{E}\Bigg{[}\bigg{(}\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{B}}))\right)$
$\displaystyle\quad\quad\quad\quad\quad\quad\cdot\left(\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{C},\hat{\eta}(D_{B},D_{\hat{\mathsf{s}}_{B}}))\right)\bigg{)}^{2r}\Bigg{]}$
$\displaystyle\leq
2^{2r}\mathbb{E}\left[\left(\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{C}}))-\psi(D_{B},\hat{\eta}(D_{C},D_{\hat{\mathsf{s}}_{B}}))\right)^{2r}\right]=2^{2r}\sigma_{\mathsf{train}}^{(2r,b-1)}$
(B.21)

where the final inequality follows from the fact that $B$ and $C$ are
exchangeable and the Hölder inequality. Putting the pieces together, we have
that

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[a\left(Z_{m}\right)-a\left(Z_{m}^{\prime}\right)\mid
Z,Z^{\prime}\right]^{2r}\mid\bm{\pi}\right]$ $\displaystyle\leq
2^{4r}\left(1-\frac{2}{gn^{2}}\right)^{2mr}\left(\frac{2n-kb-b}{gn^{2}}\right)^{2r}\left(\left(\frac{n-kb}{n-b}\right)2^{2r}\sigma_{\mathsf{max}}^{(2r)}+\left(\frac{kb-b}{n-b}\right)\sigma_{\mathsf{train}}^{(2r,b-1)}\right)$

as required.

###  B.6. Proof of Lemma 5.5

Throughout, we us the short hand $\hat{v}_{g,k}\left(Z\right)$ to denote
$\hat{v}(\mathsf{R}_{g,k},D).$ We begin by decomposing the estimator
$\hat{v}_{g,k}\left(Z\right)$ into two parts that will each be easier to
handle when considered in isolation. To this end, define the statistics

$\displaystyle\tilde{v}_{g,k}\left(Z\right)$
$\displaystyle=\frac{1}{g^{2}k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},Y)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-\overline{a}\left(D\right)\right)\quad\text{and}$
$\displaystyle\check{v}_{g,k}\left(Z\right)$
$\displaystyle=\left(a\left(Z\right)-\overline{a}\left(D\right)\right)^{2}.$

Observe that both $\tilde{v}_{g,k}\left(Z\right)$ and
$\check{v}_{g,k}\left(Z\right)$ are unbiased for $v\left(Z\right)$. Moreover,
we can write

$\displaystyle\hat{v}_{g,k}\left(Z\right)$
$\displaystyle=\frac{1}{g\left(g-1\right)k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-a\left(Z\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-a\left(Z\right)\right)$
$\displaystyle=\frac{1}{g\left(g-1\right)k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-a\left(Z\right)\right)$
$\displaystyle\quad+\frac{1}{g\left(g-1\right)k}\sum_{\ell=1}^{g}\sum_{i=1}^{g}\left(\overline{a}\left(D\right)-a\left(Z\right)\right)\left(T(\mathsf{s}_{\ell,i},D)-a\left(Z\right)\right)$
$\displaystyle=\frac{1}{g\left(g-1\right)k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-a\left(Z\right)\right)$
$\displaystyle=\frac{g}{g-1}\tilde{v}\left(Z\right)+\frac{1}{g\left(g-1\right)k}\sum_{\ell=1}^{g}\sum_{i=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(\overline{a}\left(D\right)-a\left(Z\right)\right)$
$\displaystyle=\frac{g}{g-1}\tilde{v}_{g,k}\left(Z\right)-\frac{1}{g-1}\check{v}_{g,k}\left(Z\right).$
(B.22)

Hence, it will suffice to characterize the exponential rates of conditional
concentration for the statistics $\tilde{v}_{g,k}\left(Z\right)$ and
$\check{v}_{g,k}\left(Z\right)$. These are established through the application
of the following Lemma, which follows from an argument very similar to the
proof of Theorem 3.1.

###### Lemma B.4.

Suppose that Assumptions 3.1 and 3.2 hold and that the data $D$ are
independently and identically distributed. If the eighth-order split-stability
$\zeta^{(8)}$ is finite, then:

(i) The conditional concentration inequality

$\displaystyle\log\frac{1}{2}P\left\\{|\tilde{v}\left(Z\right)-v\left(D\right)|\geq
t\mid D\right\\}\lesssim-\frac{\delta}{(2-\varphi
k-\varphi)^{4}}\frac{g^{3}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}\leavevmode\nobreak\
,$ (B.23)

holds for all $t>0$ with probability greater than $1-\delta$.

(ii) The conditional concentration inequality

$\displaystyle\log\frac{1}{2}P\left\\{|\check{v}\left(Z\right)-v\left(D\right)|\geq
t\mid D\right\\}\lesssim-\frac{\delta}{(2-\varphi
k-\varphi)^{4}}\frac{g^{2}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}\leavevmode\nobreak\
,$ (B.24)

holds for all $t>0$ with probability greater than $1-\delta$.

Putting the pieces together, by (B.22), we have that

$\displaystyle
P\left\\{|\hat{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)|\leq t\mid
D\right\\}$
$\displaystyle=P\left\\{|\frac{g}{g-1}\left(\tilde{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)\right)-\frac{1}{g-1}\left(\check{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)\right)|\leq
t\mid D\right\\}$ $\displaystyle\geq
P\left\\{\frac{g}{g-1}|\tilde{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)|+\frac{1}{g-1}|\check{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)|\leq
t\mid D\right\\}$ $\displaystyle\geq
P\left\\{\frac{g}{g-1}|\tilde{v}_{g,k}\left(Z\right)-v\left(D\right)|\leq\frac{\sqrt{g}}{1+\sqrt{g}}t,\frac{1}{g-1}|\check{v}\left(Z\right)-v\left(D\right)|\leq\frac{1}{1+\sqrt{g}}t\mid
D\right\\}$ $\displaystyle\geq
P\left\\{|\tilde{v}_{g,k}\left(Z\right)-v\left(D\right)|\leq\frac{1}{\sqrt{g}}\frac{g-1}{1+\sqrt{g}}t\mid
D\right\\}+P\left\\{|\check{v}_{g,k}\left(Z\right)-v\left(D\right)|\leq\frac{g-1}{1+\sqrt{g}}t\mid
D\right\\}-1$ $\displaystyle\geq 1-4\exp\left(-\frac{\delta}{C(2-\varphi
k-\varphi)^{4}}\frac{g^{3}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}\right)$

with probability greater than $1-\delta$ for some universal constant $C$,
where the last inequality follows by Lemma B.4 and the facts that
$4g\geq\left(1+\sqrt{g}\right)^{2}$ for all $g\geq 1$ and
$\left(1/4\right)g^{2}\leq\left(g-1\right)^{2}$ for all $g\geq 2$.

###  B.7. Proof of Lemma 5.6

Define the event

$\mathcal{W}_{\lambda}\left(D\right)=\mathcal{U}_{k,\lambda}\left(D\right)\cap\mathcal{Q}_{k,\lambda}(D),$

the quantity

$W\left(D\right)=\left(U(\mathsf{R}_{\hat{g},k},D)-U(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D\right)+\left(Q(\mathsf{R}_{\hat{g},k},D)-Q(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D)\right).$

By the decomposition (B.6), we have that

$\displaystyle\bigg{|}P\left\\{a(\mathsf{R}_{\hat{g},k},D)-a(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D)\leq\xi\mid
D\right\\}-\left(1-\beta/2\right)\bigg{|}$
$\displaystyle=\bigg{|}P\left\\{\frac{a(\mathsf{R}_{\hat{g},k},D)-a(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D)}{\sqrt{2v_{g^{\star},k}\left(D\right)}}\leq\frac{\xi}{\sqrt{2v_{g^{\star},k}\left(D\right)}}\mid
D\right\\}-\left(1-\beta/2\right)\bigg{|}$
$\displaystyle=\bigg{|}P\left\\{\frac{a(\mathsf{R}_{g^{\star},k},D)-a(\mathsf{R}_{g^{\star},k}^{\prime},D)}{\sqrt{2v_{g^{\star},k}\left(D\right)}}\leq\frac{\xi}{\sqrt{2v_{g^{\star},k}\left(D\right)}}-\frac{W\left(D\right)}{\sqrt{2v_{g^{\star},k}\left(D\right)}}\mid
D\right\\}-\left(1-\beta/2\right)\bigg{|}$
$\displaystyle\leq\sup_{q\in\left[-2\lambda,2\lambda\right]}\bigg{|}P\left\\{\frac{a(\mathsf{R}_{g^{\star},k},D)-a(\mathsf{R}_{g^{\star},k}^{\prime},D)}{\sqrt{2v_{g^{\star},k}\left(D\right)}}\leq
z_{1-\beta/2}+q\right\\}-\left(1-\beta/2\right)\bigg{|}+\left(1-P\left\\{\mathcal{W}_{\lambda}\left(D\right)\mid
D\right\\}\right)$ $\displaystyle\leq
d_{K}\left(\frac{a(\mathsf{R}_{g^{\star},k},D)-a(\mathsf{R}_{g^{\star},k}^{\prime},D)}{\sqrt{2v_{g^{\star},k}\left(D\right)}},W\mid
D\right)+2\lambda+\left(1-P\left\\{\mathcal{W}_{\lambda}\left(D\right)\mid
D\right\\}\right),$

as required.

###  B.8. Proof of Lemma 5.7, Part (i)

Observe that we can write

$a(\mathsf{R}_{g^{\star},k},D)-a(\mathsf{R}_{g^{\star},k}^{\prime},D)=\frac{1}{g^{\star}}\sum_{\ell=1}^{g}\left(\overline{a}(\mathsf{r}_{\ell},D)-\overline{a}(\mathsf{r}_{\ell}^{\prime},D)\right),$

where $\overline{a}\left(\cdot,D\right)$ is defined in (5.14). We have that

$\displaystyle\mathbb{E}\left[|\overline{a}(\mathsf{r}_{\ell},D)-\overline{a}(\mathsf{r}_{\ell}^{\prime},D)|^{3}\right]$
$\displaystyle\leq\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}_{\ell},D)-\overline{a}(\mathsf{r}_{\ell}^{\prime},D)\right)^{4}\right]\right)^{3/4}$
(Hölder) $\displaystyle\leq
2^{6}\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}_{\ell},D)\right)^{4}\right]\right)^{3/4}$
$\displaystyle\leq 2^{6}3^{2}(2-\varphi
k-\varphi)^{3}(\Gamma^{(2)}_{k,\varphi,b})^{3/4}\leavevmode\nobreak\ ,$

where the second inequality follows from Hölder’s inequality, the binomial
theorem, and the fact that $\mathsf{r}_{\ell}$ and
$\mathsf{r}_{\ell}^{\prime}$ are exchangeable. The final inequality follows
from Theorem 3.2. Consequently, we find that

$\displaystyle\frac{\mathbb{E}\left[|\overline{a}(\mathsf{r}_{\ell},D)-\overline{a}(\mathsf{r}_{\ell}^{\prime},D)|^{3}\mid
D\right]}{\left(g^{\star}\right)^{1/2}\left(2v_{1,k}\left(D\right)\right)^{3/2}}$
$\displaystyle\lesssim\frac{(2-\varphi
k-\varphi)^{3}(\Gamma^{(2)}_{k,\varphi,b})^{3/4}}{\delta\left(g^{\star}\right)^{1/2}\left(v_{1,k}\left(D\right)\right)^{3/2}}$
(Markov) $\displaystyle\lesssim\frac{\xi}{z_{1-\beta/2}}\frac{(2-\varphi
k-\varphi)^{3}(\Gamma^{(2)}_{k,\varphi,b})^{3/4}}{\delta\left(v_{1,k}\left(D\right)\right)^{2}}\leavevmode\nobreak\
,$

holds with probability $1-\delta$. The Lemma then follows by the standard
Berry-Esseen inequality.

###  B.9. Proof of Lemma 5.7, Part (ii)

Our bound is based on the following two conditional concentration
inequalities. Both arguments are based on a Chernoff-type maximal inequality,
due to Steiger, (1970).

###### Lemma B.5.

Suppose that Assumptions 3.1 and 3.2 hold, that the data $D$ are independent
and identically distributed, and that the eighth-order split $\zeta^{8}$
stability is finite.

(i) For all $t>0$ and $c>0$, the condition concentration inequality

$\displaystyle\log\frac{1}{2}P\left\\{|U(\mathsf{R}_{\hat{g},k},D)|\geq
t\sqrt{v_{g^{\star},k}\left(D\right)},|\hat{g}/g^{\star}-1|\leq c\mid
D\right\\}$ $\displaystyle\leq-\frac{\delta v_{1,k(D)}}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{t^{2}}{c}\ $ (B.25)

holds with probability greater than $1-\delta$ as $D$ varies.

(ii) If $g^{\star}c\geq 2$ and $1/2>c>0$, then the conditional concentration
inequality

$\displaystyle\log\frac{1}{8}P\left\\{|\hat{g}-g^{\star}|>cg^{\star}\mid
D\right\\}\lesssim-\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}}{\Gamma_{k,\varphi,b}^{(2)}}\frac{c^{2}}{\xi^{2}}$
(B.26)

holds with probability greater than $1-\delta$ as $D$ varies.

Observe that

$\displaystyle
P\left\\{|U(\mathsf{R}_{\hat{g},k},D)-U(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)}\right\\}$
$\displaystyle\lesssim
P\left\\{|U(\mathsf{R}_{\hat{g},k},D)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)}\right\\}$
$\displaystyle\leq
P\left\\{|U(\mathsf{R}_{\hat{g},k},D)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)},|\hat{g}/g^{\star}-1|\leq
c\mid D\right\\}+P\left\\{|\hat{g}/g^{\star}-1|\geq c\mid D\right\\}$
$\displaystyle\lesssim\exp\left(-\frac{\delta v_{1,k(D)}}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{\lambda^{2}}{c}\right)+\exp\left(-C\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}}{\Gamma_{k,\varphi,b}^{(2)}}\frac{c^{2}}{\xi^{2}}\right)$
(B.27)

for some universal constant $C$. Hence, it remains to choose $c$ and $\lambda$
such that the quantity (B.27) is less than
$\rho_{k,\varphi,b}\left(\xi,\beta\mid D\right)$. First, we choose $c$ such
that

$\displaystyle\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}}{\Gamma_{k,\varphi,b}^{(2)}}\frac{c^{2}}{\xi^{2}}$
$\displaystyle\lesssim\log\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)$

Choosing $c$ by

$c=\xi\left(\frac{\left(2-\varphi
k-\varphi\right)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}{z_{1-\beta/2}\delta^{1/2}(v_{1,k}(D))^{3/2}}\right)\log^{1/2}\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)$ (B.28)

suffices. Next, we choose $\lambda$ such that

$\frac{\delta v_{1,k(D)}}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{\lambda^{2}}{c}\lesssim\log\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right).$

We can rewrite this condition by plugging in our choice of $c$ through

$\displaystyle\frac{\lambda^{2}}{\xi}\frac{z_{1-\beta/2}\delta^{3/2}(v_{1,k}(D))^{5/2}}{\left(2-\varphi
k-\varphi\right)^{4}\Gamma^{(1)}_{k,\varphi,b}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}\lesssim\log^{3/2}\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)$

Choosing $\lambda$ by

$\displaystyle\lambda$
$\displaystyle=\left(\frac{\xi}{z_{1-\beta/2}}\frac{(2-\varphi
k-\varphi)^{4}\Gamma^{(1)}_{k,\varphi,b}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}{\delta^{3/2}(v_{1,k}\left(D\right))^{5/2}}\right)^{1/2}\tilde{\lambda}_{k,\varphi,b}^{U}\left(D\right),\quad\text{where}$
$\displaystyle\tilde{\lambda}_{k,\varphi,b}^{U}\left(D\right)$
$\displaystyle=\log^{3/4}\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)$

will then suffice, as required.

###  B.10. Proof of Lemma 5.7, Part(iii)

Observe that

$\displaystyle
P\left\\{|\left(1-\frac{\hat{g}}{g^{\star}}\right)\left(a(\mathsf{R}_{\hat{g},k},D)-\overline{a}\left(D\right)\right)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)},|\begin{gathered}g^{\star}-\hat{g}|\leq
cg^{\star}\end{gathered}\mid D\right\\}$ (B.30)
$\displaystyle=P\left\\{|\left(a(\mathsf{R}_{\hat{g},k},D)-\overline{a}\left(D\right)\right)|\geq\frac{\lambda}{c}\sqrt{2v_{g^{\star},k}\left(D\right)},|\begin{gathered}g^{\star}-\hat{g}|\leq
cg^{\star}\end{gathered}\mid D\right\\}$ (B.32) $\displaystyle\leq
P\left\\{\max_{|g^{\star}-g|\leq
cg^{\star}}|\left(a(\mathsf{R}_{g,k},D)-\overline{a}\left(D\right)\right)|\geq\frac{\lambda}{c}\sqrt{2v_{g^{\star},k}\left(D\right)}\mid
D\right\\}$ $\displaystyle\leq P\left\\{\max_{|g^{\star}-g|\leq
cg^{\star}}|\left(a(\mathsf{R}_{g,k},D)-\overline{a}\left(D\right)\right)|\geq\frac{\lambda}{c}\left(\frac{\xi}{z_{1-\beta/2}}\right)\mid
D\right\\}$ $\displaystyle\leq\sum_{|g^{\star}-g|\leq
cg^{\star}}P\left\\{|\left(a(\mathsf{R}_{g,k},D)-\overline{a}\left(D\right)\right)|\geq\frac{\lambda}{c}\left(\frac{\xi}{z_{1-\beta/2}}\right)\right\\}\leavevmode\nobreak\
.$ (B.33)

By Theorem 3.1, we have that

$\displaystyle
P\left\\{|\left(a(\mathsf{R}_{g,k},D)-\overline{a}\left(D\right)\right)|\geq\frac{\lambda}{c}\left(\frac{\xi}{z_{1-\beta/2}}\right)\right\\}$
$\displaystyle\leq 2\exp\left(-\frac{g\delta}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma_{k,\varphi,b}(1)}\frac{\lambda^{2}}{c^{2}}\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\right)$

and so is (B.33) bounded from above by

$\displaystyle 4cg^{\star}\exp\left(-\frac{g^{\star}(1-c)\delta}{4(2-\varphi
k-\varphi)^{2}\Gamma_{k,\varphi,b}(1)}\frac{\lambda^{2}}{c^{2}}\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\right)$
$\displaystyle\lesssim
v_{1,k}\left(D\right)c\left(\frac{z_{1-\beta/2}}{\xi}\right)^{2}\exp\left(-\frac{\delta
v_{1,k}(D)}{2^{5}(2-\varphi
k-\varphi)^{2}\Gamma_{k,\varphi,b}(1)}\frac{\lambda^{2}}{c^{2}}\right)$

if $1-c\geq 1/2$ by the definition of $g^{\star}$. Thus, we have that

$\displaystyle
P\left\\{|Q(\mathsf{R}_{\hat{g},k},D)-Q(\mathsf{R}_{\hat{g}^{\prime},k}^{\prime},D)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)}\mid
D\right\\}$ $\displaystyle\lesssim
P\left\\{|\left(1-\frac{\hat{g}}{g^{\star}}\right)\left(a(\mathsf{R}_{\hat{g},k},D)-\overline{a}\left(D\right)\right)|\geq\lambda\sqrt{2v_{g^{\star},k}\left(D\right)},|\begin{gathered}g^{\star}-\hat{g}|\leq
cg^{\star}\end{gathered}\mid
D\right\\}+P\left\\{|\begin{gathered}g^{\star}-\hat{g}|\geq
cg^{\star}\end{gathered}\mid D\right\\}$ (B.36) $\displaystyle\lesssim
v_{1,k}\left(D\right)c\left(\frac{z_{1-\beta/2}}{\xi}\right)^{2}\exp\left(-\frac{\delta
v_{1,k}(D)}{2^{5}(2-\varphi
k-\varphi)^{2}\Gamma_{k,\varphi,b}^{(1)}}\frac{\lambda^{2}}{c^{2}}\right)$
(B.37)
$\displaystyle\quad+\exp\left(-\frac{1}{C}\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}}{\Gamma_{k,\varphi,b}^{(2)}}\frac{c^{2}}{\xi^{2}}\right)$
(B.38)

for some universal constant $C$ by Lemma B.5, Part (ii). If $c$ is chosen to
satisfy (B.28), the term (B.38) will be bounded above by
$\rho_{\varphi,k}\left(\xi,\beta\mid D\right).$ By plugging this value of $c$
and $\lambda=\lambda_{\varphi,k}\left(\xi,\beta\mid D\right)$ into (B.37), we
obtain the sub-polynomial term

$\displaystyle\tilde{\rho}_{k,\varphi,b}(\xi,\beta\mid D)$
$\displaystyle=\left(\frac{z_{1-\beta/2}^{2}}{\xi}\right)\left(\frac{\left(2-\varphi
k-\varphi\right)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}{z_{1-\beta/2}\delta^{1/2}(v_{1,k}(D))^{1/2}}\right)\log^{1/2}\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)$
$\displaystyle\exp\left(-\frac{1}{\xi}\frac{\delta^{1/2}(v_{1,k}(D))^{3/2}}{(2-\varphi
k-\varphi)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}\tilde{\lambda}_{k,\varphi,b}^{U}\left(D\right)\log\left(\rho_{k,\varphi,b}\left(\xi,\beta\mid
D\right)^{-1}\right)\right)$ (B.39)

as required.

##  Appendix C Proofs for Auxiliary Results

###  C.1. Proof of Lemma B.1

Let
$T_{i}\left(\pi_{m,\ell}\right)=T\left(\mathsf{s}_{i}\left(\pi_{\ell,m}\right),D\right)$
and define $T_{i}(\pi_{m,\ell}^{\prime})$ analogously. Define

$R_{m}\left(\ell\right)=\left\\{i\in\left[n\right]:\pi_{m,\ell}\left(i\right)\neq\pi_{m,\ell}^{\prime}\left(i\right)\right\\}$

and let $\overline{R}_{m}\left(\ell\right)=|R_{m}\left(\ell\right)|$ denote
the number of shared indices in the permutations in $\pi_{m,\ell}$ and
$\pi_{m,\ell}^{\prime}$. Observe that

$\frac{1}{k}\sum_{i=1}^{k}\left(T_{i}\left(\pi_{m,\ell}\right)-T_{i}\left(\pi_{m,\ell}^{\prime}\right)\right)=0$
(C.1)

almost surely for all $m^{\prime}\geq m$ if and only if
$\overline{R}_{m}\left(\ell\right)=n$. Let $N\left(\ell\right)$ denote the
values of the smallest index $m$ with $\overline{R}_{m}\left(\ell\right)=n$.
Observe that

$\displaystyle\sum_{m=0}^{\infty}\bigg{|}\mathbb{E}\left[a(\mathsf{R}_{g,k}(\bm{\pi}_{m}),D)-a(\mathsf{R}_{g,k}(\bm{\pi}_{m}^{\prime}),D)\mid\bm{\pi}_{0}=\bm{\psi},\bm{\pi}_{0}^{\prime}=\bm{\psi}^{\prime},D\right]\bigg{|}$
(C.2)
$\displaystyle\leq\sum_{m=0}^{\infty}\frac{1}{g}\frac{1}{k}\sum_{\ell=1}^{g}\sum_{i=1}^{k}\mathbb{E}\left[\bigg{|}\left(T_{i}\left(\pi_{m,\ell}\right)-T_{i}\left(\pi_{m,\ell}^{\prime}\right)\right)\bigg{|}\mid\bm{\pi}_{0}=\bm{\psi},\bm{\pi}_{0}^{\prime}=\bm{\psi}^{\prime},D\right]$
$\displaystyle\leq\frac{1}{g}\frac{1}{k}\sum_{\ell=1}^{g}\sum_{i=1}^{k}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\big{|}T\left(\mathsf{s},D\right)-T\left(\mathsf{s}^{\prime},D\right)\big{|}\mathbb{E}\left[N\left(\ell\right)\right]$

Hence, it suffices to bound the quantity
$\mathbb{E}\left[N\left(\ell\right)\right]$.

To that end, let $N_{r}\left(\ell\right)$ be the value of the smallest index
$m$ with $\overline{R}_{m}\left(\ell\right)\geq r$. We proceed analogously to
standard analysis of the coupon collector’s problem (see e.g., Section 2.2 of
Levin and Peres,, 2017). We can evaluate

$\displaystyle P\left\\{\overline{R}_{m}\left(\ell\right)\geq
r+1\mid\overline{R}_{m-1}\left(\ell\right)=r\right\\}$
$\displaystyle=\frac{1}{g}P\left\\{\pi_{\ell}\left(I_{m}\right)\neq\pi_{\ell}^{\prime}\left(I_{m}\right),\pi_{\ell}^{-1}\left(J_{m}\right)\neq\pi_{\ell}^{\prime-1}\left(J_{m}\right)\right\\}=\frac{\left(n-r\right)^{2}}{gn^{2}}$

and

$\displaystyle
P\left\\{\overline{R}_{m}\left(\ell\right)<r\mid\overline{R}_{m-1}\left(\ell\right)=r\right\\}$
$\displaystyle=0,$

and thereby obtain the bound

$\displaystyle\mathbb{E}\left[N\left(\ell\right)\right]$
$\displaystyle=\sum_{r=1}^{n}\mathbb{E}\left[N_{r}\left(\ell\right)-N_{r-1}\left(\ell\right)\right]\leq\sum_{r=1}^{n}\frac{gn^{2}}{\left(n-r+1\right)^{2}}=gn^{2}\sum_{r=1}^{n}\frac{1}{r^{2}}\leq
2gn^{2}.$ (C.3)

Hence, we find that (C.2) is upper bounded by

$2gn^{2}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}T\left(\mathsf{s},D\right)-T\left(\mathsf{s}^{\prime},D\right),$

as required.

###  C.2. Proof of Lemma B.2

Observe that

$\displaystyle\frac{\text{d}}{\text{d}t}e^{tx}e^{(1-t)y}$
$\displaystyle=\left(x-y\right)e^{tx}e^{(1-t)y}.$

Thus, we find that

$\displaystyle c\left(e^{x}-e^{y}\right)$
$\displaystyle=c\int_{0}^{1}\left(\frac{\text{d}}{\text{d}t}e^{tx}e^{\left(1-t\right)y}\right)\text{dt}$
(Fundamental Theorem of Calculus)
$\displaystyle=c\left(x-y\right)\int_{0}^{1}e^{tx}e^{(1-t)y}\text{dt}$
$\displaystyle\leq
c\left(x-y\right)\int_{0}^{1}\left(te^{x}+\left(1-t\right)e^{y}\right)$
(Convexity)
$\displaystyle=\frac{c}{2}\left(x-y\right)\left(e^{x}+e^{y}\right)$
$\displaystyle=\frac{1}{2}\left(\left(s^{-1}c^{2}\left(e^{x}+e^{y}\right)\right)\left(s\left(x-y\right)^{2}\left(e^{x}+e^{y}\right)\right)\right)^{1/2}$
$\displaystyle\leq\frac{1}{4}\left(\left(s^{-1}c^{2}\right)+s\left(x-y\right)^{2}\right)\left(e^{x}+e^{y}\right),$
(AM-GM)

as required.

###  C.3. Proof of Lemma B.3

To begin, consider any collection of real numbers $x_{1},\ldots,x_{2^{c}}$,
for some positive integer $c$. For any integer $s>0$, we have

$\displaystyle\left(x_{1}\cdots x_{2^{c}}\right)^{2s}$
$\displaystyle\leq\frac{1}{4}\left(\left(x_{i_{1}}\cdots
x_{i_{2^{c-1}}}\right)^{2s}+\left(x_{i_{2^{c-1}+1}}\cdots
x_{2^{c}}\right)^{2s}\right)^{2}$ (Young’s Inequality)
$\displaystyle\leq\frac{1}{4}\left(\left(x_{i_{1}}\cdots
x_{i_{2^{c-1}}}\right)^{2(s+1)}+2\left(x_{1}\cdots
x_{2^{c}}\right)^{2s}+\left(x_{i_{2^{c-1}+1}}\cdots
x_{2^{c}}\right)^{2(s+1)}\right)$

and so

$\left(x_{1}\cdots x_{2^{c}}\right)^{2s}\leq\frac{1}{2}\left(x_{i_{1}}\cdots
x_{i_{2^{c-1}}}\right)^{2(s+1)}+\frac{1}{2}\left(x_{i_{2^{c-1}+1}}\cdots
x_{2^{c}}\right)^{2(s+1)}.$ (C.4)

Consequently, we have that

$x_{1}\cdots x_{2^{c}}\leq\frac{1}{2^{c}}\sum_{i=1}^{2^{c}}x_{i}^{2c}$ (C.5)

through $2^{r}$ applications of (C.4).

Now, to prove the Lemma, we may assume without loss that $h_{i}>0$ for all $i$
by continuity. Observe that

$\mathbb{E}\left[\left(\sum_{m=0}^{\infty}X_{m}\right)^{2^{c}}\right]=\sum_{i_{1}=0}^{\infty}\cdots\sum_{i_{2^{c}}=0}^{\infty}\mathbb{E}\left[X_{i_{1}}\cdots
X_{i_{2^{c}}}\right]$ (C.6)

by dominated convergence. By writing

$X_{1}\cdots X_{2^{c}}=\prod_{j=1}^{2^{c}}\left(\frac{\prod_{k\neq
j}h_{k}}{h_{j}^{2^{c-1}}}\right)^{1/2^{c}}X_{j}$

we find that

$\mathbb{E}\left[X_{1}\cdots
X_{2^{c}}\right]\leq\frac{1}{2^{c}}\sum_{j=1}^{2^{c}}\frac{\prod_{k\neq
j}h_{k}}{h_{j}^{2^{c-1}}}h_{j}^{2^{c}}=\prod_{j=1}^{2^{c}}h_{j}$

by (C.5). Hence, by (C.6), we have that

$\mathbb{E}\left[\left(\sum_{m=0}^{\infty}X_{m}\right)^{2^{c}}\right]\leq\sum_{i_{1}=0}^{\infty}\cdots\sum_{i_{2^{c}}=0}^{\infty}\prod_{j=1}^{2^{c}}h_{i_{j}}=\left(\sum_{m=0}^{\infty}h_{j}\right)^{2^{c}},$

as required.

###  C.4. Proof of Lemma B.4

We begin by constructing Stein representers
$\tilde{V}\left(Z,Z^{\prime}\right)$ and $\check{V}\left(Z,Z^{\prime}\right)$
for the statistic $\tilde{v}_{g,k}\left(Z\right)$ and
$\check{v}_{g,k}\left(Z\right)$, respectively. We will use the same
exchangeable pair $\left(Z,Z^{\prime}\right)_{m\geq 0}$ and Markov chain
$\left(Z_{m},Z_{m}^{\prime}\right)_{m\geq 1}$ defined in Section 5.1. The
subsequent result follows from an argument similar to Lemma 5.1, again based
on an idea expressed by Lemma 4.1 of Chatterjee, (2005).

###### Lemma C.1.

(i) Let $\bm{\psi}$ and $\psi^{\prime}$ be two sets, each containing $g$
elements of $\mathcal{P}_{n}$. The inequalities

$\displaystyle\sum_{m=0}^{\infty}\bigg{|}\mathbb{E}\left[\left(\tilde{v}_{g,k}\left(Z_{m}\right)-\tilde{v}_{g,k}\left(Z_{m}^{\prime}\right)\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]\bigg{|}$ $\displaystyle\leq
n^{2}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{2}\quad\text{and}$
$\displaystyle\sum_{m=0}^{\infty}\bigg{|}\mathbb{E}\left[\left(\check{v}_{g,k}\left(Z_{m}\right)-\check{v}_{g,k}\left(Z_{m}^{\prime}\right)\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]\bigg{|}$ $\displaystyle\leq
2gn^{2}\max_{\mathsf{s}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{2}$

hold almost surely.

(ii) The functions

$\displaystyle\tilde{V}\left(Z,Z^{\prime}\right)$
$\displaystyle=\sum_{m=0}^{\infty}\mathbb{E}\left[\left(\tilde{v}_{g,k}\left(Z_{m}\right)-\tilde{v}_{g,k}\left(Z_{m}^{\prime}\right)\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]\quad\text{and}$
$\displaystyle\check{V}\left(Z,Z^{\prime}\right)$
$\displaystyle=\sum_{m=0}^{\infty}\mathbb{E}\left[\left(\check{v}_{g,k}\left(Z_{m}\right)-\check{v}_{g,k}\left(Z_{m}^{\prime}\right)\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]$

are finite and satisfy the equalities

$\displaystyle\mathbb{E}\left[\tilde{V}\left(Z,Z^{\prime}\right)\mid Z\right]$
$\displaystyle=\tilde{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)\quad\text{and}$
$\displaystyle\mathbb{E}\left[\check{V}\left(Z,Z^{\prime}\right)\mid Z\right]$
$\displaystyle=\check{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)$

almost surely.

Next, we apply the concentration inequality stated in Theorem 5.2, due to
Chatterjee, (2005, 2007). That is, to establish part (i) of the Lemma, it will
suffice to characterize constants $s$ and $u$ that satisfy

$U_{\tilde{v}}\left(Z\right)\leq s^{-1}u\quad\text{and}\quad
U_{\tilde{V}}\left(Z\right)\leq su,$

with probability $1-\delta$, where

$U_{\tilde{v}}\left(Z\right)=\frac{1}{2}\mathbb{E}\left[\left(\tilde{v}\left(Z\right)-\tilde{v}\left(Z^{\prime}\right)\right)\mid
Z\right]\quad\text{and}\quad
U_{\tilde{V}}\left(Z\right)=\frac{1}{2}\mathbb{E}\left[\tilde{V}\left(Z,Z^{\prime}\right)^{2}\mid
Z\right].$

The same statement holds for part (ii) of the Lemma, for the objects
$U_{\check{v}}\left(Z\right)$ and $U_{\check{V}}\left(Z\right)$ defined
analogously.

We obtain such a characterization through the application of Lemma 5.3. To
this end, observe that, by Lemma C.1, part (i), the bound

$\left(\sum_{m=0}^{\infty}\mathbb{E}\left[\left(\tilde{v}_{g,k}\left(Z_{m}\right)-\tilde{v}_{g,k}\left(Z_{m}^{\prime}\right)\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]\right)^{2}\leq
n^{4}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{4}$
(C.7)

holds almost surely. The right hand side of (C.7) is square integrable, as the
eighth-order split-stability $\zeta^{(8)}$ is finite almost surely. An
analogous statement holds for the statistic $\check{v}_{g,k}\left(Z\right)$.
Thus, deterministic bounds of the form (5.10) can be obtained through the
application of the following Lemma.

###### Lemma C.2.

Suppose that Assumptions 3.1 and 3.2 hold and that the data $D$ are
independent and identically distributed. If the eighth-order split stability
$\zeta^{(8)}$ is finite, then

(i) The inequality

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\mid
Z,Z^{\prime}\right]^{2}\mid\bm{\pi}\right]\lesssim\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{4}}\right)\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
,$

holds almost surely for all integers $m\geq 0$, and

(ii) The inequality

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\mid
Z,Z^{\prime}\right]^{2}\mid\bm{\pi}\right]\lesssim\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{3}}\right)\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
,$

holds almost surely for all integers $m\geq 0$.

Thus, by Lemma 5.3, part (i), the inequalities

$\displaystyle U_{\tilde{V}}\left(Z\right)$
$\displaystyle\lesssim\frac{1}{\delta}\left(\frac{gn^{2}}{2}\right)^{2}\left(\frac{\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{4}}\right)\Gamma_{k,\varphi,b}^{(2)}$
$\displaystyle\lesssim\left(\frac{gn^{2}}{2}\right)\left(\frac{1}{\delta}\frac{(2-\varphi
k-\varphi)^{4}}{g^{3}}\right)\Gamma_{k,\varphi,b}^{(2)}$

and

$\displaystyle U_{\tilde{v}}\left(Z\right)$
$\displaystyle\lesssim\frac{1}{\delta}\left(\frac{\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{4}}\right)\Gamma_{k,\varphi,b}^{(2)}$
$\displaystyle\lesssim\left(\frac{2}{gn^{2}}\right)\left(\frac{1}{\delta}\frac{\left(2-\varphi
k-\varphi\right)^{4}}{g^{3}}\right)\Gamma_{k,\varphi,b}^{(2)}$

both hold with probability greater than $1-\delta$. Hence, we obtain the bound
(B.23) by applying Theorem 5.2 and choosing $s=gn^{2}/2$ and

$u=\frac{1}{\delta}\frac{\left(2-\varphi
k-\varphi\right)^{4}}{g^{3}}\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\ .$

Analogous inequalities for the objects $U_{\check{v}}\left(Z\right)$ and
$U_{\check{V}}\left(Z\right)$ hold by Lemma 5.3, part (ii), where in that case

$u=\frac{1}{\delta}\frac{\left(2-\varphi
k-\varphi\right)^{4}}{g^{2}}n^{4}\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
.$

which similarly implies the bound (B.24) by Theorem 5.2.

###  C.5. Proof of Lemma C.1

Reinstate the notation of the proof of Lemma B.1. We begin by noting that

$\displaystyle\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{2}$
$\displaystyle=\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-\overline{a}\left(D\right)\right)^{2}+\left(T(\mathsf{s}^{\prime},D)-\overline{a}\left(D\right)\right)^{2}$
$\displaystyle\quad\quad\quad\quad\quad+2\left(T(\mathsf{s},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}^{\prime},D)-\overline{a}\left(D\right)\right)$
$\displaystyle\geq
4\max_{\mathsf{s}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-\overline{a}\left(D\right)\right)^{2}.$

Observe that

$\displaystyle\sum_{i,i^{\prime}=1}^{k}\left(T_{i}\left(\pi_{m,\ell}\right)-\overline{a}\left(D\right)\right)\left(T_{i}\left(\pi_{m,\ell}\right)-\overline{a}\left(D\right)\right)-\sum_{i,i^{\prime}=1}^{k}\left(T_{i}\left(\pi_{m,\ell}^{\prime}\right)-\overline{a}\left(D\right)\right)\left(T_{i^{\prime}}\left(\pi_{m,\ell}^{\prime}\right)-\overline{a}\left(D\right)\right)=0$

for all for all $m^{\prime}\geq m$ if and only if
$\overline{R}_{m}\left(\ell\right)=n$. Thus, we have that

$\displaystyle\sum_{m=0}^{\infty}\bigg{|}\mathbb{E}\left[\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\mid
Z_{0}=\left(\mathsf{r}\left(\bm{\psi}\right),D\right),Z_{0}^{\prime}=\left(\mathsf{r}\left(\bm{\psi}^{\prime}\right),D\right)\right]\bigg{|}$
$\displaystyle\leq\sum_{m=0}^{\infty}\frac{1}{g^{2}k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\mathbb{E}\bigg{[}\bigg{|}\left(T_{i}\left(\pi_{m,\ell}\right)-\overline{a}\left(D\right)\right)\left(T_{i^{\prime}}\left(\pi_{m,\ell}\right)-\overline{a}\left(D\right)\right)$
$\displaystyle\quad\quad\quad\quad\quad-\left(T_{i}\left(\pi_{m,\ell}^{\prime}\right)-\overline{a}\left(D\right)\right)\left(T_{i^{\prime}}\left(\pi_{m,\ell}^{\prime}\right)-\overline{a}\left(D\right)\right)\bigg{|}\mid
Z_{0}=\left(\mathsf{r}\left(\bm{\psi}\right),D\right),Z_{0}^{\prime}=\left(\mathsf{r}\left(\bm{\psi}^{\prime}\right),D\right)\bigg{]}$
$\displaystyle\leq\frac{2}{g^{2}k^{2}}\sum_{\ell=1}^{g}\sum_{i,i^{\prime}=1}^{k}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\big{|}\left(T\left(\mathsf{s},D\right)-\overline{a}\left(D\right)\right)\left(T\left(\mathsf{s}^{\prime},D\right)-\overline{a}\left(D\right)\right)\big{|}\mathbb{E}\left[N\left(\ell\right)\right].$
$\displaystyle\leq\frac{2}{g}\max_{\mathsf{s}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-\overline{a}\left(D\right)\right)^{2}\mathbb{E}\left[N\left(\ell\right)\right].$
$\displaystyle\leq\frac{1}{2g}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{2}\mathbb{E}\left[N\left(\ell\right)\right].$

Similarly, we have that

$\displaystyle\sum_{m=0}^{\infty}\bigg{|}\mathbb{E}\left[\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\mid
Z_{0}=\left(\mathsf{r}\left(\bm{\psi}\right),D\right),Z_{0}^{\prime}=\left(\mathsf{r}\left(\bm{\psi}^{\prime}\right),D\right)\right]\bigg{|}$
$\displaystyle\leq\sum_{m=0}^{\infty}\frac{1}{g^{2}k^{2}}\sum_{\ell,\ell^{\prime}=1}^{g}\sum_{i,i^{\prime}=1}^{k}\mathbb{E}\bigg{[}\bigg{|}\left(T_{i}\left(\pi_{m,\ell}\right)-\overline{a}\left(D\right)\right)\left(T_{i^{\prime}}\left(\pi_{m,\ell^{\prime}}\right)-\overline{a}\left(D\right)\right)$
$\displaystyle\quad\quad\quad\quad\quad-\left(T_{i}\left(\pi_{m,\ell}^{\prime}\right)-\overline{a}\left(D\right)\right)\left(T_{i^{\prime}}\left(\pi_{m,\ell^{\prime}}^{\prime}\right)-\overline{a}\left(D\right)\right)\bigg{|}\mid
Z_{0}=\left(\mathsf{r}\left(\bm{\psi}\right),D\right),Z_{0}^{\prime}=\left(\mathsf{r}\left(\bm{\psi}^{\prime}\right),D\right)\bigg{]}$
$\displaystyle\leq\frac{2}{g^{2}k^{2}}\sum_{\ell,\ell^{\prime}=1}^{g}\sum_{i,i^{\prime}=1}^{k}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\big{|}\left(T\left(\mathsf{s},D\right)-\overline{a}\left(D\right)\right)\left(T\left(\mathsf{s}^{\prime},D\right)-\overline{a}\left(D\right)\right)\big{|}\mathbb{E}\left[\max\left\\{N\left(\ell\right),N\left(\ell^{\prime}\right)\right\\}\right]$
$\displaystyle\leq\frac{2}{g^{2}k^{2}}\sum_{\ell,\ell^{\prime}=1}^{g}\sum_{i,i^{\prime}=1}^{k}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\big{|}\left(T\left(\mathsf{s},D\right)-\overline{a}\left(D\right)\right)\left(T\left(\mathsf{s}^{\prime},D\right)-\overline{a}\left(D\right)\right)\big{|}\mathbb{E}\left[N\left(\ell\right)+N\left(\ell^{\prime}\right)\right]$
$\displaystyle\leq\frac{1}{2}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T(\mathsf{s},D)-T(\mathsf{s}^{\prime},D)\right)^{2}\big{|}\mathbb{E}\left[N\left(\ell\right)+N\left(\ell^{\prime}\right)\right]$

Thus, part (i) of the Lemma follows by the bound (C.3). Part (ii) of the Lemma
then follows by an argument analogous to the proof of Lemma 5.1.

###  C.6. Proof of Lemma C.2

We reinstate the notation introduced in the proof of Lemma 5.4 from Section
B.5. First, observe that

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\mid
Z,Z^{\prime}\right]^{2}\mid\bm{\pi}\right]$
$\displaystyle=\mathbb{E}\left[\left(P\left\\{\mathcal{H}_{m}\right\\}\mathbb{E}\left[\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\mid\mathcal{H}_{m},Z,Z^{\prime}\right]\right)^{2}\mid\bm{\pi}\right]$
$\displaystyle\leq\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{2kb\left(2n-bk-b\right)}{n^{2}}\right)^{2}\mathbb{E}\left[\left(\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]$
(C.8)

as before. Recall the notation

$\overline{a}(\mathsf{r}_{\ell},D)=\frac{1}{k}\sum_{i=1}^{k}(T(\mathsf{s}_{\ell,i},D)-\overline{a}(D))$

and observe that

$\displaystyle\mathbb{E}\left[\left(\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]$
$\displaystyle=\frac{1}{g^{4}}\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)^{2}-\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)^{2}\right)^{2}\mid\mathcal{H}_{m}\right]$
$\displaystyle=\frac{1}{g^{4}}\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)+\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{2}\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{2}\mid\mathcal{H}_{m}\right]$
$\displaystyle\leq\frac{1}{g^{4}}\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)+\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}$
(Cauchy-Schwarz)
$\displaystyle\quad\quad\cdot\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}$
$\displaystyle\leq\frac{2^{4}}{g^{4}}\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(D)\right)^{4}\right]\right)^{1/2}$
(Hölder)
$\displaystyle\quad\quad\cdot\left(\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}\leavevmode\nobreak\
.$ (C.9)

Observe that

$\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(D)\right)^{4}\right]\leq
3^{2}\left(2^{4}(2-\varphi
k-\varphi)^{2}\right)^{2}\Gamma_{k,\varphi,b}^{(2)}$

by Theorem 3.2, as Assumption 3.1 is maintained and the eighth-order sample-
split stability $\zeta^{(8)}$ is finite. In turn, we have that

$\mathbb{E}\left[\left(\overline{a}(\mathsf{r}(\pi_{m,L}),D)-\overline{a}(\mathsf{r}(\pi^{\prime}_{m,L}),D)\right)^{4}\mid\mathcal{H}_{m}\right]\leq\frac{4}{k^{4}b^{4}}\Gamma_{k,\varphi,b}^{(2)}$
(C.10)

by (B.14), (B.20), and (B.21). Hence, we have that

$\mathbb{E}\left[\left(\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]\leq\frac{3\cdot
2^{9}}{k^{2}b^{2}g^{4}}(2-\varphi
k-\varphi)^{2}\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\ .$ (C.11)

Combining (C.8), (C.10), (C.11), we find that

$\mathbb{E}\left[\mathbb{E}\left[\tilde{v}_{g,k}(Z_{m})-\tilde{v}_{g,k}(Z_{m}^{\prime})\mid
Z,Z^{\prime}\right]^{2}\mid\bm{\pi}\right]\leq\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{\left(3\cdot
2^{11}\right)\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{4}}\right)\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
,$

which completes the proof of the first part of the Lemma.

Second, following the same argument, we again have that

$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\mid
Z,Z^{\prime}\right]^{2}\mid\bm{\pi}\right]$
$\displaystyle\leq\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{2kb\left(2n-bk-b\right)}{n^{2}}\right)^{2}\mathbb{E}\left[\left(\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]$
(C.12)

In this case, we can compute

$\displaystyle\mathbb{E}\left[\left(\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]$
$\displaystyle=\mathbb{E}\left[\left(\left(a(Z_{m})-\overline{a}(D)\right)^{2}-\left(a(Z^{\prime}_{m})-\overline{a}(D)\right)^{2}\right)^{2}\mid\mathcal{H}_{m}\right]$
$\displaystyle=\mathbb{E}\left[\left(a(Z_{m})-\overline{a}(D)+a(Z^{\prime}_{m})-\overline{a}(D)\right)^{2}\left(a(Z_{m})-a(Z^{\prime}_{m})\right)^{2}\mid\mathcal{H}_{m}\right]$
$\displaystyle\leq\left(\mathbb{E}\left[\left(a(Z_{m})-\overline{a}(D)+a(Z^{\prime}_{m})-\overline{a}(D)\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}$
(Cauchy-Schwarz)
$\displaystyle\quad\quad\cdot\left(\mathbb{E}\left[\left(a(Z_{m})-a(Z^{\prime}_{m})\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}$
$\displaystyle\leq
2^{4}\left(\mathbb{E}\left[\left(a(Z_{m})-\overline{a}(D)\right)^{4}\right]\right)^{1/2}\left(\mathbb{E}\left[\left(a(Z_{m})-a(Z^{\prime}_{m})\right)^{4}\mid\mathcal{H}_{m}\right]\right)^{1/2}\leavevmode\nobreak\
,$ (C.13)

where the last inequality follows from Hölder’s inequality. Again we have that

$\mathbb{E}\left[\left(a(Z_{m})-a(Z^{\prime}_{m})\right)^{4}\right]\leq
3^{2}\left(\frac{2^{4}\varphi^{2}(2-\varphi
k-\varphi)^{2}}{g}\right)^{2}\Gamma_{k,\varphi,b}^{(2)}$ (C.14)

by Theorem 3.2, as Assumption 3.1 is maintained and the eighth-order sample-
split stability $\zeta^{(8)}$ is finite. Similarly. we have that

$\mathbb{E}\left[\left(a(Z_{m})-\overline{a}(D)\right)^{4}\mid\mathcal{H}_{m}\right]\leq\frac{4}{g^{4}k^{4}b^{4}}\Gamma_{k,\varphi,b}^{(2)}$
(C.15)

by (B.14), (B.20), and (B.21). Combining (C.12), (C.14), (C.15), we find that

$\mathbb{E}\left[\left(\check{v}_{g,k}(Z_{m})-\check{v}_{g,k}(Z_{m}^{\prime})\right)^{2}\mid\mathcal{H}_{m},\bm{\pi}\right]\leq\left(1-\frac{2}{gn^{2}}\right)^{2m}\left(\frac{\left(3\cdot
2^{9}\right)\varphi^{4}\left(2-\varphi
k-\varphi\right)^{4}}{n^{2}g^{3}}\right)\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
,$

which completes the proof of the second part of the Lemma.

###  C.7. Proof of Lemma B.5, Part (i)

Observe that

$\displaystyle P\left\\{|U(\mathsf{R}_{\hat{g},k},D)|\geq
t\sqrt{v_{g^{\star},k}\left(D\right)},|\hat{g}-g^{\star}|\leq cg^{\star}\mid
D\right\\}$
$\displaystyle=P\left\\{\sum_{i=1}^{g}\overline{a}\left(\mathsf{r}_{i,k},D\right)-\sum_{i=1}^{g^{\star}}\overline{a}\left(\mathsf{r}_{i,k},D\right)\geq
tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)},|\hat{g}-g^{\star}|\leq
cg^{\star}\mid D\right\\}$ $\displaystyle\leq
P\left\\{\max_{g^{\star}(1-c)\leq g\leq
g^{\star}}|\sum_{i=1}^{g}\overline{a}\left(\mathsf{r}_{i,k},D\right)-\sum_{i=1}^{g^{\star}}\overline{a}\left(\mathsf{r}_{i,k},D\right)|\geq
tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)}\mid D\right\\}$
$\displaystyle+P\left\\{\max_{g^{\star}\leq g\leq
g^{\star}(1+c)}|\sum_{i=1}^{g}\overline{a}\left(\mathsf{r}_{i,k},D\right)-\sum_{i=1}^{g^{\star}}\overline{a}\left(\mathsf{r}_{i,k},D\right)|\geq
tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)}\mid D\right\\}$
$\displaystyle=P\left\\{\max_{g^{\star}(1-c)\leq g\leq
g^{\star}}|\sum_{i=1}^{g^{\star}-g}\overline{a}\left(\mathsf{r}_{i,k},D\right)|\geq
tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)}\mid D\right\\}$
$\displaystyle+P\left\\{\max_{g^{\star}\leq g\leq
g^{\star}(1+c)}|\sum_{i=1}^{g-g^{\star}}\overline{a}\left(\mathsf{r}_{i,k},D\right)|\geq
tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)}\mid D\right\\}.$ (C.16)

To bound the two probabilities (C.16), we apply the following Chernoff-type
variation to the Kolmogorov maximal inequality, due to Steiger, (1970).

###### Theorem C.1 (Steiger,, 1970).

Let $S_{i}$, $i=1,2,\ldots$, be a real-valued martingale sequence. If the
moment generating function

$m_{n}\left(\theta\right)=\mathbb{E}\left[\exp\left(\theta
S_{n}\right)\right]$

is finite for all positive $\theta$, then the inequality

$\log\text{ }P\left\\{\max_{1\leq n^{\prime}\leq
n}S_{n^{\prime}}>t\right\\}\leq\inf_{\theta>0}\left(\log
m_{n}\left(\theta\right)-\theta t\right),$

holds.

Conditional on $D$, the random variables

$\overline{a}\left(\mathsf{r}_{i,k},D\right),\quad i=1,2,\ldots,$

are mean-zero, independent, and identically distributed. Thus, the partial
sums

$S_{m}=\sum_{i=1}^{m}\overline{a}\left(\mathsf{r}_{i,k},D\right)$

are a martingale sequence. Moreover, though inspection of the proof of Lemma
5.2, we find that Theorem Theorem 3.1 implies that

$\displaystyle\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\theta
S_{\lfloor cg^{\star}\rfloor}\right)\mid D\right]-\theta\tau\right)$
$\displaystyle=\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\frac{\theta}{\lfloor
cg^{\star}\rfloor}S_{\lfloor cg^{\star}\rfloor}\right)\mid
D\right]-\theta\frac{\tau}{\lfloor cg^{\star}\rfloor}\right)$
$\displaystyle\leq-\frac{\lfloor cg^{\star}\rfloor}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{\delta\tau^{2}}{\left(\lfloor
cg^{\star}\rfloor\right)^{2}}$
$\displaystyle\leq-\frac{\delta}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{\tau^{2}}{cg^{\star}}$

with probability greater than $1-\delta$, as Assumption 3.1 holds and the
fourth-order split stability $\zeta^{(4)}$ is finite. Thus, by setting

$\tau=tg^{\star}\sqrt{v_{g^{\star},k}\left(D\right)}=\sqrt{g^{\star}}t\left(v_{1,k}(D)\right)^{1/2}$

we find that

$\displaystyle\log\frac{1}{2}P\left\\{|U(\mathsf{R}_{\hat{g},k},D)|\geq
t\sqrt{v_{g^{\star},k}\left(D\right)},|\hat{g}-g^{\star}|\leq cg^{\star}\mid
D\right\\}$ $\displaystyle\leq-\frac{\delta v_{1,k}(D)}{2^{4}(2-\varphi
k-\varphi)^{2}\Gamma^{(1)}_{k,\varphi,b}}\frac{t^{2}}{c}$

with probability greater than $1-\delta$, by Theorem C.1 and the inequality
(C.16).

###  C.8. Proof of Lemma B.5, Part (ii)

Observe that

$P\left\\{|\hat{g}-g^{\star}|>cg^{\star}\mid
D\right\\}=P\left\\{g^{\star}\left(1+c\right)<\hat{g}\mid
D\right\\}+P\left\\{\hat{g}<g^{\star}\left(1-c\right)\mid D\right\\}.$ (C.17)

We begin by handling the first term. We have that

$\displaystyle P\left\\{g^{\star}\left(1+c\right)<\hat{g}\mid D\right\\}$
$\displaystyle\leq
P\left\\{\hat{v}_{g^{\star}\left(1+c\right),k}\left(Z\right)-v_{g^{\star}\left(1+c\right),k}\left(D\right)+v_{g^{\star}\left(1+c\right),k}\left(D\right)>\frac{1}{2}\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\mid
D\right\\}$ $\displaystyle\leq
P\left\\{\hat{v}_{g^{\star}\left(1+c\right),k}\left(Z\right)-v_{g^{\star}\left(1+c\right),k}\left(D\right)>\frac{v_{1,k}(D)}{g^{\star}}-\frac{v_{1,k}(D)}{g^{\star}\left(1+c\right)}\mid
D\right\\}$
$\displaystyle=P\left\\{\hat{v}_{g^{\star}\left(1+c\right),k}\left(Z\right)-v_{g^{\star}\left(1+c\right),k}\left(D\right)>\frac{v_{1,k}(D)}{g^{\star}}\frac{c}{1+c}\mid
D\right\\},$

where the first inequality follows the definition of $g^{\star}$. Thus, as
Assumption 3.1 holds and the eighth-order split stability $\zeta^{(8)}$ is
finite, we have that

$\displaystyle\log\frac{1}{4}P\left\\{g^{\star}\left(1+c\right)<\hat{g}\mid
D\right\\}$ $\displaystyle\lesssim-\frac{\delta(v_{1,k}(D))^{2}}{(2-\varphi
k-\varphi)^{4}}\frac{g^{\star}(1+c)c^{2}}{\Gamma_{k,\varphi,b}^{(2)}}$
$\displaystyle\lesssim-\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}c^{2}}{\xi^{2}\Gamma_{k,\varphi,b}^{(2)}}$

with probability greater than $1-\delta$, by Lemma 5.5, the definition of
$g^{\star}$ and the assumption that $0<c<1/2$.

Next, we bound the second term in (C.17). Define the partial sums

$\displaystyle A_{g}$
$\displaystyle=\sum_{\ell=1}^{g}\left(\frac{1}{k^{2}}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-\overline{a}\left(D\right)\right)-v_{1,k}(D)\right)\quad\text{and}$
$\displaystyle B_{g}$
$\displaystyle=\sum_{\ell=1}^{g}\Bigg{(}\frac{1}{k^{2}}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-\overline{a}\left(D\right)\right)$
$\displaystyle\quad\quad\quad\quad\quad+2\sum_{\ell^{\prime}=1}^{\ell-1}\left(T(\mathsf{s}_{\ell,i},D)-\overline{a}\left(D\right)\right)\left(T(\mathsf{s}_{\ell^{\prime},i^{\prime}},D)-\overline{a}\left(D\right)\right)-v_{1,k}(D)\Bigg{)}.$

Observe that the equality

$\hat{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)=\frac{g}{g-1}\left(\tilde{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)\right)-\frac{1}{g-1}\left(\check{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)\right),$

from the proof of Lemma 5.5, implies that

$\displaystyle\hat{v}_{g,k}\left(Z\right)-v_{g,k}\left(D\right)$
$\displaystyle=\frac{1}{g\left(g-1\right)}\sum_{\ell=1}^{g}\frac{1}{k^{2}}\sum_{i,i^{\prime}=1}^{k}\left(T(\mathsf{s}_{\ell,i},D)-a\left(Z\right)\right)\left(T(\mathsf{s}_{\ell,i^{\prime}},D)-a\left(Z\right)\right)-\frac{v_{1,k}(D)}{g}$
$\displaystyle=\frac{1}{g-1}\frac{1}{g}A_{g}-\frac{1}{g-1}\frac{1}{g^{2}}B_{g}$

for all positive $g$. Thus, we can write

$\displaystyle P\left\\{\hat{g}<g^{\star}\left(1-c\right)\mid D\right\\}$
$\displaystyle=P\left\\{\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\hat{v}_{g^{\prime},k}\left(Z\right)\leq\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\mid
D\right\\}$ $\displaystyle=P\left\\{\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)}{\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}}+\frac{1}{g^{\prime}}v_{1,k}(D)\leq\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\mid
D\right\\},$

where the first equality follows from the definition of $\hat{g}$. Now, in the
event that

$\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)}{\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}}+\frac{1}{g^{\prime}}v_{1,k}(D)\leq\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2},$
(C.18)

it must also be the case that

$\displaystyle\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}\left(\frac{\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)}{\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}}+\frac{1}{g^{\prime}}v_{1,k}(D)\right)\leq$
$\displaystyle(\hat{g}-1)(\hat{g})^{2}\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}$
(C.19)

as $\hat{g}\leq g^{\star}\left(1-c\right)$ necessarily. But then, similarly,
(C.19) implies that

$\displaystyle\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)+\frac{(\hat{g}-1)(\hat{g})^{2}}{g^{\prime}}v_{1,k}(D)$
$\displaystyle\leq(\hat{g}-1)(\hat{g})^{2}\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2},$

and in turn

$\displaystyle\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}$
$\displaystyle\leq\frac{(\hat{g}-1)(\hat{g})^{2}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\left(\frac{1}{g^{\star}-1}-\frac{1}{g^{\star}\left(1-c\right)}\right)v_{1,k}(D)$
$\displaystyle=\frac{(\hat{g}-1)(\hat{g})^{2}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\left(\frac{1-g^{\star}c}{g^{\star}\left(g^{\star}-1\right)\left(1-c\right)}\right)v_{1,k}(D),$

are then also true. Finally, again as (C.18) is equivalent to
$\hat{g}<g^{\star}\left(1-c\right)$, we have that

$\displaystyle P\left\\{\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{\left(g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}\right)}{\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}}+\frac{1}{g^{\prime}}v_{1,k}(D)\leq\left(\frac{\xi}{z_{1-\beta/2}}\right)^{2}\mid
D\right\\}$ $\displaystyle\leq P\left\\{\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\leq\left(\frac{1-g^{\star}c}{g^{\star}\left(g^{\star}-1\right)\left(1-c\right)}\right)v_{1,k}(D)\mid
D\right\\}.$

Now, observe that we can write

$\displaystyle P\left\\{\min_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{g^{\prime}A_{g^{\prime}}-B_{g^{\prime}}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\leq\left(\frac{1-g^{\star}c}{g^{\star}\left(g^{\star}-1\right)\left(1-c\right)}\right)v_{1,k}(D)\mid
D\right\\}$ $\displaystyle=P\left\\{\max_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{B_{g^{\prime}}-g^{\prime}A_{g^{\prime}}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\geq\left(\frac{g^{\star}c-1}{g^{\star}\left(g^{\star}-1\right)\left(1-c\right)}\right)v_{1,k}(D)\mid
D\right\\}.$ (C.20)

We bound (C.20) by combining the argument used to establish Lemma 5.5 with an
application of Theorem C.1. To this end, observe that

$\displaystyle P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{B_{g^{\prime}}-g^{\prime}A_{g^{\prime}}}{\left(g-1\right)g^{2}}\leq
t\mid D\right\\}$ $\displaystyle\geq P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{-1}{g-1}\frac{g^{\prime}}{g^{2}}A_{g^{\prime}}\leq\frac{1}{1+\sqrt{g}}t\mid
D\right\\}+P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{1}{g-1}\frac{1}{g^{2}}B_{g^{\prime}}\leq\frac{\sqrt{g}}{1+\sqrt{g}}t\mid
D\right\\}-1$ $\displaystyle\geq P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{g}{g-1}\frac{-1}{g^{2}}A_{g^{\prime}}\leq\frac{\sqrt{g}}{1+\sqrt{g}}t\mid
D\right\\}+P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{1}{g-1}\frac{1}{g^{2}}B_{g^{\prime}}\leq\frac{1}{1+\sqrt{g}}t\mid
D\right\\}-1$ $\displaystyle\geq P\left\\{\max_{2\leq g^{\prime}\leq
g}-A_{g^{\prime}}\leq g^{2}\frac{1}{\sqrt{g}}\frac{g-1}{1+\sqrt{g}}t\mid
D\right\\}+P\left\\{\max_{2\leq g^{\prime}\leq g}|B_{g^{\prime}}|\leq
g^{2}\frac{g-1}{1+\sqrt{g}}t\mid D\right\\}-1$ (C.21)

for any $t>0$ and any positive integer $D$. Observe that the partial sums
$A_{g}$ and $B_{g}$ are both martingale sequences. As Assumption 3.1 holds and
the eighth-order split stability $\zeta^{(8)}$ is finite, though inspection of
the proof of Lemma 5.2, Lemma B.4 implies that implies that

$\displaystyle\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\theta
A_{g}\right)\mid D\right]-\theta
g^{2}\frac{1}{\sqrt{g}}\frac{g-1}{1+\sqrt{g}}t\right)$
$\displaystyle=\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\frac{\theta}{g^{2}}A_{g}\right)\mid
D\right]-\theta\frac{1}{\sqrt{g}}\frac{g-1}{1+\sqrt{g}}t\right)$
$\displaystyle\lesssim-\frac{\delta}{(2-\varphi
k-\varphi)^{4}}\frac{g^{3}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}$ (C.22)

and

$\displaystyle\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\theta
B_{g}\right)\mid D\right]-\theta g^{2}\frac{g-1}{1+\sqrt{g}}t\right)$
$\displaystyle=\inf_{\theta>0}\left(\log\mathbb{E}\left[\exp\left(\frac{\theta}{g^{2}}B_{g}\right)\mid
D\right]-\theta\frac{g-1}{1+\sqrt{g}}t\right)$
$\displaystyle\lesssim-\frac{\delta}{(2-\varphi
k-\varphi)^{4}}\frac{g^{3}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}$ (C.23)

each with probability greater than $1-\delta$, where we have used the facts
that $4g\leq\left(1+\sqrt{g}\right)^{2}$ for all $g\geq 1$ and
$\left(1/4\right)g^{2}\geq\left(g-1\right)^{2}$ for all $g\geq 2$. Hence, by
Theorem C.1, and plugging (C.22) and (C.23) into (C.21), we find that

$\displaystyle\log\frac{1}{4}P\left\\{\max_{2\leq g^{\prime}\leq
g}\frac{B_{g^{\prime}}-g^{\prime}A_{g^{\prime}}}{\left(g^{\prime}-1\right)\left(g^{\prime}\right)^{2}}\geq
t\mid D\right\\}$ $\displaystyle\lesssim-\frac{\delta}{(2-\varphi
k-\varphi)^{4}}\frac{g^{3}t^{2}}{\Gamma_{k,\varphi,b}^{(2)}}$

with probability greater than $1-\delta$. Consequently, by (C.20) and the
definition of $g^{\star}$, we find that

$\displaystyle\log\frac{1}{4}P\left\\{g^{\star}-\hat{g}\geq c\mid D\right\\}$
$\displaystyle=\log\frac{1}{4}P\left\\{\max_{2\leq g^{\prime}\leq
g^{\star}\left(1-c\right)}\frac{B_{g^{\prime}}-g^{\prime}A_{g^{\prime}}}{\left(g^{\star}\left(1-c\right)-1\right)\left(g^{\star}\left(1-c\right)\right)^{2}}\geq\left(\frac{g^{\star}c-1}{g^{\star}\left(g^{\star}-1\right)\left(1-c\right)}\right)v_{1,k}(D)\mid
D\right\\}$ $\displaystyle\lesssim-\frac{\delta(v_{1,k}(D))^{2}}{(2-\varphi
k-\varphi)^{4}}\frac{g^{\star}(1-c)(g^{\star}c-1)^{2}}{(g^{\star}-1)^{2}\Gamma_{k,\varphi,b}^{(2)}}$
$\displaystyle\lesssim-\frac{\delta(v_{1,k}(D))^{2}}{(2-\varphi
k-\varphi)^{4}}\frac{g^{\star}c^{2}}{\Gamma_{k,\varphi,b}^{(2)}}$
$\displaystyle\lesssim-\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}c^{2}}{\xi^{2}\Gamma_{k,\varphi,b}^{(2)}}$

where in the second to last inequality we have used the facts that
$\frac{1}{2}x\leq x-1$ for $x\geq 2$ and $g^{\star}c\geq 2$. Thus, putting the
pieces together, we find that

$\displaystyle\log\frac{1}{8}P\left\\{|\hat{g}-g^{\star}|>cg^{\star}\mid
D\right\\}\lesssim-\frac{\delta(v_{1,k}(D))^{3}}{(2-\varphi
k-\varphi)^{4}}\frac{z_{1-\beta/2}c^{2}}{\xi^{2}\Gamma_{k,\varphi,b}^{(2)}}$

with probability greater than $1-\delta$, as required.

##  Appendix D Additional Results

###  D.1. Examples of Positive and Negative Conditional Covariance

In this appendix, we give simple examples where the conditional covariance
$\gamma_{n,b}(D)$ obtains either endpoint of the Cauchy-Schwarz bound

$-\phi_{n,b}(D)\leq\gamma_{n,b}(D)\leq\phi_{n,b}(D)\leavevmode\nobreak\ .$

Suppose that the data are

$D_{1}=-4,\quad D_{2}=-2,\quad D_{3}=2,\quad\text{and}\quad
D_{4}=4\leavevmode\nobreak\ .$

Set $b=2$ and consider the statistic

$T(\mathsf{s},D)=\big{|}\sum_{i\in\mathsf{s}}D_{i}\big{|}$

Observe that

$T(\mathsf{s},D)=T(\tilde{\mathsf{s}},D)$

for each set $\mathsf{s}$ in $\\{1,\ldots,4\\}$ of size 2. Thus, we have that

$\gamma_{n,b}(D)=\operatorname{Cov}(T(\mathsf{s},D),T(\tilde{\mathsf{s}},D)\mid
D)=\operatorname{Var}(T(\mathsf{s},D)\mid D)=\phi_{n,b}(D)\leavevmode\nobreak\
$

giving one end of the inequality.141414Observe that this will occur for any
mean zero data set. On the other hand, suppose that

$T(\mathsf{s},D)=\sum_{i\in\mathsf{s}}D_{i}\leavevmode\nobreak\ .$

In this case, we have that

$T(\mathsf{s},D)=-T(\tilde{\mathsf{s}},D)$

and thereby

$\gamma_{n,b}(D)=\operatorname{Cov}(T(\mathsf{s},D),T(\tilde{\mathsf{s}},D)\mid
D)=-\operatorname{Var}(T(\mathsf{s},D)\mid
D)=-\phi_{n,b}(D)\leavevmode\nobreak\ ,$

giving the other end of the inequality.

###  D.2. Stability of Regularized M-Estimation

In this appendix, we study the $(r,q)$th-order training sample
$\sigma_{\mathsf{train}}^{(r,q)}$ defined in 3.1. Our analysis is specialized
to the case that the estimator $\hat{\eta}$ is a regularized empirical risk
minimizer and is closely related to the proof of Proposition 4 of Austern and
Zhou, (2020).

Assume that the parameter $\eta$ is an element of some closed convex space
$H\subseteq\mathbb{R}^{p}$. Consider the estimator

$\displaystyle\Psi\left(D_{\mathsf{s}},\eta\right)$
$\displaystyle=\frac{1}{b}\sum_{i\in\mathsf{s}}\psi\left(D_{i},\eta\right)$
(D.1) $\displaystyle\hat{\eta}$ $\displaystyle=\underset{\eta\in
H}{\arg\min}\left\\{\frac{1}{n-b}\sum_{i\in\tilde{\mathsf{s}}}\ell\left(D_{i},\eta\right)+\lambda_{1,n}\|\eta\|_{1}+\lambda_{2,n}\|\eta\|_{2}\right\\},$
(D.2)

where $\psi\left(\cdot,\cdot\right)$ are $\ell\left(\cdot,\cdot\right)$
functions and $\lambda_{1,n},\lambda_{2,n}\geq 0$ are penalty parameters. Let
$\nabla\ell\left(d,\eta\right)$ and $\nabla^{2}\ell\left(d,\eta\right)$ denote
the gradient and Hessian of the function $\eta\mapsto\ell\left(d,\eta\right)$.
Similarly, we write

$\displaystyle\overline{\nabla}_{\tilde{\mathsf{s}}}\ell\left(D,\eta\right)$
$\displaystyle=\frac{1}{n-b}\sum_{i\in\tilde{\mathsf{s}}}\nabla\ell\left(D_{i},\eta\right)\quad\text{and}$
$\displaystyle\overline{\nabla}_{\tilde{\mathsf{s}}}^{2}\ell\left(D,\eta\right)$
$\displaystyle=\frac{1}{n-b}\sum_{i\in\tilde{\mathsf{s}}}\nabla^{2}\ell\left(D_{i},\eta\right)$

for the empirical averages of the gradients and the Hessian evaluated on the
data in the set $\tilde{\mathsf{s}}$. Define the moment

$\kappa_{r}=\mathbb{E}\left[\left(\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})\right)^{r}\right]$

for every even integer r.

###### Assumption D.1.

The minimum eigenvalue of
$\overline{\nabla}_{\tilde{\mathsf{s}}}^{2}\ell\left(D,\eta\right)$ is bounded
below by $\rho$ almost surely.

###### Assumption D.2.

For some strictly positive constant $C_{\psi}$, the function
$\psi\left(\cdot,\cdot\right)$ satisfies the inequality

$|\psi\left(d,\eta\right)-\psi\left(d,\eta^{\prime}\right)|\leq
C_{\psi}\|\eta-\eta^{\prime}\|_{2}$

for each $\eta\in H$ and $d$.

###### Assumption D.3.

The loss function $\ell\left(\cdot,\cdot\right)$ is strictly convex and twice
continuously differentiable in its second argument.

###### Theorem D.1.

Under Assumptions D.1, D.2, and D.3, if $\rho+\lambda_{2,n}>0$, then

$\sigma_{\mathsf{train}}^{(r,q)}\lesssim\left(\frac{q}{n-b}\frac{\kappa_{r}}{\rho+\lambda_{2,n}}\right)^{r}+\left(\lambda_{1,n}\frac{p}{\rho+\lambda_{2,n}}\right)^{r}$

as $n\to\infty$, for all even integers $r$ and positive integers $q\leq n-b$.

######  Remark D.1.

Assumption D.1 implies that the dimension $p$ of the parameter vector $\eta$
is less than the number of observations $n$. To the best of our knowledge,
analysis of the stability of $\ell_{1}$ regularized empirical risk
minimization in the regime with $p$ larger than $n$ is an open problem.
Further analysis of this quantity in the high-dimensional regime is a
promising direction for further research, given the widespread use of cross-
validation for estimation of the prediction error for the lasso and the
connections between stability and the concentration of cross-splitting
established in this paper.

######  Remark D.2.

A necessary and sufficient condition for $\hat{\eta}$ to be consistent for the
population risk minimizer associated with (D.2) is that
$\lambda_{1,n}=o\left((n-b)^{-1}\right)$. See e.g., Knight and Fu, (2000).
Thus, so long as the penalty $\lambda_{1,b}$ is chosen in this regime, the
training sample stability $\sigma_{\mathsf{train}}^{(r,q)}$ will be

$O\left(\left(\frac{q\kappa_{r}}{n-b}\right)^{-r}\right)$

as required.

####  D.2.1. Proof of Theorem D.1

By Assumptions D.3 and D.1, the objective function for the estimator (D.2) is
strongly convex. Thus, there is a unique solution to (D.2) for any data $D$.
Let $\hat{\eta}$ and $\hat{\eta}^{\prime}$ denote the solutions to (D.2) for
the data $D$ and $\tilde{D}^{(\mathsf{q})}$ respectively. Let $\partial
f\left(x\right)$ denote the subgradient set of the function $x\mapsto
f\left(x\right)$. The Karush-Kuhn-Tucker condition for the program (D.2) is
given by

$\overline{\nabla}_{\tilde{\mathsf{s}}}\ell\left(D,\eta\right)+\lambda_{2,n}\hat{\eta}+\lambda_{1,n}\hat{z}=0,$
(D.3)

where $\hat{z}\in\partial\|\hat{\eta}\|_{1}$ is the subgradient associated
with the Lasso penalty. Observe that, in this case,
$\hat{z}\in\text{sign}\left(\hat{\eta}\right)$, where we set
$\text{sign}\left(0\right)=\left[-1,1\right]$. Let $\hat{z}$ and
$\hat{z}^{\prime}$ denote the subgradients obtained from $D$ and
$\tilde{D}^{(\mathsf{q})}$, respectively. As $\ell\left(d,\cdot\right)$ is
twice continuously differentiable under Assumption D.3 (i), we have that

$\displaystyle\overline{\nabla}_{\tilde{\mathsf{s}}}\ell\left(D,\hat{\eta}^{\prime}\right)+\lambda_{2,n}\hat{\eta}^{\prime}+\lambda_{1,n}\hat{z}$
$\displaystyle=\overline{\nabla}_{\tilde{\mathsf{s}}}\ell\left(D,\hat{\eta}\right)+\lambda_{2,n}\hat{\eta}+\lambda_{1,n}\hat{z}+\left(\overline{\nabla}_{\tilde{\mathsf{s}}}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2,n}I_{d}\right)\left(\hat{\eta}-\hat{\eta}^{\prime}\right)$
$\displaystyle=\left(\overline{\nabla}_{\tilde{\mathsf{s}}}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2,n}I_{d}\right)\left(\hat{\eta}-\hat{\eta}^{\prime}\right)$
(D.4)

for some vector $\tilde{\eta}$, by a Taylor expansion and the optimality
condition (D.3). On the other hand, we have that

$\displaystyle\overline{\nabla}_{\tilde{\mathsf{s}}}\ell\left(D,\hat{\eta}^{\prime}\right)+\lambda_{2,n}\hat{\eta}^{\prime}+\lambda_{1,n}\hat{z}$
$\displaystyle=\overline{\nabla}_{\tilde{\mathsf{s}}}\ell(\tilde{D}^{(\mathsf{q})},\hat{\eta}^{\prime})+\lambda_{2,n}\hat{\eta}^{\prime}+\lambda_{1,n}\hat{z}^{\prime}$
$\displaystyle\quad+\frac{1}{n-b}\left(\sum_{i\in\mathsf{q}}\nabla\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})\right)+\lambda_{1,n}\left(\hat{z}-\hat{z}^{\prime}\right)$
$\displaystyle=\frac{1}{n-b}\left(\sum_{i\in\mathsf{q}}\nabla\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})\right)+\lambda_{1,n}\left(\hat{z}-\hat{z}^{\prime}\right)$
(D.5)

again by the optimality condition (D.3). Thus, we have that

$\displaystyle\left(\overline{\nabla}_{\tilde{\mathsf{s}}}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2,n}I_{p}\right)\left(\hat{\eta}-\hat{\eta}^{\prime}\right)$
$\displaystyle=\frac{1}{n-b}\left(\sum_{i\in\mathsf{q}}\nabla\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})\right)+\lambda_{1,n}\left(\hat{z}-\hat{z}^{\prime}\right)$
(D.6)

by (D.4) and (D.5). Observe that the the matrix
$\overline{\nabla}_{\tilde{\mathsf{s}}}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2,n}I_{p}$
is invertible by Assumption D.1. Thus, we find that

$\displaystyle\hat{\eta}-\hat{\eta}^{\prime}$
$\displaystyle=\frac{1}{n-b}\left(\overline{\nabla}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2}I_{p}\right)^{-1}\left(\sum_{i\in\mathsf{q}}\nabla\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})\right)$
$\displaystyle+\lambda_{1,n}\left(\overline{\nabla}^{(2)}\ell\left(D,\tilde{\eta}\right)+\lambda_{2}I_{d}\right)^{-1}\left(\hat{z}-\hat{z}^{\prime}\right)$

and that consequently

$\displaystyle\|\hat{\eta}-\hat{\eta}^{\prime}\|_{2}$
$\displaystyle\lesssim\frac{1}{n-b}\frac{\sum_{i\in\mathsf{q}}\nabla\ell(D^{\prime}_{i},\hat{\eta}^{\prime})-\nabla\ell(D_{i},\hat{\eta}^{\prime})}{\left(\rho+\lambda_{2,n}\right)}+\lambda_{1,n}\frac{p}{\rho+\lambda_{2,n}}$
(D.7)

by Assumption D.1. Hence, we have that

$\displaystyle\sigma_{\mathsf{train}}^{(r,q)}$
$\displaystyle=\mathbb{E}\left[\left(T\left(\mathsf{s},D\right)-T(\mathsf{s},\tilde{D}^{(\mathsf{q})})\right)^{r}\right]$
$\displaystyle\lesssim\mathbb{E}\left[\|\hat{\eta}-\hat{\eta}^{\prime}\|_{2}^{r}\right]$
$\displaystyle\lesssim\left(\frac{1}{(n-b)}\frac{q\kappa_{r}}{\rho+\lambda_{2,n}}\right)^{r}+\left(\lambda_{1,n}\frac{p}{\rho+\lambda_{2,n}}\right)^{r},$

by Assumption D.2.

###  D.3. Comparison with Zhang, (2022)

We state a Berry-Esseen bound for $a\left(\mathsf{R}_{g,k},D\right)$ through
an application of a result due to Zhang, (2022). In contrast to the bound
stated in 3.1, the bound obtained here does not shrink as $g$ increases. On
the other hand, the bound obtained in below is unconditional. It is
straightforward to modify our argument to give an analogous high-probability
conditional bound.

###### Theorem D.2.

Let $W$ denote a standard normal random variable. Suppose that Assumptions 3.1
and 3.2 hold and that the data $D$ are independent and identically
distributed. If the eighth-order split stability $\zeta^{(8)}$ is finite, then
the Berry-Esseen inequality

$\displaystyle
d_{\text{K}}\left(\frac{a\left(\mathsf{R}_{g,k},D\right)-\overline{a}\left(D\right)}{\sqrt{\mathbb{E}\left[v_{g,k}\left(D\right)\right]}},W\right)$
$\displaystyle\leq\frac{4\left(2-\varphi
k-\varphi\right)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}{\mathbb{E}\left[v_{1,k}(D)\right]}$

is satisfied.

####  D.3.1. Proof of Theorem D.2

We apply the following central limit theorem, due to Zhang, (2022). This
result generalizes Theorem 2.1 of Shao and Zhang, (2019) to accommodate
general Stein representers.

###### Theorem D.3 (Zhang,, 2022, Theorem 4.1, ).

Let $\mathcal{X}$ be a separable metric space and suppose that
$\left(X,X^{\prime}\right)$ is an exchangeable pair of $\mathcal{X}$-valued
random variables. Suppose that $f:\mathcal{X}\to\mathbb{R}$ and
$F:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ are square-integrable functions
such that $F$ is antisymmetric and

$\mathbb{E}\left[F\left(X,X^{\prime}\right)\mid X\right]=f\left(X\right)$

almost surely. Assume that $\operatorname{Var}\left(f\left(X\right)\right)$ is
finite and non-zero and that $\mathbb{E}\left[f\left(X\right)\right]=0$.
Define the objects

$\displaystyle\overline{f}\left(X\right)$
$\displaystyle=f\left(X\right)/\sqrt{\operatorname{Var}\left(f\left(X\right)\right)}.$
(D.8) $\displaystyle G\left(X\right)$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\left(f\left(X\right)-f\left(X^{\prime}\right)\right)F\left(X,X^{\prime}\right)\mid
X\right]\quad\text{and}$ (D.9) $\displaystyle\overline{G}\left(X\right)$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\left(f\left(X\right)-f\left(X^{\prime}\right)\right)|F\left(X,X^{\prime}\right)|\mid
X\right].$ (D.10)

Let $W$ denote a standard normal random variable. The bound

$\displaystyle d_{K}\left(\overline{f}\left(X\right),W\right)$
$\displaystyle\leq\frac{\mathbb{E}\left[|G\left(X\right)-\mathbb{\mathbb{E}}\left[G\left(X\right)\right]|\right]+\mathbb{E}\left[|\overline{G}\left(X\right)|\right]}{\operatorname{Var}\left(f\left(X\right)\right)}$
(D.11)

is satisfied.

To this end, define the objects

$\displaystyle B\left(Z\right)$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)A\left(Z,Z^{\prime}\right)\mid
Z\right]\quad\text{and}$ $\displaystyle\overline{B}\left(Z\right)$
$\displaystyle=\frac{1}{2}\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)|A\left(Z,Z^{\prime}\right)|\mid
Z\right].$

It will suffice to bound the quantity

$\frac{\mathbb{E}\left[|B\left(Z\right)-\mathbb{\mathbb{E}}\left[B\left(Z\right)\right]|\right]+\mathbb{E}\left[|\overline{B}\left(Z\right)|\right]}{\operatorname{Var}\left(a\left(Z\right)-\overline{a}\left(Z\right)\right)}.$
(D.12)

Observe that

$\displaystyle\mathbb{E}\left[|B\left(X\right)-\mathbb{\mathbb{E}}\left[B\left(X\right)\right]|\right]$
$\displaystyle\leq\sqrt{\operatorname{Var}\left(B\left(Z\right)\right)}\quad\text{and}$
$\displaystyle\mathbb{E}\left[|\overline{B}\left(Z\right)|\right]$
$\displaystyle\leq\sqrt{\operatorname{Var}\left(\overline{B}\left(Z\right)\right)}$

by the Cauchy-Schwarz inequality and the fact that
$\mathbb{E}\left[\overline{B}\left(X\right)\right]=0$ by exchangeability.
Consequently, as

$\displaystyle\operatorname{Var}\left(B\left(Z\right)\right)$
$\displaystyle\leq\mathbb{E}\left[B\left(Z\right)^{2}\right]=\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2}A\left(Z,Z^{\prime}\right)^{2}\right]=\operatorname{Var}\left(\overline{B}\left(Z\right)\right)$

it will suffice to bound

$2\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2}A\left(Z,Z^{\prime}\right)^{2}\right].$
(D.13)

By Young’s inequality, we have that

$\displaystyle\mathbb{E}\left[\left(a\left(Z\right)-a\left(Z^{\prime}\right)\right)^{2}A\left(Z,Z^{\prime}\right)^{2}\right]$
$\displaystyle\leq\frac{1}{2}\left(s^{-1}\mathbb{E}\left[U_{a}^{(2)}(Z)\right]+s\mathbb{E}\left[U_{A}^{(2)}(Z)\right]\right)\leavevmode\nobreak\
,$

where $U_{a}^{(2)}(Z)$ and $U_{A}^{(2)}(Z)$ are defined in Section 5.2.

Observe that the bound

$\left(\sum_{m=0}^{\infty}\mathbb{E}\left[a\left(Z_{m}\right)-a\left(Z_{m}^{\prime}\right)\mid
Z_{0}=Z,Z_{0}^{\prime}=Z^{\prime}\right]\right)^{4}\leq\left(2gn^{2}\max_{\mathsf{s},\mathsf{s}^{\prime}\in\mathsf{S}_{n,b}}\left(T\left(\mathsf{s},D\right)-T\left(\mathsf{s}^{\prime},D\right)\right)\right)^{4}$
(D.14)

holds by Lemma B.1 and that the right-hand side of (D.14) is square-integrable
as the eighth-order split stability $\zeta^{(8)}$ is finite. Thus, by
combining Lemma B.3 and Lemma 5.4, we have that

$\overline{U}_{A}^{(2)}\leq\
\left(\frac{gn^{2}}{2}\right)^{2}\left(\frac{4\left(2n-bk-b\right)^{2}}{gn^{2}}\right)^{2}\Gamma_{k,\varphi,b}^{(2)}$

and

$\overline{U}_{a}^{(2)}\leq\left(\frac{2}{gn^{2}}\right)^{2}\left(\frac{4\left(2n-bk-b\right)^{2}}{gn^{2}}\right)^{2}\Gamma_{k,\varphi,b}^{(2)}\leavevmode\nobreak\
.$

Hence, by taking $s=\left(gn^{2}/2\right)^{2}$, we find that (D.13) is bounded
above by

$\frac{4}{gn^{2}}\left(\left(2n-bk-b\right)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}\right)$

Now, we have that

$\text{Var}\left(a\left(Z\right)-\overline{a}\left(D\right)\right)=\mathbb{E}\left[v_{g,k}\left(D\right)\right]$

by the law of total variance and the fact that
$\mathbb{E}\left[a\left(Z\right)-\overline{a}\left(D\right)\mid D\right]=0$.
Consequently we can decompose

$\displaystyle\mathbb{E}\left[v_{g,k}\left(D\right)\right]$
$\displaystyle=\frac{\mathbb{E}[\phi_{n,b}(D)]+\left(k-1\right)\mathbb{E}[\gamma_{n,b}(D)]}{kg}.$
(D.15)

Hence, we have that (D.12) is bounded above by

$\frac{4\left(2-\varphi
k-\varphi\right)^{2}(\Gamma_{k,\varphi,b}^{(2)})^{1/2}}{\mathbb{E}\left[v_{1,k}(D)\right]},$

as required.