# Provably and Practically Efficient Neural Contextual Bandits

Sudeep Salgia  School of Electrical & Computer Engineering, Cornell
University, Ithaca, NY, _{<EMAIL_ADDRESS>Sattar Vakili  MediaTek
Research, UK<EMAIL_ADDRESS>Qing Zhao  School of Electrical
& Computer Engineering, Cornell University, Ithaca, NY, _{
<EMAIL_ADDRESS>
###### Abstract

We consider the neural contextual bandit problem. In contrast to the existing
work which primarily focuses on ReLU neural nets, we consider a general set of
smooth activation functions. Under this more general setting, (i) we derive
non-asymptotic error bounds on the difference between an overparameterized
neural net and its corresponding neural tangent kernel, (ii) we propose an
algorithm with a provably sublinear regret bound that is also efficient in the
finite regime as demonstrated by empirical studies. The non-asymptotic error
bounds may be of broader interest as a tool to establish the relation between
the smoothness of the activation functions in neural contextual bandits and
the smoothness of the kernels in kernel bandits.

##  1 Introduction

The stochastic contextual bandit has been extensively studied in the
literature (see, Langford and Zhang, 2007; Lattimore and Szepesvári, 2020, and
references therein). In this problem, at each discrete sequential step, a
_context_ is revealed by the environment. Then, a bandit agent chooses one of
the $K$ available actions. Choosing each action yields a random reward, the
distribution of which is determined by the context. The problem was primarily
studied under a linear setting where the expected reward of each arm is a
linear function of the context (Chu et al., 2011; Li et al., 2019b; Chen et
al., 2021). It was later extended to kernel-based models (Valko et al., 2013),
where the expected reward function associated with the context-action pairs
belongs to the reproducing kernel Hilbert space (RKHS) determined by a known
kernel. Recently, a variation of the problem has been proposed where the
expected reward function associated with the context-action pairs is modeled
using a neural net (Zhou et al., 2020; Zhang et al., 2021; Gu et al., 2021;
Kassraie and Krause, 2022). The three contextual bandit settings mentioned
above are increasingly more complex in the following order: _Linear
$\rightarrow$ Kernel-based $\rightarrow$ Neural_.

Contextual bandits find application in recommender systems, information
retrieval, healthcare and finance (see a survey on applications in Bouneffouf
and Rish, 2019). The problem can also be seen as a middle step from classic
stochastic bandits (Auer et al., 2002) and (non-contextual) linear bandits
(Abbasi-Yadkori et al., 2011) towards a reinforcement learning (RL) problem on
a Markov decision process (MDP), where the contexts resemble the states of the
MDP. One of the first formulations of linear contextual bandits was referred
to as _associative RL_ with linear value function (Auer, 2002). Nonetheless,
contextual bandit is different from RL in that the contexts are determined
arbitrarily (adversarially) rather than following a stochastic Markovian
process.

###  1.1 Existing Results on Neural Contextual Bandits

With neural nets demonstrating a great representation power (much more general
than linear models), there has been an increasing interest in modeling bandit
and RL problems based on neural nets. This setting can be implemented using
the typical neural net toolboxes. The neural contextual bandit has been
considered in several works: Zhou et al. (2020) and Zhang et al. (2021),
respectively, adopted the upper confidence bound (UCB) and Thompson sampling
(TS) algorithms to the neural bandit setting. The algorithms are,
respectively, referred to as NeuralUCB and NeuralTS. Gu et al. (2021)
considered a batch observation setting, where the reward function can be
evaluated only on batches of data. Kassraie and Krause (2022) provided
analysis for a variation of NeuralUCB algorithm with diminishing instantaneous
regret.

The analysis of neural bandits has been enabled through the theory of neural
tangent (NT) kernel (Jacot et al., 2018) which approximates an
overparameterized neural net with the kernel corresponding to its infinite
width, and the bounds on the approximation error (e.g., see, Arora et al.
(2019)). Zhou et al. (2020); Zhang et al. (2021); Gu et al. (2021) proved
$\tilde{\mathcal{O}}(\Gamma_{k}(T)\sqrt{T})$111The notations $\mathcal{O}$ and
$\tilde{\mathcal{O}}$ are used for mathematical order and that up to
logarithmic factors, respectively.  bounds on cumulative regret, where $T$ is
the number of steps and $\Gamma_{k}(T)$ is a complexity term determined by the
neural tangent kernel $k$ associated with the particular neural network.
Specifically, $\Gamma_{k}(T)$ is the information gain corresponding to $k$ for
datasets of size $T$. For the ReLU neural nets on $d$-dimensional domains
considered in Zhou et al. (2020); Zhang et al. (2021); Gu et al. (2021),
$\Gamma_{k}(T)=\tilde{\mathcal{O}}(T^{\frac{d-1}{d}})$ is the best upper bound
known for the information gain (Kassraie and Krause, 2022; Vakili et al.,
2021b). Inserting this bound on $\Gamma_{k}(T)$, the aforementioned regret
bounds become trivial (superlinear) generally when $d>1$, unless further
restrictive assumptions are made on the contexts. Kassraie and Krause (2022)
addressed this issue by considering the _Sup_ variant of NeuralUCB (referred
to as SupNeuralUCB). The Sup variant is an adoption of SupLinUCB, which was
initially introduced in (Chu et al., 2011) for linear contextual bandits, to
the neural setting. Kassraie and Krause (2022) proved an
$\tilde{\mathcal{O}}(\sqrt{\Gamma_{k}(T)T})$ regret bound for SupNeuralUCB in
the case of ReLU neural nets, which solved the issue of superlinear regret
bound (non-diminishing instantaneous regret).

###  1.2 Contribution

All the existing works mentioned above, are limited to neural nets with ReLU
activation functions. This limitation is rooted in the fact that the existing
error bound between an overparameterized neural net and the corresponding NT
kernel (Arora et al., 2019, Theorem $3.2$) holds only for the ReLU neural
nets. In Theorem 1, which may be of broader interest, we extend this result by
providing error bounds for neural nets with arbitrarily smooth activation
functions. Using Theorem 1, together with the recently established bounds on
$\Gamma_{k}(T)$ corresponding to arbitrarily smooth neural nets (Vakili et
al., 2021b), we provide regret bounds for neural contextual bandits under a
more general setting than only ReLU activation function. In particular, in
Theorem 3, we prove an $\tilde{\mathcal{O}}(T^{\frac{2d+2s-3}{2d+4s-4}})$
upper bound on regret, where $s$ is the smoothness parameter of the activation
functions ($s=1$ in the case of ReLU, and $s$ grows larger as the activations
become smoother). Our regret bounds recover that of Kassraie and Krause (2022)
for ReLU activations, and can become as small as
$\tilde{\mathcal{O}}(\sqrt{T})$ when the activations become infinitely smooth.

Broadening the scope of neural bandits to general smooth activations is of
interest in several aspects. The smooth activation functions are more suitable
for some applications such as implicit representations (see Li et al. (2019a);
Sitzmann et al. (2020) and references therein). In addition, although
sublinear, the regret bounds for ReLU neural nets grow at a fast
$\tilde{\mathcal{O}}(T^{\frac{2d-1}{2d}})$ rate, that quickly approaches the
linear rate as $d$ grows. We show that this rate can significantly reduce for
smooth activations. Furthermore, our results help establish connections
between varying smoothness of activations in neural bandits and varying
smoothness of kernels in kernel-based bandits . Kernel-based bandits (Srinivas
et al., 2010) and Kernel-based contextual bandits (Valko et al., 2013) are
well studied problems with regret bounds reported for popular kernels such as
Matérn family, which is perhaps the most commonly used family of kernels in
practice (Snoek et al., 2012; Shahriari et al., 2015). Our regret bound for a
neural contextual bandit problem with activations with smoothness parameter
$s$ is equivalent to the regret bound in the case of kernel-based bandits with
a Matérn kernel (Valko et al., 2013; Li and Scarlett, 2022) with smoothness
parameter $s-\frac{1}{2}$. This connection may be of general interest in terms
of contrasting neural nets and kernel-based models through NT kernel theory.

In Theorem 2, we prove confidence intervals for overparameterized neural nets
with smooth activation functions, which are later used in the analysis of our
algorithm. The confidence intervals are a consequence of our Theorem 1 and
those for kernel regression. In contrast to prior work, our confidence
intervals are tighter and hold for a general set of smooth activation
functions (see Sec. 3).

In addition to the above analytical results for neural bandits with general
smooth activation functions, we propose a practically efficient algorithm. The
Sup variants of UCB algorithms are known to perform poorly in experiments
(Calandriello et al., 2019; Li and Scarlett, 2022), including SupNeuralUCB
presented in Kassraie and Krause (2022), due to over-exploration. We propose
NeuralGCB, a neural contextual bandit algorithm guided by both upper and lower
confidence bounds to provide a finer control of exploration-exploitation
trade-off to avoid over-exploration. In the experiments, we show that
NeuralGCB outperforms all other existing algorithms, namely NeuralUCB (Zhou et
al., 2020), NeuralTS (Zhang et al., 2021) and SupNeuralUCB (Kassraie and
Krause, 2022).

###  1.3 Other Related Work

Linear bandits have been considered also in a non-contextual setting, where
the expected rewards are linear in the actions in a fixed domain (e.g., see
the seminal work of Abbasi-Yadkori et al., 2011). The kernel-based bandits
(also referred to as Gaussian process bandits) have been extensively studied
under a non-contextual setting (Srinivas et al., 2010; Chowdhury and Gopalan,
2017). The GP-UCB and GP-TS algorithms proposed in this setting also show
suboptimal regret bounds (see Vakili et al. (2021c) for details). Recently
there have been several works offering optimal order regret bounds for kernel-
based (non-contextual) bandits (Salgia et al., 2021; Camilleri et al., 2021;
Li and Scarlett, 2022). These results however do not address the additional
difficulties in the contextual setting.

##  2 Preliminaries and Problem Formulation

In the stochastic contextual bandit problem, at each discrete sequential step
$t=1,2,\dots,T$, for each action $a\in[K]:=\\{1,2,\dots,K\\}$, a context
vector $\mathbf{x}_{t}\in\mathcal{X}$ is revealed, where $\mathcal{X}$ is a
compact subset of $\mathbb{R}^{d}$. Then, a bandit agent chooses an action
$a_{t}\in[K]$ and receives the corresponding reward
$r_{t}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}$, where
$h:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the underlying reward function and
$\xi_{t}\in\mathbb{R}$ is a zero-mean martingale noise process. The goal is to
choose actions which maximize the cumulative reward over $T$ steps. This is
equivalent to minimizing the cumulative _regret_ , that is defined as the
total difference between the maximum possible context-dependent reward and the
actua received reward

$\displaystyle
R(T)=\sum_{t=1}^{T}(h(\mathbf{x}_{t,a^{*}_{t}})-h(\mathbf{x}_{t,a_{t}})),$ (1)

where $a^{*}_{t}\in\arg\max_{a\in[K]}h(\mathbf{x}_{t,a})$ is the context-
dependent maximizer of the reward function at step $t$. Following is a formal
statement of the assumptions on $\mathcal{X}$, $f$ and $\xi_{t}$. These are
mild assumptions which are shared with other works on neural bandits and NT
kernel.

######  Assumption 1.

_(i)_ The input space is the $d$ dimensional hypersphere:
$\mathcal{X}=\mathbb{S}^{d-1}$. _(ii)_ The reward function $h$ belongs to the
RKHS induced by the NT kernel, and $h(\mathbf{x})\in[0,1],\ \forall\
\mathbf{x}\in\mathcal{X}$. _(iii)_ $\xi_{t}$ are assumed to be conditionally
$\nu$-sub-Gaussian, i.e., for any $\zeta\in\mathbb{R}$,
$\ln(\mathbb{E}[e^{\zeta\xi_{t}}|\xi_{1},\dots,\xi_{t-1}])\leq\zeta^{2}\nu^{2}/2$.

###  2.1 The Neural Net Model and Corresponding NT Kernel

In this section, we briefly outline the neural net model and the associated NT
kernel. Let $f(\mathbf{x};\mathbf{W})$ be a fully connected feedforward neural
net with $L$ hidden layers of equal width $m$. We can express $f$ using the
following set of recursive equations:

$\displaystyle f^{(1)}(\mathbf{x})$
$\displaystyle={\mathbf{W}}^{(1)}\mathbf{x},\ \
f^{(l)}(\mathbf{x})=\sqrt{\frac{c_{s}}{m}}{\mathbf{W}}^{(l)}\sigma_{s}({f}^{(l-1)}(\mathbf{x})),~{}~{}~{}1<l\leq
L$ $\displaystyle f(\mathbf{x};\mathbf{W})$
$\displaystyle=\sqrt{\frac{c_{s}}{m}}{\mathbf{W}}^{(L+1)}\sigma_{s}({f}^{(L)}(\mathbf{x})).$
(2)

Let $\mathbf{W}=(\mathbf{W}^{l})_{1\leq l\leq L+1}$ denote the collection of
all weights. The dimensions of weight matrices satisfy:
$\mathbf{W}^{(1)}\in\mathbb{R}^{m\times d}$; for $1<l\leq L$,
$\mathbf{W}^{(l)}\in\mathbb{R}^{m\times m}$;
$\mathbf{W}^{(L+1)}\in\mathbb{R}^{1\times m}$. All the weights
$\mathbf{W}^{(l)}_{i,j}$, $\forall\ l,i,j$, are initialized to
$\mathcal{N}(0,1)$ and $c_{s}:=2/(2s-1)!!$. With an abuse of notation,
$\sigma_{s}:\mathbb{R}^{m}\rightarrow\mathbb{R}^{m}$ is used for coordinate-
wise application the activations of the form $\sigma_{s}(u)=(\max(0,u))^{s}$
to the outputs of each layer. Note that $\sigma_{s}$ is $s-1$ times
differentiable which gives our results a general interpretability across
smoothness of activations and the resulting function classes and allows us to
draw parallels between our results and well established results for kernel-
based bandits.

It has been shown that gradient based training of the neural net described
above reaches a global minimum where the weights remain within a close
vicinity of random initialization. As a result the model can be approximated
with its linear projection on the tangent space at random initialization
$\mathbf{W}_{0}$:

$\displaystyle f(\mathbf{x};\mathbf{W})\approx
f(\mathbf{x};\mathbf{W}_{0})+(\mathbf{W}-\mathbf{W}_{0})^{\top}\mathbf{g}(\mathbf{x};\mathbf{W}_{0}),$

where the notation
$\mathbf{g}(\mathbf{x};\mathbf{W})=\nabla_{\mathbf{W}}f(\mathbf{x};\mathbf{W})$
is used for the gradient of $f$ with respect to the parameters. The
approximation error can be bounded by the second order term
$\mathcal{O}(\|\mathbf{W}-\mathbf{W}_{0}\|^{2})$, and shown to be diminishing
as the width $m$ grows, where the implied constant depends on the spectral
norm of the Hessian matrix (Liu et al., 2020). The NT kernel corresponding to
this neural net when $m$ grows to infinity is defined as the kernel in the
feature space determined by the gradient at initialization:

$\displaystyle
k(\mathbf{x},\mathbf{x}^{\prime})=\lim_{m\rightarrow\infty}\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{g}(\mathbf{x};\mathbf{W}_{0}).$

The particular form on the NT kernel depends on the activation function and
the number of layers. For example, for a two layer neural net with ReLU
activations, we have

$\displaystyle
k(\mathbf{x},\mathbf{x}^{\prime})=\frac{1}{\pi}\left(\mathbf{x}^{\top}\mathbf{x}^{\prime}(\pi-\arccos(\mathbf{x}^{\top}\mathbf{x}^{\prime}))+\sqrt{1-(\mathbf{x}^{\top}\mathbf{x}^{\prime})^{2}}\right)+\frac{\mathbf{x}^{\top}\mathbf{x}^{\prime}}{\pi}(\pi-\arccos(\mathbf{x}^{\top}\mathbf{x}^{\prime})),$

For the closed form derivation of NT kernel for other values of $s$ and $L$,
see Vakili et al. (2021b).

###  2.2 Assumptions on Neural Net and NT Kernel

The following technical assumptions are mild assumptions which are used in the
handling of the overparameterized neural nets using NT kernel. These
assumptions are common in the literature and often are fulfilled without loss
of generality (Arora et al., 2019; Zhou et al., 2020; Zhang et al., 2021; Gu
et al., 2021; Kassraie and Krause, 2022).

######  Assumption 2.

_(i)_ Consider $\mathbf{H}\in\mathbb{R}^{KT\times KT}$ such that
$[\mathbf{H}]_{i,j}=k(\mathbf{z}_{i},\mathbf{z}_{j})$ for all pairs in
$\mathcal{Z}\times\mathcal{Z}$, where
$\mathcal{Z}=\\{\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}\\}_{t=1}^{T}$. We assume
$\mathbf{H}\succcurlyeq\lambda_{0}\mathbb{I}$. _(ii)_
$f(\mathbf{x};\mathbf{W}_{0})$ is assumed to be $0$. _(iii)_ The number of
epochs during training, $J$, and the learning rate, $\eta$, satisfy
$J=\tilde{\Omega}(T)$ and $\eta=\mathcal{O}(1/T)$.

