rdpurple abblue abbmagenta szred

# Contextual Bandits with Online Neural Regression

Rohan Deb
University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>Yikun Ban
University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>Shiliang Zuo
University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>
Jingrui He
University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>Arindam Banerjee
University of Illinois Urbana-Champaign
<EMAIL_ADDRESS>
###### Abstract

Recent works have shown a reduction from contextual bandits to online
regression under a realizability assumption (Foster and Rakhlin, 2020; Foster
and Krishnamurthy, 2021). In this work, we investigate the use of neural
networks for such online regression and associated Neural Contextual Bandits
(NeuCBs). Using existing results for wide networks, one can readily show a
${\mathcal{O}}(\sqrt{T})$ regret for online regression with square loss, which
via the reduction implies a ${\mathcal{O}}(\sqrt{K}T^{3/4})$ regret for
NeuCBs. Departing from this standard approach, we first show a
$\mathcal{O}(\log T)$ regret for online regression with almost convex losses
that satisfy QG (Quadratic Growth) condition, a generalization of the PL
(Polyak-Łojasiewicz) condition, and that have a unique minima. Although not
directly applicable to wide networks since they do not have unique minima, we
show that adding a suitable small random perturbation to the network
predictions surprisingly makes the loss satisfy QG with unique minima. Based
on such a perturbed prediction, we show a ${\mathcal{O}}(\log T)$ regret for
online regression with both squared loss and KL loss, and subsequently convert
these respectively to $\tilde{\mathcal{O}}(\sqrt{KT})$ and
$\tilde{\mathcal{O}}(\sqrt{KL^{*}}+K)$ regret for NeuCB, where $L^{*}$ is the
loss of the best policy. Separately, we also show that existing regret bounds
for NeuCBs are $\Omega(T)$ or assume i.i.d. contexts, unlike this work.
Finally, our experimental results on various datasets demonstrate that our
algorithms, especially the one based on KL loss, persistently outperform
existing algorithms.

##  1 Introduction

Contextual Bandits (CBs) provide a powerful framework for sequential decision
making problems, where a learner takes decisions over $T$ rounds based on
partial feedback from the environment. At each round, the learner is presented
with $K$ context vectors to choose from, and a scalar output is generated
based on the chosen context. The objective is to minimize111We use the loss
formulation instead of rewards. the accumulated output in $T$ rounds. Many
existing works assume that the expected output at each round depends linearly
on the chosen context. This assumption has enabled tractable solutions, such
as UCB-based approaches (Chu et al., 2011; Abbasi-Yadkori et al., 2011) and
Thompson Sampling (Agrawal and Goyal, 2013). However, in many real-world
applications, the output function may not be linear, rendering these methods
inadequate. Recent years have seen progress in the use of neural networks for
contextual bandit problems (Zhou et al., 2020; Zhang et al., 2021) by
leveraging the representation power of overparameterized models, especially
wide networks (Allen-Zhu et al., 2019b; Cao and Gu, 2019b; Du et al., 2019;
Arora et al., 2019b). These advances focus on learning the output function in
the Neural Tangent Kernel (NTK) regime and drawing on results from the kernel
bandit literature (Valko et al., 2013).

Separately, (Foster and Rakhlin, 2020) adapted the inverse gap weighting idea
from Abe and Long (1999); Abe et al. (2003) and gave an algorithm (SquareCB)
that relates the regret of CBs, $\operatorname{\text{Reg${}_{\text{CB}}$}}(T)$
to the regret of online regression with square loss
$\text{R}_{\operatorname{\text{Sq}}}(T)$. The work uses a realizability
assumption: the true function generating the outputs belongs to some function
class ${\cal F}$. In this approach, the learner learns a score for every arm
(using online regression) and computes the probability of choosing an arm
based on the inverse of the gap in scores leading to a regret bound
$\operatorname{\text{Reg${}_{\text{CB}}$}}(T)=\mathcal{O}\left(\sqrt{KT\text{R}_{\operatorname{\text{Sq}}}(T)}\right).$
Subsequently, Foster and Krishnamurthy (2021) revisited SquareCB and provided
a modified algorithm (FastCB), with binary Kullback–Leibler (KL) loss and a
re-weighted inverse gap weighting scheme that attains a _first-order_ regret
bound. A _first-order_ regret bound is data-dependent in the sense that it
scales sub-linearly with the loss of the best policy $L^{*}$ instead of $T$.
They showed that if regret of online regression with KL loss is
$\text{R}_{\operatorname{\text{KL}}}(T)$ then the regret for the bandit
problem can be bounded by
$\operatorname{\text{Reg${}_{\text{CB}}$}}(T)=\mathcal{O}(\sqrt{KL^{*}\text{R}_{\operatorname{\text{KL}}}(T)}+K\text{R}_{\operatorname{\text{KL}}}(T)).$
Further, under the realizability assumption, Simchi-Levi and Xu (2020) showed
that an offline regression oracle with $\mathcal{O}(\log T)$ calls can also
achieve an optimal regret for CBs. This improves upon the $\mathcal{O}(T)$
calls to an online regression oracle made by SquareCB and FastCB but works
only for the stochastic setting, i.e., when the contexts are drawn i.i.d. from
a fixed distribution.

In this work we develop novel regret bounds for online regression with neural
networks and subsequently use the reduction in Foster and Rakhlin (2020);
Foster and Krishnamurthy (2021) to give regret guarantees for NeuCBs. Before
we unpack the details, we discuss the research gaps in existing algorithms for
NeuCBs to better motivate our contributions in the context of available
literature.

###  1.1 Research Gaps in Neural Contextual Bandits

We discuss some problems and restrictive assumptions with existing NeuCB
algorithms. Table 1 summarizes these comparisons. We also discuss why naively
extending existing results for wide networks with the CBs to online regression
reduction lead to sub-optimal regret bounds. In Section 5 we further outline
some related works in contextual bandits and overparameterized neural models.

  1. 1.

Neural UCB ((Zhou et al., 2020)) and Neural TS ((Zhang et al., 2021)): Both
these works focus on learning the loss function in the Neural Tangent Kernel
(NTK) regime and drawing on results from the kernel bandit literature (Valko
et al., 2013). The regret bound is shown to be $\tilde{{\cal
O}}(\tilde{d}\sqrt{T})$, where $\tilde{d}$ is the effective dimension of the
NTK matrix. When the eigen-values of the kernel decreases polynomially, one
can show that $\tilde{d}$ depends logarithmically in $T$ (see Remark 4.4 in
(Zhou et al., 2020) and Remark 1 in (Valko et al., 2013)) and therefore the
final regret is still $\tilde{{\cal O}}(\sqrt{T})$. However in Appendix A we
show that under the assumptions in the papers, the regret bounds for both
NeuralUCB and NeuralTS is $\Omega(T)$ in worst case.

  2. 2.

EE-Net (Ban et al., 2022b): This work uses an exploitation network for
learning the output function and an exploration network to learn the potential
gain of exploring at the current step. Although EE-Net avoids picking up a
$\tilde{d}$ dependence in its regret bound, it has two drawbacks. (1) It
assumes that the contexts are chosen i.i.d. from a given distribution, an
assumption that generally does not hold for real world CB problems. (2) It
needs to store all the previous networks until the current time step and then
makes a prediction by randomly picking a network from all the past networks
(see lines 32-33 in Algorithm 1 of Ban et al. (2022b)), a strategy that does
not scale to real world deployment.

  3. 3.

SquareCB (Foster and Rakhlin, 2020) and FastCB (Foster and Krishnamurthy,
2021): Both these works provide regret bounds for CBs in terms of regret for
online regression. Using online gradient descent for online regression (as in
this paper) with regret ${\cal O}(\sqrt{T})$, SquareCB and FastCB provide
${\cal O}(\sqrt{K}T^{3/4})$ and ${\cal O}(\sqrt{KL^{*}}T^{1/4}+K\sqrt{T})$
regret for CBs (see Example 2 in Section 2.3 of Foster and Rakhlin (2020) and
Example 5 in Section 4 of Foster and Krishnamurthy (2021) respectively).
Existing analysis with neural models that use almost convexity of the loss
(see Chen et al. (2021)) show ${\cal O}(\sqrt{T})$ regret for online
regression, and naively combining it with the SquareCB and FastCB lead to the
same sub-optimal regret bounds for NeuCBs.

Algorithm | Regret | Remarks
---|---|---
Neural UCB (Zhou et al., 2020) | $\tilde{{\cal O}}(\tilde{d}\sqrt{T})$ | Bound depends on $\tilde{d}$ and could be $\Omega(T)$ in worst case.
Neural TS Zhang et al. (2021) | $\tilde{{\cal O}}(\tilde{d}\sqrt{T})$ | Bound depends on $\tilde{d}$ and could be $\Omega(T)$ in worst case.
EE-Net (Ban et al., 2022b) | $\tilde{{\cal O}}(\sqrt{T})$ | Assumes that the contexts at every round are drawn
i.i.d and needs to store all the previous networks.
NeuSquareCB (This work) | $\tilde{{\cal O}}(\sqrt{KT})$ | No dependence on $\tilde{d}$ and holds even when the contexts
are chosen adversarially.
NeuFastCB (This work) | $\tilde{{\cal O}}(\sqrt{L^{*}K}+K)$ | No dependence on $\tilde{d}$ and holds even when the contexts
are chosen adversarially. Further, this is the first
data-dependent regret bound for neural bandits.
Table 1: Comparison with prior works. $T$ is the horizon length, $L^{*}$ is
the cumulative loss of the best policy and $\tilde{d}$ is the effective
dimension of the NTK matrix. See section 1.1 and section 1.2 for detailed
discussions.

###  1.2 Our Contributions

Our key contributions are summarized below:

  1. 1.

Lower Bounds: As outlined in Section 1.1, we formally show that an (oblivious)
adversary can always choose a set of context vectors and a reward function at
the beginning, such that the regret bounds for NeuralUCB ((Zhou et al., 2020))
and NeuralTS ((Zhang et al., 2021)) becomes $\Omega(T)$. See Appendix A.1 and
A.2 for the corresponding theorems and their proofs.

  2. 2.

QG Regret: We provide ${\cal O}(\log T)+\epsilon T$ regret for online
regression when the loss function satisfies (i) $\epsilon$\- almost convexity,
(ii) QG condition, and (iii) has unique minima (cf. Assumption 2) as long as
the minimum cumulative loss in hindsight (interpolation loss) is $O(\log T)$.
This improves over the ${\cal O}(\sqrt{T})+\epsilon T$ bound in Chen et al.
(2021) that only exploits $\epsilon$\- almost convexity.

  3. 3.

Regret for wide networks: While the QG result is not directly applicable for
neural models, since they do not have unique minima, we show adding a suitably
small random perturbation to the prediction eq. 10, makes the losses satisfy
QG with unique minima. Using such a perturbed neural prediction, we provide
regret bounds with the following loss functions:

    1. (a)

Squared loss: We provide ${\cal O}(\log T)$ regret for online regression with
the perturbed network (Theorem 3.2) and thereafter using the online regression
to CB reduction obtain $\tilde{{\cal O}}(\sqrt{KT})$ regret for NeuCBs with
our algorithm $\mathsf{NeuSquareCB}$ (Algorithm 1).

    2. (b)

Kullback–Leibler (KL) loss: We further provide an ${\cal O}(\log T)$ regret
for online regression with KL loss using the perturbed network (Theorem 3.3).
To the best of our knowledge, this is the first result that shows PL/QG
condition holds for KL loss, and would be of independent interest. Further,
using the reduction, we obtain the first data dependent regret bound of
$\tilde{\mathcal{O}}(\sqrt{L^{*}K}+K)$ for NeuCBs with our algorithm
$\mathsf{NeuFastCB}$ (Algorithm 2).

  4. 4.

Empirical Performance: Finally, in Section 6 we compare our algorithms against
baseline algorithms for NeuCBs. Unlike previous works, we feed in contexts to
the algorithms in an adversarial manner (see Section 6 for details). Our
experiments on various datasets demonstrate that the proposed algorithms
(especially $\mathsf{NeuFastCB}$) consistently outperform existing NeuCB
algorithms, which themselves have been shown to outperform their linear
counterparts such as LinUCB and LinearTS (Zhou et al., 2020; Zhang et al.,
2021; Ban et al., 2022b).

We also emphasize that our regret bounds are independent of the effective
dimension that appear in kernel bandits (Valko et al., 2013) and some recent
neural bandit algorithms (Zhou et al., 2020; Zhang et al., 2021). Further our
algorithms are efficient to implement, do not require matrix inversions unlike
NeuralUCB (Zhou et al., 2020) and NeuralTS (Zhang et al., 2021), and work even
when the contexts are chosen adversarially unlike approaches specific to the
i.i.d. setting (Ban et al., 2022b).

##  2 Neural Online Regression: Setting and Formulation

Problem Formulation: At round $t\in[T]$, the learner is presented with an
input $\mathbf{x}_{t}\in{\cal X}\subset\mathbb{R}^{d}$ and is required to make
real-valued predictions $\hat{y}_{t}$. Then, the true outcome $y_{t}\in{\cal
Y}=[0,1]$ is revealed.

######  Assumption 1 (Realizability).

The conditional expectation of $y_{t}$ given $\mathbf{x}_{t}$ is given by some
unknown function $h$: ${\cal X}\mapsto{\cal Y}$, i.e.,
$\mathbb{E}[y_{t}|\mathbf{x}_{t}]=h(\mathbf{x}_{t}).$ Further, the context
vectors satisfy $\|\mathbf{x}_{t}\|\leq 1$ $\forall t\in[T]$.

Neural Architecture: We consider a feedforward neural network with smooth
activations as in Du et al. (2019); Banerjee et al. (2023) and the network
output is given by

$\displaystyle
f({\theta_{t}};\mathbf{x}):={m}^{-1/2}\mathbf{v}_{t}^{\top}\phi({m}^{-1/2}{W_{t}}^{(L)}\phi(\cdots\leavevmode\nobreak\
\phi({m}^{-1/2}{W_{t}}^{(1)}\mathbf{x})\leavevmode\nobreak\
\cdots))\leavevmode\nobreak\ ,$ (1)

where $L$ is the number of hidden layers and $m$ is the width of the network.
Further, ${W_{t}}^{(1)}\in\mathbb{R}^{m\times
d},W_{t}^{(l)}\in\mathbb{R}^{m\times m},\forall l\in\\{2,\dots,L\\}$ are
layer-wise weight matrices with $W_{t}^{(l)}=[w^{(l)}_{t,i,j}]$,
$\mathbf{v}_{t}\in\mathbb{R}^{m}$ is the last layer vector and $\phi(\cdot)$
is a lipschitz and smooth (pointwise) activation function.

We define

$\displaystyle\theta_{t}:=(\operatorname{vec}(W_{t}^{(1)})^{\top},\ldots,\operatorname{vec}(W_{t}^{(L)})^{\top},\mathbf{v}^{\top})^{\top}\leavevmode\nobreak\
$ (2)

as the vector of all parameters in the network. Note that
$\theta_{t}\in\mathbb{R}^{p}$, where $p=md+(L-1)m^{2}+m$ is total number of
parameters.

Regret: At time $t$ an algorithm picks a $\theta_{t}\in B$, where
$B\subset\mathbb{R}^{p}$ is some comparator class, and outputs the prediction
$f(\theta_{t};\mathbf{x}_{t})$. Consider a loss function $\ell:{\cal
Y}\times{\cal Y}\mapsto\mathbb{R}$ that measures the error between
$f(\theta_{t};\mathbf{x}_{t})$ and the true output $y_{t}$. Then the regret of
neural online regression with loss $\ell$ is defined as

$\text{R}(T):=\sum_{t=1}^{T}\ell(y_{t},f(\theta_{t};\mathbf{x}_{t}))-\inf_{\theta\in
B}\sum_{t=1}^{T}\ell(y_{t},f(\theta;\mathbf{x}_{t}))\leavevmode\nobreak\ ,$
(3)

######  Remark 2.1.

Given the definition of regret in eq. 3, one might wonder if we are assuming
that the function $h$ in Assumption 1 is somehow $f(\tilde{\theta};\cdot)$ for
some $\tilde{\theta}\in B$. Wide networks in fact can realize any function $h$
on a finite set of $T$ points (see Theorem E.1 in Appendix E).

Using almost convexity of the loss function for wide networks, Chen et al.
(2021) show $\text{R}(T)={\cal O}(\sqrt{T})$ regret. Instead, we work with a
small random perturbation to the neural model prediction denoted by
$\tilde{f}$ (see Section 3) with $\mathbb{E}[\tilde{f}]=f$ and consider the
following regret:

$\tilde{\text{R}}(T):=\sum_{t=1}^{T}\ell(y_{t},\tilde{f}(\theta_{t};\mathbf{x}_{t}))-\inf_{\theta\in
B}\sum_{t=1}^{T}\ell(y_{t},\tilde{f}(\theta;\mathbf{x}_{t}))\leavevmode\nobreak\
.\vspace{-0.25cm}$ (4)

As we shortly show in Section 3, the surprising aspect of working with such
mildly perturbed $\tilde{f}$ is that we will get $\tilde{R}(T)=O(\log T)$.
Further, the cumulative loss with such $\tilde{f}$ will also be competitive
against the best non-perturbed $f$ with $\theta\in B$ in hindsight (Remark
3.4).

