$\displaystyle\sigma_{n}=\delta_{n}^{\kappa}.$ (83)

From the preceding bound, it follows that
$\sup_{f\in\mathcal{F}_{K}}\|f\|_{L^{2}(\mathbb{P})}\leq C_{1}\sigma_{n}$. By
an application of (Giné and Nickl, 2021, Proposition 3.5.15), there exists a
universal constant $L>0$ such that

$\displaystyle\mathbb{E}\bigg{[}\sup_{h,h^{\prime}\in\mathbf{H}^{t}(M):\|h-h^{\prime}\|_{L^{2}(\mathbb{P})}\leq\delta_{n}}\|\mathbb{E}_{n}[R_{h-h^{\prime}}^{K}(Z)]-\mathbb{E}[R_{h-h^{\prime}}^{K}(Z)]\|_{\ell^{2}}\bigg{]}$
$\displaystyle\leq\frac{L}{\sqrt{n}}\int_{0}^{2\sigma_{n}}\sqrt{\log
N_{[]}(\mathcal{F}_{K},\|.\|_{L^{2}(\mathbb{P})},\epsilon)}d\epsilon\bigg{(}1+\frac{\zeta_{b,K}}{\sigma_{n}^{2}\sqrt{n}}\int_{0}^{2\sigma_{n}}\sqrt{\log
N_{[]}(\mathcal{F}_{K},\|.\|_{L^{2}(\mathbb{P})},\epsilon)}d\epsilon\bigg{)}.$

Fix any $\delta>0$. Let $\\{h_{i}\\}_{i=1}^{T_{1}}$ denote a $\delta$ covering
of $\big{(}\mathbf{H}^{t}(M),\|.\|_{\infty}\big{)}$ and
$\\{\gamma_{m}\\}_{m=1}^{T_{2}}$ denote a $\delta$ covering of
$(\mathbb{S}^{K-1},\|.\|_{\ell^{2}})$. For $i,j\in\\{1,\dots,T_{1}\\}$ and
$m\in\\{1,\dots,T_{2}\\}$, define the functions

$\displaystyle e_{i,j,m}(Z)$
$\displaystyle=\sup_{\gamma\in\mathbb{S}^{K-1}:\|\gamma-\gamma_{m}\|_{\ell^{2}}<\delta\;,\;h\in\mathbf{H}^{t}(M)\;,\;h^{\prime}\in\mathbf{H}^{t}(M)}\left|(\gamma-\gamma_{m})^{\prime}[R_{h}^{K}(Z)-R_{h^{\prime}}^{K}(Z)]\right|$
$\displaystyle+\sup_{\gamma\in\mathbb{S}^{K-1}\;,\;h\in\mathbf{H}^{t}(M):\|h-h_{i}\|_{\infty}<\delta}\left|\gamma^{\prime}[R_{h}^{K}(Z)-R_{h_{i}}^{K}(Z)]\right|$
$\displaystyle+\sup_{\gamma\in\mathbb{S}^{K-1}\;,\;h\in\mathbf{H}^{t}(M):\|h-h_{j}\|_{\infty}<\delta}\left|\gamma^{\prime}[R_{h}^{K}(Z)-R_{h_{j}}^{K}(Z)]\right|.$

Observe that

$\bigg{\\{}\gamma_{m}^{\prime}[R_{h_{i}}^{K}(Z)-R_{h_{j}}^{K}(Z)]-e_{i,j,m}\;,\;\gamma_{m}^{\prime}[R_{h_{i}}^{K}(Z)-R_{h_{j}}^{K}(Z)]+e_{i,j,m}\bigg{\\}}_{(i,j)\in\\{1,\dots,T_{1}\\}\;,m\in\\{1,\dots,T_{2}\\}}$

is a bracket covering for $\mathcal{F}_{K}$. Let $C_{1}(M)$ and
$\kappa\in(0,1]$ be as in Assumption 2. Let $C_{2}(M)$ be as in Assumption
3(i). By Assumptions (2, 3(i)) and Cauchy-Schwarz, we have that

$\displaystyle\|e_{i,j,m}\|_{L^{2}(\mathbb{P})}$
$\displaystyle\leq\bigg{\|}\sup_{\gamma\in\mathbb{S}^{K-1}:\|\gamma-\gamma_{m}\|_{\ell^{2}}<\delta\;,\;h\in\mathbf{H}^{t}(M)\;,\;h^{\prime}\in\mathbf{H}^{t}(M)}\left|(\gamma-\gamma_{m})^{\prime}[R_{h}^{K}(Z)-R_{h^{\prime}}^{K}(Z)]\right|\bigg{\|}_{L^{2}(\mathbb{P})}$
$\displaystyle+\bigg{\|}\sup_{\gamma\in\mathbb{S}^{K-1}\;,\;h\in\mathbf{H}^{t}(M):\|h-h_{i}\|_{\infty}<\delta}\left|\gamma^{\prime}[R_{h}^{K}(Z)-R_{h_{i}}^{K}(Z)]\right|\bigg{\|}_{L^{2}(\mathbb{P})}$
$\displaystyle+\bigg{\|}\sup_{\gamma\in\mathbb{S}^{K-1}\;,\;h\in\mathbf{H}^{t}(M):\|h-h_{j}\|_{\infty}<\delta}\left|\gamma^{\prime}[R_{h}^{K}(Z)-R_{h_{j}}^{K}(Z)]\right|\bigg{\|}_{L^{2}(\mathbb{P})}$
$\displaystyle\leq
2\delta\zeta_{b,K}C_{2}+\delta^{\kappa}\zeta_{b,K}C_{1}+\delta^{\kappa}\zeta_{b,K}C_{1}.$

In particular, for all $\delta\in(0,1]$, we have that
$\|e_{i,j,m}\|_{L^{2}(\mathbb{P})}\leq C\delta^{\kappa}\zeta_{b,K}$ for
$C=2C_{2}+2C_{1}$.

By (Ghosal and Van der Vaart, 2017, Proposition C.7), we have that $\log
N(\mathbf{H}^{t}(M),\|.\|_{\infty},\epsilon)\lessapprox\epsilon^{-d/t}$ as
$\epsilon\downarrow 0$. Since $\log
N(\mathbb{S}^{K-1},\|.\|_{\ell^{2}},\epsilon)\leq K\log(3\epsilon^{-1})$, it
follows that there exists a universal constant $L>0$ such that

$\displaystyle\int_{0}^{2\sigma_{n}}\sqrt{\log
N_{[]}(\mathcal{F}_{K},\|.\|_{L^{2}(\mathbb{P})},\epsilon)}d\epsilon$
$\displaystyle\leq
L\bigg{(}\sqrt{K}\sqrt{\log\zeta_{b,K}}\sigma_{n}+\sqrt{K}\int_{0}^{2\sigma_{n}}\sqrt{\log(\epsilon^{-1})}d\epsilon+\int_{0}^{2\sigma_{n}}\epsilon^{-d/2\kappa
t}d\epsilon\bigg{)}$ $\displaystyle\leq
L\bigg{(}\sqrt{K}\sqrt{\log\zeta_{b,K}}\sigma_{n}+\sqrt{K}\sigma_{n}\sqrt{\log(\sigma_{n}^{-1})}+\sigma_{n}^{1-d/(2\kappa
t)}\bigg{)}$ $\displaystyle\leq L\bigg{(}\sqrt{K}\sqrt{\log
K}\sigma_{n}+\sigma_{n}^{1-d/(2\kappa t)}\bigg{)}.$

From the preceding bounds and $\zeta_{b,K}\lessapprox\sqrt{K}$, it follows
that

$\displaystyle\sqrt{n}\mathbb{E}\bigg{[}\sup_{h,h^{\prime}\in\mathbf{H}^{t}(M):\|h-h^{\prime}\|_{L^{2}(\mathbb{P})}\leq\delta_{n}}\|\mathbb{E}_{n}[R_{h-h^{\prime}}^{K}(Z)]-\mathbb{E}[R_{h-h^{\prime}}^{K}(Z)]\|_{\ell^{2}}\bigg{]}$
$\displaystyle\leq L\int_{0}^{2\sigma_{n}}\sqrt{\log
N_{[]}(\mathcal{F}_{K},\|.\|_{L^{2}(\mathbb{P})},\epsilon)}d\epsilon\bigg{(}1+\frac{\zeta_{b,K}}{\sigma_{n}^{2}\sqrt{n}}\int_{0}^{2\sigma_{n}}\sqrt{\log
N_{[]}(\mathcal{F}_{K},\|.\|_{L^{2}(\mathbb{P})},\epsilon)}d\epsilon\bigg{)}$
$\displaystyle\lessapprox\bigg{(}\sqrt{K}\sqrt{\log
K}\sigma_{n}+\sigma_{n}^{1-d/(2\kappa t)}\bigg{)}+\bigg{(}\sqrt{K}\sqrt{\log
K}\sigma_{n}+\sigma_{n}^{1-d/(2\kappa
t)}\bigg{)}^{2}\frac{\sqrt{K}}{\sigma_{n}^{2}\sqrt{n}}.$

By substituting $\sigma_{n}=\delta_{n}^{\kappa}$, the preceding term reduces
to

$\displaystyle\bigg{(}\sqrt{K}\sqrt{\log
K}\delta_{n}^{\kappa}+\delta_{n}^{\kappa-d/(2t)}\bigg{)}+\bigg{(}\sqrt{K}\sqrt{\log
K}\delta_{n}^{\kappa}+\delta_{n}^{\kappa-d/(2t)}\bigg{)}^{2}\frac{\sqrt{K}}{\delta_{n}^{2\kappa}\sqrt{n}}.$

The claim follows.

∎

######  Lemma 9.

Suppose Assumptions (1-3) hold. For each realization of $W$, let $\Sigma(W)$
denote a positive definite matrix such that $\mathbb{P}(\|\Sigma(W)\|_{op}\leq
C)=1$ for some $C>0$. Given any fixed $M>0$ and sequences
$\delta_{n},\gamma_{n}\downarrow 0$, define the set

$\displaystyle\Theta_{n}=\\{h\in\mathbf{H}^{t}(M):\mathbb{E}(\|\Pi_{K}m(W,h)\|_{\ell^{2}}^{2})\leq
M\gamma_{n}^{2},\;\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq M\delta_{n}\\}.$

Then, there exists a universal constants $D,R<\infty$ such that

$\displaystyle\mathbb{E}\bigg{(}\sup_{h\in\Theta_{n}}\left|\sum_{i=1}^{n}\bigg{\\{}[\Pi_{K}m(W_{i},h)]^{\prime}\Sigma(W_{i})[\Pi_{K}m(W_{i},h)]-\mathbb{E}\big{(}[\Pi_{K}m(W,h)]^{\prime}\Sigma(W)[\Pi_{K}m(W,h)]\big{)}\bigg{\\}}\right|\bigg{)}$
$\displaystyle\leq
R\bigg{[}\sqrt{n}\gamma_{n}^{2}K\mathcal{J}(K^{-1/2})+\gamma_{n}^{2}K^{3}\mathcal{J}^{2}(K^{-1/2})\bigg{]}$

where $\mathcal{J}(.)$ is defined by

$\displaystyle\mathcal{J}(c)=\int_{0}^{c}\sqrt{\log
N(\mathcal{M}_{n},\|.\|_{L^{2}(\mathbb{P})},\tau
D\gamma_{n})}d\tau\;\;\;\;\;\;\;\;\forall\;c>0$
$\displaystyle\mathcal{M}_{n}=\\{m(w,h):h\in\Theta_{n}\\}.$

###### Proof of Lemma 9.

Define the class of functions

$\displaystyle\mathcal{F}=\\{g:g(.)=[\Pi_{K}m(.,h)]^{\prime}\Sigma(.)[\Pi_{K}m(.,h)]:h\in\Theta_{n}\\}.$

For every fixed $h\in\Theta_{n}$, we have that

$\displaystyle\Pi_{K}[m(W,h)]$
$\displaystyle=\sum_{i=1}^{K}c_{h,i}[G_{b,K}^{-1/2}b^{K}(W)]_{i}\;\;,\;\;c_{h,i}=\mathbb{E}\big{[}\rho\big{(}Y,h(X)\big{)}[G_{b,K}^{-1/2}b^{K}(W)]_{i}\big{]}\;,$

where $[G_{b,K}^{-1/2}b^{K}(W)]_{i}$ denotes the $i^{th}$ element of the
vector $G_{b,K}^{-1/2}b^{K}(W)$. For every $l\in\\{1,\dots,d_{\rho}\\}$,
denote by $c_{h}^{l}$ the coefficient vector

$\displaystyle
c_{h}^{l}=\big{\\{}\mathbb{E}\big{[}\rho_{l}\big{(}Y,h(X)\big{)}[G_{b,K}^{-1/2}b^{K}(W)]_{i}\big{]}\big{\\}}_{i=1}^{K}.$

Observe that
$\sum_{l=1}^{d_{\rho}}\|c_{h}^{l}\|_{\ell^{2}}^{2}=\mathbb{E}(\|\Pi_{K}m(W,h)\|_{\ell^{2}}^{2})$.
Let $C>0$ be such that $\mathbb{P}\big{(}\|\Sigma(W)\|_{op}\leq C\big{)}=1$.
By Cauchy-Schwarz and the definition of $\Theta_{n}$, it follows that

