$\displaystyle\lesssim\inf_{m\geq
1}\left\\{\sqrt{\log(6/\eta)}\sigma(\Sigma,m)+\frac{am^{2}\log(m^{2}/\eta)}{\sqrt{n}}\right\\}$
$\displaystyle\lesssim\inf_{m\geq
1}\left\\{\frac{M\sigma(T,m)}{\lambda}\sqrt{\log(6/\eta)}+m^{2}\frac{M\log(m^{2}/\eta)}{\lambda\sqrt{n}}\right\\}$

holds with probability at least $1-\eta$. Thus, by a union bound, it holds
with probability $1-\eta$ that

$\left\lVert\sqrt{n}(\hat{f}-f_{\lambda})-\frac{1}{\sqrt{n}}\sum_{i=1}^{n}Z_{i}\right\rVert\lesssim
Q_{\mathrm{bd}}(T,n,\lambda)M\log(12/\eta)+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}M\log(8/\eta)^{2},$

where we have simplified and consolidated log factors. ∎

Recall the bootstrap process

$\mathfrak{B}=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}h_{ij}\left(\frac{\hat{V}_{i}-\hat{V}_{j}}{\sqrt{2}}\right),\quad\hat{V}_{i}=\\{Y_{i}-\hat{f}(X_{i})\\}\hat{T}_{\lambda}^{-1}k_{X_{i}}.$

######  Proposition G.15 (Bootstrap approximation: Bounded).

Suppose Assumption 6.10 holds. Then, there exists a random variable $Z$ whose
conditional distribution given $U$ is Gaussian with covariance $\Sigma$, and
such that with probability at least $1-\eta$

$\mathbb{P}\left[\vphantom{\sum}\left\lVert\mathfrak{B}-Z\right\rVert\lesssim
M\log(16/\eta)^{2}\left\\{R_{\mathrm{bd}}(T,n,\lambda)+\frac{\kappa\mathfrak{n}(\lambda)}{\sqrt{n}}\right\\}\middle|U\right]\geq
1-\eta$

where

$R_{\mathrm{bd}}(T,n,\lambda)\coloneqq\inf_{m\geq
1}\left\\{\left(\frac{m\mathfrak{n}(\lambda)}{\lambda^{2}n}+\frac{m}{\lambda^{4}n^{2}}\right)^{\frac{1}{4}}+\frac{1}{\lambda}\sigma(T,m)\right\\}.$

###### Proof.

Under Assumption 6.10, Theorem E.9 implies that

$\left\|\mathfrak{B}-\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}h_{ij}\frac{U_{i}-U_{j}}{\sqrt{2}}\right\|\lesssim\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa
M\ln(16/\eta)^{2}$

holds with probability at least $1-\eta$ since
$n\geq\frac{4\kappa^{2}}{\mathfrak{n}(\lambda)\lambda^{2}}$ implies

$\frac{2\kappa}{n\lambda}\leq\sqrt{\frac{\mathfrak{n}(\lambda)}{n}},\quad\sqrt{\mathfrak{n}(\lambda)}\geq\frac{1}{\sqrt{n}\lambda},\quad\sqrt{\mathfrak{n}(\lambda)}\geq\frac{\mathfrak{n}(\lambda)^{1/4}}{n^{1/4}\lambda^{1/2}}.$

We use Corollary D.15 along with the bounds in Lemmas G.10 and G.11. In
particular, set
$W=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}h_{ij}\frac{U_{i}-U_{j}}{\sqrt{2}}$,
$W^{\prime}=\mathfrak{B}$, and
$\delta=\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa M\ln(16/\eta)^{2}$. Then
there must exist $Z$ with the desired conditional distribution, such that with
probability at least $1-\eta$, the $\sigma(U)$-conditional probability of the
event

$\displaystyle\left\lVert Z-\mathfrak{B}\right\rVert$
$\displaystyle\lesssim\log(6/\eta)^{3/2}\inf_{m\geq
1}\bigg{\\{}m^{\frac{1}{4}}\left(\frac{M^{2}\cdot
M^{2}\mathfrak{n}(\lambda)}{\lambda^{2}n}+\frac{M^{4}}{\lambda^{4}n^{2}}\right)^{\frac{1}{4}}$
$\displaystyle\qquad+\frac{M}{\lambda}\sigma(T,m)\bigg{\\}}+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa
M\log(16/\eta)^{2}$ $\displaystyle\lesssim M\log(16/\eta)^{2}\left(\inf_{m\geq
1}\left\\{m^{\frac{1}{4}}\left(\frac{\mathfrak{n}(\lambda)}{\lambda^{2}n}+\frac{1}{\lambda^{4}n^{2}}\right)^{\frac{1}{4}}+\frac{\sigma(T,m)}{\lambda}\right\\}+\frac{\kappa\mathfrak{n}(\lambda)}{\sqrt{n}}\right)$
$\displaystyle=M\log(16/\eta)^{2}\left(R_{\mathrm{bd}}(T,n,\lambda)+\frac{\kappa\mathfrak{n}(\lambda)}{\sqrt{n}}\right)$

is at least $1-\eta$ when $n\geq 2$. ∎

#####  G.4.3 Q and R for sub-Gaussian summands

In what follows, define
$\tilde{M}:=\frac{1}{\underline{\sigma}}(\kappa\|f_{0}\|+\bar{\sigma})$ and
$\bar{M}=M\vee\tilde{M}$.

######  Proposition G.16 (Gaussian approximation: Sub-Gaussian).

Suppose Assumptions 6.10 and 6.12 hold. Then there exists a Gaussian random
element in $H$, with covariance $\Sigma$, such that with probability $1-\eta$,

$\left\lVert\sqrt{n}(\hat{f}-f_{\lambda})-Z\right\rVert\lesssim
Q_{\mathrm{sg}}(T,n,\lambda)\bar{M}^{4}b^{3}(6/\eta)^{1/\log(mn)}+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}M\log(8/\eta)^{2},$

where

$Q_{\mathrm{sg}}(T,n,\lambda)=\inf_{m\geq
1}\left\\{\frac{\sigma(T,m)}{\lambda}+\frac{m^{3/2}\log(n^{2})}{\sqrt{n\lambda}}\right\\}.$

###### Proof.

By Theorem B.4, with probability at least $1-\eta$,

$\left\lVert\sqrt{n}(\hat{f}-f_{\lambda})-\frac{1}{\sqrt{n}}\sum_{i=1}^{n}U_{i}\right\rVert\lesssim\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}M\log(4/\eta)^{2}$

since

$\frac{2\kappa}{n\lambda}\leq\sqrt{\frac{\mathfrak{n}(\lambda)}{n}}\iff
n\geq\frac{4\kappa^{2}}{\mathfrak{n}(\lambda)\lambda^{2}}.$

Then, using Proposition C.8 together with the bounds deduced in Lemmas G.10
and G.12, we deduce that

$\displaystyle\left\|\frac{1}{\sqrt{n}}\sum_{i=1}^{n}U_{i}-Z\right\|$
$\displaystyle\lesssim\inf_{m\geq
1}\left\\{\tilde{b}\sigma(\Sigma,m)\sqrt{\log(6/\eta)}+\left\lVert\Sigma\right\rVert_{op}^{\frac{1}{2}}\tilde{b}^{3}\left(\frac{m^{\frac{3}{2}}\log(n)^{2}}{\sqrt{n}}\right)(3/\eta)^{1/\log(mn)}\right\\}$
$\displaystyle\lesssim\inf_{m\geq
1}\left\\{\tilde{M}b\frac{M\sigma(T,m)}{\lambda}\sqrt{\log(6/\eta)}+\frac{M}{\sqrt{\lambda}}\tilde{M}^{3}b^{3}\left(\frac{m^{\frac{3}{2}}\log(n)^{2}}{\sqrt{n}}\right)(3/\eta)^{1/\log(mn)}\right\\}$

holds with probability at least $1-\eta$. Note that we use the bound

$\|\Sigma\|_{op}\leq M^{2}\|T_{\lambda}^{-2}T\|_{op}\leq
M^{2}\frac{1}{\lambda}$

which is justified in the proof of Proposition I.4 with $s=1$ and $c=2$.

Thus, by a union bound, it holds with probability $1-\eta$ that

$\left\lVert\sqrt{n}(\hat{f}-f_{\lambda})-Z\right\rVert\lesssim
Q_{\mathrm{bd}}(T,n,\lambda)\bar{M}^{4}b^{3}(6/\eta)^{1/\log(mn)}+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}M\log(8/\eta)^{2},$

where we have simplified and consolidated log factors. ∎

######  Proposition G.17 (Bootstrap approximation: Sub-Gaussian).

Suppose Assumptions 6.10 and 6.12 hold. Then, there exists a random variable
$Z$ whose conditional distribution given $U$ is Gaussian with covariance
$\Sigma$, and such that with probability at least $1-\eta$

$\mathbb{P}\left[\vphantom{\sum}\left\lVert\mathfrak{B}-Z\right\rVert\lesssim\bar{M}^{2}b\cdot\log(16/\eta)^{2}\left\\{R_{\mathrm{sg}}(T,n,\lambda)+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\right\\}\middle|U\right]\geq
1-\eta$

where

$R_{\mathrm{sg}}(T,n,\lambda)\coloneqq\inf_{m\geq
1}\left\\{\left(\frac{m\mathfrak{n}(\lambda)^{2}}{n}\right)^{\frac{1}{4}}+\frac{1}{\lambda}\sigma(T,m)\right\\}.$

###### Proof.

Under Assumption 6.10, Theorem E.9 implies that

$\left\|\mathfrak{B}-\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}h_{ij}\frac{U_{i}-U_{j}}{\sqrt{2}}\right\|\lesssim\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa
M\ln(16/\eta)^{2}$

holds with probability at least $1-\eta$ since
$n\geq\frac{4\kappa^{2}}{\mathfrak{n}(\lambda)\lambda^{2}}$ implies

$\frac{2\kappa}{n\lambda}\leq\sqrt{\frac{\mathfrak{n}(\lambda)}{n}},\quad\sqrt{\mathfrak{n}(\lambda)}\geq\frac{1}{\sqrt{n}\lambda},\quad\sqrt{\mathfrak{n}(\lambda)}\geq\frac{\mathfrak{n}(\lambda)^{1/4}}{n^{1/4}\lambda^{1/2}}.$

We use Corollary D.15 along with the bounds in Lemmas G.10 and G.12. In
particular, set
$W=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{n}h_{ij}\frac{U_{i}-U_{j}}{\sqrt{2}}$,
$W^{\prime}=\mathfrak{B}$, and
$\delta=\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa M\ln(16/\eta)^{2}$. Then
there must exist $Z$ with the desired conditional distribution, such that with
probability at least $1-\eta$, the $\sigma(U)$-conditional probability of the
event

$\displaystyle\left\lVert Z-\mathfrak{B}\right\rVert$
$\displaystyle\lesssim\log(6/\eta)^{3/2}\inf_{m\geq
1}\left\\{\left(\frac{m}{n}\tilde{M}^{4}b^{4}M^{4}\mathfrak{n}(\lambda)^{2}\right)^{\frac{1}{4}}+\frac{M}{\lambda}\sigma(T,m)\right\\}+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\kappa
M\log(16/\eta)^{2}$
$\displaystyle\lesssim\bar{M}^{2}b\cdot\log(16/\eta)^{2}\left(\inf_{m\geq
1}\left\\{\left(\frac{m\mathfrak{n}(\lambda)^{2}}{n}\right)^{\frac{1}{4}}+\frac{\sigma(T,m)}{\lambda}\right\\}+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\right)$
$\displaystyle=\bar{M}^{2}b\cdot\log(16/\eta)^{2}\left(R_{\mathrm{sg}}(T,n,\lambda)+\frac{\mathfrak{n}(\lambda)}{\sqrt{n}}\right)$

is at least $1-\eta$. ∎

####  G.5 Corollaries

Recall the definitions of quantities appearing in Theorem G.6:

$\displaystyle\begin{aligned}
Q_{\mathrm{bd}}(n,\lambda)&=\frac{1}{\lambda}\inf_{m\geq
1}\left\\{\sigma(m)+\frac{m^{2}\log(m^{2})}{\sqrt{n}}\right\\},\\\
R_{\mathrm{bd}}(n,\lambda)&=\inf_{m\geq
1}\left[\left\\{\frac{m\,\mathfrak{n}(\lambda)}{\lambda^{2}n}+\frac{m}{\lambda^{4}n^{2}}\right\\}^{\frac{1}{4}}+\frac{\sigma(m)}{\lambda}\right],\\\
\end{aligned}\quad\begin{aligned} Q_{\mathrm{sg}}(n,\lambda)&=\inf_{m\geq
1}\left\\{\frac{\sigma(m)}{\lambda}+\frac{m^{\frac{3}{2}}\log(n)^{2}}{\sqrt{n\lambda}}\right\\},\\\
R_{\mathrm{sg}}(n,\lambda)&=\inf_{m\geq
1}\left[\left\\{\frac{m\,\mathfrak{n}^{2}(\lambda)}{n}\right\\}^{\frac{1}{4}}+\frac{\sigma(m)}{\lambda}\right].\\\
\end{aligned}$

We will now give a simplified asymptotic characterization for each of these
expressions under two different assumptions on the spectrum of $T$, namely (i)
polynomial decay, i.e. $\nu_{s}(T)\leq\omega s^{-\beta}$; (ii) exponential
decay, i.e. $\nu_{s}(T)\leq\omega\exp(-\alpha s^{\gamma})$. We suppress
dependence on $T$ in the notation. Note that, within $R_{\mathrm{bd}}$,

$\frac{m\mathfrak{n}(\lambda)}{\lambda^{2}n}\geq\frac{m}{\lambda^{4}n^{2}}\iff
n\geq\frac{1}{\lambda^{2}\mathfrak{n}(\lambda)}$

which is implied by Assumption 6.10.

##### Sobolev RKHS: Bounded data

We proceed in steps.

  1. 1.

If $\nu_{s}\leq\omega s^{-\beta}$ then by Proposition I.2 we have
$\sigma(m)\lesssim_{\beta,\omega}m^{1/2-\beta/2}$, and by Proposition I.4 we
have $\mathfrak{n}(\lambda)\lesssim_{\beta,\omega}\lambda^{-1-1/\beta}$.

  2. 2.