Notation: $n=\mathcal{O}(t)$ (and $\Omega(t)$ respectively) means there exists
constant $c>0$ such that $n\leq ct$ (and $n\geq ct$ respectively). Further the
notation $n=\Theta(t)$ means there exist constants $c_{1},c_{2}>0$ such that
$c_{1}t\leq n\leq c_{2}t$. The notations
$\tilde{\mathcal{O}}(t),\tilde{\Omega}(t),\tilde{\Theta}(t)$ further hide the
dependence on logarithmic terms.

##  3 Neural Online Regression: Regret Bounds

Our objective in this section is to provide regret bounds for projected Online
Gradient Descent (OGD) with the projection operator
$\displaystyle\prod_{B}(\theta)={\operatorname{arginf}}_{\theta^{\prime}\in
B}\|\theta^{\prime}-\theta\|_{2}$. The iterates are given by

$\displaystyle{\theta}_{t+1}=\prod_{B}\big{(}{\theta}_{t}-\eta_{t}\nabla\ell(y_{t},f(\theta_{t};\mathbf{x}_{t}))\big{)}.$
(5)

######  Definition 3.1 (Quadratic Growth (QG) condition).

Consider a function $J:\mathbb{R}^{p}\rightarrow\mathbb{R}$ and let the
solution set be
$\mathcal{J}^{*}=\\{\theta^{\prime}:\theta^{\prime}\in\arg\min_{\theta}J(\theta)\\}$.
Then $J$ is said to satisfy the QG condition with QG constant $\mu$, if
$J(\theta)-J(\theta^{*})\geq\frac{\mu}{2}\|\theta-\theta^{*}\|^{2}\leavevmode\nobreak\
,\forall\theta\in\mathbb{R}^{p}\setminus\mathcal{J}^{*},$ where $\theta^{*}$
is the projection of $\theta$ onto $\mathcal{J}^{*}$.

######  Remark 3.1 (PL $\Rightarrow$ QG).

The recent literature has extensively studied the PL condition and how neural
losses satisfy the PL condition (Karimi et al., 2016; Liu et al., 2020, 2022).
While the Quadratic Growth (QG) condition has not been as widely studied, one
can show that the PL condition implies the QG condition (Karimi et al., 2016,
Appendix A), i.e., for $\mu>0$

$\displaystyle J(\theta)-J(\theta^{*})\leq\frac{1}{2\mu}\|\nabla
J(\theta)\|_{2}^{2}\;\;\;\;\text{{(PL)}}\quad\Rightarrow\quad
J(\theta)-J(\theta^{*})\geq\frac{\mu}{2}\|\theta-\theta^{*}\|_{2}^{2}\;\;\;\;\text{{(QG)}}$

######  Assumption 2.

Consider a predictor $g(\theta;\mathbf{x})$ and suppose the loss
$\ell(y_{t},g(\theta;\mathbf{x}_{t})),\forall t\in[T]$, satisfies

  1. (a)

Almost convexity, i.e., there exists $\epsilon>0$, such that
$\forall\theta,\theta^{\prime}\in B$,

$\displaystyle\ell(y_{t},g(\theta;\mathbf{x}_{t}))\geq\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))+\langle\theta-\theta^{\prime},\nabla_{\theta}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))\rangle-\epsilon.$
(6)

  2. (b)

QG condition i.e., $\exists\mu>0$, such that $\forall\theta\in
B\setminus\Theta^{*}_{t}$, where
$\Theta^{*}_{t}=\left\\{\theta_{t}|\theta_{t}\in\operatorname{arginf}_{\theta}\ell(y_{t},g(\theta;\mathbf{x}_{t}))\right\\}$
and $\theta^{*}_{t}$ is the projection of $\theta$ onto $\Theta_{t}^{*}$ we
have

$\displaystyle\ell(y_{t},g(\theta;\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t}))\geq\frac{\mu}{2}\|\theta-\theta^{*}_{t}\|_{2}^{2}.$
(7)

  3. (c)

has a unique minima.

Following (Liu et al., 2020, 2022), we also assume the following for the
activation and loss function.

######  Assumption 3.

With $\ell_{t}:=\ell(y_{t},\hat{y}_{t})$,
$\ell_{t}^{\prime}:=\frac{d\ell_{t}}{d\hat{y}_{t}}$, and
$\ell_{t}^{\prime\prime}:=\frac{d^{2}\ell_{t}}{d\hat{y}^{2}_{t}}$, we assume
that the loss $\ell(y_{t},\hat{y}_{t})$ is Lipschitz, i.e.,
$|\ell_{t}^{\prime}|\leq\lambda,$ strongly convex, i.e.,
$\ell^{\prime\prime}_{t}\geq a$ and smooth, i.e., $\ell^{\prime\prime}_{t}\leq
b$, for some $\lambda,a,b>0.$

######  Theorem 3.1 (Regret Bound under QG condition).

Under Assumptions 2 and 3 the regret of projected OGD with step size
$\eta_{t}=\frac{4}{\mu t}$, where $\mu$ is the QG constant from Assumption
2(b), satisfies

$\displaystyle\tilde{\text{R}}(T)\leq{\cal O}\left(\frac{\lambda^{2}}{\mu}\log
T\right)+\epsilon T+2\underset{\theta\in
B}{\inf}\sum_{t=1}^{T}\ell(y_{t},g(\theta;\mathbf{x}_{t})).$ (8)

The proof of Theorem 3.1 can be found in Appendix C.1.

######  Remark 3.2.

Under Assumption 2(a), Chen et al. (2021) show $R(T)={\cal
O}(\sqrt{T})+\epsilon T$. In contrast our bound improves the first term to
${\cal O}(\log T)$ but has an extra term: cumulative loss of the best
$\theta$, and uses two additional assumptions (2(b) and 2(c)). Note that the
third term vanishes if $g$ interpolates and the interpolation loss is zero
(holds for e.g., with over-parameterized networks and square loss). Further
for over-parameterized networks Chen et al. (2021) show that
$\epsilon=1/\text{poly}(m)$, and therefore the $\epsilon T$ term is ${\cal
O}(1)$ for large enough $m$. A similar argument also holds for our model.

Next we discuss if Theorem 3.1 can indeed be used for neural loss functions.
For concreteness consider the square loss
$\ell_{\operatorname{\text{Sq}}}(y_{t},f(\theta_{t};\mathbf{x}_{t})):=\frac{1}{2}(y_{t}-f(\theta_{t};\mathbf{x}_{t}))^{2}$.
Following Liu et al. (2020); Banerjee et al. (2023), we make the following
assumption on the initial parameters of the network.

######  Assumption 4.

We initialize $\theta_{0}$ with $w_{0,ij}^{(l)}\sim{\cal N}(0,\sigma_{0}^{2})$
for $l\in[L]$ where $\sigma_{0}=\frac{\sigma_{1}}{2\left(1+\frac{\sqrt{\log
m}}{\sqrt{2m}}\right)},\sigma_{1}>0$, and $\mathbf{v}_{0}$ is a random unit
vector with $\left\lVert\mathbf{v}_{0}\right\rVert_{2}=1$.

Next we define $K_{\operatorname{NTK}}(\theta):=[\langle\nabla
f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t^{\prime}})\rangle]\in\mathbb{R}^{T\times T}$ to be the
so-called Neural Tangent Kernel (NTK) matrix at $\theta$ (Jacot et al., 2018)
and make the following assumption at initialization.

######  Assumption 5.

${K_{{\operatorname{NTK}}}(\theta_{0})}$ is positive definite, i.e.,
$K_{\operatorname{NTK}}(\theta_{0})\succeq\lambda_{0}\mathbb{I}$ for some
$\lambda_{0}>0$.

######  Remark 3.3.

The above assumption on the NTK is common in the deep learning literature (Du
et al., 2019; Arora et al., 2019b; Cao and Gu, 2019a) and is ensured as long
any two context vectors $\mathbf{x}_{t}$ do not overlap. All existing regret
bounds for NeuCBs make this assumption (see Assumption 4.2 in Zhou et al.
(2020), Assumption 3.4 in Zhang et al. (2021) and Assumption 5.1 in Ban et al.
(2022b)).

Finally we choose the comparator class
$B=B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, the layer-wise
Frobenius ball around the initialization $\theta_{0}$ with radii
$\rho,\rho_{1}$ (to be chosen as part of analysis) which is defined as

$\displaystyle
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0}):=\\{\theta\in\mathbb{R}^{p}\leavevmode\nobreak\
\text{as in}\leavevmode\nobreak\
\lx@cref{creftype~refnum}{eq:theta_def}:\|\operatorname{vec}(W^{(l)})-\operatorname{vec}(W_{0}^{(l)})\|_{2}\leq\rho,l\in[L],\|\mathbf{v}-\mathbf{v}_{0}\|_{2}\leq\rho_{1}\\}.$
(9)

Consider a network $f(\theta;\mathbf{x})$ that satisfies Assumption 5 with
$\theta_{0}$ initialized as in Assumption 4. Then for
$B=B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ we can show the
following: (i) $\ell_{\operatorname{\text{Sq}}}$ satisfies Assumption 2(a)
with $\epsilon={\cal O}({\text{poly}(L,\rho,\rho_{1})}/{\sqrt{m}})$ (Lemma 13)
and therefore with $m=\Omega(\text{poly}(T,L,\rho,\rho_{1}))$, the second term
in eq. 8 is ${\cal O}(1)$. (ii) $\ell_{\operatorname{\text{Sq}}}$ for a wide
networks satisfies PL condition (Liu et al., 2022) which implies QG, and
therefore Assumption 2(b) is satisfied. (iii) Further the network interpolates
(Theorem E.1) which ensures that the third term in eq. 8 is 0, which makes the
rhs ${\cal O}(\log T)$. However neural models do not have a unique minima and
as such we cannot take advantage of Theorem 3.1 as Assumption 2(c) is
violated. To mitigate this, in the next subsection we construct a randomized
predictor $\tilde{f}$ with $\mathbb{E}[\tilde{f}]=f$ and show that Assumption
2(a),2(b) and 2(c) hold in high probability.

###  3.1 Regret bounds for Squared Loss

To ensure that the loss has a unique minimizer at every time step, we consider
a random network with a small perturbation to the output. In detail, given the
input $\mathbf{x}_{t}$, we define a perturbed network as

$\displaystyle\tilde{f}(\theta_{t},\mathbf{x}_{t},\bm{\varepsilon})=f(\theta_{t};\mathbf{x}_{t})+c_{p}\sum_{j=1}^{p}\frac{(\theta_{t}-\theta_{0})^{T}e_{j}\varepsilon_{j}}{m^{1/4}}\leavevmode\nobreak\
,$ (10)

where $f(\theta_{t};\mathbf{x}_{t})$ is the output of the network as defined
in eq. 1, $c_{p}$ is the perturbation constant to be chosen later,
$\\{e_{j}\\}_{j=1}^{p}$ are the standard basis vectors and
$\bm{\varepsilon}=(\varepsilon_{1},\ldots,\varepsilon_{p})^{T}$ is a random
vector where $\varepsilon_{j}$ is drawn i.i.d from a Rademacher distribution,
i.e., $P(\varepsilon_{j}=+1)=$ $P(\varepsilon_{j}=-1)=1/2$.

Note that $\mathbb{E}[\tilde{f}]=f$. Further $\tilde{f}$ ensures that the
expected loss
$\mathbb{E}_{\bm{\varepsilon}}\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
has a unique minimizer (see Lemma 14). However, since running projected OGD on
$\mathbb{E}_{\bm{\varepsilon}}\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
is not feasible, we next consider an average version of it. Let
${\bm{\varepsilon}}_{s}=(\varepsilon_{s,1},\varepsilon_{s,2},\ldots,\varepsilon_{s,p})^{T}$
where each $\varepsilon_{s,i}$ is i.i.d. Rademacher. Consider $S$ such i.i.d.
draws $\\{{\bm{\varepsilon}}_{s}\\}_{s=1}^{S}$, and define the predictor

$\displaystyle\tilde{f}^{(S)}\left(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\right)=\frac{1}{S}\sum_{s=1}^{S}\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}_{s}),$
(11)

where $\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}_{s})$ is as defined
in eq. 10.

We define the corresponding regret with square loss as

$\displaystyle{\tilde{\text{R}}_{\operatorname{\text{Sq}}}}(T)=\sum_{t=1}^{T}\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}^{(S)}\big{(}\theta_{t};\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\right)-\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}^{(S)}\big{(}\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\right).$
(12)

However, instead of running projected OGD with the loss
$\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}^{(S)}\big{(}\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\right)$,
we use

$\displaystyle{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}:=\frac{1}{S}\sum_{s=1}^{S}\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\right)$
(13)

Note that since $\ell_{\operatorname{\text{Sq}}}$ is convex in the second
argument, using Jensen we have

$\displaystyle\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}^{(S)}\big{(}\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\right)=\ell_{\operatorname{\text{Sq}}}\Big{(}y_{t},\frac{1}{S}\sum_{s=1}^{S}\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}_{s})\Big{)}\leq\frac{1}{S}\sum_{s=1}^{S}\ell_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}_{s})\right).$
(14)

Subsequently we will show via eq. 14 that bounding the regret with eq. 13
implies a bound on eq. 12.

######  Theorem 3.2 (Regret Bound for square loss).

Under Assumption 1, 4 and 5 with appropriate choice of step-size sequence
$\\{\eta_{t}\\}$, width $m$, and perturbation constant $c_{p}$ in eq. 10, with
probability at least $\big{(}1-\frac{C}{T^{4}}\big{)}$ for some constant
$C>0$, over the randomness of initialization and
$\\{\bm{\varepsilon}\\}_{s=1}^{S}$, the regret in eq. 12 of projected OGD with
loss ${\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$,
$S=\Theta(\log m)$ and projection ball
$B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ with
$\rho=\Theta(\sqrt{T}/\lambda_{0})$ and $\rho_{1}=\Theta(1)$ is given by
$\emph{$\tilde{\text{R}}_{\operatorname{\text{Sq}}}(T)$}={\cal O}(\log T).$

_Proof sketch._ The proof of the theorem follows along four key steps as
described below. All of these hold with high probability over the randomness
of initialization and $\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$. A detailed
version of the proof along with all intermediate lemmas and their proofs are
in Appendix C.2. Note that we do not use Assumptions 2 and 3 and, but rather
explicitly prove that they hold.

  1. 1.

Square loss is Lipschitz, strongly convex, and smooth w.r.t. the output: This
step ensures that Assumption 3 is satisfied. Strong convexity and smoothness
follow trivially from the definition of the $\ell_{\operatorname{\text{Sq}}}$.
To show that $\ell_{\operatorname{\text{Sq}}}$ is Lipschitz we show that the
output $\tilde{f}(\theta;\mathbf{x},\bm{\varepsilon})$ is bounded for any
$\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$. Also note
from Theorem 3.1 that the lipschitz parameter of the loss, $\lambda$ appears
in the $\log T$ term and therefore to obtain a ${\cal O}(\log T)$ regret we
also ensure that $\lambda={\cal O}(1)$.

  2. 2.

The average loss in eq. 13 is almost convex and has a unique minimizer: We
show that with $S=\Theta(\log m),$ the average loss in eq. 13 is $\nu$ \-
Strongly Convex (SC) with $\nu={\cal O}\left(\frac{1}{\sqrt{m}}\right)$ w.r.t.
$\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, $\forall
t\in[T]$ which immediately implies Assumption 2(a) and 2(c).

  3. 3.

The average loss in eq. 13 satisfies the QG condition:  It is known that
square loss with wide networks under Assumption 5 satisfies the PL condition
(eg. Liu et al. (2022)) with $\mu={\cal O}(1)$. We show that the average loss
in eq. 13 with $S=\Theta(\log m),$ also satisfies the PL condition with
$\mu={\cal O}(1)$, which implies that it satisfies the QG condition with same
$\mu$.

  4. 4.

Bounding the final regret:  Steps 1 and 2 above surprisingly show that with a
small output perturbation, square loss satisfies (a) almost convexity, (b) QG,
and (c) unique minima as in Assumption 2. Combining with step 3, we have that
all the assumptions of Theorem 3.1 are satisfied by the average loss. Using
union bound over the three steps, invoking Theorem 3.1 we get with high
probability

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta_{t};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}-\inf_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}({\theta};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle\leq 2\inf_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}({\theta};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}+{\cal
O}(\log T).$ (15)

