# Neural Active Learning with Performance Guarantees

Pranjal Awasthi
Google Research NY &Christoph Dann
Google Research NY &Claudio Gentile
Google Research NY &Ayush Sekhari
Cornell University &Zhilei Wang
New York University

###### Abstract

We investigate the problem of active learning in the streaming setting in non-
parametric regimes, where the labels are stochastically generated from a class
of functions on which we make no assumptions whatsoever. We rely on recently
proposed Neural Tangent Kernel (NTK) approximation tools to construct a
suitable neural embedding that determines the feature space the algorithm
operates on and the learned model computed atop. Since the shape of the label
requesting threshold is tightly related to the complexity of the function to
be learned, which is a-priori unknown, we also derive a version of the
algorithm which is agnostic to any prior knowledge. This algorithm relies on a
regret balancing scheme to solve the resulting online model selection problem,
and is computationally efficient. We prove joint guarantees on the cumulative
regret and number of requested labels which depend on the complexity of the
labeling function at hand. In the linear case, these guarantees recover known
minimax results of the generalization error as a function of the label
complexity in a standard statistical learning setting.

##  1 Introduction

Supervised learning is a fundamental paradigm in machine learning and is at
the core of modern breakthroughs in deep learning [28]. A machine learning
system trained via supervised learning requires access to labeled data
collected via recruiting human experts, crowdsourcing, or running expensive
experiments. Furthermore, as the complexity of current deep learning
architectures grows, their requirement for labeled data increases
significantly. The area of active learning aims to reduce this data
requirement by studying the design of algorithms that can learn and generalize
from a small carefully chosen subset of the training data [13, 39].

The two common formulations of active learning are pool based active learning,
and sequential (or streaming) active learning. In the pool based setting [29],
the learning algorithm has access to a large unlabeled set of data points, and
the algorithm can ask for a subset of the data to be labeled. In contrast, in
the sequential setting, data points arrive in a streaming manner, either
adversarially or drawn i.i.d. from a distribution, and the algorithm must
decide whether to query the label of a given point or not [14].

From a theoretical perspective, active learning has typically been studied
under models inspired by the probably approximately correct (PAC) model of
learning [40]. Here one assumes that there is a pre-specified class
$\mathcal{H}$ of functions such that the target function mapping examples to
their labels either lies in $\mathcal{H}$ or has a good approximation inside
the class. Given access to unlabeled samples generated i.i.d. from the
distribution, the goal is to query for a small number of labels and produce a
hypothesis of low error.

In the parametric setting, namely, when the class of functions $\mathcal{H}$
has finite VC-dimension (or finite disagreement coefficient) [21], the rate of
convergence of active learning, i.e., the rate of decay of the error as a
function of the number of label queries ($N$), is of the form
$\nu\,N^{-1/2}+e^{-N}$, where $\nu$ is the population loss of the best
function in class $\mathcal{H}$. This simple finding shows that active
learning behaves like passive learning when $\nu>0$, while very fast rates can
only be achieved under low noise ($\nu\approx 0$) conditions. This has been
worked out in, e.g., [19, 15, 5, 4, 6, 37].

While the parametric setting comes with methodological advantages, the above
shows that in order to unleash the true power of active learning, two
properties are desirable: (1) A better interplay between the input
distribution and the label noise and, (2) a departure from the parametric
setting leading us to consider wider classes of functions (so as to reduce the
approximation error $\nu$ to close to 0). To address the above, there has also
been considerable theoretical work in recent years on non-parametric active
learning [10, 32, 30]. However, these approaches suffer from the curse of
dimensionality and do not lead to computationally efficient algorithms. A
popular approach that has been explored empirically in recent works is to use
Deep Neural Networks (DNNs) to perform active learning (e.g., [36, 25, 38, 3,
43]). While these works empirically demonstrate the power of the DNN-based
approach to active learning, they do not come with provable guarantees. The
above discussion raises the following question: Is provable and
computationally efficient active learning possible in non-parametric settings?

We answer the above question in the affirmative by providing the first, to the
best of our knowledge, computationally efficient algorithm for active learning
based on Deep Neural Networks. Similar to non-parametric active learning, we
avoid fixing a function class a-priori. However, in order to achieve
computational efficiency, we instead propose to use over-parameterized DNNs,
where the amount of over-parameterization depends on the input data at hand.
We work in the sequential setting, and propose a simple active learning
algorithm that forms an uncertainty estimate for the current data point based
on the output of a DNN, followed by a gradient descent step to update the
network parameters if the data point is queried. We show that under standard
low-noise assumptions [31] our proposed algorithm achieves fast rates of
convergence.

In order to analyze our algorithm, we use tools from the theory of Neural
Tangent Kernel (NTK) approximation [23, 2, 18] that allows us to analyze the
dynamics of gradient descent by considering a linearization of the network
around random initialization. Since we study the non-parametric regime, the
convergence rates of our algorithm depend on a data-dependent complexity term
that is expected to be small in practical settings, but could be very large in
worst-case scenarios. Furthermore, the algorithm itself needs an estimate of
complexity term in order to form accurate uncertainty estimates. We show that
one can automatically adapt to the magnitude of the unknown complexity term by
designing a novel model selection algorithm inspired by recent works in model
selection in multi-armed bandit settings [35, 34]. Yet, several new insights
are needed to ensure that the model selection algorithm can simultaneously
achieve low generalization error without spending a significant amount of
budget on label queries.

##  2 Preliminaries and Notation

Let $\mathcal{X}$ denote the input space, $\mathcal{Y}$ the output space, and
$\mathcal{D}$ an unknown distribution over $\mathcal{X}\times\mathcal{Y}$. We
denote the corresponding random variables by $x$ and $y$. We also denote by
$\mathcal{D}_{\mathcal{X}}$ the marginal distribution of $\mathcal{D}$ over
$\mathcal{X}$, and by $\mathcal{D}_{\mathcal{Y}|x_{0}}$ the conditional
distribution of random variable $y$ given $x=x_{0}$. Moreover, given a
function $f$ (sometimes called a hypothesis or a model) mapping $\mathcal{X}$
to $\mathcal{Y}$, the conditional population loss (often referred to as
conditional risk) of $f$ is denoted by $L(f\,|\,x)$, and defined as
$L(f\,|\,x)=\mathbb{E}_{y\sim\mathcal{D}_{\mathcal{Y}|x}}[\ell(f(x),y)\,|\,x]$,
where $\ell\,\colon\,\mathcal{Y}\times\mathcal{Y}\to[0,1]$ is a loss function.
For ease of presentation, we restrict to a binary classification setting with
0-1 loss, whence $\mathcal{Y}=\\{-1,+1\\}$, and $\ell(a,y)=\
1{1}{\left\\{a\neq y\right\\}}\in\\{0,1\\}$, $\ 1{1}{\left\\{\cdot\right\\}}$
being the indicator function of the predicate at argument. When clear from the
surrounding context, we will omit subscripts like
“$y\sim\mathcal{D}_{\mathcal{Y}|x}$" from probabilities and expectations.

We investigate a non-parametric setting of active learning where the
conditional distribution of $y$ given $x$ is defined through an unknown
function $h\,:\,\mathcal{X}^{2}\rightarrow[0,1]$ such that

$\mathbb{P}(y=1\,|\,x)=h((x,0))\qquad\mathbb{P}(y=-1\,|\,x)=h((0,x))~{},$ (1)

where $0\in\mathcal{X}$, $(x_{1},x_{2})$ denotes the concatenation (or
pairing) of the two instances $x_{1}$ and $x_{2}$ (so that $(x,0)$ and $(0,x)$
are in $\mathcal{X}^{2}$) and, for all $x\in\mathcal{X}$ we have
$h((x,0))+h((0,x))=1$. We make no explicit assumptions on $h$, other than its
well-behavedness w.r.t. the data $\\{x_{t}\\}_{t=1}^{T}$ at hand through the
formalism of Neural Tangent Kernels (NTK) – see below. As a simple example, in
the linear case, $\mathcal{X}$ is the $d$-dimensional unit ball,
$h(\cdot,\cdot)$ is parametrized by an unknown unit vector
$\theta\in\mathbb{R}^{d}$, and
$h((x_{1},x_{2}))=\frac{1+\langle(\theta,-\theta),(x_{1},x_{2})\rangle}{2}~{},$
so that $h((x,0))=\frac{1+\langle\theta,x\rangle}{2}$ and
$h((0,x))=\frac{1-\langle\theta,x\rangle}{2},$ where
$\langle\cdot,\cdot\rangle$ is the usual dot product in $\mathbb{R}^{d}$.

We consider a streaming setting of active learning where, at each round
$t\in[T]=\\{1,\ldots,T\\}$, a pair
$(x_{t},y_{t})\in\mathcal{X}\times\mathcal{Y}$ is drawn i.i.d. from
$\mathcal{D}$. The learning algorithm receives as input only $x_{t}$, and is
compelled to both issue a prediction $a_{t}$ for $y_{t}$ and, at the same
time, decide on-the-fly whether or not to observe $y_{t}$. These decisions can
only be based on past observations. Let $\mathbb{E}_{t}$ denote the
conditional expectation
$\mathbb{E}[\cdot\,|(x_{1},y_{1})\ldots,(x_{t-1},y_{t-1}),x_{t}],$ and we
introduce the shorthand

$x_{t,a}=\begin{cases}(x_{t},0)&{\mbox{if $a=1$}}\\\ (0,x_{t})&{\mbox{if
$a=-1$}}~{}.\end{cases}$

Notice that with this notation
$\mathbb{E}[\ell(a,y_{t})\,|\,x_{t}]=1-h(x_{t,a})$, for all $a\in\mathcal{Y}$.
We quantify the accuracy of the learner’s predictions through its (pseudo)
_regret_ , defined as

$R_{T}~{}=~{}\sum_{t=1}^{T}\Bigl{(}\mathbb{E}_{t}[\ell(a_{t},y_{t})\,|\,x_{t}]-\mathbb{E}[\ell(a^{*}_{t},y_{t})\,|\,x_{t}]\Bigl{)}~{}=~{}\sum_{t=1}^{T}\left(h(x_{t,a^{*}_{t}})-h(x_{t,a_{t}})\right)~{},$

where $a_{t}^{*}$ is the Bayesian-optimal classifier on instance $x_{t}$, that
is, $a_{t}^{*}=\arg\max_{a\in\mathcal{Y}}h(x_{t,a})$. Additionally, we are
interested in bounding the number of labels $N_{T}$ the algorithm decides to
request. Our goal is to simultaneously bound $R_{T}$ and $N_{T}$ with high
probability over the generation of the sample
$\\{(x_{t},y_{t})\\}_{t=1,\ldots,T}$ .

Throughout this work, we consider the following common low-noise condition on
the marginal distribution $\mathcal{D}_{\mathcal{X}}$ (Mammen-Tsybakov low
noise condition [31]): There exist absolute constants $c>0$, and $\alpha\geq
0$ such that for all $\epsilon\in(0,1/2)$ we have
$\mathbb{P}\bigl{(}|h((x,0))-\frac{1}{2}|<\epsilon\bigr{)}\leq
c\,\epsilon^{\alpha}.$ In particular, $\alpha=\infty$ gives the so-called hard
margin condition
$\mathbb{P}\bigl{(}|h((x,0))-\frac{1}{2}|<\epsilon\bigr{)}=0.$ while, at the
opposite extreme, exponent $\alpha=0$ (and $c=1$) results in no assumptions
whatsoever on $\mathcal{D}_{\mathcal{X}}$. For simplicity, we shall assume
throughout that the above low-noise condition holds for111 A more general
formulation requires the above to hold only for $\epsilon\leq\epsilon_{0}$,
where $\epsilon_{0}\in(0,1/2)$ is a third parameter. We shall omit this extra
parameter from our presentation.  $c=1$.

Our techniques are inspired by the recent work [44] from which we also borrow
some notation. We are learning the class of functions $\\{h\\}$ by means of
fully connected neural networks

$f(x,{\theta})=\sqrt{m}W_{n}\sigma(...\sigma(W_{1}x))~{},$

where $\sigma$ is a ReLU activation function $\sigma(x)=\max\\{0,x\\}$, $m$ is
the width of the network and $n\geq 2$ is its depth. In the above,
$\theta\in\mathbb{R}^{p}$ collectively denotes the set of weights
$\\{W_{1},W_{2},\ldots,W_{n}\\}$ of the network, where $p=m+2md+m^{2}(n-2)$ is
their number, and the input $x$ at training time should be thought of as some
$x_{t,a}\in\mathcal{X}^{2}$.

With any depth-$n$ network and data points
$\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$ we associate a depth-$n$ NTK matrix
as follows [23]. First, rename $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$ as
$\\{x^{(i)}\\}_{i=1,\ldots,2T}$. Then define matrices

${\widetilde{H}^{(1)}}=\left[H^{(1)}_{i,j}\right]_{i,j=1}^{2T\times
2T}\qquad\Sigma^{(1)}=\left[\Sigma^{(1)}_{i,j}\right]_{i,j=1}^{2T\times
2T}\qquad{\mbox{with}}\qquad H^{(1)}_{i,j}=\Sigma^{(1)}_{i,j}=\langle
x^{(i)},x^{(j)}\rangle~{},$

and then, for any $k\leq n$ and $i,j=1,\ldots,2T$, introduce the bivariate
covariance matrix
$A^{(k)}_{i,j}=\begin{bmatrix}\Sigma^{(k)}_{i,i}&\Sigma^{(k)}_{i,j}\\\
\Sigma^{(k)}_{i,j}&\Sigma^{(k)}_{j,j}\end{bmatrix}$ by which we recursively
define $\Sigma^{(k+1)}_{i,j}=2\mathbb{E}_{(u,v)\sim
N(0,A^{(k)}_{i,j})}[\sigma(u)\sigma(v)]$ and
${\widetilde{H}}^{(k+1)}_{i,j}=2{\widetilde{H}}^{(k)}_{i,j}\mathbb{E}_{(u,v)\sim
N(0,A^{(k)}_{i,j})}[\ 1{1}{\left\\{u\geq 0\right\\}}\ 1{1}{\left\\{v\geq
0\right\\}}]+\Sigma^{(k+1)}_{i,j}~{}.$ The $2T\times 2T$-dimensional matrix
$H=\frac{1}{2}({\widetilde{H}}^{(n)}+\Sigma^{(n)})$ is called the Neural
Tangent Kernel (NTK) matrix of depth $n$ (and infinite width) over the set of
points $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$. The reader is referred to
[23] for more details on NTK.

In order to avoid heavy notation, we assume $||x_{t}||=1$ for all $t$. Matrix
$H$ is positive semi-definite by construction but, as is customary in the NTK
literature (e.g., [2, 9, 17]), we assume it is actually positive definite
(hence invertible) with smallest eigenvalue $\lambda_{0}>0$. This is a mild
assumption that can be shown to hold if no two vectors $x_{t}$ are aligned to
each other.

We measure the complexity of the function $h$ at hand in a way similar to
[44]. Using the same rearrangement of $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$
into $\\{x^{(i)}\\}_{i=1,\ldots,2T}$ as above, let $\mathbf{h}$ be the
$2T$-dimensional (column) vector whose $i$-th component is $h(x^{(i)})$. Then,
we define the complexity $S_{T,n}(h)$ of $h$ over
$\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$ w.r.t. an NTK of depth $n$ as
$S_{T,n}(h)=\sqrt{\mathbf{h}^{\top}H^{-1}\mathbf{h}}~{}.$ Notice that this
notion of (data-dependent) complexity is consistent with the theoretical
findings of [2], who showed that for a two-layer network the bound on the
generalization performance is dominated by
$\mathbf{y}^{\top}H^{-1}\mathbf{y}$, where $\mathbf{y}$ is the vector of
labels. Hence if $\mathbf{y}$ is aligned with the top eigenvectors of $H$ the
learning problem becomes easier. In our case, vector $\mathbf{h}$ plays the
role of vector $\mathbf{y}$. Also observe that $S^{2}_{T,n}(h)$ can in general
be as big as linear in $T$ (in which case learning becomes hopeless with our
machinery). In the special case where $h$ belongs to the RKHS induced by the
NTK, one can upper bound $S_{T,n}(h)$ by the norm of $h$ in the RKHS. The
complexity term $S_{T,n}(h)$ is typically unknown to the learning algorithm,
and it plays a central role in both regret and label complexity guarantees.
Hence the algorithm needs to learn this value as well during its online
functioning. Apparently, this aspect of the problem has been completely
overlooked by [44] (as well as by earlier references on contextual bandits in
RKHS, like [12]), where a (tight) upper bound on $S_{T,n}(h)$ is assumed to be
available in advance. We will cast the above as a model selection problem in
active learning, where we adapt and largely generalize to active learning the
regret balancing technique from [35, 34]. In what follows, we use the short-
hand $g(x;\theta)=\nabla_{\theta}f(x,\theta)~{}$ and, for a vector
$g\in\mathbb{R}^{p}$ and matrix $Z\in\mathbb{R}^{p\times p}$, we often write
$\sqrt{g^{\top}Zg}$ as $||g||_{Z}$, so that
$S_{T,n}(h)=||\mathbf{h}||_{H^{-1}}$.

###  2.1 Related work

The main effort in theoretical works in active learning is to obtain rates of
convergence of the population loss of the hypothesis returned by the algorithm
as a function of the number $N$ of requested labels. We emphasize that most of
these works, that heavily rely on approximation theory, are not readily
comparable to ours, since our goal here is not to approximate $h$ through a
DNN on the entire input domain, but only on the data at hand.

As we recalled in the introduction, in the parametric setting the convergence
rates are of the form $\nu\,N^{-1/2}+e^{-N}$, where $\nu$ is the population
loss of the best function in class $\mathcal{H}$. Hence, active learning rates
behave like the passive learning rate $N^{-1/2}$ when $\nu>0$, while fast
rates can only be achieved under very low noise ($\nu\approx 0$) conditions.
In this respect, relevant references include [20, 26] where, e.g., in the
realizable case (i.e., when the Bayes optimal classifier lies in
$\mathcal{H}$), minimax active learning rates of the form
$N^{-\frac{\alpha+1}{2}}$ are shown to hold for adaptive algorithms that do
not know beforehand the noise exponent $\alpha$. In non-parametric settings, a
comprehensive set of results has been obtained by [30], which builds on and
significantly improves over earlier results from [32]. Both papers work under
smoothness (Holder continuity/smoothness) assumptions. In addition, [32]
requires $\mathcal{D}_{\mathcal{X}}$ to be (quasi-)uniform on
$\mathcal{X}=[0,1]^{d}$. In [30] the minimax active learning rate
$N^{-\frac{\beta(\alpha+1)}{2\beta+d}}$ is shown to hold for $\beta$-Holder
classes, where exponent $\beta$ plays the role of the complexity of the class
of functions to learn, and $d$ is the input dimension. This algorithm is
adaptive to the complexity parameter $\beta$, and is therefore performing a
kind of model selection. Notice that minimax rates in the parametric regime
are recovered by setting $\beta\rightarrow\infty$. Of a somewhat similar
flavor is an earlier result by [26], where a convergence rate of the form
$N^{-\frac{\alpha+1}{2+\kappa\alpha}}$ is shown, being $\kappa$ the metric
entropy of the class (again, a notion of complexity). A refinement of the
results in [30] has recently been obtained by [33] where, following [11], a
more refined notion of smoothness for the Bayes classifier is adopted which,
however, also implies more restrictive assumptions on the marginal
distribution $\mathcal{D}_{\mathcal{X}}$.