###  2.3 Information Gain

The regret bounds for neural bandits are typically given in terms of maximal
information gain (or the effective dimension) of the NT kernel. The maximal
information gain is defined as the maximum log determinant of the kernel
matrix (Srinivas et al., 2010):

$\displaystyle\Gamma_{k}(t)=\sup_{\mathbf{X}_{t}\subseteq\mathcal{X}}\log\left(\det\left(\mathbb{I}+\frac{1}{\lambda}k_{\mathbf{X}_{t},\mathbf{X}_{t}}\right)\right).$
(3)

It is closely related to the effective dimension of the kernel, which denotes
the number of features with a significant impact on the regression model and
can be finite for a finite dataset even when the feature space of the kernel
is infinite dimensional (Zhang, 2005; Valko et al., 2013). It is defined as

$\displaystyle\tilde{d}_{k}(t)=\mathrm{tr}\left(k_{\mathbf{X}_{t},\mathbf{X}_{t}}(k_{\mathbf{X}_{t},\mathbf{X}_{t}}+\lambda\mathbb{I})^{-1}\right).$
(4)

It is known that the information gain and the effective dimension are the same
up to logarithmic factors (Calandriello et al., 2019). We give our results in
terms of information gain; nonetheless, that can be replaced by effective
dimension.

##  3 Approximation Error and Confidence Bounds

As discussed earlier, the error between an overparameterized neural net and
the associated NT kernel can be quantified and shown to be small for large
$m$. To formalize this, we recall the technique of kernel ridge regression.
Given a dataset $\mathcal{D}_{t}=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{t}$, let
$f_{\textsc{NTK}}$ denote the regressor obtained by kernel ridge regression
using NT kernel. In particular, we have

$\displaystyle
f_{\textsc{NTK}}(\mathbf{x})=k^{\top}_{\mathbf{X}_{t}}(\mathbf{x})(\lambda\mathbb{I}_{t}+k_{\mathbf{X}_{t},\mathbf{X}_{t}})^{-1}\mathbf{Y}_{t},$
(5)

where
$k_{\mathbf{X}_{t}}(\mathbf{x})=[k(\mathbf{x}_{1},\mathbf{x}),\dots,k(\mathbf{x}_{t},\mathbf{x})]^{\top}$
is the NT kernel evaluated between $\mathbf{x}$ and $t$ data points,
$k_{\mathbf{X}_{t},\mathbf{X}_{t}}=[k(\mathbf{x}_{i},\mathbf{x}_{j})]_{i,j=1}^{t}$
is the NT kernel matrix evaluated on the data,
$\mathbf{Y}_{t}=[y_{1},\dots,y_{t}]^{\top}$ is the vector of output values,
and $\lambda\geq 0$ is a free parameter. Note that $f_{\textsc{NTK}}$ can be
computed in closed form (without training a neural net). In addition, let
$f_{\textsc{NN}}$ be prediction of the neural net at the end of training using
$\mathcal{D}_{t}$. Theorem $3.2$ of Arora et al. (2019) states that, when the
activations are ReLU and $m$ is sufficiently large, we have, with probability
at least $1-\delta$, that
$|f_{\textsc{NN}}(\mathbf{x})-f_{\textsc{NTK}}(\mathbf{x})|\leq\epsilon$. In
this theorem, the value of $m$ should be sufficiently large in terms of
$t,L,\delta,\epsilon$, and $\lambda_{0}$. We now present a bound on the error
between the neural net and the associated NT kernel for smooth activations.

######  Theorem 1.

Consider the neural net $f(\mathbf{x};\mathbf{W})$ defined in (2) consisting
of $L$ hidden layers each of width
$m\geq\mathrm{poly}(1/\varepsilon,s,1/\lambda_{0},|\mathcal{D}|,\log(1/\delta))$
with activations $\sigma_{s}$. Let $f_{\textsc{NTK}}$ and $f_{\textsc{NN}}$ be
the kernel ridge regressor and trained neural net using a dataset
$\mathcal{D}$. Then for any $\mathbf{x}\in\mathcal{X}$, with probability at
least $1-\delta$ over the random initialization of the neural net, we have,

$\displaystyle|f_{\textsc{NTK}}(\mathbf{x})-f_{\textsc{NN}}(\mathbf{x})|\leq\varepsilon.$

Theorem 1 is an generalization of Theorem $3.2$ in Arora et al. (2019) to the
class of smooth activation functions $\\{\sigma_{s},s\in\mathbb{N}\\}$. To
prove Theorem 1, we show the following bound on the error between NT kernel
and the kernel induced by the finite width neural net at initialization. This
result is an generalization of Theorem $3.1$ in Arora et al. (2019) to smooth
activation functions.

######  Lemma 1.

Consider the neural net $f(\mathbf{x};\mathbf{W})$ defined in (2) consisting
of $L$ hidden layers each of width
$m\geq\mathcal{O}(\frac{s^{L}L^{2}c_{s}^{2}}{\varepsilon^{2}}\log^{2}(sL/\delta\varepsilon))$
with activations $\sigma_{s}$. Let
$\mathbf{g}(\mathbf{x};\mathbf{W})=\nabla_{\mathbf{W}}f(\mathbf{x};\mathbf{W})$
and $k$ be the associated NT kernel, as defined in Section 2.1. Fix
$\varepsilon>0$ and $\delta\in(0,1)$. Then for any
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, with probability at least
$1-\delta$ over the initialization of the network, we have,

$\displaystyle\left|\mathbf{g}^{\top}(\mathbf{x};\mathbf{W}_{0})\mathbf{g}(\mathbf{x}^{\prime};\mathbf{W}_{0})-k(\mathbf{x},\mathbf{x}^{\prime})\right|\leq(L+1)\varepsilon.$

The proof entails a non-trivial generalization of various lemmas used in the
proof of Arora et al. (2019, Theorem 3.2) to the class of smooth activation
functions. We defer the detailed proof of the lemma and theorem to Appendix A.

##### Confidence Intervals:

The analysis of bandit problems classically builds on confidence intervals
applicable to the values of the reward function. The NT kernel allows us to
use the confidence intervals for kernel ridge regression, in building
confidence intervals for overparameterized neural nets. In particular, given a
dataset $\mathcal{D}_{t}$, let

$\displaystyle\mathbf{V}_{t}=\lambda\mathbb{I}+\sum_{i=1}^{t}\mathbf{g}(\mathbf{x}_{i};\mathbf{W}_{0})\mathbf{g}^{\top}(\mathbf{x}_{i};\mathbf{W}_{0})$
(6)

be the Gram matrix in the feature space determined by the gradient. Taking
into account the linearity of the model in the feature space, we can define a
(surrogate) posterior variance as follows,

$\displaystyle\hat{\sigma}^{2}_{t}(\mathbf{x})=\mathbf{g}^{\top}(\mathbf{x})\mathbf{V}_{t}^{-1}\mathbf{g}(\mathbf{x}),$
(7)

that can be used as a measure of uncertainty in the prediction provided by the
trained neural net. Using Theorem 1 in conjunction with the confidence
intervals for kernel ridge regression, we prove the following confidence
intervals for a sufficiently wide neural net.

######  Theorem 2.

Let $\mathcal{D}_{t}=\\{(\mathbf{x}_{i},r_{i})\\}_{i=1}^{t}$ denote a dataset
obtained under the observation model described in Section 2 such that the
points $\\{\mathbf{x}_{i}\\}_{i=1}^{t}$ are independent of the noise sequence
$\\{\xi_{i}\\}_{i=1}^{t}$. Suppose Assumptions 1 and 2 hold. Suppose the
neural net defined in (2) consisting of $L$ hidden layers each of width
$m\geq\mathrm{poly}(T,s,L,K,\lambda^{-1},\lambda_{0}^{-1},\log(1/\delta))$ is
trained using this dataset. Then, with probability at least $1-\delta$, the
following relation holds for any $\mathbf{x}\in\mathcal{X}$:

$\displaystyle\left|h(\mathbf{x})-f(\mathbf{x};\mathbf{W}_{t})\right|\leq\frac{C_{s,L}t}{\lambda
m}+\beta_{t}\hat{\sigma}_{t}(\mathbf{x}),$ (8)

where $\mathbf{W}_{t}$ denotes the parameters of the trained model,
$\beta_{t}=S+2\nu\sqrt{\log(1/\delta)}+C_{s,L}^{\prime}t(1-\eta\lambda)^{J/2}\sqrt{t/\lambda}+C^{\prime\prime}_{s,L}\sqrt{t^{3}/\lambda
m}$, $S$ is the RKHS (corresponding to the NT kernel) norm of $h$ and
$C_{s,L},C_{s,L}^{\prime},C_{s,L}^{\prime\prime}$ are constants depending only
on $s$ and $L$.

Both results presented in this section may be of broader interest in neural
net literature. We would like to emphasize that these bounds hold for all
activation functions $\\{\sigma_{s}:s\in\mathbb{N}\\}$ improving upon the
existing results which hold only for ReLU activation function. Furthermore,
this bound is tighter than the one derived in Kassraie and Krause (2022), even
for the case of ReLU activation function.The confidence intervals are
important building blocks in the analysis of NeuralGCB in Section 4. Please
refer to Appendix C for a detailed proof of the theorem.

##  4 Algorithm

The UCB family of algorithms achieve optimal regret in classic stochastic
finite action bandits (Auer et al., 2002). The optimal regret, however, hinges
on the statistical independence of the actions. In more complex settings such
as kernel-based and neural bandits, the inherent statistical dependence across
adaptively chosen actions leads to skewed posterior distributions, resulting
in sub-optimal and potentially trivial (i.e., superlinear) regret guarantees
of UCB based algorithms (Vakili et al., 2021c). To address this issue, one
approach adopted in the literature is to use samples with limited adaptivity.
These algorithms are typically referred to as Sup variant of UCB algorithms,
and have been developed for linear (Chu et al., 2011), kernel-based (Valko et
al., 2013) and neural (Kassraie and Krause, 2022) contextual bandits. These
Sup variants, however, are known to perform poorly in practice due to their
tendency to overly explore suboptimal arms.

We propose NeuralGCB, a neural bandit algorithm guided by both upper and lower
confidence bounds to avoid over-exploring, leading to superior performance in
practice while preserving the nearly optimal regret guarantee. The key idea of
NeuralGCB is a finer control of the exploration-exploitation tradeoff based on
the predictive standard deviation of past actions. This finer control
encourages more exploitation and reduces unnecessary exploration.
Specifically, NeuralGCB partitions past action-reward pairs into $R=\log T$
subsets (some subsets may be empty at the beginning of the learning horizon).
Let $\\{\Psi^{(r)}\\}_{r=1}^{R}$ denotes these subsets of action-reward pairs
where the index $r$ represents the level of uncertainty about the data points
in that set (with $r=1$ representing the highest uncertainty). Upon seeing a
new context at time $t$, NeuralGCB traverses down the subsets starting from
$r=1$. At each level $r$, it evaluates the largest predictive standard
deviation among current set of candidate actions, $A_{r}$, and compares it
with $2^{-r}$.

If this value is smaller than $2^{-r}$, NeuralGCB checks if it can exploit
based on predictions at the $r^{\text{th}}$ level. Specifically, if the
predictive standard deviation of the action that maximizes the UCB score is
$\mathcal{O}(1/\sqrt{t})$ (indicating a high reward with reasonably high
confidence), then NeuralGCB plays that action. Otherwise, it updates $A_{r}$
by eliminating actions with small UCB score and moves to the next level. This
encourages exploitation of less certain actions in a controlled manner as
opposed to SupNeuralUCB which exploits only actions with much higher
certainty.

On the other hand, if the value is greater than $2^{-r}$, NeuralGCB directly
exploits the maximizer of the mean computed using data points in
$\Psi^{(r-1)}$ until the allocated budget for exploitation at level $r$ is
exhausted. It then resorts to more exploratory actions by choosing actions
with large values of $\hat{\sigma}_{t-1}^{(r)}$. The exploitation budget is
set to match the length of exploration sequence at the corresponding level to
ensure an optimal balance of exploitation and exploration and preserve the
optimal regret order while boosting empirical performance.

In addition to improved empirical performance, NeuralGCB takes into
consideration the practical requirements for training the neural nets.
Specifically, as pointed out in Gu et al. (2021), it is practically more
efficient to train the neural net over batches of observations, rather than
sequentially at each step. Consequently, before evaluating the mean and
variance at any level $r$, NeuralGCB retrains the neural net corresponding to
that level only if $q_{r}$ samples have been added to that level since it was
last trained. This index-dependent choice of batch size, $q_{r}$ lends a
natural adaptivity to the retraining frequency by reducing it as time
progresses.

A pseudo code of the algorithm is outlined in Algorithm 1. In the pseudo code,
$\text{UCB}_{t}^{(r)}$ and $\text{LCB}_{t}^{(r)}$ refer to the upper and lower
confidence scores respectively at time $t$ corresponding to index $r$ and are
defined as
$\text{UCB}_{t}^{(r)}(\cdot)=f(\cdot;\mathbf{W}_{t}^{(r)})+\beta\hat{\sigma}_{t}^{(r)}(\cdot)$
and
$\text{LCB}_{t}^{(r)}(\cdot)=f(\cdot;\mathbf{W}_{t}^{(r)})-\beta\hat{\sigma}_{t}^{(r)}(\cdot)$.
GetPredictions is a local routine that calculates the predictive mean and
variance after appropriately retraining the neural net (see supplementary for
a pseudo code). Lastly, the arrays ctr, max_mu and fb are used to store the
exploitation count, maximizer of the neural net output and feedback time
instants. We now formally state the regret guarantees for NeuralGCB in the
following theorem.

######  Theorem 3.

Suppose Assumptions 1 and 2 hold. Consider NeuralGCB given in Algorithm 2,
with $R$ neural nets, as defined in (2) with $L$ hidden layers each of width
$m\geq\text{poly}(T,L,K,\lambda^{-1},\lambda_{0}^{-1},S^{-1},\log(1/\delta))$.
Suppose NeuralGCB is run with a fixed batch size for each group, then the
regret defined in (1) satisfies

$\displaystyle
R(T)=\tilde{\mathcal{O}}\left(\sqrt{T\Gamma_{k}(T)}+\sqrt{T\Gamma_{k}(T)\log(1/\delta)}+\max_{r}q_{r}\Gamma_{k}(T)\right)$

As suggested by the above theorem, NeuralGCB preserves the regret guarantees
of SupNeuralUCB which are much tighter than those of NeuralUCB. Moreover,
these guarantees hold for even for smooth activation functions as opposed to
just for ReLU activation. Furthermore, the above regret guarantees show that
the retraining neural nets only at the end of batches of observations
increases the regret at most with an additive term in the batch size. Our
results also hold with an adaptive batch size (see supplementary material).

Algorithm 1 NeuralGCB

1: Require: Time horizon $T$, maximum initial variance $\sigma_{0}$, error
probability $\delta$

2: Initialize: $R\leftarrow\lceil\log_{2}T\rceil$, Ensemble of $R$ Neural Nets
with $\mathbf{W}_{0}^{(r)}=\mathbf{W}_{0}$,
$\Psi_{0}^{(r)}\leftarrow\emptyset,\ \ \forall\ r\in[R]$,
$\mathcal{H}\leftarrow\emptyset$, arrays ctr, max_mu, fb of size $R$ with all
elements set to $0$, batch sizes $\\{q_{r}\\}_{r=1}^{R}$

3: for $t=1,2,3,\dots T$ do

4: $r\leftarrow 1,\hat{A}_{r}(t)=[K]$

5: while True do

6: Receive the context-action pairs $\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}$

7:
$\\{f(\mathbf{x}_{t,a};\mathbf{W}_{t}^{(r)}),\hat{\sigma}_{t-1}^{(r)}(\mathbf{x}_{t,a})\\}_{a=1}^{K},\mathbf{W}_{t}^{(r)},\texttt{fb}[r]\leftarrow$
GetPredictions$\left(\mathcal{H},\Psi_{t-1}^{(r)},\\{\mathbf{x}_{t,a}\\}_{a=1}^{K},\texttt{fb}[r],\mathbf{W}_{t-1}^{(r)},q_{r}\right)$

8:
$\tilde{\sigma}_{t-1}^{(r)}\leftarrow\max_{a\in\hat{A}_{r}(t)}\hat{\sigma}_{t-1}^{(r)}(x_{t,a})$,
$\texttt{max\\_mu}[r]\leftarrow\operatorname*{arg\,max}_{a\in\hat{A}_{r}(t)}f(x_{t,a};\mathbf{W}_{t-1}^{(r)})$

9: if $\tilde{\sigma}_{t-1}^{(r)}\leq\sigma_{0}2^{-r}$ then

10:
$a_{\text{UCB}}\leftarrow\operatorname*{arg\,max}_{a\in\hat{A}_{r}(t)}\text{UCB}_{t-1}^{(r)}(\mathbf{x}_{t,a})$