Finally we show that $\inf_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\big{(}y_{t},\big{\\{}\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}={\cal
O}(1)$ using the fact that wide networks interpolate (Theorem E.1) which
implies $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\big{(}y_{t},\big{\\{}\tilde{f}(\theta_{t};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}={\cal
O}(\log T)$ which using eq. 14 and recalling the definition in eq. 13 implies
$\tilde{\text{R}}_{\operatorname{\text{Sq}}}(T)={\cal O}(\log T)$∎

######  Remark 3.4.

Note that $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\big{(}y_{t},\big{\\{}\tilde{f}(\theta_{t};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}={\cal
O}(\log T)$ from step-4 above also implies that $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\big{(}y_{t},\big{\\{}\tilde{f}(\theta_{t};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}-\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},{f}(\theta,\mathbf{x}_{t})\big{)}={\cal
O}(\log T)$ and therefore our predictions are competitive against $f$ as
defined in eq. 1 as well.

######  Remark 3.5.

Although the average loss in eq. 13 is SC (Lemma 6), we do not use standard
results from Shalev-Shwartz (2012); Hazan (2021) to obtain $\mathcal{O}(\log
T)$ regret. This is because, the strong convexity constant
$\nu=\mathcal{O}(1/\sqrt{m})$, and although OGD ensures $\mathcal{O}(\log T)$
regret for SC functions, the constant hidden by ${\cal O}$ scales as
$\frac{1}{\nu}=\sqrt{m}$. For large width models, $m>>T$, and therefore this
approach does not yield a $\mathcal{O}(\log T)$ bound. The key idea is to
introduce bare minimum strong convexity using eq. 10, to ensure unique minima,
without letting go of the QG condition with $\mu={\cal O}(1)$. ∎

###  3.2 Regret bounds for KL Loss

Next we consider the binary KL loss, defined as
$\ell_{\operatorname{\text{KL}}}(y_{t},\hat{y}_{t})=y_{t}\ln\left(\frac{y_{t}}{\sigma(\hat{y}_{t})}\right)+(1-y_{t})\ln\left(\frac{1-y_{t}}{1-\sigma(\hat{y}_{t})}\right),$
where $\sigma(y)=\frac{1}{1+e^{-y}}$ is the sigmoid function. Following the
approach outlined in Section 3.1, we consider a perturbed network as defined
in eq. 10.

Note that here the output of the neural network is finally passed through a
sigmoid. As in eq. 11, we will consider a combined predictor. With slight
abuse of notation, we define the prediction and the corresponding regret with
$\ell_{\operatorname{\text{KL}}}$ respectively as

$\displaystyle\sigma\big{(}\tilde{f}^{(S)}\big{(}\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\big{)}$
$\displaystyle=\frac{1}{S}\sum_{s=1}^{S}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}_{s}))$
(16)
$\displaystyle\tilde{\text{R}}_{\operatorname{\text{KL}}}(T)=\sum_{t=1}^{T}\ell_{\operatorname{\text{KL}}}\big{(}y_{t},\sigma\big{(}\tilde{f}^{(S)}\big{(}\theta_{t};\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\big{)}\big{)}$
$\displaystyle-\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}\ell_{\operatorname{\text{KL}}}\big{(}y_{t},\sigma\big{(}\tilde{f}^{(S)}\big{(}\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{(1:S)}\big{)}\big{)}\big{)}.$

######  Theorem 3.3 (Regret Bound for KL Loss).

Under Assumption 1, 4 and 5 for $y_{t}\in[z,1-z]$, $0<z<1$, with appropriate
choice of step-size sequence $\\{\eta_{t}\\}$, width $m$, and perturbation
constant $c_{p}$, with high probability over the randomness of initialization
and $\\{\bm{\varepsilon}\\}_{s=1}^{S}$, the regret of projected OGD with loss
${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\big{)}=\frac{1}{S}\sum_{s=1}^{S}\ell_{\operatorname{\text{KL}}}\left(y_{t},\sigma(\tilde{f}\big{(}\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{)}\right)$,
$S=\Theta(\log m)$ and projection ball
$B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ with
$\rho=\Theta(\sqrt{T}/\lambda_{0})$ and $\rho_{1}=\Theta(1)$ is given by
$\emph{$\text{R}_{\operatorname{\text{KL}}}(T)$}={\cal O}(\log T)$.

The proof of the theorem follows a similar approach as in proof of Theorem 3.2
(See Appendix C.3).

##  4 Neural Contextual Bandits: Formulation and Regret Bounds

Algorithm 1 Neural SquareCB ($\mathtt{NeuSquareCB}$); Uses Square loss

1:Initialize $\bm{\theta}_{0}$, $\gamma,\\{\eta_{t}\\}$

2:for $t=1,2,...,T$ do

3: Receive contexts $\mathbf{x}_{t,1},...,\mathbf{x}_{t,K}$, and compute
$\hat{y}_{t,a}=\tilde{f}^{(S)}\left(\theta;\mathbf{x}_{t,a},{\bm{\varepsilon}}^{(1:S)}\right),\forall
a\in[K]$ using $\eqref{eq:ftildeS}$

4: Let $b=\arg\min_{a}\hat{y}_{t,a},$
$p_{t,a}=\frac{1}{K+\gamma(\hat{y}_{t,b}-\hat{y}_{t,a})},$ and
$p_{t,b}=1-\sum_{a\neq b}p_{t,a}$

5: Sample arm $a_{t}\sim p_{t}$ and observe output $y_{t,a_{t}}$

6: Update
${\theta}_{t+1}=\prod_{B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\Big{(}{\theta}_{t}-\eta_{t}\nabla{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\big{(}y_{t,a_{t}},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t,a_{t}},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}\Big{)}$.

7:end for

We consider a contextual bandit problem where a learner needs to make
sequential decisions over $T$ time steps. At any round $t\in[T]$, the learner
observes the context for $K$ arms
$\mathbf{x}_{t,1},,...,\mathbf{x}_{t,K}\in\mathbb{R}^{d}$, where the contexts
can be chosen adversarially. The learner chooses an arm $a_{t}\in[K]$ and then
the associated output $y_{t,a_{t}}\in[0,1]$ is observed. We make the following
assumption on the output.

######  Assumption 6.

The conditional expectation of $y_{t,a}$ given $\mathbf{x}_{t,a}$ is given by
$h$: $\mathbb{R}^{d}\mapsto[0,1]$, i.e.,
$\mathbb{E}[y_{t,a}|\mathbf{x}_{t,a}]=h(\mathbf{x}_{t,a}).$ Further, the
context vectors satisfy $\|\mathbf{x}_{t,a}\|\leq 1$, $t\in[T],a\in[K]$.

The learner’s goal is to minimize the regret of the contextual bandit problem
and is defined as the expected difference between the cumulative output of the
algorithm and that of the optimal policy:

$\operatorname{\text{Reg${}_{\text{CB}}$}}(T)=\mathbb{E}\Big{[}\sum_{t=1}^{T}\left(y_{t,a_{t}}-y_{t,a_{t}^{*}}\right)\Big{]},$
(17)

where $a_{t}^{*}=\arg\min_{k\in[K]}h(\mathbf{x}_{t,a})$ is the best action
minimizing the expected output in round $t$.

$\mathtt{NeuSquareCB}$ and $\mathtt{NeuFastCB}$ are summarized in Algorithm 1
and Algorithm 2 respectively. At time $t$, the algorithm computes
$\tilde{f}^{(S)}\left(\theta;\mathbf{x}_{t,a},{\bm{\varepsilon}}^{(1:S)}\right),\forall
a\in[K]$ using eq. 11 (see line 4). It then computes the probability of
selecting an arm using the gap between learned outputs following inverse gap
weighting scheme from Abe and Long (1999) (see line 6) and samples an action
$a_{t}$ from this distribution (see line 7). It then receives the true output
for the selected arm $y_{t,a_{t}}$, and updates the parameters of the network
using projected online gradient descent.

$\mathtt{NeuFastCB}$ employs a similar approach, except that it uses KL loss
to update the parameters of the network and uses a slightly different
weighting scheme to compute the action distribution (Foster and Krishnamurthy,
2021).

######  Theorem 4.1 (Regret bound for $\mathtt{NeuSquareCB}$).

Under Assumption 6 and 5 with appropriate choice of the parameter $\gamma$,
step-size sequence $\\{\eta_{t}\\}$ width $m$, and regularization parameter
$c_{p}$, with high probability over the randomness in the initialization and
$\\{\bm{\varepsilon}\\}_{s=1}^{S}$ the regret for $\mathtt{NeuSquareCB}$ with
$\rho=\Theta(\sqrt{T}/\lambda_{0}),\rho_{1}=\Theta(1)$ is given by
${\emph{$\operatorname{\text{Reg${}_{\text{CB}}$}}(T)$}}\leq\tilde{{\cal
O}}(\sqrt{KT})$.

######  Theorem 4.2 (Regret bound for $\mathtt{NeuFastCB}$).

Under Assumption 6 and 5 with appropriate choice of the parameter $\gamma$,
step-size sequence $\\{\eta_{t}\\}$ width $m$, and regularization parameter
$c_{p}$, with high probability over the randomness in the initialization and
$\\{\bm{\varepsilon}\\}_{s=1}^{S}$, the regret for $\mathtt{NeuFastCB}$ with
$\rho=\Theta(\sqrt{T}/\lambda_{0}),\rho_{1}=\Theta(1)$ is given by
$\emph{$\operatorname{\text{Reg${}_{\text{CB}}$}}(T)$}\leq\tilde{{\cal
O}}(\sqrt{L^{*}K}+K),$ where $L^{*}=\sum_{t=1}^{T}y_{t,a_{t}^{*}}$.

The proof of the Theorem 4.1 and 4.2 follow using the reduction from Foster
and Rakhlin (2020) and (Foster and Krishnamurthy, 2021) respectively, and
crucially using our sharp regret bounds for online regression in Section 3. We
provide both proofs in Appendix D for completeness.

######  Remark 4.1.

Note that since $L^{*}\leq T$ then
$\mathcal{O}(\sqrt{KL^{*}})\leq\mathcal{O}(\sqrt{KT})$. Therefore NeuFastCB is
expected to perform better in most settings “in practice”, especially when
$L^{*}$ is small, i.e., the best policy has low regret. Also note that going
by the upper bounds on the regret, especially the dependence on $K$,
NeuSquareCB could outperform NeuFastCB only if $L^{*}=\Theta(T)$ and $K>>T$.

######  Remark 4.2.

In the linear setting, (Azoury and Warmuth, 2001) gives
$\text{R}_{\operatorname{\text{Sq}}}(T)\leq{\cal O}(p\log(T/p))$, where $p$ is
the feature dimension (Section 2.3, Foster and Rakhlin (2020)). This
translates to $\mathtt{Reg}_{\mathtt{CB}}(T)\leq\tilde{{\cal O}}(\sqrt{pKT})$.
Further with KL loss, using continuous exponential weights gives
$\mathbb{R}_{\operatorname{\text{KL}}}(T)={\cal O}(p\log T/p)$ which
translates to $\mathtt{Reg}_{\mathtt{CB}}(T)\leq{\cal O}(\sqrt{L^{*}Lp\log
T/p}+Kp\log T/p)$ (Section 4, Foster and Krishnamurthy (2021)). However, with
over-parameterized networks, (with $p>>T$), both bounds are $\Omega(T)$.
Therefore it becomes essential to obtain regret bounds that are independent of
the number of parameters in the network, which our results do.

Algorithm 2 Neural FastCB ($\mathsf{NeuFastCB}$); Uses KL loss

1:Initialize $\bm{\theta}_{0}$, $\gamma,\\{\eta_{t}\\}$

2:for $t=1,2,...,T$ do

3: Receive contexts $\mathbf{x}_{t,1},...,\mathbf{x}_{t,K}$ and compute
$\hat{y}_{t,k},\;\forall k\in[K]$ using eq. 16

4: Let $\displaystyle b_{t}=\operatorname*{argmin}_{k\in[K]}\hat{y}_{t,k}$,
$p_{t,k}=\frac{{\hat{y}}_{t,b_{t}}}{K{\hat{y}}_{t,b_{t}}+\gamma({\hat{y}}_{t,k}-{\hat{y}}_{t,b_{t}})},k\in[K],$
and $p_{t,b_{t}}=1-\sum_{k\neq b_{t}}p_{t,k}.$

5: Sample arm $a_{t}\sim p_{t}$ and observe output $y_{t,a_{t}}$

6: Update
${\theta}_{t+1}=\prod_{B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\big{(}{\theta}_{t}-\eta_{t}\nabla{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\big{(}y_{t,a_{t}},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t,a_{t}},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\big{)}\big{)}$.

7:end for

##  5 Related Work

Contextual Bandits: The contextual bandit setting with linear losses has
received extensive attention over the past decade (see for eg. Abe et al.,
2003; Chu et al., 2011; Abbasi-Yadkori et al., 2011; Agrawal and Goyal, 2013;
Ban and He, 2020, 2021). Owing to its remarkable success, Lu and Van Roy
(2017); Zahavy and Mannor (2020); Riquelme et al. (2018) adapted neural models
to the contextual bandit setting. In these initial works all but the last
layers of a DNN were utilized as a feature map to transform contexts from the
raw input space to a low-dimensional space and a linear exploration policy was
then learned on top of the last hidden layer of the DNN. Although these
attempts have yielded promising empirical results, no regret guarantees were
provided. Subsequently (Zhou et al., 2020) introduced the first neural bandit
algorithm with provable regret guarantees that uses a UCB based exploration
and Zhang et al. (2021) further extended it to the Thompson sampling approach.
Both these approaches rely on Kernel bandits (Valko et al., 2013) and have a
linear dependence on effective dimension $\tilde{d}$ of the (NTK) Neural
Tangent Kernel (see Allen-Zhu et al., 2019b; Jacot et al., 2018; Cao and Gu,
2019b). Moreover both these algorithms require the inversion of a matrix of
size equal to the number of parameters in the model at each step of the
algorithm. Recently, Ban et al. (2022b) attained a regret bound independent of
$\tilde{d}$, but makes distributional assumptions on the context. (Qi et al.,
2022, 2023; Ban et al., 2021, 2022a) shows the successful application of
neural bandits on the recommender systems.

Overparameterized Models: Considerable progress has been made in understanding
the expressive power of Deep Neural Networks in the overparameterized regime
(Du et al., 2019; Allen-Zhu et al., 2019b, a; Cao and Gu, 2019b; Arora et al.,
2019a). It has been shown that the dynamics of the Neural Tangent Kernel
always stays close to random initialization when the network is wide enough
(Jacot et al., 2018; Arora et al., 2019b). Further Cao and Gu (2019b)
demonstrate that the loss function of neural network has the almost convexity
in the overparameterized regime while Liu et al. (2020, 2022); Frei and Gu
(2021); Charles and Papailiopoulos (2018) study neural models under Polyak-
Lojasiewicz (PL) Type conditions (Polyak, 1963; Lojasiewicz, 1963; Karimi et
al., 2016). Recently, Banerjee et al. (2023) provided a bound on the spectral
norm of the Hessian of the netowrk over a larger layerwise spectral norm
radius ball (in comparison to the radius in Liu et al. (2020)) and show
geometric convergence in deep learning optimization using restricted strong
convexity. Our regret analysis makes use of these recent advances in deep
learning.

##  6 Experiments

We evaluate the performance of $\mathsf{NeuSquareCB}$ and
$\mathsf{NeuFastCB}$, without output perturbation against some popular NeuCB
algorithms. We include a discussion on the effect of output perturbation in
Appendix F.

Figure 1: Comparison of cumulative regret of $\mathsf{NeuSquareCB}$ and
$\mathsf{NeuFastCB}$ with baselines on openml datasets (averaged over 20
runs).

Baselines. We choose four neural bandit algorithms: (1) NeuralUCB (Zhou et
al., 2020) maintains a confidence bound at every step using the gradients of
the network and selects the most optimistic arm. (2) NeuralTS (Neural Thompson
Sampling) (Zhang et al., 2021) estimates the rewards by drawing them from a
normal distribution whose mean is the output of the neural network and the
variance is a quadratic form of the gradients of the network. The arm with the
maximum sampled reward from this distribution is selected. (3) EE-Net (Ban et
al., 2022b): In addition to employing an Exploitation network for learning the
output function, it uses another Exploration network to learn the potential
gain of exploring in relation to the current estimated reward. (4)
NeuralEpsilon employs the $\epsilon$-greedy strategy: with probability
$1-\epsilon$ it chooses the arm with the maximum estimated reward generated by
the network and with probability $\epsilon$ it chooses a random arm.

Datasets. We consider a collection of 6 multiclass classification based
datasets from the $\mathtt{openml.org}$ platform: covertype, fashion,
MagicTelescope, mushroom, Plants and shuttle. Following the evaluation setting
of existing works (Zhou et al., 2020; Ban et al., 2022b), given an input
$\mathbf{x}_{t}\in\mathbb{R}^{d}$ for a $K$-class classification problem, we
transform it into $dK$ dimensional context vectors for each arm:
$\mathbf{x}_{t,1}=(\mathbf{x}_{t},\mathbf{0},\mathbf{0},\ldots,\mathbf{0})^{T}$,
$\mathbf{x}_{t,2}=(\mathbf{0},\mathbf{x}_{t},\mathbf{0},\ldots,\mathbf{0})^{T}),\ldots,\mathbf{x}_{t,K}=(\mathbf{0},\mathbf{0},\ldots,\mathbf{0},\mathbf{x}_{t})^{T}$.
The reward is defined as $1$ if the index of selected arm equals
$\mathbf{x}$’s ground-truth class; otherwise, the reward is $0$.

Architecture: Both $\mathsf{NeuSquareCB}$ and $\mathsf{NeuFastCB}$ use a
2-layered ReLu network with 100 hidden neurons. The last layer in
$\mathtt{NeuRIG}$ uses a linear activation while $\mathsf{NeuFastCB}$ uses a
sigmoid. Following the scheme in Zhou et al. (2020) and Zhang et al. (2021) we
use a diagonal matrix approximation in both NeuralUCB and NeuralTS to save
computation cost in matrix inversion. Both use a 2-layered ReLu network with
100 hidden neurons and the last layer uses a linear activation. We perform a
grid-search over the regularization parameter $\lambda$ over $(1,0.1,0.01)$
and the exploration parameter $\nu$ over $(0.1,0.01,0.001)$. NeuralEpsilon
uses the same neural architecture and the exploration parameter $\epsilon$ is
searched over $(0.1,0.05,0.01)$. For EE-Net we use the architecture from
https://github.com/banyikun/EE-Net-ICLR-2022. For all the algorithms we also
do a grid-search for the step-size over $(0.01,0.005,0.001)$.

Adversarial Contexts. In order to evaluate the performance of the algorithms
on adversarially chosen contexts, we feed data points to each of the model in
the following manner: for the first 500 rounds, an instance $\mathbf{x}$ is
uniformly sampled from each of the classes, transformed into context vectors
as described above and presented to the model. We calculate the accuracy for
each class by recording the rewards of this class divided by the number of
instances drawn from this class. In the subsequent 500 rounds, we increase the
probability of sampling instances from the class which had the least accuracy
in the previous rounds. We repeat this procedure every 500 rounds.

Results. Figure 1 plots the cumulative regret of all the algorithms across
different rounds. All experiments were averaged across 20 rounds and the
standard deviation is plotted along with the average performance. Although all
the algorithms use a neural network to model the potential non-linearity in
the reward, the baseline algorithms show erratic performance with a lot of
variance. Both our algorithms $\mathsf{NeuSquareCB}$ and $\mathsf{NeuFastCB}$
show consistent performance across all the datasets. Moreover,
$\mathsf{NeuFastCB}$ persistently outperforms all baselines for all the
datasets.

##  7 Conclusion

In this work, we develop novel regret bounds for online regression with neural
networks and subsequently give regret guarantees for NeuCBs. We provide a
sharp ${\cal O}(\log T)$ regret for online regression when the loss satisfies
almost convexity, QG condition, and has unique minima. We then propose a
network with a small random perturbation, and show that surprisingly this
makes the neural losses satisfy all three conditions. Using these results we
obtain ${\cal O}(\log T)$ regret bound with both square loss and KL loss and
thereafter, convert these bounds to regret bounds for NeuCBs. Separately, our
lower bound results for two popular NeuCB algorithms, namely Neural UCB(Zhou
et al., 2020) and Neural TS(Zhang et al., 2021) show that even an oblivious
adversary can choose a sequence of contexts and a reward function that makes
their regret bounds $\Omega(T)$. Our algorithms in contrast guarantee ${\cal
O}(\sqrt{T})$ regret, are efficient to implement (no matrix inversions as in
NeuralUCB and NeuralTS), work even for contexts drawn by an adaptive adversary
and does not need to store previous networks (unlike (Ban et al., 2022b)).
Additionally, our experimental comparisons with the baselines on various
datasets further highlight the advantages of our methods and therefore
significantly advances the state of the art in NeuCBs from both theoretical
and empirical perspectives.

#### Acknowledgements.

The work was supported in part by the National Science Foundation (NSF)
through awards IIS 21-31335, OAC 21-30835, DBI 20-21898, as well as a C3.ai
research award.

## 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.
  * Abe and Long [1999] N. Abe and P. M. Long.  Associative reinforcement learning using linear probabilistic concepts.  In _ICML_ , pages 3–11. Citeseer, 1999.
  * Abe et al. [2003] N. Abe, A. W. Biermann, and P. M. Long.  Reinforcement learning with immediate rewards and linear hypotheses.  _Algorithmica_ , 37(4):263–293, 2003.
  * Agrawal and Goyal [2013] S. Agrawal and N. Goyal.  Thompson sampling for contextual bandits with linear payoffs.  In _International conference on machine learning_ , pages 127–135. PMLR, 2013.
  * Allen-Zhu et al. [2019a] Z. Allen-Zhu, Y. Li, and Y. Liang.  Learning and generalization in overparameterized neural networks, going beyond two layers.  _Advances in neural information processing systems_ , 32, 2019a.
  * Allen-Zhu et al. [2019b] Z. Allen-Zhu, Y. Li, and Z. Song.  A convergence theory for deep learning via over-parameterization.  In _International Conference on Machine Learning_ , pages 242–252. PMLR, 2019b.
  * Arora et al. [2019a] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pages 322–332. PMLR, 2019a.
  * Arora et al. [2019b] 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, 2019b.
  * Azoury and Warmuth [2001] K. S. Azoury and M. K. Warmuth.  Relative loss bounds for on-line density estimation with the exponential family of distributions.  _Mach. Learn._ , 43(3):211–246, jun 2001.  ISSN 0885-6125.  doi: 10.1023/A:1010896012157.  URL https://doi.org/10.1023/A:1010896012157.
  * Ban and He [2020] Y. Ban and J. He.  Generic outlier detection in multi-armed bandit.  In _Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 913–923, 2020.
  * Ban and He [2021] Y. Ban and J. He.  Local clustering in contextual multi-armed bandits.  In _Proceedings of the Web Conference 2021_ , pages 2335–2346, 2021\.
  * Ban et al. [2021] Y. Ban, J. He, and C. B. Cook.  Multi-facet contextual bandits: A neural network perspective.  In _Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, pages 35–45, 2021.
  * Ban et al. [2022a] Y. Ban, Y. Qi, T. Wei, and J. He.  Neural collaborative filtering bandits via meta learning.  _arXiv preprint arXiv:2201.13395_ , 2022a.
  * Ban et al. [2022b] Y. Ban, Y. Yan, A. Banerjee, and J. He.  EE-net: Exploitation-exploration neural networks in contextual bandits.  In _International Conference on Learning Representations_ , 2022b.  URL https://openreview.net/forum?id=X_ch3VrNSRg.
  * Banerjee et al. [2023] A. Banerjee, P. Cisneros-Velarde, L. Zhu, and M. Belkin.  Restricted strong convexity of deep learning models with smooth activations.  In _The Eleventh International Conference on Learning Representations_ , 2023.  URL https://openreview.net/forum?id=PINRbk7h01.
  * Cao and Gu [2019a] Y. Cao and Q. Gu.  Generalization error bounds of gradient descent for learning over-parameterized deep relu networks.  In _AAAI Conference on Artificial Intelligence_ , 2019a.
  * Cao and Gu [2019b] Y. Cao and Q. Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  _Advances in neural information processing systems_ , 32, 2019b.
  * Charles and Papailiopoulos [2018] Z. Charles and D. Papailiopoulos.  Stability and generalization of learning algorithms that converge to global optima.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 745–754. PMLR, 10–15 Jul 2018.
  * Chen et al. [2021] X. Chen, E. Minasyan, J. D. Lee, and E. Hazan.  Provable regret bounds for deep online learning and control.  _arXiv preprint arXiv:2110.07807_ , 2021.
  * 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.
  * Du et al. [2019] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai.  Gradient descent finds global minima of deep neural networks.  In _International conference on machine learning_ , pages 1675–1685. PMLR, 2019.
  * Foster and Rakhlin [2020] D. Foster and A. Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * Foster and Krishnamurthy [2021] D. J. Foster and A. Krishnamurthy.  Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Frei and Gu [2021] S. Frei and Q. Gu.  Proxy convexity: A unified framework for the analysis of neural networks trained by gradient descent.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.  URL https://openreview.net/forum?id=NVpGLJUuPx5.
  * Hazan [2021] E. Hazan.  Introduction to online convex optimization, 2021.
  * Honorio and Jaakkola [2014] J. Honorio and T. Jaakkola.  Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sample Guarantees.  In S. Kaski and J. Corander, editors, _Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics_ , volume 33 of _Proceedings of Machine Learning Research_ , pages 384–392, Reykjavik, Iceland, 22–25 Apr 2014. PMLR.  URL https://proceedings.mlr.press/v33/honorio14.html.
  * Jacot et al. [2018] A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: Convergence and generalization in neural networks.  _Advances in neural information processing systems_ , 31, 2018.
  * Karimi et al. [2016] H. Karimi, J. Nutini, and M. Schmidt.  Linear convergence of gradient and proximal-gradient methods under the Polyak-lojasiewicz condition.  In _Joint European conference on machine learning and knowledge discovery in databases_ , pages 795–811. Springer, 2016.
  * 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.
  * Liu et al. [2022] C. Liu, L. Zhu, and M. Belkin.  Loss landscapes and optimization in over-parameterized non-linear systems and neural networks.  _Applied and Computational Harmonic Analysis_ , 59:85–116, 2022.
  * Lojasiewicz [1963] S. Lojasiewicz.  A topological property of real analytic subsets (in french).  In _Les équations aux dérivées partielles_ , pages 87–89. Coll. du CNRS, 1963.
  * Lu and Van Roy [2017] X. Lu and B. Van Roy.  Ensemble sampling.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 3260–3268, Red Hook, NY, USA, 2017. Curran Associates Inc.  ISBN 9781510860964.
  * Polyak [1963] B. Polyak.  Gradient methods for the minimisation of functionals.  _USSR Computational Mathematics and Mathematical Physics_ , 3(4):864–878, 1963.  ISSN 0041-5553.  doi: https://doi.org/10.1016/0041-5553(63)90382-3.  URL https://www.sciencedirect.com/science/article/pii/0041555363903823.
  * Qi et al. [2022] Y. Qi, Y. Ban, and J. He.  Neural bandit with arm group graph.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 1379–1389, 2022.
  * Qi et al. [2023] Y. Qi, Y. Ban, and J. He.  Graph neural bandits.  In _Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 1920–1931, 2023.
  * Riquelme et al. [2018] C. Riquelme, G. Tucker, and J. Snoek.  Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=SyYe6k-CW.
  * Sason [2015] I. Sason.  On reverse pinsker inequalities, 2015.
  * Shalev-Shwartz [2012] S. Shalev-Shwartz.  Online learning and online convex optimization.  _Foundations and Trends® in Machine Learning_ , 4(2):107–194, 2012.  ISSN 1935-8237.  doi: 10.1561/2200000018.  URL http://dx.doi.org/10.1561/2200000018.
  * Simchi-Levi and Xu [2020] D. Simchi-Levi and Y. Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  _ArXiv_ , abs/2003.12699, 2020.
  * 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.
  * Vershynin [2011] R. Vershynin.  Introduction to the non-asymptotic analysis of random matrices, 2011.
  * Zahavy and Mannor [2020] T. Zahavy and S. Mannor.  Neural linear bandits: Overcoming catastrophic forgetting through likelihood matching, 2020.  URL https://openreview.net/forum?id=r1gzdhEKvH.
  * Zhang et al. [2021] W. Zhang, D. Zhou, L. Li, and Q. Gu.  Neural thompson sampling.  In _International Conference on Learning Representation (ICLR)_ , 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 A Comparison with recent Neural Contextual Bandit Algorithms

In this section we show that the regret bounds for NeuralUCB [Zhou et al.,
2020] and Neural Thompson Sampling (NeuralTS) [Zhang et al., 2021] is
$\Omega(T)$ in the worst case. We start with a brief description of the
notations used in these works. $\mathbf{H}$ is the Neural Tangent Kernel (NTK)
matrix computed from all the context vectors $\mathbf{x}_{t,i}$,
$t\in[T],i\in[K]$, and $h(\mathbf{x})$ is the true reward function given a
context $\mathbf{x}$. The cumulative reward vector is defined as
$\mathbf{h}=(h(\mathbf{x}_{1}),\ldots,h(\mathbf{x}_{TK}))^{\top}$.

With $\lambda$ as the regularization parameter in the loss, the effective
dimension $\tilde{d}$ of the Neural Tangent Kernel $\mathbf{H}$ on the
contexts $\\{\mathbf{x}_{t}\\}_{t=1}^{TK}$ is defined as:

$\displaystyle\tilde{d}=\frac{\log\det(\mathbf{I}+\mathbf{H}/\lambda)}{\log(1+T/\lambda)}$

Further it is assumed that $\mathbf{H}\succeq\lambda_{0}\mathbb{I}$ (see
Assumption 4.2 in [Zhou et al., 2020] and Assumption 3.4 in [Zhang et al.,
2021]).

###  A.1 $\Omega(T)$ regret for NeuralUCB

The bound on the regret for NeuralUCB [Zhou et al., 2020] is given by
(ignoring constants):

$\displaystyle\operatorname{\text{Reg${}_{\text{CB}}$}}(T)$
$\displaystyle\leq\sqrt{T}\sqrt{\tilde{d}\log\left(1+\frac{TK}{\lambda}\right)}\left(\sqrt{\tilde{d}\log\left(1+\frac{TK}{\lambda}\right)}+\sqrt{\lambda}S\right)$
$\displaystyle=\sqrt{T}\left(\tilde{d}\log\left(1+\frac{TK}{\lambda}\right)+S\sqrt{\tilde{d}\log\left(1+\frac{TK}{\lambda}\right)\lambda}\right)\mathrel{\mathop{:}}=\text{B}_{\text{NUCB}}(T,\lambda),$

where, $\lambda$ is the regularization constant and
$S\geq\sqrt{\mathbf{h}^{T}H^{-1}\mathbf{h}}$ with
$\mathbf{h}=(h(\mathbf{x}_{1}),\ldots,h(\mathbf{x}_{TK}))^{T}$. We provide two
$\Omega(T)$ regret bounds for NeuralUCB.

The first result creates an instance that an oblivious adversary can choose
before the algorithm begins such that the regret bound is $\Omega(T)$. The
second result provides an $\Omega(T)$ bound for any reward function and set of
context vectors as long as $\displaystyle\frac{\kappa}{\|\mathbf{h}\|}$ is
$\Theta(1)$.

######  Theorem A.1.

There exists a reward vector $\mathbf{h}$ such that the regret bound for
NeuralUCB is lower bounded as

$\emph{$\text{B}_{\text{NUCB}}$}(\lambda,T)\geq\displaystyle\frac{1}{\sqrt{2}}\sqrt{K}T.$

###### Proof.

Consider the eigen-decomposition of $\mathbf{H}=U\Sigma_{\mathbf{H}}U^{T}$,
where columns of $U\in\mathbb{R}^{TK\times TK}$ are the normalized eigen-
vectors $\\{u_{i}\\}_{i=1}^{TK}$ of $\mathbf{H}$ and $\Sigma_{\mathbf{H}}$ is
a diagonal matrix containing the eigenvalues
$\\{\lambda_{i}(\mathbf{H})\\}_{i=1}^{TK}$ of $H$. Now,

$\displaystyle S$
$\displaystyle\geq\sqrt{\mathbf{h}^{T}\mathbf{H}^{-1}\mathbf{h}}=\sqrt{\mathbf{h}^{T}U\Sigma_{\mathbf{H}}^{-1}U^{T}\mathbf{h}}=\sqrt{\sum_{i=1}^{TK}\frac{1}{\lambda_{i}(\mathbf{H})}(u_{i}^{T}h)^{2}}\geq\xi\sqrt{\sum_{i=1}^{TK}\frac{1}{\lambda_{i}(\mathbf{H})}},$
(18) $\displaystyle\qquad\qquad\qquad\qquad\qquad\text{where
}\xi=\min_{i}(u_{i}^{T}\mathbf{h})$

Further observe that we can rewrite the effective dimension as follows:

$\displaystyle\tilde{d}=\frac{\log\det(\mathbf{I}+\mathbf{H}/\lambda)}{\log(1+TK/\lambda)}=\frac{\log\left(\displaystyle\prod_{i=1}^{TK}\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)\right)}{\log(1+TK/\lambda)}=\frac{\displaystyle\sum_{i=1}^{TK}\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}{\log(1+{TK}/{\lambda})}$

Using these we can lower bound $\text{B}_{\text{NUCB}}(T,\lambda)$ as follows:

$\displaystyle\text{B}_{\text{NUCB}}(T,\lambda)$
$\displaystyle\geq\sqrt{T}\Bigg{(}\sum_{i=1}^{TK}\frac{\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}{\log\left(1+\frac{TK}{\lambda}\right)}\log\left(1+\frac{TK}{\lambda}\right)$
$\displaystyle\qquad\qquad+\xi\sqrt{\sum_{i=1}^{TK}\frac{\lambda}{\lambda_{i}(\mathbf{H})}\sum_{i=1}^{TK}\frac{\log(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda})}{\log\left(1+\frac{TK}{\lambda}\right)}\log\left(1+\frac{TK}{\lambda}\right)}\Bigg{)}$
$\displaystyle=\sqrt{T}\left(\sum_{i=1}^{TK}{\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}+\xi\sqrt{\sum_{i=1}^{TK}\frac{\lambda}{\lambda_{i}(\mathbf{H})}\sum_{i=1}^{TK}{\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}}\right)$
$\displaystyle\geq\sqrt{T}\left(\sum_{i=1}^{TK}{\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}+\xi\sqrt{\sum_{i=1}^{TK}\frac{\lambda}{\lambda_{i}(\mathbf{H})}{\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}}\right)$
$\displaystyle=\sqrt{T}\left(\sum_{i=1}^{TK}{\log\left(1+\frac{1}{y_{i}}\right)}+\xi\sqrt{\sum_{i=1}^{TK}y_{i}{\log\left(1+\frac{1}{y_{i}}\right)}}\right),$

where $y_{i}=\frac{\lambda}{\lambda_{i}(\mathbf{H})}$, $i\in[TK]$. Using this
we can further bound $\text{B}_{\text{NUCB}}(T,\lambda)$ as follows:

$\displaystyle\text{B}_{\text{NUCB}}(T,\lambda)$
$\displaystyle\geq\sqrt{T}\left(\sum_{i=1}^{TK}{\log\left(1+\frac{1}{y_{i}}\right)}+\frac{\xi}{\sqrt{TK}}\sum_{i=1}^{TK}\sqrt{y_{i}{\log\left(1+\frac{1}{y_{i}}\right)}}\right)$
$\displaystyle\geq\frac{1}{\sqrt{K}}\left(\sum_{i=1}^{TK}{\log\left(1+\frac{1}{y_{i}}\right)}+{\xi}{y_{i}{\log\left(1+\frac{1}{y_{i}}\right)}}\right)$
$\displaystyle\geq\frac{1}{\sqrt{K}}\left(\sum_{i=1}^{TK}\log\left(1+\frac{1}{y_{i}}\right)\big{(}1+\xi
y_{i}\big{)}\right)$
$\displaystyle\geq\frac{1}{\sqrt{K}}\left(\sum_{i=1}^{TK}\frac{\frac{1}{y_{i}}}{1+\frac{1}{y_{i}}}\big{(}1+\xi
y_{i}\big{)}\right)$
$\displaystyle=\frac{1}{\sqrt{K}}\left(\sum_{i=1}^{TK}\frac{1+\xi
y_{i}}{1+y_{i}}\right)$ $\displaystyle\geq T\sqrt{K}{\xi}.$

Recall that $\xi=\underset{i}{\min}(u_{i}^{T}\mathbf{h})^{2}$. Now, consider
an $\mathbf{h}$ that makes a $\pi/4$ angle with all the eigen-vectors $u_{i}$,
$i\in[TK]$ and therefore $\xi=\frac{1}{\sqrt{2}}$. Note that for the positive
definite assumption of NTK to hold, all the contexts need to be distinct and
therefore an oblivious adversary can always choose such an $h$. In such a
case, the regret bound for NeuralUCB is
$\text{B}_{\text{NUCB}}(T,\lambda)=\Omega(T)$. ∎

######  Remark A.1.

Note that the $\Omega(T)$ regret holds for any $\mathbf{h}$ whose dot product
with all the eigen vectors of $\mathbf{H}$ is lower bounded by a constant.

######  Theorem A.2.

For any cumulative reward vector $\mathbf{h}$, with $\kappa$ as the condition
number of the NTK matrix, the regret bound for NeuralUCB is

$\emph{$\text{B}_{\text{NUCB}}$}(\lambda,T)\geq\displaystyle\frac{\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}\sqrt{K}T.$

###### Proof.

Using the same notation as in the previous section, we can lower bound $S$ and
$\tilde{d}$ as follows:

$\displaystyle S$
$\displaystyle\geq\sqrt{\lambda_{\min}(\mathbf{H}^{-1})\|\mathbf{h}\|_{2}^{2}}=\frac{1}{\sqrt{\lambda_{\max}(\mathbf{H})}}\|\mathbf{h}\|_{2}$
$\displaystyle\tilde{d}=\frac{\log\det(\mathbf{I}+\mathbf{H}/\lambda)}{\log(1+TK/\lambda)}$
$\displaystyle\geq\frac{\log\left(\lambda_{\min}\left(\mathbf{I}+\mathbf{H}/\lambda\right)^{TK}\right)}{\log\left(1+TK/\lambda\right)}\geq
TK\frac{\log(1+\frac{\lambda_{0}}{\lambda})}{\log\left(1+\frac{TK}{\lambda}\right)}$

Using these we can lower bound $\text{B}_{\text{NUCB}}(T,\lambda)$ as follows:

$\displaystyle\text{B}_{\text{NUCB}}(T,\lambda)$
$\displaystyle\geq\sqrt{T}\Bigg{(}TK\frac{\log(1+\frac{\lambda_{0}}{\lambda})}{\log\left(1+\frac{TK}{\lambda}\right)}\log\left(1+\frac{TK}{\lambda}\right)$
$\displaystyle\qquad\qquad+\|\mathbf{h}\|_{2}\sqrt{TK\frac{\lambda}{\lambda_{\max}(H)}\frac{\log(1+\frac{\lambda_{0}}{\lambda})}{\log\left(1+\frac{TK}{\lambda}\right)}\log\left(1+\frac{TK}{\lambda}\right)}\Bigg{)}$
$\displaystyle=T\sqrt{K}\left(\sqrt{TK}\log\left(1+\frac{\lambda_{0}}{\lambda}\right)+\frac{\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}\sqrt{\frac{\lambda}{\lambda_{0}}\log\left(1+\frac{\lambda_{0}}{\lambda}\right)}\right)$
$\displaystyle=T\sqrt{K}\left(\sqrt{TK}\log\left(1+\frac{1}{y}\right)+\frac{\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}\sqrt{y\log\left(1+\frac{1}{y}\right)}\right),$

where $y=\frac{\lambda}{\lambda_{0}}$ and
$\kappa=\frac{\lambda_{\max(H)}}{\lambda_{\min}(H)}$ is the condition number
of of the NTK. Since $y\log(1+\frac{1}{y})\leq 1$ and for $T,K\geq 1$, we have

$\displaystyle\text{B}_{\text{NUCB}}(T,\lambda)$ $\displaystyle\geq
T\sqrt{K}\left(\log\left(1+\frac{1}{y}\right)\left(1+\frac{y\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}\right)\right)$
(19) $\displaystyle\geq
T\sqrt{K}\left(\frac{1+\frac{\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}y}{1+y}\right)$
(20) $\displaystyle\geq T\sqrt{K}\frac{\|\mathbf{h}\|_{2}}{\sqrt{\kappa}}$
(21)

If $\displaystyle\frac{\kappa}{\|\mathbf{h}\|}$ is $\Theta(1)$ then
$\text{B}_{\text{NUCB}}(T,\lambda)$ is $\Omega(T)$. ∎

###  A.2 $\Omega(T)$ regret for Neural Thompson Sampling

The bound on the regret for Neural Thompson sampling [Zhang et al., 2021] is
given by (ignoring constants):

$\displaystyle\operatorname{\text{Reg${}_{\text{CB}}$}}(T)$
$\displaystyle\leq\sqrt{T}(1+\sqrt{\log T+\log
K})\left(S+\sqrt{\tilde{d}\log(1+TK/\lambda)}\right)\sqrt{\lambda\tilde{d}\log(1+TK)}$
$\displaystyle:=B(T)$

We present two lower bounds on $\text{B}_{\text{NTS}}(T)$ below. As in
NeuralUCB, the first result creates an instance that an oblivious adversary
can choose before the algorithm begins such that the regret bound is
$\Omega(T)$ and the second result provides an $\Omega(T)$ bound for any reward
function and set of context vectors as long as $\lambda_{0}$ is $\Theta(1)$.

######  Theorem A.3.

There exists a reward vector $\mathbf{h}$ such that the regret bound for
NeuralUCB is lower bounded as

$\emph{$\text{B}_{\text{NUCB}}$}(\lambda,T)\geq\displaystyle\frac{1}{2\sqrt{2}}\sqrt{K}T.$

###### Proof.

For Neural Thompson sampling the regularization parameter $\lambda$ is chosen
to be $\lambda=1+1/T$ (see Theorem 3.5 in Zhang et al. [2021]) and therefore
$1\leq\lambda\leq 2$ for any $T\geq 1$. Therefore we can lower bound the
effective dimension as,

$\displaystyle\tilde{d}$
$\displaystyle=\frac{\log\det(\mathbf{I}+\mathbf{H}/\lambda)}{\log(1+TK/\lambda)}=\frac{\log\left(\displaystyle\prod_{i=1}^{TK}\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)\right)}{\log(1+TK/\lambda)}$
$\displaystyle=\frac{\displaystyle\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{\lambda}\right)}{\log(1+{TK}/{\lambda})}\geq\frac{\displaystyle\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{2}\right)}{\log(1+{TK})}$
$\displaystyle\text{B}_{\text{NTS}}(T)$
$\displaystyle\geq\sqrt{T}\left(\sqrt{\mathbf{h}^{T}\mathbf{H}^{-1}\mathbf{h}}\sqrt{\displaystyle\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{2}\right)}+\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{2}\right)\right)$
$\displaystyle\geq\sqrt{T}\left(\xi\sqrt{\sum_{i=1}^{TK}\frac{1}{\lambda_{i}(\mathbf{H})}\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{2}\right)}+\sum_{i=1}^{TK}\log\left(1+\frac{\lambda_{i}(\mathbf{H})}{2}\right)\right)$