Model selection of the scale of a Nearest-Neighbor-based active learning
algorithm is also performed in [27], whose main goal is to achieve data-
dependent rates based on the noisy-margin properties of the random sample at
hand, rather than those of the marginal distribution. Their active learning
rates are not directly comparable to ours and, unlike our paper, the authors
work in a pool-based scenario, where all unlabeled points are available
beforehand. Finally, an interesting investigation in active learning for over-
parametrized and interpolating regimes is contained in [24]. The paper
collects a number of interesting insights in active learning for 2-layer
Neural Networks and Kernel methods, but it restricts to either uniform
distributions on the input space or cases of well-clustered data points, with
no specific regret and query complexity guarantees, apart from very special
(though insightful) cases.

##  3 Basic Algorithm

Our first algorithm (Algorithm 1) uses randomly initialized, but otherwise
frozen, network weights (a more refined algorithm where the network weights
are updated incrementally is described and analyzed in the appendix).
Algorithm 1 is an adaptation to active learning of the neural contextual
bandit algorithm of [44], and shares similarities with an earlier selective
sampling algorithm analyzed in [16] for the linear case. The algorithm
generates network weights $\theta_{0}$ by independently sampling from Gaussian
distributions of appropriate variance, and then uses $\theta_{0}$ to stick
with a gradient mapping $\phi(\cdot)$ which will be kept frozen from beginning
to end. The algorithm also takes as input the complexity parameter
$S=S_{T,n}(h)$ of the underlying function $h$ satisfying (1). We shall later
on remove the assumption of the prior knowledge of $S_{T,n}(h)$. In
particular, removing the latter, turns out to be quite challenging from a
technical standpoint, and gives rise to a complex online model selection
algorithms for active learning in non-parametric regimes.

Input: Confidence level $\delta$, complexity parameter $S$, network width $m$,
and depth $n$ .

Initialization:

  * •

Generate each entry of $W_{k}$ independently from $\mathcal{N}(0,2/m)$, for
$k\in[n-1]$, and each entry of $W_{n}$ independently from
$\mathcal{N}(0,1/m)$;

  * •

Define $\phi(x)=g(x;\theta_{0})/\sqrt{m}$, where $\theta_{0}=\langle
W_{1},\ldots,W_{n}\rangle\in\mathbb{R}^{p}$ is the (frozen) weight vector of
the neural network so generated;

  * •

Set $Z_{0}=I\in\mathbb{R}^{p\times p}$, $b_{0}=0\in\mathbb{R}^{p}$ .

for  _$t=1,2,\ldots,T$_

Observe instance $x_{t}\in\mathcal{X}$ and build $x_{t,a}\in\mathcal{X}^{2}$,
for $a\in\mathcal{Y}$

Set
$\mathcal{C}_{t-1}=\\{\theta:\|\theta-\theta_{t-1}\|_{Z_{t-1}}\leq\frac{\gamma_{t-1}}{\sqrt{m}}\\}$,
with $\gamma_{t-1}=\sqrt{\log\det Z_{t-1}+2\log(1/\delta)}+S$

Set
$U_{t,a}=\sqrt{m}\max_{\theta\in\mathcal{C}_{t-1}}\langle\phi(x_{t,a}),\theta-\theta_{0}\rangle=\sqrt{m}\langle\phi(x_{t,a}),\theta_{t-1}-\theta_{0}\rangle+\gamma_{t-1}\|\phi(x_{t,a})\|_{Z_{t-1}^{-1}}$
Predict $a_{t}=\arg\max_{a\in\mathcal{Y}}U_{t,a}$

Set $I_{t}=\ 1{1}{\left\\{|U_{t,a_{t}}-1/2|\leq B_{t}\right\\}}\in\\{0,1\\}$
with $B_{t}=B_{t}(S)=2\gamma_{t-1}\|\phi(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}$

if  _$I_{t}=1$_

Query $y_{t}\in\mathcal{Y}$, and set loss $\ell_{t}=\ell(a_{t},y_{t})$

Update  $\displaystyle Z_{t}$
$\displaystyle=Z_{t-1}+\phi(x_{t,a_{t}})\phi(x_{t,a_{t}})^{\top}$
$\displaystyle b_{t}$ $\displaystyle=b_{t-1}+(1-\ell_{t})\phi(x_{t,a_{t}})$
$\displaystyle\theta_{t}$ $\displaystyle=Z_{t}^{-1}b_{t}/\sqrt{m}+\theta_{0}$

else

$Z_{t}=Z_{t-1}$, $b_{t}=b_{t-1}$, $\theta_{t}=\theta_{t-1}$,
$\gamma_{t}=\gamma_{t-1}$, $\mathcal{C}_{t}=\mathcal{C}_{t-1}$ .

Algorithm 1 Frozen NTK Selective Sampler.

At each round $t$, Algorithm 1 receives an instance $x_{t}\in\mathcal{X}$, and
constructs the two augmented vectors $x_{t,1}=(x_{t},0)$ and
$x_{t,-1}=(0,x_{t})$ (intuitively corresponding to the two “actions" of a
contextual bandit algorithm). The algorithm predicts the label $y_{t}$
associated with $x_{t}$ by maximizing over $a\in\mathcal{Y}$ an upper
confidence index $U_{t,a}$ stemming from the linear approximation
$h(x_{t,a})\approx\sqrt{m}\langle\phi(x_{t,a}),\theta_{t-1}-\theta_{0}\rangle$
subject to ellipsoidal constraints $\mathcal{C}_{t-1}$, as in standard
contextual bandit algorithms operating with the frozen mapping $\phi(\cdot)$.
In addition, in order to decide whether or not to query label $y_{t}$, the
algorithm estimates its own uncertainty by checking to what extent
$U_{t,a_{t}}$ is close to $1/2$. This uncertainty level is ruled by the time-
varying threshold $B_{t}$, which is expected to shrink to 0 as time
progresses. Notice that $B_{t}$ is a function of $\gamma_{t-1}$, which in turn
includes in its definition the complexity parameter $S$. Finally, if $y_{t}$
is revealed, the algorithm updates its least-squares estimator $\theta_{t}$ by
a rank-one adjustment of matrix $Z_{t}$ and an additive update to the bias
vector $b_{t}$. No update is taking place if the label is not queried. The
following is our initial building block.222 All proofs are in the appendix.

######  Theorem 1.

Let Algorithm 1 be run with parameters $\delta$, $S$, $m$, and $n$ on an
i.i.d. sample $(x_{1},y_{1}),\ldots,(x_{T},y_{T})\sim\mathcal{D}$, where the
marginal distribution $\mathcal{D}_{\mathcal{X}}$ fulfills the low-noise
condition with exponent $\alpha\geq 0$ w.r.t. a function $h$ that satisfies
(1) and such that $\sqrt{2}S_{T,n}(h)\leq S$. Then with probability at least
$1-\delta$ the cumulative regret $R_{T}$ and the total number of queries
$N_{T}$ are simultaneously upper bounded as follows:

$\displaystyle R_{T}$
$\displaystyle=O\biggl{(}L_{H}^{\frac{\alpha+1}{\alpha+2}}\Bigl{(}L_{H}+\log(\log
T/\delta)+S^{2}\Bigl{)}^{\frac{\alpha+1}{\alpha+2}}T^{\frac{1}{\alpha+2}}\biggr{)}$
$\displaystyle N_{T}$
$\displaystyle=O\biggl{(}L_{H}^{\frac{\alpha}{\alpha+2}}\Bigl{(}L_{H}+\log(\log
T/\delta)+S^{2}\Bigl{)}^{\frac{\alpha}{\alpha+2}}T^{\frac{2}{\alpha+2}}\biggr{)}~{},$

where $L_{H}=\log\det(I+H)$, $H$ being the NTK matrix of depth $n$ over the
set of points $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$.

The above bounds depend, beyond time horizon $T$, on three relevant
quantities: the noise level $\alpha$, the complexity parameters $S$ and the
log-determinant quantity $L_{H}$. Notice that, whereas $S$ essentially
quantifies the complexity of the function $h$ to be learned, $L_{H}$ measures
instead the complexity of the NTK itself, hence somehow quantifying the
complexity of the function space we rely upon in learning $h$. It is indeed
instructive to see how the bounds in the above theorem vary as a function of
these quantities. First, as expected, when $\alpha=0$ we recover the usual
regret guarantee $R_{T}=O(\sqrt{T})$, more precisely a bound of the form
$R_{T}=O((L_{H}+\sqrt{L_{H}}S)\sqrt{T})$, with the trivial label complexity
$N_{T}=O(T)$. At the other extreme, when $\alpha\rightarrow\infty$ we obtain
the guarantees $R_{T}=N_{T}=O(L_{H}(L_{H}+S^{2}))$. In either case, if $h$ is
“too complex" when projected onto the data, that is, if
$S^{2}_{T,n}(h)=\Omega(T)$, then all bounds become vacuous.333 The same
happens, e.g., to the regret bounds in [44].  At the opposite end of the
spectrum, if $\\{h\\}$ is simple, like a class of linear functions with
bounded norm in a $d$-dimensional space, and the network depth $n$ is 2 then
$S_{T,n}(h)=O(1)$, while $L_{H}=O(d\log T$), and we recover the rates reported
in [16] for the linear case. The quantity $L_{H}$ is tightly related to the
decaying rate of the eigenvalues of the NTK matrix $H$, and is poly-
logarithmic in $T$ in several important cases [41]. One relevant example is
discussed in [42], which relies on the spectral characterization of NTK in [7,
8]: If $n=2$ and all points $x^{(i)}$ concentrate on a $d_{0}$-dimensional
nonlinear subspace of the RKHS spanned by the NTK, then $L_{H}=O(d_{0}\log
T)$.

It is also important to stress that, via a standard online-to-batch
conversion, the result in Theorem 1 can be turned to a compelling guarantee in
a traditional statistical learning setting, where the goal is to come up at
the end of the $T$ rounds with a hypothesis $f$ whose population loss
$L(f)=\mathbb{E}_{x\sim D_{\mathcal{X}}}[L(f\,|\,x)]$ exceeds the Bayes
optimal population loss $\mathbb{E}_{x_{t}\sim
D_{\mathcal{X}}}[h(x_{t,a^{*}_{t}})]=\mathbb{E}_{x_{t}\sim
D_{\mathcal{X}}}[\max\\{h(x_{t,1}),h(x_{t,-1})\\}]$ by a vanishing quantity.
Following [16], this online-to-batch algorithm will simply run Algorithm 1 by
sweeping over the sequence $\\{(x_{t},y_{t})\\}_{t=1,\ldots,T}$ only once, and
pick one function uniformly at random among the sequence of predictors
generated by Algorithm 1 during its online functioning, that is, among the
sequence $\\{U_{t}(x)\\}_{t=1,\ldots,T}$, where
$U_{t}(x)=\arg\max_{a\in\mathcal{Y}}\max_{\theta\in\mathcal{C}_{t-1}}\langle\phi(x_{\cdot,a}),\theta-\theta_{0}\rangle$,
with $x_{\cdot,1}=(x,0)$ and $x_{\cdot,-1}=(0,x)$. This randomized algorithm
enjoys the following high-probability excess risk guarantee:444 Observe that
this is a data-dependent bound, in that the RHS is random variable. This is
because both $L_{H}$ and $S$ may depend on $x_{1},\ldots,x_{T}$.

$\mathbb{E}_{t\sim{\textrm{unif}}(T)}[L(U_{t})]-\mathbb{E}_{x_{t}\sim
D_{\mathcal{X}}}[h(x_{t,a^{*}_{t}})]=O\Biggl{(}\Biggl{(}\frac{L_{H}\Bigl{(}L_{H}+\log({\log
T}/\delta)+S^{2}\Bigl{)}}{T}\Biggl{)}^{\frac{\alpha+1}{\alpha+2}}+\,\frac{\log\log(T/\delta)}{T}\Biggl{)}~{}.$

Combining with the guarantee on the number of labels $N_{T}$ from Theorem 1
(and disregarding log factors), this allows us to conclude that the above
excess risk can be bounded as a function of $N_{T}$ as

$\Bigl{(}\frac{L_{H}(L_{H}+S^{2})}{N_{T}}\Bigl{)}^{\frac{\alpha+1}{2}}~{},$
(2)

where $L_{H}(L_{H}+S^{2})$ plays the role of a (compound) complexity term
projected onto the data $x_{1},\ldots,x_{T}$ at hand. When restricting to VC-
classes, the convergence rate $N_{T}^{-\frac{\alpha+1}{2}}$ is indeed the best
rate (minimax rate) one can achieve under the Mammen-Tsybakov low-noise
condition with exponent $\alpha$ (see, e.g., [10, 20, 26, 16]).

Yet, since we are not restricting to the parametric case, both $L_{H}$ and,
more importantly, $S^{2}$ can be a function of $T$. In such cases, the
generalization bound in (2) can still be expressed as a function of $N_{T}$
alone, For instance, when $L_{H}$ is poly-logarithmic in $T$ and
$S^{2}=O(T^{\beta})$, for some $\beta\in[0,1)$, one can easily verify that (2)
takes the form $N_{T}^{-\frac{(1-\beta)(\alpha+1)}{2+\beta\alpha}}$ (again, up
to log factors).

In Section A.3 of the appendix, we extend all our results to the case where
the network weights are not frozen, but are updated on the fly according to a
(stochastic) gradient descent procedure. In this case, in Algorithm 1 the
gradient vector $\phi(x)=g(x;\theta_{0})/\sqrt{m}$ will be replaced by
$\phi_{t}(x)=g(x;\theta_{t-1})/\sqrt{m}$, where $\theta_{t}$ is not the
linear-least squares estimator
$\theta_{t}=Z_{t}^{-1}b_{t}/\sqrt{m}+\theta_{0}$, as in Algorithm 1, but the
result of the DNN training on the labeled data $\\{(x_{k},y_{k})\,:\,k\leq
t,\,I_{k}=1\\}$ gathered so far.

##  4 Model Selection

Our model selection algorithm is described in Algorithm 2. The algorithm
operates on a pool of base learners of Frozen NTK selective samplers like
those in Algorithm 1, each member in the pool being parametrized by a pair of
parameters $(S_{i},d_{i})$, where $S_{i}$ plays the role of the (unknown)
complexity parameter $S_{T,n}(h)$ (which was replaced by $S$ in Algorithm 1),
and $d_{i}$ plays the role of an (a-priori unknown) upper bound on the
relevant quantity $\sum_{t\in T\,:\,i_{t}=i}\frac{1}{2}\wedge
I_{t,i}B_{t,i}^{2}$ that is involved in the analysis (see Lemma 5 and Lemma 7
in Appendix A.1). This quantity will at the end be upper bounded by a term of
the form $L_{H}(L_{H}+\log(\log T/\delta)+S^{2}_{T,n}(h))$, whose components
$L_{H}$ and $S^{2}_{T,n}(h)$ are initially unknown to the algorithm.

Algorithm 2 maintains over time a set $\mathcal{M}_{t}$ of active base
learners, and a probability distribution ${\mbox{\boldmath$p$}}_{t}$ over
them. This distribution remains constant throughout a sequence of rounds
between one change to $\mathcal{M}_{t}$ and the next. We call such sequence of
rounds an epoch. Upon observing $x_{t}$, Algorithm 2 selects which base
learner to rely upon in issuing its prediction $a_{t}$ and querying the label
$y_{t}$, by drawing base learner $i_{t}\in\mathcal{M}_{t}$ according to
${\mbox{\boldmath$p$}}_{t}$.

Then Algorithm 2 undergoes a series of carefully designed elimination tests
which are meant to rule out mis-specified base learners, that is, those whose
associated parameter $S_{i}$ is likely to be smaller than $S_{T,n}(h)$, while
retaining those such that $S_{i}\geq S_{T,n}(h)$. These tests will help keep
both the regret bound and the label complexity of Algorithm 2 under control.
Whenever, at the end of some round $t$, any such test triggers, that is, when
it happens that $|\mathcal{M}_{t+1}|<|\mathcal{M}_{t}|$ at the end of the
round, a new epoch begins, and the algorithm starts over with a fresh
distribution ${\mbox{\boldmath$p$}}_{t+1}\neq{\mbox{\boldmath$p$}}_{t}$.