$\displaystyle\sup_{g\in\mathcal{F}}\left|g(W)\right|\leq
C\sup_{h\in\Theta_{n}}\|\Pi_{K}m(W,h)\|_{\ell^{2}}^{2}$ $\displaystyle\leq
C\zeta_{b,K}^{2}\sum_{l=1}^{d_{\rho}}\|c_{h}^{l}\|_{\ell^{2}}^{2}$
$\displaystyle=C\zeta_{b,K}^{2}\mathbb{E}(\|\Pi_{K}m(W,h)\|_{\ell^{2}}^{2})$
$\displaystyle\leq CM\zeta_{b,K}^{2}\gamma_{n}^{2}.$

From the estimate $\zeta_{b,K}\lessapprox\sqrt{K}$, it follows that
$\sup_{g\in\mathcal{F}}\left|g(W)\right|\leq C\gamma_{n}^{2}K$ for some
constant $C<\infty$. It follows that we can take $F=C\gamma_{n}^{2}K$ to be an
envelope of $\mathcal{F}$. From this bound and the definition of $\Theta_{n}$,
we also obtain

$\displaystyle\sup_{g\in\mathcal{F}}\mathbb{E}[g^{2}(W)]\leq
F\sup_{g\in\mathcal{F}}\mathbb{E}[\left|g(W)\right|]\lessapprox
F\sup_{h\in\Theta_{n}}\mathbb{E}(\|\Pi_{K}m(W,h)\|_{\ell^{2}}^{2})\lessapprox\gamma_{n}^{4}K.$

From similar arguments to those employed above, we have for every fixed
$h,h^{\prime}\in\Theta_{n}$, the bound

$\displaystyle\sup_{w}\left|[\Pi_{K}m(w,h)]^{\prime}\Sigma(w)[\Pi_{K}m(w,h)]-[\Pi_{K}m(w,h^{\prime})]^{\prime}\Sigma(w)[\Pi_{K}m(w,h^{\prime})]\right|$
$\displaystyle\lessapprox\sup_{w}\sup_{g\in\Theta_{n}}\left|[\Pi_{K}m(w,h)-\Pi_{K}m(w,h^{\prime})]^{\prime}\Sigma(w)[\Pi_{K}m(w,g)]\right|$
$\displaystyle\lessapprox\sqrt{F}\sup_{w}\|\Pi_{K}m(w,h)-\Pi_{K}m(w,h^{\prime})\|_{\ell^{2}}$
$\displaystyle\lessapprox\gamma_{n}K\sqrt{\mathbb{E}\big{(}\|\Pi_{K}m(W,h)-\Pi_{K}m(W,h^{\prime})\|_{\ell^{2}}^{2}\big{)}}.$
$\displaystyle\lessapprox\gamma_{n}K\sqrt{\mathbb{E}\big{(}\|m(W,h)-m(W,h^{\prime})\|_{\ell^{2}}^{2}\big{)}}.$

In particular, there exists a universal constant $c>0$ such that

$\displaystyle\sup_{Q}\log N(\mathcal{F},\|.\|_{L^{2}(Q)},\tau F)\leq\log
N(\mathcal{M},\|.\|_{L^{2}(\mathbb{P})},c\tau\gamma_{n})\;\;\;\;\;\;\;\forall\;\;\tau\in(0,1)\;\;,$

where the supremum is over all discrete probability measures $Q$ on
$\mathcal{W}$. From an application of (Giné and Nickl, 2021, Theorem 3.5.4),
it follows that

$\displaystyle\mathbb{E}\bigg{(}\sup_{g\in\mathcal{F}}\left|\sum_{i=1}^{n}g(W_{i})-\mathbb{E}g(W)\right|\bigg{)}\lessapprox\sqrt{n}\gamma_{n}^{2}K\mathcal{J}(K^{-1/2})+\gamma_{n}^{2}K^{3}\mathcal{J}^{2}(K^{-1/2}).$

∎

###### Proof of Theorem 4.

Let $C,C^{\prime}$ denote generic universal constants that may change from
line to line. Before proceeding with the proof, we introduce a few
definitions, clarify some notation and state a few preliminary observations
that will be used throughout the proof.

Given a positive semi-definite matrix $\Sigma\in\mathbb{R}^{\rho\times\rho}$,
we denote the inner product and norm induced by $\Sigma$ as $\langle
v,w\rangle_{\Sigma}=v^{\prime}\Sigma w$ and
$\|v\|_{\Sigma}^{2}=v^{\prime}\Sigma v$, respectively. With this notation, the
quasi-Bayes posterior can be expressed as

$\displaystyle\mu(.|\alpha,K,\mathcal{Z}_{n})=\frac{\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,.)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(.|\alpha,K)}{\int\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}.$
(84)

Given functions $h,g:\mathcal{X}\rightarrow\mathbb{R}$, for ease of notation,
we denote the differenced empirical estimate and projection at $(h,g)$ by

$\displaystyle\widehat{m}(W,h-g)=\widehat{m}(W,h)-\widehat{m}(W,g)\;,$ (85)
$\displaystyle\Pi_{K}m(W,h-g)=\Pi_{K}m(W,h)-\Pi_{K}m(W,g).$ (86)

For close variations of $\widehat{m}$ introduced below such as $\widetilde{m}$
in (97), the notation $\widetilde{m}(W,h-g)$ is to be interpreted similar to
(85). Given a function $h:\mathcal{X}\rightarrow\mathbb{R}$ and
$t\in\mathbb{R}$, we denote by $h_{t}$ the quantity

$\displaystyle h_{t}=h-\frac{t}{\sqrt{n}}\tilde{\Phi}.$ (87)

Given a vector $v\in\mathbb{R}^{n}$, we denote the least squares projection of
$v$ onto the subspace spanned by
$\\{b_{1}(W_{i}),\dots,b_{K}(W_{i})\\}_{i=1}^{n}$ by $\widehat{\Pi}_{K}[v]$.
In particular, for every $h:\mathcal{X}\rightarrow\mathbb{R}$ and
$l\in\\{1,\dots,d_{\rho}\\}$, we have

$\displaystyle\widehat{\Pi}_{K}[\\{\rho_{l}(Y_{i},h(X_{i})\\}_{i=1}^{n}]=\\{\widehat{m}(W_{i},h)\\}_{i=1}^{n}.$
(88)

From the representation in (18), the Reproducing Kernel Hilbert Space (RKHS)
associated to the Gaussian random element $G_{\alpha}$ can be represented as

$\displaystyle\mathbb{H}=\bigg{\\{}h\in
L^{2}(\mathcal{X}):\|h\|_{\mathbb{H}}^{2}=\sum_{i=1}^{\infty}i^{1+2\alpha/d}\left|\langle
h,e_{i}\rangle_{L^{2}(\mathcal{X})}\right|^{2}<\infty\bigg{\\}}.$ (89)

From this representation, it is straightforward to verify that the RKHS
$(\mathbb{H}_{n},\|.\|_{\mathbb{H}_{n}})$ of the scaled measure
$\mu(.|\alpha,K)\sim G_{\alpha}/\sqrt{K\log n}$ is given by

$\displaystyle\mathbb{H}_{n}=\bigg{\\{}h\in
L^{2}(\mathcal{X}):\|h\|_{\mathbb{H}_{n}}^{2}=K\log(n)\sum_{i=1}^{\infty}i^{1+2\alpha/d}\left|\langle
h,e_{i}\rangle_{L^{2}(\mathcal{X})}\right|^{2}<\infty\bigg{\\}}.$ (90)

Since $\tilde{\Phi}\in\mathbb{H}$, it follows immediately that
$\tilde{\Phi}\in\mathbb{H}_{n}$. By definition of the RKHS, we have

$h\sim\mu(.|\alpha,K_{n})\implies\langle
h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}\sim
N(0,\|\tilde{\Phi}\|_{\mathbb{H}_{n}}^{2}).$

Define the sequences

$\displaystyle\epsilon_{n}=\frac{\sqrt{K}}{\sqrt{n}}\;\;,\;\;\delta_{n}=\begin{cases}n^{-\frac{\alpha}{2[\alpha+\zeta]+d}}\sqrt{\log
n}&\text{mildly ill-posed}\\\ (\log n)^{-\alpha/\zeta}\sqrt{\log\log
n}&\text{severely ill-posed}.\end{cases}$ (91) $\displaystyle
r_{n}=\begin{cases}(\log n)^{-1}&\text{mildly ill-posed}\\\ (\log\log
n)^{-1}&\text{severely ill-posed.}\end{cases}$

Given any $D,M>0$, define the set $\Theta_{n}=\Theta_{n}(M,D)$ by

$\displaystyle\Theta_{n}=\bigg{\\{}h\in\mathbf{H}^{t}(M):$
$\displaystyle\|m(W,h)\|_{L^{2}(\mathbb{P})}\leq D\sqrt{\log
n}\epsilon_{n},\;\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\ell^{2}}^{2}\big{)}\leq
D^{2}\log(n)\epsilon_{n}^{2},$ (92)
$\displaystyle\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq D\delta_{n}\;,\big{|}\langle
h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}\big{|}\leq M\sqrt{n}\sqrt{\log
n}\epsilon_{n}\|\tilde{\Phi}\|_{\mathbb{H}_{n}},$
$\displaystyle\|h\|_{\mathcal{H}^{\alpha-r_{n}}}\leq
Mr_{n}^{-1/2},\|D_{h_{0}}[h-h_{0}]\|_{L^{2}(\mathbb{P})}\leq D\sqrt{\log
n}\epsilon_{n}\bigg{\\}}.$

The proof proceeds through several steps which we outline below.

  1. $(i)$

From the proof of Theorem 3 and an application of Lemma 3 to the Gaussian
random variable $Z_{n}=\langle h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}$, we can
choose $D,M>0$ large enough such that

$\displaystyle\mu(\Theta_{n}^{c}|\alpha,K,\mathcal{Z}_{n})\leq
e^{-Rn\epsilon_{n}^{2}\log n}$ (93)

holds with $\mathbb{P}$ probability approaching $1$, where $R>0$ is a
universal constant (that depends on $D,M$).

Define the localized posterior measure generated by restricting
$\mu(.|\alpha,K,\mathcal{Z}_{n})$ to $\Theta_{n}$ by

$\displaystyle\mu^{\star}(A|\alpha,K,\mathcal{Z}_{n})=\frac{\int_{A\cap\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{[}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{]}\big{missing})d\mu(h|\alpha,K)}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{[}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{]}\big{missing})d\mu(h|\alpha,K)}$
(94)

for every Borel set $A$. If $\|.\|_{TV}$ denotes the total variation metric,
it follows that

$\displaystyle\|\mu(.|\alpha,K,\mathcal{Z}_{n})-\mu^{\star}(.|\alpha,K,\mathcal{Z}_{n})\|_{TV}\leq
2\mu(\Theta_{n}^{c}|\alpha,K,\mathcal{Z}_{n})\xrightarrow{\mathbb{P}}0.$ (95)

Therefore, it suffices to verify the weak convergence under the localized
measure $\mu^{\star}(.|\alpha,K,\mathcal{Z}_{n})$.

  2. $(ii)$

We verify that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}\right|=o_{\mathbb{P}}(n^{-1}).$

This proceeds in several steps. From the definition of $\Theta_{n}$, we have
that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\Sigma(W)}^{2}\big{)}\right|$
$\displaystyle\leq\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\ell^{2}}^{2}\|\widehat{\Sigma}(W)-\Sigma(W)\|_{op}\big{)}$
$\displaystyle\leq\sup_{w\in\mathcal{W}}\|\widehat{\Sigma}(w)-\Sigma(w)\|_{op}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\ell^{2}}^{2}\big{)}$
$\displaystyle=\epsilon_{n}^{2}\log(n)O_{\mathbb{P}}\bigg{(}\sup_{w\in\mathcal{W}}\|\widehat{\Sigma}(w)-\Sigma(w)\|_{op}\bigg{)}$
$\displaystyle=n^{-1}O_{\mathbb{P}}\big{(}\gamma_{n}\log(n)K_{n}\big{)}$
$\displaystyle=n^{-1}o_{\mathbb{P}}(1).$

For any fixed $h:\mathcal{X}\rightarrow\mathbb{R}$, the estimator
$\widehat{m}(w,h)$ can be expressed as

$\displaystyle\widehat{m}(w,h)=\mathbb{E}_{n}\big{(}\rho(Y,h(X))\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}[\widehat{G}_{b,K}^{o}]^{-1}G_{b,K}^{-1/2}b^{K}(w).$
(96)

It follows that

$\displaystyle\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\ell^{2}}^{2}\big{)}=\sum_{l=1}^{d_{\rho}}[\mathbb{E}_{n}(R_{h,l}^{K})]^{\prime}[\widehat{G}_{b,K}^{o}]^{-1}[\mathbb{E}_{n}(R_{h,l}^{K})]$
$\displaystyle
R_{h,l}^{K}(Z)=\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}\rho_{l}(Y,h(X)).$

By replacing $\widehat{G}_{b,K}^{o}$ with its population analog $I_{K}$, we
define