where recall from $\eqref{eq:S_lower}$ that

$\displaystyle S$
$\displaystyle\geq\xi\sqrt{\sum_{i=1}^{TK}\frac{1}{\lambda_{i}(\mathbf{H})}},$
$\displaystyle\text{where }\xi=\min_{i}(u_{i}^{T}\mathbf{h})$

Therefore

$\displaystyle\text{B}_{\text{NTS}}(T)$
$\displaystyle\geq\sqrt{T}\left(\xi\sqrt{\sum_{i=1}^{TK}y_{i}\log\left(1+\frac{1}{2y_{i}}\right)}+\sum_{i=1}^{TK}\log\left(1+\frac{1}{2y_{i}}\right)\right)$
$\displaystyle\geq\sqrt{T}\left(\xi\frac{1}{\sqrt{TK}}\sum_{i=1}^{TK}\sqrt{y_{i}\log\left(1+\frac{1}{2y_{i}}\right)}+\sum_{i=1}^{TK}\log\left(1+\frac{1}{2y_{i}}\right)\right)$
$\displaystyle\geq\sqrt{T}\left(\frac{1}{\sqrt{TK}}\sum_{i=1}^{TK}\xi
y_{i}\log\left(1+\frac{1}{2y_{i}}\right)+\log\left(1+\frac{1}{2y_{i}}\right)\right)$
$\displaystyle=\sqrt{T}\left(\frac{1}{\sqrt{TK}}\sum_{i=1}^{TK}\log\left(1+\frac{1}{2y_{i}}\right)(1+\xi
y_{i})\right)$
$\displaystyle\geq\sqrt{T}\left(\frac{1}{\sqrt{TK}}\sum_{i=1}^{TK}\frac{1/2y_{i}}{1+1/2y_{i}}(1+\xi
y_{i})\right)$
$\displaystyle=\sqrt{T}\left(\frac{1}{\sqrt{TK}}\sum_{i=1}^{TK}\frac{1+\xi
y_{i}}{1+2y_{i}}\right)$
$\displaystyle\geq\sqrt{T}\frac{1}{\sqrt{TK}}TK\frac{\xi}{2}$
$\displaystyle=T\sqrt{K}\frac{\xi}{2}.$