11: if ${\sigma}_{t-1}^{(r)}(x_{t,a_{\text{UCB}}})\leq\eta_{0}/\sqrt{t}$ then

12: Choose $a_{t}\leftarrow a_{\text{UCB}}$ and set $\upsilon_{t}\leftarrow 1$

13: Receive $y_{t}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}$ and update
$\mathcal{H}\leftarrow\mathcal{H}\cup\\{(x_{t,a_{t}},y_{t})\\}$

14: Set
$\Psi_{t}^{(r+1)}\leftarrow\Psi_{t-1}^{(r+1)}\cup\\{(t,\upsilon_{t})\\}$ and
$\Psi_{t}^{(r^{\prime})}\leftarrow\Psi_{t-1}^{(r^{\prime})}$ for all
$r^{\prime}\in[R]\setminus\\{r+1\\}$

15: break

16: else

17:
$\hat{A}_{r+1}(t)\leftarrow\\{a\in\hat{A}_{r}(t):\text{UCB}_{t-1}^{(r)}(\mathbf{x}_{t,a})\geq\max_{a^{\prime}\in\hat{A}_{r}(t)}\text{LCB}_{t-1}^{(r)}(\mathbf{x}_{t,a^{\prime}})\\}$,
$r\leftarrow r+1$

18: end if

19: else

20: if $r=1$ or$\ \texttt{ctr}[r]>\alpha_{0}4^{r}$ then

21: Choose any $a_{t}\in\hat{A}_{r}(t)$ such that
$\hat{\sigma}_{t-1}^{(r)}(x_{t,a})>\sigma_{0}2^{-r}$ and set
$\upsilon_{t}\leftarrow 2$

22: else

23: Choose $a_{t}\leftarrow\texttt{max\\_mu}[r-1]$ and set
$\upsilon_{t}\leftarrow 3$

24: end if

25: Receive $y_{t}=h(\mathbf{x}_{t,a_{t}})+\xi_{t}$ and update
$\mathcal{H}\leftarrow\mathcal{H}\cup\\{(x_{t,a_{t}},y_{t})\\}$,
$\texttt{ctr}[r]\leftarrow\texttt{ctr}[r]+1$

26: Set $\Psi_{t}^{(r)}\leftarrow\Psi_{t-1}^{(r)}\cup\\{(t,\upsilon_{t})\\}$
and $\Psi_{t}^{(r^{\prime})}\leftarrow\Psi_{t-1}^{(r^{\prime})}$ for all
$r^{\prime}\in[R]\setminus\\{r\\}$

27: break

28: end if

29: end while

30: end for

##  5 Empirical Studies

In this section, we provide numerical experiments on comparing NeuralGCB with
several representative baselines, namely, LinUCB (Chu et al., 2011), NeuralUCB
(Zhou et al., 2020), NeuralTS (Zhang et al., 2021), SupNeuralUCB (Kassraie and
Krause, 2022) and Batched NeuralUCB (Gu et al., 2021).

We perform the empirical studies on three synthetic and two real-world
datasets. We first compare NeuralGCB with the fully sequential algorithms
(LinUCB, NeuralUCB, NeuralTS ans SupNeuralUCB). We then compare the regret
incurred and the time taken by NeuralGCB, NeuralUCB and Batch NeuralUCB. We
perform both set of experiments with two different activation functions. The
construction of the synthetic datasets and the experimental settings are
described below.

(a) $h_{1}(x)$ with $\sigma_{1}(x)$

(b) $h_{1}(x)$ with $\sigma_{2}(x)$

(c) Batched algorithms on $h_{1}(x)$

(d) $h_{2}(x)$ with $\sigma_{1}(x)$

(e) $h_{2}(x)$ with $\sigma_{2}(x)$

(f) Batched algorithms on $h_{2}(x)$

(g) Mushroom with $\sigma_{1}(x)$

(h) Mushroom with $\sigma_{2}(x)$

(i) Batched algorithms on Mushroom

Figure 1: First, second and third rows correspond to the reward functions
$h_{1}(x)$, $h_{2}(x)$ and the Mushroom dataset, respectively. The two
leftmost columns show the cumulative regret incurred by the algorithms against
number of steps, with $\sigma_{1}$ activation functions for the first column
and $\sigma_{2}$ for the second. The rightmost column compares the regret
incurred and the time taken (in seconds) for batched and sequential versions
of NeuralUCB and NeuralGCB.

###  5.1 Datasets

For each of the synthetic datasets, we construct a contextual bandit problem
with a feature dimension of $d=10$ and $K=4$ actions per context running over
a time horizon of $T=2000$ rounds. The set of context vectors
$\\{\\{\mathbf{x}_{t,a}\\}_{a=1}^{K}\\}_{t=1}^{T}$ are drawn uniformly from
the unit sphere. Similar to Zhou et al. (2020), we consider the following
three reward functions:

$\displaystyle h_{1}(\mathbf{x})=4|\mathbf{a}^{\top}\mathbf{x}|^{2};\quad\
h_{2}(\mathbf{x})=4\sin^{2}(\mathbf{a}^{\top}\mathbf{x});\quad\
h_{3}(\mathbf{x})=\|\mathbf{A}\mathbf{x}\|_{2}.$ (9)

For the above functions, the vector $\mathbf{a}$ is drawn uniformly from the
unit sphere and each entry of matrix $\mathbf{A}$ is randomly generated from
$\mathcal{N}(0,0.25)$.

We also consider two real datasets for classification namely Mushroom and
Statlog (Shuttle), both of which are available on the UCI repository (Dua and
Graff, 2017). The classification problem is then converted into a contextual
bandit problem using techniques outlined in Li et al. (2010). Each datapoint
in the dataset $(\mathbf{x},y)\in\mathbb{R}^{d}\times\mathbb{R}$ is
transformed into $K$ vectors of the form
${\mathbf{x}}^{(1)}=(\mathbf{x},\mathbf{0},\dots,\mathbf{0})\dots,{\mathbf{x}}^{(K)}=(\mathbf{0},\dots,\mathbf{0},\mathbf{x})\in\mathbb{R}^{Kd}$
corresponding to the $K$ actions associated with context $\mathbf{x}$. Here
$K$ denotes the number of classes in the original classification problem. The
reward function is set to $h({\mathbf{x}}^{(k)})=\mathbbm{1}\\{y=k\\}$, that
is, the agent receives a reward of $1$ if they classify the context correctly
and $0$ otherwise. We present the results for $h_{1}(x),h_{2}(x)$ and the
Mushroom dataset in the main paper, and the additional results in the
supplementary material.

###  5.2 Experimental Setting

For all the experiments, the rewards are generated by adding zero mean
Gaussian noise with a standard deviation of $0.1$ to the reward function. All
the experiments are run for a time horizon of $T=2000$. We report the regret
averaged over $10$ Monte Carlo runs with different random seeds. For the real
datasets, we shuffle the context vectors for each Monte Carlo run. For all the
algorithms, we set the parameter $\nu$ to $0.1$, and $S$, the RKHS norm of the
reward, to $4$ for synthetic functions, and $1$ for real datasets. The
exploration parameter $\beta_{t}$ is set to the value prescribed by each
algorithm.

We consider a 2 layered neural net for all the experiments as described in
Equation (2). We carry two sets of experiments each with different activation
functions, namely $\sigma_{1}$ (or equivalently, ReLU) and $\sigma_{2}$. For
the experiments with $\sigma_{1}$ as the activation, we set the number of
hidden neurons to $m=20$ and $m=50$ for synthetic and real datasets
respectively. Similarly, for $\sigma_{2}$, $m$ is set to $30$ and $80$ for
synthetic and real datasets, respectively. For all the experiments, we perform
a grid search for $\lambda$ and $\eta$ over $\\{0.05,0.1,0.5\\}$ and
$\\{0.001,0.01,0.1\\}$, respectively, and choose the best ones for each
algorithm. The number of epochs is set to $200$ for synthetic datasets and
Mushroom, and to $400$ for Statlog. For the experiments with sequential
algorithms, we retrain the neural nets at every step, including NeuralGCB. For
Batched NeuralUCB, we use a fixed batch size of $10$ for synthetic datasets,
and $20$ for Mushroom. For NeuralGCB we set batch size to $q_{r}=5\cdot
2^{r-1}$ for synthetic datasets, and $q_{r}=5\cdot 2^{r+1}$ for Mushroom. More
details and additional experiments are given in Appendix E.

###  5.3 Results

The two leftmost columns in Fig. 1show that NeuralGCB outperforms other
algorithms in the case of both synthetic and real world datasets,
corroborating the theoretical claims. That holds true for both set of
experiments with different activation functions, further bolstering the
practical efficiency of the proposed algorithm. In addition, the regret
incurred by the algorithms in experiments with $\sigma_{2}$ as the activation
is less than that for the experiments with $\sigma_{1}$ as the activation,
demonstrating the effect of smooth kernels on the performance of the
algorithms in practice.

In the third column, we compare the regret and running time between the
batched and the sequential versions of NeuralUCB and NeuralGCB. We plot the
regret incurred against time taken for different training schedules for $10$
different runs. For all functions, the regret incurred by the batched version
is comparable to that of the sequential version while having a significantly
less running time. Furthermore, NeuralGCB has a smaller regret compared to
Batched NeuralUCB for comparable running times.

##  6 Conclusion

In this work, we studied the problem of neural contextual bandits with general
set of smooth activation functions. We established non-asymptotic error bounds
on the difference between an overparametrized neural net and its corresponding
NT kernel along with confidence bounds for prediction using neural nets under
this general setting. Furthermore, we proposed a new algorithm that incurs
sublinear regret under this general setting is also efficient in practice, as
demonstrated by extensive empirical studies.

## References

  * Abbasi-Yadkori et al. (2011) Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24, 2011.
  * Arora et al. (2019) S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang.  On exact computation with an infinitely wide neural net.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Auer (2002) P. Auer.  Using confidence bounds for exploitation-exploration trade-offs.  _Journal of Machine Learning Research_ , 3(Nov):397–422, 2002.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, and P. Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2):235–256, 2002.
  * Boucheron et al. (2013) S. Boucheron, G. Lugosi, and P. Massart.  _Concentration Inequalities - A Nonasymptotic Theory of Independence_.  Oxford University Press, 2013.  ISBN 978-0-19-953525-5.  doi: 10.1093/acprof:oso/9780199535255.001.0001.  URL https://doi.org/10.1093/acprof:oso/9780199535255.001.0001.
  * Bouneffouf and Rish (2019) D. Bouneffouf and I. Rish.  A survey on practical applications of multi-armed and contextual bandits.  _arXiv preprint arXiv:1904.10040_ , 2019.
  * Calandriello et al. (2019) D. Calandriello, L. Carratino, A. Lazaric, M. Valko, and L. Rosasco.  Gaussian process optimization with adaptive sketching: Scalable and no regret.  In _Conference on Learning Theory_ , pages 533–557. PMLR, 2019.
  * Camilleri et al. (2021) R. Camilleri, K. Jamieson, and J. Katz-Samuels.  High-dimensional experimental design and kernel bandits.  In _International Conference on Machine Learning_ , pages 1227–1237. PMLR, 2021.
  * Chen et al. (2021) C. Chen, L. Luo, W. Zhang, Y. Yu, and Y. Lian.  Efficient and robust high-dimensional linear contextual bandits.  In _Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence_ , pages 4259–4265, 2021.
  * Chowdhury and Gopalan (2017) S. R. Chowdhury and A. Gopalan.  On kernelized multi-armed bandits.  In _International Conference on Machine Learning_ , pages 844–853, 2017.
  * Chu et al. (2011) W. Chu, L. Li, L. Reyzin, and R. Schapire.  Contextual bandits with linear payoff functions.  In _Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics_ , pages 208–214. JMLR Workshop and Conference Proceedings, 2011.
  * Cramér (1938) H. Cramér.  Sur un nouveau théorème-limite de la théorie des probabilités.  Actual. sci. industr. 736, 5-23. (Confér. internat. Sci. math. Univ. Genève. Théorie des probabilités. III: Les sommes et les fonctions de variables aléatoires.) (1938)., 1938.
  * Daniely et al. (2016) A. Daniely, R. Frostig, and Y. Singer.  Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity.  In _Advances in Neural Information Processing Systems_ , pages 2261–2269, 2016.
  * Dua and Graff (2017) D. Dua and C. Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Gantert et al. (2014) N. Gantert, K. Ramanan, and F. Rembart.  Large deviations for weighted sums of stretched exponential random variables.  _Electronic Communications in Probability_ , 19, 2014.  ISSN 1083589X.  doi: 10.1214/ECP.v19-3266.
  * Gu et al. (2021) Q. Gu, A. Karbasi, K. Khosravi, V. Mirrokni, and D. Zhou.  Batched neural bandits.  _arXiv preprint arXiv:2102.13028_ , 2021.
  * Jacot et al. (2018) A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _arXiv preprint arXiv:1806.07572_ , 2018.
  * Kassraie and Krause (2022) P. Kassraie and A. Krause.  Neural contextual bandits without regret.  In _AISTATS_ , 2022.
  * Langford and Zhang (2007) J. Langford and T. Zhang.  The epoch-greedy algorithm for multi-armed bandits with side information.  _Advances in neural information processing systems_ , 20, 2007.
  * Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Li et al. (2019a) B. Li, S. Tang, and H. Yu.  Better approximations of high dimensional smooth functions by deep neural networks with rectified power units.  _arXiv preprint arXiv:1903.05858_ , 2019a.
  * Li et al. (2010) L. Li, W. Chu, J. Langford, and R. E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th International Conference on World Wide Web, WWW ’10_ , pages 661–670, feb 2010.  ISBN 9781605587998.  doi: 10.1145/1772690.1772758.  URL http://arxiv.org/abs/1003.0146http://dx.doi.org/10.1145/1772690.1772758.
  * Li et al. (2019b) Y. Li, Y. Wang, and Y. Zhou.  Nearly minimax-optimal regret for linearly parameterized bandits.  In _Conference on Learning Theory_ , pages 2173–2174. PMLR, 2019b.
  * Li and Scarlett (2022) Z. Li and J. Scarlett.  Gaussian process bandit optimization with few batches.  In _AISTATS_ , 2022.
  * Liu et al. (2020) C. Liu, L. Zhu, and M. Belkin.  On the linearity of large non-linear models: when and why the tangent kernel is constant.  _Advances in Neural Information Processing Systems_ , 33:15954–15964, 2020.
  * Salgia et al. (2021) S. Salgia, S. Vakili, and Q. Zhao.  A domain-shrinking based Bayesian optimization algorithm with order-optimal regret performance.  _Conference on Neural Information Processing Systems_ , 34, 2021.
  * Shahriari et al. (2015) B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas.  Taking the human out of the loop: A review of bayesian optimization.  _Proceedings of the IEEE_ , 104(1):148–175, 2015\.
  * Sitzmann et al. (2020) V. Sitzmann, J. Martel, A. Bergman, D. Lindell, and G. Wetzstein.  Implicit neural representations with periodic activation functions.  _Advances in Neural Information Processing Systems_ , 33:7462–7473, 2020.
  * Snoek et al. (2012) J. Snoek, H. Larochelle, and R. P. Adams.  Practical bayesian optimization of machine learning algorithms.  _Advances in neural information processing systems_ , 25, 2012.
  * Srinivas et al. (2010) N. Srinivas, A. Krause, S. Kakade, and M. Seeger.  Gaussian process optimization in the bandit setting: no regret and experimental design.  In _International Conference on Machine Learning_ , pages 1015–1022. Omnipress, 2010.
  * Vakili et al. (2021a) S. Vakili, N. Bouziani, S. Jalali, A. Bernacchia, and D.-s. Shiu.  Optimal order simple regret for Gaussian process bandits.  In _Conference on Neural Information Processing Systems_ , 2021a.
  * Vakili et al. (2021b) S. Vakili, M. Bromberg, J. Garcia, D.-s. Shiu, and A. Bernacchia.  Uniform generalization bounds for overparameterized neural networks.  _arXiv preprint arXiv:2109.06099_ , 2021b.
  * Vakili et al. (2021c) S. Vakili, J. Scarlett, and T. Javidi.  Open problem: Tight online confidence intervals for RKHS elements.  In _Conference on Learning Theory_ , pages 4647–4652. PMLR, 2021c.
  * Valko et al. (2013) M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini.  Finite-time analysis of kernelised contextual bandits.  _arXiv preprint arXiv:1309.6869_ , 2013.
  * Wang et al. (2021) T. Wang, D. Zhou, and Q. Gu.  Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints.  2021\.  URL http://arxiv.org/abs/2101.02195.
  * Zhang (2005) T. Zhang.  Learning bounds for kernel regression using effective data dimensionality.  _Neural Computation_ , 17(9):2077–2098, 2005\.
  * Zhang et al. (2021) W. Zhang, D. Zhou, L. Li, and Q. Gu.  Neural Thompson sampling.  In _International Conference on Learning Representations_ , 2021.
  * Zhou et al. (2020) D. Zhou, L. Li, and Q. Gu.  Neural contextual bandits with UCB-based exploration.  In _International Conference on Machine Learning_ , pages 11492–11502. PMLR, 2020.