$\displaystyle\widetilde{m}(w,h)=\mathbb{E}_{n}\big{(}\rho(Y,h(X))\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}G_{b,K}^{-1/2}b^{K}(w).$
(97)

Observe that

$\displaystyle\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)-\widetilde{m}(W,h)\|_{\ell^{2}}^{2}\big{)}\leq\bigg{(}\sum_{l=1}^{d_{\rho}}[\mathbb{E}_{n}(R_{h,l}^{K})]^{\prime}[\mathbb{E}_{n}(R_{h,l}^{K})]\bigg{)}\|\big{(}[\widehat{G}_{b,K}^{o}]^{-1}-I\big{)}\|_{op}^{2}\|\widehat{G}_{b,K}^{o}\|_{op}.$

With $\mathbb{P}$ probability approaching $1$, an application of Lemma 2
implies that the first term on the right is bounded above (up to a constant)
by $\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\ell^{2}}^{2}\big{)}$.
Similarly, the second term has asymptotic rate $\sqrt{K}\sqrt{\log
K}/\sqrt{n}$ and the third term is bounded above by a constant. By Assumption
4.2$(iii)$, the eigenvalues of $\Sigma(W)$ are bounded above with probability
$1$. By Cauchy-Schwarz and the definition of $\Theta_{n}$, it follows that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{[}\widehat{m}(W,h-h_{0})\Sigma(W)\widehat{m}(W,h-h_{0})\big{]}-\mathbb{E}_{n}\big{[}\widetilde{m}(W,h-h_{0})\Sigma(W)\widetilde{m}(W,h-h_{0})\big{]}\right|$
$\displaystyle=O_{\mathbb{P}}\bigg{(}\sup_{h\in\Theta_{n}}\sqrt{\mathbb{E}_{n}\|\widehat{m}(W,h)-\widetilde{m}(W,h)\|_{\ell^{2}}^{2}}\sqrt{\mathbb{E}_{n}\|\widehat{m}(W,h)\|_{\ell^{2}}^{2}}\bigg{)}$
$\displaystyle=O_{\mathbb{P}}\big{(}\|[\widehat{G}_{b,K}^{o}]^{-1}-I_{K}\|_{op}\big{)}\log(n)\epsilon_{n}^{2}$
$\displaystyle=n^{-1}O_{\mathbb{P}}\bigg{(}\frac{\log(n)K\sqrt{K\log
K}}{\sqrt{n}}\bigg{)}.$

Since $\log(n)K\sqrt{K\log K}/\sqrt{n}=o(1)$, the preceding term is
$o_{\mathbb{P}}(n^{-1}).$

Observe that $\Pi_{K}m(w,h)$ can be expressed as

$\displaystyle\Pi_{K}m(w,h)=\mathbb{E}\big{(}\rho(Y,h(X))\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}G_{b,K}^{-1/2}b^{K}(w).$
(98)

By Lemma 2, 8 and Condition $\ref{misc1}(ii)$, there exists a sequence $r_{n}$
satisfying $r_{n}\sqrt{K_{n}}\sqrt{\log n}\downarrow 0$ such that

$\displaystyle\sup_{h\in\Theta_{n}}\mathbb{E}_{n}\|\widetilde{m}(W,h-h_{0})-\Pi_{K}m(W,h-h_{0})\|_{\ell^{2}}^{2}$
$\displaystyle\leq\sup_{h\in\Theta_{n}}\bigg{(}\sum_{l=1}^{d_{\rho}}\|\mathbb{E}_{n}(R_{h,l}^{K})-\mathbb{E}(R_{h,l}^{K})\|_{\ell^{2}}^{2}\bigg{)}\|\widehat{G}_{b,K}^{o}\|_{op}$
$\displaystyle=O_{\mathbb{P}}\big{(}n^{-1}r_{n}^{2}\big{)}.$

By Cauchy-Schwarz, it follows that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{[}\widetilde{m}(W,h-h_{0})\Sigma(W)\widetilde{m}(W,h-h_{0})\big{]}-\mathbb{E}_{n}\big{[}\Pi_{K}m(W,h-h_{0})\Sigma(W)\Pi_{K}m(W,h-h_{0})\big{]}\right|$
$\displaystyle=O_{\mathbb{P}}\bigg{(}\sup_{h\in\Theta_{n}}\sqrt{\mathbb{E}_{n}\|\widetilde{m}(W,h)-\Pi_{K}m(W,h)\|_{\ell^{2}}^{2}}\sqrt{\mathbb{E}_{n}\|\widetilde{m}(W,h)\|_{\ell^{2}}^{2}}\bigg{)}$
$\displaystyle=O_{\mathbb{P}}\big{(}n^{-1/2}r_{n}\sqrt{\log
n}\epsilon_{n}\big{)}$
$\displaystyle=n^{-1}O_{\mathbb{P}}\big{(}r_{n}\sqrt{\log
n}\sqrt{K_{n}}\big{)}$ $\displaystyle=n^{-1}o_{\mathbb{P}}(1).$

Finally, by Lemma 9 and Condition 4.6$(i)$, we obtain

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}-\mathbb{E}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}\right|$
$\displaystyle=o_{\mathbb{P}}(n^{-1}).$

  3. $(ii)$

We verify that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}-\mathbb{E}\big{(}\Pi_{K}D_{h_{0}}[h-h_{0}]^{\prime}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{0}]\big{)}\right|=o(n^{-1}).$

Denote the remainder obtained from linearizing the map at $h$ by

$\displaystyle R_{h_{0}}(h,W)=m(W,h)-m(W,h_{0})-D_{h_{0}}[h-h_{0}].$ (99)

Observe that

$\displaystyle\mathbb{E}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}-\mathbb{E}\big{(}\Pi_{K}D_{h_{0}}[h-h_{0}]^{\prime}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{0}]\big{)}$
$\displaystyle=\mathbb{E}\big{[}\Pi_{K}R_{h_{0}}(h,W)^{\prime}\Sigma(W)\Pi_{K}R_{h_{0}}(h,W)\big{]}+2\mathbb{E}\big{[}\Pi_{K}R_{h_{0}}(h,W)^{\prime}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{0}]\big{]}.$

Since the eigenvalues of $\Sigma(.)$ are uniformly bounded above, Cauchy-
Schwarz yields

$\displaystyle
n\sup_{h\in\Theta_{n}}\left|\mathbb{E}\big{\\{}\Pi_{K}m(W,h)^{\prime}\Sigma(W)\Pi_{K}m(W,h)\big{\\}}-\mathbb{E}\big{(}\Pi_{K}D_{h_{0}}[h-h_{0}]^{\prime}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{0}]\big{)}\right|$
$\displaystyle\lessapprox
n\sup_{h\in\Theta_{n}}\bigg{[}\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}^{2}+\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}\|\Pi_{K}D_{h_{0}}[h-h_{0}]\|_{L^{2}(\mathbb{P})}\bigg{]}$
$\displaystyle\lessapprox
n\sup_{h\in\Theta_{n}}\bigg{[}\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}^{2}+\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}\sqrt{\log
n}\epsilon_{n}\bigg{]}$
$\displaystyle=n\sup_{h\in\Theta_{n}}\bigg{[}\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}^{2}+\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}\sqrt{\log
n}\sqrt{K}n^{-1/2}\bigg{]}.$

The preceding quantity is $o(1)$ by Condition 4.6$(iii)$.

  4. $(iii)$

By repeating the argument from parts $(i-ii)$, we similarly obtain for every
fixed $t\in\mathbb{R}$, the estimate

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t}-h_{0})\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}\big{(}\Pi_{K}D_{h_{0}}[h_{t}-h_{0}]^{\prime}\Sigma(W)\Pi_{K}D_{h_{0}}[h_{t}-h_{0}]\big{)}\right|$
$\displaystyle=o_{\mathbb{P}}(n^{-1}).$

  5. $(iv)$

Define

$\displaystyle
S_{n}=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),D_{h_{0}}[\tilde{\Phi}](W)\rangle_{\Sigma(W)}\big{]}.$
(100)

For any fixed $t\in\mathbb{R}$, we aim to verify that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{(}\langle\widehat{m}(W,h_{0}),\widehat{m}(W,h-h_{t})\rangle_{\widehat{\Sigma}(W)}\big{)}-\frac{t}{\sqrt{n}}S_{n}\right|=o_{\mathbb{P}}(n^{-1}).$
(101)

By a similar argument to parts $(i-ii)$, it is straightforward to verify that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\widehat{m}(W,h-h_{t})\rangle_{\widehat{\Sigma}(W)}\big{]}-\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\widehat{m}(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}\right|=o_{\mathbb{P}}(n^{-1})$
$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\widehat{m}(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}-\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\Pi_{K}m(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}\right|=o_{\mathbb{P}}(n^{-1}).$

By orthogonality of the least squares projection, we can write

$\displaystyle\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\Pi_{K}m(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}$
$\displaystyle=\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\Sigma(W)\Pi_{K}m(W,h-h_{t})\rangle\big{]}$
$\displaystyle=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\widehat{\Pi}_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}\;,$

where $\widehat{\Pi}_{K}$ is the operator as defined in (88). By interchanging
$\mathbb{E}_{n}$ and the inner product, the preceding term can be expressed as
an inner product of two vectors in $\mathbb{R}^{d_{\rho}}$. In particular,
$\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\Pi_{K}m(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}=\sum_{i=1}^{d_{\rho}}V_{i}$
where

$\displaystyle
V_{l}=\mathbb{E}_{n}\big{(}[\Sigma(W)\Pi_{K}m(W,h-h_{t})]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}[\widehat{G}_{b,K}^{o}]^{-1}\frac{1}{n}\sum_{i=1}^{n}G_{b,K}^{-1/2}b^{K}(W_{i})\rho_{l}(Y_{i},h_{0}(X_{i})).$

Similarly, we can express
$\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}$
as $\sum_{i=1}^{d_{\rho}}\widetilde{V}_{i}$ where

$\displaystyle\widetilde{V}_{l}=\mathbb{E}\big{(}[\Sigma(W)\Pi_{K}m(W,h-h_{t})]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}\frac{1}{n}\sum_{i=1}^{n}G_{b,K}^{-1/2}b^{K}(W_{i})\rho_{l}(Y_{i},h_{0}(X_{i})).$

The $\|.\|_{\ell^{2}}$ norm of the sample average on the right is of order
$\sqrt{K}/\sqrt{n}$ (by Lemma 5). As the eigenvalues of $\Sigma(.)$ are
uniformly bounded above, a straightforward application of Lemma 8 and
Condition 4.6$(ii)$ implies that

$\displaystyle\mathbb{E}\bigg{[}\sup_{h\in\Theta_{n}}\|(\mathbb{E}_{n}-\mathbb{E})\big{(}[\Sigma(W)\Pi_{K}m(W,h-h_{t})]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}\|_{\ell^{2}}\bigg{]}\leq\frac{r_{n}}{\sqrt{n}}$

for some sequence $r_{n}$ satisfying $r_{n}\sqrt{K}\sqrt{\log n}\downarrow 0$.
Furthermore, by Lemma 2, we have
$\|[\widehat{G}_{b,K}^{o}]^{-1}-I_{K}\|_{op}\leq C\sqrt{K\log(K)}/\sqrt{n}$
with $\mathbb{P}$ probability approaching $1$. From combining the preceding
bounds and an application of Cauchy-Schwarz, we obtain

$\displaystyle\sup_{h\in\Theta_{n}}\left|\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\Pi_{K}m(W,h-h_{t})\rangle_{\Sigma(W)}\big{]}-\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}\right|$
$\displaystyle=o_{\mathbb{P}}(n^{-1}).$

Next, write $m(W,h)=R_{h_{0}}(h,W)+D_{h_{0}}[h-h_{0}]$ to obtain

$\displaystyle\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}$
$\displaystyle=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}R_{h_{0}}(h,W)\big{]}\rangle\big{]}-\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}R_{h_{0}}(h_{t},W)\big{]}\rangle\big{]}$
$\displaystyle+\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{t}]\big{]}\rangle\big{]}.$

By interchanging $\mathbb{E}_{n}$ and the inner product as above, the first
two terms on the right side of the equality can be analyzed through the terms

$\displaystyle
Q_{i,1}=\mathbb{E}\big{(}[\Sigma(W)\Pi_{K}R_{h_{0}}(h,W)]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}\frac{1}{n}\sum_{i=1}^{n}G_{b,K}^{-1/2}b^{K}(W_{i})\rho_{l}(Y_{i},h_{0}(X_{i}))\;,$
$\displaystyle
Q_{i,2}=-\mathbb{E}\big{(}[\Sigma(W)\Pi_{K}R_{h_{0}}(h_{t},W)]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}^{\prime}\big{)}\frac{1}{n}\sum_{i=1}^{n}G_{b,K}^{-1/2}b^{K}(W_{i})\rho_{l}(Y_{i},h_{0}(X_{i})).$

The $\|.\|_{\ell^{2}}$ norm of the sample average on the right of both the
preceding terms is of order $\sqrt{K}/\sqrt{n}$ (by Lemma 5). Furthermore, by
the Bessel inequality, we obtain