As in the proof of Theorem A.1, for $\mathbf{h}$ making an angle of $\pi/4$
with all eigen-vectors of $\mathbf{H}$, $\xi\geq\frac{1}{\sqrt{2}}$, which
proves the claim.

######  Theorem A.4.

For any cumulative reward vector $\mathbf{h}$, the regret bound for Neural
Thompson sampling is

$\emph{$\text{B}_{\text{NTS}}$}(\lambda,T)\geq
T\sqrt{T}K\frac{\lambda_{0}}{2+\lambda_{0}}$

Recall, $1\leq\lambda\leq 2$ for any $T\geq 1$, and therefore we can lower
bound the effective dimension as,

$\displaystyle\tilde{d}=\frac{\log\det(I+\mathbf{H}/\lambda)}{\log(1+TK/\lambda)}\geq\displaystyle
TK\frac{\log(1+{\lambda_{0}}/{\lambda})}{\log(1+TK/\lambda)}\geq
TK\frac{\log(1+{\lambda_{0}}/{\lambda})}{\log(1+TK)}$

Therefore, using $1\leq\lambda\leq 2$ and
$S\geq\sqrt{\mathbf{h}^{T}\mathbf{H}^{-1}\mathbf{h}}$,

$\displaystyle\text{B}_{\text{NTS}}(T)$
$\displaystyle\geq\sqrt{T}\left(\sqrt{\mathbf{h}^{T}\mathbf{H}^{-1}\mathbf{h}}+\sqrt{TK\log(1+\lambda_{0}/2)}\right)\sqrt{TK\log(1+\lambda_{0}/2)}$
$\displaystyle\geq T\sqrt{T}K\log(1+\lambda_{0}/2)$ $\displaystyle\geq
T\sqrt{T}K\frac{\lambda_{0}/2}{1+\lambda_{0}/2}$ $\displaystyle\geq
T\sqrt{T}K\frac{\lambda_{0}}{2+\lambda_{0}}$

If $\lambda_{0}=\Theta(1)$, $\text{B}_{\text{NTS}}(T)$ is $\Omega(T)$.

∎

##  Appendix B Background and Preliminaries for Technical Analysis

Before we proceed with the proof of the claims in Section 3, we state a few
recent results from Banerjee et al. [2023] that we will use throughout our
proofs. We assume the loss to be the squared loss throughout this subsection.

######  Lemma 1 (Hessian Spectral Norm Bound, Theorem 4.1 and Lemma 4.1 in
Banerjee et al. [2023] ).

Under Assumptions 3 and 4, for any $\mathbf{x}\in{\cal X}$, $\theta\in
B_{\rho,\rho_{1}}^{\operatorname{Spec}}(\theta_{0})$, with probability at
least $(1-\frac{2(L+1)}{m})$, we have

$\left\lVert\nabla^{2}_{\theta}f(\theta;\mathbf{x})\right\rVert_{2}\leq\frac{c_{H}}{\sqrt{m}}\quad\text{and}\quad\|\nabla_{\theta}f(\theta;\mathbf{x})\|_{2}\leq\varrho\leavevmode\nobreak\
,$ (22)

where,

$\displaystyle
c_{H}=L(L^{2}\gamma^{2L}+L\gamma^{L}+1)\cdot(1+\rho_{1})\cdot\psi_{H}\cdot\max_{l\in[L]}\gamma^{L-l}+L\gamma^{L}\max_{l\in[L]}h(l)\leavevmode\nobreak\
,$ $\displaystyle\gamma=\sigma_{1}+\frac{\rho}{\sqrt{m}},\quad
h(l)=\gamma^{l-1}+|\phi(0)|\sum^{l-1}_{i=1}\gamma^{i-1},$
$\displaystyle\psi_{H}=\max_{1\leq l_{1}<l_{2}\leq
L}\left\\{\beta_{\phi}h(l_{1})^{2}\leavevmode\nobreak\ ,\leavevmode\nobreak\
h(l_{1})\left(\frac{\beta_{\phi}}{2}(\gamma^{2}+h(l_{2})^{2})+1\right)\leavevmode\nobreak\
,\leavevmode\nobreak\
\beta_{\phi}\gamma^{2}h(l_{1})h(l_{2})\right\\}\leavevmode\nobreak\ ,$
$\displaystyle\varrho^{2}={(h(L+1))^{2}+\frac{1}{m}(1+\rho_{1})^{2}\sum_{l=1}^{L+1}(h(l))^{2}\gamma^{2(L-l)}}.$

######  Lemma 2 (Loss bounds, Lemma 4.2 in Banerjee et al. [2023]).

Under Assumptions 3 and 4, for $\gamma=\sigma_{1}+\frac{\rho}{\sqrt{m}}$, each
of the following inequalities hold with probability at least
$\left(1-\frac{2(L+1)}{m}\right)$: $\ell(\theta_{0})\leq c_{0,\sigma_{1}}$ and
$\ell(\theta)\leq c_{\rho_{1},\gamma}$ for $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, where
$c_{a,b}={2}\sum^{N}_{i=1}y_{i}^{2}+2(1+a)^{2}|g(b)|^{2}$ and
$g(a)=a^{L}+|\phi(0)|\sum^{L}_{i=1}a^{i}$ for any $a,b\in\mathbb{R}$.

######  Lemma 3 (Loss gradient bound, Corollary 4.1 in Banerjee et al.
[2023]).

Under Assumptions 3 and 4, for $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, with probability at
least $\left(1-\frac{2(L+1)}{m}\right)$, we have
$\|\nabla_{\theta}\ell(\theta)\|_{2}\leq 2\sqrt{\ell(\theta)}\varrho\leq
2\sqrt{c_{\rho_{1},\gamma}}\varrho$, with $\varrho$ as in Lemma 1 and
$c_{\rho_{1},\gamma}$ as in Lemma 2.

######  Lemma 4 (Local Smoothness, Theorem 5.2 in Banerjee et al. [2023]).

Under Assumptions 3 and 4, with probability at least $(1-\frac{2(L+1)}{m})$,
$\forall\theta,\theta^{\prime}\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$,

$\begin{split}\ell(\theta^{\prime})&\leq\ell(\theta)+\langle\theta^{\prime}-\theta,\nabla_{\theta}{\hat{\ell}}(\theta)\rangle+\frac{\beta}{2}\|\theta^{\prime}-\theta\|_{2}^{2}\leavevmode\nobreak\
,\quad\text{with}\quad\beta=b\varrho^{2}+\frac{c_{H}\sqrt{c_{\rho_{1},\gamma}}}{\sqrt{m}}\leavevmode\nobreak\
,\end{split}$ (23)

with $c_{H}$ as in Lemma 1, $\varrho$ as in Lemma 1, and $c_{\rho_{1},\gamma}$
as in Lemma 2. Consequently, ${\hat{\ell}}$ is locally $\beta$-smooth.

##  Appendix C Proof of Claims for Neural Online Regression (Section 3)

###  C.1 Regret Bound under QG condition (Proof of Theorem 3.1)

See 3.1

###### Proof.

Take any $\theta^{\prime}\in B$. By Assumption 2(a) (almost convexity) we have

$\displaystyle\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))$
$\displaystyle\leq\langle\theta_{t}-\theta^{\prime},\nabla\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))\rangle+\epsilon$

Note that for any $\theta\in B$, we have

$\Bigg{\|}\prod_{B}(\theta^{\prime\prime})-\theta\Bigg{\|}_{2}\leq\|\theta^{\prime\prime}-\theta\|_{2}.$

As a result, for $\theta^{\prime}\in B$, we have

$\displaystyle\|\theta_{t+1}-\theta^{\prime}\|_{2}^{2}-\|\theta_{t}-\theta^{\prime}\|_{2}^{2}$
$\displaystyle\leq\|\theta_{t}-\eta_{t}\nabla\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\theta^{\prime}\|_{2}^{2}-\|\theta_{t}-\theta^{\prime}\|_{2}^{2}$
$\displaystyle=-2\eta_{t}\langle\theta_{t}-\theta^{\prime},\nabla\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))\rangle+\eta_{t}^{2}\big{\|}\nabla\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))\big{\|}_{2}^{2}$
$\displaystyle\leq-2\eta_{t}\left(\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))-\epsilon\right)+\eta_{t}^{2}\lambda^{2}\varrho^{2}\leavevmode\nobreak\
.$