The first test (“disagreement test") restricts to all active base learners
that would not have requested the label if asked. As our analysis for the base
selective sampler (see Lemma 8 in Appendix A.1) shows that a well-specified
base learner does not suffer (with high probability) any regret on non-queried
rounds, any disagreement among them reveals mis-specification, thus we
eliminate in pairwise comparison the base learner that holds the smaller
$S_{i}$ parameter. The second test (“observed regret test") considers the
regret behavior of each pair of base learners $i,j\in\mathcal{M}_{t}$ on the
rounds $k\leq t$ on which $i$ was selected $(i_{k}=i)$ and requested the label
$(I_{k,i}=1$), but $j$ would not have requested if asked ($I_{k,j}=0$), and
the predictions of the two happened to disagree on that round ($a_{k,i}\neq
a_{k,j}$). The goal here is to eliminate base learners whose cumulative regret
is likely to exceed the regret of the smallest well-specified learner, while
ensuring (with high probability) that any well-specified base learner $i$ is
not removed from the pool. In a similar fashion, the third test (“label
complexity test") is aimed at keeping under control the label complexity of
the base learners in the active pool $\mathcal{M}_{t}$. Finally, the last test
(“$d_{i}$ test") simply checks whether or not the candidate value $d_{i}$
associated with base learner $i$ remains a valid (and tight) upper bound on
$L_{H}(L_{H}+S^{2}_{T,n}(h))$.

Input: Confidence level $\delta$; probability parameter $\gamma\geq 0$; pool
of base learners $\mathcal{M}_{1}$, each identified with a pair
$(S_{i},d_{i})$; number of rounds $T$.

Set $L(t,\delta)=\log\frac{5.2\log(2t)^{1.4}}{\delta}$

for  _$t=1,2,\ldots,T$_

Observe instance $x_{t}\in\mathcal{X}$ and build $x_{t,a}\in\mathcal{X}^{2}$,
for $a\in\mathcal{Y}$

for  _$i\in\mathcal{M}_{t}$_

Set $I_{t,i}\in\\{0,1\\}$ as the indicator of whether base learner $i$ would
ask for label on $x_{t}$

Set $a_{t,i}\in\mathcal{Y}$ as the prediction of base learner $i$ on $x_{t}$

Let $B_{t,i}=B_{t,i}(S_{i})$ denote the query threshold of base learner $i$
(from Algorithm 1)

Select base learner
$i_{t}\sim{\mbox{\boldmath$p$}}_{t}=(p_{t,1},p_{t,2},\dots,p_{t,|\mathcal{M}_{t}|})$,
where
$p_{t,i}=\begin{cases}\frac{d_{i}^{-(\gamma+1)}}{\sum_{j\in\mathcal{M}_{t}}d_{j}^{-(\gamma+1)}},&\text{if
}i\in\mathcal{M}_{t}\\\ 0,&\text{otherwise}\end{cases}$

Predict $a_{t}=a_{t,i_{t}}$

if  _$I_{t,i_{t}}=1$_

Query label $y_{t}\in\mathcal{Y}$ and send $(x_{t},y_{t})$ to base learner
$i_{t}$

$\mathcal{M}_{t+1}=\mathcal{M}_{t}$

[2mm] Set $\mathcal{N}_{t}=\\{i\in\mathcal{M}_{t}\colon I_{t,i}=0\\}$ // (1)
Disagreement test

for  _all pairs of base learners $i,j\in\mathcal{N}_{t}$ that disagree in
their prediction ($a_{t,i}\neq a_{t,j}$)_

Eliminate all learners with smaller $S$:
$\mathcal{M}_{t+1}=\\{m\in\mathcal{M}_{t+1}\colon
S_{m}>\min\\{S_{i},S_{j}\\}\\}$

for  _all pairs of base learners $i,j\in\mathcal{M}_{t}$ _ // (2) Observed
regret test

Consider rounds where the chosen learner $i$ requested the label but $j$ did
not, and $i$ and $j$ disagree in their prediction:
$\displaystyle\mathcal{V}_{t,i,j}=\\{k\in[t]\colon
i_{k}=i,I_{k,i}=1,I_{k,j}=0,a_{k,i}\neq a_{k,j}\\}$ if  _
$\displaystyle\sum_{k\in\mathcal{V}_{t,i,j}}\\!\\!(\ 1{1}{\left\\{a_{k,i}\neq
y_{k}\right\\}}-\ 1{1}{\left\\{a_{k,j}\neq
y_{k}\right\\}})>\\!\\!\\!\\!\sum_{k\in\mathcal{V}_{t,i,j}}\\!\\!\\!(1\\!\wedge\\!B_{k,i})+1.45\sqrt{|{\mathcal{V}}_{t,i,j}|L(|{\mathcal{V}}_{t,i,j}|,\delta)}$
_

Eliminate base learner $i$:
$\mathcal{M}_{t+1}=\mathcal{M}_{t+1}\setminus\\{i\\}$

for  _$i\in\mathcal{M}_{t}$_ // (3) Label complexity test

Consider rounds where base learner $i$ was played:
$\displaystyle\mathcal{T}_{t,i}=\\{k\in[t]\colon i_{k}=i\\}$

if  _
$\displaystyle\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}>\inf_{\epsilon\in(0,1/2]}\biggl{(}3\epsilon^{\gamma}|\mathcal{T}_{t,i}|+\frac{1}{\epsilon^{2}}\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}^{2}\wedge\frac{1}{4}\biggr{)}+2L(|\mathcal{T}_{t,i}|,\delta/(M\log_{2}(12t)))$
_

Eliminate base learner $i$:
$\mathcal{M}_{t+1}=\mathcal{M}_{t+1}\setminus\\{i\\}$

for  _$i\in\mathcal{M}_{t}$ _ // (4) $d_{i}$ test

if  _ $\sum_{k\in\mathcal{T}_{t,i}}(\mbox{$\frac{1}{2}$}\wedge
I_{k,i}B_{k,i}^{2})>8d_{i}$ _

Eliminate base learner $i$:
$\mathcal{M}_{t+1}=\mathcal{M}_{t+1}\setminus\\{i\\}$

Algorithm 2 Frozen NTK Selective Sampler with Model Selection.

We have the following result, whose proof is contained in Appendix A.2.

######  Theorem 2.

Let Algorithm 2 be run with parameters $\delta$, $\gamma\leq\alpha$ with a
pool of base learners $\mathcal{M}_{1}$ of size $M$ on an i.i.d. sample
$(x_{1},y_{1}),\ldots,(x_{T},y_{T})\sim\mathcal{D}$, where the marginal
distribution $\mathcal{D}_{\mathcal{X}}$ fulfills the low-noise condition with
exponent $\alpha\geq 0$ w.r.t. a function $h$ that satisfies (1) and
complexity $S_{T,n}(h)$. Let also $\mathcal{M}_{1}$ contain at least one base
learner $i$ such that $\sqrt{2}S_{T,n}(h)\leq S_{i}\leq 2\sqrt{2}S_{T,n}(h)$
and $d_{i}=\Theta(L_{H}(L_{H}+\log(M\log T/\delta)+S^{2}_{T,n}(h)))$, where
$L_{H}=\log\det(I+H)$, being $H$ the NTK matrix of depth $n$ over the set of
points $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$. Then with probability at
least $1-\delta$ the cumulative regret $R_{T}$ and the total number of queries
$N_{T}$ are simultaneously upper bounded as follows:

$\displaystyle R_{T}$
$\displaystyle=O\left(M\,\Bigl{(}L_{H}\bigl{(}L_{H}+\log(M\log
T/\delta)+S^{2}_{T,n}(h)\bigl{)}\Bigl{)}^{\gamma+1}T^{\frac{1}{\gamma+2}}+M\,L(T,\delta)\right)$
$\displaystyle N_{T}$
$\displaystyle=O\left(M\,\Bigl{(}L_{H}\bigl{(}L_{H}+\log(M\log
T/\delta)+S^{2}_{T,n}(h)\bigl{)}\Bigl{)}^{\frac{\gamma}{\gamma+2}}T^{\frac{2}{\gamma+2}}+M\,L(T,\delta)\right)~{},$

where $L(T,\delta)$ is the logarithmic term defined at the beginning of
Algorithm 2’s pseudocode.

We run Algorithm 2 with the pool
$\mathcal{M}_{1}=\\{(S_{i_{1}},d_{i_{2}})\\}$, where $S_{i_{1}}=2^{i_{1}}$,
$i_{1}=0,1,\ldots,O(\log T)$ and $d_{i_{2}}=2^{i_{2}}$,
$i_{2}=0,1,\ldots,O(\log T+\log\log(M\log T/\delta))$, ensuring the existence
of a pair $(i_{1},i_{2})$ such that

$\sqrt{2}S_{T,n}(h)\leq S_{i_{1}}\leq 2\sqrt{2}S_{T,n}(h)$

and

$L_{H}\bigl{(}L_{H}+\log(M\log T/\delta)+S^{2}_{T,n}(h)\bigl{)}\leq
d_{i_{2}}\leq 2L_{H}\bigl{(}L_{H}+\log(M\log
T/\delta)+S^{2}_{T,n}(h)\bigl{)}~{}.$

Hence the resulting error due to the discretization is just a constant factor,
while the resulting number $M$ of base learners is $O(\log^{2}T+(\log
T)(\log\log(M\log T/\delta)))$.

Theorem 2 allows us to conclude that running Algorithm 2 on the above pool of
copies of Algorithm 1 yields guarantees that are similar to those obtained by
running a single instance of Algorithm 1 with $S=\sqrt{2}S_{T,n}(h)$, that is,
as if the complexity parameter $S_{T,n}(h)$ were known beforehand. Yet, this
model selection guarantee comes at a price, since Algorithm 2 needs to receive
as input the noise exponent $\alpha$ (through parameter $\gamma\leq\alpha$) in
order to correctly shape its label complexity test.

The very same online-to-batch conversion mentioned in Section 3 can be applied
to Algorithm 2. Again, combining with the bound on the number of labels and
disregarding log factors, this gives us a high probability excess risk bound
of the form

$\left(\frac{\left[L_{H}\left(L_{H}+S^{2}_{T,n}(h)\right)\right]^{\frac{3\alpha+2}{\alpha+2}}}{N_{T}}\right)^{\frac{\alpha+1}{2}}~{},$
(3)

provided $\gamma=\alpha$. Following the same example as at the end of Section
3, when $L_{H}$ is poly-logarithmic in $T$ and $S^{2}=O(T^{\beta})$, for some
$\beta\in[0,1)$, one can verify that (3) is of the form
$N_{T}^{-\frac{(1-\beta(\alpha+1))(\alpha+1)}{2+\beta\alpha}}$ (up to log
factors), which converges for $\beta<1/(\alpha+1)$. Hence, compared to (2) we
can ensure convergence in a more restricted set of cases.

Section A.3 in the appendix contains the extension of our model selection
procedure to the case where the network weights are themselves updated.

##  5 Conclusions and Work in Progress

We have presented a rigorous analysis of selective sampling and active
learning in general non-parametric scenarios, where the complexity of the
Bayes optimal predictor is evaluated on the data at hand as a fitting measure
with respect to the NTK matrix of a given depth associated with the same data.
This complexity measure plays a central role in the level of uncertainty the
algorithm assigns to labels (the higher the complexity the higher the
uncertainty, hence the more labels are queried). Yet, since this is typically
an unknown parameter of the problem, special attention is devoted to designing
and analyzing a model selection technique that adapts to this unknown
parameter.

In doing so, we borrowed tools and techniques from Neural Bandits [44, 42],
selective sampling (e.g., [16]), and online model selection in contextual
bandits [35, 34], and combined them together in an original and non-trivial
manner.

We proved regret and label complexity bounds that recover known minimax rates
in the parametric case, and extended such results well beyond the parametric
setting achieving favorable guarantees that cannot easily be compared to
available results in the literature of active learning in non-parametric
settings. One distinctive feature of our proposed technique is that it gives
rise to efficient and manageable algorithms for modular DNN architecture
design and deployment.

We conclude by mentioning a few directions we are currently exploring:

  1. 1.

We are trying to get rid of the prior knowledge of $\alpha$ in the model
selection Algorithm 2. This may call for a slightly more refined balancing
technique that jointly involves $S_{T,n}(h)$ and $\alpha$ itself.

  2. 2.

Regardless of whether $\alpha$ is available, it would be nice to improve the
dependence on $\gamma=\alpha$ in the regret bound of Theorem 2. This would
ensure convergence of the generalization bound as $N_{T}\rightarrow\infty$
when $S_{T,n}(h)^{2}=T^{\beta}$, for all $\beta\in[0,1)$. We conjecture that
this is due to a suboptimal design of our balancing mechanism for model
selection in Algorithm 2.

  3. 3.

We are investigating links between the complexity measure $S_{T,n}(h)$ and the
smoothness properties of the (Bayes) regression function $h$ with respect to
the NTK kernel (of a given depth $n$).

## References

  * [1] Y. Abbasi-yadkori, D. Pál, and C. Szepesvári.  Improved algorithms for linear stochastic bandits.  In Advances in Neural Information Processing Systems 24, pages 2312–2320. Curran Associates, Inc., 2011.
  * [2] S. Arora, S. S. Du, W. Hu, Z. Li, R. Salakhutdinov, and R. Wang.  On exact computation with an infinitely wide neural net.  In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
  * [3] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal.  Deep batch active learning by diverse, uncertain gradient lower bounds.  arXiv preprint arXiv:1906.03671, 2019.
  * [4] M. Balcan, A. Beygelzimer, and J. Langford.  Agnostic active learning.  Journal of Computer and System Sciences, 75(1):78–89, 2009.
  * [5] N. Balcan, S. Hanneke, and J. Wortman.  The true sample complexity of active learning.  In COLT, 2008.
  * [6] A. Beygelzimer, S. Dasgupta, and J. Langford.  Importance weighted active learning.  In ICML, 2009.
  * [7] A. Bietti and J. Mairal.  On the inductive bias of neural tangent kernels.  In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
  * [8] Y. Cao, Z. Fang, Y. Wu, D. Zhou, and Q. Gu.  Towards understanding the spectral bias of deep learning.  In arXiv:1912.01198, 2019.
  * [9] Y. Cao and Q. Gu.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
  * [10] R. Castro and R. Nowak.  Minimax bounds for active learning.  IEEE Transactions on Information Theory, 54(5):2339–2353, 2008\.
  * [11] K. Chaudhuri and S. Dasgupta.  Rates of convergence for nearest neighbor classification.  In Advances in Neural Information Processing Systems, pages 3437–3445, 2014.
  * [12] S. R. Chowdhury and A. Gopalan.  On kernelized multi-armed bandits.  In Proceedings of the 34th International Conference on Machine Learning, 2017.
  * [13] D. Cohn, L. Atlas, and R. Ladner.  Improving generalization with active learning.  Machine learning, 15(2):201–221, 1994.
  * [14] I. Dagan and S. P. Engelson.  Committee-based sampling for training probabilistic classifiers.  In Machine Learning Proceedings 1995, pages 150–157. Elsevier, 1995\.
  * [15] S. Dasgupta, D. Hsu, and C. Monteleoni.  A general agnostic active learning algorithm.  In Advances in Neural Information Processing Systems, 2007.
  * [16] O. Dekel, C. Gentile, and K. Sridharan.  Selective sampling and active learning from single and multiple teachers.  J. Mach. Learn. Res., 13(1), 2012.
  * [17] 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, page 1675–1685, 2019.
  * [18] S. Du, J. Lee, Y. Tian, A. Singh, and B. Poczos.  Gradient descent learns one-hidden-layer CNN: Don’t be afraid of spurious local minima.  In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1339–1348. PMLR, 2018.
  * [19] S. Hanneke.  A bound on the label complexity of agnostic active learning.  In ICML, 2007.
  * [20] S. Hanneke.  Adaptive rates of convergence in active learning.  In Proc. of the 22th Annual Conference on Learning Theory, 2009\.
  * [21] S. Hanneke et al.  Theory of disagreement-based active learning.  Foundations and Trends® in Machine Learning, 7(2-3):131–309, 2014.
  * [22] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon.  Time-uniform, nonparametric, nonasymptotic confidence sequences.  arXiv preprint arXiv:1810.08240, 2018.
  * [23] A. Jacot, F. Gabriel, and C. Hongler.  Neural tangent kernel: convergence and generalization in neural networks.  In Advances in neural information processing systems, page 8571–8580. MIT Press, 2018.
  * [24] M. Karzand and R. Nowak.  Maximin active learning in overparameterized model classes.  In arXiv:1905.12782v2. 2020.
  * [25] A. Kirsch, J. Van Amersfoort, and Y. Gal.  Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning.  arXiv preprint arXiv:1906.08158, 2019.
  * [26] V. Koltchinskii.  Rademacher complexities and bounding the excess risk of active learning.  Journal of Machine Learning Research, 11:2457–2485, 2010.
  * [27] A. Kontorovich, S. Sabato, and R. Urner.  Active nearest-neighbor learning in metric spaces.  In Advances in Neural Information Processing Systems, pages 856–864, 2016.
  * [28] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [29] D. D. Lewis and W. A. Gale.  A sequential algorithm for training text classifiers.  In SIGIR’94, pages 3–12. Springer, 1994.
  * [30] C. A. Locatelli A. and S. Kpotufe.  Adaptivity to noise parameters in nonparametric active learning.  In Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 1383–1416, 2017.
  * [31] E. Mammen and A. Tsybakov.  Smooth discrimination analysis.  The Annals of Statistics, 27(6):1808–1829, 1999.
  * [32] S. Minsker.  Plug-in approach to active learning.  Journal of Machine Learning Research, 13:67–90, 2012.
  * [33] B. Njike and X. Siebert.  Nonparametric adaptive active learning under local smoothness condition.  In arxiv: 2102.11077. 2021.
  * [34] A. Pacchiano, C. Dann, G. C., and P. Bartlett.  Regret bound balancing and elimination for model selection in bandits and RL.  arXiv preprint arXiv:2012.13045, 2020.
  * [35] A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, T. Lattimore, and C. Szepesvari.  Model selection in contextual stochastic bandit problems.  In Advances in Neural Information Processing Systems, volume 33, pages 10328–10337. Curran Associates, Inc., 2020.
  * [36] R. Pop and P. Fulop.  Deep ensemble bayesian active learning: Addressing the mode collapse issue in monte carlo dropout via ensembles.  arXiv preprint arXiv:1811.03897, 2018.
  * [37] M. Raginsky and A. Rakhlin.  Lower bounds for passive and active learning.  In Advances in Neural Information Processing Systems, 2011.
  * [38] O. Sener and S. Savarese.  Active learning for convolutional neural networks: A core-set approach.  arXiv preprint arXiv:1708.00489, 2017.
  * [39] B. Settles.  Active learning literature survey.  2009\.
  * [40] L. G. Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [41] M. Valko, N. Korda, R. Munos, I. Flaounas, and N. Cristianini.  Finite-time analysis of kernelised contextual bandits.  In arxiv:1309.6869. 2013.
  * [42] W. Zhang, D. Zhou, L. Li, and Q. Gu.  Neural thompson sampling.  In arXiv:2010.00827. 2020.
  * [43] F. Zhdanov.  Diverse mini-batch active learning.  arXiv preprint arXiv:1901.05954, 2019.
  * [44] D. Zhou, L. Li, and Q. Gu.  Neural contextual bandits with ucb-based exploration.  In Proceedings of the 37th International Conference on Machine Learning, 2020.

##  Appendix A Appendix

This appendix contains, beyond the proof of all results contained in the main
body (Section A.1 and Section A.2), the extension of our model selection
results to the non-frozen NTK case (Section A.3). Section A.4 contains
ancillary technical lemmas used throughout the proofs.

###  A.1 Proofs for Section 3

We first recall the following representation theorem (which is Lemma 5.1 in
[44]). We give a proof sketch for completeness.

######  Lemma 1.

There exists a positive constant $C$ such that for any $\delta\in(0,1)$, if

$m\geq CT^{4}n^{6}\log(2Tn/\delta)/\lambda_{0}^{4}$

then with probability at least $1-\delta$ over the random initialization
$\theta_{0}$, there exists $\theta^{*}\in\mathbb{R}^{p}$ for which

$\displaystyle h(x_{t,a})=\langle
g(x_{t,a};\theta_{0}),\theta^{*}-\theta_{0}\rangle\qquad{\mbox{and}}\qquad\sqrt{m}\,\|\theta^{*}-\theta_{0}\|_{2}\leq\sqrt{2}S_{T,n}(h)$
(4)

for all $t\in[T]$, $a\in\mathcal{Y}$, and $h$.

###### Proof.

Recall the rearrangement of $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$ into
$\\{x^{(i)}\\}_{i=1,\ldots,2T}$. We define the $p\times 2T$ matrix
$G=\left[\phi(x^{(1)}),\ldots,\phi(x^{(2T)})\right]$. For
$m=\Omega(T^{4}n^{6}\log(2Tn/\delta)/\lambda_{0}^{4})$, we have
$\|G^{\top}G-H\|_{F}\leq\lambda_{0}/2$ with probability at least $1-\delta$
over the random initialization over $\theta_{0}$, which is based on a union
bound over Theorem 3.1 in [2]. Since $H$ on $\\{x^{(i)}\\}_{i=1,\ldots,2T}$ is
positive definite with smallest eigenvalue $\lambda_{0}$, $G^{\top}G$ is also
positive definite. Let the singular value decomposition of $G$ be
$G=PAQ^{\top}$, $P\in\mathbb{R}^{p\times 2T}$, $A\in\mathbb{R}^{2T\times 2T}$,
$Q\in\mathbb{R}^{2T\times 2T}$, then $A$ is also positive definite. We define

$\theta^{*}=\theta_{0}+PA^{-1}Q^{\top}\mathbf{h}/\sqrt{m}~{}.$

It is easy to see that $\theta^{*}$ satisfies (4), hence concluding the proof.
∎

Next we present a lemma relating the matrix $Z_{T}$ with NTK matrix $H$.

######  Lemma 2.

There exists a positive constant $C$ such that for any $\delta\in(0,1)$, if

$m\geq CT^{6}n^{6}\log(Tn/\delta)$

then with probability at least $1-\delta$ over the random initialization
$\theta_{0}$ we have

$\displaystyle\log\det Z_{T}\leq\log\det(I+H)+1~{}.$ (5)

###### Proof.

The proof is an adaptation of the proof of Lemma 5.4 in [44]. Let
$G=(\phi(x^{(1)},...,\phi(x^{(2T)}))\in\mathbb{R}^{p\times 2T}$. We can write

$\displaystyle\log\det Z_{T}$
$\displaystyle=\log\det\left(I+\sum_{t=1}^{T}I_{t}\phi(x_{t,a_{t}})\phi(x_{t,a_{t}})^{\top}\right)$
$\displaystyle\leq\log\det\left(I+\sum_{i=1}^{2T}\phi(x^{(i)})\phi(x^{(i)})^{\top}\right)$
$\displaystyle=\log\det\bigl{(}I+GG^{\top}\bigr{)}$
$\displaystyle=\log\det\bigl{(}I+G^{\top}G\bigr{)}$
$\displaystyle=\log\det\bigl{(}I+H+(G^{\top}G-H)\bigr{)}$
$\displaystyle\leq\log\det\bigl{(}I+H)+\langle(I+H)^{-1},(G^{\top}G-H)\rangle_{F}$
$\displaystyle\leq\log\det\bigl{(}I+H)+\|(I+H)^{-1}\|_{F}\|G^{\top}G-H\|_{F}$
$\displaystyle\leq\log\det\bigl{(}I+H)+\sqrt{2T}\,\|G^{\top}G-H\|_{F}$
$\displaystyle\leq\log\det(I+H)+1~{}.$

In the above, the first inequality is obvious, the second inequality uses the
fact that $\log\det(\cdot)$ is a concave function, the third one used Cauchy-
Schwartz inequality, the fourth one comes from
$\|(I+H)^{-1}\|_{F}\leq\|I\|_{F}=\sqrt{2T}$, and the last inequality uses
Lemma B.1 in [44] along with our choice of $m$. ∎

The proofs of both Lemma 1 and Lemma 2 rely on controlling the size of
$\|G^{\top}G-H\|_{F}$, which is small with high probability when $m$ is large
enough. Therefore, given

$m\geq CT^{4}\log(2Tn/\delta)n^{6}\left(T^{2}\vee
1/\lambda_{0}^{4}\right)~{},$

we have

$\displaystyle\mathcal{E}_{0}=\\{\exists\,\theta^{*}\in\mathbb{R}^{p}\,:\,(\ref{eqn:representation
formula})\ {\mbox{and}}\ (\ref{ineq:bounding Z_T by H})\ {\mbox{hold}}\\}~{},$
(6)

holds with probability at least $1-\delta$ over random initialization of
$\theta_{0}$.

To take into account the random noise from the sequence of labels, we also
define

$\displaystyle\mathcal{E}=\\{\exists\,\theta^{*}\in\mathbb{R}^{p}\,:\,\mathcal{E}_{0}\
{\mbox{holds and }}\theta^{*}\in\mathcal{C}_{t}\ \forall t>0\\}~{}.$ (7)

In order to make sense of the querying threshold $B_{t}$ in Algorithm 1, we
derive an upper and a lower bound for $U_{t,a}-h(x_{t,a})$ under
$\mathcal{E}$.

As for the lower bound, simply notice that, by definition ,

$\displaystyle U_{t,a}=\max_{\theta\in\mathcal{C}_{t-1}}\langle
g(x_{t,a};\theta_{0}),\theta-\theta_{0}\rangle\geq\langle
g(x_{t,a};\theta_{0}),\theta^{*}-\theta_{0}\rangle=h(x_{t,a})~{}.$ (8)

To derive an upper bound, we can write

$\displaystyle U_{t,a}-h(x_{t,a})$
$\displaystyle=\max_{\theta\in\mathcal{C}_{t-1}}\langle
g(x_{t,a};\theta_{0}),\theta-\theta_{0}\rangle-\langle
g(x_{t,a};\theta_{0}),\theta^{*}-\theta_{0}\rangle$
$\displaystyle=\max_{\theta\in\mathcal{C}_{t-1}}\langle
g(x_{t,a};\theta_{0}),\theta-\theta_{t-1}\rangle-\langle
g(x_{t,a};\theta_{0}),\theta^{*}-\theta_{t-1}\rangle$
$\displaystyle\leq\max_{\theta\in\mathcal{C}_{t-1}}\|g(x_{t,a};\theta_{0})\|_{Z_{t-1}^{-1}}\Bigl{(}\|\theta-\theta_{t-1}\|_{Z_{t-1}}+\|\theta^{*}-\theta_{t-1}\|_{Z_{t-1}}\Bigl{)}$
$\displaystyle\leq 2\gamma_{t-1}\|\phi(x_{t,a})\|_{Z_{t-1}^{-1}}~{},$ (9)

where in the last inequality we used the definition of $\mathcal{C}_{t-1}$ and
the assumption that $\theta^{*}\in\mathcal{C}_{t-1}$. A proof of this
assumption is contained in the below lemma, which follows from standard
arguments.

######  Lemma 3.

Let the input parameter $S$ in Algorithm 1 be such that
$\sqrt{2}S_{T,n}(h)\leq S$, then under event $\mathcal{E}_{0}$ for any
$\delta>0$, with probability at least $1-\delta$ over the random noises we
have

$\|\theta^{*}-\theta_{t}\|_{Z_{t}}\leq\gamma_{t}/\sqrt{m}$

for all $t\geq 0$ simultaneously, i.e., $\theta^{*}\in\mathcal{C}_{t}$ with
high probability simultaneously for all $t\geq 0$.

###### Proof.

We essentially follow the proof of Theorem 2 in [1] (see also the proof of
Lemma 5.2 in [44]).

We have $\ell_{t}=1-h(x_{t,a_{t}})-\xi_{t}$, where
$\xi_{t}=1-\ell_{t}-h(x_{t,a_{t}})$ is a sub-Gaussian random variable. Hence,
setting $\bm{\xi}_{t}=(I_{1}\xi_{1},...,I_{t}\xi_{t})^{\top}$,
$X_{t}=(I_{1}\phi(x_{1,a_{1}}),...,I_{t}\phi(x_{t,a_{t}}))^{\top}$, and
$Y_{t}=(I_{1}(1-\ell_{1}),...,I_{t}(1-\ell_{t}))^{\top}$, we can write

$Z_{t}=X_{t}^{\top}X_{t}+I,\qquad b_{t}=X_{t}^{\top}Y_{t}$

Plug them into the definition of $\theta_{t}$ gives

$\displaystyle\theta_{t}-\theta_{0}$ $\displaystyle=Z_{t}^{-1}b_{t}/\sqrt{m}$
$\displaystyle=(X_{t}^{\top}X_{t}+I)^{-1}X_{t}^{\top}(\sqrt{m}X_{t}(\theta^{*}-\theta_{0})+\bm{\xi}_{t})/\sqrt{m}$
$\displaystyle=(X_{t}^{\top}X_{t}+I)^{-1}X_{t}^{\top}\bm{\xi}_{t}/\sqrt{m}+\theta^{*}-\theta_{0}-(X_{t}^{\top}X_{t}+I)^{-1}(\theta^{*}-\theta_{0})~{},$

where in the first equality we used definition of $\xi_{t}$ and Lemma 1. Now,
for any $x\in\mathbb{R}^{p}$, we get

$\displaystyle x^{\top}(\theta_{t}-\theta^{*})=\langle
x,X_{t}^{\top}\bm{\xi}_{t}\rangle_{Z_{t}^{-1}}/\sqrt{m}-\langle
x,\theta^{*}-\theta_{0}\rangle_{Z_{t}^{-1}}~{},$

hence

$\displaystyle|x^{\top}(\theta_{t}-\theta^{*})|$
$\displaystyle\leq\|x\|_{Z_{t}^{-1}}\Bigl{(}\|X_{t}^{\top}\bm{\xi}_{t}\|_{Z_{t}^{-1}}/\sqrt{m}+\|\theta^{*}-\theta_{0}\|_{Z_{t}^{-1}}\Bigl{)}$
$\displaystyle\leq\|x\|_{Z_{t}^{-1}}\Bigl{(}\|X_{t}^{\top}\bm{\xi}_{t}\|_{Z_{t}^{-1}}/\sqrt{m}+\|\theta^{*}-\theta_{0}\|_{2}\Bigl{)}~{},$

where the first inequality derives from the Cauchy-Schwartz inequality and the
second from the fact that the smallest eigenvalue of $Z_{t}$ is at least $1$.
Then, by Theorem 1 in [1], for any $\delta$ with probability at least
$1-\delta$ over the random noises

$\|X_{t}^{\top}\bm{\xi}_{t}\|_{Z_{t}^{-1}}\leq\sqrt{\log\biggl{(}\frac{\det(Z_{t})}{\delta^{2}}\biggr{)}}~{}.$

Therefore, when $\mathcal{E}_{0}$ holds, we have for all $t>0$, with
probability at least $1-\delta$,

$|x^{\top}(\theta_{t}-\theta^{*})|\leq\|x\|_{Z_{t}^{-1}}\left(\sqrt{\log\biggl{(}\frac{\det(Z_{t})}{\delta^{2}}\biggr{)}/m}+\sqrt{2}S_{T,n}(h)/\sqrt{m}\right)~{}.$

Plugging in $x=Z_{t}(\theta_{t}-\theta^{*})$ and using $\sqrt{2}S_{T,n}(h)\leq
S$, we obtain

$\|\theta^{*}-\theta_{t}\|_{Z_{t}}\leq\sqrt{\log\biggl{(}\frac{\det(Z_{t})}{\delta^{2}}\biggr{)}/m}+S/\sqrt{m}=\gamma_{t}/\sqrt{m}~{},$

as claimed. ∎

Combining Lemma 1, 2 and 3 we confirm that $\mathcal{E}$ is a high probability
event.

######  Lemma 4.

There exists a constant $C$ such that if $m\geq
CT^{4}\log(2Tn/\delta)n^{6}\left(T^{2}\vee 1/\lambda_{0}^{4}\right)$ and
$\sqrt{2}S_{T,n}(h)\leq S$, then

$\displaystyle\mathbb{P}(\mathcal{E})\geq 1-2\delta~{}.$ (10)

###### Proof.

Lemma 1 and 2 imply that $\mathbb{P}(\mathcal{E}_{0})\geq 1-\delta$ when
$m\geq CT^{4}\log(2Tn/\delta)n^{6}\left(T^{2}\vee 1/\lambda_{0}^{4}\right)$.
Lemma 3 implies that when $\sqrt{2}S_{T,n}(h)\leq S$,
$\mathbb{P}(\theta^{*}\in\mathcal{C}_{t}\ \forall t>0\mid\mathcal{E}_{0})\geq
1-\delta$. Therefore,

$\mathbb{P}(\mathcal{E})=\mathbb{P}(\theta^{*}\in\mathcal{C}_{t}\ \forall
t>0\mid\mathcal{E}_{0})\mathbb{P}(\mathcal{E}_{0})\geq(1-\delta)^{2}\geq
1-2\delta~{}.$

∎

######  Lemma 5.

For any $b>0$ we have

$\sum_{t=1}^{T}b\wedge I_{t}B_{t}^{2}\leq 8\left(\log\det
Z_{T}+2\log(1/\delta)+S^{2}+\frac{b}{8}\right)\log\det Z_{T}~{}.$ (11)

###### Proof.

By definition of $B_{t}$ and the fact that $\gamma_{t}$ is increasing, we have

$\sum_{t=1}^{T}b\wedge I_{t}B_{t}^{2}\leq
4\gamma_{T}^{2}\sum_{t=1}^{T}\frac{b}{4\gamma_{T}^{2}}\wedge
I_{t}\|\phi(x_{t,a_{t}})\|_{{Z}_{t-1}^{-1}}^{2}\leq(b+4\gamma_{T}^{2})\log\det
Z_{T}~{},$

where the second inequality is from Lemma 24. Using the definition of
$\gamma_{T}$ and the inequality $(a+b)^{2}\leq 2a^{2}+2b^{2}$ we obtain

$\gamma_{T}^{2}\leq 2\log\det Z_{T}+4\log(1/\delta)+2S^{2}~{}.$

Plugging this in we get (11). ∎

Let us now introduce the short-hand notation

$\displaystyle\widehat{\Delta}_{t}=U_{t,a_{t}}-1/2~{},\qquad\Delta_{t}=h(x_{t,a_{t}})-1/2~{},\qquad
T_{\epsilon}=\sum_{t=1}^{T}\
1{1}{\left\\{\Delta_{t}^{2}\leq\epsilon^{2}\right\\}}~{},$

for some $\epsilon\in(0,\frac{1}{2})$. Combined with (8) and (9), we have the
following statement about $\widehat{\Delta}_{t}$ and $\Delta_{t}$.

######  Lemma 6.

Under event $\mathcal{E}$, $0\leq\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}$
and $\ 0\leq\widehat{\Delta}_{t}$ hold for all $t$, where $B_{t}$ is the
querying threshold in Algorithm 1, i.e.,

$B_{t}=2\gamma_{t-1}\|\phi(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}~{}.$

###### Proof.

Recalling that (8) and (9) implies that for $a\in\mathcal{Y}$

$0\leq U_{t,a}-h(x_{t,a})\leq B_{t}~{}.$

Specifically when $a=a_{t}$,

$0\leq\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}~{}.$

Also using (8) we have $U_{t,1}+U_{t,-1}\geq h(x_{t,1})+h(x_{t,-1})=1$. Hence,
by definition of $a_{t}$, $U_{t,a_{t}}\geq 1/2$, i.e.,
$\widehat{\Delta}_{t}\geq 0$. ∎

The following lemma bounds the label complexity $N_{T}$ of Algorithm 1 under
event $\mathcal{E}$. Notice that, as stated, the bound does not depend on any
specific properties of the marginal distribution $\mathcal{D}_{\mathcal{X}}$.

######  Lemma 7.

Under event $\mathcal{E}$, for any $\epsilon\in(0,1/2)$ we have

$\displaystyle N_{T}$ $\displaystyle\leq
T_{\epsilon}+\frac{8}{\epsilon^{2}}(\log\det
Z_{T}+2\log(1/\delta)+S^{2}+\frac{1}{32})\log\det Z_{T}$
$\displaystyle=O\left(T_{\epsilon}+\frac{1}{\epsilon^{2}}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\log\det(I+H)\right)~{}.$

###### Proof.

We adapt the proof of Lemma 6 in [16]. Assume $\mathcal{E}$ holds. Since
$0\leq\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}$ and $\widehat{\Delta}_{t}\geq
0$ by Lemma 6, $\hat{\Delta}_{t}\leq B_{t}$ implies $|\Delta_{t}|\leq B_{t}$.
We can write