$\displaystyle\|\mathbb{E}\big{(}[\Sigma(W)\Pi_{K}R_{h_{0}}(h,W)]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}\|_{\ell^{2}}^{2}\leq\|[\Sigma(W)\Pi_{K}R_{h_{0}}(h,W)]_{l}\|_{L^{2}(\mathbb{P})}^{2}\;,$
$\displaystyle\|\mathbb{E}\big{(}[\Sigma(W)\Pi_{K}R_{h_{0}}(h_{t},W)]_{l}\big{[}G_{b,K}^{-1/2}b^{K}(W)\big{]}\|_{\ell^{2}}^{2}\leq\|[\Sigma(W)\Pi_{K}R_{h_{0}}(h_{t},W)]_{l}\|_{L^{2}(\mathbb{P})}^{2}.$

As the eigenvalues of $\Sigma(.)$ are uniformly bounded above, the preceding
bounds imply the expansion

$\displaystyle\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}$
$\displaystyle=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{t}]\big{]}\rangle\big{]}$
$\displaystyle+\frac{\sqrt{K}}{\sqrt{n}}O_{\mathbb{P}}\bigg{(}\sup_{h\in\Theta_{n}}\|\Pi_{K}R_{h_{0}}(h,W)\|_{L^{2}(\mathbb{P})}+\sup_{h\in\Theta_{n}}\|\Pi_{K}R_{h_{0}}(h_{t},W)\|_{L^{2}(\mathbb{P})}\bigg{)}$

uniformly over $h\in\Theta_{n}$. Hence, by Condition 4.6$(iii)$, it follows
that

$\displaystyle\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}m(W,h-h_{t})\big{]}\rangle\big{]}$
$\displaystyle=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{t}]\big{]}\rangle\big{]}+o_{\mathbb{P}}(n^{-1})$

uniformly over $h\in\Theta_{n}$. By construction
$h-h_{t}=t\tilde{\Phi}/\sqrt{n}$ and $D_{h_{0}}(.)$ is a linear operator. It
follows that the preceding term can be expressed as

$\displaystyle\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[h-h_{t}]\big{]}\rangle\big{]}=\
\frac{t}{\sqrt{n}}\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\big{]}\rangle\big{]}.$

Hence, to show (101), it suffices to verify that

$\displaystyle\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Pi_{K}\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\big{]}\rangle\big{]}=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\rangle\big{]}+o_{\mathbb{P}}(n^{-1/2}).$
(102)

Observe that the sample mean is over a mean zero random variable, since
$\mathbb{E}[\rho(Y,h_{0}(X))|W]=m(W,h_{0})=0$. Furthermore, since
$\mathbb{E}\big{(}\|\rho(Y,h_{0}(X))\|_{\ell^{2}}^{2}|W)$ is bounded above
(with $\mathbb{P}$ probability $1$), we have that

$\displaystyle
n\mathbb{E}\left|\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),(\Pi_{K}-I)\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[\tilde{\Phi}](W)\big{]}\rangle]\right|^{2}$
$\displaystyle=\mathbb{E}\bigg{(}\left|\langle\rho(Y,h_{0}(X)),(\Pi_{K}-I)\big{[}\Sigma(W)\Pi_{K}D_{h_{0}}[\tilde{\Phi}](W)\big{]}\rangle\right|^{2}\bigg{)}$
$\displaystyle\rightarrow 0.$

Similarly, we obtain

$\displaystyle
n\mathbb{E}\left|\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),\big{[}\Sigma(W)(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}](W)\big{]}\rangle]\right|^{2}$
$\displaystyle=\mathbb{E}\bigg{(}\left|\langle\rho(Y,h_{0}(X)),\big{[}\Sigma(W)(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}](W)\big{]}\rangle\right|^{2}\bigg{)}$
$\displaystyle\rightarrow 0.$

The expression in $(\ref{sn-verify-new})$ follows by Markov’s inequality.

  6. $(v)$

The preceding steps $(i-iv)$ show that

$\displaystyle\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}$
$\displaystyle=\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h-h_{0})\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t}-h_{0})\|_{\widehat{\Sigma}(W)}^{2}\big{)}+2\mathbb{E}_{n}\big{[}\langle\widehat{m}(W,h_{0}),\widehat{m}(W,h-h_{t})\rangle_{\widehat{\Sigma}(W)}\big{]}$
$\displaystyle=\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[h-h_{0}]\|_{\Sigma(W)}^{2}\big{)}-\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[h_{t}-h_{0}]\|_{\Sigma(W)}^{2}\big{)}+2\frac{t}{\sqrt{n}}S_{n}+o_{\mathbb{P}}(n^{-1})$

uniformly over $h\in\Theta_{n}$, where $S_{n}$ is as in (100). Furthermore,
since $D_{h_{0}}(.)$ is a linear operator, we obtain

$\displaystyle\frac{n}{2}\bigg{[}\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[h-h_{0}]\|_{\Sigma(W)}^{2}\big{)}-\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[h_{t}-h_{0}]\|_{\Sigma(W)}^{2}\big{)}\bigg{]}$
$\displaystyle=-\frac{t^{2}}{2}\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\|_{\Sigma(W)}^{2}\big{)}+t\sqrt{n}\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\rangle_{\Sigma(W)}\big{]}.$

For the first term, continuity yields

$-\frac{t^{2}}{2}\mathbb{E}\big{(}\|\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\|_{\Sigma(W)}^{2}\big{)}=-\frac{t^{2}}{2}\mathbb{E}\big{(}\|D_{h_{0}}[\tilde{\Phi}]\|_{\Sigma(W)}^{2}\big{)}+o(1).$

For the second term, we expand it as

$\displaystyle\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\rangle_{\Sigma(W)}\big{]}$
$\displaystyle=\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}\big{\\{}\Sigma(W)\Pi_{K}D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}$
$\displaystyle=\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}\big{\\{}\Sigma(W)(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}+\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}\big{\\{}\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}.$

Since the eigenvalues of $\Sigma(.)$ are uniformly bounded above, Cauchy-
Schwarz yields

$\displaystyle\sup_{h\in\Theta_{n}}\sqrt{n}\left|\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}\big{\\{}\Sigma(W)(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}\right|$
$\displaystyle\lessapprox\sqrt{n}\epsilon_{n}\sqrt{\log
n}\|(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}]\|_{L^{2}(\mathbb{P})}$
$\displaystyle=\sqrt{K}\sqrt{\log
n}\|(\Pi_{K}-I)D_{h_{0}}[\tilde{\Phi}]\|_{L^{2}(\mathbb{P})}$
$\displaystyle=o(1).$

Next, by orthogonality we have that

$\displaystyle\mathbb{E}\big{[}\langle\Pi_{K}D_{h_{0}}[h-h_{0}],\Pi_{K}\big{\\{}\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}$
$\displaystyle=\mathbb{E}\big{[}\langle
D_{h_{0}}[h-h_{0}],\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\rangle\big{]}+\mathbb{E}\big{[}\langle(\Pi_{K}-I)D_{h_{0}}[h-h_{0}],(\Pi_{K}-I)\big{\\{}\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}.$

By Cauchy-Schwarz, we obtain

$\displaystyle\sup_{h\in\Theta_{n}}\sqrt{n}\left|\mathbb{E}\big{[}\langle(\Pi_{K}-I)D_{h_{0}}[h-h_{0}],(\Pi_{K}-I)\big{\\{}\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\big{\\}}\rangle\big{]}\right|$
$\displaystyle\lessapprox\sqrt{n}\epsilon_{n}\sqrt{\log
n}\|(\Pi_{K}-I)\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\|_{L^{2}(\mathbb{P})}$
$\displaystyle=\sqrt{K}\sqrt{\log
n}\|(\Pi_{K}-I)\Sigma(W)D_{h_{0}}[\tilde{\Phi}]\|_{L^{2}(\mathbb{P})}$
$\displaystyle=o(1).$

From combining the preceding bounds, we obtain the expansion

$\displaystyle\frac{-n}{2}\bigg{[}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\bigg{]}$
$\displaystyle=\frac{t^{2}}{2}\mathbb{E}\big{(}\|D_{h_{0}}[\tilde{\Phi}]\|_{\Sigma(W)}^{2}\big{)}-t\sqrt{n}\mathbb{E}\big{[}\langle
D_{h_{0}}[h-h_{0}],D_{h_{0}}[\tilde{\Phi}]\rangle_{\Sigma(W)}\big{]}-t\sqrt{n}S_{n}+o_{\mathbb{P}}(1)$

uniformly over $h\in\Theta_{n}$. Furthermore, by definition of the adjoint
$D_{h_{0}}^{*}$ and Condition 4.8$(i)$, we can write

$\displaystyle t\sqrt{n}\mathbb{E}\big{[}\langle
D_{h_{0}}[h-h_{0}],D_{h_{0}}[\tilde{\Phi}]\rangle_{\Sigma(W)}\big{]}$
$\displaystyle=t\sqrt{n}\langle
h-h_{0},D_{h_{0}}^{*}D_{h_{0}}[\tilde{\Phi}]\rangle_{L^{2}(\mathbb{P})}$
$\displaystyle=t\sqrt{n}\langle h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}.$

  7. $(vi)$

We compute the Laplace transform of the random variable
$\sqrt{n}\big{[}\langle h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}+S_{n}\big{]}$
where $h\sim\mu^{*}(.|\alpha,K,\mathcal{Z}_{n})$. Fix any $t\in\mathbb{R}$.
From the conclusion of part $(v)$, the Laplace transform is

$\displaystyle\mathbb{E}^{*}\bigg{[}\exp\\{t\sqrt{n}\big{[}\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}+S_{n}\big{]}\bigg{\\}}\bigg{|}\alpha,K,\mathcal{Z}_{n}\bigg{]}$
$\displaystyle=\frac{\int_{\Theta_{n}}\exp\\{t\sqrt{n}\big{[}\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}+S_{n}\big{]}\bigg{\\}}\exp\\{-\frac{n}{2}\bigg{[}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}-\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\bigg{]}\bigg{\\}}}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}$
$\displaystyle\times\exp\\{-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\bigg{\\}}d\mu(h|\alpha,K)$
$\displaystyle=\exp[\frac{t^{2}}{2}\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\Sigma(W)(D_{h_{0}}\tilde{\Phi})\big{]}+o_{\mathbb{P}}(1)\bigg{]}\times\frac{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}.$

Next, we verify that

$\displaystyle\frac{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}\xrightarrow{\mathbb{P}}1.$

Let $\mu_{t,\tilde{\Phi}}(h|\alpha,K)$ denote the measure obtained from
translating $\mu(.|\alpha,K)$ around $t\tilde{\Phi}/\sqrt{n}$. To be specific,
it is the measure obtained via

$\mu_{t,\tilde{\Phi}}(h|\alpha,K)\sim\frac{G_{\alpha}}{\sqrt{K}\sqrt{\log
n}}-\frac{t}{\sqrt{n}}\tilde{\Phi}.$

Since $\tilde{\Phi}\in\mathbb{H}$, it follows from (Ghosal and Van der Vaart,
2017, Proposition I.20) that $\mu_{t,\tilde{\Phi}}(h|\alpha,K)$ is absolutely
continuous with respect to $\mu(.|\alpha,K)$ and admits a density function

$\displaystyle\frac{d\mu_{t,\tilde{\Phi}}(h|\alpha,K)}{d\mu(h|\alpha,K)}=\exp\\{\frac{t}{\sqrt{n}}\langle
h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}-\frac{t^{2}}{2n}\|\tilde{\Phi}\|_{\mathbb{H}_{n}}^{2}\bigg{\\}}.$
(103)

From the definition of $\Theta_{n}$, we have

$\displaystyle\sup_{h\in\Theta_{n}}\left|\frac{t}{\sqrt{n}}\langle
h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}\right|\leq
M\frac{t}{\sqrt{n}}\sqrt{n}\sqrt{\log
n}\epsilon_{n}\|\tilde{\Phi}\|_{\mathbb{H}_{n}}$ $\displaystyle=Mt\sqrt{\log
n}\epsilon_{n}\|\tilde{\Phi}\|_{\mathbb{H}_{n}}=Mt\epsilon_{n}\log(n)\sqrt{K}\|\tilde{\Phi}\|_{\mathbb{H}}\;,$

where we used the fact that
$\|\tilde{\Phi}\|_{\mathbb{H}_{n}}=\sqrt{K\log(n)}\|\tilde{\Phi}\|_{\mathbb{H}}$.
It follows that

$\displaystyle\sup_{h\in\Theta_{n}}\left|\frac{t}{\sqrt{n}}\langle
h,\tilde{\Phi}\rangle_{\mathbb{H}_{n}}\right|\lessapprox\frac{K\log(n)}{\sqrt{n}}=o(1)\;,$
$\displaystyle\frac{t^{2}}{2n}\|\tilde{\Phi}\|_{\mathbb{H}_{n}}^{2}\lessapprox\frac{K\log(n)}{\sqrt{n}}=o(1).$

Define

$\Theta_{n,\tilde{\Phi}}=\Theta_{n}-\frac{t}{\sqrt{n}}\tilde{\Phi}=\bigg{\\{}g:g=h-\frac{t}{\sqrt{n}}\tilde{\Phi}\;,h\in\Theta_{n}\bigg{\\}}.$