Rearranging sides and dividing by $2\eta_{t}$ we get

$\displaystyle\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))\leq\frac{\|\theta_{t}-\theta^{\prime}\|_{2}^{2}-\|\theta_{t+1}-\theta^{\prime}\|_{2}^{2}}{2\eta_{t}}+\frac{\eta_{t}}{2}\lambda^{2}\varrho^{2}+\epsilon\leavevmode\nobreak\
.$ (24)

Let $\eta_{t}=\frac{4}{\mu t}$. Then, summing eq. 24 over $t=1,\ldots,T$, we
have

$\displaystyle\text{R}(T)$
$\displaystyle=\sum_{t=1}^{T}\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}\|\theta_{t}-\theta^{\prime}\|_{2}^{2}\left(\frac{1}{2\eta_{t}}-\frac{1}{2\eta_{t-1}}\right)+\frac{\lambda^{2}\varrho^{2}}{2}\sum_{t=1}^{T}\eta_{t}+\epsilon$
$\displaystyle\leq\frac{\mu}{8}\sum_{t=1}^{T}\|\theta_{t}-\theta^{\prime}\|_{2}^{2}+{\cal
O}(\lambda^{2}\log T)+\frac{c_{0}T}{\sqrt{m}}$
$\displaystyle\leq\frac{\mu}{4}\sum_{t=1}^{T}\|\theta_{t}-\theta_{t}^{*}\|_{2}^{2}+\frac{\mu}{4}\sum_{t=1}^{T}\|\theta^{\prime}-\theta_{t}^{*}\|_{2}^{2}+{\cal
O}(\lambda^{2}\log T)+\epsilon$ (25)

where
$\theta^{*}_{t}\in\operatorname{arginf}_{\theta}\ell(y_{t},g(\theta;\mathbf{x}_{t}))$.
By Assumption 2(b), the loss satisfies the QG condition and by Assumption
2(c), it has unique minimizer, so that for $t\in[T]$

$\displaystyle\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t}))$
$\displaystyle\geq\frac{\mu}{2}\|\theta_{t}-\theta_{t}^{*}\|_{2}^{2}\leavevmode\nobreak\
,$ (26)
$\displaystyle\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t}))$
$\displaystyle\geq\frac{\mu}{2}\|\theta^{\prime}-\theta_{t}^{*}\|_{2}^{2}\leavevmode\nobreak\
.$ (27)

Then, we can lower bound the regret as

$\displaystyle\tilde{\text{R}}(T)$
$\displaystyle=\sum_{t=1}^{T}\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))$
$\displaystyle=\sum_{t=1}^{T}\left(\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t}))\right)-\sum_{t=1}^{T}(\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t})))$
$\displaystyle\geq\frac{\mu}{2}\sum_{t=1}^{T}\|\theta_{t}-\theta_{t}^{*}\|_{2}^{2}-\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))\leavevmode\nobreak\
,$ (28)

from eq. 26 Multiplying eq. 28 by $-\frac{1}{2}$ and adding to eq. 25, we get

$\displaystyle\frac{1}{2}\tilde{\text{R}}(T)$
$\displaystyle=\sum_{t=1}^{T}\ell(y_{t},g(\theta_{t};\mathbf{x}_{t}))-\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))$
$\displaystyle\leq\frac{\mu}{4}\sum_{t=1}^{T}\|\theta^{\prime}-\theta_{t}^{*}\|_{2}^{2}+{\cal
O}(\lambda^{2}\log T)+\epsilon
T+\frac{\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))}{2}$
$\displaystyle{\leq}\frac{1}{2}\sum_{t=1}^{T}(\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))-\ell(y_{t},g(\theta_{t}^{*};\mathbf{x}_{t})))+{\cal
O}(\lambda^{2}\log T)+\epsilon
T+\frac{\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))}{2}$
$\displaystyle{\leq}\sum_{t=1}^{T}\ell(y_{t},g(\theta^{\prime};\mathbf{x}_{t}))+{\cal
O}(\lambda^{2}\log T)+\epsilon T\leavevmode\nobreak\ .$

Since $\theta^{\prime}\in B$ was arbitrary, taking an infimum completes the
proof. ∎

###  C.2 Regret Bound for Square Loss (Proof of Theorem 3.2)

See 3.2

###### Proof.

The proof follows along the following four steps.

  1. 1.

Square loss is Lipschitz, strongly convex, and smooth w.r.t. the output:

This step ensures that Assumption 3 (lipschitz, strong convexity and
smoothness) is satisfied. We show that the loss function
$\ell_{\operatorname{\text{Sq}}}$ is lipschitz, strongly convex and smooth
with respect to the output $\tilde{f}(\theta;\mathbf{x},\bm{\varepsilon})$
inside $B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ with high
probability over the randomness of initialization and
$\\{\bm{\varepsilon}\\}_{s=1}^{S}$. We will denote
$\lambda_{\operatorname{\text{Sq}}},a_{\operatorname{\text{Sq}}}$ and
$b_{\operatorname{\text{Sq}}}$ as the lipschitz, strong convexity and
smoothness parameters respectively as defined in Assumption 3.

######  Lemma 5.

For $\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, with
probability $\left(1-\frac{2(L+1)+1}{m}\right)$ over the randomness of
initialization and $\\{\bm{\varepsilon}\\}_{s=1}^{S}$, the loss
$\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
is lipschitz, strongly convex and smooth with respect to its output
$\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon})$. Further the corresponding
parameters for square loss,
$\lambda_{\operatorname{\text{Sq}}},a_{\operatorname{\text{Sq}}}$ and
$b_{\operatorname{\text{Sq}}}$ are ${\cal O}(1)$.

Strong convexity and smoothness follow trivially from the definition of the
$\ell_{\operatorname{\text{Sq}}}$. To show that
$\ell_{\operatorname{\text{Sq}}}$ is Lipschitz we show that the output of the
neural network $\tilde{f}(\theta;\mathbf{x},\bm{\varepsilon})$ is bounded for
any $\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$. Also note
from Theorem 3.1 that $\lambda^{2}$ appears in the $\log T$ term and therefore
to obtain a ${\cal O}(\log T)$ regret we must ensure that
$\lambda_{\operatorname{\text{Sq}}}={\cal O}(1)$, which Lemma 5 does. Note
that using a union bound over $t\in[T]$ and Lemma 5 it follows that with
probability $\left(1-\frac{2(L+1)+1}{m}\right)$, ${\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
is also lipschitz, strongly convex and smooth with respect to each of the
outputs $\tilde{f}\big{(}\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}),s\in[S]$.

  2. 2.

The average loss in eq. 13 is almost convex and has a unique minimizer:

We show that with $S=\Theta(\log m),$ the average loss in eq. 13 is $\nu$ \-
Strongly Convex (SC) with $\nu={\cal O}\left(\frac{1}{\sqrt{m}}\right)$ w.r.t.
$\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, $\forall
t\in[T]$ which immediately implies Assumption 2(a) (almost convexity) and 2(c)
(unique minima).

######  Lemma 6.

Under Assumption 5 and
$c_{p}=\sqrt{8\lambda_{\operatorname{\text{Sq}}}C_{H}}$, with probability
$\left(1-\frac{2T(L+2)}{m}\right)$ over the randomness of the initialization
and $\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$, ${\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
is $\nu$-strongly convex with respect to $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, where
$\nu=\mathcal{O}\left(\frac{1}{\sqrt{m}}\right).$

  3. 3.

The average loss in eq. 13 satisfies the QG condition:

It is known that square loss with wide networks under Assumption 5 (positive
definite NTK) satisfies the PL condition (eg. Liu et al. [2022]) with
$\mu={\cal O}(1)$. We show that the average loss in eq. 13 with $S=\Theta(\log
m),$ also satisfies the PL condition with $\mu={\cal O}(1)$, which implies
that it satisfies the QG condition with same $\mu$ with high probability over
the randomness of initialization $\bm{\varepsilon}_{s}$.

######  Lemma 7.

Under Assumption 5 with probability $\big{(}1-\frac{2T(L+1)C}{m}\big{)}$, for
some absolute constant $C>0$, ${\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
satisfies the QG condition over the randomness of the initialization and
$\\{\varepsilon_{s}\\}_{s=1}^{S}$, with QG constant $\mu={\cal O}(1)$.

  4. 4.

Bounding the final regret.

Steps 1 and 2 above surprisingly show that with a small output perturbation,
square loss satisfies (a) almost convexity, (b) QG, and (c) unique minima as
in Assumption 2. Combining with step 3, we have that all the assumptions of
Theorem 3.1 are satisfied by the average loss. Using union bound over the
three steps, invoking Theorem 3.1 we get with probability
$\big{(}1-\frac{T(L+1){{C}}}{m}\big{)}$ for some absolute constant ${C}>0$,
with $\tilde{\theta}^{*}=\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$,

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta_{t};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}-{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
(29) $\displaystyle\leq 2\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}+{\cal
O}(\log T).$ (30)

Next we bound $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
using the following lemma.

######  Lemma 8.

Under Assumption 1 and 5 with probability $\left(1-\frac{2T(L+1)}{m}\right)$
over the randomness of the initialization and
$\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$ we have $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}={\cal
O}(1).$

Using Lemma 8 and eq. 29 we have $\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}({\theta_{t}};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}={\cal
O}(\log T)$ which using eq. 14 and recalling the definition in eq. 13 implies
$\tilde{\text{R}}_{\operatorname{\text{Sq}}}(T)={\cal O}(\log T)$

∎

Next we prove all the intermediate lemmas in the above steps. See 5

###### Proof.

We begin by showing that the output of both regularized and un-regularized
network defined in eq. 10 and eq. 1 respectively is bounded with high
probability over the randomness of the initialization and in expectation over
the randomness of $\bm{\varepsilon}$. Consider any $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ and
$\mathbf{x}\in\mathcal{X}$. Then, the output of the network in expectation
w.r.t. $\varepsilon_{i}$’s can be bounded as follows.

$\displaystyle\mathbb{E}_{\bm{\varepsilon}}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|^{2}$
$\displaystyle\leq
2|f(\theta;\mathbf{x})|^{2}+2c_{\operatorname{\text{reg}}}^{2}\mathbb{E}_{\bm{\varepsilon}}\left(\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{j}\varepsilon_{j}}{m^{1/4}}\right)^{2}$
$\displaystyle=2|f(\theta;\mathbf{x})|^{2}+2c_{\operatorname{\text{reg}}}^{2}\left(\sum_{i=1}^{p}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{i}e_{j}^{T}(\theta-\theta_{0})}{\sqrt{m}}\mathbb{E}_{\bm{\varepsilon}}[\varepsilon_{i}\varepsilon_{j}]\right)$
$\displaystyle\overset{(a)}{\leq}2|f(\theta;\mathbf{x})|^{2}+2c_{\operatorname{\text{reg}}}^{2}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})_{i}^{2}}{\sqrt{m}}$
$\displaystyle\overset{}{=}\frac{2}{{m}}|\mathbf{v}^{\top}\alpha^{(L)}(\mathbf{x})|^{2}+\frac{2c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}\|\theta-\theta_{0}\|^{2}$
$\displaystyle\overset{(b)}{\leq}\frac{2}{{m}}\|\mathbf{v}\|^{2}\|\alpha^{(L)}(\mathbf{x})\|^{2}+\frac{2}{\sqrt{m}}c_{\operatorname{\text{reg}}}^{2}(L\rho+\rho_{1})^{2}$
$\displaystyle\overset{(c)}{\leq}\frac{2}{m}(1+\rho_{1})^{2}\left(\gamma^{L}+|\phi(0)|\sum^{L}_{i=1}\gamma^{i-1}\right)^{2}{m}+\frac{2}{\sqrt{m}}c_{\operatorname{\text{reg}}}^{2}(L\rho+\rho_{1})^{2}$

where $\gamma=\sigma_{1}+\frac{\rho}{\sqrt{m}}$. Here $(a)$ follows from the
fact that $\mathbb{E}[\varepsilon_{i}\varepsilon_{j}]=0$ when $i\neq j$, and
$\mathbb{E}[\varepsilon_{i}\varepsilon_{j}]=1$ when $i=j$, $(b)$ follows from
$\|\theta-\theta_{0}\|_{2}\leq L\rho+\rho_{1}$, and $(c)$ holds with
probability $\left(1-\frac{2(L+1)}{m}\right)$ and follows from the fact that
$\left\lVert\mathbf{v}\right\rVert\leq\left\lVert\mathbf{v}_{0}\right\rVert+\left\lVert\mathbf{v}-\mathbf{v}_{0}\right\rVert\leq
1+\rho_{1}$ and thereafter using the arguments in proof of Lemma 4.2 from
Banerjee et al. [2023]. Finally with a union bound over $t\in[T]$ and using
Jensen we get with probability $\left(1-\frac{2T(L+1)}{m}\right)$

$\displaystyle\mathbb{E}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|$
$\displaystyle\leq\sqrt{\mathbb{E}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|^{2}}$
$\displaystyle\leq\sqrt{2(1+\rho_{1})^{2}\left(\gamma^{L}+|\phi(0)|\sum_{i=1}^{L}\gamma^{i-1}\right)^{2}+\frac{2}{\sqrt{m}}c_{\operatorname{\text{reg}}}^{2}(L\rho+\rho_{1})^{2}}.$
(31)

Now consider
${\bm{\varepsilon}}=(\varepsilon_{1},\ldots,\varepsilon_{j-1},\varepsilon_{j},\varepsilon_{j+1}\ldots,\varepsilon_{p})$
and
${\bm{\varepsilon}}^{\prime}=(\varepsilon_{1},\ldots,\varepsilon_{j-1},\varepsilon_{j}^{\prime},\varepsilon_{j+1}\ldots,\varepsilon_{p})$
that differ only at the $j$-th variable where $\varepsilon_{j}$ is an
independent copy of $\varepsilon_{j}^{\prime}$. Now,

$\displaystyle|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})-\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}}^{\prime})|$
$\displaystyle=\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}|(\theta-\theta_{0})^{T}v_{j}\varepsilon_{j}-(\theta-\theta_{0})^{T}v_{j}\varepsilon_{j}^{\prime}|$
$\displaystyle\leq\frac{2c_{\operatorname{\text{reg}}}}{m^{1/4}}|(\theta-\theta_{0})_{j}|$

By McDiarmid’s inequality we have with probability $(1-\delta)$ over the
randomness of $\\{\varepsilon_{i}\\}_{i=1}^{p}$

$\displaystyle\Big{|}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|-\mathbb{E}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|\Big{|}$
$\displaystyle\leq\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}\sqrt{{\sum_{j=1}^{p}(\theta-\theta_{0})_{j}^{2}}\ln(1/\delta)}$
$\displaystyle=\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}\|\theta-\theta_{0}\|_{2}\sqrt{\ln(1/\delta)}$
$\displaystyle\leq\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}(L\rho+\rho_{1})\sqrt{\ln(1/\delta)}$

Taking a union bound over $t\in[T]$, with probability $1-{\delta}$ over the
randomness of $\\{\varepsilon_{i}\\}_{i=1}^{p}$ we have

$\displaystyle\Big{|}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|-\mathbb{E}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|\Big{|}\leq\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}(L\rho+\rho_{1})\sqrt{\ln(T/\delta)}$

Choosing $\delta=\frac{1}{m}$ we get with probability
$\left(1-\frac{1}{m}\right)$ over the randomness of
$\\{\varepsilon_{i}\\}_{i=1}^{p}$

$\displaystyle\Big{|}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|-\mathbb{E}|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|\Big{|}\leq\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}(L\rho+\rho_{1})\sqrt{\ln(mT)}$

Combining with section C.2, we have with probability at least
$\left(1-\frac{2T(L+2)+1}{m}\right)$ over the randomness of the initialization
and $\\{\varepsilon_{i}\\}_{i=1}^{p}$ we have

$\displaystyle|\tilde{f}(\theta;\mathbf{x}_{t},{\bm{\varepsilon}})|$
$\displaystyle\leq\sqrt{2(1+\rho_{1})^{2}\left(\gamma^{L}+|\phi(0)|\sum_{i=1}^{L}\gamma^{i-1}\right)^{2}+\frac{2}{\sqrt{m}}c_{\operatorname{\text{reg}}}^{2}(L\rho+\rho_{1})^{2}}$
$\displaystyle\qquad+\frac{\sqrt{2}c_{\operatorname{\text{reg}}}}{m^{1/4}}(L\rho+\rho_{1})\sqrt{\ln(mT)}$
(32)

Finally taking a union bound over $\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$ for
$S={\cal O}(\log m)$ and using the fact that
$m={\Omega}(T^{5}L/\lambda_{0}^{6})$ we get with probability at least
$\left(1-\frac{2T(L+2)+1}{m}\right)$ over the randomness of the initialization
and $\\{\bm{\varepsilon}\\}_{s=1}^{S},$ $\forall t\in[T],$ ${\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
is lipschitz with $\lambda_{\operatorname{\text{Sq}}}=\Theta(1)$.

Further $\ell^{\prime\prime}_{\operatorname{\text{Sq}}}=1$ and therefore the
loss is strongly convex and smooth with
$a_{\operatorname{\text{Sq}}}=b_{\operatorname{\text{Sq}}}=1$ a.s. over the
randomness of $\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$, which completes the
proof. ∎

See 6

###### Proof.

From eq. 10 we have a.s.

$\displaystyle\nabla_{\theta}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})$
$\displaystyle=\nabla_{\theta}f(\theta;\mathbf{x})+c_{\operatorname{\text{reg}}}\sum_{i=1}^{p}\frac{e_{i}\varepsilon_{i}}{m^{1/4}}\leavevmode\nobreak\
,$ (33)
$\displaystyle\nabla_{\theta}^{2}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})$
$\displaystyle=\nabla_{\theta}^{2}f(\theta;\mathbf{x}).$ (34)