First we study $Q_{\mathrm{bd}}(n,\lambda)$. Plugging in our bound on
$\sigma(m)$ and then equating the main terms (ignoring constants and log
factors) gives

$m^{1/2-\beta/2}=\frac{m^{2}}{\sqrt{n}}\iff m=n^{1/(3+\beta)}.$

Plugging this in and simplifying exponents in the logarithm gives

$\displaystyle Q_{\mathrm{bd}}(n,\lambda)$
$\displaystyle\lesssim_{\beta,\omega}\lambda^{-1}\cdot(n^{\frac{1}{3+\beta}})^{\frac{1-\beta}{2}}\cdot\log(n)$
$\displaystyle=\lambda^{-1}n^{(1-\beta)/(6+2\beta)}\log(n)$
$\displaystyle=\log(n)\left(\frac{1}{n\lambda^{\frac{6+2\beta}{\beta-1}}}\right)^{(\beta-1)/(6+2\beta)}.$

  3. 3.

Next we study $R_{\mathrm{bd}}(n,\lambda)$. Plugging in our bounds and
equating main terms gives

$\displaystyle
m^{\frac{1}{4}}\left\\{\frac{\lambda^{-1-1/\beta}}{\lambda^{2}n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\frac{m^{1/2-\beta/2}}{\lambda}$
$\displaystyle\iff\left\\{\frac{\lambda^{1-1/\beta}}{n}\right\\}^{\frac{1}{1-2\beta}}$
$\displaystyle=m.$

Using this value of $m$ gives the bound

$\displaystyle R_{\mathrm{bd}}(n,\lambda)$
$\displaystyle\lesssim_{\beta,\omega}\left\\{\frac{m^{1/2-\beta/2}}{\lambda}\right\\}$
$\displaystyle=\frac{1}{\lambda}\left\\{\frac{\lambda^{1-1/\beta}}{n}\right\\}^{\frac{1-\beta}{2-4\beta}}$
$\displaystyle=\left\\{\frac{1}{\lambda^{3+1/\beta+2/(\beta-1)}n}\right\\}^{\frac{1-\beta}{2-4\beta}}.$
$\left(\frac{\lambda^{\frac{6+2\beta}{\beta-1}}}{\log(n)}\wedge\lambda^{3+1/\beta+2/(\beta-1)}\right)n\gg
1.$

##### Sobolev RKHS: Sub-Gaussian data

We proceed in steps.

  1. 1.

Once again, if $\nu_{s}\leq\omega s^{-\beta}$ then by Proposition I.2 we have
$\sigma(m)\lesssim_{\beta,\omega}m^{1/2-\beta/2}$, and by Proposition I.4 we
have $\mathfrak{n}(\lambda)\lesssim_{\beta,\omega}\lambda^{-1-1/\beta}$.

  2. 2.

For $Q_{\mathrm{sg}}(n,\lambda)$, equating main terms gives

$\frac{m^{1/2-\beta/2}}{\lambda}=\frac{m^{\frac{3}{2}}}{\sqrt{\lambda n}}\iff
m^{-1-\beta/2}=\sqrt{\frac{\lambda}{n}}\iff m=(n/\lambda)^{1/(2+\beta)}.$

Plugging this in gives

$\displaystyle Q_{\mathrm{sg}}(n,\lambda)$
$\displaystyle\lesssim_{\beta,\omega}\log^{2}(n)n^{3/(4+2\beta)-1/2}\lambda^{-3/(4+2\beta)-1/2}$
$\displaystyle=\log^{2}(n)n^{\frac{1-\beta}{4+2\beta}}\lambda^{\frac{-(5+\beta)}{4+2\beta}}$
$\displaystyle=\log^{2}(n)\left(\frac{1}{n\lambda^{\frac{5+\beta}{\beta-1}}}\right)^{\frac{\beta-1}{4+2\beta}}.$

  3. 3.

For $R_{\mathrm{sg}}(n,\lambda)$, equating main terms gives

$\displaystyle
m^{\frac{1}{4}}\left\\{\frac{\lambda^{-2-2/\beta}}{n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\frac{m^{1/2-\beta/2}}{\lambda}\iff\left\\{\frac{\lambda^{2-2/\beta}}{n}\right\\}^{\frac{1}{1-2\beta}}=m.$

Using this value of $m$ gives the bound

$\displaystyle R_{\mathrm{sg}}(n,\lambda)$
$\displaystyle\lesssim_{\beta,\omega}\left\\{\frac{m^{1/2-\beta/2}}{\lambda}\right\\}$
$\displaystyle=\frac{1}{\lambda}\left\\{\frac{\lambda^{2-2/\beta}}{n}\right\\}^{\frac{1-\beta}{2-4\beta}}$
$\displaystyle=\left\\{\frac{1}{\lambda^{2+2/\beta+2/(\beta-1)}n}\right\\}^{\frac{1-\beta}{2-4\beta}}.$

##### Gaussian RKHS: Bounded data

We proceed in steps.

  1. 1.

If $\nu_{s}\leq\omega\exp(-\alpha m^{\gamma})$ then by Proposition I.2 we have
$\sigma(m)\lesssim_{\,\omega,\alpha,\gamma}m^{1/2-\gamma/2}\exp(-\alpha
m^{\gamma}/2)$, and by Proposition I.4 we have
$\mathfrak{n}(\lambda)\lesssim_{\,\omega,\alpha,\gamma}\lambda^{-1}\log(1/\lambda)^{1/\gamma}$.

  2. 2.

First we study $Q_{\mathrm{bd}}(n,\lambda)$. Plugging in our bound on
$\sigma(m)$ and then equating the main terms (ignoring constants and log
factors) gives

$\exp(-\alpha m^{\gamma}/2)=\frac{1}{\sqrt{n}}\iff
m=\left(\frac{\log(n)}{\alpha}\right)^{\frac{1}{\gamma}}.$
$\displaystyle\sigma(m)$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}m^{\frac{1-\gamma}{2}}\exp(-\alpha
m^{\gamma}/2)$
$\displaystyle=\left(\frac{\log(n)}{\alpha}\right)^{\frac{1-\gamma}{2\gamma}}\exp\left(-\alpha\frac{\log(n)}{\alpha}/2\right)$
$\displaystyle=\left(\frac{\log(n)}{\alpha}\right)^{\frac{1-\gamma}{2\gamma}}\exp\left(\log(n^{-1/2})\right)$
$\displaystyle=\left(\frac{\log(n)}{\alpha}\right)^{\frac{1-\gamma}{2\gamma}}n^{-1/2}$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}\log(n)^{\frac{1-\gamma}{2\gamma}}n^{-1/2}.$

Moreover,

$\displaystyle\frac{m^{2}\log(m^{2})}{\sqrt{n}}$
$\displaystyle=n^{-1/2}\left(\frac{\log(n)}{\alpha}\right)^{\frac{2}{\gamma}}\log\left\\{\left(\frac{\log(n)}{\alpha}\right)^{\frac{2}{\gamma}}\right\\}\lesssim_{\omega,\gamma,\alpha}n^{-1/2}\log(n)^{\frac{2}{\gamma}}\log(\log(n)).$

Therefore, since $\gamma>0$ implies
$\frac{2}{\gamma}>\frac{1-\gamma}{2\gamma}$

$Q_{\mathrm{bd}}(n,\lambda)\lesssim_{\,\omega,\alpha,\gamma}\frac{1}{\lambda\sqrt{n}}\log(n)^{\frac{2}{\gamma}}\log(\log(n)).$

  3. 3.

Next we study $R_{\mathrm{bd}}(n,\lambda)$. Plugging in our bounds and
equating main terms gives

$\displaystyle\left\\{\frac{\lambda^{-1}\log(1/\lambda)^{1/\gamma}}{\lambda^{2}n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\frac{\exp(-\alpha m^{\gamma}/2)}{\lambda}$
$\displaystyle\iff\left\\{\frac{\lambda\log(1/\lambda)^{1/\gamma}}{n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\exp(-\alpha m^{\gamma}/2)$
$\displaystyle\iff\left\\{\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1}{\gamma}}\quad$
$\displaystyle=m.$

Using this value of $m$,

$\displaystyle\frac{\sigma(m)}{\lambda}$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}\frac{1}{\lambda}m^{\frac{1-\gamma}{2}}\exp(-\alpha
m^{\gamma}/2)$
$\displaystyle=\frac{1}{\lambda}\left\\{\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1-\gamma}{2\gamma}}\exp\left(-\alpha\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]/2\right)$
$\displaystyle=\frac{1}{\lambda}\left\\{\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1-\gamma}{2\gamma}}\exp\left(-\frac{1}{4}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right)$
$\displaystyle=\frac{1}{\lambda}\left\\{\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1-\gamma}{2\gamma}}\left\\{\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}^{-\frac{1}{4}}$
$\displaystyle\lesssim_{\omega,\gamma,\alpha}\frac{1}{\lambda}\left\\{\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1-\gamma}{2\gamma}}\left\\{\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}^{-\frac{1}{4}}.$

Meanwhile

$\displaystyle\left\\{\frac{m\mathfrak{n}(\lambda)}{n\lambda^{2}}\right\\}^{\frac{1}{4}}$
$\displaystyle\lesssim_{\omega,\gamma,\alpha}\left[\frac{1}{n\lambda^{2}}\left\\{\frac{1}{2\alpha}\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1}{\gamma}}\lambda^{-1}\log(1/\lambda)^{1/\gamma}\right]^{\frac{1}{4}}$
$\displaystyle=\lesssim_{\omega,\gamma,\alpha}\left\\{\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1}{4\gamma}}n^{-1/4}\lambda^{-1}\\{\lambda\log(1/\lambda)^{1/\gamma}\\}^{1/4}.$

Therefore since $\gamma>0$ implies $\frac{1}{2\gamma}>\frac{1}{4\gamma}$ and
$\frac{1}{2\gamma}>\frac{1-\gamma}{2\gamma}$, we conclude that

$R_{\mathrm{bd}}(n,\lambda)\lesssim_{\omega,\gamma,\alpha}\left\\{\log\left[\frac{n}{\lambda\log(1/\lambda)^{1/\gamma}}\right]\right\\}^{\frac{1}{2\gamma}}\left\\{\frac{n\lambda^{3}}{\log(1/\lambda)^{1/\gamma}}\right\\}^{-\frac{1}{4}}.$

##### Gaussian RKHS: Sub-Gaussian data

We proceed in steps.

  1. 1.

If $\nu_{s}\leq\omega\exp(-\alpha m^{\gamma})$ then by Proposition I.2 we have
$\sigma(m)\lesssim_{\,\omega,\alpha,\gamma}m^{\frac{1-\gamma}{2}}\exp(-\alpha
m^{\gamma}/2)$, and by Proposition I.4 we have
$\mathfrak{n}(\lambda)\lesssim_{\,\omega,\alpha,\gamma}\lambda^{-1}\log(1/\lambda)^{1/\gamma}$.

  2. 2.

For $Q_{\mathrm{sg}}(n,\lambda)$, equating main terms gives

$\frac{\exp(-\alpha m^{\gamma}/2)}{\lambda}=\frac{1}{\sqrt{\lambda n}}\iff
m=\left\\{\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)\right\\}^{\frac{1}{\gamma}}.$

Using this value of $m$,

$\displaystyle\frac{\sigma(m)}{\lambda}$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}\lambda^{-1}m^{\frac{1-\gamma}{2}}\exp(-\alpha
m^{\gamma}/2)$
$\displaystyle=\lambda^{-1}\left\\{\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)\right\\}^{\frac{1-\gamma}{2\gamma}}\exp(-\alpha\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)/2)$
$\displaystyle=\lambda^{-1}\left\\{\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)\right\\}^{\frac{1-\gamma}{2\gamma}}\exp\left\\{\log\left(\frac{\lambda^{1/2}}{n^{1/2}}\right)\right\\}$
$\displaystyle=\left\\{\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)\right\\}^{\frac{1-\gamma}{2\gamma}}\frac{1}{\lambda^{1/2}n^{1/2}}$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}\log\left(\frac{n}{\lambda}\right)^{\frac{1-\gamma}{2\gamma}}\frac{1}{\lambda^{1/2}n^{1/2}}.$

Meanwhile

$\displaystyle\frac{m^{3/2}\log(n)^{2}}{\sqrt{n\lambda}}$
$\displaystyle=\frac{\log(n)^{2}}{\sqrt{n\lambda}}\left\\{\frac{1}{\alpha}\log\left(\frac{n}{\lambda}\right)\right\\}^{\frac{3}{2\gamma}}\lesssim_{\omega,\alpha,\gamma}\frac{\log(n)^{2}}{\sqrt{n\lambda}}\log\left(\frac{n}{\lambda}\right)^{\frac{3}{2\gamma}}.$

Since $\gamma>0$ implies $\frac{3}{2\gamma}>\frac{1-\gamma}{2\gamma}$, w
conclude that

$Q_{\mathrm{sg}}(n,\lambda)\lesssim_{\,\omega,\alpha,\gamma}\frac{\log(n)^{2}}{\sqrt{n\lambda}}\log\left(\frac{n}{\lambda}\right)^{\frac{3}{2\gamma}}.$

  3. 3.

Next we study $R_{\mathrm{sg}}(n,\lambda)$. Plugging in our bounds and
equating main terms gives