By Gaussian change of variables in (103) and the preceding bounds, we obtain

$\displaystyle\frac{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}=e^{o(1)}\frac{\mu(\Theta_{n,\tilde{\Phi}}|\alpha,K,\mathcal{Z}_{n})}{\mu(\Theta_{n}|\alpha,K,\mathcal{Z}_{n})}.$

Since $\mu(\Theta_{n}^{c}|\alpha,K,\mathcal{Z}_{n})\xrightarrow{\mathbb{P}}0$,
the preceding expression reduces to

$\displaystyle\frac{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h_{t})\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}{\int_{\Theta_{n}}\exp\big(-\frac{n}{2}\mathbb{E}_{n}\big{(}\|\widehat{m}(W,h)\|_{\widehat{\Sigma}(W)}^{2}\big{)}\big{missing})d\mu(h|\alpha,K)}=e^{o(1)}\frac{\mu(\Theta_{n,\tilde{\Phi}}|\alpha,K,\mathcal{Z}_{n})}{1+o_{\mathbb{P}}(1)}.$

By replacing $D,M$ in the definition of $\Theta_{n}$ in (92) with a larger
$D^{\prime},M^{\prime}$ if necessary, it is straightforward to verify that
$\mu(\Theta_{n,\tilde{\Phi}}|\alpha,K,\mathcal{Z}_{n})\xrightarrow{\mathbb{P}}1$.
From combining the preceding bounds, we obtain

$\displaystyle\mathbb{E}^{*}\bigg{[}\exp\\{t\sqrt{n}\big{[}\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}+S_{n}\big{]}\bigg{\\}}\bigg{|}\alpha,K,\mathcal{Z}_{n}\bigg{]}$
(104)
$\displaystyle=\exp[\frac{t^{2}}{2}\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\Sigma(W)(D_{h_{0}}\tilde{\Phi})\big{]}\bigg{]}[1+o_{\mathbb{P}}(1)].$

Since this is true for every $t\in\mathbb{R}$, it follows from (Castillo and
Rousseau, 2015, Lemma 1) and (95) that

$\displaystyle\sqrt{n}\big{(}\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}+S_{n}\big{)}\big{|}\mathcal{Z}_{n}\overset{\mathbb{P}}{\rightsquigarrow}N\big{(}0,\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\Sigma(D_{h_{0}}\tilde{\Phi})\big{]}\big{)}.$
(105)

  8. $(vii)$

Recall that

$\displaystyle
S_{n}=\mathbb{E}_{n}\big{[}\langle\rho(Y,h_{0}(X)),D_{h_{0}}[\tilde{\Phi}](W)\rangle_{\Sigma(W)}\big{]}.$
(106)

Since $S_{n}$ is the sample mean of a mean zero random variable with finite
variance, note that $n\mathbb{E}[S_{n}^{2}]=O(1)$. From (105) and Lemma 10, it
follows from a uniform integrability in probability argument (see e.g. Monard
et al. (2021b)) that

$\displaystyle\langle\mathbb{E}\big{[}h|\alpha,K,\mathcal{Z}_{n}\big{]},\Phi\rangle_{L^{2}(\mathbb{P})}=\langle
h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}-S_{n}+o_{\mathbb{P}}(n^{-1/2}).$ (107)

The first implication of this is that by substituting this identity back into
(105), we obtain

$\displaystyle\sqrt{n}\langle
h-\mathbb{E}\big{[}h|\alpha,K,\mathcal{Z}_{n}\big{]},\Phi\rangle\big{|}\mathcal{Z}_{n}\overset{\mathbb{P}}{\rightsquigarrow}N\big{(}0,\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\Sigma(D_{h_{0}}\tilde{\Phi})\big{]}\big{)}.$

The second implication is that
$\sqrt{n}\langle\mathbb{E}\big{[}h|\alpha,K,\mathcal{Z}_{n}\big{]}-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}$
is asymptotically equivalent to $-\sqrt{n}S_{n}$. Hence, by the central limit
theorem, we obtain

$\displaystyle\sqrt{n}\langle
h_{0}-\mathbb{E}\big{[}h|\alpha,K,\mathcal{Z}_{n}\big{]},\Phi\rangle=\sqrt{n}S_{n}+o_{\mathbb{P}}(1)\rightsquigarrow$
$\displaystyle
N(0,\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\Sigma\rho\rho^{\prime}\Sigma(D_{h_{0}}\tilde{\Phi})\big{]}).$

The claim follows.

∎

######  Lemma 10.

Suppose the hypothesis of Theorem 4 holds. Then

$\displaystyle n\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\bigg{|}\alpha,K,\mathcal{Z}_{n}\bigg{]}=O_{\mathbb{P}}(1).$

###### Proof of Lemma 10.

Let $C$ denote a generic universal constant that may change from line to line.
Define the sequences

$\displaystyle\epsilon_{n}=\frac{\sqrt{K_{n}}}{\sqrt{n}}\;\;,\;\;\delta_{n}=\begin{cases}n^{-\frac{\alpha}{2[\alpha+\zeta]+d}}\sqrt{\log
n}&\text{mildly ill-posed}\\\ (\log n)^{-\alpha/\zeta}\sqrt{\log\log
n}&\text{severely ill-posed}.\end{cases}$ (108)

First, we state a few preliminary observations from the proof of Theorem 3.
There exists a universal constant $c>0$ such that

$\displaystyle\int\exp\bigg(-\frac{n}{2}\mathbb{E}_{n}\big{[}\widehat{m}(W,h)^{\prime}\widehat{\Sigma}(W)\widehat{m}(W,h)\big{]}\bigg{missing})d\mu(h|\alpha,K)\geq\exp\big(-cn\log(n)\epsilon_{n}^{2}\big{missing})$
(109)

holds with $\mathbb{P}$ probability approaching $1$. Furthermore, for every
$E^{\prime}>0$, there exists a sufficiently large $E$ (which depends on
$E^{\prime}$) such that

$\displaystyle\mu\big{(}\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq
E\delta_{n}\big{|}\alpha,K,\mathcal{Z}_{n}\big{)}\geq
1-\exp(-E^{\prime}n\log(n)\epsilon_{n}^{2})$ (110)

holds with $\mathbb{P}$ probability approaching $1$.

Fix any $E^{\prime}>c$ and let $E$ be as specified above. Write

$\displaystyle\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\bigg{|}\mathcal{Z}_{n}\bigg{]}$
$\displaystyle=\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\mathbbm{1}\\{\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq
E\delta_{n}\\}\bigg{|}\mathcal{Z}_{n}\bigg{]}$
$\displaystyle+\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\mathbbm{1}\\{\|h-h_{0}\|_{L^{2}(\mathbb{P})}>E\delta_{n}\\}\bigg{|}\mathcal{Z}_{n}\bigg{]}$
$\displaystyle=A_{1}+A_{2}.$

For $A_{2}$, Cauchy-Schwarz yields

$\displaystyle A_{2}^{2}\leq\bigg{(}\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{4}\bigg{|}\alpha,K,\mathcal{Z}_{n}\bigg{]}\bigg{)}\mu\big{(}\|h-h_{0}\|_{L^{2}(\mathbb{P})}>E\delta_{n}\big{|}\alpha,K,\mathcal{Z}_{n}\big{)}.$

From $(\ref{lb-newproof})$, we obtain

$\displaystyle\mathbb{E}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{4}\bigg{|}\mathcal{Z}_{n}\bigg{]}$
$\displaystyle=\frac{\int\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{4}\exp\bigg(-\frac{n}{2}\mathbb{E}_{n}\big{[}\widehat{m}(W,h)^{\prime}\widehat{\Sigma}(W)\widehat{m}(W,h)\big{]}\bigg{missing})d\mu(h|\alpha,K)}{\int\exp\bigg(-\frac{n}{2}\mathbb{E}_{n}\big{[}\widehat{m}(W,h)^{\prime}\widehat{\Sigma}(W)\widehat{m}(W,h)\big{]}\bigg{missing})d\mu(h|\alpha,K)}$
$\displaystyle\leq\exp(cn\log(n)\epsilon_{n}^{2})\int\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{4}\exp\bigg(-\frac{n}{2}\mathbb{E}_{n}\big{[}\widehat{m}(W,h)^{\prime}\widehat{\Sigma}(W)\widehat{m}(W,h)\big{]}\bigg{missing})d\mu(h|\alpha,K)$
$\displaystyle\leq\exp(cn\log(n)\epsilon_{n}^{2})\|\Phi\|_{L^{2}(\mathbb{P})}^{4}\int\|h-h_{0}\|_{L^{2}(\mathbb{P})}^{4}d\mu(h|\alpha,K)$
$\displaystyle\leq C\exp(cn\log(n)\epsilon_{n}^{2}).$

Hence, by (110) it follows that

$\displaystyle A_{2}^{2}\leq C\exp((c-E^{\prime})n\log(n)\epsilon_{n}^{2}).$

Since $E^{\prime}>c$, it follows that $nA_{2}=o_{\mathbb{P}}(1)$.

Let $\Theta_{n}$ be defined as (92). In particular, by $(\ref{theta-n-
bound})$, we have $\mu(\Theta_{n}^{c}|\alpha,K,\mathcal{Z}_{n})\leq
e^{-Rn\epsilon_{n}^{2}\log n}$ for some universal constant $R>0$. We denote by
$\mathbb{E}^{*}(.|\alpha,K,\mathcal{Z}_{n})$, the expectation with respect to
the localized (to $\Theta_{n}$) posterior measure
$\mu^{*}(.|\alpha,K,\mathcal{Z}_{n})$ in $(\ref{mu-star})$. It follows that
$A_{1}$ can be expressed as

$\displaystyle A_{1}$ $\displaystyle=\mathbb{E}^{*}\bigg{[}\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\mathbbm{1}\\{\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq
E\delta_{n}\\}\bigg{|}\mathcal{Z}_{n}\bigg{]}$
$\displaystyle+\int\left|\langle
h-h_{0},\Phi\rangle_{L^{2}(\mathbb{P})}\right|^{2}\mathbbm{1}\\{\|h-h_{0}\|_{L^{2}(\mathbb{P})}\leq
E\delta_{n}\\}d\big{[}\mu(h|\alpha,K,\mathcal{Z}_{n})-\mu^{*}(h|\alpha,K,\mathcal{Z}_{n})]$
$\displaystyle=A_{1,1}+A_{1,2}.$

From the general bound $x^{2}\leq 2\big{(}e^{x}+e^{-x})$ for every
$x\in\mathbb{R}$, it follows from (104) with $t=\pm 1$ that

$\displaystyle nA_{1,1}\leq
C\big{(}e^{\sqrt{n}S_{n}}+e^{-\sqrt{n}S_{n}}\big{)}\;,$

with $\mathbb{P}$ probability approaching $1$, where $S_{n}$ is defined as in
(100). Since $S_{n}$ is a sample mean of a mean zero random variable with
finite variance, the central limit theorem implies
$nA_{1,1}=O_{\mathbb{P}}(1)$.

For $A_{1,2}$, if $\|.\|_{TV}$ denotes the total variation metric, we have
that

$\displaystyle A_{1,2}\leq
E^{2}\delta_{n}^{2}\|\Phi\|_{L^{2}(\mathbb{P})}^{2}\|\mu-\mu^{*}\|_{TV}\leq
E^{2}\delta_{n}^{2}2\mu(\Theta_{n}^{c}|\alpha,K,\mathcal{Z}_{n})\leq
C\delta_{n}^{2}e^{-Rn\epsilon_{n}^{2}\log(n)}.$

It follows that $nA_{1,2}=o_{\mathbb{P}}(1)$. ∎

###### Proof of Corollary 1.

Let $\delta_{n}$ denote the stated contraction rate and
$\epsilon_{n}=\sqrt{K_{n}}/\sqrt{n}$. From the proof of Theorem 3, there
exists a universal constant $D>0$ such that for all sufficiently large $L>0$,
we have

$\displaystyle\mu\big{(}\|h-h_{0}\|_{L^{2}}>L\delta_{n}\>\big{|}\>\mathcal{Z}_{n}\big{)}\leq\exp(-DL\log(n)n\epsilon_{n}^{2}).$

with $\mathbb{P}$ probability approaching $1$. Suppose the preceding bound
holds for all $L\geq\overline{L}>0$. We have that

$\displaystyle\|h_{0}-\mathbb{E}\big{[}h|\mathcal{Z}_{n}\big{]}\|_{L^{2}}^{2}$
$\displaystyle\leq\mathbb{E}\big{(}\|h-h_{0}\|_{L^{2}}^{2}\big{|}\mathcal{Z}_{n})$
$\displaystyle=\int_{\|h-h_{0}\|_{L^{2}}<\overline{L}\delta_{n}}\|h-h_{0}\|_{L^{2}}^{2}d\mu(h|\mathcal{Z}_{n})+\sum_{j=1}^{\infty}\int\limits_{j\overline{L}\delta_{n}\leq\|h-h_{0}\|_{L^{2}}<(j+1)\overline{L}\delta_{n}}\|h-h_{0}\|_{L^{2}}^{2}d\mu(h|\mathcal{Z}_{n})$
$\displaystyle\leq\overline{L}^{2}\delta_{n}^{2}+\overline{L}^{2}\delta_{n}^{2}\sum_{j=1}^{\infty}(j+1)^{2}\exp(-Dj\overline{L}\log(n)n\epsilon_{n}^{2}).$