Next, with
$\ell^{\prime}_{t}=(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})-y_{t})$

$\displaystyle\nabla_{\theta}\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
$\displaystyle=\ell^{\prime}_{t}\nabla_{\theta}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})$
$\displaystyle\nabla_{\theta}^{2}\ell_{\operatorname{\text{Sq}}}\big{(}y_{t},\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
$\displaystyle=\nabla_{\theta}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})\nabla_{\theta}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})^{T}+\ell^{\prime}_{t}\nabla_{\theta}^{2}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})$

where we have used the fact that $\ell^{\prime\prime}_{t}=1$, and
$\nabla_{\theta}^{2}\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})=\nabla_{\theta}^{2}{f}(\theta;\mathbf{x}_{t})$
from eq. 34.

Consider $u\in\mathcal{S}^{p-1}$, the unit ball in $\mathbb{R}^{p}$. Then

$\displaystyle u^{T}\nabla_{\theta}^{2}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}u=\frac{1}{S}\sum_{s=1}^{S}u^{T}\Bigg{[}\nabla_{\theta}f(\theta;\mathbf{x}_{t})\nabla_{\theta}f(\theta;\mathbf{x}_{t})^{T}$
$\displaystyle+c_{\operatorname{\text{reg}}}\sum_{i=1}^{p}\frac{v_{i}\nabla_{\theta}f(\theta;\mathbf{x}_{t})^{T}}{m^{1/4}}\varepsilon_{s,i}+c_{\operatorname{\text{reg}}}\sum_{i=1}^{p}\frac{\nabla_{\theta}f(\theta;\mathbf{x}_{t})v_{i}^{T}}{m^{1/4}}\varepsilon_{s,i}+c_{\operatorname{\text{reg}}}^{2}\sum_{i=1}^{p}\sum_{j=1}^{p}\frac{v_{i}v_{j}^{T}}{\sqrt{m}}\varepsilon_{s,i}\varepsilon_{s,j}\Bigg{]}u$
$\displaystyle+\ell^{\prime}_{t,i}u^{T}\nabla_{\theta}^{2}{f}(\theta;\mathbf{x}_{t})u$
$\displaystyle=\langle\nabla_{\theta}f(\theta;\mathbf{x}_{t}),u\rangle^{2}+2\langle\nabla_{\theta}f(\theta;\mathbf{x}_{t}),u\rangle\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\frac{1}{S}\sum_{s=1}^{S}\underbrace{\sum_{i=1}^{p}u_{i}\varepsilon_{s,i}}_{\Gamma_{s}}$
$\displaystyle\qquad+\frac{c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}\frac{1}{S}\sum_{s=1}^{S}\underbrace{\sum_{i=1}^{p}\sum_{j=1}^{p}u_{i}u_{j}\varepsilon_{s,i}\varepsilon_{s,j}}_{\Gamma_{s}^{2}}+\ell^{\prime}_{t,i}u^{T}\nabla_{\theta}^{2}{f}(\theta;\mathbf{x}_{t})u$
(35)

Notice that $\forall s\in[S]$, $\Gamma_{s}=\langle
u,{\bm{\varepsilon}}_{s}\rangle$ is a weighted sum of Rademacher random
variables and therefore is $\|u\|_{2}=1$ sub-gaussian. Using Hoeffding’s
inequality, for a given $t\in[T]$,

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\leq-\omega_{1}\Bigg{\\}}$
$\displaystyle\leq e^{-S^{2}\omega_{1}^{2}/2}.$

Taking a union bound we get $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\leq-\omega_{1}\Bigg{\\}}$
$\displaystyle\leq Te^{-S^{2}\omega_{1}^{2}/2}.$

Further if $\Gamma_{s}$ is $\sigma_{s}$ sub-gaussian, then $\Gamma_{s}^{2}$ is
$(\nu^{2},\alpha)$ sub-exponential with
$\nu=4\sqrt{2}\sigma^{2}_{s},\alpha=4\sigma_{s}^{2}$ (see Honorio and Jaakkola
[2014, Appendix B]) and therefore $\Gamma_{s}^{2}$ is $(4\sqrt{2},4)$ sub-
exponential. Using Bernstein’s inequality for a given $t\in[T]$,

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\leq-\omega_{2}\Bigg{\\}}\leq
e^{-\frac{1}{2}\min\left(\frac{S^{2}\omega_{2}^{2}}{32},\frac{S\omega_{2}}{4}\right)}$

Taking a union bound we get for any $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\leq-\omega_{2}\Bigg{\\}}\leq
Te^{-\frac{1}{2}\min\left(\frac{S^{2}\omega_{2}^{2}}{32},\frac{S\omega_{2}}{4}\right)}$

Now choosing $\omega_{1}=\omega_{2}=\frac{1}{2},$ we get for any $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\leq-\frac{1}{2}\Bigg{\\}}$
$\displaystyle\leq Te^{-S^{2}/8}.$ $\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\leq-\frac{1}{2}\Bigg{\\}}$
$\displaystyle\leq
Te^{-\frac{1}{2}\min\left(\frac{S^{2}}{128},\frac{S}{8}\right)}$
$\displaystyle\leq Te^{-{S}/{8}}\leavevmode\nobreak\ ,\quad\forall S\geq 16$

Observing that $\mathbb{E}\Gamma_{s}=0$, $\mathbb{E}\Gamma_{s}^{2}=1$,
combining with eq. 35 and recalling that with probability
$\left(1-\frac{2(L+1)T}{m}\right)$ over the randomness of initialization,
$\|\nabla_{\theta}f(\theta;\mathbf{x}_{t})\|_{2}\leq\frac{c_{H}}{\sqrt{m}}$ we
get with probability at least $1-T(e^{-S^{2}/8}+e^{-S/8})-\frac{2(L+1)T}{m}$

$\displaystyle u^{T}\nabla_{\theta}^{2}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}u\geq\underbrace{\langle\nabla_{\theta}f(\theta;\mathbf{x}_{t}),u\rangle^{2}-\langle\nabla_{\theta}f(\theta;\mathbf{x}_{t}),u\rangle\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}}_{I}+\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}-\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}.$

Term $I$ is minimized for
$\displaystyle\langle\nabla_{\theta}f(\theta;\mathbf{x}_{t}),u\rangle=\frac{c_{\operatorname{\text{reg}}}}{2m^{1/4}}$
and the minimum value is
$-\frac{c_{\operatorname{\text{reg}}}^{2}}{4\sqrt{m}}$. Substituting this back
to the above equation we get

$\displaystyle u^{T}\nabla_{\theta}^{2}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}u$
$\displaystyle\geq-\frac{c_{\operatorname{\text{reg}}}^{2}}{4\sqrt{m}}+\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}-\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}$
$\displaystyle=\frac{c_{\operatorname{\text{reg}}}^{2}}{4\sqrt{m}}-\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}$
$\displaystyle=\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}$

where the last equality follows because
$c_{\operatorname{\text{reg}}}^{2}=8\lambda_{\operatorname{\text{Sq}}}C_{H}$.
Since $S^{2}/8\geq S/8$ for $S\geq 1$, we have for $S\geq 16$ with probability
$1-2Te^{-S/8}-\frac{2(L+1)T}{m}$

$\displaystyle u^{T}\nabla_{\theta}^{2}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}u\geq\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}>0.$

Choosing $S=\max\\{8\log m,16\\}$, we have with probability
$\left(1-\frac{2T(L+2)}{m}\right)$ over the randomness of initialization and
$\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$ we have

$\displaystyle u^{T}\nabla_{\theta}^{2}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}u\geq\frac{\lambda_{\operatorname{\text{Sq}}}C_{H}}{\sqrt{m}}>0.$

which completes the proof. ∎

See 7

###### Proof.

We have

$\displaystyle\Big{\|}\nabla{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}\Big{\|}_{2}^{2}=\Big{\|}\frac{1}{S}\sum_{s=1}^{S}\nabla{\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\right)\Big{\|}_{2}^{2}$
$\displaystyle=\frac{1}{S^{2}}\sum_{s=1}^{S}\sum_{s^{\prime}=1}^{S}(\tilde{f}(\theta;\mathbf{x}_{t},\varepsilon_{s})-y_{t})(\tilde{f}(\theta;\mathbf{x}_{t},\varepsilon_{s})-y_{t})\Big{\langle}\nabla\tilde{f}(\theta;\mathbf{x}_{t},\varepsilon_{s}),\nabla\tilde{f}(\theta;\mathbf{x}_{t},\varepsilon_{s^{\prime}})\Big{\rangle}$
$\displaystyle=\frac{1}{S^{2}}({F}(\theta;\mathbf{x}_{t})-y_{t}\mathbbm{1}_{S})^{T}\tilde{K}(\theta,\mathbf{x}_{t})({F}(\theta;\mathbf{x}_{t})-y_{t}\mathbbm{1}_{S})$
(36)

where ${F}(\theta,\mathbf{x}_{t}):\mathbb{R}^{p\times
d}\rightarrow\mathbb{R}^{S}$ such that
$({F}(\theta,\mathbf{x}_{t}))_{s}=\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})$,
$\mathbbm{1}_{S}$ is an $S$-dimensional vector of $1^{\prime}s$ and
$\tilde{K}(\theta,\mathbf{x}_{t})=\big{[}\big{\langle}\nabla_{\theta}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}),\nabla_{\theta}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}^{\prime})\big{\rangle}\big{]}$.
∎

Now,

$\displaystyle\tilde{K}(\theta,\mathbf{x}_{t})_{s,s^{\prime}}$
$\displaystyle=\Big{\langle}\nabla
f(\theta;\mathbf{x}_{t})+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{j=1}^{p}e_{j}\varepsilon_{s,j},f(\theta;\mathbf{x}_{t})+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{j=1}^{p}e_{j}\varepsilon_{s^{\prime},j}\Big{\rangle}$
$\displaystyle=\Big{\langle}\nabla
f(\theta;\mathbf{x}_{t})+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\bar{\bm{\varepsilon}}_{s},f(\theta;\mathbf{x}_{t})+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\bar{\bm{\varepsilon}}_{s^{\prime}}\Big{\rangle}$
$\displaystyle=\big{\langle}\nabla f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\langle\bar{\bm{\varepsilon}}_{s},\nabla
f(\theta;\mathbf{x}_{t})\rangle$
$\displaystyle\qquad+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\langle\bar{\bm{\varepsilon}}_{s^{\prime}},\nabla
f(\theta;\mathbf{x}_{t})\rangle+\frac{c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}\langle\bar{\bm{\varepsilon}}_{s},\bar{\bm{\varepsilon}}_{s^{\prime}}\rangle$

where $\bar{\bm{\varepsilon}}_{s}\in\mathbb{R}^{S}$ with
$(\bar{\bm{\varepsilon}}_{s})_{j}=\varepsilon_{s,j}$. Therefore,

$\displaystyle\tilde{K}(\theta,\mathbf{x}_{t})$
$\displaystyle=\big{\langle}\nabla f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}\mathbbm{1}_{S}\mathbbm{1}_{S}^{T}+\frac{c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M}$
$\displaystyle+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\begin{pmatrix}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}\\\ \nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}\\\ &&\vdots&\\\ \nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}\end{pmatrix}$
$\displaystyle+\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\begin{pmatrix}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{1}\\\ \nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{2}\\\ \vdots&&\vdots&\\\
\nabla f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}&\cdots&\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{S}\end{pmatrix}$

where $\bm{\varepsilon}_{M}$ is an $p\times S$ matrix whose columns are
$\bar{\bm{\varepsilon}}_{s}$. Next we give a uniform bound on the smallest
eigenvalue of $\tilde{K}(\theta,\mathbf{x}_{t})$. Consider
$u\in\mathcal{S}^{S-1}$, unit sphere in $\mathbb{R}^{S}$. We have

$\displaystyle u^{T}\tilde{K}(\theta,\mathbf{x}_{t})u$
$\displaystyle=\underbrace{\big{\langle}\nabla f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}u^{T}\mathbbm{1}_{S}\mathbbm{1}_{S}^{T}u}_{I}+\underbrace{\frac{c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}u^{T}\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M}u}_{II}$
$\displaystyle\qquad+\underbrace{\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}\sum_{s^{\prime}=1}^{S}u_{s}u_{s^{\prime}}\big{(}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{s}+\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{s^{\prime}}\big{)}}_{III}$

Consider term $I$. We can lower bound it as follows

$\displaystyle\big{\langle}\nabla f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}u^{T}\mathbbm{1}_{S}\mathbbm{1}_{S}^{T}u\geq\big{\langle}\nabla
f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}\geq\frac{\lambda_{0}}{2}.$

where the first inequality follows because
$\lambda_{\min}(\mathbbm{1}_{S}\mathbbm{1}_{S}^{T})\geq 0$ and the second
inequality because for any $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ with probability
$\left(1-\frac{2(L+1)}{m}\right)$ over the initialization

$\displaystyle\big{\langle}\nabla f(\theta;\mathbf{x}_{t}),\nabla
f(\theta;\mathbf{x}_{t})\big{\rangle}\geq\lambda_{\min}(K_{\operatorname{NTK}}(\theta))$
$\displaystyle\geq\lambda_{0}-\frac{2c_{H}\varrho{T}}{\sqrt{m}}L(\rho+\rho_{1})\leavevmode\nobreak\
\geq\frac{\lambda_{0}}{2}\geq 0\leavevmode\nobreak\ ,$ (37)

where the last inequality holds by choosing $m\geq\frac{16c_{H}^{2}\varrho
T^{2}(L\rho+\rho_{1})^{2}}{\lambda_{0}^{2}}=\Omega(T^{3}/\lambda_{0}^{4})$. To
see why eq. 37 holds observe that using the exact same argument as in eq. 55
and eq. 52 we have

$\displaystyle\left\lVert
K_{\operatorname{NTK}}(\theta)-K_{\operatorname{NTK}}(\theta_{0})\right\rVert_{2}\leq
2\sqrt{T}\varrho\frac{c_{H}\sqrt{T}}{\sqrt{m}}\left\lVert\theta-\theta_{0}\right\rVert_{2}$

Using the fact that $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ we have

$\displaystyle\left\lVert
K_{\operatorname{NTK}}(\theta)-K_{\operatorname{NTK}}(\theta_{0})\right\rVert_{2}{\leq}\frac{2c_{H}\varrho{T}}{\sqrt{m}}L(\rho+\rho_{1})$

and therefore

$\displaystyle\lambda_{\min}(K_{\operatorname{NTK}}(\theta))$
$\displaystyle\geq\lambda_{\min}(K_{\operatorname{NTK}}(\theta_{0}))-\left\lVert
K_{\operatorname{NTK}}(\theta)-K_{\operatorname{NTK}}(\theta_{0})\right\rVert_{2}$
$\displaystyle{\geq}\lambda_{0}-\frac{2c_{H}\varrho{T}}{\sqrt{m}}L(\rho+\rho_{1})\leavevmode\nobreak\
.$

Next consider term $II$. Since every entry of the $p\times S$ matrix
$\bm{\varepsilon}_{M}$ is i.i.d Rademacher, using Lemma 5.24, Vershynin
[2011], it follows that the rows are independent sub-gaussian, with the sub-
gaussian norm of the any row $\|(\bm{\varepsilon}_{M})_{i}\|_{\psi_{2}}\leq
C_{i}$, where $C_{i}$ is an absolute constant. Further using Theorem 5.39 from
Vershynin [2011] we have with probability at least $1-2\exp(-c_{M}t^{2})$

$\displaystyle\lambda_{\min}(\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M})\geq\sqrt{p}-C_{M}\sqrt{S}-t$

where $C_{M}$ and $c_{M}$ depend on the maximum of sub-gaussian norm of the
rows of $\bm{\varepsilon}_{M}$, i.e.,
$\max_{i}\|(\bm{\varepsilon}_{M})_{i}\|_{\psi_{2}}$, which is an absolute
constant. Choosing $t=\sqrt{S}$, for some absolute constant $c$, with
probability at least $\left(1-\frac{c}{m}\right)$, uniformly for any
$u\in\mathcal{S}^{S-1}$ we have

$\displaystyle\lambda_{\min}(\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M})\geq\sqrt{p}-(C_{M}+1)\sqrt{S}$

Noting that $S=\max\\{16,8\log m\\}$ and $p=md+(L-1)m^{2}+m$ we have

$\displaystyle\lambda_{\min}(\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M})\geq\frac{m+\sqrt{m}}{2}-(C_{M}+1)\sqrt{\max\\{16,8\log
m\\}}.$

Using $m\geq 64(C_{M}+1)^{2},\sqrt{m\log m}\geq 8\sqrt{2}(C_{M}+1)$, with
probability at least $\left(1-\frac{c}{m}\right)$, uniformly for any
$u\in\mathcal{S}^{S-1}$ we have

$\displaystyle u^{T}(\bm{\varepsilon}_{M}^{T}\bm{\varepsilon}_{M})u\geq m/2$

Finally consider term $III$. We have