## Appendix

We present the proofs of the theorems and lemmas stated in the main paper, as
well as additional empirical results, in the appendix. The appendix is
structured as follows: In Appendix A, we provide the proof of Theorem 1, while
we defer the proof of auxiliary lemmas to Appendix B. Proof of Theorem 2 is
given in Appendix C. Further details on NeuralGCB and proof of Theorem 3 are
provided in Appendix D. Lastly, the details on empirical studies and further
results are reported in Appendix E.

##  Appendix A Proof of Theorem 1

Before we provide the proof of Theorem 1, we first set up some preliminaries
and notation that would be useful throughout the proof.

###  A.1 Proof Preliminaries

####  A.1.1 Notation

For any $n\in\mathbb{N}$, $[n]$ denotes the set $\\{1,2,\dots,n\\}$. For any
vector $\mathbf{v}\in\mathbb{R}^{n}$, $\text{diag}(\mathbf{v})$ is the
$\mathbb{R}^{n\times n}$ diagonal matrix with the elements on $\mathbf{v}$ on
its diagonal entries. $\|\mathbf{v}\|$ denotes the $L_{2}$ norm of the vector
$\mathbf{v}$. $\|\mathbf{M}\|_{2}$ and $\|\mathbf{M}\|_{F}$ denotes the
spectral and Frobenius norms respectively of a matrix $\mathbf{M}$. For events
$A$ and $B$, we define $A\Rightarrow B:=\neg A\lor B$. For matrix
$\mathbf{A}$, we denote the projection matrix for the column space of
$\mathbf{A}$ by
$\boldsymbol{\Pi}_{\mathbf{A}}:=\mathbf{A}\mathbf{A}^{\dagger}$, where
$\mathbf{A}^{\dagger}$ denotes the pseudo-inverse of $\mathbf{A}$. Similarly,
we denote the orthogonal projection matrix as
$\boldsymbol{\Pi}_{\mathbf{A}}^{\perp}:=\mathbf{I}-\mathbf{A}\mathbf{A}^{\dagger}$.
For two random variables, $X$ and $Y$, $X\overset{d}{=}_{A}Y$ means $X$ is
equal to $Y$ in distribution conditioned on the $\sigma$-algebra generated by
the event $A$. For any $\rho\in[-1,1]$, we use $\Sigma_{\rho}$ to denote the
matrix $\begin{pmatrix}1&\rho\\\ \rho&1\end{pmatrix}$. Lastly, for
$n\in\mathbb{N}$, we define $(2n-1)!!=\prod_{i=1}^{n}(2i-1)$. For example
$3!!=3$ and $5!!=15$.

####  A.1.2 Fully connected Neural Network

In this proof, we consider a general fully connected neural net consisting of
$L$ hidden layers defined recursively as follows:

$\displaystyle{\mathbf{f}}^{(l)}(\mathbf{x})={\mathbf{W}}^{(l)}{\mathbf{h}}^{(h-1)}(\mathbf{x})\in\mathbb{R}^{d_{l}},\quad{\mathbf{h}}^{(l)}(\mathbf{x})=\sqrt{\frac{c_{\sigma}}{d_{l}}}\sigma\left({\mathbf{f}}^{(l)}(\mathbf{x})\right)\in\mathbb{R}^{d_{l}},\
\ \ \ l=1,2,\dots,L,$ (10)

where ${\mathbf{h}}^{(0)}(\mathbf{x})=\mathbf{x}$ and
$\mathbf{x}\in\mathcal{X}$ is the input to the network. In the above
expression, ${\mathbf{W}}^{(l)}\in\mathbb{R}^{d_{l}\times d_{l-1}}$ is the
weight matrix in the $l^{\text{th}}$ layer for $l\in[L]$ and $d_{0}=d$,
$\sigma(\cdot):\mathbb{R}\to\mathbb{R}$ is a coordinate-wise activation
function and the constant
$c_{\sigma}:=\left(\mathbb{E}_{z\sim\mathcal{N}(0,1)}[\sigma(z)^{2}]\right)^{-1}$.
The output of the neural network is given by its last layer defined as
follows:

$\displaystyle f(\mathbf{x};\mathbf{W})$
$\displaystyle={\mathbf{f}}^{(L+1)}(\mathbf{x})={\mathbf{W}}^{(L+1)}{\mathbf{h}}^{(L)}(\mathbf{x}),$
(11)

where ${\mathbf{W}}^{(L+1)}\in\mathbb{R}^{1\times d_{L}}$ is the weight matrix
in the final layer, and
$\mathbf{W}=({\mathbf{W}}^{(1)},{\mathbf{W}}^{(2)},\dots,{\mathbf{W}}^{(L+1)})$
represents all the parameters of the network. Recall that the domain is
assumed to be the hypersphere $\mathbb{S}^{d-1}$. Consequently,
$\|\mathbf{x}\|=1$ for all $\mathbf{x}\in\mathcal{X}$. This is just the
generalization of the of the neural net defined in eqn. (2) with possibly
different width in each layer.

The partial derivative of the output of the neural network with respect to a
particular weight matrix is given as

$\displaystyle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}}={\mathbf{b}}^{(l)}(\mathbf{x})\cdot\left({\mathbf{h}}^{(l-1)}(\mathbf{x})\right)^{\top},\quad
l=1,2,\dots,L+1,$ (12)

where ${\mathbf{b}}^{(l)}(\mathbf{x})$ is defined recursively as

$\displaystyle{\mathbf{b}}^{(l)}(\mathbf{x})=\begin{cases}1&l=L+1,\\\
\sqrt{\dfrac{c_{\sigma}}{d_{l}}}{\mathbf{D}}^{(l)}(\mathbf{x})\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{x})&l=1,2,\dots,L.\end{cases}$
(13)

In the above definition,

$\displaystyle{\mathbf{D}}^{(l)}(\mathbf{x}):=\text{diag}\left(\sigma^{\prime}\left({\mathbf{f}}^{(l)}(\mathbf{x})\right)\right)\in\mathbb{R}^{d_{l}\times
d_{l}},$ (14)

is a diagonal matrix, where $\sigma^{\prime}(\cdot)$ is the derivative of the
activation function $\sigma$ and is also applied coordinate wise. Note that
${\mathbf{b}}^{(l)}(\mathbf{x})\in\mathbb{R}^{d_{l}}$ for $l=1,2,\dots,L$ and
${\mathbf{b}}^{(L+1)}(\mathbf{x})\in\mathbb{R}$. In other words,
${\mathbf{b}}^{(l)}(\mathbf{x})$ is the gradient of output of the neural
network $f(\mathbf{x};\mathbf{W})$ with respect to ${\mathbf{f}}^{(l)}$, the
pre-activation of layer $l$.

###  A.2 Neural Tangent Kernel

In the infinite width limit, the pre-activation functions ${\mathbf{f}}^{(l)}$
at every hidden layer $l\in[L]$ has all its coordinates tending to i.i.d.
centered Gaussian Processes with covariance matrix
${\Sigma}^{(l-1)}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ defined
recursively for $l\in[L]$ as:

$\displaystyle{\Sigma}^{(0)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=\mathbf{x}^{\top}\mathbf{x}^{\prime},$
$\displaystyle{\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=\begin{bmatrix}{\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x})&{\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\\\
{\Sigma}^{(l-1)}(\mathbf{x}^{\prime},\mathbf{x})&{\Sigma}^{(l-1)}(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\\
\end{bmatrix},$ $\displaystyle{\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=c_{\sigma}\mathbb{E}_{(u,v)\sim\mathcal{N}(0,{\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}[\sigma(u)\sigma(v)].$
(15)

Similar to ${\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$, we also define
${\dot{\Sigma}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$ as follows:

$\displaystyle{\dot{\Sigma}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=c_{\sigma}\mathbb{E}_{(u,v)\sim\mathcal{N}(0,{\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}[\sigma^{\prime}(u)\sigma^{\prime}(v)],$
(16)

for $l\in[L]$ and ${\dot{\Sigma}}^{(L+1)}(\mathbf{x},\mathbf{x}^{\prime})=1$
for $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$. The final NTK expression
for the fully-connected network is given as

$\displaystyle{\Theta}^{(L)}(\mathbf{x},\mathbf{x}^{\prime})=\sum_{l=1}^{L+1}\left({\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})\right).$
(17)

Note that this is same as $k(\mathbf{x},\mathbf{x}^{\prime})$ referred to in
the main text.

###  A.3 The Activation Function

In this work, we assume that the activation function
$\sigma\in\mathcal{A}_{\sigma}$, where
$\mathcal{A}_{\sigma}=\\{\sigma_{s}(x):s\in\mathbb{N}\\}$ and
${\sigma}_{s}(x)=(\max(0,x))^{s}$. Note that ${\sigma}_{1}(x)$ corresponds to
the popular ReLU activation function and existing results hold only for
${\sigma}_{1}(x)$.

We state some definitions which we will be later used to establish certain
properties of activation functions in $\mathcal{A}$.

######  Fact 1.

(Vakili et al. [2021b]) The normalizing constant
$c_{\sigma_{s}}=\dfrac{2}{(2s-1)!!}$ for all $\sigma_{s}\in\mathcal{A}$.

For simplicity of notation we use $c_{s}$ instead of $c_{\sigma_{s}}$ for the
rest of the proof.

######  Definition 1.

A function $f:\mathbb{R}\to\mathbb{R}$ is said to be $\alpha$-homogeneous, if
$f(\lambda x)=\lambda^{\alpha}f(x)$ for all $x\in\mathbb{R}$ and $\lambda>0$.

It is straightforward to note that $\sigma_{s}(x)$ is $s$-homogeneous.

Let $\mathcal{M}_{+}(d)$ denote the set of positive semi-definite matrices of
dimension $d$, that is, $\mathcal{M}_{+}=\\{\mathbf{M}\in\mathbb{R}^{d\times
d}:\mathbf{x}^{\top}\mathbf{M}\mathbf{x}\geq 0\ \ \forall\
\mathbf{x}\in\mathbb{R}^{d}\\}$. Similarly, we use $\mathcal{M}_{++}(d)$ to
denote the class of positive definite matrices of dimension $d$. For
$\gamma\in[0,1]$, we denote

$\displaystyle\mathcal{M}_{+}^{\gamma}=\left\\{\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{12}&\Sigma_{22}\\\
\end{pmatrix}\in\mathcal{M}_{+}(2)\bigg{|}1-\gamma\leq\Sigma_{11},\Sigma_{22}\leq
1+\gamma\right\\}.$ (18)

######  Definition 2.

The dual of an activation function $\sigma(\cdot)$ is the function
$\bar{\sigma}:[-1,1]\to\mathbb{R}$ defined as

$\displaystyle\bar{\sigma}(\rho)=c_{\sigma}\mathbb{E}_{(X,Y)\sim\mathcal{N}(0,\Sigma_{\rho})}[\sigma(X)\sigma(Y)].$
(19)

Note that from definition of $c_{\sigma}$, $\bar{\sigma}(\rho)\in[-1,1]$ and
$\bar{\sigma}(1)=1$.

######  Fact 2 (Daniely et al. [2016], Lemma 11).

The dual $\bar{\sigma}$ is continuous in $[-1,1]$, smooth in $(-1,1)$, convex
in $[0,1]$ and is non-decreasing.

The dual of an activation function can be extended to
$\breve{\sigma}:\mathcal{M}_{+}(2)\to\mathbb{R}$ as
$\breve{\sigma}(\Sigma)=c_{\sigma}\mathbb{E}_{(X,Y)\sim\mathcal{N}(0,\Sigma)}[\sigma(X)\sigma(Y)]$.
Note that if $\Sigma=\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{12}&\Sigma_{22}\\\ \end{pmatrix}$ and $\sigma$ is $k$-homogeneous, we
have,

$\displaystyle\breve{\sigma}(\Sigma)=(\Sigma_{11}\Sigma_{22})^{k/2}\bar{\sigma}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right).$

Let $\bar{\sigma}_{s}$ be the dual function of
$\sigma_{s}\in\mathcal{A}_{\sigma}$ for all $s\in\mathbb{N}$ and
$\bar{\mathcal{A}}_{\sigma}=\\{\bar{\sigma}_{s}:s\in\mathbb{N}\\}$ denote the
set of dual functions. It is not difficult to note that
$\bar{\sigma}_{s}(-1)=0$ and $\bar{\sigma}_{s}(1)=1$ for all $s\in\mathbb{N}$.
Since $\bar{\sigma}_{s}$ is non-decreasing, $\bar{\sigma}_{s}(\rho)\in[0,1]$
for all $\rho\in[-1,1]$.

######  Fact 3 (Vakili et al. [2021b], Lemma 1).

The functions in $\bar{\mathcal{A}}_{\sigma}$ satisfy,

$\displaystyle\bar{\sigma}_{s}^{\prime}(\rho)=\frac{s^{2}}{2s-1}\bar{\sigma}_{s-1}(\rho)$
(20)

for $s>1$. Here $\bar{\sigma}_{s}^{\prime}$ denotes the derivative of
$\bar{\sigma}_{s}$.

Consequently,
$|\bar{\sigma}_{s}^{\prime}(\rho)|\leq\dfrac{s^{2}}{2s-1}|\bar{\sigma}_{s-1}(\rho)|\leq\dfrac{s^{2}}{2s-1}$.
Thus, $\bar{\sigma}_{s}$ is $s^{2}/(2s-1)$ Lipschitz.

######  Definition 3.

For any function $\sigma_{s}\in\mathcal{A}_{\sigma}$, we define
$\mu_{s,\rho}:=\mathbb{E}_{(X,Y)\sim\mathcal{N}(0,\Sigma_{\rho})}[\sigma_{s}(X)\sigma_{s}(Y)]=\dfrac{\bar{\sigma}_{s}}{c_{s}}$.

###  A.4 Proof of Lemma 1

The central piece in the proof of Theorem 1 is Lemma 1. We focus our attention
on first proving Lemma 1. Since the proof is involved, we first provide an
outline of the proof to give the reader an overview of the approach before
delving into the technical details.

Informally, Lemma 1 states that for sufficiently large network widths, the
following relation holds with probability of at least $1-\delta$ over the
random initialization of the network weights.

$\displaystyle\left|\left\langle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial\mathbf{W}},\frac{\partial
f(\mathbf{x}^{\prime};\mathbf{W})}{\partial\mathbf{W}}\right\rangle-{\Theta}^{(L)}(\mathbf{x},\mathbf{x}^{\prime})\right|\leq(L+1)\varepsilon.$

Firstly, note that

$\displaystyle\left\langle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial\mathbf{W}},\frac{\partial
f(\mathbf{x}^{\prime};\mathbf{W})}{\partial\mathbf{W}}\right\rangle=\sum_{l=1}^{L+1}\left\langle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}},\frac{\partial
f(\mathbf{x}^{\prime};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}}\right\rangle$

and recall that

$\displaystyle{\Theta}^{(L)}(\mathbf{x},\mathbf{x}^{\prime})=\sum_{l=1}^{L+1}\left({\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})\right).$

Using these relations, note that it is sufficient to show that,

$\displaystyle\left|\left\langle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}},\frac{\partial
f(\mathbf{x}^{\prime};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}}\right\rangle-{\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})\right|\leq\varepsilon$
(21)

holds for all $l\in[L]$ with probability $1-\delta$. Furthermore, we have,

$\displaystyle\left\langle\frac{\partial
f(\mathbf{x};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}},\frac{\partial
f(\mathbf{x}^{\prime};\mathbf{W})}{\partial{\mathbf{W}}^{(l)}}\right\rangle$
$\displaystyle=\left\langle{\mathbf{b}}^{(l)}(\mathbf{x})\cdot\left({\mathbf{h}}^{(l-1)}(\mathbf{x})\right)^{\top},{\mathbf{b}}^{(l)}(\mathbf{x}^{\prime})\cdot\left({\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right)^{\top}\right\rangle$
$\displaystyle=\left\langle{\mathbf{h}}^{(l-1)}(\mathbf{x}),{\mathbf{h}}^{(l-1)}(\mathbf{x})^{\prime}\right\rangle\left\langle{\mathbf{b}}^{(l)}(\mathbf{x}),{\mathbf{b}}^{(l)}(\mathbf{x}^{\prime})\right\rangle.$

The proof revolves around establishing
$\left\langle{\mathbf{h}}^{(l-1)}(\mathbf{x}),{\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right\rangle$
is close to ${\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})$ while
$\left\langle{\mathbf{b}}^{(l)}(\mathbf{x}),{\mathbf{b}}^{(l)}(\mathbf{x}^{\prime})\right\rangle$
is close to
$\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})$. On
combining these two relations, we obtain the result in (21) and consequently
prove the theorem.

Throughout the proof, we fix some $s\in\mathbb{N}$ and hence
$\sigma=\sigma_{s}$. Recall from equation (15), we have,