$\displaystyle\left\\{\frac{\lambda^{-2}\log(1/\lambda)^{2/\gamma}}{n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\frac{\exp(-\alpha m^{\gamma}/2)}{\lambda}$
$\displaystyle\iff\left\\{\frac{\lambda^{2}\log(1/\lambda)^{2/\gamma}}{n}\right\\}^{\frac{1}{4}}$
$\displaystyle=\exp(-\alpha m^{\gamma}/2)$
$\displaystyle\iff\left[\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}\right]^{\frac{1}{\gamma}}\quad$
$\displaystyle=m.$

Using this value of $m$,

$\displaystyle\frac{\sigma(m)}{\lambda}$
$\displaystyle\lesssim_{\omega,\gamma,\alpha}\lambda^{-1}m^{\frac{1-\gamma}{2}}\exp(-\alpha
m^{\gamma}/2)$
$\displaystyle=\lambda^{-1}\left[\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}\right]^{\frac{1-\gamma}{2\gamma}}\exp\left[-\alpha\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}/2\right]$
$\displaystyle=\lambda^{-1}\left[\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}\right]^{\frac{1-\gamma}{2\gamma}}\exp\left[\log\left\\{\frac{\lambda^{1/2}\log(1/\lambda)^{1/2\gamma}}{n^{1/4}}\right\\}\right]$
$\displaystyle=\lambda^{-1}\left[\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}\right]^{\frac{1-\gamma}{2\gamma}}\frac{\lambda^{1/2}\log(1/\lambda)^{1/2\gamma}}{n^{1/4}}$
$\displaystyle\lesssim_{\omega,\alpha,\gamma}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}^{\frac{1-\gamma}{2\gamma}}\frac{\log(1/\lambda)^{1/2\gamma}}{\lambda^{1/2}n^{1/4}}.$

Meanwhile

$\displaystyle\left\\{\frac{m\mathfrak{n}(\lambda)^{2}}{n}\right\\}^{1/4}$
$\displaystyle\lesssim_{\omega,\gamma,\alpha}\left[\frac{1}{\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}\right]^{\frac{1}{4\gamma}}n^{-1/4}\left\\{\lambda^{-1}\log(1/\lambda)^{1/\gamma}\right\\}^{1/2}$
$\displaystyle\lesssim_{\omega,\gamma,\alpha}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}^{\frac{1}{4\gamma}}n^{-1/4}\left\\{\lambda^{-1}\log(1/\lambda)^{1/\gamma}\right\\}^{1/2}.$

Since $\gamma>0$ implies $\frac{1}{2\gamma}>\frac{1}{4\gamma}$ and
$\frac{1}{2\gamma}>\frac{1-\gamma}{2\gamma}$, we conclude that

$R_{\mathrm{bd}}(n,\lambda)\lesssim_{\,\omega,\alpha,\gamma}\log\left\\{\frac{n^{1/2}}{\lambda\log(1/\lambda)^{1/\gamma}}\right\\}^{\frac{1}{2\gamma}}\frac{\log(1/\lambda)^{1/2\gamma}}{\lambda^{1/2}n^{1/4}}.$

##### Summary

Spectrum | Poly. : $\nu_{s}\leq\omega s^{-\beta}$ | Exp. : $\nu_{s}\leq\omega\exp(-\alpha s^{\gamma})$
---|---|---
Data | Bounded | sub-Gaussian | Bounded | sub-Gaussian
$Q_{\bullet}$ | $\lambda^{-1}n^{\frac{1-\beta}{6+2\beta}}$ | $\lambda^{\frac{-(5+\beta)}{4+2\beta}}n^{\frac{1-\beta}{4+2\beta}}$ | $\lambda^{-1}n^{-\frac{1}{2}}$ | $(\lambda n)^{-\frac{1}{2}}$
$R_{\bullet}$ | $\left({\lambda^{3+\frac{1}{\beta}+\frac{2}{\beta-1}}n}\right)^{\frac{1-\beta}{4\beta-2}}$ | $\left({\lambda^{2+\frac{2}{\beta}+\frac{2}{\beta-1}}n}\right)^{\frac{1-\beta}{4\beta-2}}$ | $\lambda^{-3/4}n^{-1/4}$ | $\lambda^{-1/2}n^{-1/4}$
Table 11: Summary of results under different assumptions. The initial two rows
present rates (suppressing log factors) for the quantities $Q_{\mathrm{bd}}$,
$Q_{\mathrm{sg}}$, $R_{\mathrm{bd}}$, and $R_{\mathrm{sg}}$.

These values correspond to $(Q,R)$ in Table 7. We now derive the remaining
entries in that table. We proceed in steps.

  1. 1.

$L$. Lemma G.13 implies $L\asymp\mathfrak{n}(\lambda)^{1/2}-\lambda^{-1/2}$.
Note that
$\mathfrak{n}(\lambda)=\sigma^{2}\\{(T+\lambda)^{-2}T,0\\}=\psi(0,2)$, so we
appeal to Proposition I.5. For polynomial decay, we show
$\psi(0,2)\gtrsim\lambda^{-1-1/\beta}$. Hence, for $\beta>1$,

$L\asymp\mathfrak{n}(\lambda)^{1/2}-\lambda^{-1/2}\gtrsim\lambda^{-\frac{1}{2}-\frac{1}{2\beta}}-\lambda^{-1/2}=\lambda^{-1/2}(\lambda^{-\frac{1}{2\beta}}-1)\gtrsim\lambda^{-\frac{1}{2}-\frac{1}{2\beta}}.$

For exponential decay, we show $\psi(0,2)\gtrsim\lambda^{-1}$, ignoring log
factors. Hence

$L\asymp\mathfrak{n}(\lambda)^{1/2}-\lambda^{-1/2}\gtrsim\lambda^{-\frac{1}{2}}-\lambda^{-\frac{1}{2}}\asymp\lambda^{-\frac{1}{2}}.$

  2. 2.

$B\ll L$. For polynomial decay
$n\lambda^{r-1}\ll\lambda^{-1-1/\beta}\iff\lambda^{r+1/\beta}\ll n^{-1}.$ For
exponential decay $n\lambda^{r-1}\ll\lambda^{-1}\iff\lambda^{r}\ll n^{-1}.$

  3. 3.

$Q+R\ll L$.

    1. (a)

Polynomial decay, bounded data. We have

$\displaystyle Q\ll
L\iff\lambda^{-2}n^{\frac{1-\beta}{3+\beta}}\ll\lambda^{-1-1/\beta}\iff
n^{\frac{1-\beta}{3+\beta}}\ll\lambda^{1-1/\beta}$ $\displaystyle\iff
n^{\frac{1-\beta}{3+\beta}}\ll\lambda^{(\beta-1)/\beta}\iff
n^{\frac{1}{3+\beta}}\gg\lambda^{-1/\beta}\iff
n^{\frac{-\beta}{3+\beta}}\ll\lambda.$

Then

$\displaystyle R\ll
L\iff\\{\lambda^{3+\frac{1}{\beta}+\frac{2}{\beta-1}}n\\}^{\frac{1-\beta}{2\beta-1}}$
$\displaystyle\ll\lambda^{-1-1/\beta}$
$\displaystyle\iff\\{\lambda^{3+\frac{1}{\beta}+\frac{2}{\beta-1}}n\\}^{\frac{1-\beta}{2\beta-1}}$
$\displaystyle\ll\lambda^{-(\beta+1)/\beta}$
$\displaystyle\iff\lambda^{3+\frac{1}{\beta}+\frac{2}{\beta-1}}n$
$\displaystyle\gg\lambda^{-\frac{(\beta+1)(2\beta-1)}{\beta(1-\beta)}}$
$\displaystyle\iff\lambda^{3+\frac{1}{\beta}+\frac{2}{\beta-1}}n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)}{\beta(\beta-1)}}$
$\displaystyle\iff\lambda^{\frac{3\beta(\beta-1)+(\beta-1)+2\beta}{\beta(\beta-1)}}n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)}{\beta(\beta-1)}}$
$\displaystyle\iff n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)-[3\beta(\beta-1)+(\beta-1)+2\beta]}{\beta(\beta-1)}}$
To simplify the numerator, note that
$\displaystyle(\beta+1)(2\beta-1)-[3\beta(\beta-1)+(\beta-1)+2\beta]$
$\displaystyle=2\beta^{2}+\beta-1-[3\beta^{2}-3\beta+\beta-1+2\beta]$
$\displaystyle=-\beta^{2}+\beta=\beta(1-\beta).$

Therefore the above simplifies to $n\gg\lambda^{-1}\iff\lambda\gg 1/n$.

Since $1>\beta/(3+\beta)$, the $Q$ condition binds. Combining $Q+R\ll L$ with
$B\ll L$,

$\displaystyle n^{\frac{-\beta}{3+\beta}}\ll\lambda\ll
n^{-\beta/(r\beta+1)}\iff 3+\beta\leq r\beta+1\iff r\geq 1+2/\beta.$

    2. (b)

Polynomial decay, sub-Gaussian data. We have

$\displaystyle Q\ll
L\iff\lambda^{-\frac{5+\beta}{2+\beta}}n^{\frac{1-\beta}{2+\beta}}$
$\displaystyle\ll\lambda^{-1-1/\beta}$
$\displaystyle\iff\lambda^{-\frac{3}{2+\beta}}n^{\frac{1-\beta}{2+\beta}}$
$\displaystyle\ll\lambda^{-1/\beta}$
$\displaystyle\iff\lambda^{-3}n^{1-\beta}$
$\displaystyle\ll\lambda^{-(2+\beta)/\beta}$ $\displaystyle\iff
n^{-1(\beta-1)}$ $\displaystyle\ll\lambda^{(2\beta-2)/\beta}$
$\displaystyle\iff\lambda$ $\displaystyle\gg n^{-\beta/2}.$

Then

$\displaystyle R\ll
L\iff\\{\lambda^{2+\frac{2}{\beta}+\frac{2}{\beta-1}}n\\}^{\frac{1-\beta}{2\beta-1}}$
$\displaystyle\ll\lambda^{-1-1/\beta}$
$\displaystyle\iff\\{\lambda^{2+\frac{2}{\beta}+\frac{2}{\beta-1}}n\\}^{\frac{1-\beta}{2\beta-1}}$
$\displaystyle\ll\lambda^{-(\beta+1)/\beta}$
$\displaystyle\iff\lambda^{2+\frac{2}{\beta}+\frac{2}{\beta-1}}n$
$\displaystyle\gg\lambda^{-\frac{(\beta+1)(2\beta-1)}{\beta(1-\beta)}}$
$\displaystyle\iff\lambda^{2+\frac{2}{\beta}+\frac{2}{\beta-1}}n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)}{\beta(\beta-1)}}$
$\displaystyle\iff\lambda^{\frac{2\beta(\beta-1)+2(\beta-1)+2\beta}{\beta(\beta-1)}}n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)}{\beta(\beta-1)}}$
$\displaystyle\iff n$
$\displaystyle\gg\lambda^{\frac{(\beta+1)(2\beta-1)-[2\beta(\beta-1)+2(\beta-1)+2\beta]}{\beta(\beta-1)}}$
To simplify the numerator, note that
$\displaystyle(\beta+1)(2\beta-1)-[2\beta(\beta-1)+2(\beta-1)+2\beta]$
$\displaystyle=2\beta^{2}+\beta-1-[2\beta^{2}-2\beta+2\beta-2+2\beta]$
$\displaystyle=1-\beta.$

Therefore the above simplifies to $n\gg\lambda^{-1/\beta}\iff\lambda\gg
n^{-\beta}$.

Since $\beta>\beta/2$, the $Q$ condition binds. Combining $Q+R\ll L$ with
$B\ll L$,

$\displaystyle n^{\frac{-\beta}{2}}\ll\lambda\ll
n^{-\beta/(r\beta+1)}\iff\frac{1}{2}\geq\frac{1}{r\beta+1}\iff r\geq 1/\beta.$

    3. (c)

Exponential decay, bounded data. The two conditions are equivalent:

$Q\ll L\iff\lambda^{-2}n^{-1}\ll\lambda^{-1}\iff\lambda\gg n^{-1};$ $R\ll
L\iff\lambda^{-\frac{3}{2}}n^{-\frac{1}{2}}\ll\lambda^{-1}\iff\lambda^{1/2}\gg
n^{-1/2}.$

Combining $Q+R\ll L$ with $B\ll L$,

$\displaystyle n^{-1}\ll\lambda\ll n^{-1/r}\iff 1\geq\frac{1}{r}\iff r\geq 1.$

    4. (d)

Exponential decay, sub-Gaussian data. The two conditions are equivalent:

$Q\ll L\iff\lambda^{-1}n^{-1}\ll\lambda^{-1}\iff 1\gg n^{-1};$ $R\ll
L\iff\lambda^{-1}n^{-\frac{1}{2}}\ll\lambda^{-1}\iff 1\gg n^{-1/2}.$

Combining $Q+R\ll L$ with $B\ll L$, $0\ll\lambda\ll n^{-1/r}.$

###  Appendix H Concentration inequalities for Bahadur representation
(Sections B and E)

####  H.1 Concentration

We quote a version of Bernstein’s inequality for random variables in a Hilbert
space.

######  Lemma H.1 (Theorem 3.3.4 of Yurinsky, (1995)).

Let $\xi_{1},\xi_{2},\ldots$ be an independent sequence of random variables in
a Hilbert space that satisfy $\mathbb{E}[\xi_{i}]=0$. If, for some $B,A>0$ and
all $\ell\geq 2$ it holds that
$\sum_{i=1}^{n}\mathbb{E}\|\xi_{i}\|^{\ell}\leq\frac{\ell!}{2}B^{2}A^{\ell-2},$
then for $\delta>0$

$\mathbb{P}\left(\max_{m\in[n]}\left\|\sum_{i=1}^{m}\xi_{i}\right\|\geq\delta
B\right)\leq 2\exp\left\\{\frac{-\delta^{2}/2}{1+\delta A/B}\right\\}.$

A useful corollary, frequently used in the kernel ridge regression literature
(Caponnetto and De Vito,, 2007), is as follows.

######  Lemma H.2.

Suppose that $\xi_{i}$ are i.i.d. random elements of a Hilbert space, which
satisfy, for all $\ell\geq 2$
$\mathbb{E}\left\lVert\xi_{i}-\mathbb{E}\xi_{i}\right\rVert^{\ell}\leq\frac{1}{2}\ell!B^{2}(A/2)^{\ell-2}.$
Then for any $0<\eta<1$ it holds with probability at least $1-\eta$ that

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}\xi_{i}-\mathbb{E}[\xi_{i}]\right\rVert\leq
2\left(\sqrt{\frac{B^{2}\log(2/\eta)}{n}}\vee\frac{A\log(2/\eta)}{n}\right)\leq
2\log(2/\eta)\left\\{\frac{A}{n}\vee\sqrt{\frac{B^{2}}{n}}\right\\}.$