$\displaystyle I_{t}$ $\displaystyle=I_{t}\ 1{1}{\left\\{\hat{\Delta}_{t}\leq
B_{t}\right\\}}$ $\displaystyle\leq I_{t}\ 1{1}{\left\\{\hat{\Delta}_{t}\leq
B_{t},B_{t}\geq\epsilon\right\\}}+I_{t}\ 1{1}{\left\\{\widehat{\Delta}_{t}\leq
B_{t},B_{t}<\epsilon\right\\}}$
$\displaystyle\leq\frac{I_{t}B_{t}^{2}}{\epsilon^{2}}\wedge 1+\
1{1}{\left\\{\Delta_{t}^{2}\leq\epsilon^{2}\right\\}}~{}.$

For the first term, summing over $t$ yields

$\displaystyle\frac{1}{\epsilon^{2}}\sum_{t=1}^{T}I_{t}B_{t}^{2}\wedge\epsilon^{2}$
$\displaystyle\leq\frac{1}{\epsilon^{2}}\sum_{t=1}^{T}I_{t}B_{t}^{2}\wedge\frac{1}{4}$
$\displaystyle\leq\frac{8}{\epsilon^{2}}\left(\log\det
Z_{T}+2\log(1/\delta)+S^{2}+\frac{1}{32}\right)\log\det Z_{T}$
$\displaystyle=O\left(\frac{1}{\epsilon^{2}}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\log\det(I+H)\right)~{},$

where the second bound follows from Lemma 5, and the last bound holds under
event $\mathcal{E}$. ∎

The next lemma shows that on rounds where Algorithm 1 does not issue a query,
we are confident that our prediction $a_{t}$ suffers no regret.

######  Lemma 8.

Under event $\mathcal{E}$, for the rounds $t$ such that $I_{t}=0$, we have
$a_{t}=a_{t}^{*}$, that is, Algorithm 1 suffers no regret.

###### Proof.

We apply Lemma 6, when $I_{t}=0$ this yields $\widehat{\Delta}_{t}>B_{t}$. As
a consequence of the condition $\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}$, we
get $\Delta_{t}>0$, which in turn entails $a_{t}=a_{t}^{*}$. ∎

The next lemma establishes an upper bound on the cumulative regret $R_{T}$ in
the same style as in Lemma 7.

######  Lemma 9.

Under event $\mathcal{E}$, for any $\epsilon\in(0,1/2)$ we have

$\displaystyle R_{T}$ $\displaystyle\leq 2\epsilon
T_{\epsilon}+\frac{16}{\epsilon}\left(\log\det{Z}_{T}+2\log(1/\delta)+S^{2}+\frac{1}{16}\right)\log\det{Z}_{T}$
$\displaystyle=O\left(\epsilon
T_{\epsilon}+\frac{1}{\epsilon}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\,\log\det(I+H)\right)~{}.$

###### Proof.

By virtue of Lemma 8, we can restrict with high probability to the rounds $t$
on which $I_{t}=1$. We have

$\displaystyle R_{T}$
$\displaystyle=\sum_{t=1}^{T}I_{t}\bigl{(}h(x_{t,a_{t}^{*}})-h(x_{t,a_{t}})\bigr{)}$
$\displaystyle=\sum_{t=1}^{T}I_{t}\bigl{(}h(x_{t,a_{t}^{*}})-h(x_{t,a_{t}})\bigr{)}\
1{1}{\left\\{a_{t}\neq a_{t}^{*}\right\\}}$
$\displaystyle\leq\sum_{t=1}^{T}I_{t}\bigl{|}h(x_{t,1})-h(x_{t,-1})\bigr{|}\
1{1}{\left\\{a_{t}\neq a_{t}^{*}\right\\}}$
$\displaystyle=2\,\sum_{t=1}^{T}I_{t}|\Delta_{t}|$
$\displaystyle=2\sum_{t=1}^{T}I_{t}|\Delta_{t}|\
1{1}{\left\\{|\Delta_{t}|>\epsilon\right\\}}+2\sum_{t=1}^{T}I_{t}|\Delta_{t}|\
1{1}{\left\\{|\Delta_{t}|\leq\epsilon\right\\}}~{}.$

The second sum is clearly upper bounded by $2\epsilon T_{\epsilon}$. As for
the first sum, notice that Lemma 6 along with $I_{t}=1$ implies
$|\Delta_{t}|\leq B_{t}$ under event $\mathcal{E}$. Therefore

$\displaystyle 2\sum_{t=1}^{T}I_{t}|\Delta_{t}|\
1{1}{\left\\{|\Delta_{t}|>\epsilon\right\\}}$
$\displaystyle\leq\frac{2}{\epsilon}\sum_{t=1}^{T}I_{t}\Delta_{t}^{2}\wedge\epsilon$
$\displaystyle\leq\frac{2}{\epsilon}\sum_{t=1}^{T}I_{t}B_{t}^{2}\wedge\frac{1}{2}$
$\displaystyle\leq\frac{16}{\epsilon}\left(\log\det{Z}_{T}+2\log(1/\delta)+S^{2}+\frac{1}{16}\right)\log\det{Z}_{T}$
$\displaystyle=O\left(\frac{1}{\epsilon}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\,\log\det(I+H)\right)~{}.$