$\displaystyle{\Sigma}^{(0)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=\mathbf{x}^{\top}\mathbf{x}^{\prime},$
$\displaystyle{\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=\begin{bmatrix}{\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x})&{\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})\\\
{\Sigma}^{(l-1)}(\mathbf{x}^{\prime},\mathbf{x})&{\Sigma}^{(l-1)}(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\\
\end{bmatrix},$ $\displaystyle{\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})$
$\displaystyle=c_{s}\mathbb{E}_{(u,v)\sim\mathcal{N}(0,{\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}[\sigma_{s}(u)\sigma_{s}(v)].$

Since $\|\mathbf{x}\|=1$ for all $x\in\mathcal{X}$,
${\Sigma}^{(0)}(\mathbf{x},\mathbf{x})=1$ for all $x\in\mathcal{X}$. Using
induction, we can establish that ${\Sigma}^{(l)}(\mathbf{x},\mathbf{x})=1$ for
all $x\in\mathcal{X}$, for all $l\in\\{0,1,2,\dots,L\\}$. The base case
follows immediately as ${\Sigma}^{(0)}(\mathbf{x},\mathbf{x})=1$ for all
$x\in\mathcal{X}$. Assume true for $l-1$. Consequently, we have,
${\Lambda}^{(l)}(\mathbf{x},\mathbf{x})=\begin{bmatrix}1&1\\\ 1&1\\\
\end{bmatrix}$. On plugging this value in the definition of
${\Sigma}^{(l)}(\mathbf{x},\mathbf{x})$, we obtain
${\Sigma}^{(l)}(\mathbf{x},\mathbf{x})=1$, completing the inductive step. As a
result, $|{\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})|\leq 1$ for all
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$ and hence we can write
${\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})=\bar{\sigma}_{s}({\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime}))$.

As the final step before the proof, we define a sequence of events which will
be used throughout the proof. Let
${\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}):={\mathbf{D}}^{(l)}(\mathbf{x}){\mathbf{D}}^{(l)}(\mathbf{x}^{\prime})$.
We define the following events:

  * •

$\displaystyle\mathcal{A}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{1})=\left\\{\left|\left({\mathbf{h}}^{(l)}(\mathbf{x})\right)^{\top}{\mathbf{h}}^{(l)}(\mathbf{x}^{\prime})-{\Sigma}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right|\leq\varepsilon_{1}\right\\}$,

  * •

$\displaystyle\bar{\mathcal{A}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{1})=\mathcal{A}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{1})\cap\mathcal{A}^{l}(\mathbf{x},\mathbf{x},\varepsilon_{1})\cap\mathcal{A}^{l}(\mathbf{x}^{\prime},\mathbf{x}^{\prime},\varepsilon_{1})$

  * •

$\displaystyle\bar{\mathcal{A}}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{1})=\bigcap_{l=0}^{L}\bar{\mathcal{A}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{1})$

  * •

$\displaystyle\mathcal{B}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{2})=\left\\{\left|\left\langle{\mathbf{b}}^{(l)}(\mathbf{x}),{\mathbf{b}}^{(l)}(\mathbf{x}^{\prime})\right\rangle-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})\right|\leq\varepsilon_{2}\right\\}$

  * •

$\displaystyle\bar{\mathcal{B}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{2})=\mathcal{B}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{2})\cap\mathcal{B}^{l}(\mathbf{x},\mathbf{x},\varepsilon_{2})\cap\mathcal{B}^{l}(\mathbf{x}^{\prime},\mathbf{x}^{\prime},\varepsilon_{2})$

  * •

$\displaystyle\bar{\mathcal{B}}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{2})=\bigcap_{l=1}^{L+1}\bar{\mathcal{B}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{2})$

  * •

$\displaystyle\bar{\mathcal{C}}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{3})=\\{|f(\mathbf{x};\mathbf{W})|\leq\varepsilon_{3},|f(\mathbf{x}^{\prime};\mathbf{W})|\leq\varepsilon_{3}\\}$

  * •

$\displaystyle\mathcal{D}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})=\left\\{\left|c_{s}\dfrac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}{d_{l}}-{\dot{\Sigma}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right|<\varepsilon_{4}\right\\}$

  * •

$\displaystyle\bar{\mathcal{D}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})=\mathcal{D}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})\cap\mathcal{D}^{l}(\mathbf{x},\mathbf{x},\varepsilon_{4})\cap\mathcal{D}^{l}(\mathbf{x}^{\prime},\mathbf{x}^{\prime},\varepsilon_{4})$

  * •

$\displaystyle\bar{\mathcal{D}}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})=\bigcap_{l=1}^{L+1}\bar{\mathcal{D}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})$

  * •

$\displaystyle\mathcal{E}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{5})=\left\\{\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\|_{2}<\varepsilon_{5}\right\\}$

  * •

$\displaystyle\bar{\mathcal{E}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{5})=\mathcal{E}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{4})\cap\mathcal{E}^{l}(\mathbf{x},\mathbf{x},\varepsilon_{4})\cap\mathcal{E}^{l}(\mathbf{x}^{\prime},\mathbf{x}^{\prime},\varepsilon_{5})$

  * •

$\displaystyle\bar{\mathcal{E}}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{5})=\bigcap_{l=1}^{L+1}\bar{\mathcal{E}}^{l}(\mathbf{x},\mathbf{x}^{\prime},\varepsilon_{5})$

We also state the following two Lemmas taken from Arora et al. [2019] which
are used at several points in the proof before beginning with the first part.

######  Lemma 2.

For any two events, $A$ and $B$, $\Pr(A\Rightarrow B)\geq\Pr(B|A)$.

######  Lemma 3.

Let $\mathbf{w}\sim\mathcal{N}(0,\mathbf{I}_{d})$,
$\mathbf{G}\in\mathbb{R}^{d\times k}$ be a fixed matrix and
$\mathbf{F}=\mathbf{w}^{\top}\mathbf{G}$ be a random matrix. Then, conditioned
on the value of $\mathbf{F}$, $\mathbf{w}$ remains Gaussian in the null space
of the row space of $\mathbf{G}$. Mathematically,

$\displaystyle\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\mathbf{w}\overset{d}{=}_{\mathbf{F}=\mathbf{w}^{\top}\mathbf{G}}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\tilde{\mathbf{w}},$

where $\tilde{\mathbf{w}}$ is a i.i.d. copy of $\mathbf{w}$.

####  A.4.1 Pre-activations are close to the NTK matrix

In the first step, we show that
$\left\langle{\mathbf{h}}^{(l-1)}(\mathbf{x}),{\mathbf{h}}^{(l-1)}(\mathbf{x}^{\prime})\right\rangle$
is close to ${\Sigma}^{(l-1)}(\mathbf{x},\mathbf{x}^{\prime})$. We formalize
this idea in the following lemma.

######  Lemma 4.

For $\sigma(z)=\sigma_{s}(z)$ and
$[{\mathbf{W}}^{(l)}]_{ij}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,1)$ for
all $i\in[d_{l+1}],j\ \in[d_{l}]$ and $l\in\\{0,1,2,\dots,L\\}$. There exist
constants $c_{1},c_{2}>0$ such that if $\min_{l}d_{l}\geq
c_{1}\frac{s^{L}L^{2}c_{s}^{2}}{\varepsilon^{2}}\log^{2}(sL/\delta\varepsilon)$
and $\varepsilon\leq c_{2}/s$, then for fixed
${\mathbf{x}},{\mathbf{x}}^{\prime}\in\mathcal{X}$,

$\displaystyle\left|\left\langle{\mathbf{h}}^{(l)}(\mathbf{y}),{\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})\right\rangle-{\Sigma}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\leq\varepsilon,$

holds with probability at least $1-\delta$ for all $l\in\\{0,1,\dots,L\\}$ and
all
$(\mathbf{y},\mathbf{y}^{\prime})\in\left\\{({\mathbf{x}},{\mathbf{x}}),({\mathbf{x}},{\mathbf{x}}^{\prime}),({\mathbf{x}}^{\prime},{\mathbf{x}}^{\prime})\right\\}$.
In other words, $\Pr(\bar{\mathcal{A}}(\varepsilon))\geq 1-\delta$, for fixed
${\mathbf{x}},{\mathbf{x}}^{\prime}$.

###### Proof.

The proof of this Lemma relies on following lemmas.

######  Lemma 5.

Let $\rho\in[-1,1]$ and $(X,Y)\sim\mathcal{N}(0,\Sigma_{\rho})$. If
$(X_{1},Y_{1}),(X_{2},Y_{2}),\dots,(X_{n},Y_{n})$ are independent samples from
$\mathcal{N}(0,\Sigma_{\rho})$ and
$S_{n}=\frac{1}{n}\sum_{i=1}^{n}\sigma_{s}(X_{i})\sigma_{s}(Y_{i})$ for some
$\sigma_{s}\in\mathcal{A}$, then for any $t\geq 0$,

$\displaystyle\Pr(S_{n}-\mu_{s}\geq t)$
$\displaystyle\leq\begin{cases}(n+1)\exp\left(-\dfrac{nt^{2}}{2\sqrt{3\mu_{4s,\rho}}}\right)&\text{
if }t\leq t^{*}(n),\\\
(n+1)\exp\left(-\dfrac{(nt)^{1/s}}{8(1+\rho)}\right)&\text{ if
}t>t^{*}(n).\end{cases}$ $\displaystyle\Pr(S_{n}-\mu_{s}\leq-t)$
$\displaystyle\leq\exp\left(-\frac{nt^{2}}{2\mu_{2s,\rho}}\right),$

where
$t^{*}(n)=\left(\dfrac{\sqrt{3\mu_{4s,\rho}}}{4(1+\rho)}\right)^{2-1/s}n^{-\left(\frac{s-1}{2s-1}\right)}$.
Consequently, if $n\geq n_{*}(s,\delta,\rho)$, then

$\displaystyle\Pr\left(|S_{n}-\mu_{s,\rho}|\geq\sqrt{\frac{2(\sqrt{3\mu_{4s,\rho}}+\mu_{2s,\rho})}{n}\log\left(\frac{n+1}{\delta}\right)}\right)\leq\delta,$

where $\displaystyle
n_{*}(s,\delta,\rho):=\min\left\\{m\in\mathbb{N}:m\geq\frac{(8(1+\rho))^{2s}}{2\sqrt{3\mu_{4s,\rho}}}\left[\log\left(\frac{m+1}{\delta}\right)\right]^{2s-1}\right\\}+1$

For simplicity of notation, we define
$\varphi_{s}(n,\delta,\rho):=\sqrt{\frac{2(\sqrt{3\mu_{4s,\rho}}+\mu_{2s,\rho})}{n}\log\left(\frac{n+1}{\delta}\right)}$.
Thus, the result of Lemma 5 can be restated as
$\Pr(|S_{n}-\mu_{s,\rho}|\geq\varphi_{s}(n,\delta,\rho))\leq\delta$.

######  Lemma 6.

For a given $s\in\mathbb{N}$, the dual activation function
$\breve{\sigma}_{s}$ is $\beta_{s}$-Lipschitz in
$\mathcal{M}_{+}^{\gamma_{s}}$ w.r.t. the $\infty$-norm for $\gamma_{s}\leq
1/s$ and $\beta_{s}\leq 6s$.

######  Lemma 7 (Daniely et al. [2016]).

For $\sigma(z)=\sigma_{s}(z)$ and
$[{\mathbf{W}}^{(l)}]_{ij}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,1)$ for
all $i\in[d_{l+1}],j\ \in[d_{l}]$ and $l\in\\{0,1,2,\dots,L\\}$. If
$\min_{l\in[L]}d_{l}\geq
n_{s}^{*}\left(\frac{\varepsilon}{B_{L,s}},\frac{\delta}{8\bar{d}}\right)$,
then for fixed ${\mathbf{x}},{\mathbf{x}}^{\prime}\in\mathcal{X}$,

$\displaystyle\left|\left\langle{\mathbf{h}}^{(l)}(\mathbf{y}),{\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})\right\rangle-{\Sigma}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\leq\varepsilon,$

holds with probability at least $1-\delta$ for all $l\in\\{0,1,\dots,L\\}$ and
all
$(\mathbf{y},\mathbf{y}^{\prime})\in\left\\{({\mathbf{x}},{\mathbf{x}}),({\mathbf{x}},{\mathbf{x}}^{\prime}),({\mathbf{x}}^{\prime},{\mathbf{x}}^{\prime})\right\\}$.
In the above expression, $B_{L,s}=\sum_{j=0}^{L-1}\beta_{s}^{i}$,
$\bar{d}=\sum_{l=1}^{L+1}d_{l}$ and
$n^{*}_{s}(\varepsilon,\delta)=\min\\{n:\varphi_{s}(n,\delta)\leq\varepsilon\\}$.

Lemma 4 follows immediately from Lemma 7 which in turn follows from the
previous lemmas. The proofs of Lemma 5 and 6 are provided in Appendix B.

∎

####  A.4.2 Pre-activation gradients are close to NTK derivative matrices

In the second step, we show that
$\left\langle{\mathbf{b}}^{(l)}(\mathbf{x}),{\mathbf{b}}^{(l)}(\mathbf{x}^{\prime})\right\rangle$
is close to
$\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{x}^{\prime})$. We
formalize this idea in the following lemma.

######  Lemma 8.

For $\sigma=\sigma_{s}$ and
$[{\mathbf{W}}^{(l)}]_{ij}\overset{\text{i.i.d.}}{\sim}\mathcal{N}(0,1)$ for
all $i\in[d_{l+1}],j\ \in[d_{l}]$ and $l\in\\{0,1,2,\dots,L\\}$. There exist
constants $c_{1},c_{2}>0$ such that if $\min_{l}d_{l}\geq
c_{1}\frac{s^{L}L^{2}c_{s}^{2}}{\varepsilon^{2}}\log^{2}(sL/\delta\varepsilon)$
and $\varepsilon\leq c_{2}s^{-L+2}/L$, then for fixed
${\mathbf{x}},{\mathbf{x}}^{\prime}\in\mathcal{X}$,

$\displaystyle\left|\left\langle{\mathbf{b}}^{(l)}(\mathbf{y}),{\mathbf{b}}^{(l)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|\leq
L(\beta_{s}+1)s^{L+1}\varepsilon,$

holds with probability at least $1-\delta$ for all $l\in\\{0,1,\dots,L\\}$ and
all
$(\mathbf{y},\mathbf{y}^{\prime})\in\left\\{({\mathbf{x}},{\mathbf{x}}),({\mathbf{x}},{\mathbf{x}}^{\prime}),({\mathbf{x}}^{\prime},{\mathbf{x}}^{\prime})\right\\}$.
In other words, if $\min_{l}d_{l}\geq
c_{1}\frac{s^{L}L^{2}c_{s}^{2}}{\varepsilon_{1}^{2}}\log^{2}(sL/\delta\varepsilon_{1})$
and $\varepsilon_{1}\leq c_{2}s^{-L+2}/L$, then for fixed
${\mathbf{x}},{\mathbf{x}}^{\prime}$,
$\Pr\left(\bar{\mathcal{A}}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}(L(\beta_{s}+1)s^{L+1}\varepsilon_{1})\right)\geq
1-\delta$.

###### Proof.

We first state some helper lemmas that will be used in the proof followed by
the proof of the above lemma.

######  Lemma 9 (Arora et al. [2019], Lemma E.4).

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{L}(\varepsilon/2)\Rightarrow\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{4}{\delta}\right)}\right)\right]\geq
1-\delta\ \ \quad\forall\ \varepsilon\in[0,1],\ \ \forall\ \delta\in(0,1).$

######  Lemma 10.

If
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$
for any pair of points $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, then
for any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$,
we have

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L}{\dot{\Sigma}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\leq
s^{L-l}\varepsilon_{4}+s\varepsilon_{2}.$

######  Lemma 11.

If
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$
for any pair of points $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, then
for any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$

$\displaystyle\left|\frac{c_{s}}{d_{l}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})-\frac{c_{s}}{d_{l}}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right|$
$\displaystyle\leq
c_{s}\left(\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\rangle+\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right)\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{3}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{3}{\delta}\right)\right)\varepsilon_{5}$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \
+\frac{2c_{s}}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\varepsilon_{5}.$

holds with probability at least $1-\delta$. Consequently, for any
$\mathbf{y}\in\\{\mathbf{x},\mathbf{x}^{\prime}\\}$,

$\displaystyle\sqrt{\frac{c_{s}}{d_{l}}}\left\|\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y})\right\|$
$\displaystyle\leq\sqrt{2c_{s}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\rangle\varepsilon_{5}}.$

######  Lemma 12.

If
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$
for any pair of points $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, then
for any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$

$\displaystyle\frac{c_{s}}{d_{l}}\bigg{|}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
-\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\bigg{|}\leq$
$\displaystyle\frac{c_{s}\varepsilon_{5}}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+\varepsilon_{2})\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\times$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\left\\{\frac{1}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]+\sqrt{8}(s^{(L-l)/2}+1)\right\\}$

holds with probability at least $1-\delta$.

######  Lemma 13.