In particular, this holds if
$\mathbb{E}(\left\lVert\xi_{i}\right\rVert^{2})\leq B^{2}$ and
$\left\lVert\xi_{i}\right\rVert\leq A/2$ almost surely.

######  Remark H.3.

Note that the result of Lemma H.2 for bounded random vectors may be recovered
from Talagrand’s concentration inequality for empirical processes (see
Massart,, 2000), by considering the special case where the sample paths are
linear and the parameter space is an ellipsoid.

####  H.2 Bounds for sums

######  Lemma H.4.

With probability $1-\eta$,

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}T_{\lambda}^{-1}\varepsilon_{i}k_{X_{i}}\right\rVert\leq
2\bar{\sigma}\ln(2/\eta)\left\\{\sqrt{\frac{\mathfrak{n}(\lambda)}{n}}\vee\frac{2\kappa}{n\lambda}\right\\}.$

###### Proof.

Note that
$\mathbb{E}[T_{\lambda}^{-1}\varepsilon_{i}k_{X_{i}}]=\mathbb{E}[T_{\lambda}^{-1}k_{X_{i}}\mathbb{E}(\varepsilon_{i}|X_{i})]=0$.
It therefore suffices to show $\left\lVert
T_{\lambda}^{-1}\varepsilon_{i}k_{X_{i}}\right\rVert\leq\left\lVert
T_{\lambda}^{-1}\right\rVert_{op}\left\lVert\varepsilon_{i}k_{X_{i}}\right\rVert\leq\frac{\kappa\bar{\sigma}}{\lambda}$
and

$\displaystyle\mathbb{E}\left\lVert
T_{\lambda}^{-1}\varepsilon_{i}k_{X_{i}}\right\rVert^{2}$
$\displaystyle\leq\bar{\sigma}^{2}\mathbb{E}\left\lVert
T_{\lambda}^{-1}k_{X_{i}}\right\rVert^{2}=\bar{\sigma}^{2}\sum_{s=1}^{\infty}\frac{\mathbb{E}\left\langle
k_{X_{i}},\,e_{s}\right\rangle^{2}}{(\nu_{s}+\lambda)^{2}}=\bar{\sigma}^{2}\sum_{s=1}^{\infty}\frac{\nu_{s}}{(\nu_{s}+\lambda)^{2}}=\bar{\sigma}^{2}\mathfrak{n}(\lambda).$

Plugging these estimates into Lemma H.2 gives the result. ∎

######  Lemma H.5.

With probability $1-\eta$,

$\left\lVert\frac{1}{n}\sum_{i=1}^{n}T_{\lambda}^{-1}(T_{i}-T)\right\rVert_{\mathrm{HS}}\leq
2\kappa\ln(2/\eta)\left\\{\sqrt{\frac{\mathfrak{n}(\lambda)}{n}}\vee\frac{2\kappa}{n\lambda}\right\\}.$

###### Proof.

Note that
$\mathbb{E}[T_{\lambda}^{-1}(T_{i}-T)]=T_{\lambda}^{-1}\mathbb{E}[T_{i}-T]=0$.
Also,

$\left\lVert
T_{\lambda}^{-1}(T_{i}-T)\right\rVert_{\mathrm{HS}}\leq\left\lVert
T_{\lambda}^{-1}\right\rVert_{op}\left\lVert
T_{i}-T\right\rVert_{\mathrm{HS}}\leq\frac{2\kappa^{2}}{\lambda}.$

Finally, using the fact that $T$, $T_{i}$ and $T_{\lambda}^{-1}$ are self-
adjoint,

$\displaystyle\mathbb{E}\left\lVert
T_{\lambda}^{-1}(T_{i}-T)\right\rVert^{2}_{\mathrm{HS}}$
$\displaystyle=\mathbb{E}\operatorname{tr}[T_{\lambda}^{-1}(T_{i}-T)^{2}T_{\lambda}^{-1}]$
$\displaystyle=\operatorname{tr}\mathbb{E}[T_{\lambda}^{-1}(T_{i}-T)^{2}T_{\lambda}^{-1}]$
$\displaystyle=\operatorname{tr}\\{\mathbb{E}[T_{\lambda}^{-1}T_{i}^{2}T_{\lambda}^{-1}]-T_{\lambda}^{-1}TT_{\lambda}^{-1}\\}.$
Since both operators are positive definite, this is
$\displaystyle\leq\operatorname{tr}\\{\mathbb{E}[T_{\lambda}^{-1}T_{i}^{2}T_{\lambda}^{-1}].$
Since $T_{i}=k_{X_{i}}\otimes k_{X_{i}}^{*}$,
$\|T_{i}\|_{op}\leq\|T_{i}\|_{\mathrm{HS}}=\left\lVert
k_{X_{i}}\right\rVert^{2}\leq\kappa^{2}$, and hence
$\displaystyle\leq\kappa^{2}\mathbb{E}[|\operatorname{tr}\\{T_{\lambda}^{-1}T_{i}T_{\lambda}^{-1}\\}|].$
Since the trace is almost surely positive, this is
$\displaystyle=\kappa^{2}\mathbb{E}[\operatorname{tr}\\{T_{\lambda}^{-1}T_{i}T_{\lambda}^{-1}\\}]$
$\displaystyle=\kappa^{2}\operatorname{tr}[T_{\lambda}^{-1}TT_{\lambda}^{-1}].$
Finally, since $T$ commutes with $T_{\lambda}^{-1}$ by construction, this is
$\displaystyle=\kappa^{2}\operatorname{tr}[T_{\lambda}^{-2}T]=\kappa^{2}\mathfrak{n}(\lambda).$

Plugging these estimates into Lemma H.2 gives the result. ∎

###  Appendix I Spectral bounds for Gaussian couplings (Section C)

We characterize the behavior of $\sigma^{2}(m)=\sum_{s>m}\nu_{s}$ and
$\mathfrak{n}(\lambda)=\operatorname{tr}(T_{\lambda}^{-2}T)$ under various
regimes for the spectrum of $\Sigma$. Such regimes can be deduced directly
from regularity of the kernel function $k$ (Belkin,, 2018).

####  I.1 Spectral decay

We need the following technical lemma on the size of the incomplete Gamma
function.

######  Lemma I.1 (Natalini and Palumbo, 2000, Sec 3.1 and eq. 3.5).

Let the (upper) incomplete gamma function $\Gamma$ be given by
$\Gamma(z,x)\coloneqq\int_{x}^{\infty}u^{z-1}e^{-u}\,du.$ For $z>1$ and $x\geq
0$ we have

$x^{z-1}e^{-x}<\Gamma(z,x)\leq\frac{x^{z}e^{-x}}{x-z}.$

######  Proposition I.2.

Suppose $\nu_{s}\leq\bar{\nu}(s):\mathbb{R}\to\mathbb{R}$ for some non-
increasing positive function $\bar{\nu}(s)$. Then, it holds that
$\sigma^{2}(m)=\sum_{s=m+1}^{\infty}\nu_{s}\leq\int_{m}^{\infty}\bar{\nu}(s)\,ds.$
In particular, if $\nu_{s}\leq\omega s^{-\beta}$ for $\beta>1$, then we have
$\sigma^{2}(m)\leq\frac{\omega m^{1-\beta}}{\beta-1}.$ Similarly, if
$\nu_{s}\leq\omega\exp(-\alpha s^{\gamma})$ for $\alpha,\omega,\gamma>0$, then
we have $\sigma^{2}(m)\leq C(\gamma,\alpha)\omega m^{1-\gamma}\exp(-\alpha
m^{\gamma}),$ for a constant $C(\gamma,\alpha)$ which depends only on $\alpha$
and $\gamma$ (and not on $m$).

###### Proof.

We upper bound
$\sigma^{2}(m)=\sum_{s=m+1}^{\infty}\nu_{s}\leq\int_{m}^{\infty}\bar{\nu}(s)\,ds,$
where $\bar{\nu}:\mathbb{R}\to\mathbb{R}$ is any non-increasing function with
$\bar{\nu}(s)\geq\nu_{s}$. The first bound follows from taking
$\bar{\nu}(s)=\omega s^{-\beta}$ and computing the resulting integral exactly.
For the second bound, we take $\bar{\nu}(s)=\omega\exp(-\alpha s^{\gamma})$
and obtain $\frac{\sigma^{2}(m)}{\omega}\leq\int_{m}^{\infty}\exp(-\alpha
s^{\gamma})\,ds.$ To bound the right hand side, we proceed in steps.

  1. 1.

Making the substitution $u=\alpha s^{\gamma}$ gives us

$\int_{m}^{\infty}\exp(-\alpha
s^{\gamma})\,ds=\gamma^{-1}\alpha^{\frac{-1}{\gamma}}\int_{\alpha
m^{\gamma}}^{\infty}\exp(-u)u^{\nicefrac{{(1-\gamma)}}{{\gamma}}}\,du.$

  2. 2.

We have $\int_{\alpha
m^{\gamma}}^{\infty}\exp(-u)u^{\nicefrac{{(1-\gamma)}}{{\gamma}}}\,du=\Gamma(1/\gamma,\alpha
m^{\gamma})$ where $\Gamma(z,x)$ is the incomplete Gamma function (cf. Lemma
I.1). By Lemma I.1, $\Gamma(z,x)\leq\frac{x^{z}e^{-x}}{x-z}$, so

$\displaystyle\frac{\sigma^{2}(m)}{\omega}\leq\gamma^{-1}\alpha^{\frac{-1}{\gamma}}\Gamma\Big{(}1/\gamma,\alpha
m^{\gamma}\Big{)}\leq\gamma^{-1}\alpha^{\frac{-1}{\gamma}}\frac{(\alpha
m^{\gamma})^{1/\gamma}e^{-\alpha m^{\gamma}}}{\alpha
m^{\gamma}-1/\gamma}=\frac{m\exp(-\alpha m^{\gamma})}{\alpha\gamma
m^{\gamma}-1}.$

  3. 3.

Finally we absorb constants. When $m\geq\\{2/(\alpha\gamma)\\}^{1/\gamma}$, we
have that $\alpha\gamma m^{\gamma}\geq 2$ and hence $\alpha\gamma
m^{\gamma}-1\geq\alpha\gamma m^{\gamma}/2$. Thus, the final expression is at
most $(2/\alpha\gamma)m^{1-\gamma}\exp(-\alpha m^{\gamma})$. For
$m<\\{2/(\alpha\gamma)\\}^{1/\gamma}$, we decompose the sum as

$\sum_{s=m+1}^{\lfloor\\{2/(\alpha\gamma)\\}^{1/\gamma}\rfloor}\nu_{s}+\sum_{s=\lceil\\{2/(\alpha\gamma)\\}^{1/\gamma}\rceil}^{\infty}\nu_{s}.$

The latter sum is bounded by the previous case. Focusing on the former sum,

$\sum_{s=m+1}^{\\{2/(\alpha\gamma)\\}^{1/\gamma}}\nu_{s}\leq\sum_{s=1}^{\\{2/(\alpha\gamma)\\}^{1/\gamma}}\nu_{s}\leq\\{2/(\alpha\gamma)\\}^{1/\gamma}\nu_{1}\leq\\{2/(\alpha\gamma)\\}^{1/\gamma}\cdot\omega\exp(-\alpha)$

since $\nu_{1}\leq\bar{\nu}(1)\leq\omega\exp(-\alpha
1^{\gamma})=\omega\exp(-\alpha).$ These terms may be absorbed into a constant
depending only on $\omega,\alpha,\gamma$, and which is linear in $\omega$.

∎

####  I.2 Complexity measures

Recall the definition of the ellipse $\mathfrak{E}=\Sigma^{\frac{1}{2}}B$,
where $B$ is the unit ball in $L^{2}(\mathbb{P})$. We use the results of Wei
et al., (2020) to briefly sketch the claim that, under suitable regularity
conditions, the local width $\sigma(\Sigma,m)$ is roughly comparable to the
local Gaussian complexity of $\mathfrak{E}$ at scale
$\delta=\mathrm{ent}_{m}(\mathfrak{E})$, which we denote by
$\mathcal{G}(\mathfrak{E}\cap\delta B)$.

First, some technicalities. For $S_{m}\subset\mathbb{R}^{m}$, the Gaussian
width and Gaussian complexity are given by $\mathbb{E}\sup_{t\in
S_{m}}\left\langle g,\,s\right\rangle$ and $\mathbb{E}\sup_{t\in
S_{m}}|\left\langle g,\,s\right\rangle|,$ respectively, where $g$ is an
isotropic Gaussian vector. These quantities immediately generalize to compact
subsets of a separable Hilbert space by finite-dimensional approximation.
Moreover, when $S_{m}$ contains the origin (as in our setting) they are
equivalent up to a constant (Vershynin,, 2018, Chapter 7). Thus, as is
standard, we can use the results of Wei et al., (2020), who study the Gaussian
width of finite-dimensional sets, to characterize the Gaussian complexity in
our setting.

######  Lemma I.3.

Suppose either

  1. 1.

$\nu_{s}(\Sigma)\asymp s^{-\beta}$ for $\beta>1$, or

  2. 2.

$\nu_{s}(\Sigma)\asymp\exp(-\alpha s^{\gamma})$ for $\alpha>0$ and
$\gamma\in(0,1)$.

Then, for sufficiently small $\delta=\mathrm{ent}_{m}(\mathfrak{E})$, we have
$\sigma(\Sigma,m)\lesssim\mathcal{G}(\mathfrak{E}\cap\delta B)$.

###### Proof.

Both cases were covered by Wei et al., (2020, Example 4), and the subsequent
discussion in Section 4 of that paper.

In particular, it was shown that given a scale parameter $\delta$, one can
compute the “critical dimension” $m^{*}$ as the smallest $m$ such that
$\sqrt{\nu_{m}(\Sigma)}\leq 9\delta/10$. Then, according to regularity
conditions which were checked in the aforementioned Example 4, one has by Wei
et al., (2020, Theorem 2) that for small enough $\delta$,
$\delta\sqrt{m^{*}}\lesssim\mathcal{G}(\mathfrak{E}\cap\delta B).$ It then
follows from our bounds in Proposition I.2 above that

$\delta\sqrt{m^{*}}\gtrsim\sqrt{m^{*}\nu_{m^{*}}(\Sigma)}\gtrsim\sigma(\Sigma,m^{*})$

in both of the above examples.

Next, Wei et al., (2020, Corollary 2) implies (after inverting the entropy
function) that in the same setting

$\delta\lesssim\mathrm{ent}_{m^{*}}(\mathfrak{E}\cap\delta
B)\leq\mathrm{ent}_{m^{*}}(\mathfrak{E})=\delta^{\prime}.$

Our sketch is then complete by monotonicity of $\mathcal{G}$ since

$\sigma(\Sigma,m^{*})\lesssim\mathcal{G}(\mathfrak{E}\cap\delta
B)\leq\mathcal{G}(\mathfrak{E}\cap\delta^{\prime}B).$

∎

####  I.3 Effective dimension

In this subsection, we will derive bounds on the quantities

$\psi(m,c)=\sum_{s=m+1}^{\infty}\frac{\nu_{s}}{(\nu_{s}+\lambda)^{c}},$

where $c\geq 1$, which are crucial for our analysis. Such quantities arise
frequently in studies of ridge regression; see, for example, the “effective
dimension” appearing in Caponnetto and De Vito, (2007). In particular note
that according to our definition, $\mathfrak{n}(\lambda)=\psi(0,2)$. We
provide matching upper and lower bounds.

######  Proposition I.4 (Upper bound on effective dimension).

Suppose $\nu_{s}\leq\bar{\nu}(s):\mathbb{R}\to\mathbb{R}$ for some non-
increasing positive function $\bar{\nu}(s)$, and let $c\geq 1$ be given. Then

$\psi(m,c)\leq\lambda^{1-c}\inf_{s\geq
m}\left\\{(s-m+1)+\frac{1}{\lambda}\int_{s}^{\infty}\bar{\nu}(t)\,dt\right\\}.$

In particular, if $\nu_{s}\leq\omega s^{-\beta}$ for some $\omega>0$ and
$\beta>1$, and if $\lambda\leq\omega$,

$\psi(m,c)\leq\frac{\omega(2\beta-1)}{\beta-1}\left(\frac{1}{\lambda^{c+1/\beta-1}}\wedge\frac{m^{1-\beta}}{\lambda^{c}}\right).$

If $\nu_{s}\leq\omega e^{-\alpha s^{\gamma}}$ for some
$\alpha,\omega,\gamma>0$, and if $\lambda\leq\omega/e^{\alpha}$, then

$\psi(m,c)\leq
C(\alpha,\omega,\gamma)\left\\{\frac{1}{\lambda^{c-1}}\left(\frac{\log(\omega/\lambda)}{\alpha}\right)^{1/\gamma}\wedge\frac{m^{1-\gamma}\exp(-\alpha
m^{\gamma})}{\lambda^{c}}\right\\}$

for some constant $C(\alpha,\omega,\gamma)$ which depends only on $\alpha$,
$\omega$, and $\gamma$.

###### Proof of Proposition I.4.

We proceed in steps.

  1. 1.

First we note

$\frac{\nu_{s}}{(\nu_{s}+\lambda)^{c}}\leq\frac{\nu_{s}}{\lambda^{c}},\quad\frac{\nu_{s}}{(\nu_{s}+\lambda)^{c}}\leq\lambda^{1-c}.$

The former holds since $\nu_{s}\geq 0$. The latter follows from maximizing the
function $f(u)=\frac{u}{(u+\lambda)^{c}}$ at $u=\lambda/(c-1)$.

  2. 2.

Combining the two, we have for any $k\geq m$ that

$\displaystyle\psi(m,c)$
$\displaystyle=\sum_{s=m+1}^{\infty}\frac{\nu_{s}}{(\nu_{s}+\lambda)^{c}}$
$\displaystyle\leq\sum_{s=m+1}^{k}\lambda^{1-c}+\sum_{s=k+1}^{\infty}\frac{\nu_{s}}{\lambda^{c}}$
$\displaystyle\leq\lambda^{1-c}\left\\{(k-m)+\frac{1}{\lambda}\int_{k}^{\infty}\bar{\nu}(t)\,dt\right\\}.$

Since $k$ was arbitrary, we can further deduce that

$\displaystyle\psi(m,c)$ $\displaystyle\leq\lambda^{1-c}\inf_{k\geq
m}\left\\{(k-m)+\frac{1}{\lambda}\int_{k}^{\infty}\bar{\nu}(t)\,dt\right\\}$
$\displaystyle=\lambda^{1-c}\inf_{s\geq m}\left\\{(\lceil
s\rceil-m)+\frac{1}{\lambda}\int_{\lceil
s\rceil}^{\infty}\bar{\nu}(t)\,dt\right\\}$
$\displaystyle\leq\lambda^{1-c}\inf_{s\geq m}\left\\{(\lceil
s\rceil-m)+\frac{1}{\lambda}\int_{s}^{\infty}\bar{\nu}(t)\,dt\right\\},$

where the latter infimum is over real numbers $s$.

  3. 3.

Optimizing the bounds. In the infimum, consider $s=m$. Then

$\psi(m,c)\leq\lambda^{-c}\int_{m}^{\infty}\bar{\nu}(t)\,dt.$

Alternatively, consider the choice $s^{*}=\bar{\nu}^{-1}(\lambda)\vee m$. Then

$\psi(m,c)\leq\lambda^{1-c}\left\\{1+s^{*}-m+\frac{1}{\lambda}\int_{s^{*}}^{\infty}\bar{\nu}(t)\,dt\right\\}.$

In particular, choosing $m=0$ and $s^{*}=\bar{\nu}^{-1}(\lambda)$, we see

$\psi(m,c)\leq\psi(0,c)\leq\lambda^{1-c}\left\\{1+\bar{\nu}^{-1}(\lambda)+\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt\right\\}.$

Combining both bounds,

$\psi(m,c)\leq\lambda^{1-c}\left\\{1+\bar{\nu}^{-1}(\lambda)+\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt\right\\}\wedge\frac{1}{\lambda^{c}}\int_{m}^{\infty}\bar{\nu}(t)\,dt.$

  4. 4.

Polynomial decay. Now, if $\bar{\nu}(s)=\omega s^{-\beta}$ then we have
$\bar{\nu}^{-1}(\lambda)=(\omega/\lambda)^{1/\beta}$, and as argued in
Proposition I.2, $\int_{s}^{\infty}\bar{\nu}(t)\,dt=\frac{\omega
s^{1-\beta}}{\beta-1}.$ Plugging this into the first term in the optimized
bound,

$\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt=\frac{1}{\lambda}\frac{\omega\\{(\omega/\lambda)^{1/\beta}\\}^{1-\beta}}{\beta-1}=\lambda^{-1-(1-\beta)/\beta}\omega^{1+(1-\beta)/\beta}\frac{1}{\beta-1}=\lambda^{-1/\beta}\cdot\omega^{1/\beta}\cdot(\beta-1)^{-1}$

so that, when $\omega\geq\lambda$,

$\displaystyle\lambda^{1-c}\left\\{1+\bar{\nu}^{-1}(\lambda)+\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt\right\\}$
$\displaystyle=\lambda^{1-c}\left\\{1+(\omega/\lambda)^{1/\beta}+\lambda^{-1/\beta}\cdot\omega^{1/\beta}\cdot(\beta-1)^{-1}\right\\}$
$\displaystyle\leq\lambda^{1-c}\left\\{2(\omega/\lambda)^{1/\beta}+\lambda^{-1/\beta}\cdot\omega^{1/\beta}\cdot(\beta-1)^{-1}\right\\}$
$\displaystyle=\left(2\omega^{1/\beta}+\frac{\omega^{1/\beta}}{{\beta-1}}\right)\lambda^{1-c-1/\beta}$
$\displaystyle=\frac{2\beta-1}{\beta-1}\omega^{1/\beta}\lambda^{1-c-1/\beta}.$

Therefore the overall bound is

$\frac{2\beta-1}{\beta-1}\omega^{1/\beta}\lambda^{1-c-1/\beta}\wedge\frac{\omega
m^{1-\beta}}{\lambda^{c}(\beta-1)}\leq\frac{\omega(2\beta-1)}{\beta-1}\left(\frac{1}{\lambda^{c+1/\beta-1}}\wedge\frac{m^{1-\beta}}{\lambda^{c}}\right).$

  5. 5.

Exponential decay. If $\bar{\nu}(t)\leq\omega\exp(-\alpha t^{\gamma})$ then we
have $\bar{\nu}^{-1}(\lambda)=\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}$
and, as argued in Proposition I.2, $\int_{s}^{\infty}\bar{\nu}(t)\,dt\leq
C\omega s^{1-\gamma}\exp(-\alpha s^{\gamma}).$ Plugging this into the first
term in the optimized bound,