The third bound follows from Lemma 5, while the last bound holds under event
$\mathcal{E}$. ∎

At this point, we leverage the fact that $x_{1},...,x_{T}$ are generated in an
i.i.d. fashion according to a marginal distribution
$\mathcal{D}_{\mathcal{X}}$ satisfying the low-noise assumption with exponent
$\alpha$ recalled in Section 3. A direct application of Lemma 23 (Appendix
A.4) gives, with probability at least $1-\delta$,

$T_{\epsilon}\leq 3T\epsilon^{\alpha}+O\left(\log\frac{\log
T}{\delta}\right)~{},$

simultaneously over $\epsilon$. Using the above bound on $T_{\epsilon}$ back
into both Lemma 7 and Lemma 9 and optimizing over $\epsilon$ in the two bounds
separately yields the following result, which is presented in the main body as
Theorem 1.

######  Theorem 3.

Let Algorithm 1 be run with parameters $\delta$, $S$, $m$, and $n$ on an
i.i.d. sample $(x_{1},y_{1}),\ldots,(x_{T},y_{T})\sim\mathcal{D}$, where the
marginal distribution $\mathcal{D}_{\mathcal{X}}$ fulfills the low-noise
condition with exponent $\alpha\geq 0$ w.r.t. a function $h$ that satisfies
(1) and such that $\sqrt{2}S_{T,n}(h)\leq S$ for all $\\{x_{i}\\}_{i=1}^{T}$.
Also assume $m\geq CT^{4}\log(2Tn/\delta)n^{6}\left(T^{2}\vee
1/\lambda_{0}^{4}\right)$ where $C$ is the constant in Lemma 1 and Lemma 2.
Then with probability at least $1-\delta$ the cumulative regret $R_{T}$ and
the total number of queries $N_{T}$ are simultaneously upper bounded as
follows:

$\displaystyle R_{T}$
$\displaystyle=O\biggl{(}L_{H}^{\frac{\alpha+1}{\alpha+2}}\Bigl{(}L_{H}+\log(\log
T/\delta)+S^{2}\Bigl{)}^{\frac{\alpha+1}{\alpha+2}}T^{\frac{1}{\alpha+2}}\biggr{)}$
$\displaystyle N_{T}$
$\displaystyle=O\biggl{(}L_{H}^{\frac{\alpha}{\alpha+2}}\Bigl{(}L_{H}+\log(\log
T/\delta)+S^{2}\Bigl{)}^{\frac{\alpha}{\alpha+2}}T^{\frac{2}{\alpha+2}}\biggr{)}~{},$

where $L_{H}=\log\det(I+H)$, and $H$ is the NTK matrix of depth $n$ over the
set of points $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$.

###  A.2 Proofs for Section 4

##### Additional notation.

In this section, we add subscript “$i$" to the relevant quantities occurring
in the proof when these quantities refer to the $i$-th base learner. For
instance, we write $Z_{t,i}$ to denote the covariance matrix updated within
the $i$-th base learner,
$B_{t,i}=B_{t,i}(S_{i})=2\gamma_{t-1,i}\|\phi(x_{t,a_{t}})\|_{Z_{t-1,i}^{-1}}$,
with $\gamma_{t-1,i}=\sqrt{\log\det Z_{t-1,i}+2\log(1/\delta)}+S_{i}$, and
${\mathcal{C}}_{t,i}$ to denote the confidence ellipsoid maintained by the
$i$-th base learner.

For convenience, we also introduce the function

$\displaystyle
d(S,\delta)=(\log\det(I+H)+1)(\log\det(I+H)+\frac{17}{16}+2\log(M/\delta)+S^{2})~{}.$
(12)

The above is a high probability upper bound on
$(\frac{1}{16}+\frac{1}{2}\gamma_{T,i}^{2})\log\det Z_{T,i}$ (holding for all
$i$), which in turn upper bounds
$\frac{1}{8}\sum_{t=1}^{T}I_{t,i}B_{t,i}^{2}\wedge\frac{1}{2}$.

By the assumption in Theorem 2, we know that there is a learner
$i^{\star}=\langle i^{\star}_{1},i^{\star}_{2}\rangle\in\mathcal{M}_{1}$ such
that its parameters $S_{i^{\star}_{1}}$ and $d_{i^{\star}_{2}}$ satisfy

$\displaystyle\sqrt{2}S_{T,n}(h)\leq$
$\displaystyle~{}~{}S_{i^{\star}_{1}}\leq 2\sqrt{2}S_{T,n}(h)$ (13)
$\displaystyle d(S_{T,n}(h),\delta)\leq d(S_{i^{\star}_{1}},\delta)\leq$
$\displaystyle~{}~{}d_{i^{\star}_{2}}\leq 2d(S_{i^{\star}_{1}},\delta)\leq
8d(S_{T,n}(h),\delta)~{}.$ (14)

Throughout the proof we will refer to a specific learner that satisfies these
conditions by $i^{\star}$. Moreover, we denote by $\mathcal{E}_{i}$ the event
where the conditions of the event in Eq. (7) and the event in Lemma 2 hold for
base learner $i$. In $\mathcal{E}_{i}$, we call $i$ well-specified.

Let $R({\mathcal{T}})$ and $N(\mathcal{T})$ denote cumulative regret $R$ and
number of requested labels $N$ when restricted to subset
${\mathcal{T}}\subseteq[T]$. Then the regret and label complexity analyses of
Algorithm 1 in Section A.1 directly imply the following regret and label
complexity bounds of a well-specified base learner $i$ during the execution of
Algorithm 2.

######  Lemma 10 (Regret and label complexity of a well-specified base
learner).

Let $i\in\mathcal{M}_{1}$ be any base learner. In event $\mathcal{E}_{i}$
(when $i$ is well-specified), the following regret and label complexity bound
holds for any $0<\epsilon<\frac{1}{2}$ and $t\in[T]$:

$\displaystyle R(\mathcal{T}_{t,i})$ $\displaystyle\leq
2\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}\wedge\frac{1}{2}~{}~{}\leq~{}~{}\frac{16}{\epsilon}\,d(S_{i_{1}},\delta)+2\epsilon|\mathcal{T}_{t,i}^{\epsilon}|$
$\displaystyle N(\mathcal{T}_{t,i})$
$\displaystyle\leq|\mathcal{T}_{t,i}^{\epsilon}|+\frac{1}{\epsilon^{2}}\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}^{2}\wedge\frac{1}{4}~{}~{}\leq~{}~{}\frac{8}{\epsilon^{2}}\,d(S_{i_{1}},\delta)+|\mathcal{T}_{t,i}^{\epsilon}|~{},$

where $\mathcal{T}_{t,i}^{\epsilon}=\\{k\in[t]\colon
i_{k}=i,~{}|\Delta_{k}|\leq\epsilon\\}$. Furthermore, in rounds
$t\in\mathcal{T}_{t,i}$ where the label is not queried ($I_{t,i}=0$), the
regret is $0$.

###### Proof.

This follows directly from the analysis of Algorithm 1 in the previous
section. ∎

Equipped with these two properties of well-specified base learners, we can
first show that with high probability, Algorithm 2 will never eliminate a
well-specified learner, and subsequently analyze the label complexity and
cumulative regret of Algorithm 2.

######  Lemma 11.

Let $i=\langle i_{1},i_{2}\rangle\in\mathcal{M}_{1}$ be a base learner with
$d_{i_{2}}\geq d(S_{i_{1}},\delta)$. Assume $\gamma\leq\alpha$ and consider
event $\bigcap_{j\colon j\geq i_{1}}\mathcal{E}_{j}$. Then, under that event,
with probability at least $1-M\delta$ Algorithm 2 never eliminates base
learner $i$.

###### Proof.

We show the statement for each of the four mis-specification tests in turn:

  * •

Disagreement test: Consider a round $t$ and any learner $j=\langle
j_{1},j_{2}\rangle$ with $S_{j_{1}}\geq S_{i_{1}}$ and $I_{t,i}=I_{t,j}=0$. By
assumption, $\mathcal{E}_{i}\cap\mathcal{E}_{j}$ holds. Since $i$ did not ask
for the label, this implies that $|\Delta_{t}|>0$ (since in rounds with no
margin $|\Delta_{t}|=0$, a learner always asks for the label). Further, by
Lemma 10, the prediction of $i$ and $j$ has no regret in round $t$. Thus, $i$
and $j$ need to make the same prediction and the test does not trigger.

  * •

Observed regret test: Consider a round $t$ and any $j\in\mathcal{M}_{t}$.
Then, by virtue of Lemma 21 (Appendix A.4), the left-hand side of the observed
regret test for pair $(i,j)$ is upper-bounded with probability at east
$1-\delta$ as

$\displaystyle\sum_{k\in\mathcal{V}_{t,i,j}}(\ 1{1}{\left\\{a_{k,i}\neq
y_{k}\right\\}}$ $\displaystyle-\ 1{1}{\left\\{a_{k,j}\neq y_{k}\right\\}})$
$\displaystyle\leq\sum_{k\in\mathcal{V}_{t,i,j}}(h(x_{k,a_{k,j}})-h(x_{k,a_{k,i}}))+0.72\sqrt{|\mathcal{V}_{t,i,j}|L(|\mathcal{V}_{t,i,j}|,\delta)}$
$\displaystyle\leq\sum_{k\in\mathcal{V}_{t,i,j}}(h(x_{k,a^{\star}_{k}})-h(x_{k,a_{k,i}}))+0.72\sqrt{|\mathcal{V}_{t,i,j}|L(|\mathcal{V}_{t,i,j}|,\delta)}$
$\displaystyle=R(\mathcal{V}_{t,i,j})+0.72\sqrt{|\mathcal{V}_{t,i,j}|L(|\mathcal{V}_{t,i,j}|,\delta)}~{},$

where the second inequality follows from the definition of the best prediction
$a^{*}_{k}$ for round $k$. Finally, in event $\mathcal{E}_{i}$ the regret of
$i$ in rounds $\mathcal{V}_{t,i,j}$ is bounded by Lemma 10 as

$\displaystyle R(\mathcal{V}_{t,i,j})\leq\sum_{k\in\mathcal{V}_{t,i,j}}1\wedge
B_{k,i}~{}.$

Therefore, this test does not trigger for pair $(i,j)$ in round $t$. By a
union bound, this happens with probability at least $1-M\delta$.

  * •

Label complexity test: By Lemma 10, the number of labels requested by $i$ up
to round $t$ is at most

$\displaystyle\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}\leq\inf_{\epsilon\in(0,1/2]}|\mathcal{T}_{t,i}^{\epsilon}|+\frac{1}{\epsilon^{2}}\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}^{2}\wedge\frac{1}{4}~{}.$

We now use Lemma 23 (Appendix A.4) to upper-bound
$|\mathcal{T}_{t,i}^{\epsilon}|$ simultaneously for all $\epsilon$ as

$\displaystyle|\mathcal{T}_{t,i}^{\epsilon}|\leq
3\epsilon^{\gamma}|\mathcal{T}_{t,i}|+2L(|\mathcal{T}_{t,i}|,\delta/\log_{2}(12t))~{}.$

By plugging this expression into the previous bound (and taking a union bound
over $i$) we show that the label complexity test is not triggered.

  * •

$d_{i}$ test: Using the assumption that $\mathcal{E}_{i}$ holds and Lemma 5,
we can bound the left-hand side of the test as

$\displaystyle\sum_{k\in\mathcal{T}_{t,i}}(\frac{1}{2}\wedge
I_{k,i}B_{k,i}^{2})$ $\displaystyle\leq 8(\log\det
Z_{t,i}+2\log(1/\delta)+S_{i_{1}}^{2}+1/16)\log\det Z_{t,i}$
$\displaystyle\leq
8(\log\det(H+I)+2\log(1/\delta)+S_{i_{1}}^{2}+17/16)(\log\det(H+I)+1)$
$\displaystyle=8d(S_{i_{1}},\delta)$

and by the assumption that $d_{i_{2}}\geq d(S_{i_{1}},\delta)$, learner $i$ is
not be eliminated by this test.

This concludes the proof. ∎

####  A.2.1 Label Complexity Analysis

######  Lemma 12 (Label complexity of Algorithm 2).

In event $\bigcap_{i=\langle i_{1},i_{2}\rangle\in\mathcal{M}_{1}\colon
i_{1}\geq{i^{\star}_{1}}}\mathcal{E}_{i}$, Algorithm 2 queries with
probability at least $1-M\delta$

$\displaystyle N(T)$ $\displaystyle=O\left(\sum_{i=\langle
i_{1},i_{2}\rangle\in\mathcal{M}_{1}}\left(\frac{d_{i_{2}}}{\epsilon^{2}}+\epsilon^{\gamma}T\left(1\wedge\frac{d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}\right)+ML(T,\delta/\log
T)\right)$

labels.

###### Proof.

We can decompose the total number of label requests as

$\displaystyle N(T)$
$\displaystyle=\sum_{t=1}^{T}I_{t,i_{t}}=\sum_{i=1}^{M}\sum_{t\in\mathcal{T}_{T,i}}I_{t,i}=\sum_{i\in\mathcal{M}_{1}}N(\mathcal{T}_{T,i})~{}.$

Since each learner $i$ satisfied the label complexity test except possibly for
the round where it was eliminated, we have

$\displaystyle N(\mathcal{T}_{T,i})$
$\displaystyle=O\left(\inf_{\epsilon\in(0,1/2)}\biggl{(}\epsilon^{\gamma}|\mathcal{T}_{T,i}|+\frac{1}{\epsilon^{2}}\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}^{2}\wedge\frac{1}{4}\biggr{)}+L(|\mathcal{T}_{T,i}|,\delta/\log
t)\right)$
$\displaystyle=O\left(\inf_{\epsilon\in(0,1/2)}\biggl{(}\epsilon^{\gamma}\sum_{k\in[T]}p_{k,i}+\frac{1}{\epsilon^{2}}\sum_{k\in\mathcal{T}_{t,i}}I_{k,i}B_{k,i}^{2}\wedge\frac{1}{4}\biggr{)}+L(T,\delta/\log
T)\right)$
$\displaystyle=O\left(\inf_{\epsilon\in(0,1/2)}\biggl{(}\epsilon^{\gamma}\sum_{k\in[T]}p_{k,i}+\frac{d_{i_{2}}}{\epsilon^{2}}\biggr{)}+L(T,\delta/\log
T)\right)~{},$ (15)

where the second inequality holds with probability at least $1-\delta$ by
Lemma 22 and the final inequality holds by the $d_{i}$ test. We now bound
$\sum_{k\in[T]}p_{k,i}$ as

$\displaystyle\sum_{k\in[T]}p_{k,i}\leq T(1\wedge
d_{i_{2}}^{-(\gamma+1)}d_{i^{\star}_{2}}^{\gamma+1})\leq
Td_{i_{2}}^{-(\gamma+1)}(8d(S_{T,n}(h),\delta))^{\gamma+1}\wedge T$

where we used that by Lemma 11 learner $i^{\star}$ never gets eliminated in
the considered event. ∎

####  A.2.2 Regret Analysis

To bound the overall cumulative regret of Algorithm 2, we decompose the rounds
$[T]$ into the following three disjoint sets of rounds

$[T]=\mathcal{R}_{i^{\star}}\dot{\cup}\,\,\mathcal{U}_{i^{\star}}\dot{\cup}\,\,\mathcal{O}_{i^{\star}},$
(16)

where

  * •

$\mathcal{R}_{i^{\star}}=\\{t\in[T]\colon I_{t,i^{\star}}=1\\}$ are the rounds
where $i^{\star}$ requests a label,

  * •

$\mathcal{U}_{i^{\star}}=\\{t\in[T]\colon I_{t,i^{\star}}=0,I_{t,i_{t}}=0\\}$
are the rounds where $i^{\star}$ does not request the label and the label was
not observed,

  * •

$O_{i^{\star}}=\\{t\in[T]\colon I_{t,i^{\star}}=0,I_{t,i_{t}}=1\\}$ are the
rounds where $i^{\star}$ does not request the label and the label was
observed.

In the following three lemmas, we bound the regret in these sets of rounds
separately.

######  Lemma 13 (Regret in rounds where $i^{\star}$ requests).

In event $\bigcap_{i=\langle i_{1},i_{2}\rangle\in\mathcal{M}_{1}\colon
i_{1}\geq i^{\star}_{1}}\mathcal{E}_{i}$, the regret in rounds where
$i^{\star}=\langle i^{\star}_{1},i^{\star}_{2}\rangle$ would request the label
is bounded with probability at least $1-\delta$ for all $\epsilon\in(0,1/2)$
as

$\displaystyle
R(\mathcal{R}_{i^{\star}})=O\left(\frac{M}{\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+2}+\frac{M}{\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+1}L(T,\delta)+\epsilon
T_{\epsilon}\right)~{}.$ (17)

###### Proof.

In any round, the largest instantaneous regret possible is
$2|h(x_{t,1})-1/2|=2|h(x_{t,-1})-1/2|=2|\Delta_{t,i^{\star}}|$, no matter
whether the prediction of $i^{\star}$ was followed or not. Thus, the regret in
rounds $\mathcal{R}_{i^{\star}}$ can be bounded as

$\displaystyle R(\mathcal{R}_{i^{\star}})\leq
2\sum_{t\in\mathcal{R}_{i^{\star}}}|\Delta_{t,i^{\star}}|=2\sum_{t\in\mathcal{R}_{i^{\star}}}\
1{1}{\left\\{|\Delta_{t,i^{\star}}|>\epsilon\right\\}}|\Delta_{t,i^{\star}}|+2\epsilon|\mathcal{R}_{i^{\star}}^{\epsilon}|,$

for any $\epsilon\in(0,1/2)$ where
$\mathcal{R}_{i^{\star}}^{\epsilon}=\\{t\in\mathcal{R}_{i^{\star}}\colon|\Delta_{t}|\leq\epsilon\\}$.

On rounds $\mathcal{R}_{i^{\star}}$, learner $i^{\star}$ wants to query the
label which means $\widehat{\Delta}_{t,i^{\star}}\leq B_{t,i^{\star}}$.
Moreover in $\mathcal{E}_{i^{\star}}$, the conditions
$0\leq\widehat{\Delta}_{t,i^{\star}}-\widehat{\Delta}_{t,i^{\star}}\leq
B_{t,i^{\star}}$ and $0\leq\widehat{\Delta}_{t,i^{\star}}$ hold. Combining
both inequalities gives $|\Delta_{t,i^{\star}}|\leq B_{t,i^{\star}}$ and we
can further bound the display above as

$\displaystyle R(\mathcal{R}_{i^{\star}})\leq$
$\displaystyle\sum_{t\in\mathcal{R}_{i^{\star}}}\
1{1}{\left\\{|\Delta_{t,i^{\star}}|>\epsilon\right\\}}(1\wedge
2B_{t,i^{\star}})+2\epsilon|\mathcal{R}_{i^{\star}}^{\epsilon}|$
$\displaystyle\leq$ $\displaystyle\sum_{t\in\mathcal{R}_{i^{\star}}}\
1{1}{\left\\{|\Delta_{t,i^{\star}}|>\epsilon\right\\}}\left(1\wedge\frac{2B_{t,i^{\star}}^{2}}{\epsilon}\right)+2\epsilon|\mathcal{R}_{i^{\star}}^{\epsilon}|$
$\displaystyle\leq$
$\displaystyle\frac{2}{\epsilon}\sum_{t\in\mathcal{R}_{i^{\star}}}\left(\frac{\epsilon}{2}\wedge
B_{t,i^{\star}}^{2}\right)+2\epsilon|\mathcal{R}_{i^{\star}}^{\epsilon}|~{}.$