Since the preceding sum is finite, the claim follows. ∎

###### Proof of Corollary 2.

The set $C_{n}(\gamma)$ can equivalently be expressed as

$\displaystyle
C_{n}(\gamma)=\\{t\in\mathbb{R}:\sqrt{n}\left|t-\mathbf{L}\big{(}\mathbb{E}[h|\mathcal{Z}_{n}]\big{)}\right|\leq
c_{1-\gamma}\\}\>,$ $\displaystyle c_{1-\gamma}=(1-\gamma)\;\>\text{quantile
of}\>\;\sqrt{n}\left|\mathbf{L}(h)-\mathbf{L}\big{(}\mathbb{E}[h|\mathcal{Z}_{n}]\big{)}\right|\;,\;h\sim\mu(.|\alpha,K,\mathcal{Z}_{n}).$

Define

$\displaystyle\sigma_{\Phi}^{2}=\mathbb{E}\big{[}(D_{h_{0}}\tilde{\Phi})^{\prime}\\{\mathbb{E}[\rho(Y,h_{0}(X))\rho(Y,h_{0}(X))^{\prime}|W]\\}^{-1}(D_{h_{0}}\tilde{\Phi})\big{]}.$

By Theorem 4$(i)$, we have

$\displaystyle
c_{1-\gamma}\xrightarrow{\mathbb{P}}(1-\gamma)\;\>\text{quantile
of}\>\;\left|Z\right|\;\;,\;\;Z\sim N(0,\sigma_{\Phi}^{2}).$ (111)

By Theorem 4$(ii)$, the distribution of
$\sqrt{n}\big{(}\mathbf{L}(h_{0})-\mathbf{L}\big{(}\mathbb{E}[h|\mathcal{Z}_{n}]\big{)}\big{)}$
is asymptotically Gaussian with variance $\sigma_{\Phi}^{2}$. From this
observation and (111), it follows that the frequentist coverage of
$C_{n}(\gamma)$ is given by

$\displaystyle\mathbb{P}\big{(}\sqrt{n}\left|\mathbf{L}(h_{0})-\mathbf{L}\big{(}\mathbb{E}[h|\mathcal{Z}_{n}]\big{)}\right|\leq
c_{1-\gamma}\big{)}=1-\gamma+o_{\mathbb{P}}(1).$

∎

## References

  * Agapiou et al. (2013) Agapiou, Sergios, Stig Larsson, and Andrew M Stuart (2013): “Posterior contraction rates for the Bayesian approach to linear ill-posed inverse problems,” _Stochastic Processes and their Applications_ , 123 (10), 3828–3860.
  * Belloni et al. (2015) Belloni, Alexandre, Victor Chernozhukov, Denis Chetverikov, and Kengo Kato (2015): “Some new asymptotic theory for least squares series: Pointwise and uniform results,” _Journal of Econometrics_ , 186 (2), 345–366.
  * Blundell et al. (2007) Blundell, Richard, Xiaohong Chen, and Dennis Kristensen (2007): “Semi-nonparametric IV estimation of shape-invariant Engel curves,” _Econometrica_ , 75 (6), 1613–1669.
  * Borovitskiy et al. (2020) Borovitskiy, Viacheslav, Alexander Terenin, Peter Mostowsky, et al. (2020): “Matérn Gaussian processes on Riemannian manifolds,” _Advances in Neural Information Processing Systems_ , 33, 12426–12437.
  * Breunig (2020) Breunig, Christoph (2020): “Specification testing in nonparametric instrumental quantile regression,” _Econometric Theory_ , 36 (4), 583–625.
  * Castillo and Rousseau (2015) Castillo, Ismaël and Judith Rousseau (2015): “A Bernstein–von Mises theorem for smooth functionals in semiparametric models,” _The Annals of Statistics_ , 43 (6), 2353–2383.
  * Chen et al. (2014) Chen, Xiaohong, Victor Chernozhukov, Sokbae Lee, and Whitney K Newey (2014): “Local identification of nonparametric and semiparametric models,” _Econometrica_ , 82 (2), 785–809.
  * Chen and Christensen (2015) Chen, Xiaohong and Timothy M Christensen (2015): “Optimal uniform convergence rates and asymptotic normality for series estimators under weak dependence and weak conditions,” _Journal of Econometrics_ , 188 (2), 447–465.
  * Chen et al. (2003) Chen, Xiaohong, Oliver Linton, and Ingrid Van Keilegom (2003): “Estimation of semiparametric models when the criterion function is not smooth,” _Econometrica_ , 71 (5), 1591–1608.
  * Chen and Pouzo (2009) Chen, Xiaohong and Demian Pouzo (2009): “Efficient estimation of semiparametric conditional moment models with possibly nonsmooth residuals,” _Journal of Econometrics_ , 152 (1), 46–60.
  * Chen and Pouzo (2012) ——— (2012): “Estimation of nonparametric conditional moment models with possibly nonsmooth generalized residuals,” _Econometrica_ , 80 (1), 277–321.
  * Chen and Pouzo (2015) ——— (2015): “Sieve Wald and QLR inferences on semi/nonparametric conditional moment models,” _Econometrica_ , 83 (3), 1013–1079.
  * Chen et al. (2019) Chen, Xiaohong, Demian Pouzo, and James L Powell (2019): “Penalized sieve GEL for weighted average derivatives of nonparametric quantile IV regressions,” _Journal of Econometrics_ , 213 (1), 30–53.
  * Chernozhukov and Hong (2003) Chernozhukov, Victor and Han Hong (2003): “An MCMC approach to classical estimation,” _Journal of econometrics_ , 115 (2), 293–346.
  * Chernozhukov et al. (2007) Chernozhukov, Victor, Guido W Imbens, and Whitney K Newey (2007): “Instrumental variable estimation of nonseparable models,” _Journal of Econometrics_ , 139 (1), 4–14.
  * Chernozhukov et al. (2023) Chernozhukov, Victor, Whitney K Newey, and Andres Santos (2023): “Constrained conditional moment restriction models,” _Econometrica_ , 91 (2), 709–736.
  * De Hoop et al. (2012) De Hoop, Maarten V, Lingyun Qiu, and Otmar Scherzer (2012): “Local analysis of inverse problems: Hölder stability and iterative reconstruction,” _Inverse Problems_ , 28 (4), 045001.
  * Dunker et al. (2014) Dunker, Fabian, Jean-Pierre Florens, Thorsten Hohage, Jan Johannes, and Enno Mammen (2014): “Iterative estimation of solutions to noisy nonlinear operator equations in nonparametric instrumental regression,” _Journal of Econometrics_ , 178, 444–455.
  * Evans (2022) Evans, Lawrence C (2022): _Partial differential equations_ , vol. 19, American Mathematical Society.
  * Florens and Simoni (2016) Florens, Jean-Pierre and Anna Simoni (2016): “Regularizing priors for linear inverse problems,” _Econometric Theory_ , 32 (1), 71–121.
  * Ghosal and Van der Vaart (2017) Ghosal, Subhashis and Aad Van der Vaart (2017): _Fundamentals of nonparametric Bayesian Inference_ , Cambridge University Press.
  * Giné and Nickl (2021) Giné, Evarist and Richard Nickl (2021): _Mathematical foundations of infinite-dimensional statistical models_ , Cambridge university press.
  * Giordano and Nickl (2020) Giordano, Matteo and Richard Nickl (2020): “Consistency of Bayesian inference with Gaussian process priors in an elliptic inverse problem,” _Inverse Problems_ , 36 (8), 085001.
  * Gugushvili et al. (2020) Gugushvili, Shota, Aad van der Vaart, and Dong Yan (2020): “Bayesian linear inverse problems in regularity scales,” in _Annales de l’Institut Henri Poincaré-Probabilités et Statistiques_ , vol. 56, 2081–2107.
  * Hall and Horowitz (2005) Hall, Peter and Joel L Horowitz (2005): “Nonparametric methods for inference in the presence of instrumental variables,” _Annals of Statistics_ , 33 (6), 2904–2929.
  * Hanke et al. (1995) Hanke, Martin, Andreas Neubauer, and Otmar Scherzer (1995): “A convergence analysis of the Landweber iteration for nonlinear ill-posed problems,” _Numerische Mathematik_ , 72 (1), 21–37.
  * Horowitz and Lee (2007) Horowitz, Joel L and Sokbae Lee (2007): “Nonparametric instrumental variables estimation of a quantile regression model,” _Econometrica_ , 75 (4), 1191–1208.
  * Kaltenbacher et al. (2021) Kaltenbacher, Barbara, Tram Thi Ngoc Nguyen, and Otmar Scherzer (2021): “The tangential cone condition for some coefficient identification model problems in parabolic PDEs,” _Time-dependent Problems in Imaging and Parameter Identification_ , 121–163.
  * Kaltenbacher et al. (2009) Kaltenbacher, Barbara, Frank Schöpfer, and Thomas Schuster (2009): “Iterative methods for nonlinear ill-posed problems in Banach spaces: convergence and applications to parameter identification problems,” _Inverse Problems_ , 25 (6), 065003.
  * Kato (2013) Kato, Kengo (2013): “Quasi-Bayesian analysis of nonparametric instrumental variables models,” _The Annals of Statistics_ , 41 (5), 2359–2390.
  * Knapik and Salomond (2018) Knapik, Bartek and Jean-Bernard Salomond (2018): “A general approach to posterior contraction in nonparametric inverse problems,” _Bernoulli_ , 24 (3), 2091–2121.
  * Knapik et al. (2011) Knapik, BT, AW van der Vaart, and JH van Zanten (2011): “Bayesian inverse problems with Gaussian priors,” _The Annals of Statistics_ , 39 (5), 2626–2657.
  * Liao and Jiang (2011) Liao, Yuan and Wenxin Jiang (2011): “Posterior consistency of nonparametric conditional moment restricted models,” _The Annals of Statistics_ , 39 (6), 3003–3031.
  * Mair and Ruymgaart (1996) Mair, Bernard A and Frits H Ruymgaart (1996): “Statistical inverse estimation in Hilbert scales,” _SIAM Journal on Applied Mathematics_ , 56 (5), 1424–1444.
  * Mathé and Pereverzev (2001) Mathé, Peter and Sergei V Pereverzev (2001): “Optimal discretization of inverse problems in Hilbert scales. Regularization and self-regularization of projection methods,” _SIAM Journal on Numerical Analysis_ , 38 (6), 1999–2021.
  * Monard et al. (2021a) Monard, François, Richard Nickl, and Gabriel P Paternain (2021a): “Consistent Inversion of Noisy Non-Abelian X-Ray Transforms,” _Communications on Pure and Applied Mathematics_ , 74 (5), 1045–1099.
  * Monard et al. (2021b) ——— (2021b): “Statistical guarantees for Bayesian uncertainty quantification in nonlinear inverse problems with Gaussian process priors,” _The Annals of Statistics_ , 49 (6), 3255–3298.
  * Newey and Powell (2003) Newey, Whitney K and James L Powell (2003): “Instrumental variable estimation of nonparametric models,” _Econometrica_ , 71 (5), 1565–1578.
  * Ray (2013) Ray, Kolyan (2013): “Bayesian inverse problems with non-conjugate priors,” _Electronic Journal of Statistics_ , 7, 2516–2549.
  * Reed (2012) Reed, Michael (2012): _Methods of modern mathematical physics: Functional analysis_ , Elsevier.
  * Severini and Tripathi (2012) Severini, Thomas A and Gautam Tripathi (2012): “Efficiency bounds for estimating linear functionals of nonparametric regression models with endogenous regressors,” _Journal of Econometrics_ , 170 (2), 491–498.
  * Tropp (2012) Tropp, Joel A (2012): “User-friendly tail bounds for sums of random matrices,” _Foundations of computational mathematics_ , 12, 389–434.
  * Van Der Vaart (1991) Van Der Vaart, Aad (1991): “On differentiable functionals,” _The Annals of Statistics_ , 178–204.
  * Van Der Vaart and Wellner (1996) Van Der Vaart, Aad W and Jon A Wellner (1996): _Weak convergence and empirical processes: with applications to statistics_ , vol. 3, Springer.


# On the Zarankiewicz problem for graphs with bounded VC-dimension

Oliver Janzer Department of Pure Mathematics and Mathematical Statistics,
University of Cambridge, United Kingdom and Department of Mathematics, ETH
Zürich, Switzerland. Email<EMAIL_ADDRESS>Cosmin Pohoata Department of
Mathematics, Yale University, USA. Email<EMAIL_ADDRESS>
###### Abstract