$\displaystyle\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt$
$\displaystyle=\frac{1}{\lambda}C\omega[\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}]^{1-\gamma}\cdot\exp(-\alpha[\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}]^{\gamma})$
$\displaystyle=\frac{1}{\lambda}C\omega\\{\log(\omega/\lambda)/\alpha\\}^{(1-\gamma)/\gamma}\cdot\exp(-\alpha\\{\log(\omega/\lambda)/\alpha\\})$
$\displaystyle=\frac{1}{\lambda}C\omega\\{\log(\omega/\lambda)/\alpha\\}^{(1-\gamma)/\gamma}\cdot\frac{\lambda}{\omega}$
$\displaystyle=C\\{\log(\omega/\lambda)/\alpha\\}^{(1-\gamma)/\gamma}$

so that, when $\omega/e^{\alpha}\geq\lambda$,

$\displaystyle\lambda^{1-c}\left\\{1+\bar{\nu}^{-1}(\lambda)+\frac{1}{\lambda}\int_{\bar{\nu}^{-1}(\lambda)}^{\infty}\bar{\nu}(t)\,dt\right\\}$
$\displaystyle=\lambda^{1-c}\left[1+\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}+C\\{\log(\omega/\lambda)/\alpha\\}^{(1-\gamma)/\gamma}\right]$
$\displaystyle\leq\lambda^{1-c}\left[2\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}+C\\{\log(\omega/\lambda)/\alpha\\}^{(1-\gamma)/\gamma}\right]$
$\displaystyle\leq
C^{\prime}\lambda^{1-c}\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}$

since $\gamma>0$ implies $1/\gamma>(1-\gamma)/\gamma$. Therefore the overall
bound is

$\displaystyle
C^{\prime}\lambda^{1-c}\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}\wedge\frac{1}{\lambda^{c}}C\omega
m^{1-\gamma}\exp(-\alpha m^{\gamma})$ $\displaystyle\leq
C^{\prime}\omega\left(\frac{\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}}{\lambda^{c-1}}\wedge\frac{m^{1-\gamma}\exp(-\alpha
m^{\gamma})}{\lambda^{c}}\right).$

∎

######  Proposition I.5 (Lower bound on effective dimension).

Suppose $\nu_{s}\geq\underline{\nu}(s):\mathbb{R}\to\mathbb{R}$ for some non-
increasing positive function $\underline{\nu}(s)$. Then, if $s^{*}$ is the
smallest positive integer with $\underline{\nu}(s^{*})\leq\lambda$,

$\psi(m,2)\geq\int_{s^{*}\vee(m+1)}^{\infty}\frac{\underline{\nu}(s)}{(\underline{\nu}(s)+\lambda)^{2}}\,ds\\\
\geq\frac{1}{4\lambda^{2}}\int_{s^{*}\vee(m+1)}^{\infty}\underline{\nu}(s)\,ds.$

Moreover, if we have $\underline{\nu}(s)=\omega s^{-\beta}$ for $\beta>1$
(polynomial decay), then, whenever $\lambda\leq\omega$,

$\psi(0,2)\geq\frac{1}{c_{\beta}}\left(\frac{\omega^{1/\beta}}{\lambda^{1+1/\beta}}\right).$

If $\underline{\nu}(s)=\omega\exp(-\alpha s^{\gamma})$ for $\gamma<1$
(exponential decay), then, whenever $\lambda\leq\omega/e^{\alpha}$,

$\psi(0,2)\geq\frac{1}{c_{\alpha,\gamma}}\left(\frac{\log(\omega/\lambda)^{(1-\gamma)/\gamma}}{\lambda}\right).$

###### Proof.

We proceed in steps.

  1. 1.

Note that the function $t\mapsto(t+\lambda)^{-2}t$ is strictly increasing for
all $t<\lambda$. Thus, for each integer $s$ such that
$\underline{\nu}(s)\leq\lambda$ we have

$\frac{\nu_{s}}{(\nu_{s}+\lambda)^{2}}\geq\int_{s}^{s+1}\frac{\underline{\nu}(t)}{(\underline{\nu}(t)+\lambda)^{2}}\,dt.$

So we may bound the sum by an integral to show

$\psi(m,2)=\sum_{s=m+1}^{\infty}\frac{\nu_{s}}{(\nu_{s}+\lambda)^{2}}\geq\int_{s^{*}\vee(m+1)}^{\infty}\frac{\underline{\nu}(t)}{(\underline{\nu}(t)+\lambda)^{2}}\,dt\geq\frac{1}{4\lambda^{2}}\int_{s^{*}\vee(m+1)}^{\infty}\underline{\nu}(t)\,dt,$

where $s^{*}$ is the smallest positive integer such that
$\underline{\nu}(s)\leq\lambda$.

  2. 2.

Polynomial decay. If $\underline{\nu}(s)=\omega s^{-\beta}$ then
$s^{*}\leq(\lambda/\omega)^{-1/\beta}+1$. Using the exact integral from
Proposition I.2,

$\displaystyle\psi(0,2)$
$\displaystyle\geq\frac{1}{4\lambda^{2}}\int_{s^{*}}^{\infty}\omega
s^{-\beta}\,ds\geq\frac{\omega(\beta-1)^{-1}}{4\lambda^{2}}[s^{*}]^{1-\beta}\geq\frac{\omega(\beta-1)^{-1}}{4\lambda^{2}}[(\lambda/\omega)^{-1/\beta}+1]^{1-\beta}.$
Under the condition that $\lambda\leq\omega$, the bracketed term is at most
$2(\lambda/\omega)^{-1/\beta}$. This yields $\displaystyle\psi(0,2)$
$\displaystyle\geq\frac{(\beta-1)^{-1}\omega^{1/\beta}}{2^{1+\beta}\lambda^{1+1/\beta}}\geq\frac{1}{c_{\beta,\omega}}\left(\frac{1}{\lambda^{1+1/\beta}}\right).$

  3. 3.