For any $\varepsilon_{1}\in[0,1/s]$, $\varepsilon_{2},\varepsilon_{4}\in[0,1]$
and $\varepsilon_{3},\varepsilon_{5}\geq 0$,

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})\Rightarrow\bar{\mathcal{B}}^{l}(\varepsilon^{\prime})\right]\geq
1-\delta,$

where

$\displaystyle\varepsilon^{\prime}=2c_{s}(s^{L-l}+1)\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{6}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{6}{\delta}\right)\right)\varepsilon_{5}+\frac{2c_{s}}{d_{l}}(s^{L-l}+1)\varepsilon_{5}+s^{L-l}\varepsilon_{4}+s\varepsilon_{2}$
$\displaystyle+\frac{c_{s}\varepsilon_{5}}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\times$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \
\left\\{\frac{1}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]+\sqrt{8}(s^{(L-l)/2}+1)\right\\}.$

We now prove Lemma 8 by using induction on Lemma 13. Before the inductive
step, we note some relations that will be useful to us during the analysis.
Firstly, using Lemma 4, we can conclude that if $d_{l}\geq
n_{s}^{*}(\varepsilon/B_{L,s},\delta/32\bar{d}(L+1))$ and $\varepsilon\leq
c_{2}/s$, then

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{L}(\varepsilon/2)\right]\geq
1-\delta/4.$ (22)

From Lemma 9, we can conclude that

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{L}(\varepsilon/2)\Rightarrow\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\right]\geq
1-\delta/4.$ (23)

If $d_{l}\geq n_{s}^{*}(\varepsilon/3,\delta/24(L+1))$, then we can conclude
that
$3s^{2}\varphi_{s-1}((\min_{l}d_{l}),\delta/24(L+1))+\frac{s^{2}\beta_{s}\varepsilon}{2s-1}\leq(\beta+1)s^{2}\varepsilon$.
Consequently for $\varepsilon\leq 2/s$,

$\displaystyle\Pr\left[\bar{\mathcal{A}}(\varepsilon/2)\Rightarrow\bar{\mathcal{D}}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}\left(\varepsilon^{\prime\prime}\right)\right]\geq
1-\delta/4,$ (24)

where
$\displaystyle\varepsilon^{\prime\prime}=3s^{2}\left[2\log\left(\frac{6(L+1)(\max_{l}d_{l})}{\delta}\right)\right]^{s-1}$.
Applying the union bound on (22), (23) and (24), we obtain that

$\displaystyle\Pr\left[\bar{\mathcal{A}}(\varepsilon/2)\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}\left(\varepsilon^{\prime\prime}\right)\right]\geq
1-3\delta/4.$ (25)

Let $d_{l}$ be chosen large enough to ensure that

$\displaystyle s^{L-l+2}\varepsilon$ $\displaystyle\geq
2c_{s}(s^{L-l}+1)\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{24(L+1)}{\delta}\right)}+\frac{1}{d_{l}}\left(+\log\left(\frac{24(L+1)}{\delta}\right)\right)\right)\varepsilon^{\prime\prime}$
$\displaystyle+c_{s}\varepsilon^{\prime\prime}\sqrt{\frac{8}{d_{l}}}(s^{(L-l)/2}+1)\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{64(L+1)}{\delta}\right)}+4s^{L-l}\sqrt{\log\left(\frac{16(L+1)}{\delta}\right)}\right]$
$\displaystyle+\frac{c_{s}\varepsilon^{\prime\prime}}{d_{l}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{64(L+1)}{\delta}\right)}+4s^{L-l}\sqrt{\log\left(\frac{16(L+1)}{\delta}\right)}\right]^{2}.$

Define $\upsilon_{l}:=(L+1-l)(\beta_{s}+1)s^{L-l+2}\varepsilon$ for
$l=0,1,\dots,L+1$. Invoking Lemma 13 with $\varepsilon_{1}=\varepsilon$,
$\varepsilon_{2}=\upsilon_{l+1}$,
$\varepsilon_{3}=2\sqrt{\log\left(\frac{16}{\delta}\right)}$,
$\varepsilon_{4}=(\beta_{s}+1)s^{2}\varepsilon$ and
$\varepsilon_{5}=\varepsilon^{\prime\prime}$ gives us that

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{L}(\varepsilon/2)\land\bar{\mathcal{B}}^{l+1}(\upsilon_{l+1})\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}^{l}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}^{l}(\varepsilon^{\prime\prime})\Rightarrow\bar{\mathcal{B}}^{l}(\upsilon_{l})\right]\geq
1-\frac{\delta}{4(L+1)}.$

Thus,

$\displaystyle\Pr\left[\bar{\mathcal{A}}(\varepsilon/2)\land\bar{\mathcal{B}}(\upsilon_{1})\right]$
$\displaystyle\geq\Pr\left[\underbrace{\bar{\mathcal{A}}(\varepsilon/2)\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}(\varepsilon^{\prime\prime})}_{:=\mathcal{F}(\varepsilon)}\land\left(\bigcap_{l=1}^{L+1}\bar{\mathcal{B}}^{l}(\upsilon_{l})\right)\right]$
$\displaystyle\geq\Pr\left[\mathcal{F}(\varepsilon)\land\bar{\mathcal{B}}^{L+1}(\upsilon_{L+1})\land\bigcap_{l=0}^{L}\left\\{\mathcal{F}(\varepsilon)\land\left(\bigcap_{j=L+1-l}^{L+1}\bar{\mathcal{B}}^{j+1}(\upsilon_{j+1})\right)\Rightarrow\bar{\mathcal{B}}^{L-l}(\upsilon_{L-l})\right\\}\right]$
$\displaystyle\geq\Pr\Bigg{[}\mathcal{F}(\varepsilon)\land\bar{\mathcal{B}}^{L+1}(\upsilon_{L+1})\land$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\bigcap_{l=0}^{L}\left\\{\bar{\mathcal{A}}^{L}(\varepsilon/2)\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}^{l}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}^{l}(\varepsilon^{\prime\prime})\land\bar{\mathcal{B}}^{l+1}(\upsilon_{l+1})\Rightarrow\bar{\mathcal{B}}^{l}(\upsilon_{l})\right\\}\Bigg{]}$
$\displaystyle\geq
1-\Pr\left[\neg\left\\{\bar{\mathcal{A}}(\varepsilon/2)\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}(\varepsilon^{\prime\prime})\right\\}\right]-\Pr\left[\neg\bar{\mathcal{B}}^{L+1}(\upsilon_{L+1})\right]$
$\displaystyle\ \ \ \ \ \
-\sum_{l=0}^{L}\Pr\left[\neg\left\\{\bar{\mathcal{A}}^{L}(\varepsilon/2)\land\bar{\mathcal{C}}\left(2\sqrt{\log\left(\frac{16}{\delta}\right)}\right)\land\bar{\mathcal{D}}^{h}((\beta_{s}+1)s^{2}\varepsilon)\land\bar{\mathcal{E}}^{l}(\varepsilon^{\prime\prime})\land\bar{\mathcal{B}}^{l+1}(\upsilon_{l+1})\Rightarrow\bar{\mathcal{B}}^{l}(\upsilon_{l})\right\\}\right]$
$\displaystyle\geq 1-\frac{3\delta}{4}-\sum_{l=0}^{L}\frac{\delta}{4(L+1)}$
$\displaystyle\geq 1-\delta.$

Thus,
$\Pr\left[\bar{\mathcal{A}}(\varepsilon/2)\land\bar{\mathcal{B}}(L(\beta_{s}+1)s^{L+1}\varepsilon)\right]\geq
1-\delta$, as required. The proof of the helper lemmas are provided in
Appendix B.

∎

Now, it is straightforward to note that Lemma 1 immediately follows from the
Lemma 4 and Lemma 8. With Lemma 1 in place, the rest of the proof of Theorem 1
follows similar to the proof of Theorem 3.2 in Arora et al. [2019]. The only
step in the proof of Theorem 3.2 that is dependent on kernel being ReLU, is
Lemma F.6, where they bound the perturbation in gradient based on the amount
of perturbation in the weight matrices. We would like to emphasize that this
is only step apart from the ones which use Theorem 3.1. Such steps follow
immediately by invoking Lemma 1 proven above, instead of Theorem 3.1. Using
the result from Liu et al. [2020, Theorem 3.2], we know that the spectral norm
of the Hessian of the neural net is $\mathcal{O}(m^{-1/2})$. Here the implied
constant only depends on $s$ and $L$. Thus for the a perturbation in the
weight matrices of the order of $\mathcal{O}(\sqrt{m}\omega)$, the
corresponding perturbation in the gradient is $\mathcal{O}(\omega)$, with the
implied constant depending only on $s$ and $L$. On substituting this relation
in place of Lemma F.6, the claim of Theorem 1 follows using the same arguments
as the ones used in the proof of Theorem 3.2 of Arora et al. [2019].

##  Appendix B Proof of Helper Lemmas

We first state some additional intermediate lemmas which are used in the
proofs several helper lemmas then provide a proof of all the lemmas.

######  Definition 4.

$\displaystyle{\mathbf{G}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})=[{\mathbf{h}}^{(l)}(\mathbf{x})\
\ {\mathbf{h}}^{(l)}(\mathbf{x}^{\prime})]\in\mathbb{R}^{d_{l}\times 2}$
$\displaystyle{\tilde{\mathbf{G}}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})=[{\mathbf{G}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})]^{\top}{\mathbf{G}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})=\begin{bmatrix}\left\langle{\mathbf{h}}^{(l)}(\mathbf{x}),{\mathbf{h}}^{(l)}(\mathbf{x})\right\rangle&\left\langle{\mathbf{h}}^{(l)}(\mathbf{x}),{\mathbf{h}}^{(l)}(\mathbf{x}^{\prime})\right\rangle\\\
\left\langle{\mathbf{h}}^{(l)}(\mathbf{x}^{\prime}),{\mathbf{h}}^{(l)}(\mathbf{x})\right\rangle&\left\langle{\mathbf{h}}^{(l)}(\mathbf{x}^{\prime}),{\mathbf{h}}^{(l)}(\mathbf{x}^{\prime})\right\rangle\\\
\end{bmatrix}\equiv\begin{bmatrix}G_{11}&G_{12}\\\ G_{12}&G_{22}\\\
\end{bmatrix}$

######  Lemma 14.

$\displaystyle\Pr\left[\bar{\mathcal{A}}^{l}(\varepsilon)\Rightarrow\bar{\mathcal{D}}^{l+1}\left(3s^{2}\varphi_{s-1}(d_{l},\delta/6,1)+\frac{2s^{2}\beta_{s}\varepsilon}{2s-1}\right)\land\bar{\mathcal{E}}^{l+1}\left(3s^{2}\left[2\log\left(\frac{6d_{l}}{\delta}\right)\right]^{s-1}\right)\right]\geq
1-\delta$ $\displaystyle\quad\forall\ \varepsilon\in[0,1/s],\ \delta\in(0,1).$

######  Lemma 15.

Let

$\displaystyle\varepsilon^{\prime}=3s^{2}\varphi_{s-1}((\min_{l}d_{l}),\delta/6(L+1),1)+\frac{2s^{2}\beta_{s}\varepsilon}{2s-1},\quad\varepsilon^{\prime\prime}=3s^{2}\left[2\log\left(\frac{6(L+1)(\max_{l}d_{l})}{\delta}\right)\right]^{s-1}.$

Then,

$\displaystyle\Pr\left[\bar{\mathcal{A}}(\varepsilon)\Rightarrow\bar{\mathcal{D}}(\varepsilon^{\prime})\land\bar{\mathcal{E}}(\varepsilon^{\prime\prime})\right]\geq
1-\delta\quad\forall\ \varepsilon\in[0,1/s],\ \delta\in(0,1).$

######  Lemma 16.

For any $1\leq l\leq L$, any fixed $\\{{\mathbf{W}}^{(i)}\\}_{i=1}^{l-1}$ and
$\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, with probability $1-\delta$
over the randomness of ${\mathbf{W}}^{(l)}$, we have,

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime}))}{d_{l}}-\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\tilde{\mathbf{G}}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right)\right|\leq
s^{2}(G_{11}G_{22})^{\frac{(s-1)}{2}}\varphi_{s-1}(d_{l},\delta/2,\rho_{G}),$

and

$\displaystyle\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\|_{2}$
$\displaystyle\leq
s^{2}\left[\left(\sqrt{G_{11}G_{22}}+G_{12}\right)\log\left(\frac{2d_{l}}{\delta}\right)\right]^{s-1},$

where $\rho_{G}=\frac{G_{12}}{\sqrt{G_{11}G_{22}}}$.

######  Lemma 17 (Boucheron et al. [2013]).

Let $\boldsymbol{\xi}\sim\mathcal{N}(0,\mathbf{I}_{n})$ be an $n$-dimensional
unit Gaussian random vector and $\mathbf{A}\in\mathbb{R}^{n\times n}$ be a
symmetric matrix, then for any $t>0$,

$\displaystyle\Pr\left(\left|\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}-\mathbb{E}\left[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}\right]\right|>2\|\mathbf{A}\|_{F}\sqrt{t}+2\|\mathbf{A}\|_{2}t\right)\leq\exp(-t),$

or equivalently,

$\displaystyle\Pr\left(\left|\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}-\mathbb{E}\left[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}\right]\right|>t\right)\leq\exp\left(-\frac{t^{2}}{4\|\mathbf{A}\|_{F}^{2}+4\|\mathbf{A}\|_{2}}\right).$

######  Lemma 18.

If
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$
for any pair of points $\mathbf{x},\mathbf{x}^{\prime}\in\mathcal{X}$, then
for any $\mathbf{y}\in\\{\mathbf{x},\mathbf{x}^{\prime}\\}$

$\displaystyle\left\|\boldsymbol{\Pi}_{\mathbf{G}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\|$
$\displaystyle\leq(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{4}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}.$

holds with probability at least $1-\delta$.

###  B.1 Proof of Lemma 5

We fix a particular $s\in\mathbb{N}$. Let
$(X_{1},Y_{1}),(X_{2},Y_{2}),\dots,(X_{n},Y_{n})$ be $n$ independent samples
from $\mathcal{N}(0,\Sigma_{\rho})$ and let
$Z_{i}=\sigma_{s}(X_{i})\sigma_{s}(Y_{i})$. Define
$S_{n}:=\frac{1}{n}\sum_{i=1}^{n}Z_{i}$. Note that
$\mathbb{E}[S_{n}]=\mathbb{E}[Z_{1}]=\mu_{s}$. To prove the bound, we first
bound $\Pr(Z_{i}>t)$ for any $t\geq 0$ and then using techniques borrowed from
Gantert et al. [2014], we obtain an upper bound on $\Pr(S_{n}-\mu_{s}>t)$. The
bound on $\Pr(S_{n}-\mu_{s}<-t)$ follows from Cramer’s Theorem [Cramér, 1938].

We begin with bounding $\Pr(Z_{i}>t)$ for any $t\geq 0$. Since
$Z_{i}=(\sigma_{1}(X_{i})\sigma_{1}(Y_{i}))^{s}$, we just focus on bounding
$\Pr(\sigma_{1}(X)\sigma_{1}(Y)>t)$ for
$(X,Y)\sim\mathcal{N}(0,\Sigma_{\rho})$. Fix a $t\geq 0$. We have,

$\displaystyle\Pr(\sigma_{1}(X)\sigma_{1}(Y)>t)$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}\left\\{\sigma_{1}(X)\sigma_{1}(Y)>t\right\\}\right]$
$\displaystyle=\mathbb{E}\left[\mathbbm{1}\left\\{XY>t,X\geq 0,Y\geq
0\right\\}\right].$

Using a change of variables define $U=(X+Y)/\sqrt{2}$ and $V=(X-Y)/\sqrt{2}$.
Note that $U$ and $V$ are zero-mean Gaussian random variables with
$\text{Cov}(U,V)=0$ implying that they are independent. Also
$\text{Var}(U)=1+\rho$ and $\text{Var}(V)=1-\rho$. Thus,

$\displaystyle\Pr(\sigma_{1}(X)\sigma_{1}(Y)>t)$
$\displaystyle=\mathbb{E}_{X,Y}\left[\mathbbm{1}\left\\{XY>t,X\geq 0,Y\geq
0\right\\}\right]$
$\displaystyle=\mathbb{E}_{U,V}\left[\mathbbm{1}\left\\{U^{2}-V^{2}>2t,U\geq
0,V\in[-U,U]\right\\}\right]$
$\displaystyle\leq\mathbb{E}_{U,V}\left[\mathbbm{1}\left\\{U^{2}>V^{2}+2t,U\geq
0\right\\}\right]$
$\displaystyle\leq\mathbb{E}_{V}\left[\Pr\left(U>\sqrt{V^{2}+2t}\right)\right]$
$\displaystyle\leq\mathbb{E}_{V}\left[\exp\left(-\frac{V^{2}+2t}{2(1+\rho)}\right)\right]$
$\displaystyle\leq\frac{1}{\sqrt{2\pi(1-\rho)}}\int_{-\infty}^{\infty}\exp\left(-\frac{v^{2}+2t}{2(1+\rho)}\right)\exp\left(-\frac{v^{2}}{2(1-\rho)}\right)\
\mathrm{d}v$
$\displaystyle\leq\frac{e^{-t/(1+\rho)}}{\sqrt{2\pi(1-\rho)}}\int_{-\infty}^{\infty}\exp\left(-\frac{v^{2}}{(1-\rho^{2})}\right)\
\mathrm{d}v$
$\displaystyle\leq\exp\left(-\frac{t}{1+\rho}\right)\sqrt{\frac{1+\rho}{2}}$
$\displaystyle\leq\exp\left(-\frac{t}{1+\rho}\right).$