The problem of Zarankiewicz asks for the maximum number of edges in a
bipartite graph on $n$ vertices which does not contain the complete bipartite
graph $K_{k,k}$ as a subgraph. A classical theorem due to Kővári, Sós, and
Turán says that this number of edges is $O\left(n^{2-1/k}\right)$. An
important variant of this problem is the analogous question in bipartite
graphs with VC-dimension at most $d$, where $d$ is a fixed integer such that
$k\geq d\geq 2$. A remarkable result of Fox, Pach, Sheffer, Suk, and Zahl with
multiple applications in incidence geometry shows that, under this additional
hypothesis, the number of edges in a bipartite graph on $n$ vertices and with
no copy of $K_{k,k}$ as a subgraph must be $O\left(n^{2-1/d}\right)$. This
theorem is sharp when $k=d=2$, because by design any $K_{2,2}$-free graph
automatically has $VC$-dimension at most $2$, and there are well-known
examples of such graphs with $\Omega\left(n^{3/2}\right)$ edges. However, it
turns out this phenomenon no longer carries through for any larger $d$.

We show the following improved result: the maximum number of edges in
bipartite graphs with no copies of $K_{k,k}$ and VC-dimension at most $d$ is
$o(n^{2-1/d})$, for every $k\geq d\geq 3$.

##  1 Introduction

The problem of Zarankiewicz is a central problem in extremal graph theory. It
asks for the maximum number of edges $\operatorname{ex}(n,K_{k,k})$ in a
bipartite graph on $n$ vertices, where each side of the bipartition contains
$n/2$ vertices and which does not contain the complete bipartite graph
$K_{k,k}$ as a subgraph. In 1954, Kővári, Sós, and Turán [13] proved that this
number of edges is at most $c_{k}n^{2-\frac{1}{k}}$, for some positive
constant $c_{k}$ which depends only on $k$. Classical constructions of Reiman
and Brown show that this bound is tight for $k=2,3$ (see [15]). However, the
Zarankiewicz problem for $k\geq 4$ remains one of the most challenging
unsolved problems in combinatorics. The best lower bound for $k=4$ simply
comes from the Brown construction [5], namely

$\operatorname{ex}(n,K_{4,4})\geq\operatorname{ex}(n,K_{3,3})=\Omega\left(n^{5/3}\right).$

For $k=5,6$, the best lower bounds are due to Ball and Pepe [2] and come from
the norm graph construction of Alon, Rónyai and Szabó [1] (originally
considered for the asymmetric Zarankiewicz problem regarding bipartite graphs
containing no copies of $K_{4,7}$), i.e.

$\operatorname{ex}(n,K_{6,6})\geq\operatorname{ex}(n,K_{5,5})=\Omega(n^{7/4}).$

For $k\geq 7$, the best construction comes from a result of Bohman and Keevash
[3] on random graph processes, and is of the form

$\operatorname{ex}(n,K_{k,k})=\Omega\left(n^{2-2/(k+1)}(\log
k)^{1/(k^{2}-1)}\right).$

An important variant of this problem is the analogous question in bipartite
graphs with VC-dimension at most $d$, where $d$ is a fixed integer not larger
than $k$. The VC-dimension of a set system $\mathcal{F}$ on the ground set $V$
is the largest integer $d$ for which there exists a $d$-element set $S\subset
V$ such that for every subset $B\subset S$, one can find a member
$A\in\mathcal{F}$ with $A\cap S=B$. The VC-dimension, introduced by Vapnik and
Chervonenkis [19], is one of the most useful combinatorial parameters that
measures the complexity of graphs and hypergraphs. Over the years it has
proven tremendously important in many areas in (and out of) combinatorics and
mathematics, in general. We refer to [9] for a nice discussion (and a further
remarkable application). In order to define the VC-dimension of a bipartite
graph $G=(A,B,E)$ with vertex set $A\cup B$ and edge set $E\subset A\times B$,
the standard convention is to make a choice between $A$ and $B$, and then
define the VC-dimension of $G=(A,B,E)$ with respect to $A$ to be the VC-
dimension of the set system of neighborhoods of vertices $b\in B$ (regarded as
subsets of $A$), and vice versa (see also [8]). In this paper, we will always
choose the first side of the bipartition $A$ as the ground set, and so we
shall say that the VC-dimension of a bipartite $G=(A,B,E)$ is the VC-dimension
of $G$ with respect to $A$.

With this terminology, we now state the following remarkable result of Fox,
Pach, Sheffer, Suk and Zahl from [8, Theorem 2.1], which goes below the
Kővári, Sós, and Turán upper bound for the Zarankiewicz problem, in the
presence of bounded VC-dimension.

###### Theorem 1

Let $k$ and $d$ be integers such that $k\geq d\geq 2$. Let $G=(A,B,E)$ be a
bipartite graph with $|A|=|B|=n/2$ with VC-dimension at most $d$. Then, if $G$
is $K_{k,k}$-free, we have

$|E(G)|\leq cn^{2-1/d},$

for some positive constant $c=c(d,k)$.

Using a slightly stronger version of Theorem 1 for bipartite graphs
$G=(A,B,E)$ with $|A|$ and $|B|$ of possibly different sizes and with dual
shatter function of degree at most d, the observation that semi-algebraic
bipartite graphs of bounded description complexity also have bounded VC-
dimension (a consequence of the Milnor-Thom theorem), and a standard
amplification trick via the so-called cutting lemma of Chazelle [6], the
authors deduced the following general result.

###### Theorem 2

Let $G=(P,Q,E)$ be a semi-algebraic bipartite graph in
$\left(\mathbb{R}^{d_{1}},\mathbb{R}^{d_{2}}\right)$ such that $E$ has
description complexity at most $t$, $|P|=m$, and $|Q|=n$. If $G$ is
$K_{k,k}$-free, then

$|E(G)|\leq c_{1}\left((mn)^{2/3}+m+n\right)$

for $d_{1}=d_{2}=2$, and

$|E(G)|\leq
c_{2}\left(m^{\frac{d_{2}(d_{1}-1)}{d_{1}d_{2}-1}+\epsilon}n^{\frac{d_{1}(d_{2}-1)}{d_{1}d_{2}-1}}+m+n\right)$

for every $\epsilon>0$, for all $d_{1},d_{2}$. Here $c_{1}=c_{1}(t,k)$ and
$c_{2}=c_{2}(d_{1},d_{2},t,k,\epsilon)$.

Since in this paper we will not be discussing anything specific to semi-
algebraic graphs, we won’t attempt to make Theorem 2 (and its connection to
Theorem 1) more precise by providing the required definitions, but we invite
the interested reader to consult [8]. Nevertheless, it is worth mentioning at
least that this theorem has multiple applications in combinatorial geometry,
as the case $d_{1}=d_{2}=2$ already directly implies the celebrated Szemeredi-
Trotter theorem [18].

The main result of this paper concerns Theorem 1. Going back to the statement,
it is important to note that it is sharp when $k=d=2$. This is because, by
design, every $K_{2,2}$-free bipartite graph has $VC$-dimension at most $2$,
and so the well-known examples of such graphs with
$\Omega\left(n^{3/2}\right)$ edges automatically serve as constructions which
match the upper bound from Theorem 1. However, it turns out this phenomenon
does not extend for larger $k$. For example, already when $k=3$, it is not
difficult to check that the dense $K_{3,3}$-free graph from Brown’s
construction [5] has VC-dimension equal to $4$, so it does not anymore provide
a matching lower bound. This suggests that a potential improvement of Theorem
1 might be possible when $k\geq d\geq 3$.

In what follows, we confirm this suspicion by proving the following improved
result.

###### Theorem 3

Let $k$ and $d$ be integers such that $k\geq d\geq 3$. Let $G=(A,B,E)$ be a
bipartite graph with $|A|=|B|=n/2$ with VC-dimension at most $d$. Then, if $G$
is $K_{k,k}$-free, we have

$|E(G)|=o_{n\to\infty}\left(n^{2-1/d}\right).$

We give the proof of Theorem 3 in Section 2. It is perhaps important to
emphasize that, unlike the argument used in [8], our method does not rely on
the so-called packing lemma of Haussler [11]. Instead, our approach is similar
in spirit to an argument used by Sudakov and Tomon [17] in a related, but
different context.

##  2 Proof of Theorem 3

Our notation is mostly standard. For a graph $G$ and vertex $v\in V(G)$, we
write $N_{G}(v)$ for the set of neighbors of $v$ in $G$. When the graph is
clear, we often write $N(v)$ for the same set. If $T\subset V(G)$, we write
$N(T)$ for the set of common neighbours of the set $T$.

Let $G=(A,B,E)$ be a $K_{k,k}$-free bipartite graph with the number of edges
satisfying $|E(G)|\geq cn^{2-1/d}$ for some constant $c>0$, and where
$|A|=|B|=n/2$. In order to show that $G$ has VC-dimension at least $d+1$, we
need to prove the existence of a set $S$ of $d+1$ vertices in $A$, which is
shattered by the set system formed by the neighborhoods $N(b)$ of the vertices
$b\in B$; that is, a set $S$ with $|S|=d+1$ such that for every subset
$S^{\prime}\subset S$, there exist $b\in B$ with the property that $N(b)\cap
S=S^{\prime}$.

First, we move to a subgraph with large minimum degree and choose the vertex
which will be a neighbor to every vertex in $S$.

###### Proposition 1

Let $G$ be a $K_{k,k}$-free bipartite graph with parts $A$ and $B$ and at
least $cn^{2-1/d}$ edges, where $c>0$ is a constant and $|A|,|B|=n/2$. Then
$G$ has an induced subgraph $G^{\prime}$ with parts $A^{\prime}\subset A$ and
$B^{\prime}\subset B$ such that $G^{\prime}$ has minimum degree at least
$\frac{c}{4}n^{1-1/d}$ and there exists a vertex $x\in B^{\prime}$ such that
$|N(x^{\prime})\cap N(x)|=o(|N(x)|)$ holds for every $x^{\prime}\in
B^{\prime}\setminus\\{x\\}$.

In the short proof we shall use the asymmetric Kővári–Sós–Turán theorem.

###### Lemma 1

Let $G$ be a $K_{k,k}$-free bipartite graph with parts of size $m$ and $n$.
Then $G$ has at most $O_{k}(nm^{1-1/k}+m)$ edges.

Proof of Proposition 1: First, by iteratively discarding vertices of degree
less than $\frac{c}{2}n^{1-1/d}$, we find a non-empty subgraph
$G^{\prime\prime}$ which has minimum degree at least $\frac{c}{2}n^{1-1/d}$.
Let $G^{\prime\prime}$ have parts $A^{\prime\prime}$ and $B^{\prime\prime}$.
Choose a vertex $x\in B^{\prime\prime}$ arbitrarily. By Lemma 1, since
$G^{\prime\prime}$ is $K_{k,k}$-free and
$|N_{G^{\prime\prime}}(x)|\geq\frac{c}{2}n^{1-1/d}$, it is easy to see that
the number of vertices $y\in B^{\prime\prime}$ such that
$|N_{G^{\prime\prime}}(y)\cap
N_{G^{\prime\prime}}(x)|\geq\frac{|N_{G^{\prime\prime}}(x)|}{\log n}$ is at
most $n^{1/100}$. Write $B^{\prime}$ for the set obtained from
$B^{\prime\prime}$ after removing these vertices (apart from $x$). Let
$A^{\prime}=A^{\prime\prime}$ and let $G^{\prime}$ be the induced subgraph of
$G^{\prime\prime}$ with parts $A^{\prime}$ and $B^{\prime}$. This choice of
$x$ and $G^{\prime}$ satisfies the conditions in the statement of the
proposition. $\Box$

The next proposition will be applied for the subgraph found in the previous
result.

###### Proposition 2

Let $G$ be a bipartite graph with parts $A$ and $B$ and with minimum degree
satisfying $\delta(G)=\delta\geq cn^{1-1/d}$ for some constant $c>0$, and
where $|A|,|B|\leq n/2$. Let $r$ be a constant positive integer and let $x\in
B$. Then one of the following two statements must be true:

  1. 1.

there exists a set $R\subset N(x)$ of size $r$ such that for every $T\subset
R$ of size $d$, we have $|N(T)|\geq r$ or

  2. 2.

there exist $\Theta(|N(x)|^{r})$ sets $R\subset N(x)$ of size $r$ such that
for every $T\subset R$ of size $d$, we have
$N(T)\setminus\\{x\\}\neq\emptyset$.

To prove this, we will use the so-called hypergraph removal lemma, proved
independently by Nagle, Rödl, Schacht [14] and Gowers [10].

###### Lemma 2

Let $r,d$ be positive integers. For every $\beta>0$ there exists
$\delta=\delta(r,d,\beta)>0$ such that the following holds. If $\mathcal{H}$
is a $d$-uniform hypergraph on $N$ vertices such that one needs to remove at
least $\beta N^{d}$ hyperedges of $\mathcal{H}$ in order to make it free of
copies of $K_{r}^{(d)}$, then $\mathcal{H}$ contains at least $\delta N^{r}$
copies of $K_{r}^{(d)}$.