Exponential decay. If $\underline{\nu}(s)=\omega\exp(-\alpha s^{\gamma})$ then
we have

$\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}\leq
s^{*}\leq\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}+1\leq
2\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}$

following from the condition that $\lambda\leq\omega/e^{\alpha}$. We can
compute

$\displaystyle 4\lambda^{2}\cdot\psi(0,2)$
$\displaystyle\geq\int_{s^{*}}^{\infty}\omega\exp(-\alpha s^{\gamma})\,ds.$
Making the substitution $u=\alpha s^{\gamma}$ as in Proposition I.2 gives us
$\displaystyle=\omega\gamma^{-1}\alpha^{\frac{-1}{\gamma}}\int_{\alpha(s^{*})^{\gamma}}^{\infty}\exp(-u)u^{\nicefrac{{(1-\gamma)}}{{\gamma}}}\,du$
$\displaystyle=\omega\gamma^{-1}\alpha^{\frac{-1}{\gamma}}\Gamma(1/\gamma,\alpha[s^{*}]^{\gamma}).$
Using Lemma I.1, which says that $\Gamma(z,x)\geq x^{z-1}e^{-x}$ for $z>1$,
this is
$\displaystyle\geq\omega\gamma^{-1}\alpha^{\frac{-1}{\gamma}}(\alpha[s^{*}]^{\gamma})^{1/\gamma-1}e^{-\alpha[s^{*}]^{\gamma}}$
$\displaystyle=\omega\gamma^{-1}\alpha^{-1}(s^{*})^{1-\gamma}\exp(-\alpha[s^{*}]^{\gamma}).$
Finally we use the bounds on $s^{*}$ in to find that this is
$\displaystyle\geq\omega\gamma^{-1}\alpha^{-1}\left[\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}\right]^{1-\gamma}\exp(-\alpha[2\\{\log(\omega/\lambda)/\alpha\\}^{1/\gamma}]^{\gamma})$
$\displaystyle=\omega\gamma^{-1}\alpha^{-1}\\{\log(\omega/\lambda)/\alpha\\}^{(1/\gamma)-1}\frac{\lambda}{\omega}e^{2^{\gamma}}$
$\displaystyle=\lambda\gamma^{-1}\alpha^{-1}e^{2^{\gamma}}\\{\log(\omega/\lambda)/\alpha\\}^{(1/\gamma)-1}.$

After rearranging, we obtain

$\psi(0,2)\geq\frac{1}{c_{\alpha,\gamma}}\left(\frac{\log(\omega/\lambda)^{(1-\gamma)/\gamma}}{\lambda}\right).$

∎

###  Appendix J Bounding key terms for bootstrap couplings (Section D)

The abstract bound is in terms of
$\Delta_{1}:=\|\hat{\Sigma}-\Sigma\|_{\mathrm{HS}}$ and
$\Delta_{2}:=\operatorname{tr}\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp},$
where

$\Sigma=\mathbb{E}[U_{i}\otimes
U_{i}^{*}],\quad\hat{\Sigma}=\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}.$

We bound these key quantities under different assumptions. In particular, we
prove _unconditional_ bounds, i.e., high probability bounds with respect to
$U$.

######  Assumption J.1 (boundedness).

The random variables $U_{i}$ satisfy $\left\lVert U_{i}\right\rVert\leq a$
almost surely.

######  Assumption J.2 (sub-Gaussianity).

For all $f\in H$, the random variables $U_{i}$ satisfy

$\mathbb{P}\left\\{\left\langle
f,\,U_{i}\right\rangle>ub\left(\mathbb{E}\left\langle
f,\,U_{i}\right\rangle^{2}\right)^{\frac{1}{2}}\right\\}\leq 2e^{-u^{2}}.$

####  J.1 Boundedness

######  Lemma J.3.

Under Assumption J.1, the following event holds with probability at least
$1-2\eta$:

$\lVert\hat{\Sigma}-\Sigma\rVert_{\mathrm{HS}}\leq
2\log(2/\eta)^{2}\left\\{\sqrt{\frac{a^{2}\sigma^{2}(0)}{n}}\vee\frac{4a^{2}}{n}\vee\frac{8a^{2}}{n^{2}}\right\\}.$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition. Write

$\displaystyle\hat{\Sigma}-\Sigma$ $\displaystyle=\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}-\Sigma$
$\displaystyle=\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}-\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}.$

  2. 2.

Focusing on the former term, write $\Sigma_{i}=U_{i}\otimes U_{i}^{*}$. Since
$\left\lVert\Sigma_{i}\right\rVert_{\mathrm{HS}}=\|U_{i}\|^{2}\leq a^{2}$ and

$\mathbb{E}\|\Sigma_{i}\|^{2}_{\mathrm{HS}}=\int\operatorname{tr}(\Sigma_{i}^{*}\Sigma_{i})\mathrm{d}\mathbb{P}\leq\int\|\Sigma_{i}\|_{op}\operatorname{tr}(\Sigma_{i})\mathrm{d}\mathbb{P}\leq
a^{2}\operatorname{tr}(\Sigma)=a^{2}\sigma^{2}(0),$

by Lemma H.2, with probability $1-\eta$,

$\lVert\mathbb{E}_{n}[U_{i}\otimes U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\rVert_{\mathrm{HS}}\leq
2\log(2/\eta)\left\\{\sqrt{\frac{a^{2}\sigma^{2}(0)}{n}}\vee\frac{2a^{2}}{n}\right\\}.$

  3. 3.

Focusing on the latter term, write

$\displaystyle\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}$
$\displaystyle=\|\mathbb{E}_{n}[U_{i}]\|^{2}=\|\mathbb{E}_{n}[U_{i}]-0\|^{2}.$

Notice that $\|U_{i}\|\leq a$ and $\mathbb{E}\|U_{i}\|^{2}\leq a^{2}$ so by
Lemma H.2, with probability $1-\eta$,

$\|\mathbb{E}_{n}[U_{i}]-0\|\leq
2\log(2/\eta)\left\\{\sqrt{\frac{a^{2}}{n}}\vee\frac{2a}{n}\right\\}$

and therefore

$\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}\leq
4\log(2/\eta)^{2}\left\\{\frac{a^{2}}{n}\vee\frac{4a^{2}}{n^{2}}\right\\}=2\log(2/\eta)^{2}\left\\{\frac{2a^{2}}{n}\vee\frac{8a^{2}}{n^{2}}\right\\}.$

  4. 4.

In summary

$\displaystyle\lVert\hat{\Sigma}-\Sigma\rVert_{\mathrm{HS}}$
$\displaystyle\leq\lVert\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\rVert_{\mathrm{HS}}+\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}$
$\displaystyle\leq
2\log(2/\eta)\left\\{\sqrt{\frac{a^{2}\sigma^{2}(0)}{n}}\vee\frac{2a^{2}}{n}\right\\}+2\log(2/\eta)^{2}\left\\{\frac{2a^{2}}{n}\vee\frac{8a^{2}}{n^{2}}\right\\}.$

∎

######  Lemma J.4.

Under Assumption J.1, the following event holds with probability at least
$1-\eta$:

$\operatorname{tr}\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}\leq
2\log(2/\eta)\left(\sqrt{\frac{a^{2}\sigma^{2}(m)}{n}}\vee\frac{2a^{2}}{n}\right).$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition. As before

$\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}=\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}\Pi_{m}^{\perp}-\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}.$

  2. 2.

Focusing on the former term, notice that

$\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]=\mathbb{E}_{n}\xi_{i}-\mathbb{E}\xi_{i},\quad\xi_{i}=\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\Pi_{m}^{\perp}.$

Then we have

$\displaystyle\xi_{i}$
$\displaystyle=\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\Pi_{m}^{\perp}=\operatorname{tr}\\{\Pi_{m}^{\perp}U_{i}\otimes
U_{i}^{*}\Pi_{m}^{\perp}\\}=\|\Pi_{m}^{\perp}U_{i}\|^{2}\leq\|U_{i}\|^{2}\leq
a^{2},$ $\displaystyle\mathbb{E}\xi_{i}^{2}$ $\displaystyle\leq
a^{2}\mathbb{E}\xi_{i}=a^{2}\int\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\Pi_{m}^{\perp}\mathrm{d}\mathbb{P}=a^{2}\int\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\mathrm{d}\mathbb{P}=a^{2}\operatorname{tr}\Pi_{m}^{\perp}\Sigma=a^{2}\sigma^{2}(m),$

so by Lemma H.2, with probability $1-\eta$,

$\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]\leq
2\log(2/\eta)\left\\{\sqrt{\frac{a^{2}\sigma^{2}(m)}{n}}\vee\frac{2a^{2}}{n}\right\\}.$

  3. 3.

Focusing on the latter term, notice that

$\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}]=\|\Pi_{m}^{\perp}\mathbb{E}_{n}[U_{i}]\|^{2}\geq
0.$

  4. 4.

In summary

$\displaystyle\operatorname{tr}\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}$
$\displaystyle=\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\qquad-\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\leq\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\leq
2\log(2/\eta)\left\\{\sqrt{\frac{a^{2}\sigma^{2}(m)}{n}}\vee\frac{2a^{2}}{n}\right\\}.$

∎

####  J.2 Sub-Gaussianity

The sub-Gaussian case is more involved. We quote some helpful results before
bounding the key terms.

#####  J.2.1 Preliminaries

######  Lemma J.5 (Dirksen, (2015, Theorem 3.2)).

Let $(X_{t})_{t\in T}$ denote a real-valued stochastic process on the
separable metric space $(T,d)$, whose increments are sub-Gaussian with respect
to $d$, i.e. $\mathbb{P}\left(\vphantom{\sum}|X_{s}-X_{t}|>ud(s,t)\right)\leq
2e^{-u^{2}}.$ Define the $\gamma$ functional

$\gamma(T,d)=\inf_{S}\sup_{t\in T}\;\sum_{n=0}^{\infty}2^{n/2}d(S_{n},t),$

where the infimum is over sequences $S=(S_{0},S_{1},\ldots)$ of subsets of $T$
satisfying the growth condition $\\#S_{0}=1$, $\\#S_{n}\leq 2^{2^{n}}$, and
$d(S_{n},t)\coloneqq\inf_{s\in S_{n}}d(s,t)$. Then, there exist universal
constants $C,D$ such that the following inequalities hold, for any $t_{0}\in
T$:

$\left(\mathbb{E}\sup_{t\in T}|X_{t}-X_{t_{0}}|^{p}\right)^{\frac{1}{p}}\leq
C\gamma(T,d)+2\sup_{t\in
T}\left(\mathbb{E}|X_{t}-X_{t_{0}}|^{p}\right)^{\frac{1}{p}}.$

######  Lemma J.6 (Talagrand, (2014, Theorem 2.4.1)).

Let $(Z_{t})_{t\in T}$ be a Gaussian process on the separable metric space
$(T,d)$, where
$d(s,t)=\left(\mathbb{E}|Z_{s}-Z_{t}|^{2}\right)^{\frac{1}{2}}$. Then there
exists a universal constant $C>0$ such that
$C^{-1}\gamma(T,d)\leq\mathbb{E}\sup_{t\in T}|Z_{t}|\leq C\gamma(T,d).$

#####  J.2.2 Bounding moments

######  Lemma J.7.

Under Assumption J.2, there exists a universal constant $C$ such that
$\left(\vphantom{\sum}\mathbb{E}\left\lVert
U_{i}\right\rVert^{p}\right)^{\frac{1}{p}}\leq Cb\sqrt{p}\sigma(0).$

###### Proof.

We proceed in steps.

  1. 1.

Matching symbols. We consider the process $X_{t}=\left\langle
U_{i},\,t\right\rangle$ indexed by $t\in B_{H}$. Note in particular that if
$d(s,t)=\left\langle(s-t),\,b^{2}C(s-t)\right\rangle^{\frac{1}{2}}$ then
$(X_{t})_{t\in B_{H}}$ satisfies the sub-Gaussian increments condition with
respect to $d$:

$\mathbb{P}\left(\left\langle
s-t,\,U_{i}\right\rangle>ub\left(\mathbb{E}\left\langle
s-t,\,U_{i}\right\rangle^{2}\right)^{\frac{1}{2}}\right)\leq 2e^{-u^{2}}$

implies $\mathbb{P}\left(\vphantom{\sum}|X_{s}-X_{t}|>ud(s,t)\right)\leq
2e^{-u^{2}}$ when

$d(s,t)=b\left(\mathbb{E}\left\langle
s-t,\,U_{i}\right\rangle^{2}\right)^{\frac{1}{2}}=\left\langle(s-t),\,b^{2}C(s-t)\right\rangle^{\frac{1}{2}}.$

Note also that $\sup_{t\in B_{H}}|X_{t}|=\sup_{t\in B}\left\langle
U_{i},\,t\right\rangle=\left\lVert U_{i}\right\rVert.$ Applying Lemma J.5 to
$(X_{t})_{t\in B_{H}}$ with $t_{0}=0$ therefore yields

$\left(\mathbb{E}\left\lVert U_{i}\right\rVert^{p}\right)^{\frac{1}{p}}\leq
C\gamma(B_{H},d)+2\sup_{t\in B_{H}}\left(\mathbb{E}|\left\langle
t,\,U_{i}\right\rangle|^{p}\right)^{\frac{1}{p}}.$

  2. 2.

First term. To bound $\gamma(B_{H},d)$, note that if
$Z_{t}=b\langle\Sigma^{\frac{1}{2}}g,\,t\rangle$ so that
$\mathbb{E}|Z_{s}-Z_{t}|^{2}=d(s,t)^{2}$ by construction, it holds by Lemma
J.6 that