In the sixth line we used the concentration bound for Gaussian random variable
and in the eighth line we used the Gaussian integral. Consequently,

$\displaystyle\Pr(Z_{i}>t)=\Pr(\sigma_{1}(X)\sigma_{1}(Y)>t^{1/s})\leq\exp\left(-\frac{t^{1/s}}{1+\rho}\right).$
(26)

Using this relation, we now move on to bound $\Pr(S_{n}\geq x)$ for
$x\geq\mu_{s,\rho}$. For the rest of the proof we drop the argument $\rho$ for
simplicity. Firstly, note that

$\displaystyle\Pr(S_{n}\geq x)\leq\underbrace{\Pr\left(\max_{j\in[n]}Z_{j}\geq
n(x-\mu_{s})\right)}_{A_{1}^{n}}+\underbrace{\Pr\left(S_{n}\geq x,\
\max_{j\in[n]}Z_{j}<n(x-\mu_{s})\right)}_{A_{2}^{n}}.$

We begin with the first term.

$\displaystyle\Pr\left(\max_{j\in[n]}Z_{j}\geq n(x-\mu_{s})\right)\leq
n\Pr(Z_{i}\geq n(x-\mu_{s}))\leq
n\exp\left(-\frac{n^{1/s}(x-\mu_{s})^{1/s}}{1+\rho}\right).$

Let $\beta_{\zeta}(n)=\frac{\zeta n^{1/s}}{1+\rho}>0$ for some $\zeta>0$ which
will be specified later. We have,

$\displaystyle A_{2}^{n}$ $\displaystyle=\Pr\left(S_{n}\geq x,\
\max_{j\in[n]}Z_{j}<n(x-\mu_{s})\right)$
$\displaystyle=\Pr\left(\exp\left(\beta_{\zeta}(n)S_{n}\right)\geq\exp\left(\beta_{\zeta}(n)x\right),\
\max_{j\in[n]}Z_{j}<n(x-\mu_{s})\right)$
$\displaystyle\leq\exp\left(-\beta_{\zeta}(n)x\right)\mathbb{E}\left[\exp\left(\beta_{\zeta}(n)S_{n}\right)\mathbbm{1}\left\\{\max_{j\in[n]}Z_{j}<n(x-\mu_{s})\right\\}\right]$
$\displaystyle\leq\exp\left(-\beta_{\zeta}(n)x\right)\prod_{j=1}^{n}\mathbb{E}\left[\exp\left(\frac{\beta_{\zeta}(n)Z_{j}}{n}\right)\mathbbm{1}\left\\{Z_{j}<n(x-\mu_{s})\right\\}\right]$
$\displaystyle\implies\log\left(A_{2}^{n}\right)$
$\displaystyle\leq-\beta_{\zeta}(n)x+\sum_{j=1}^{n}{\Gamma_{\zeta}}^{(j)}(n),$

where
${\Gamma_{\zeta}}^{(j)}(n)=\log\left(\mathbb{E}\left[\exp\left(\dfrac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)\right]\right)$
and ${Z_{j}}^{(n)}:=Z_{j}\mathbbm{1}\left\\{Z_{j}<n(x-\mu_{s})\right\\}$.
Using the relations $\log(1+x)\leq x$ and $e^{x}\leq
1+x+\frac{x^{2}}{2}e^{x}$, we have,

$\displaystyle\sum_{j=1}^{n}{\Gamma_{\zeta}}^{(j)}(n)$
$\displaystyle=\sum_{j=1}^{n}\log\left(\mathbb{E}\left[\exp\left(\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)\right]\right)$
$\displaystyle\leq\sum_{j=1}^{n}\log\left(1+\mathbb{E}\left[\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right]+\frac{1}{2}\mathbb{E}\left[\left(\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)^{2}\exp\left(\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)\right]\right)$
$\displaystyle\leq\sum_{j=1}^{n}\left\\{\mathbb{E}\left[\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right]+\frac{1}{2}\mathbb{E}\left[\left(\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)^{2}\exp\left(\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right)\right]\right\\}.$

Note that,

$\displaystyle\sum_{j=1}^{n}\mathbb{E}\left[\frac{\beta_{\zeta}(n){Z_{j}}^{(n)}}{n}\right]$
$\displaystyle=\sum_{j=1}^{n}\frac{\beta_{\zeta}(n)}{n}\mathbb{E}\left[{Z_{j}}^{(n)}\right]$
$\displaystyle\leq\beta_{\zeta}(n)\mu_{s}.$

For the second term we have,

$\displaystyle\mathbb{E}\left[\left(\frac{\beta_{\zeta}(n){Z_{1}}^{(n)}}{n}\right)^{2}\exp\left(\frac{\beta_{\zeta}(n){Z_{1}}^{(n)}}{n}\right)\right]$
$\displaystyle\leq\left(\frac{\beta_{\zeta}(n)}{n}\right)^{2}\mathbb{E}\left[\left({Z_{1}}^{(n)}\right)^{\frac{2(1+\eta)}{\eta}}\right]^{\frac{\eta}{1+\eta}}\mathbb{E}\left[\exp\left(\frac{(1+\eta)\beta_{\zeta}(n){Z_{1}}^{(n)}}{n}\right)\right]^{\frac{1}{1+\eta}}$

for some $\eta>0$ by using Hölder’s inequality. Since
$\mathbb{E}\left[\left({Z_{1}}^{(n)}\right)^{2(1+\eta)/\eta}\right]^{\eta/(1+\eta)}=\left[\mu_{\frac{2s(1+\eta)}{\eta}}\right]^{\frac{\eta}{1+\eta}}$,
we focus on the other term. We have,

$\displaystyle\mathbb{E}\left[\exp\left(\frac{(1+\eta)\beta_{\zeta}(n){Z_{1}}^{(n)}}{n}\right)\right]$
$\displaystyle=1+\int_{0}^{n(x-\mu_{s})}\frac{(1+\eta)\beta_{\zeta}(n)}{n}\exp\left(\frac{(1+\eta)\beta_{\zeta}(n)z}{n}\right)\Pr(Z_{1}>z)\
\mathrm{d}z$
$\displaystyle=1+n(x-\mu_{s})\int_{0}^{1}\frac{(1+\eta)\beta_{\zeta}(n)}{n}\exp\left(\frac{(1+\eta)\beta_{\zeta}(n)n(x-\mu_{s})y}{n}\right)\Pr(Z_{1}>n(x-\mu_{s})y)\
\mathrm{d}y$ $\displaystyle\leq
1+(x-\mu_{s})\int_{0}^{1}(1+\eta)\beta_{\zeta}(n)\exp\left((1+\eta)\beta_{\zeta}(n)(x-\mu_{s})y-\frac{(n(x-\mu_{s})y)^{1/s}}{1+\rho}\right)\
\mathrm{d}y$ $\displaystyle\leq
1+(x-\mu_{s})(1+\eta)\beta_{\zeta}(n)\int_{0}^{1}\exp\left(\beta_{\zeta}(n)\left[(1+\eta)(x-\mu_{s})y-\frac{(x-\mu_{s})^{1/s}y^{1/s}}{\zeta}\right]\right)\
\mathrm{d}y.$

For $\zeta\leq\dfrac{(x-\mu_{s})^{1/s-1}}{2(1+\eta)}$, we have,

$\displaystyle\mathbb{E}\left[\exp\left(\frac{(1+\eta)\beta_{\zeta}(n){Z_{1}}^{(n)}}{n}\right)\right]$
$\displaystyle\leq
1+(x-\mu_{s})(1+\eta)\beta_{\zeta}(n)\int_{0}^{1}\exp\left(\beta_{\zeta}(n)\left[(1+\eta)(x-\mu_{s})y-\frac{(x-\mu_{s})^{1/s}y^{1/s}}{\zeta}\right]\right)\
\mathrm{d}y$ $\displaystyle\leq
1+(x-\mu_{s})(1+\eta)\beta_{\zeta}(n)\int_{0}^{1}\exp\left(-\frac{1}{2}\beta_{\zeta}(n)(1+\eta)(x-\mu_{s})y\right)\
\mathrm{d}y$ $\displaystyle\leq 3.$

On combining all the equations, we obtain that for
$\zeta\leq\frac{(x-\mu_{s})^{1/s-1}}{2(1+\eta)}$ and $\eta>0$

$\displaystyle\log\left(A_{2}^{n}\right)$
$\displaystyle\leq-\beta_{\zeta}(n)(x-\mu_{s})+\frac{(\beta_{\zeta}(n))^{2}}{2n}\left(\left[\mu_{\frac{2s(1+\eta)}{\eta}}\right]^{\frac{\eta}{1+\eta}}3^{\frac{1}{1+\eta}}\right)$

We set $\eta=1$. Thus for $\zeta\leq 0.25{(x-\mu_{s})^{1/s-1}}$, we have,

$\displaystyle\log\left(A_{2}^{n}\right)$ $\displaystyle\leq-\frac{\zeta
n^{1/s}(x-\mu_{s})}{1+\rho}+\frac{\zeta^{2}n^{2/s-1}}{2(1+\rho)^{2}}\sqrt{3\mu_{4s}}.$

Note that the RHS is minimized at
$\zeta_{*}=\dfrac{n^{1-1/s}(x-\mu_{s})(1+\rho)}{\sqrt{3\mu_{4s}}}$. However,
$\zeta_{*}\leq 0.25{(x-\mu_{s})^{1/s-1}}$ only for
$\displaystyle(x-\mu_{s})\leq\underbrace{\left(\frac{\sqrt{3\mu_{4s}}}{4(1+\rho)}\right)^{2-1/s}n^{-\left(\frac{s-1}{2s-1}\right)}}_{:=t^{*}(n)}$.
Thus, for $(x-\mu_{s})\leq t^{*}(n)$, we can plug in $\zeta=\zeta_{*}$ in the
above expression to obtain

$\displaystyle\log\left(A_{2}^{n}\right)$
$\displaystyle\leq-\frac{n(x-\mu_{s})^{2}}{2\sqrt{3\mu_{4s}}}.$

For $(x-\mu_{s})>t^{*}(n)$, we plug in $\zeta=0.25{(x-\mu_{s})^{1/s-1}}$ to
obtain

$\displaystyle\log\left(A_{2}^{n}\right)$
$\displaystyle\leq-\frac{n^{1/s}(x-\mu_{s})^{1/s}}{8(1+\rho)}.$

On combining the two, we obtain that for any $t\geq 0$

$\displaystyle\Pr(S_{n}-\mu_{s}\geq
t)=\begin{cases}(n+1)\exp\left(-\dfrac{nt^{2}}{2\sqrt{3\mu_{4s}}}\right)&\text{
if }t\leq t^{*}(n),\\\
(n+1)\exp\left(-\dfrac{(nt)^{1/s}}{8(1+\rho)}\right)&\text{ if
}t>t^{*}(n).\end{cases}$

We now consider the other side. Consider any $x\leq\mu_{s}$ and $\lambda>0$.
We have,

$\displaystyle\Pr(S_{n}\leq x)$ $\displaystyle=\Pr\left(\exp(-\lambda
S_{n})\geq e^{-\lambda x}\right)$
$\displaystyle\leq\mathbb{E}\left[\exp(-\lambda S_{n})\right]e^{\lambda x}$
$\displaystyle\leq\mathbb{E}\left[1-\lambda
S_{n}+\frac{\lambda^{2}S_{n}^{2}}{2}\right]e^{\lambda x}$
$\displaystyle\leq\left(1-\lambda\mathbb{E}[S_{n}]+\frac{\lambda^{2}\mathbb{E}[S_{n}^{2}]}{2}\right)e^{\lambda
x}$
$\displaystyle\leq\left(1-\lambda\mu_{s}+\frac{\lambda^{2}\mu_{2s}}{2n}\right)e^{\lambda
x}$
$\displaystyle\leq\exp\left(-\lambda\mu_{s}+\frac{\lambda^{2}\mu_{2s}}{2n}+\lambda
x\right)$
$\displaystyle\leq\exp\left(\lambda(x-\mu_{s})+\frac{\lambda^{2}\mu_{2s}}{2n}+\lambda
x\right).$

Minimizing this over $\lambda$ yields
$\lambda_{*}=-\dfrac{n(x-\mu_{s})}{\mu_{2s}}>0$. On plugging this value, we
obtain,

$\displaystyle\Pr(S_{n}\leq x)$
$\displaystyle\leq\exp\left(-\frac{n(x-\mu_{s})^{2}}{2\mu_{2s}}\right).$

Consequently for any $t\geq 0$, we have,

$\displaystyle\Pr(S_{n}-\mu_{s}\leq-t)$
$\displaystyle\leq\exp\left(-\frac{nt^{2}}{2\mu_{2s}}\right).$

On combining the relations, we can conclude that if $n\geq
n_{*}(s,\delta,\rho)$, then

$\displaystyle\Pr\left(|S_{n}-\mu_{s}|\geq\sqrt{\frac{2(\sqrt{3\mu_{4s}}+\mu_{2s})}{n}\log\left(\frac{n+1}{\delta}\right)}\right)\leq\delta.$

###  B.2 Proof of Lemma 6

Fix a $s\in\mathbb{N}$. We drop the subscript $s$ for the remainder of the
proof for ease of notation. We need to show that the dual activation function
$\breve{\sigma}$ is $\beta$-Lipschitz in $\mathcal{M}_{+}^{\gamma}$ w.r.t. the
$\infty$-norm. Let $\Sigma=\begin{pmatrix}\Sigma_{11}&\Sigma_{12}\\\
\Sigma_{12}&\Sigma_{22}\\\ \end{pmatrix}\in\mathcal{M}_{+}^{\gamma}$. In order
to prove $\beta$-Lipschitzness w.r.t. the $\infty$-norm, it is sufficient to
show that,

$\displaystyle\|\nabla\breve{\sigma}_{s}\|_{1}=\left|\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{12}}\right|+\left|\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{11}}\right|+\left|\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{22}}\right|\leq\beta.$

Recall that since $\sigma_{s}$ is $s$-homogeneous,

$\displaystyle\breve{\sigma}_{s}(\Sigma)=(\Sigma_{11}\Sigma_{22})^{s/2}\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right).$

Using this relation, we have,

$\displaystyle\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{12}}$
$\displaystyle=(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)$
$\displaystyle\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{11}}$
$\displaystyle=\frac{s}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}\Sigma_{22}\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)-\frac{1}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\frac{\Sigma_{12}}{\Sigma_{11}}$
$\displaystyle=\Sigma_{22}\left\\{\frac{s}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)-\frac{1}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\frac{\Sigma_{12}}{\Sigma_{11}\Sigma_{22}}\right\\}$
$\displaystyle\frac{\partial\breve{\sigma}_{s}}{\partial\Sigma_{22}}$
$\displaystyle=\frac{s}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}\Sigma_{11}\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)-\frac{1}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\frac{\Sigma_{12}}{\Sigma_{22}}$
$\displaystyle=\Sigma_{11}\left\\{\frac{s}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)-\frac{1}{2}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\frac{\Sigma_{12}}{\Sigma_{11}\Sigma_{22}}\right\\}.$

Consequently,

$\displaystyle\|\nabla\breve{\sigma}_{s}\|_{1}$
$\displaystyle=(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\left|\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\right|+$
$\displaystyle\quad\quad\frac{(\Sigma_{11}+\Sigma_{22})(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}}{2}\left|s\bar{\sigma}_{s}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)-\bar{\sigma}_{s}^{\prime}\left(\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right)\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}\right|.$

For simplicity, let
$\tilde{\rho}=\frac{\Sigma_{12}}{\sqrt{\Sigma_{11}\Sigma_{22}}}$. For $s=1$,
Arora et al. [2019] showed that the above expression is $1+o(\gamma)$. We
consider the case for $s>1$. Using (20), we have,

$\displaystyle\|\nabla\breve{\sigma}_{s}\|_{1}$
$\displaystyle=\frac{s^{2}}{2s-1}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}\left|\bar{\sigma}_{s-1}\left(\tilde{\rho}\right)\right|+\frac{(\Sigma_{11}+\Sigma_{22})(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}}{2}\left|s\bar{\sigma}_{s}\left(\tilde{\rho}\right)-\frac{s^{2}}{2s-1}\bar{\sigma}_{s-1}\left(\tilde{\rho}\right)\tilde{\rho}\right|$
$\displaystyle\leq\frac{2s}{3}(\Sigma_{11}\Sigma_{22})^{\frac{s-1}{2}}+\frac{3s}{4}(\Sigma_{11}+\Sigma_{22})(\Sigma_{11}\Sigma_{22})^{\frac{s}{2}-1}$
$\displaystyle\leq\frac{13s}{6}(1+\gamma)^{s-1}$