Proof of Proposition 2: Define a $d$-uniform hypergraph $\mathcal{H}$ on
vertex set $N(x)$ such that any $T\subset N(x)$ of size $d$ is a hyperedge in
$\mathcal{H}$ if and only if $N(T)\setminus\\{x\\}\neq\emptyset$. Then outcome
2. is equivalent to saying that $\mathcal{H}$ contains $\Theta(|N(x)|^{r})$
copies of $K_{r}^{(d)}$. If the first statement does not hold, by using Lemma
2, it then suffices to prove that in order to destroy all copies of
$K_{r}^{(d)}$ in $\mathcal{H}$, one needs to remove $\Theta(|N(x)|^{d})$
hyperedges from $\mathcal{H}$. To this end, we shall prove that this indeed
holds provided that there is no set $R\subset N(x)$ of size $r$ such that for
every $T\subset R$ of size $d$, we have $|N(T)|\geq r$.

Color a $d$-set $T\subset N(x)$ green if $N(T)=\\{x\\}$, blue if $1<|N(T)|<r$
and red if $|N(T)|\geq r$. Note that if $y\in B\setminus\\{x\\}$, then any
$d$-set $T\subset N(x)\cap N(y)$ is colored blue or red. If there exists some
$R\subset N(x)$ of size $r$ such that every $T\subset R$ of size $d$ is red,
then condition 1. holds. However, if $\ell$ is sufficiently large, by Ramsey’s
theorem (see [16] or [12, Theorem 4.18]) we know that for every set $L\subset
N(x)\cap N(y)$ of size $\ell$, there exists a subset $R\subset L$ of size $r$
such that all $d$-sets in $R$ have the same color.

Therefore each $\ell$-set in $N(x)\cap N(y)$ contains a monochromatic blue
$r$-set. Clearly any such $r$-set $R$ has the property that for every
$T\subset R$ of size $d$, we have $N(T)\setminus\\{x\\}\neq\emptyset$. Hence,
if we are to delete all such $r$-sets from $\mathcal{H}$, then we need to
delete a blue edge from every $\ell$-set in $N(x)\cap N(y)$, for every $y\in
B\setminus\\{x\\}$. Hence, we need to delete at least

$\frac{1}{r}\sum_{y\in
B\setminus\\{x\\}}\frac{1}{\binom{\ell}{d}}\binom{d(x,y)}{d}$

hyperedges, where $d(x,y)=|N(x)\cap N(y)|$. Clearly,

$\sum_{y\in B\setminus\\{x\\}}d(x,y)=e(B\setminus\\{x\\},N(x))\geq\sum_{z\in
N(x)}(d(z)-1)\geq d(x)(\delta-1).$

Hence, by Jensen’s inequality,

$\sum_{y\in
B\setminus\\{x\\}}\binom{d(x,y)}{d}\geq\Omega(n(d(x)\delta/n)^{d})\geq\Omega(d(x)^{d})=\Omega(|N(x)|^{d}).$

Note that in the first inequality we have used implicitly that
$d(x)\delta\geq(cn^{1-1/d})^{2}\geq\omega(n)$ as $d\geq 3$.

Thus, we indeed need to delete $\Omega(|N(x)|^{d})$ hyperedges to destroy all
copies of $K_{r}^{(d)}$ in $\mathcal{H}$. $\Box$

###### Proposition 3

Let $q$ be a positive integer and let $F$ be a $K_{k,k}$-free bipartite graph
with parts $B$ and $Q$, where $|Q|=q$. Assume that there exists $x\in B$ which
is joined to all vertices of $Q$ and that for every $T\subset Q$ of size $d$,
we have $|N(T)|\geq q$. If $q$ is sufficiently large compared to $d$ and $k$,
then $Q$ has a subset of size $d+1$ that is shattered by $\\{N(b):b\in B\\}$.

Proof of Proposition 3: Let $Z$ be a uniformly random subset of $Q$ of size
$d+1$. We shall prove that $Z$ is shattered with probability at least $1/2$.

In order to do this, we show that with probability at least $1/2$, the
following property holds.

For every $S\subset Z$ of size at most $d$ and every $z\in Z\setminus S$, we
have $|N(S\cup\\{z\\})|<\frac{1}{d+1}|N(S)|$.

For convenience, let us call this property by the name Property $\mathcal{VC}$
and see first why it implies that the set $Z$ is shattered. For each $S\subset
Z$, we need to choose a vertex $b_{S}\in B$ such that $N(b_{S})\cap Z=S$. For
$S=Z$, choose $b_{S}=x$. Let $S\subset Z$ be a set of size at most $d$. By
Property $\mathcal{VC}$, the number of vertices in $N(S)$ which have a
neighbor in the set $Z\setminus S$ is less than
$(d+1)\frac{1}{d+1}|N(S)|=|N(S)|$. Hence, we can pick some $b_{S}\in N(S)$
with $N(b_{S})\cap Z=S$.

It remains to prove that Property $\mathcal{VC}$ holds with probability at
least $1/2$. Using the union bound and conditioning on the $d$-subsets of $Z$,
it suffices to prove that for any $S\subset Q$ of size at most $d$, the
probability that there exists $z\in Z\setminus S$ with
$|N(S\cup\\{z\\})|\geq\frac{1}{d+1}|N(S)|$ is at most $\frac{1}{2\cdot
2^{d+1}}$. However, note that since $|N(S)|\geq q$, where $q$ is sufficiently
large compared to $d$ and $k$, and the induced subgraph of $F$ with parts $Q$
and $N(S)$ is $K_{k,k}$-free, it follows by Lemma 1 that the number of
vertices $y\in Q\setminus S$ with $|N(S\cup\\{y\\})|\geq\frac{1}{d+1}|N(S)|$
is at most $f(d,k)$ for some function $f$. Hence, if $q$ is sufficiently
large, then with probability more than $1-\frac{1}{2\cdot 2^{d+1}}$, the
random subset $Z\subset Q$ avoids all these vertices. $\Box$

We are now in a position to prove Theorem 3.

Proof of Theorem 3: Suppose, for contradiction, that $G$ has at least
$cn^{2-1/d}$ edges for some constant $c>0$. Choose a subgraph $G^{\prime}$ and
a vertex $x$ as in Proposition 1. In what follows, all neighborhoods are
defined in $G^{\prime}$. By Proposition 2, one of the following two must hold.

  1. 1.

there exists a set $R\subset N(x)$ of size $r$ such that for every $T\subset
R$ of size $d$, we have $|N(T)|\geq r$, or

  2. 2.

there exist $\Theta(|N(x)|^{r})$ sets $R\subset N(x)$ of size $r$ such that
for every $T\subset R$ of size $d$, we have
$N(T)\setminus\\{x\\}\neq\emptyset$.

If condition 1. holds, then by Proposition 3, $G^{\prime}$ has VC-dimension at
least $d+1$. This implies that $G$ also has VC-dimension at least $d+1$, which
is a contradiction.

So we may assume that condition 2. holds. Let $R\subset N(x)$ be a set of size
$r$ such that for every $T\subset R$ of size $d$, we have
$N(T)\setminus\\{x\\}\neq\emptyset$.

Let $q$ be a constant which is sufficiently large compared to $d$ and $k$. Now
if $r$ is sufficiently large, by Ramsey’s theorem, there exists a set
$Q\subset R$ of size $q$ such that either $|N(T)|\geq q$ for every $T\subset
Q$ of size $d$, or $|N(T)|<q$ for every $T\subset Q$ of size $d$. In the
former case, Proposition 3 shows that $G^{\prime}$ has VC-dimension at least
$d+1$, which is a contradiction. Hence, $|N(T)|<q$ for every $T\subset Q$ of
size $d$.

Since we can start with $\Theta(|N(x)|^{r})$ many possible sets $R$ to get a
subset $Q\subset R$ as above, it follows that there exist $\Theta(|N(x)|^{q})$
sets $Q\subset N(x)$ such that for every $T\subset Q$ of size $d$, we have
$N(T)\setminus\\{x\\}\neq\emptyset$ and $|N(T)|<q$.

Let $Q$ be such a set. Assume that the sets $N(T)\setminus\\{x\\}$ are
pairwise disjoint as $T$ ranges over all subsets of $Q$ of size $d$. Then we
distinguish between two cases.

Case (a) is when for every $S\subset Q$ of size $d-1$ we have $|N(S)|\geq q$.
In this case, if $q$ is sufficiently large compared to $d$ and $k$, then using
an argument very similar to the one in Proposition 3, $Q$ has a subset of size
$d+1$ which is shattered. In fact, just as in the proof of that proposition, a
random subset $Z$ of size $d+1$ is shattered with probability at least $1/2$.
The only difference is that for every set $S\subset Z$ of size $d$, the vertex
$b_{S}$ is chosen from the set $N(S)\setminus\\{x\\}$. Since these sets are
disjoint, we get a different vertex for each $S$, and we have $N(b_{S})\cap
Z=S$. Sets of size at most $d-1$ are treated just like in Proposition 3. Now
$G^{\prime}$ has VC-dimension at least $d+1$, which is a contradiction.

Otherwise, which we call case (b), there exists $S\subset Q$ of size $d-1$
such that $|N(S)|<q$. However, note that the number of $q$-sets for which case
(b) can occur is $o(|N(x)|^{q})$. Indeed, there are $O(|N(x)|^{d-1})$ ways to
choose the set $S$ and there are less than $q$ ways to choose a common
neighbor of the set $S$. But any element $z\in Q\setminus S$ has a neighbor in
$N(S)\setminus\\{x\\}$ (since $N(S\cup\\{z\\})\setminus\\{x\\}\neq\emptyset$),
which leaves $o(|N(x)|)$ choices for each of these vertices. Altogether, we
get only $o(|N(x)|^{q})$ possibilities for $Q$.

It follows that the number of $q$-sets $Q\subset N(x)$ such that for every
$T\subset Q$ of size $d$ we have $|N(T)|<q$ and the sets
$N(T)\setminus\\{x\\}$ are not pairwise disjoint is $\Theta(|N(x)|^{q})$. We
now show that this is impossible by upper bounding the number of such sets.
Let us choose distinct sets $T,T^{\prime}\subset Q$ of size $d$ such that
$(N(T)\setminus\\{x\\})\cap(N(T^{\prime})\setminus\\{x\\})\neq\emptyset$. Note
that there are at most $|N(x)|^{d}$ ways to choose $T$, given such a choice
there are at most $|N(T)|<q$ ways to choose an element from
$(N(T)\setminus\\{x\\})\cap(N(T^{\prime})\setminus\\{x\\})$, and given these
there are at most $o(|N(x)|)$ ways to choose each vertex in
$T^{\prime}\setminus T$. Every vertex in $Q\setminus(T\cup T^{\prime})$ can be
chosen in at most $|N(x)|$ many ways, so altogether we only have
$o(|N(x)|^{q})$ possibilities for $Q$, which is a contradiction. $\Box$

## References

  * [1] N. Alon, L. Rónyai, T. Szabó, Norm-graphs: variations and applications, Journal of Combinatorial Theory. Series B 76 (1999), 280–290.
  * [2] S. Ball, V. Pepe, Asymptotic improvements to the lower bound of certain bipartite Turán numbers, Combinatorics, Probability and Computing 21 (2012), 323–329.
  * [3] T. Bohman and P. Keevash, The early evolution of the H-free process, Inventiones Mathematicae 181 (2010), 291–336.
  * [4] S. Basu, R. Pollack, M.F. Roy, Algorithms in Real Algebraic Geometry, 2nd Edition, Algorithms and Computation in Mathematics, 10, Springer-Verlag, Berlin, 2006.
  * [5] W. G. Brown, On graphs that do not contain a Thomsen graph, Canadian Mathematical Bulletin 9 (1966), 281–285.
  * [6] B. Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete Comput. Geom. 9 (1993), 145–-158.
  * [7] P. Erdős, On extremal problems of graphs and generalized graphs, Israel J. Math. 2 (1964), 183–190.
  * [8] J. Fox, J. Pach, A. Sheffer, A. Suk, J. Zahl, A semi-algebraic version of Zarankiewicz’s problem, J. Eur. Math. Soc. (JEMS) 19 (6) (2017), 1785–1810.
  * [9] J. Fox, J. Pach, A. Suk, Bounded VC-dimension implies the Schur-Erdos conjecture, Symposium on Computational Geometry (SoCG ‘20), Zurich, Switzerland, 2020.
  * [10] T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Annals of Mathematics, 166 (2017), 897–-946.
  * [11] D. Haussler, Sphere packing numbers for subsets of the Boolean $n-$cube with bounded Vapnik-Chervonenkis dimension, Journal of Combinatorial Theory. Series A 69 (1995), 217–-232.
  * [12] S. Jukna, Extremal combinatorics: with applications in computer science, Springer Science, 2011.
  * [13] T. Kővári, V. T. Sós and P. Turán, On a problem of K. Zarankiewicz, Colloquium Mathematicum 3 (1954), 50–57.
  * [14] B. Nagle, V. Rödl, and M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures & Algorithms, 28 (2006), 113-–179.
  * [15] J. Pach, P. K. Agarwal, Combinatorial Geometry, Wiley, New York, 1995.
  * [16] F. P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society, 30 (1930), 264–286.
  * [17] B. Sudakov, I. Tomon, The Turán number of bipartite graphs with no $K_{t,t}$, Proceedings of the American Mathematical Society, 148 (2020), 2811–2818.
  * [18] E. Szemerédi, W. T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392.
  * [19] V. Vapnik and A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl. 16 (1971), 264–-280.