$\displaystyle\frac{c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}\sum_{s^{\prime}=1}^{S}u_{s}u_{s^{\prime}}\big{(}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{s}+\nabla
f(\theta;\mathbf{x}_{t})^{T}\bar{\bm{\varepsilon}}_{s^{\prime}}\big{)}\geq\frac{2\sqrt{S}c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}u_{s}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bm{\varepsilon}_{s}.$

Since each $\varepsilon_{s,j}$ is $1$ sub-gaussian, therefore $\nabla
f(\theta;\mathbf{x}_{t})^{T}\bm{\varepsilon}_{s}$ is $\|\nabla
f(\theta;\mathbf{x}_{t})\|_{2}\,(\leq\varrho)$ sub-gaussian with zero mean.
Using Hoeffding we have with probability at least $1-\exp(-S^{2}t^{2})$

$\displaystyle\frac{2\sqrt{S}c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}u_{s}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bm{\varepsilon}_{s}\geq-\frac{2\sqrt{S}c_{\operatorname{\text{reg}}}}{m^{1/4}}St$

Choosing $t=\frac{1}{8}$ and noting that $S=\max\\{16,8\log m\\}$, we get with
probability at least $\left(1-\frac{1}{m^{2}}\right)$

$\displaystyle\frac{2\sqrt{S}c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}u_{s}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bm{\varepsilon}_{s}\geq\frac{-16c_{\operatorname{\text{reg}}}}{m^{1/4}}(\log
m)^{3/2}\geq-1$

where the last inequality used $m^{1/4}\geq 16c_{\operatorname{\text{reg}}}$
and $m^{1/4}(\log m)^{-3/2}\geq 4\sqrt{2}$. Finally to get a uniform bound
over $\mathcal{S}^{S-1}$, we can use a standard $\epsilon$-net argument with
$\epsilon=1/4$ and metric entropy $S\log 9$ (see eg. proof of Theorem 5.39 in
Vershynin [2011]). Using $m(\log m)^{-1}\geq 8\log 9$, with probability at
least $\left(1-\frac{1}{m}\right)$ uniformly for any $u\in\mathcal{S}^{S-1}$
we have

$\displaystyle\frac{2\sqrt{S}c_{\operatorname{\text{reg}}}}{m^{1/4}}\sum_{s=1}^{S}u_{s}\nabla
f(\theta;\mathbf{x}_{t})^{T}\bm{\varepsilon}_{s}\geq-1$

Combining all the terms and using $m\geq 4$, we get with probability
$\big{(}1-\frac{2(L+1)C}{m}\big{)}$ for some absolute constant $C>0$

$\displaystyle\frac{1}{S^{2}}({F}(\theta;\mathbf{x}_{t})-y_{t}\mathbbm{1}_{S})^{T}\tilde{K}(\theta,\mathbf{x}_{t})({F}(\theta;\mathbf{x}_{t})-y_{t}\mathbbm{1}_{S})$
$\displaystyle\geq\frac{m}{4S}\frac{1}{S}\big{\|}({F}(\theta;\mathbf{x}_{t})-y_{t}\mathbbm{1}_{S})\big{\|}_{2}$
$\displaystyle=\frac{m}{64\log m}\frac{1}{S}\sum_{s=1}^{S}{\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\right)$
$\displaystyle\geq 2\mu\,{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$

where $\mu=128$ where the last inequality follows from $m(\log m)^{-1}\geq 1$.
Combining with eq. 36 and using the fact that PL implies QG (see Remark 3.1)
along with a union bound over $t\in[T]$ completes the proof.

See 8

###### Proof.

Consider any $\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$.
We have

$\displaystyle{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle=\frac{1}{S}\sum_{s=1}^{S}{\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\right)=\frac{1}{2S}\sum_{s=1}^{S}\big{(}y_{t}-\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{)}^{2}$
$\displaystyle=\frac{1}{2S}\sum_{s=1}^{S}\left(y_{t}-f(\theta_{t};\mathbf{x}_{t})-c_{\operatorname{\text{reg}}}\sum_{j=1}^{p}\frac{(\theta_{t}-\theta_{0})^{T}e_{j}\varepsilon_{s,j}}{m^{1/4}}\right)^{2}$
$\displaystyle=\frac{1}{2}\Bigg{[}\big{(}y_{t}-f(\theta_{t};\mathbf{x}_{t})\big{)}^{2}-2c_{\operatorname{\text{reg}}}\big{(}y_{t}-f(\theta_{t};\mathbf{x}_{t})\big{)}\underbrace{\frac{1}{S}\sum_{s=1}^{S}\Big{(}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{j}\varepsilon_{s,j}}{m^{1/4}}\Big{)}}_{I}$
$\displaystyle\qquad+c_{\operatorname{\text{reg}}}^{2}\underbrace{\frac{1}{S}\sum_{s=1}^{S}\Big{(}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{j}\varepsilon_{s,j}}{m^{1/4}}\Big{)}^{2}}_{II}\Bigg{]}$
(38)

Consider term $I$.

$\displaystyle\frac{1}{S}\sum_{s=1}^{S}\Big{(}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{j}\varepsilon_{s,j}}{m^{1/4}}\Big{)}=\frac{1}{m^{1/4}}\frac{1}{S}\sum_{s=1}^{S}\underbrace{\Big{(}\sum_{j=1}^{p}(\theta-\theta_{0})_{j}\varepsilon_{s,j}\Big{)}}_{\Gamma_{s}}$

Since $\varepsilon_{s,j}$ is 1 sub-gaussian, $\Gamma_{s}$ is
$\|\theta-\theta_{0}\|_{2}^{2}$ sub-gaussian. Using Hoeffding’s inequality

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\geq\omega_{1}\Bigg{\\}}$
$\displaystyle\leq e^{-S^{2}\omega_{1}^{2}/2\|\theta-\theta_{0}\|_{2}}.$

Taking a union bound we get $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\geq\omega_{1}\Bigg{\\}}$
$\displaystyle\leq Te^{-S^{2}\omega_{1}^{2}/2\|\theta-\theta_{0}\|_{2}}.$

Next consider term $II$.

$\displaystyle\frac{1}{S}\sum_{s=1}^{S}\Big{(}\sum_{j=1}^{p}\frac{(\theta-\theta_{0})^{T}e_{j}\varepsilon_{s,j}}{m^{1/4}}\Big{)}^{2}=\frac{1}{\sqrt{m}}\frac{1}{S}\sum_{s=1}^{S}\underbrace{\sum_{i=1}^{p}\sum_{j=1}^{p}(\theta-\theta_{0})_{i}(\theta-\theta_{0})_{j}\varepsilon_{s,i}\varepsilon_{s,j}}_{\Gamma_{s}^{2}}$

Further if $\Gamma_{s}$ is $\sigma_{s}$ sub-gaussian, then $\Gamma_{s}^{2}$ is
$(\nu^{2},\alpha)$ sub-exponential with
$\nu=4\sqrt{2}\sigma^{2}_{s},\alpha=4\sigma_{s}^{2}$ (see Honorio and Jaakkola
[2014, Appendix B]) and therefore $\Gamma_{s}^{2}$ is
$\big{(}4\sqrt{2}\|\theta-\theta_{0}\|_{2}^{2},4\|\theta-\theta_{0}\|_{2}^{2}\big{)}$
sub-exponential. Using Bernstein’s inequality for a given $t\in[T]$,

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\geq\omega_{2}\Bigg{\\}}\leq
e^{-\frac{1}{2}\min\left(\frac{S^{2}\omega_{2}^{2}}{32\|\theta-\theta_{0}\|_{2}^{4}},\frac{S\omega_{2}}{4\|\theta-\theta_{0}\|_{2}^{2}}\right)}$

Taking a union bound we get for any $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\geq\omega_{2}\Bigg{\\}}\leq
Te^{-\frac{1}{2}\min\left(\frac{S^{2}\omega_{2}^{2}}{32\|\theta-\theta_{0}\|_{2}^{4}},\frac{S\omega_{2}}{4\|\theta-\theta_{0}\|_{2}^{2}}\right)}$

Now choosing
$\omega_{1}=\|\theta-\theta_{0}\|_{2},\omega_{2}=\|\theta-\theta_{0}\|_{2}^{2},$
we get for any $t\in[T]$

$\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}\geq\|\theta-\theta_{0}\|_{2}\Bigg{\\}}$
$\displaystyle\leq Te^{-S^{2}/2}.$ $\displaystyle
P\Bigg{\\{}\frac{1}{S}\sum_{s=1}^{S}\Gamma_{s}^{2}-\mathbb{E}\Gamma_{s}^{2}\geq\frac{1}{2}\|\theta-\theta_{0}\|_{2}^{2}\Bigg{\\}}$
$\displaystyle\leq
Te^{-\frac{1}{2}\min\left(\frac{S^{2}}{128},\frac{S}{8}\right)}$
$\displaystyle\leq Te^{-{S}/{8}}\leavevmode\nobreak\ ,\quad\forall S\geq 16$

Observing that $\mathbb{E}\Gamma_{s}=0$,
$\mathbb{E}\Gamma_{s}^{2}=\frac{c_{\operatorname{\text{reg}}}^{2}}{\sqrt{m}}\|\theta-\theta_{0}\|_{2}^{2}$,
using the fact that
$\lambda_{\operatorname{\text{Sq}}}=|y_{t}-{f}(\theta;\mathbf{x}_{t})|=\Theta(1)$
with probability $\left(1-\frac{2T(L+1)}{m}\right)$ (see proof of Lemma 5) and
finally combining with eq. 38 we get with probability at least
$1-T(e^{-S^{2}/2}+e^{-S/8})-\frac{2T(L+1)}{m}$

$\displaystyle{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle\leq{\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},f(\theta;\mathbf{x}_{t})\right)+\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}\|\theta-\theta_{0}\|_{2}^{2}+\frac{2c_{\operatorname{\text{reg}}}\lambda_{\operatorname{\text{Sq}}}}{m^{1/4}}\|\theta-\theta_{0}\|_{2}$

Summing over $t$ and taking a $\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}$ over the left hand side
we get for any $\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$

$\displaystyle\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle\leq\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},f(\theta;\mathbf{x}_{t})\right)+\sum_{t=1}^{T}\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}\|\theta-\theta_{0}\|_{2}^{2}+\frac{2c_{\operatorname{\text{reg}}}\lambda_{\operatorname{\text{Sq}}}}{m^{1/4}}\|\theta-\theta_{0}\|_{2}$

From Theorem E.1 we know there exists $\bar{\theta}\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ such that with
probability at least $(1-\frac{2(L+1)}{m})$ over the randomness of
initialization we have $f(\bar{\theta},\mathbf{x}_{t})=y_{t}$ for any set of
$y_{t}\in[0,1],t\in[T]$ which implies ${\cal
L}_{\operatorname{\text{Sq}}}\left(y_{t},f(\bar{\theta};\mathbf{x}_{t})\right)=0,\,\forall
t\in[T]$. Therefore

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{Sq}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle\leq
0+\sum_{t=1}^{T}\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}\|\theta^{\prime}-\theta_{0}\|_{2}^{2}+\frac{2c_{\operatorname{\text{reg}}}\lambda_{\operatorname{\text{Sq}}}}{m^{1/4}}\|\theta^{\prime}-\theta_{0}\|_{2}$
$\displaystyle\overset{(a)}{\leq}\frac{c_{\operatorname{\text{reg}}}^{2}}{2\sqrt{m}}(L\rho+\rho_{1})^{2}+\frac{2c_{\operatorname{\text{reg}}}\lambda_{\operatorname{\text{Sq}}}}{m^{1/4}}(L\rho+\rho_{1})\overset{(b)}{=}{\cal
O}(1)$ (39)

where $(a)$ follows because $\bar{\theta^{\prime}}\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ implies
$\theta^{\prime}\in B_{L\rho+\rho_{1}}^{\operatorname{Euc}}({\theta_{0}})$ and
$(b)$ follows by choosing $m=\Omega(T^{5}L/\lambda_{0}^{6})$. ∎

###  C.3 Proof of Theorem 3.3

See 3.3 _Proof._ The proof of the claim follows along similar lines as in the
previous subsection. It consists of the following four steps:

  1. 1.

Binary KL loss is lipschitz, strongly convex and smooth w.r.t. the output.

We show that $\ell_{\operatorname{\text{KL}}}(y_{t},\hat{y}_{t})$ is
lipschitz, strongly convex and smooth with respect to the output
$\hat{y}_{t}=\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon})$ inside
$B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ almost surely over the
randomness of initialization and $\bm{\varepsilon}$. We will use
$\lambda_{\operatorname{\text{KL}}},a_{\operatorname{\text{KL}}}$ and
$b_{\operatorname{\text{KL}}}$ respectively to denote the lipschitz, strong
convexity and smoothness parameter for
$\ell_{\operatorname{\text{KL}}}(y_{t},\hat{y}_{t})$ (c.f. Assumption
3(lipschitz, strongly convex and smooth)).

######  Lemma 9.

For $\theta\in B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, the loss
$\ell_{\operatorname{\text{KL}}}\big{(}y_{t},\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon})\big{)}$
is lipschitz, strongly convex and smooth with respect to the output
$\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon})$ a.s. over the randomness
of initialization and $\bm{\varepsilon}$. Further the parameters
$\lambda_{{\operatorname{\text{KL}}}},a_{\operatorname{\text{KL}}}$ and
$b_{\operatorname{\text{KL}}}$ are ${\cal O}(1)$.

Note that Lemma 9 implies that $\displaystyle{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}=\frac{1}{S}\sum_{s=1}^{S}\ell_{\operatorname{\text{KL}}}\left(y_{t},\sigma(\tilde{f}\big{(}\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{)}\right)$
is also lipschitz, strongly convex and smooth a.s. with respect to each of the
outputs $\tilde{f}\big{(}\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})$.

  2. 2.

The average loss at $t\in[T]$, ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
is almost convext and has a unique minimizer w.r.t. $\theta$.

We show that the random perturbation to the output in eq. 10 assures that
${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
is strongly convex with respect to $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$ at every $t\in[T]$ (with
a very small $\mathcal{O}\left(\frac{1}{\sqrt{m}}\right)$ strong convexity
parameter), which implies that it satisfies 2(a) and 2(c).

######  Lemma 10.

Under Assumption 5 and
$c_{p}=\sqrt{8\lambda_{\operatorname{\text{Sq}}}C_{H}}$, with probability
$\left(1-\frac{2T(L+2)}{m}\right)$ over the randomness of the initialization
and $\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$, ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
is $\nu$-strongly convex with respect to $\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})$, where
$\nu=\mathcal{O}\left(\frac{1}{\sqrt{m}}\right).$

  3. 3.

The average loss at $t\in[T]$, ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
satisfies the QG condition.

We show that the loss ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
satisfies the QG condition (with QG constant $\mu={\cal O}(1)$) with high
probability over the randomness of initialization and
$\\{\bm{\varepsilon}_{s}\\}_{s=1}^{S}$.

######  Lemma 11.

Under Assumption 5 with probability $\big{(}1-\frac{2T(L+1)C}{m}\big{)}$, for
some absolute constant $C>0$, ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s})\big{\\}}_{s=1}^{S}\Big{)}$
satisfies the QG condition over the randomness of the initialization and
$\\{\varepsilon_{s}\\}_{s=1}^{S}$, with constant $\mu={\cal O}(1)$.

  4. 4.

Bounding the final regret.

The above three steps ensure that all the assumptions of Theorem 3.1 are
satisfied by the loss function ${\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$.
Taking a union over the events in the above three steps, invoking Theorem 3.1,
we get with probability $\big{(}1-\frac{TL{{C}}}{m}\big{)}$ for some absolute
constant ${C}>0$,

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}-{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
$\displaystyle\leq 2\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\tilde{\theta}^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}+{\cal
O}(\log T).$ (40)
$\displaystyle\text{where}\quad\tilde{\theta}^{*}=\min_{\theta\in
B^{\operatorname{Frob}}_{\rho,\rho_{1}}(\theta_{0})}\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$

Next we bound $\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}$
using the following lemma.

######  Lemma 12.

Under Assumption 1 and 5 with probability $\left(1-\frac{TLC}{m}\right)$ for
some absolute constant $C>0$ over the randomness of the initialization we have

$\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta^{*};\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}={\cal
O}(1).$

Using Lemma 12 and eq. 40 we have $\displaystyle\sum_{t=1}^{T}{\cal
L}_{\operatorname{\text{KL}}}^{(S)}\Big{(}y_{t},\big{\\{}\sigma(\tilde{f}(\theta;\mathbf{x}_{t},\bm{\varepsilon}_{s}))\big{\\}}_{s=1}^{S}\Big{)}\leq{\cal
O}(\log T)$. which implies $\text{R}_{\operatorname{\text{KL}}}(T)\leq{\cal
O}(\log T)$.

∎

Next we prove Lemmas 9,10,11 and 12. See 9

###### Proof.

Consider $\theta\in B_{\rho,\rho_{1}}^{\operatorname{Spec}}({\theta_{0}})$.
Now,

$\displaystyle\ell_{\operatorname{\text{KL}}}^{\prime}$
$\displaystyle:=\frac{d\ell_{\log}(y_{t},\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))}{d\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})}$
$\displaystyle=-\left(\frac{y_{t}\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))(1-\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})))}{\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))}-\frac{(1-y_{t})\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon})(1-\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))}{1-\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))}\right)$
$\displaystyle=-y_{t}+y_{t}\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))+\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))-y_{t}\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))$
$\displaystyle=\sigma(\tilde{f}(\theta,\mathbf{x}_{t},\bm{\varepsilon}))-y_{t}.$