If $\gamma\leq 1/s$, then $\|\nabla\breve{\sigma}_{s}\|_{1}\leq 6s$, as
required.

###  B.3 Proof of Lemma 10

We have,

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}-{\dot{\Sigma}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\left|\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right|+$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left|{\dot{\Sigma}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\left|\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l+1}^{L}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\left|\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right|\varepsilon_{4}+\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\Lambda}^{(l)}(\mathbf{x},\mathbf{x}^{\prime})\right)\varepsilon_{2}$

Since $\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})$,
$\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\leq\prod_{j=l+1}^{L}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})+\varepsilon_{2}\leq\prod_{j=l+1}^{L}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})+1$.
Moreover, since
${\dot{\Sigma}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})=\frac{s^{2}}{2s-1}\breve{\sigma}_{s-1}\left({\Lambda}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right)\leq\frac{s^{2}}{2s-1}$,
we have,

$\displaystyle\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l+1}^{L}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\left(\left(\frac{s^{2}}{2s-1}\right)^{L-l}+1\right)\varepsilon_{4}+s\varepsilon_{2}$
$\displaystyle\leq s^{L-l}\varepsilon_{4}+s\varepsilon_{2}.$

###  B.4 Proof of Lemma 11

Fix any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$.
Recall that
${\mathbf{G}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})=[{\mathbf{h}}^{(l)}(\mathbf{y})\
\ {\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})]\in\mathbb{R}^{d_{l}\times 2}$.
Similarly define,
${\mathbf{F}}^{(l+1)}(\mathbf{y},\mathbf{y}^{\prime})=[{\mathbf{f}}^{(l+1)}(\mathbf{y})\
\ {\mathbf{f}}^{(l+1)}(\mathbf{y}^{\prime})]\in\mathbb{R}^{d_{l}\times 2}$.
Using Lemma 3 for each row of ${\mathbf{W}}^{(l+1)}$, we can conclude that

$\displaystyle{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\overset{d}{=}_{{\mathbf{F}}^{(l+1)}={\mathbf{W}}^{(l+1)}{\mathbf{G}}^{(l)}}\widetilde{\mathbf{W}}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp},$

where $\widetilde{\mathbf{W}}$ is a i.i.d. copy of ${\mathbf{W}}^{(l+1)}$.

Note that
$\left[\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}\widetilde{\mathbf{W}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right)^{\top}\widetilde{\mathbf{W}}\right]^{\top}\in\mathbb{R}^{2d_{l}}\sim\mathcal{N}(0,\boldsymbol{\Sigma})$
where
$\boldsymbol{\Sigma}=\begin{bmatrix}b\mathbb{I}_{d_{l}}&b^{\prime}\mathbb{I}_{d_{l}}\\\
b^{\prime}\mathbb{I}_{d_{l}}&b^{\prime\prime}\mathbb{I}_{d_{l}}\end{bmatrix}$.
In the definition of $\boldsymbol{\Sigma}$,
$b=\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\rangle,b^{\prime}=\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle$
and
$b^{\prime\prime}=\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle$.
If $\mathbf{M}$ is such that
$\boldsymbol{\Sigma}=\mathbf{M}\mathbf{M}^{\top}$, then

$\displaystyle\left[\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}\widetilde{\mathbf{W}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right)^{\top}\widetilde{\mathbf{W}}\right]^{\top}\overset{d}{=}\mathbf{M}\boldsymbol{\xi},$

where $\boldsymbol{\xi}\sim\mathcal{N}(0,\mathbb{I}_{2d_{l}})$. Thus, for
fixed ${\mathbf{G}}^{(l)}$ and conditioned on the value of
$\\{{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime}),{\mathbf{h}}^{(l)}(\mathbf{y}),{\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})\\}$,
we have,

$\displaystyle\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})$
$\displaystyle\overset{d}{=}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}\widetilde{\mathbf{W}}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left(\widetilde{\mathbf{W}}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})$
$\displaystyle\overset{d}{=}([\mathbb{I}_{d_{l}}\ \
0]\mathbf{M}\boldsymbol{\xi})^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}([0\
\ \mathbb{I}_{d_{l}}]\mathbf{M}\boldsymbol{\xi})$
$\displaystyle\overset{d}{=}\frac{1}{2}\boldsymbol{\xi}^{\top}\mathbf{M}^{\top}\begin{bmatrix}0&\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\\\
\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}&0\end{bmatrix}\mathbf{M}\boldsymbol{\xi}$

Define

$\displaystyle\mathbf{A}:=\frac{1}{2}\mathbf{M}^{\top}\begin{bmatrix}0&\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\\\
\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}&0\end{bmatrix}\mathbf{M}.$

Then we have,

$\displaystyle\mathbb{E}[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}]$
$\displaystyle=\mathrm{tr}(\mathbf{A})=\frac{1}{2}\mathrm{tr}\left(\begin{bmatrix}0&\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\\\
\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}&0\end{bmatrix}\boldsymbol{\Sigma}\right)$
$\displaystyle=b^{\prime}\mathrm{tr}(\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\mathbb{I}_{d_{l}})$
$\displaystyle=b^{\prime}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp})$
$\displaystyle=b^{\prime}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})(\mathbf{I}_{d_{l}}-\boldsymbol{\Pi}_{\mathbf{G}}))$
$\displaystyle=b^{\prime}\left[\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))-\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}})\right].$

Since
$\mathrm{tr}(\boldsymbol{\Pi}_{\mathbf{G}})=\mathrm{rank}(\boldsymbol{\Pi}_{\mathbf{G}}))\leq
2$, we have,

$\displaystyle
0\leq\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}})\leq\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}\mathrm{tr}(\boldsymbol{\Pi}_{\mathbf{G}})\leq
2\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}.$

Consequently,

$\displaystyle\left|\mathbb{E}[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}]-b^{\prime}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))\right|\leq
2b^{\prime}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}.$

For the upper bound on the spectrum, note that
$\|\mathbf{M}\|_{2}^{2}=\|\boldsymbol{\Sigma}\|_{2}\leq b+b^{\prime\prime}$.
Hence,

$\displaystyle\|\mathbf{A}\|_{2}$
$\displaystyle\leq\frac{1}{2}\|\mathbf{M}\|_{2}^{2}\|\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\|_{2}$
$\displaystyle\leq\frac{1}{2}(b+b^{\prime\prime})\|\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\|_{2}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}\|\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\|_{2}$
$\displaystyle\leq\frac{b+b^{\prime\prime}}{2}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}.$

Thus, on using Lemma 17 with $t=\log(3/\delta)$, we have with probability at
least $1-\delta/3$

$\displaystyle\left|\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}-\mathbb{E}[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}]\right|$
$\displaystyle\leq 2(\|\mathbf{A}\|_{F}\sqrt{t}+\|\mathbf{A}\|_{2}t)$
$\displaystyle\leq 2\|\mathbf{A}\|_{2}(\sqrt{2d_{l}t}+t)$
$\displaystyle\leq(b+b^{\prime\prime})\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}\left(\sqrt{2d_{l}\log\left(\frac{3}{\delta}\right)}+\log\left(\frac{3}{\delta}\right)\right).$

Consequently,

$\displaystyle\left|\frac{c_{s}}{d_{l}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})-\frac{c_{s}}{d_{l}}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right|$
$\displaystyle\leq\frac{c_{s}}{d_{l}}\left|\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}-\mathbb{E}[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}]\right|+\frac{c_{s}}{d_{l}}\left|\mathbb{E}[\boldsymbol{\xi}^{\top}\mathbf{A}\boldsymbol{\xi}]-b^{\prime}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))\right|$
$\displaystyle\leq
c_{s}(b+b^{\prime\prime})\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{3}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{3}{\delta}\right)\right)+\frac{2b^{\prime}c_{s}}{d_{l}}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2},$

holds with probability at least $1-\delta/3$. The lemma follows by taking a
union bound over all possible choices of $(\mathbf{y},\mathbf{y}^{\prime})$.

We can use the above result to obtain the following bound for any
$\mathbf{y}\in\\{\mathbf{x},\mathbf{x}^{\prime}\\}$

$\displaystyle\sqrt{\frac{c_{s}}{d_{l}}}\left\|\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y})\right\|$
$\displaystyle\leq\left\\{\frac{c_{s}}{d_{l}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\\}^{1/2}$
$\displaystyle\leq\left\\{\frac{c_{s}}{d_{l}}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}))b+2c_{s}b\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y})\|_{2}\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{3}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{3}{\delta}\right)\right)+\frac{2bc_{s}}{d_{l}}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}\right\\}^{1/2}$
$\displaystyle\leq\sqrt{bc_{s}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y})\|_{2}}\cdot\left\\{1+2\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{3}{\delta}\right)}+\frac{1}{d_{l}}\left(1+\log\left(\frac{3}{\delta}\right)\right)\right)\right\\}^{1/2}$
$\displaystyle\leq\sqrt{2bc_{s}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y})\|_{2}},$

where
$b=\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\rangle$
and the last step uses the relation the bound on $d_{l}$.

###  B.5 Proof of Lemma 12

Fix any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$.
For ease of writing let
${\mathbf{V}}^{(l+1)}(\mathbf{x}):=\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{x})$.
We are interested in bounding the following expression.

$\displaystyle\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}){\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})-\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})$
$\displaystyle=\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}(\boldsymbol{\Pi}_{\mathbf{G}}+\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}){\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})(\boldsymbol{\Pi}_{\mathbf{G}}+\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}){\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})-$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})$
$\displaystyle=\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})+\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})+$
$\displaystyle\ \ \ \ \
\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime}).$

Consequently,

$\displaystyle\frac{c_{s}}{d_{l}}\left|\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}){\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})-\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})\right|$
$\displaystyle=\frac{c_{s}}{d_{l}}\bigg{|}\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})+\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})+$
$\displaystyle\ \ \ \ \
\left({\mathbf{V}}^{(l+1)}(\mathbf{y})\right)^{\top}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y}){\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{V}}^{(l+1)}(\mathbf{y}^{\prime})\bigg{|}$
$\displaystyle\leq\frac{c_{s}}{d_{l}}\left\|\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y})\right\|\left\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\|+$
$\displaystyle\ \ \ \ \
\frac{c_{s}}{d_{l}}\left\|\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}{\mathbf{D}}^{(l)}(\mathbf{y})\right\|\left\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\|+$
$\displaystyle\ \ \ \ \
\frac{c_{s}}{d_{l}}\left\|\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\mathbf{D}}^{(l)}(\mathbf{y})\right\|\left\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\|$
$\displaystyle\leq\frac{c_{s}}{d_{l}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\|{\mathbf{D}}^{(l)}(\mathbf{y})\|_{2}\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\|_{2}+$
$\displaystyle\ \ \ \ \
c_{s}\sqrt{\frac{2}{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\|{\mathbf{D}}^{(l)}(\mathbf{y})\|_{2}\|{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\|\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\|_{2}+$
$\displaystyle\ \ \ \ \
c_{s}\sqrt{\frac{2}{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\|{\mathbf{D}}^{(l)}(\mathbf{y})\|_{2}\|{\mathbf{b}}^{(l+1)}(\mathbf{y})\|\|{\mathbf{D}}^{(l)}(\mathbf{y}^{\prime})\|_{2}$
$\displaystyle\leq\frac{c_{s}}{d_{l}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]^{2}\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}+$
$\displaystyle\ \ \ \ \
c_{s}\sqrt{\frac{8}{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right](s^{(L-l)/2}+1)\|{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\|_{2}$
$\displaystyle\leq\frac{c_{s}\varepsilon_{5}}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\times$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}`\left\\{\frac{1}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{8}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]+\sqrt{8}(s^{(L-l)/2}+1)\right\\},$

where we used Lemma 11 and 18 in fourth step and the condition of
$\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$
in the last step. Both lemmas hold with probability at least $1-\delta/2$,
ensuring that the overall expression is true with probability at least
$1-\delta$.

###  B.6 Proof of Lemma 13

Fix any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$.
Conditioned on
$\bar{\mathcal{A}}^{L}(\varepsilon_{1}/2)\land\bar{\mathcal{B}}^{l+1}(\varepsilon_{2})\land\bar{\mathcal{C}}(\varepsilon_{3})\land\bar{\mathcal{D}}^{l}(\varepsilon_{4})\land\bar{\mathcal{E}}^{l}(\varepsilon_{5})$,
we begin with bounding
$\left|\left\langle{\mathbf{b}}^{(l)}(\mathbf{y}),{\mathbf{b}}^{(l)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{x},\mathbf{y}^{\prime})\right|$.
Using the definition of ${\mathbf{b}}^{(l)}(\mathbf{y})$ we have,

$\displaystyle\left|\left\langle{\mathbf{b}}^{(l)}(\mathbf{y}),{\mathbf{b}}^{(l)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle=\left|\frac{c_{s}}{d_{l}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(j)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\frac{c_{s}}{d_{l}}\bigg{|}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
-\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\bigg{|}$
$\displaystyle+\Bigg{|}\frac{c_{s}}{d_{l}}\left({\mathbf{b}}^{(l+1)}(\mathbf{y})\right)^{\top}{\mathbf{W}}^{(l+1)}\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}{\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\boldsymbol{\Pi}_{\mathbf{G}}^{\perp}\left({\mathbf{W}}^{(l+1)}\right)^{\top}{\mathbf{b}}^{(l+1)}(\mathbf{y})-$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\frac{c_{s}}{d_{l}}\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\Bigg{|}$
$\displaystyle+\left|c_{s}\frac{\mathrm{tr}({\boldsymbol{\Delta}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime}))}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle-\prod_{j=l}^{L+1}{\dot{\Sigma}}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|$
$\displaystyle\leq\Bigg{(}\frac{c_{s}\varepsilon_{5}}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\times$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left\\{\frac{1}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]+\sqrt{8}(s^{(L-l)/2}+1)\right\\}\Bigg{)}$
$\displaystyle+c_{s}\left(\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y})\right\rangle+\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\right)\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{6}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{6}{\delta}\right)\right)\varepsilon_{5}$
$\displaystyle+\frac{2c_{s}}{d_{l}}\left\langle{\mathbf{b}}^{(l+1)}(\mathbf{y}),{\mathbf{b}}^{(l+1)}(\mathbf{y}^{\prime})\right\rangle\varepsilon_{5}+s^{L-l}\varepsilon_{4}+s\varepsilon_{2}$
$\displaystyle\leq\Bigg{(}\frac{c_{s}\varepsilon_{5}}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]\times$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\left\\{\frac{1}{\sqrt{d_{l}}}\left[(s^{(L-l)/2}+1)\sqrt{2\log\left(\frac{16}{\delta}\right)}+s^{L-l}\varepsilon_{3}\sqrt{2}\right]+\sqrt{8}(s^{(L-l)/2}+1)\right\\}\Bigg{)}$
$\displaystyle+2c_{s}(s^{L-l}+1)\left(\sqrt{\frac{2}{d_{l}}\log\left(\frac{6}{\delta}\right)}+\frac{1}{d_{l}}\log\left(\frac{6}{\delta}\right)\right)\varepsilon_{5}+\frac{2c_{s}}{d_{l}}(s^{L-l}+1)\varepsilon_{5}+s^{L-l}\varepsilon_{4}+s\varepsilon_{2}.$

In the fourth step, we used Lemma 10, 12 and 11 with the last two each holding
with probability at least $1-\delta/2$. Consequently, the above expression
holds with probability at least $1-\delta$.

###  B.7 Proof of Lemma 14

We carry out the analysis conditioned on $\bar{\mathcal{A}}^{l}(\varepsilon)$.
Since
$\left|\left({\mathbf{h}}^{(l)}(\mathbf{y})\right)^{\top}{\mathbf{h}}^{(l)}(\mathbf{y}^{\prime})-{\Sigma}^{(l)}(\mathbf{y},\mathbf{y}^{\prime})\right|\leq\varepsilon$
for all
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$
we can conclude that
$\|{\tilde{\mathbf{G}}}^{(l)}-{\Lambda}^{(l)}\|_{\infty}\leq 2\varepsilon$.
Since $\breve{\sigma}_{s-1}$ is $\beta_{s-1}$-Lipschitz in
$\mathcal{M}_{+}^{\gamma_{s-1}}$ w.r.t. $\infty$-norm, we have,

$\displaystyle|\breve{\sigma}_{s-1}({\mathbf{G}}^{(l)})-\breve{\sigma}_{s-1}({\Lambda}^{(l+1)})|\leq\beta_{s-1}\|{\tilde{\mathbf{G}}}^{(l)}-{\Lambda}^{(l+1)}\|_{\infty}\leq
2\beta_{s-1}\varepsilon,$

for $\varepsilon\leq\gamma_{s-1}$. Fix any
$(\mathbf{y},\mathbf{y}^{\prime})\in\\{(\mathbf{x},\mathbf{x}),(\mathbf{x},\mathbf{x}^{\prime}),(\mathbf{x}^{\prime},\mathbf{x}^{\prime})\\}$.
We have that,