To bound the remaining sum, we appeal to the randomized potential lemma in
Lemma 25. We denote $\underline{p}^{\star}=\min_{k\in[T]}p_{k,i^{\star}}$ the
smallest probability of $i^{\star}$ in any round. Then Lemma 25 gives with
probability at least $1-\delta$

$\displaystyle\sum_{t\in\mathcal{R}_{i^{\star}}}\left(\frac{\epsilon}{2}\wedge
B_{t,i^{\star}}^{2}\right)$
$\displaystyle\leq\sum_{t\in\mathcal{R}_{i^{\star}}}\left(\frac{1}{4}\wedge
B_{t,i^{\star}}^{2}\right)\leq
4\gamma_{T,i^{\star}}^{2}\sum_{t\in\mathcal{R}_{i^{\star}}}\left(\frac{1}{16\gamma_{T,i^{\star}}^{2}}\wedge\|\phi(x_{t,a_{t,i^{\star}}})\|_{Z_{t-1,i^{\star}}^{-1}}^{2}\right)$
$\displaystyle\leq
4\gamma_{T,i^{\star}}^{2}\biggl{(}1+\frac{3}{16\underline{p}^{\star}\gamma_{T,i^{\star}}^{2}}L(T,\delta)\biggr{)}+\frac{8\gamma_{T,i^{\star}}^{2}}{\underline{p}^{\star}}(1+\frac{1}{16\gamma_{T,i^{\star}}^{2}})\log\det
Z_{T,i^{\star}}$
$\displaystyle\leq\frac{12\gamma_{T,i^{\star}}^{2}+\frac{1}{2}}{\underline{p}^{\star}}\log\det
Z_{T,i^{\star}}+\frac{3}{4\underline{p}^{\star}}L(T,\delta)~{},$

because $\gamma_{t,i^{\star}}$ is non-decreasing in $T$. Plugging this back
into the previous display yields

$\displaystyle R(\mathcal{R}_{i^{\star}})$ $\displaystyle\leq
24\frac{\gamma_{T,i^{\star}}^{2}+\frac{1}{24}}{\epsilon\underline{p}^{\star}}\log\det
Z_{T,i^{\star}}+\frac{3}{2\epsilon\underline{p}^{\star}}L(T,\delta)+2\epsilon|\mathcal{R}_{i^{\star}}^{\epsilon}|$
$\displaystyle\leq
48\frac{d(S_{i^{\star}_{1}},\delta)}{\epsilon\underline{p}^{\star}}+\frac{3}{2\epsilon\underline{p}^{\star}}L(T,\delta)+2\epsilon
T_{\epsilon}~{}.$

Now, Lemma 11 ensures that $i^{\star}$ never gets eliminated in the considered
event. Therefore

$\displaystyle\frac{1}{\underline{p}^{\star}}\leq\frac{\sum_{i\in\mathcal{M}_{1}}d_{i_{2}}^{-(\gamma+1)}}{d_{i^{\star}_{2}}^{-(\gamma+1)}}=d_{i^{\star}_{2}}^{\gamma+1}M\leq
M(2d(S_{i^{\star}_{1}},\delta))^{\gamma+1}~{},$

where the last inequality follows from Eq. (13). Plugging this bound back into
the previous display yields

$\displaystyle
R(\mathcal{R}_{i^{\star}})\leq\frac{48M}{\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+2}+\frac{3M}{2\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+1}L(T,\delta)+2\epsilon
T_{\epsilon}~{},$

as claimed. ∎

######  Lemma 14 (Regret in unobserved rounds where $i^{\star}$ does not
request).

In event $\mathcal{E}_{i^{\star}}$,

$\displaystyle R(\mathcal{U}_{i^{\star}})\leq M~{}.$ (18)

###### Proof.

If $i^{\star}$ is not requesting the label then $i^{\star}$ predicts the label
as $a^{*}_{t}$. From the disagreement test $i_{t}$ will predict the same label
as $i^{\star}$ so there should be no regret, except when a learner gets
eliminated. Since there are at most $M$ learners and the regret per round is
at most $1$, the total regret on rounds $\mathcal{U}_{i^{\star}}$ can at most
be $M$. ∎

######  Lemma 15 (Regret in observed rounds where $i^{\star}$ does not
request).

In event $\bigcap_{i=\langle i_{1},i_{2}\rangle\in\mathcal{M}_{1}\colon
i_{1}\geq i^{\star}_{1}}\mathcal{E}_{i}$, the regret in rounds where
$i^{\star}$ does not request the label, but the label was still observed is
bounded as

$\displaystyle R$ $\displaystyle(\mathcal{O}_{i^{\star}})$
$\displaystyle=O\left(\sum_{i=\langle
i_{1},i_{2}\rangle\in\mathcal{M}_{1}}\inf_{\epsilon\in(0,1/2)}\left(\frac{d_{i_{2}}}{\epsilon}+T\left(\frac{\epsilon\,d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}+\frac{L(T,\delta)}{\epsilon}\right)+ML(T,\delta/\log
T)\right)~{}.$

###### Proof.

Note that we can decompose the regret in those rounds as

$\displaystyle R(\mathcal{O}_{i^{\star}})=\sum_{i\neq
i_{*}}R(\mathcal{V}_{T,i,i^{\star}})$

since no regret occurs if the played action agrees with the action proposed by
$i^{\star}$ which did not request a label and in $\mathcal{E}_{i^{\star}}$
does not incur any regret in such rounds. We bound
$R(\mathcal{V}_{T,i,i^{\star}})$ by using the fact that in all but at most one
of those rounds both the observed regret test and the $d_{i}$ test did not
trigger. This gives

$\displaystyle\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(\
1{1}{\left\\{a_{k,i}\neq y_{k}\right\\}}-\ 1{1}{\left\\{a_{k,i^{\star}}\neq
y_{k}\right\\}})\leq\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}1\wedge
B_{k,i}+1.45\sqrt{|{\mathcal{V}}_{T,i,i^{\star}}|L(|{\mathcal{V}}_{T,i,i^{\star}}|,\delta)}+1~{}.$

We now apply the concentration argument in Lemma 21 to bound the LHS from
below as

$\displaystyle\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(\
1{1}{\left\\{a_{k,i}\neq y_{k}\right\\}}-\ 1{1}{\left\\{a_{k,i^{\star}}\neq
y_{k}\right\\}})$
$\displaystyle\geq\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(h(x_{k,a_{k,i^{\star}}})-h(x_{k,a_{k,i}}))-0.72\sqrt{|\mathcal{V}_{T,i,i^{\star}}|L(|\mathcal{V}_{T,i,i^{\star}}|,\delta)}$
$\displaystyle=\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(h(x_{k,a^{\star}_{k}})-h(x_{k,a_{k,i}}))-0.72\sqrt{|\mathcal{V}_{T,i,i^{\star}}|L(|\mathcal{V}_{T,i,i^{\star}}|,\delta)}$
$\displaystyle=R(\mathcal{V}_{T,i,i^{\star}})-0.72\sqrt{|\mathcal{V}_{T,i,i^{\star}}|L(|\mathcal{V}_{T,i,i^{\star}}|,\delta)}~{},$

where $a_{k}^{\star}$ is the optimal prediction in round $k$. Combining the
previous two displays allows us to bound the regret from above for any
$\epsilon\in(0,1/2)$ as

$\displaystyle R(\mathcal{V}_{T,i,i^{\star}})$
$\displaystyle\leq\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(1\wedge
B_{k,i})+3\sqrt{|{\mathcal{V}}_{T,i,i^{\star}}|L(T,\delta)}+1~{}$
$\displaystyle\leq\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(1\wedge
I_{k,i}B_{k,i})\
1{1}{\left\\{B_{k,i}\geq\epsilon\right\\}}+\frac{5}{2}\epsilon|{\mathcal{V}}_{T,i,i^{\star}}|+\frac{3}{2}\frac{L(T,\delta)}{\epsilon}+1~{}$
$\displaystyle\leq\frac{1}{\epsilon}\sum_{k\in\mathcal{V}_{T,i,i^{\star}}}(\epsilon\wedge
I_{k,i}B_{k,i}^{2})+\frac{5}{2}\epsilon|{\mathcal{V}}_{T,i,i^{\star}}|+\frac{3}{2}\frac{L(T,\delta)}{\epsilon}+1~{}$
$\displaystyle\leq
8\frac{d_{i}}{\epsilon}+\frac{5}{2}\epsilon|{\mathcal{V}}_{T,i,i^{\star}}|+\frac{3}{2}\frac{L(T,\delta)}{\epsilon}+1~{},$

where the last inequality applies the condition of the $d_{i}$ test. Since
${\mathcal{V}}_{T,i,i^{\star}}$ can only contain rounds where $i$ was chosen
and requested a label, we can apply the label complexity bound from Eq. (15)
(with $\sum_{k\in[T]}p_{k,i}$ therein upper bounded as explained just
afterwards) which gives