$\displaystyle\gamma(B_{H},d)$ $\displaystyle\leq C\mathbb{E}\sup_{t\in
B_{H}}|b\langle\Sigma^{\frac{1}{2}}g,\,t\rangle|=bC\mathbb{E}\lVert\Sigma^{\frac{1}{2}}g\rVert\leq
bC\left(\mathbb{E}\lVert\Sigma^{\frac{1}{2}}g\rVert^{2}\right)^{\frac{1}{2}}=bC\sigma(0).$

In particular

$\mathbb{E}\lVert\Sigma^{\frac{1}{2}}g\rVert^{2}=\mathbb{E}[\operatorname{tr}g^{*}\Sigma
g]=\mathbb{E}[\operatorname{tr}\Sigma g\otimes
g^{*}]=\operatorname{tr}\Sigma=\sigma^{2}(0).$

  3. 3.

Second term. What remains is control of the latter term $\sup_{t\in
B_{H}}\left(\mathbb{E}|\left\langle
t,\,U_{i}\right\rangle|^{p}\right)^{\frac{1}{p}}$. Initially fix $t$. To
begin, we argue that $\left\langle t,\,U_{i}\right\rangle$ is sub-Gaussian
with $\left\lVert\left\langle
U_{i},\,t\right\rangle\right\rVert_{\psi_{2}}\leq Cb\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}$. To see why, notice that in our sub-Gaussian
assumption, $b\left(\mathbb{E}\left\langle
t,\,U_{i}\right\rangle^{2}\right)^{\frac{1}{2}}=b\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}.$ Therefore we are effectively assuming

$\left\|\frac{\left\langle t,\,U_{i}\right\rangle}{b\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}}\right\|_{\psi_{2}}\leq C\iff\left\|\left\langle
t,\,U_{i}\right\rangle\right\|_{\psi_{2}}\leq Cb\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}.$

Since $\left\langle t,\,U_{i}\right\rangle$ is sub-Gaussian, we can appeal to
Vershynin, (2018, Proposition 2.5.2) to control its moments. In particular,

$\left(\mathbb{E}|\left\langle
t,\,U_{i}\right\rangle|^{p}\right)^{\frac{1}{p}}\leq C\sqrt{p}\|\left\langle
t,\,U_{i}\right\rangle\|_{\psi_{2}}\leq Cb\sqrt{p}\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}.$

Taking the supremum over $t\in B_{H}$,

$\sup_{t\in B_{H}}\left(\mathbb{E}|\left\langle
t,\,U_{i}\right\rangle|^{p}\right)^{\frac{1}{p}}\leq Cb\sqrt{p}\sup_{t\in
B_{H}}\left\langle t,\,\Sigma
t\right\rangle^{\frac{1}{2}}=Cb\sqrt{p}\nu_{1}^{1/2}\leq Cb\sqrt{p}\sigma(0).$

  4. 4.

Collecting results. In summary,

$\displaystyle\left(\mathbb{E}\left\lVert
U_{i}\right\rVert^{p}\right)^{\frac{1}{p}}$ $\displaystyle\leq
C\gamma(B_{H},d)+2\sup_{t\in B_{H}}\left(\mathbb{E}|\left\langle
t,\,U_{i}\right\rangle|^{p}\right)^{\frac{1}{p}}\leq
bC\sigma(0)+Cb\sqrt{p}\sigma(0)=Cb\sqrt{p}\sigma(0).$

∎

######  Lemma J.8.

Under Assumption J.2, there exists a universal constant $C$ such that
$\left(\mathbb{E}\left\lVert\Pi_{m}^{\perp}U_{i}\right\rVert^{p}\right)^{\frac{1}{p}}\leq
Cb\sqrt{p}\sigma(m).$

###### Proof.

We use as identical proof to Lemma J.7, replacing $U_{i}$ with
$\Pi_{m}^{\perp}U_{i}$. In particular, we consider the process
$X_{t}=\left\langle\Pi_{m}^{\perp}U_{i},\,t\right\rangle=\left\langle
U_{i},\,\Pi_{m}^{\perp}t\right\rangle$ which corresponds restricting the index
set to $t\in\Pi_{m}^{\perp}B_{H}$. Since this process is simply a restriction
of the original process, the increment condition is again satisfied, and it
suffices to plug in the improved bounds

$\displaystyle\gamma(\Pi_{m}^{\perp}B_{H},d)$ $\displaystyle\leq
bC\mathbb{E}\left\lVert\Pi_{m}^{\perp}\Sigma^{\frac{1}{2}}g\right\rVert\leq
bC\sigma^{2}(m),$
$\displaystyle\sup_{t\in\Pi_{m}^{\perp}B_{H}}\left\lVert\left\langle
U_{i},\,t\right\rangle\right\rVert_{\psi_{2}}$ $\displaystyle\leq Cb\sup_{t\in
B_{H}}\left\langle\Pi_{m}^{\perp}t,\,\Sigma\Pi_{m}^{\perp}t\right\rangle^{\frac{1}{2}}=Cb\sqrt{\nu_{m}}\leq
b\sigma(m).$

∎

#####  J.2.3 Main result

######  Lemma J.9.

Under Assumption J.2, the following event holds with probability at least
$1-2\eta$, $\lVert\hat{\Sigma}-\Sigma\rVert_{\mathrm{HS}}\leq
C\log(2/\eta)^{2}\frac{b^{2}\sigma^{2}(0)}{\sqrt{n}}.$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition. As before, write

$\displaystyle\hat{\Sigma}-\Sigma$ $\displaystyle=\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}-\Sigma$
$\displaystyle=\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}-\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}.$

  2. 2.

Focusing on the first term, write $\Sigma_{i}=U_{i}\otimes U_{i}^{*}$. Notice
that

$\displaystyle\|\|\Sigma_{i}-\Sigma\|_{\mathrm{HS}}\|_{p}$
$\displaystyle\leq\|\|\Sigma_{i}\|_{\mathrm{HS}}+\|\Sigma\|_{\mathrm{HS}}\|_{p}\leq\|\|\Sigma_{i}\|_{\mathrm{HS}}\|_{p}+\|\|\Sigma\|_{\mathrm{HS}}\|_{p}.$

Note that the former term is
$\|\|\Sigma_{i}\|_{\mathrm{HS}}\|^{p}_{p}=\mathbb{E}(\|\Sigma_{i}\|_{\mathrm{HS}}^{p}).$
Within the latter term
$\|\Sigma\|_{\mathrm{HS}}=\|\mathbb{E}(\Sigma_{i})\|_{HS}\leq\mathbb{E}(\|\Sigma_{i}\|_{\mathrm{HS}})$
hence

$\|\|\Sigma\|_{\mathrm{HS}}\|^{p}_{p}\leq\mathbb{E}[\\{\mathbb{E}(\|\Sigma_{i}\|_{\mathrm{HS}})\\}^{p}]\leq\mathbb{E}\\{\mathbb{E}(\|\Sigma_{i}\|^{p}_{\mathrm{HS}})\\}=\mathbb{E}(\|\Sigma_{i}\|^{p}_{\mathrm{HS}}).$

In summary $\|\|\Sigma_{i}-\Sigma\|_{\mathrm{HS}}\|_{p}\leq
2\|\|\Sigma_{i}\|_{\mathrm{HS}}\|_{p}.$ Finally, we have
$\|\Sigma_{i}\|^{p}_{\mathrm{HS}}=\|U_{i}\|^{2p}.$ Thus, we can estimate using
Lemma J.7 that

$\mathbb{E}\left\lVert\Sigma_{i}-\Sigma\right\rVert^{p}_{\mathrm{HS}}\leq
2^{p}\mathbb{E}(\left\lVert
U_{i}\right\rVert^{2p})\leq(2b^{2}C^{2})^{p}(\sqrt{2p})^{2p}\sigma^{2p}(0)$

since $\mathbb{E}\left\lVert
U_{i}\right\rVert^{q}\leq\\{Cb\sqrt{q}\sigma(0)\\}^{q}$ where $q=2p.$

  3. 3.

By Stirling’s approximation, we have $p!\geq(p/e)^{p}$, so
$(2e)^{p}p!\geq(2p)^{p}=(\sqrt{2p})^{2p}$. Hence

$\displaystyle\mathbb{E}\left\lVert\Sigma_{i}-\Sigma\right\rVert^{p}_{\mathrm{HS}}$
$\displaystyle\leq(2b^{2}C^{2})^{p}(2e)^{p}p!\sigma^{2p}(0)=(2^{1/p}4eb^{2}C^{2})^{p}\frac{1}{2}p!\sigma^{2p}(0)=(C^{\prime\prime})^{p}\frac{1}{2}p!\sigma^{2p}(0)$

and therefore
$\mathbb{E}\left\lVert\frac{\Sigma_{i}-\Sigma}{C^{\prime\prime}}\right\rVert^{p}_{\mathrm{HS}}\leq\frac{1}{2}p!\\{\sigma^{2}(0)\\}^{p}$
where $C^{\prime\prime}=2^{1/p}4eb^{2}C^{2}.$ Therefore by applying Lemma H.2
with $A=B=\sigma^{2}(0)$, we see that with probability at least $1-\eta$,

$\displaystyle\left\lVert\mathbb{E}_{n}[\Sigma_{i}]-\Sigma\right\rVert_{\mathrm{HS}}$
$\displaystyle=C^{\prime\prime}\left\lVert\frac{\mathbb{E}_{n}[\Sigma_{i}]-\Sigma}{C^{\prime\prime}}\right\rVert_{\mathrm{HS}}$
$\displaystyle\leq
C^{\prime\prime}2\ln(2/\eta)\left\\{\frac{\sigma^{2}(0)}{n}\vee\sqrt{\frac{\sigma^{4}(0)}{n}}\right\\}$
$\displaystyle\leq 2C^{\prime\prime}\ln(2/\eta)\frac{\sigma^{2}(0)}{\sqrt{n}}$
$\displaystyle\leq 16eb^{2}C^{2}\ln(2/\eta)\frac{\sigma^{2}(0)}{\sqrt{n}}.$

  4. 4.

Turning to the second term, write

$\displaystyle\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}$
$\displaystyle=\|\mathbb{E}_{n}[U_{i}]\|^{2}=\|\mathbb{E}_{n}[U_{i}]-0\|^{2}.$

By Lemma J.7,

$\mathbb{E}\|U_{i}\|^{p}\leq\\{Cb\sqrt{p}\sigma(0)\\}^{p}=(bC)^{p}\sqrt{p}^{p}\\{\sigma(0)\\}^{p}.$

By Stirling’s approximation, $p!\geq(p/e)^{p}$ so
$\sqrt{p}^{p}\leq(e^{p}p!)^{1/2}\leq e^{p/2}p!$. Therefore

$\mathbb{E}\|U_{i}\|^{p}\leq(bCe^{1/2})^{p}p!\\{\sigma(0)\\}^{p}=(C^{\prime})^{p}\frac{1}{2}p!\\{\sigma(0)\\}^{p},\quad
C^{\prime}=2^{1/p}bCe^{1/2}.$

Applying Lemma H.2 with $A=B=\sigma(0)$, with probability at least $1-\eta$,

$\displaystyle\|\mathbb{E}_{n}[U_{i}]\|$
$\displaystyle=C^{\prime}\left\|\frac{\mathbb{E}_{n}[U_{i}]}{C^{\prime}}\right\|$
$\displaystyle\leq
C^{\prime}2\ln(2/\eta)\left\\{\frac{\sigma(0)}{n}\vee\sqrt{\frac{\sigma^{2}(0)}{n}}\right\\}$
$\displaystyle\leq 2C^{\prime}\ln(2/\eta)\frac{\sigma(0)}{\sqrt{n}}$
$\displaystyle\leq 4bCe^{1/2}\ln(2/\eta)\frac{\sigma(0)}{\sqrt{n}}.$

Therefore

$\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}\leq
16b^{2}C^{2}e\ln(2/\eta)^{2}\frac{\sigma^{2}(0)}{n}.$

  5. 5.

In summary

$\displaystyle\lVert\hat{\Sigma}-\Sigma\rVert_{\mathrm{HS}}$
$\displaystyle\leq\lVert\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\rVert_{\mathrm{HS}}+\|\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\|_{\mathrm{HS}}$
$\displaystyle\leq
16eb^{2}C^{2}\ln(2/\eta)\frac{\sigma^{2}(0)}{\sqrt{n}}+16b^{2}C^{2}e\ln(2/\eta)^{2}\frac{\sigma^{2}(0)}{n}.$

∎

######  Lemma J.10.

Under Assumption J.2, the following event holds with probability at least
$1-\eta$:
$\operatorname{tr}\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}\leq
C\log(2/\eta)\frac{b^{2}\sigma^{2}(m)}{\sqrt{n}}.$

###### Proof.

We proceed in steps.

  1. 1.

Decomposition. As before

$\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}=\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}\Pi_{m}^{\perp}-\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}.$

  2. 2.

Focusing on the first term, notice that

$\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes
U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]=\mathbb{E}_{n}\xi_{i}-\mathbb{E}\xi_{i},\quad\xi_{i}=\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\Pi_{m}^{\perp}.$

Moreover
$\|\xi_{i}-\mathbb{E}\xi_{i}\|_{p}\leq\|\xi_{i}\|_{p}+\|\mathbb{E}\xi_{i}\|_{p}.$
The former term is $\|\xi_{i}\|^{p}_{p}=\mathbb{E}(|\xi_{i}|^{p}).$ Within the
latter term

$\|\mathbb{E}\xi_{i}\|^{p}_{p}=\mathbb{E}[|\mathbb{E}\xi_{i}|^{p}]\leq\mathbb{E}[\mathbb{E}(|\xi_{i}|^{p})]=\mathbb{E}(|\xi_{i}|^{p}).$

In summary $\|\xi_{i}-\mathbb{E}\xi_{i}\|_{p}\leq 2\|\xi_{i}\|_{p}.$ Then

$\xi_{i}=\operatorname{tr}\Pi_{m}^{\perp}\Sigma_{i}\Pi_{m}^{\perp}=\operatorname{tr}\\{\Pi_{m}^{\perp}U_{i}\otimes
U_{i}^{*}\Pi_{m}^{\perp}\\}=\|\Pi_{m}^{\perp}U_{i}\|^{2}.$