$\displaystyle|{\mathcal{V}}_{T,i,i^{\star}}|=O\left(\inf_{\epsilon\in(0,1/2)}\biggl{(}\epsilon^{\gamma}T\left(\frac{d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}+\frac{d_{i_{2}}}{\epsilon^{2}}\biggr{)}+L(T,\delta/\log
T)\right)~{},$ (19)

and plugging this back into the previous bound yields, for any $i=\langle
i_{1},i_{2}\rangle$,

$\displaystyle R(\mathcal{V}_{T,i,i^{\star}})$
$\displaystyle=O\left(\frac{d_{i_{2}}}{\epsilon}+T\left(\frac{\epsilon\,d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}+\frac{L(T,\delta)}{\epsilon}+L(T,\delta/\log
T)\right)~{}.$

Summing over $i\neq i^{*}$ gives the claimed result. ∎

####  A.2.3 Putting it all together

Putting together the above results gives rise to the following guarantee on
the regret and the label complexity of Algorithm 2, presented in the main body
of the paper as Theorem 2.

######  Theorem 4.

Let Algorithm 2 be run with parameters $\delta$, $\gamma\leq\alpha$ with a
pool of base learners $\mathcal{M}_{1}$ of size $M$ on an i.i.d. sample
$(x_{1},y_{1}),\ldots,(x_{T},y_{T})\sim\mathcal{D}$, where the marginal
distribution $\mathcal{D}_{\mathcal{X}}$ fulfills the low-noise condition with
exponent $\alpha\geq 0$ w.r.t. a function $h$ that satisfies (1) and
complexity $S_{T,n}(h)$. Let also $\mathcal{M}_{1}$ contain at least one base
learner $i$ such that $\sqrt{2}S_{T,n}(h)\leq S_{i}\leq 2\sqrt{2}S_{T,n}(h)$
and $d_{i}=\Theta(L_{H}(L_{H}+\log(M\log T/\delta)+S^{2}_{T,n}(h)))$, where
$L_{H}=\log\det(I+H)$, being $H$ the NTK matrix of depth $n$ over the set of
points $\\{x_{t,a}\\}_{t=1,\ldots,T,\,a=\pm 1}$. Also assume $m\geq
CT^{4}\log(2Tn/\delta)n^{6}\left(T^{2}\vee 1/\lambda_{0}^{4}\right)$ where $C$
is the constant in Lemma 1 and Lemma 2. Then with probability at least
$1-\delta$ the cumulative regret $R_{T}$ and the total number of queries
$N_{T}$ are simultaneously upper bounded as follows:

$\displaystyle R_{T}$
$\displaystyle=O\left(M\,\Bigl{(}L_{H}\bigl{(}L_{H}+\log(M\log
T/\delta)+S^{2}_{T,n}(h)\bigl{)}\Bigl{)}^{\gamma+1}T^{\frac{1}{\gamma+2}}+M\,L(T,\delta)\right)$
$\displaystyle N_{T}$
$\displaystyle=O\left(M\,\Bigl{(}L_{H}\bigl{(}L_{H}+\log(M\log
T/\delta)+S^{2}_{T,n}(h)\bigl{)}\Bigl{)}^{\frac{\gamma}{\gamma+2}}T^{\frac{2}{\gamma+2}}+M\,L(T,\delta)\right)~{},$

where $L(T,\delta)$ is the logarithmic term defined at the beginning of
Algorithm 2’s pseudocode.

###### Proof.

Using the decomposition in Eq. (16) combined with Lemmas 13, 14, and 15 we see
that the regret of Algorithm 2 can be bounded as

$\displaystyle R(T)$
$\displaystyle\leq~{}R(\mathcal{R}_{i_{\star}})+R(\mathcal{U}_{i_{\star}})+R(\mathcal{O}_{i_{\star}})$
$\displaystyle=O\Biggl{(}\frac{M}{\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+2}+\frac{M}{\epsilon}2^{\gamma+1}d(S_{i^{\star}_{1}},\delta)^{\gamma+1}L(T,\delta)+\epsilon
T_{\epsilon}$ $\displaystyle~{}~{}~{}~{}+\sum_{i=\langle
i_{1},i_{2}\rangle\in\mathcal{M}_{1}}\inf_{\epsilon\in(0,1/2)}\left(\frac{d_{i_{2}}}{\epsilon}+T\left(\frac{\epsilon\,d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}+\frac{L(T,\delta)}{\epsilon}\right)+ML(T,\delta/\log
T)\Biggl{)}~{}.$

We first bound term $T_{\epsilon}$ through Lemma 23 (Appendix A.4). This
gives, with probability at least $1-\delta$,

$T_{\epsilon}=O\left(T\epsilon^{\gamma}+\log\frac{\log T}{\delta}\right)~{},$

simultaneously over $\epsilon$. Plugging back into the above, collecting terms
and resorting to a big-oh notation that disregards multiplicative constants
independent of $T$, $M$, $1/\delta$ yields

$\displaystyle R(T)$
$\displaystyle=O\Biggl{(}\frac{M}{\epsilon}\Bigl{(}d(S_{T,n}(h),\delta)^{\gamma+2}+d(S_{T,n}(h),\delta)^{\gamma+1}L(T,\delta)\Bigl{)}+\epsilon^{\gamma+1}T+ML(T,\delta/\log
T)$ (20) $\displaystyle\qquad\qquad+\sum_{i=\langle
i_{1},i_{2}\rangle\in\mathcal{M}_{1}}\inf_{\epsilon\in(0,1/2)}\left(\frac{d_{i_{2}}}{\epsilon}+T\left(\frac{\epsilon\,d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}+\frac{L(T,\delta)}{\epsilon}\right)\Biggl{)}~{},$
(21)

holding simultaneously for all $\epsilon\in(0,1/2)$.

Now, the sum of the first two terms in the RHS (that is, Eq. (20)) is
minimized by selecting $\epsilon$ of the form

$\epsilon=\left(M\left(\frac{d(S_{T,n}(h),\delta)^{\gamma+2}+d(S_{T,n}(h),\delta)^{\gamma+1}L(T,\delta)}{T}\right)\right)^{\frac{1}{\gamma+2}}~{}$

which, plugged back into (20) gives

$\displaystyle(\ref{e:first term})$
$\displaystyle=O\left(\Bigl{(}M\left(d(S_{T,n}(h),\delta)^{\gamma+2}+d(S_{T,n}(h),\delta)^{\gamma+1}L(T,\delta)\right)\Bigl{)}^{\frac{\gamma+1}{\gamma+2}}\,T^{\frac{1}{\gamma+2}}+ML(T,\delta/\log
T)\right)$
$\displaystyle=O\left(Md(S_{T,n}(h),\delta)^{\gamma+1}\,T^{\frac{1}{\gamma+2}}\,L(T,\delta/\log
T)\right)~{}.$

Notice that $\epsilon$ is constrained to lie in $(0,1/2)$. If that is not the
case with the above choice of $\epsilon$, our bound delivers vacuous regret
guarantees.

As for the sum in (21), each term in the sum is individually minimized by an
$\epsilon$ of the form

$\epsilon=\left(\frac{(d_{i_{2}}+L(T,\delta))\cdot
d^{\gamma+1}_{i_{2}}}{T\cdot
d(S_{T,n}(h),\delta)^{\gamma+1}}\right)^{\frac{1}{\gamma+2}}.$

Notice that the above value of $\epsilon$ lies in the range $(0,\frac{1}{2})$
provided $d_{i_{2}}=o(T^{\frac{1}{\gamma+2}})$. Hence we simply assume that
our model selection algorithm is performed over base learners with $d_{i_{2}}$
bounded as above. In fact, if $d(S_{T,n}(h),\delta)$ exceeds this range then
our bounds become vacuous.

Next, substituting the value of $\epsilon$ obtained above we get that Eq. (21)
can be bounded as

$(\ref{e:second
term})=O\left(Md(S_{T,n}(h),\delta)^{\frac{\gamma+1}{\gamma+2}}T^{\frac{1}{\gamma+2}}\right).$

Combining the bounds on Eq. (20) and Eq. (21) we get the claimed bound on the
regret $R_{T}$.

Next, we bound the label complexity of the our model selection procedure. From
Lemma 12 we have that the label complexity can be bounded by

$\displaystyle N_{T}$ $\displaystyle=O\left(\sum_{i=\langle
i_{1},i_{2}\rangle\in\mathcal{M}_{1}}\left(\frac{d_{i_{2}}}{\epsilon^{2}}+\epsilon^{\gamma}T\left(1\wedge\frac{d(S_{T,n}(h),\delta)}{d_{i_{2}}}\right)^{\gamma+1}\right)+ML(T,\delta/\log
T)\right)~{}.$ (22)

Next consider a term in the summation in Eq. (22) with $d_{i_{2}}\geq
d(S_{T,n}(h),\delta)$. The following value of $\epsilon$ minimizes the term:

$\epsilon=\left(\frac{d_{i_{2}}}{T^{\frac{1}{\gamma+2}}}d(S_{T,n}(h),\delta)^{-\frac{\gamma+1}{\gamma+2}}\right).$

Again we notice that this is a valid range of $\epsilon$ provided that
$d_{i_{2}}=o(T^{\frac{1}{\gamma+2}})$. Substituting back into Eq. (22) we
obtain that the label complexity incurred due to such terms (denoted by
$N_{1}(T)$) is bounded as

$\displaystyle N_{1}(T)$
$\displaystyle=O\left(M\frac{T^{\frac{2}{\gamma+2}}d(S_{T,n}(h),\delta)^{\frac{2(\gamma+1)}{\gamma+2}}}{d_{i_{2}}}+ML(T,\delta/\log
T)\right)$
$\displaystyle=O\left(M{T^{\frac{2}{\gamma+2}}d(S_{T,n}(h),\delta)^{\frac{\gamma}{\gamma+2}}}+ML(T,\delta/\log
T)\right).$ (23)

Finally, consider a term in the summation in Eq. (22) with
$d_{i_{2}}<d(S_{T,n}(h),\delta)$. Then the value of $\epsilon$ that minimizes
the term equals

$\epsilon=\left(\frac{d_{i_{2}}}{T}\right)^{\frac{1}{\gamma+2}}.$

Substituting back into Eq. (22), we get that the label complexity incurred by
such terms (denoted by $N_{2}(T)$) is bounded by

$\displaystyle N_{2}(T)$
$\displaystyle=O\left(M{T^{\frac{2}{\gamma+2}}d(S_{T,n}(h),\delta)^{\frac{\gamma}{\gamma+2}}}+ML(T,\delta/\log
T)\right).$ (24)

Noting that $N_{T}=N_{1}(T)+N_{2}(T)$, we get the claimed bound on the label
complexity of the algorithm. ∎

###  A.3 Extension to non-Frozen NTK

Following [44], in order to avoid computing $f(x,\theta_{0})$ for each input
$x$, we replace each vector $x_{t,a}\in\mathbb{R}^{2d}$ by
$[x_{t,a},x_{t,a}]/\sqrt{2}\in\mathbb{R}^{4d}$, matrix $W_{l}$ by
$\begin{pmatrix}W_{l}&0\\\ 0&W_{l}\end{pmatrix}\in\mathbb{R}^{4d\times 4d}$,
for $l=1,\ldots,n-1$, and $W_{n}$ by
$\left(W_{n}^{\top},-W_{n}^{\top}\right)^{\top}\in\mathbb{R}^{2d}$. This
ensures that the initial output of neural network $f(x,\theta_{0})$ is always
0 for any $x$.

####  A.3.1 Non-Frozen NTK Base Learner

The pseudocode for the base learner in the non-frozen case is contained in
Algorithm 3. Unlike Algorithm 1, Algorithm 3 updates $\theta_{t}$ using
gradient descent. The update of $\theta_{t}$ is handled by the pseudocode in
Algorithm 4.

Input: Confidence level $\delta$, complexity parameter $S$, network width $m$
and depth $n$, number of rounds $T$, step size $\eta$, number of gradient
descent steps $J$ .

Initialization:

  * •

Generate each entry of $W_{k}$ independently from $\mathcal{N}(0,4/m)$, for
$k\in[n-1]$, and each entry of $W_{n}$ independently from
$\mathcal{N}(0,2/m)$;

  * •

Define $\phi_{t}(x)=g(x;\theta_{t-1})/\sqrt{m}$, where $\theta_{t-1}=\langle
W_{1},\ldots,W_{n}\rangle\in\mathbb{R}^{p}$ is the weight vector of the neural
network so generated at round $t-1$;

  * •

Set $Z_{0}=I\in\mathbb{R}^{p\times p}$ .

for  _$t=1,2,\ldots,T$_

Observe instance $x_{t}\in\mathcal{X}$ and build $x_{t,a}\in\mathcal{X}^{2}$,
for $a\in\mathcal{Y}$

Set
$\mathcal{C}_{t-1}=\\{\theta:\|\theta-\theta_{t-1}\|_{Z_{t-1}}\leq\frac{\gamma_{t-1}}{\sqrt{m}}\\}$,
with $\gamma_{t-1}=3(\sqrt{\log{\det Z_{t-1}}+3\log(1/\delta)}+S)$

Set  $\displaystyle U_{t,a}=$ $\displaystyle
f(x_{t,a},{\theta}_{t-1})+\gamma_{t-1}\|\phi_{t-1}(x_{t,a})\|_{Z_{t-1}^{-1}}+\mbox{$\frac{1}{\sqrt{T}}$}$
Predict $a_{t}=\arg\max_{a\in\mathcal{Y}}U_{t,a}$

Set $I_{t}=\ 1{1}{\left\\{|U_{t,a_{t}}-1/2|\leq B_{t}\right\\}}\in\\{0,1\\}$
with
$B_{t}=2\gamma_{t-1}\|\phi_{t-1}(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}+\frac{2}{\sqrt{T}}$

if  _$I_{t}=1$_

Query $y_{t}\in\mathcal{Y}$, and set loss $\ell_{t}=\ell(a_{t},y_{t})$

Update  $\displaystyle Z_{t}$
$\displaystyle=Z_{t-1}+\phi_{t}(x_{t,a_{t}})\phi_{t}(x_{t,a_{t}})^{\top}$
$\displaystyle{\theta}_{t}$
$\displaystyle=\operatorname{TrainNN}\biggl{(}\eta,\,J,\,m,\,\\{x_{s,a_{s}}\,|\,s\in[t],I_{s}=1\\},\,\\{\ell_{s}\,|\,s\in[t],I_{s}=1\\},\,{\theta}_{0}\biggr{)}$

else

$Z_{t}=Z_{t-1}$, $\theta_{t}=\theta_{t-1}$, $\gamma_{t}=\gamma_{t-1}$,
$\mathcal{C}_{t}=\mathcal{C}_{t-1}$ .

Algorithm 3 NTK Selective Sampler.

Input: Step size $\eta$, number of gradient descent steps $J$, network width
$m$, contexts $\\{x_{i}\\}_{i=1}^{l}$, loss values $\\{\ell_{i}\\}_{i=1}^{l}$,
initial weight ${\theta}^{(0)}$.

Set
$\mathcal{L}({\theta})=\sum_{i=1}^{l}(f(x_{i},\theta)-1+\ell_{i})^{2}/2+m\|{\theta}-{\theta}^{(0)}\|_{2}^{2}$.

for  _$j=0,\ldots,J-1$_

${\theta}^{(j+1)}={\theta}^{(j)}-\eta\nabla\mathcal{L}({\theta}^{(j)})$

Return ${\theta}^{(J)}$

Algorithm 4 TrainNN($\eta$, $J$, $m$, $\\{x_{i}\\}_{i=1}^{l}$,
$\\{\ell_{i}\\}_{i=1}^{l}$, ${\theta}^{(0)})$

Note that both Algorithm 1 and Algorithm 3 determine the confidence ellipsoid
$\mathcal{C}_{t}$ by updating $\theta_{t}$, $\gamma_{t}$ and $Z_{t}$. To tell
apart the two learners, we use $\bar{\gamma}_{t}$, $\bar{Z}_{t}$ and
$\bar{\theta}_{t}$ to denote the ellipsoid parameters for Algorithm 1. We make
use of a few relevant lemmas from [44] and its references therein stating that
in the over-parametrized regime, i.e., when $\displaystyle
m\geq{\mbox{poly}}(T,n,\lambda_{0}^{-1},S^{-1},\log(1/\delta))$, the gradient
descent update does not leave $\theta_{t}$ and $Z_{t}$ too far from the
corresponding $\bar{\theta}_{t}$ and $\bar{Z}_{t}$. Moreover, the neural
network $f$ is close to its first order approximation. The interested reader
is referred to Lemmas B.2 through B.6 of [44]. Combining these results with
the analysis in Section A.1 we bound the label complexity and regret for
Algorithm 3.

The below proofs are mainly sketched, since they follow from a combination of
the arguments in Section A.1 and some technical lemmas in [44].

We re-define here $\mathcal{E}_{0}$ to be the event where (4) and (5) hold
along with all the bounds in the well-approximation lemmas of [44] (Lemmas B.2
throug B.6). From [44], there exists a constant $C$ such that if

$m\geq CT^{19}n^{27}(\log m)^{3}$

then $\mathbb{P}(\mathcal{E}_{0})\geq 1-\delta$. Event $\mathcal{E}$ is
defined as in Eq. (7) with this specific event $\mathcal{E}_{0}$ therein.

We give a new version of Lemma 3 below, which implies that event $\mathcal{E}$
still holds with high probability for Algorithm 3, with a specific learning
rate $\eta$, number of gradient descent steps $J$ and network width $m$.

######  Lemma 16.

There exist positive constants $\bar{C}_{1},\bar{C}_{2}$ such that if

$\displaystyle\eta=\frac{\bar{C}_{1}}{2mnT}~{},\qquad\qquad
J=\frac{4nT}{\bar{C}_{1}}\log\frac{S}{CnT^{3/2}}~{},\qquad\qquad
m\geq\bar{C}_{2}T^{19}n^{27}(\log m)^{3}$

and $\sqrt{2}S_{T,n}(h)\leq S$, then under event $\mathcal{E}_{0}$ for any
$\delta\in(0,1)$ we have with probability at least $1-\delta$

$\displaystyle\|{\theta}^{*}-{\theta}_{t}\|_{Z_{t}}\leq\gamma_{t}/\sqrt{m}$

simultaneously for all $t>0$. In other words, under event $\mathcal{E}_{0}$,
${\theta}^{*}\in\mathcal{C}_{t}$ with high probability for all $t$.

###### Proof sketch.

In Lemma 5.2 of [44], it is shown that

$\displaystyle\sqrt{m}\|{\theta}^{*}-{\theta}_{t}\|_{Z_{t}}$
$\displaystyle\leq\sqrt{1+Cm^{-1/6}\sqrt{\log m}n^{4}t^{7/6}}$
$\displaystyle\hskip 72.26999pt\times\left(\sqrt{\log{\det
Z_{t}}+Cm^{-1/6}\sqrt{\log m}n^{4}t^{5/3}+2\log(1/\delta)}+S\right)$
$\displaystyle~{}~{}~{}~{}+Cn\left((1-\eta m)^{J/2}t^{3/2}+Cm^{-1/6}\sqrt{\log
m}n^{7/2}t^{19/6}\right)$

for some constant $C$ under event $\mathcal{E}_{0}$ and the assumption that
$\sqrt{2}S_{T,n}(h)\leq S$. Setting $\eta=\frac{\bar{C}_{1}}{2mnT}$ and
$J=\frac{4nT}{\bar{C}_{1}}\log\frac{S}{CnT^{3/2}}$ allows us to bound
$Cn(1-\eta m)^{J/2}T^{3/2}$ by $S$. Lastly, since $m$ satisfies

$\frac{C^{2}\sqrt{\log m}\,n^{9/2}T^{19/6}}{m^{1/6}}\leq 1~{},$

we have

$\displaystyle\sqrt{m}\|{\theta}^{*}-{\theta}_{t}\|_{Z_{t}}$
$\displaystyle\leq\sqrt{2}\left(\sqrt{\log{\det
Z_{t}}+1+2\log(1/\delta)}+S\right)+S+1$ $\displaystyle\leq
3\left(\sqrt{\log{\det Z_{t}}+3\log(1/\delta)}+S\right)~{},$

as claimed. ∎

We next show the properties of $\widehat{\Delta}_{t}$ and $\Delta_{t}$, which
is a new version of Lemma 6 for the non-frozen case.

######  Lemma 17.

Assume $\displaystyle m\geq poly(T,n,\lambda_{0}^{-1},S,\log(1/\delta))$ and
$\sqrt{2}S_{T,n}(h)\leq S$. Then under event $\mathcal{E}$ we have
$0\leq\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}$ and $\
0\leq\widehat{\Delta}_{t}$, where $B_{t}$ is the querying threshold in
Algorithm 3, i.e.,

$B_{t}=2\gamma_{t-1}\|\phi_{t}(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}+\frac{2}{\sqrt{T}}~{}.$

###### Proof.

Denote

$\tilde{U}_{t,a}=\max_{{\theta}\in\mathcal{C}_{t-1}}\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}-{\theta}_{0}\rangle=\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}_{t-1}-{\theta}_{0}\rangle+\gamma_{t-1}\|\phi_{t}(x_{t,a})\|_{Z_{t-1}^{-1}}~{}.$

We decompose

$\widehat{\Delta}_{t}-\Delta_{t}=(U_{t,a}-\tilde{U}_{t,a})+(\tilde{U}_{t,a}-h(x_{t,a}))=:A_{1}+A_{2}~{}.$

For $A_{1}$, by definition of $U_{t,a}$ in Algorithm 3 we have

$\displaystyle U_{t,a}-\tilde{U}_{t,a}=f(x_{t,a};{\theta}_{t-1})-\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}_{t-1}-{\theta}_{0}\rangle+\frac{1}{\sqrt{T}}~{}.$

Under event $\mathcal{E}$, the bound in Lemma B.4 of [44] holds. That is,
there is a constant $C_{2}$ such that

$\displaystyle|f(x_{t,a};{\theta}_{t-1})-\langle g(x_{t,a};{\theta}_{t-1}),$
$\displaystyle{\theta}_{t-1}-{\theta}_{0}\rangle|$
$\displaystyle=|f(x_{t,a};{\theta}_{t-1})-f(x_{t,a};{\theta}_{0})-\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}_{t-1}-{\theta}_{0}\rangle|$
$\displaystyle\leq C_{2}m^{-1/6}\sqrt{\log m}n^{3}t^{2/3}~{}.$

Setting $m$ so large as to satisfy $C_{2}m^{-1/6}\sqrt{\log
m}n^{3}T^{2/3}\leq\frac{1}{2\sqrt{T}}$ gives us

$\frac{1}{2\sqrt{T}}\leq A_{1}\leq\frac{3}{2\sqrt{T}}~{}.$

To estimate $A_{2}$ we decompose it further as

$\displaystyle A_{2}$ $\displaystyle=\left(\tilde{U}_{t,a}-\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}^{\star}-{\theta}_{0}\rangle\right)+\left(\langle
g(x_{t,a};{\theta}_{t-1}),{\theta}^{\star}-{\theta}_{0}\rangle-\langle
g(x_{t,a};{\theta}_{0}),{\theta}^{\star}-{\theta}_{0}\rangle\right)$
$\displaystyle=:A_{3}+A_{4}~{}.$

Following the argument in Lemma 6 we can show the inequality $0\leq A_{3}\leq
2\gamma_{t-1}\|\phi_{t}(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}$ under event
$\mathcal{E}$. By Cauchy-Schwartz inequality
$|A_{4}|\leq\|g(x_{t,a};{\theta}_{t-1})-g(x_{t,a};{\theta}_{0})\|_{2}\|{\theta}^{\star}-{\theta}_{0}\|_{2}$.
Using the assumption that the bounds in Lemmas B.5 and B.6 in [44] hold and
$\sqrt{2}S_{T,n}(h)\leq S$, there exists a constant $C_{1}$ such that

$\displaystyle|A_{4}|\leq\|g(x_{t,a};{\theta}_{t-1})-g(x_{t,a};{\theta}_{0})\|_{2}\|{\theta}^{\star}-{\theta}_{0}\|_{2}\leq
C_{1}Sm^{-1/6}\sqrt{\log m}n^{7/2}t^{1/6}~{}.$

Setting $m$ large enough to satisfy $C_{1}Sm^{-1/6}\sqrt{\log
m}n^{7/2}T^{1/6}\leq\frac{1}{2\sqrt{T}}$ gives us

$-\frac{1}{2\sqrt{T}}\leq A_{2}\leq
2\gamma_{t-1}\|\phi_{t}(x_{t,a_{t}})\|_{Z_{t-1}^{-1}}+\frac{1}{2\sqrt{T}}~{}.$

Combining the bound for $A_{1}$ and $A_{2}$ we obtain

$\displaystyle 0\leq\widehat{\Delta}_{t}-\Delta_{t}\leq B_{t}~{},$

which proves the first part of the claim.

Next, since $U_{t,a}-h(x_{t,a})\geq 0$ for $a\in\mathcal{Y}$, we also have

$U_{t,1}+U_{t,-1}\geq h(x_{t,1})+h(x_{t,-1})=1$

which, by definition of $a_{t}$, gives $U_{t,a_{t}}\geq\frac{1}{2}$, i.e.,
$\widehat{\Delta}_{t}\geq 0$. This concludes the proof. ∎

As a consequence of the above lemma, like in the frozen case, on rounds where
Algorithm 3 does not issue a query, we are confident that prediction $a_{t}$
suffers no regret.

Before bounding the label complexity and regret, we give the following lemma
which is the non-frozen counterpart to Lemma 5 in Section A.1. The proof
follows from very similar arguments, and is therefore omitted.

######  Lemma 18.

Let $\eta$, $J$ and $m$ be as in Lemma 16 and $\sqrt{2}S_{T,n}(h)\leq S$. Then
for any $b>0$ we have

$\sum_{t=1}^{T}b\wedge I_{t}B_{t}^{2}=O\left(\left(\log\det
Z_{T}+\log(1/\delta)+S^{2}+b\right)\log\det Z_{T}\right)~{}.$ (25)

Combining the above lemmas we can bound the label complexity and regret
similar to Section A.1.

######  Lemma 19.

Let $\eta$, $J$ be as in Lemma 16, $\displaystyle m\geq
poly(T,n,\lambda_{0}^{-1},S,\log(1/\delta))$, and $\sqrt{2}S_{T,n}(h)\leq S$.
Then under event $\mathcal{E}$ for any $\epsilon\in(0,1/2)$ we have

$\displaystyle N_{T}$
$\displaystyle=O\left(T_{\epsilon}+\frac{1}{\epsilon^{2}}(\log\det
Z_{T}+\log(1/\delta)+S^{2})\log\det Z_{T}\right)$
$\displaystyle=O\left(T_{\epsilon}+\frac{1}{\epsilon^{2}}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\log\det(I+H)\right)~{}.$

######  Lemma 20.

Let $\eta$, $J$ be as in Lemma 16, $\displaystyle m\geq
poly(T,n,\lambda_{0}^{-1},S,\log(1/\delta))$, and $\sqrt{2}S_{T,n}(h)\leq S$.
Then under event $\mathcal{E}$ for any $\epsilon\in(0,1/2)$ we have,

$\displaystyle R_{T}$ $\displaystyle=O\left(\epsilon
T_{\epsilon}+\frac{1}{\epsilon}\left(\log\det{Z}_{T}+\log(1/\delta)+S^{2}\right)\log\det{Z}_{T}\right)$
$\displaystyle=O\left(\epsilon
T_{\epsilon}+\frac{1}{\epsilon}\left(\log\det(I+H)+\log(1/\delta)+S^{2}\right)\,\log\det(I+H)\right)~{}.$

The rest of the analysis follows from the same argument that relies on Lemma
23 (Appendix A.4) allowing one to replace $T_{\epsilon}$ by
$O\left(T\epsilon^{\alpha}+O\left(\log\frac{\log T}{\delta}\right)\right),$
and culminating into a statement very similar to Theorem 1.

####  A.3.2 Model Selection for Non-Frozen NTK Base Learners

The pseudocode for the model selection algorithm applied to the case where the
base learners are of the form of Algorithm 3 instead of Algorithm 1 is very
similar to Algorithm 2, and so is the corresponding analysis. The adaptation
to non-frozen base learners simply requires to change a constant.
Specifically, we replace ‘8’ in the $d_{i}$ test of Algorithm 2 with ‘432’,
all the rest remains the same, provided the definition of $B_{t,i}$ (querying
threshold of the $i$-th base learner) is now taken from Algorithm 3 ($B_{t}$
therein).

An analysis very similar to Lemma 11 shows that a well-specified learner is
(with high probability) not removed from the pool $\mathcal{M}_{t}$, while the
label complexity and the regret analyses mimic the corresponding analyses
contained in Section A.2.1 and A.2.2, with inflated constants and network
width $m$.

###  A.4 Ancillary technical lemmas

######  Lemma 21.

Let $i,j\in\mathcal{M}_{1}$ be two base learners. with probability at least
$1-2\delta$ the following concentration bound holds for all rounds $t$

$\displaystyle\left|\displaystyle\sum_{k\in\mathcal{V}_{t,i,j}}(\
1{1}{\left\\{a_{k,i}\neq y_{k}\right\\}}-\ 1{1}{\left\\{a_{k,j}\neq
y_{k}\right\\}}+h(x_{k,a_{k,i}})-h(x_{k,a_{k,j}}))\right|\leq
0.72\sqrt{|\mathcal{V}_{t,i,j}|L(|\mathcal{V}_{t,i,j}|,\delta)}~{}.$

###### Proof.

We write the LHS of the inequality to show as
$\left|\sum_{k=1}^{t}Y_{k}\right|$ where

$\displaystyle Y_{k}=\ 1{1}{\left\\{k\in\mathcal{V}_{t,i,j}\right\\}}(\
1{1}{\left\\{a_{k,j}=y_{k}\right\\}}-\
1{1}{\left\\{a_{k,i}=y_{k}\right\\}}+h(x_{k,a_{k,i}})-h(x_{k,a_{k,j}})).$

and let $\mathbb{E}_{k}$ and $\operatorname{Var}_{k}$ denote expectation and
variance conditioned on everything before $y_{k}$ (including
$x_{k},a_{k,i},a_{k,j}$ and $i_{k}$). Note that $Y_{k}$ is a martingale
difference sequence since $\mathbb{E}_{k}Y_{k}=0$. Further, $H_{k}=\
1{1}{\left\\{k\in\mathcal{V}_{t,i,j}\right\\}}(1+h(x_{k,a_{k,i}})-h(x_{k,a_{k,j}}))$
and $G_{k}=-\
1{1}{\left\\{k\in\mathcal{V}_{t,i,j}\right\\}}(-1+h(x_{k,a_{k,i}})-h(x_{k,a_{k,j}}))$
are predictable sequences with $-G_{k}\leq Y_{k}\leq H_{k}$. Thus, we can
apply Lemma 27 and get that with probability at least $1-\delta$, for all
$t\in\mathbb{N}$

$\displaystyle\sum_{i=1}^{t}Y_{i}$ $\displaystyle\leq 1.44\sqrt{(W_{t}\vee
m)\left(1.4\log\log\left(2\left(\frac{W_{t}}{m}\vee
1\right)\right)+\log\frac{5.2}{\delta}\right)}$ $\displaystyle\leq
0.72\sqrt{|\mathcal{V}_{t,i,j}|\left(1.4\log\log\left(2|\mathcal{V}_{t,i,j}|\right)+\log\frac{5.2}{\delta}\right)}=0.72\sqrt{|\mathcal{V}_{t,i,j}|L(|\mathcal{V}_{t,i,j}|,\delta)}$

where $W_{t}=|\mathcal{V}_{t,i,j}|/4$ and $m=1/4$. We can apply the same
argument to $-Y_{k}$ which yields the statement to show. ∎

######  Lemma 22.

For any $i\in\mathcal{M}_{1}$ the number of rounds in which $i$ was played is
bounded with probability at least $1-\delta$ for all $t\in[T]$ as

$\displaystyle|\mathcal{T}_{t,i}|\leq\frac{3}{2}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta)~{}.$

###### Proof.

###### Proof.

We can write the size of $T_{t,i}$ by its definition as
$|\mathcal{T}_{t,i}|=\sum_{k=1}^{t}\ 1{1}{\left\\{i_{k}=i\right\\}}$. We
denote by $\mathcal{F}_{k}$ the $\sigma$-field induced by all observed
quantities in Algorithm 2 before $i_{k}$ is sampled (including the set of
active learners $\mathcal{M}_{k}$). By construction
$(\mathcal{F}_{t})_{t\in\mathbb{N}}$ is a filtration. Note further that $\
1{1}{\left\\{i_{k}=i\right\\}}$ conditioned on $\mathcal{F}_{k}$ is Bernoulli
random variable with probability $p_{k,i}$. We can therefore apply Lemma 26
with $Y_{k}=\ 1{1}{\left\\{i_{k}=i\right\\}}-p_{k,i}$, $m=p_{1,i}$ (which is a
fixed quantity) and
$W_{t}=\sum_{k=1}^{t}p_{k,i}(1-p_{k,i})\leq\sum_{k=1}^{t}p_{k,i}$. This gives
that with probability at least $1-\delta$

$\displaystyle\sum_{k=1}^{t}\
1{1}{\left\\{i_{k}=i\right\\}}-\sum_{k=1}^{t}p_{k,i}\leq$ $\displaystyle
1.44\sqrt{L(t,\delta)\sum_{k=1}^{t}p_{k,i}}+0.41L(t,\delta)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta).$

Note that $W_{t}/p_{1,i}\leq t$ holds because the smallest non-zero
probability $p_{k,i}$ is $p_{1,i}$. Rearranging terms yields the desired
statement. ∎

∎

######  Lemma 23.

Under the low-noise assumption with exponent $\alpha\geq 0$, each of the
following three bounds holds for any $i\in[M]$ with probability at least
$1-\log_{2}(12T)\delta$:

$\displaystyle\forall
t\in[T],\epsilon\in(0,1/2)\colon\quad|\mathcal{T}_{t,i}^{\epsilon}|$
$\displaystyle\leq 3\epsilon^{\alpha}\sum_{k=1}^{t}p_{k,i}+2L(t,\delta),$ (26)
$\displaystyle\forall
t\in[T],\epsilon\in(0,1/2)\colon\quad|\mathcal{T}_{t,i}^{\epsilon}|$
$\displaystyle\leq
3\epsilon^{\alpha}|\mathcal{T}_{t,i}|+2L(|\mathcal{T}_{t,i}|,\delta),$ (27)
$\displaystyle\epsilon\in(0,1/2)\colon\qquad T_{\epsilon}$ $\displaystyle\leq
3\epsilon^{\alpha}T+2L(T,\delta)~{}.$ (28)

###### Proof.

We here show the result for Eq. (26). The arguments for Eq. (27) and Eq. (28)
follow analogously (by considering $\ 1{1}{\left\\{i_{k}=i\right\\}}$ and $1$
instead of $p_{k,i}$). To show Eq. (26), we first prove this condition for a
_fixed_ $\epsilon\in(0,1/2]$: We begin by writing $T_{t,i}^{\epsilon}$ by its
definition as

$\displaystyle|\mathcal{T}_{t,i}^{\epsilon}|=\sum_{k=1}^{t}\
1{1}{\left\\{i_{k}=i\right\\}}\
1{1}{\left\\{|\Delta_{k}|\leq\epsilon\right\\}}~{}.$

We denote by $\mathcal{F}_{k}$ the $\sigma$-field induced by all quantities
determined up to the end of round $k-1$ in Algorithm 2 (including the set of
active learners $\mathcal{M}_{k}$ but not $i_{k}$ or $x_{k}$). By construction
$(\mathcal{F}_{t})_{t\in\mathbb{N}}$ is a filtration. Conditioned on
$\mathcal{F}_{k}$, the r.v. $\ 1{1}{\left\\{i_{k}=i\right\\}}\
1{1}{\left\\{|\Delta_{k}|\leq\epsilon\right\\}}$ is a Bernoulli random
variables with probability $q_{k}\leq p_{k,i}\epsilon^{\alpha}$, because the
choice of learner and the distribution of $|\Delta_{k}|\leq\epsilon$ are
independent in each round and by low noise condition, the latter is at most
$\epsilon^{\alpha}$. We can therefore apply Lemma 26 with $Y_{k}=\
1{1}{\left\\{i_{k}=i\right\\}}\
1{1}{\left\\{|\Delta_{k}|\leq\epsilon\right\\}}-q_{k}$, $m=q_{1}$ and
$W_{t}=\sum_{k=1}^{t}q_{k}(1-q_{k})\leq\sum_{k=1}^{t}q_{k}$. This gives that
with probability at least $1-\delta$

$\displaystyle\sum_{k=1}^{t}\ 1{1}{\left\\{i_{k}=i\right\\}}\
1{1}{\left\\{|\Delta_{k}|\leq\epsilon\right\\}}-\sum_{k=1}^{t}q_{k}\leq$
$\displaystyle 1.44\sqrt{L(t,\delta)\sum_{k=1}^{t}q_{k}}+0.41L(t,\delta)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{k=1}^{t}q_{k}+1.45L(t,\delta),$

where the second inequality follows from AM-GM. Rearranging terms and using
$q_{k}\leq p_{k,i}\epsilon^{\alpha}\leq p_{k,i}$ gives for a fixed $\epsilon$

$\displaystyle|\mathcal{T}_{t,i}^{\epsilon}|\leq\frac{3}{2}\epsilon^{\alpha}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta)~{}.$
(29)

We now consider the following set of values for $\epsilon$

$\displaystyle\mathcal{K}=\left\\{\left(\frac{1}{3T}\right)^{1/\alpha}2^{\frac{i-1}{\alpha}}\colon
i=1,\dots,\log_{2}\left(\frac{3T}{2^{\alpha-1}}\right)\right\\}\cap\\{1/2\\}~{}.$

and apply the argument above for all $\epsilon\in\mathcal{K}$ which gives that
with probability at least $1-\delta|\mathcal{K}|\geq 1-\log_{2}(12T)\delta$,
the bound in Eq. (29) holds for all $\epsilon\in\mathcal{K}$ and
$t\in\mathbb{N}$ simultaneously. In this event, consider any arbitrary
$\epsilon\in(0,1/2)$ and $t\in[T]$. Then

$\displaystyle|\mathcal{T}_{t,i}^{\epsilon}|\leq|\mathcal{T}_{t,i}^{\epsilon^{\prime}}|\leq\frac{3}{2}{\epsilon^{\prime}}^{\alpha}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta),$

where $\epsilon^{\prime}=\min\\{x\in\mathcal{K}\colon x\geq\epsilon\\}$. If
$\epsilon^{\prime}$ is the smallest value in $\mathcal{K}$, then
$\frac{3}{2}{\epsilon^{\prime}}^{\alpha}\sum_{k=1}^{t}p_{k,i}\leq
1/2\leq\nicefrac{{1}}{{2}}L(t,\delta)$. Thus, the RHS is bounded as
$2L(t,\delta)$ in this case. If $\epsilon^{\prime}$ is not the smallest value
in $\mathcal{K}$, then by construction $\epsilon^{\alpha}\geq
2{\epsilon^{\prime}}^{\alpha}$ and the RHS is bounded as
$\frac{3}{2}{\epsilon^{\prime}}^{\alpha}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta)\leq
3{\epsilon}^{\alpha}\sum_{k=1}^{t}p_{k,i}+1.45L(t,\delta$. Combining both
cases gives the desired result for Eq. (26). ∎

######  Lemma 24 (Elliptical potential, Lemma C.2 [34]).

Let $x_{1},\dots,x_{n}\in\mathbb{R}^{d}$ and
$V_{t}=V_{0}+\sum_{i=1}^{t}x_{i}x_{i}^{\top}$ and $b>0$ then

$\displaystyle\sum_{t=1}^{n}b\wedge\|x_{t}\|_{V_{t-1}^{-1}}^{2}\leq\frac{b}{\log(b+1)}\log\frac{\det
V_{n}}{\det V_{0}}\leq(1+b)\log\frac{\det V_{n}}{\det V_{0}}.$

######  Lemma 25 (Randomized elliptical potential).

Let $x_{1},x_{2},\dots\in\mathbb{R}^{d}$ and $I_{1},I_{2},\dots\in\\{0,1\\}$
and $V_{0}\in\mathbb{R}^{d\times d}$ be random variables so that
$\mathbb{E}[I_{k}|x_{1},I_{1},\dots,x_{k-1},I_{k-1},x_{k},V_{0}]=p_{k}$ for
all $k\in\mathbb{N}$. Further, let
$V_{t}=V_{0}+\sum_{i=1}^{t}I_{i}x_{i}x_{i}^{\top}$. Then

$\displaystyle\sum_{t=1}^{n}b\wedge\|x_{t}\|_{V_{t-1}^{-1}}^{2}$
$\displaystyle\leq 1\vee 2.9\frac{b}{p}\left(1.4\log\log\left(2bn\vee
2\right)+\log\frac{5.2}{\delta}\right)+\frac{2}{p}\left(1+b\right)\log\frac{\det
V_{n}}{\det V_{0}}$

holds with probability at least $1-\delta$ for all $n$ simultaneously where
$p=\min_{k}p_{k}$ is the smallest probability.

###### Proof.

This proof is a slight generalization of the Lemma C.4 in [34]. We provide the
full proof here for convenience: We decompose the sum of squares as

$\displaystyle\sum_{t=1}^{n}b\wedge\|x_{t}\|_{V_{t-1}^{-1}}^{2}\leq\frac{1}{p}\sum_{t=1}^{n}(bI_{t}\wedge\|I_{t}x_{t}\|_{V_{t-1}^{-1}}^{2})+\sum_{t=1}^{n}\frac{1}{p_{t}}(p_{t}-I_{t})(b\wedge\|x_{t}\|_{V_{t-1}^{-1}}^{2})$
(30)

The first term can be controlled using the standard elliptical potential lemma
in Lemma 24 as

$\displaystyle\frac{1}{p}\sum_{t=1}^{n}(bI_{t}\wedge\|I_{t}x_{t}\|_{V_{t-1}^{-1}}^{2})\leq\frac{1}{p}\left(1+b\right)\ln\frac{\det
V_{n}}{\det V_{0}}.$

For the second term, we apply an empirical variance uniform concentration
bound. Let
$\mathcal{F}_{i-1}=\sigma(V_{0},x_{1},p_{1},I_{1},\dots,x_{i-1},I_{i-1},x_{i},p_{i})$
be the sigma-field up to before the $i$-th indicator. Let
$Y_{i}=\frac{1}{p_{i}}(p_{i}-I_{i})\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge
b\right)$ which is a martingale difference sequence because
$\mathbb{E}[Y_{i}|\mathcal{F}_{i-1}]=0$ and consider the process
$S_{t}=\sum_{i=1}^{t}Y_{i}$ with variance process

$\displaystyle W_{t}$
$\displaystyle=\sum_{i=1}^{t}\mathbb{E}[Y_{i}^{2}|\mathcal{F}_{i-1}]=\sum_{i=1}^{t}\frac{1}{p_{i}^{2}}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge
b\right)^{2}\mathbb{E}[(p-I_{i})^{2}|\mathcal{F}_{i-1}]$
$\displaystyle=\sum_{i=1}^{t}\frac{1-p_{i}}{p_{i}}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge
b\right)^{2}\leq\sum_{i=1}^{t}\frac{b}{p_{i}}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge
b\right)\leq\sum_{i=1}^{t}\frac{b^{2}}{p_{i}}.$

Note that $Y_{t}\leq b$ and therefore, $S_{t}$ satisfies with variance process
$W_{t}$ the sub-$\psi_{P}$ condition of [22] with constant $c=b$ (see Bennett
case in Table 3 of [22]). By Lemma 26 below, the bound

$\displaystyle S_{t}\leq$ $\displaystyle~{}1.44\sqrt{(W_{t}\vee
m)\left(1.4\ln\ln\left(2(W_{t}/m\vee 1)\right)+\ln\frac{5.2}{\delta}\right)}$
$\displaystyle+0.41b\left(1.4\ln\ln\left(2(W_{t}/m\vee
1)\right)+\ln\frac{5.2}{\delta}\right)$

holds for all $t\in\mathbb{N}$ with probability at least $1-\delta$. We set
$m=\frac{b}{p}$ and upper-bound the RHS further as

$\displaystyle
1.44\sqrt{\frac{b}{p}\left(1\vee\sum_{i=1}^{t}\left(b\wedge\|x_{i}\|^{2}_{V_{i-1}^{-1}}\right)\right)\left(1.4\ln\ln\left(2bt\vee
2\right)+\ln\frac{5.2}{\delta}\right)}$
$\displaystyle+0.41b\left(1.4\ln\ln\left(2bt\vee
2\right)+\ln\frac{5.2}{\delta}\right)$
$\displaystyle\leq\frac{1}{2}\left(1\vee\sum_{i=1}^{t}\left(b\wedge\|x_{i}\|^{2}_{V_{i-1}^{-1}}\right)\right)+1.45\frac{b}{p}\left(1.4\ln\ln\left(2bt\vee
2\right)+\ln\frac{5.2}{\delta}\right),$

where the inequality is an application of the AM-GM inequality. Thus, we have
shown that with probability at least $1-\delta$, for all $n$, the second term
in Eq. (30) is bounded as

$\displaystyle\frac{1}{p}\sum_{t=1}^{n}(p_{t}-I_{t})(b\wedge\|x_{t}\|_{V_{t-1}^{-1}}^{2})\leq\frac{1}{2}\left(1\vee\sum_{i=1}^{n}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge
b\right)\right)+Z.$

where $Z=1.45\frac{b}{p}\left(1.4\ln\ln\left(2bn\vee
2\right)+\ln\frac{5.2}{\delta}\right)$. And when combining all bounds on the
sum of squares term in Eq. (30), we get that either
$\sum_{i=1}^{n}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge b\right)\leq 1$ or

$\displaystyle\sum_{i=1}^{n}\left(\|x_{i}\|^{2}_{V_{i-1}^{-1}}\wedge b\right)$
$\displaystyle\leq 2Z+\frac{2}{p}\left(1+b\right)\ln\frac{\det V_{n}}{\det
V_{0}}$ $\displaystyle\leq\frac{4}{p}(1+b)\ln\frac{\ln(2bn\vee 2)5.2\det
V_{n}}{\delta\det V_{0}}$

which gives the desired statement. ∎

######  Lemma 26 (Time-uniform Bernstein bound).

In the terminology of [22], let $S_{t}=\sum_{i=1}^{t}Y_{i}$ be a
sub-$\psi_{P}$ process with parameter $c>0$ and variance process $W_{t}$. Then
with probability at least $1-\delta$ for all $t\in\mathbb{N}$

$\displaystyle S_{t}$ $\displaystyle\leq 1.44\sqrt{(W_{t}\vee
m)\left(1.4\log\log\left(2\left(\frac{W_{t}}{m}\vee
1\right)\right)+\log\frac{5.2}{\delta}\right)}$
$\displaystyle\qquad+0.41c\left(1.4\log\log\left(2\left(\frac{W_{t}}{m}\vee
1\right)\right)+\log\frac{5.2}{\delta}\right)$

where $m>0$ is arbitrary but fixed. This holds in particular when
$W_{t}=\sum_{i=1}^{t}\mathbb{E}_{i-1}Y^{2}$ and $Y_{i}\leq c$ for all
$i\in\mathbb{N}$.

###### Proof.

The proof follows directly from Theorem 1 with the condition in Table 3 and
their stitching boundary in Eq. (10) of [22]. ∎

######  Lemma 27 (Time-uniform Hoeffding bound).

Let $Y_{t}$ be a a martingale difference sequence and $G_{t},H_{t}$ two
predictable sequences such that $-G_{t}\leq Y_{t}\leq H_{t}$. Then with
probability at least $1-\delta$ for all $t\in\mathbb{N}$

$\displaystyle\sum_{i=1}^{t}Y_{i}$ $\displaystyle\leq 1.44\sqrt{(W_{t}\vee
m)\left(1.4\log\log\left(2\left(\frac{W_{t}}{m}\vee
1\right)\right)+\log\frac{5.2}{\delta}\right)}$

where $m>0$ is arbitrary but fixed and
$W_{t}=\frac{1}{4}\sum_{i=1}^{t}(G_{i}+H_{i})^{2}$.

###### Proof.

We use the results of [22]. In their terminology, Table 3 in that work shows
that $\sum_{i=1}^{t}Y_{i}$ is a sub-$\psi_{N}$ process with variance process
$W_{t}$. We can thus apply their Theorem 1 with the stitching boundary in
their Eq. (10) with $c=0$. Setting $\eta=2$ and $s=1.4$ gives the desired
result. ∎