By Lemma J.8,

$\mathbb{E}(|\xi_{i}-\mathbb{E}\xi_{i}|^{p})\leq
2^{p}\mathbb{E}(|\xi_{i}|^{p})=2^{p}\mathbb{E}(\|\Pi_{m}^{\perp}U_{i}\|^{2p})\leq
2^{p}\\{Cb\sqrt{2p}\sigma(m)\\}^{2p}.$

  3. 3.

By Stirling’s approximation, $p!\geq(p/e)^{p}$, so
$(2e)^{p}p!\geq(2p)^{p}=(\sqrt{2p})^{2p}$. Hence

$\displaystyle\mathbb{E}(|\xi_{i}|^{p})$ $\displaystyle\leq
2^{p}\\{Cb\\}^{2p}(2e)^{p}p!\\{\sigma^{2}(m)\\}^{p}$
$\displaystyle=(2^{1/p}4eb^{2}C^{2})^{p}\frac{1}{2}p!\\{\sigma^{2}(m)\\}^{p}$
$\displaystyle=(C^{\prime\prime\prime})^{p}\frac{1}{2}p!\\{\sigma^{2}(m)\\}^{p}$

and therefore

$\mathbb{E}\left(\left|\frac{\xi_{i}}{C^{\prime\prime\prime}}\right|^{p}\right)\leq\frac{1}{2}p!\\{\sigma^{2}(m)\\}^{p},\quad
C^{\prime\prime\prime}=2^{1/p}4eb^{2}C^{2}.$

Applying Lemma H.2 with $A=B=\sigma^{2}(m)$, we see that with probability
$1-\eta$

$\displaystyle|\mathbb{E}_{n}\xi_{i}-\mathbb{E}\xi_{i}|$
$\displaystyle=C^{\prime\prime\prime}\left|\frac{\mathbb{E}_{n}\xi_{i}-\mathbb{E}\xi_{i}}{C^{\prime\prime\prime}}\right|$
$\displaystyle\leq
C^{\prime\prime\prime}2\ln(2/\eta)\left\\{\frac{\sigma^{2}(m)}{n}\vee\sqrt{\frac{\sigma^{4}(m)}{n}}\right\\}$
$\displaystyle\leq
2C^{\prime\prime\prime}\ln(2/\eta)\frac{\sigma^{2}(m)}{\sqrt{n}}.$
$\displaystyle\leq 16eb^{2}C^{2}\ln(2/\eta)\frac{\sigma^{2}(m)}{\sqrt{n}}.$

  4. 4.

Focusing on the second term, notice that

$\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}]=\|\Pi_{m}^{\perp}\mathbb{E}_{n}[U_{i}]\|^{2}\geq
0.$

  5. 5.

In summary

$\displaystyle\operatorname{tr}\Pi_{m}^{\perp}(\hat{\Sigma}-\Sigma)\Pi_{m}^{\perp}$
$\displaystyle=\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\qquad-\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}]\otimes(\mathbb{E}_{n}[U_{i}])^{*}\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\leq\operatorname{tr}[\Pi_{m}^{\perp}\left\\{\mathbb{E}_{n}[U_{i}\otimes
U_{i}^{*}]-\mathbb{E}[U_{i}\otimes U_{i}^{*}]\right\\}\Pi_{m}^{\perp}]$
$\displaystyle\leq 16eb^{2}C^{2}\ln(2/\eta)\frac{\sigma^{2}(m)}{\sqrt{n}}.$

∎

###  Appendix K Simulation details

####  K.1 Robust performance in Sobolev spaces

In this appendix, we present additional results in Sobolev spaces. The Sobolev
space corresponds to the Matern kernel. We verify nominal coverage across
smoothness degrees, sample sizes, and regularization values. We document
additional metrics such as bias and width of the confidence bands.

Figure 6: Regression in $\mathbb{H}_{2}^{1}$ with standard data. Figure 7: Our approach succeeds in $\mathbb{H}_{2}^{1}$. sample |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
50 | 0.942 | 0.946 | 0.938 | 0.944
100 | 0.968 | 0.972 | 0.934 | 0.940
500 | 0.928 | 0.924 | 0.916 | 0.926
1000 | 0.970 | 0.970 | 0.955 | 0.960
Table 12: Coverage is nominal across sample sizes in $\mathbb{H}^{1}_{2}$. Across rows, we vary $n$ and set $\lambda=n^{-1/3}$, following Section 6. reg. |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
0.500 | 0.784 | 0.920 | 0.750 | 0.918
0.100 | 0.938 | 0.942 | 0.934 | 0.942
0.050 | 0.932 | 0.932 | 0.920 | 0.924
0.010 | 0.942 | 0.942 | 0.954 | 0.954
0.005 | 0.934 | 0.934 | 0.914 | 0.914
0.001 | 0.956 | 0.956 | 0.922 | 0.922
Table 13: Coverage is nominal across regularization values in $\mathbb{H}^{1}_{2}$. Across rows, we fix $n=500$ and vary $\lambda$ across a reasonable range. metric |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
coverage | 0.952 | 0.954 | 0.942 | 0.946
bias | 0.019 | 0.000 | 0.022 | 0.000
width | 0.878 | 0.878 | 0.889 | 0.889
Table 14: A detailed look: Coverage, bias, and width in $\mathbb{H}^{1}_{2}$. Across rows, we fix $n=500$ and set $\lambda=n^{-1/3}$. We examine additional metrics in addition to coverage. Figure 8: Regression in $\mathbb{H}_{2}^{2}$ with standard data. Figure 9: Our approach succeeds in $\mathbb{H}_{2}^{2}$. sample |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
50 | 0.884 | 0.878 | 0.746 | 0.752
100 | 0.942 | 0.940 | 0.940 | 0.946
500 | 0.976 | 0.972 | 0.980 | 0.978
1000 | 0.980 | 0.980 | 0.970 | 0.975
Table 15: Coverage is nominal across sample sizes in $\mathbb{H}^{2}_{2}$. Across rows, we vary $n$ and set $\lambda=n^{-1/3}$, following Section 6. reg. |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
0.500 | 0.884 | 0.970 | 0.810 | 0.970
0.100 | 0.930 | 0.940 | 0.930 | 0.942
0.050 | 0.948 | 0.948 | 0.940 | 0.940
0.010 | 0.964 | 0.966 | 0.940 | 0.940
0.005 | 0.950 | 0.948 | 0.958 | 0.958
0.001 | 0.928 | 0.928 | 0.970 | 0.970
Table 16: Coverage is nominal across regularization values in $\mathbb{H}^{2}_{2}$. Across rows, we fix $n=500$ and vary $\lambda$ across a reasonable range. metric |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
coverage | 0.938 | 0.944 | 0.944 | 0.944
bias | 0.017 | 0.000 | 0.024 | 0.000
width | 0.855 | 0.855 | 0.872 | 0.872
Table 17: A detailed look: Coverage, bias, and width in $\mathbb{H}^{2}_{2}$.
Across rows, we fix $n=$ and set $\lambda=n^{-1/3}$. We examine additional
metrics in addition to coverage.

####  K.2 Pseudo true coverage under mis-specification

In this appendix, we present additional results for the mis-specified Gaussian
kernel. While coverage for the true parameter $f_{0}\not\in H$ breaks down,
coverage for the pseudo true parameter $f_{\lambda}\in H$ remains nominal
across sample sizes and regularization values. These simulations showcase how
our inferential theory delivers meaningful guarantees without any assumptions
on the bias $f_{\lambda}-f_{0}$. Again, we document additional metrics such as
bias and width of the confidence bands.

Figure 10: Standard data with mis-specification Figure 11: Our approach succeeds with mis-specification sample |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
50 | 0.000 | 0.974 | 0.000 | 0.966
100 | 0.000 | 0.946 | 0.000 | 0.952
500 | 0.000 | 0.948 | 0.000 | 0.956
1000 | 0.000 | 0.955 | 0.000 | 0.950
Table 18: Coverage is nominal across sample sizes with mis-specification. Across rows, we vary $n$ and set $\lambda=n^{-1/3}$, following Section 6. reg. |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
0.500 | 0.000 | 0.952 | 0.000 | 0.946
0.100 | 0.000 | 0.956 | 0.000 | 0.964
0.050 | 0.000 | 0.960 | 0.000 | 0.932
0.010 | 0.000 | 0.948 | 0.000 | 0.944
0.005 | 0.000 | 0.960 | 0.000 | 0.960
0.001 | 0.000 | 0.942 | 0.000 | 0.954
Table 19: Coverage is nominal across regularization values with mis-specification. Across rows, we fix $n=500$ and vary $\lambda$ across a reasonable range. metric |  $\sup$ norm |  $H$ norm
---|---|---
true | pseudo | true | pseudo
coverage | 0.000 | 0.960 | 0.000 | 0.976
bias | 4.973 | 0.000 | NA | 0.000
width | 1.366 | 1.366 | 1.976 | 1.976
Table 20: A detailed look: Coverage, bias, and width with mis-specification.
Across rows, we fix $n=500$ and set $\lambda=n^{-1/3}$. We examine additional
metrics in addition to coverage.

####  K.3 Implementation details

In Section 4.2, each observation is generated as follows. Draw
$X_{i}\sim\mathrm{Unif}([0,1])$ and $\varepsilon_{i}\sim\mathrm{Unif}([-2,2])$
independently for each $1\leq i\leq n$. Then set
$Y_{i}=f_{0}(X_{i})+\varepsilon_{i}$ where

$f_{0}=\frac{1}{\sqrt{5}}\sum_{i=1}^{5}e_{i}g_{i},$

where $e_{i}$ denote the eigenfunctions of the integral operator
$\mathbb{E}[k_{X_{i}}k_{X_{i}}^{*}]$, and the $g_{i}$ are independent standard
normal multipliers. We implement Estimator 4.1 with the Gaussian kernel
$k(x,y)=\exp\\{-\lVert x-y\rVert/(2\iota^{2})\\}$, with the scale $\iota$ set
to $0.1$.

In Section 4.3, each observation is generated as in section 4.2, with the
following changes. The covariates $X_{i}$ are a uniform random permutation of
$\left\\{1,2,\cdots,7\right\\}$, and the kernel $k$ is chosen to be the
Mallows kernel
$k(\pi,\pi^{\prime})=\exp\\{-\tau(\pi,\pi^{\prime})/(2\iota^{2})\\}$; here
$\tau$ is Kendall’s-$\tau$ function which counts the number of discordant
pairs. We employ the standard heuristic and choose $\iota$ to be the median of
the $\tau(X_{i},X_{j})$ for independent draws of the data.

In Section K.1, each observation is generated as in Section 4.2, replacing
$f_{0}$ with the third eigenfunction of the Matern kernel. We implement
Estimator 4.1 with the length-scale parameter set to $0.1$.

In Section K.2, each observation is generated as in Section 4.2, replacing
$f_{0}$ with the step function $f_{0}(x)=\mathbbm{1}\\{x\geq 1/2\\}$. We
implement Estimator 4.1, with the length-scale parameter set to $0.1$.

###  Appendix L Application details

####  L.1 Random utility model

In order to evaluate our proposed direct approach, we generate synthetic data
which resemble real student preferences using the discrete choice model
estimated and reported in Pathak and Shi, (2021). In that paper, the authors
fit several common discrete choice models to students’ reported preference
data from the Boston Public Schools centralized match, and then assess each
model’s ability to forecast demand. As Boston Public Schools used a student-
proposing variant of the deferred acceptance (DA) algorithm of Gale and
Shapley, (1962), strategy-proofness holds and students can reasonably be
assumed to report preferences truthfully (Pathak and Sönmez,, 2008).

In the random utility model of Pathak and Shi, (2021), the utility of student
$i$ at school $s$ is

$u_{is}=\hat{}\alpha_{s}+\hat{\beta}_{1}^{\top}X_{1}+\beta_{2}^{\top}X_{2}+\epsilon_{i}.$

In this model, $X_{1}$ and $X_{2}$ are student-school covariates such as
student race, school demographics, walking distance to the school, student
English language learner status ,and the availability of English instructional
programs in the student’s language. The vector $\hat{\beta}_{1}$ contains
estimated coefficients, while $\beta_{2}\sim
N(\hat{\mu}_{2},\hat{\Sigma}_{2})$ are random coefficients fit using the mixed
multinomial logit procedure outlined in the paper. Finally, $\hat{}\alpha_{s}$
is a school fixed-effect, and $\epsilon_{i}$ is an independent standard Gumbel
random variable.

For the scenario of no match effects, we generate student preferences as
described above. We draw school effects as

$Y_{is}=\mu+\sigma\delta_{i}+\gamma_{1}P_{s},$

where $\delta_{i}$ is a standard normal random variable. We truncate $Y_{is}$
to lie in $[0,100]$.

For the scenario of match effects, we generate student preferences with an
additional taste parameter:

$u_{is}=\hat{}\alpha_{s}+\hat{\beta}_{1}^{\top}X_{1}+\beta_{2}^{\top}X_{2}+\chi_{i}P_{s}\epsilon_{i},$

where $P_{s}$ indicated whether $s$ is a pilot school and $\chi_{i}$
represents preference for pilot sector schools. Here, $\chi_{i}$ determines
sector effects: we generate counterfactual outcomes by calculating and then
truncating

$Y_{is}=\mu+\sigma\delta_{i}+\gamma\chi_{i}P_{s},$

so students who prefer pilot sector schools also benefit more from them.

####  L.2 Comparison to propensity score conditioning

As remarked in the main text, group average treatment effects for rank strata
(and, indeed, individual preference types) are also identified by simple
averages. However, when the strata are relatively small, the resulting
measurements are far too noisy for meaningful statistical inference. KRR
improves precision by using the full ranked list to predict outcomes. To
illustrate this point, we compare our methodology using KRR to the standard
inverse propensity-weighted averages below.

(a) KRR (uniform bands)

(b) IPW (uniform bands)

(c) IPW (pointwise bands)

Figure 12: KRR inference improves power. In our experiment, simply averaging
the inverse propensity-weighted score frequently produces the incorrect sign
(with pointwise signifiance), and uniform confidence bands are uninformative.