Contextual Bandits with Online Neural Regression
Authors: Rohan Deb
Yikun Ban
Shiliang Zuo
Jingrui He
Arindam Banerjee
Venue: ICLR 2024 poster (2024)
Keywords: Neural Bandits
Contextual Bandits
Regret Bounds
Deep Learning
Online Regression
Primary area: optimization
TL;DR: Neural bandit algorithms with provable regret gurantees and significantly better empirical performance

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

Published as a conference paper at ICLR 2024
CONTEXTUAL BANDITS WITH ONLINE NEURAL REGRESSION
Rohan Deb, Yikun Ban, Shiliang Zhou, Jingrui He, & Arindam Banerjee University of Illinois, Urbana- Urbana-Champaige Champaign (rd22, y kunb2, szuo3, jingrui, arindamb) @cs. illilnnniiii edu
ABSTRACT
Recent works have shown a reduction from contextual bandits to online regression under a realizability assumption (Foster and Rakhlin, 2020; Foster and Krishna- murthy, 2021). In this work, we investigate the use of neural networks for such online regression and associated Neural Contextual Bandits (NeuCBs). Using existing results for wide networks, one can readily show a (VVT) regret for online regression with square loss, which via the reduction implics a D(VKT3/4 regret for NeuCBs. Departing from this standard approach, we first show (log regret for online regression with almost convex losses that satisfy QG (Quadratic Growth) condition, generalization of the PL Poolyak-Lojasiewicz condition, and that have a unique minima. Although not directly applicable to wide networks since they do not have unique minima, we show that adding a suitable small random perturbation to the network predictions surprisingly makes the loss satisfy QG with unique minima. Based on such a perturbed prediction, we show a (log T') regret for online regression with both squared loss and KL loss, and subsequently convert these respectively to Ó( /KT) and (VKLL" + K)) regret for NeuCB, where L is the loss of the best policy. Separately, we also show that existing regret bounds for NeuCBs are S?T)) or assume i.i.d. contexts, unlike this work. Finally, our experimental results on various datasets demonstrate that our algorithms, especially the one based on KL loss, persistently outperform existing algorithms.
INTRODUCTION
Contextual Bandits (CBs) provide a powerful framework for sequential decision making problems, where learner takes decisions over T rounds based on partial feedback from the environment. each round, the learner is presented with K context vectors to choose from, and a scalar output is generated based on the chosen context. The objective is to minimize' the accumulated output in T rounds. Many existing works assume that the expected output at each round depends linearly on the chosen context. This assumption has enabled tractable solutions, such as UCB-based approaches (Chu et al., 2011; Abbasi- Yadkori et al., 201 1) and Thompson Sampling (Agrawal and Goyal, 2013). However, in many real-world applications, the output function may not be linear, rendering these methods inadequate. Recent years have seen progress in the use of neural networks for contextual bandit problems (Zhou et al., 2020; Zhang et al., 2021) by leveraging the representation power of overparameterized models, especially wide networks (Allen-Zhu al., 2019b; Cao and Gu, 2019b; Du et al., 2019; Arora et al., 2019b). These advances focus on learning the output function in the Neural Tangent Kernel (NTK) regime and drawing on results from the kernel bandit literature (Valko al., 2013).
Separately, (Foster and Rakhlin, 2020) adapted the inverse gap weighting idea from Abe and Long (1999); Abe et al. (2003) and gave an algorithm (SquareCB) that relates the regret of CBs, Regeb (T) to the regret of online regression with square loss (TT The work uses realizability assumption: the true function generating the outputs belongs to some function class F. In this approach, the learner learns score for every arm (using online regression) and computes the probability of choosing an arm based on the inverse of the gap in scores leading to regret bound Regcu (T) O (D/KTRRR, (KTRsq(T)) (T)) Subsequently, Foster and Krishnamurthy (2021) revisited SquareCB and provided a modified algo- rithm (FastCB), with binary Kullback-Leibh (KI.) loss and re-weighted inverse gap weighting scheme that attains a first-order regret bound. A first-order regret bound is data-dependent in the
We use the loss formulation instead of rewards.

---

Published as a conference paper at ICLR 2024
sense that it scales sub-linearly with the loss of the best policy L instead of T. They showed that if regret of online regression with KL loss is (T) then the regret for the bandit problem can be bounded by RegcB(22 (2)) = O( O(VKL-KKL (T)) + (R))(T)). Further, under the realizability assumption, Simchi-Levi and Xu (2020) showed that an offline regression oracle with (log T) calls can also achieve an optimal regret for CBs. This improves upon the ((') calls to an online regression oracle made by SquareCB and FastCB but works only for the stochastic setting, i... when the contexts are drawn i.i.d. from a fixed distribution.
In this work we develop novel regret bounds for online regression with neural networks and subse- quently use the reduction in Foster and Rakhlin (2020); Foster and Krishnamurthy (2021) to give regret guarantees for NeuCBs. Before we unpack the details, we discuss the research gaps in existing algorithms for NeuCBs to better motivate our contributions in the context of available literature.
1.1 RESEARCH GAPS IN NEURAL CONTEXTUAL BANDITS
We discuss some problems and restrictive assumptions with existing NeuCB algorithms. Table 1 summarizes these comparisons. We also discuss why naively extending existing results for wide networks with the CBs online regression reduction lead to sub-optimal regret bounds. In Section F we further outline some related works in contextual bandits and overparameterized neural models.
Neural UCB (Zhou et al., 2020)) and Neural TS ((Zhang et al., 2021)): Both these works focus on learning the loss function in the Neural Tangent Kernel (NTK) regime and drawing on results from the kernel bandit literature (Valko et al., 2013). The regret bound is shown to be Ö(dvT), where d is the effective dimension of the NTK matrix. When the eigen- values of the kernel decreases polynomially, one show that d depends logarithmically in T (see Remark 4.4 in (Zhou et al., 2020) and Remark in (Valko et al., 2013)) and therefore the final regret is still Ö However in Appendix A we show that under the assumptions in the papers, the regret bounds for both NeuralUCB and S is (?T) in worst case.
2. EE-Net (Ban et al., 2022b): This work uses an exploitation network for learning the output function and an exploration network learn the potential gain of exploring at current step. Although EE-Net avoids picking up a d dependence in its regret bound, it has two drawbacks. It assumes that the contexts are chosen i.i.d. from given distribution, hold for real world CB problems. 2) needs to store all the previous networks until the current time step and then makes prediction by randomly picking network from all the past networks (see lines 32-33 in Algorithm I of Ban et al. (2022b)), a strategy that does not scale to real world deployment.
assumption that generally does not
3. SquareCB (Foster and Rakhlin, 2020) and FastCB (Foster and Krishnamurthy, 2021): Both these works provide regret bounds for CBs in terms of regret for online regression. Using online gradient descent for online regression (as in this paper) with regret (VVT), SquareCB and FastCB provide (v /KT3/44 and O( KL-1//4 + K (T) regret for CBs (see Example 2 in Section 2.3 of Foster and Rakhlin (2020) and Example in Section 4 of Foster and Krishnamurthy (2021) respectively). Existing analysis with neural models that use almost convexity of the loss (see Chen et al. (2021)) show (VTT) regret for online regression, and naively combining it with the SquareCB and FastCB lead to the same sub-optimal regret bounds for NeuCBs.
1.2 OUR CONTRIBUTIONS
Lower Bounds: As outlined in Section 1.1, we formally show that an (oblivious) adversary can always choose set of context vectors and reward function at the beginning, such that the regret bounds for NcuralUCB ((Zhou et al., 2020)) and NeuralTS ((Zhang et al., 2021)) becomes Q(T). See Appendix 1. and A.2 for the corresponding theorems and their proofs.
2. QG Regret:
We provide Ollog +eT regret for online regression when the loss function satisfies (i) e- almost convexity, (ii) QG condition, and (iii) has unique minima (ef. Assumption 2) long as the minimum cumulative loss in hindsight (interpolation loss) is Ollog T). This improves over the (VVT) + cT bound in Chen et al. (2021) that only exploits e- almost convexity.
3. Regret for wide networks: While the QG result is not directly applicable for neural models, since they do not have unique minima, we show adding a suitably small random perturbation to the prediction (10), makes the losses satisfy QG with unique minima. Using such a perturbed neural prediction, we provide regret bounds with the following loss functions:
2

---

Published as a conference paper at ICLR 2024
Algorithm
Regret
Remarks
NeuralUCB (Zhou al., 2020)
O(dVT)
Bound PT()) worst case.
NeuralTSS Zhang et al. (2021)
O(dvT)
Bound is Q(() in worst case.
Assumes that the contexts are drawn i.i.d and needs to store all previous networks.
EE-Net (Ban et al., 2022b)
Ö(VT)
No dependence on d and holds even when the contexts are chosen adversarially.
NeuSquareCB (This work)
Ö(VKT)
No dependence on d and holds even when the contexts are chosen adversarially.
NeuFastCB (This work)
Ö(VT<K + K)
Table Comparison with prior works. T the horizon length, L* is the cumulative loss the best policy, d the effective dimension of the NTK matrix and K is the number of arms.
(a) Squared loss: We provide Olog'") regret for online regression with the perturbed network (Theorem 3.2) and thereafter using the online regression to CB reduction obtain ((v (TT) regret for NeuCBs with our algorithm NeuSquareCB (Algorithm 1).
(b) Kullback-Leibler (KL) loss: We further provide Oloo T) regret for online regression with KL loss using the perturbed network (Theorem 3.3). ). To the best of our knowledge, this is the first result that shows PL/QG condition holds for KL loss, and would be of independent interest. Further, using the reduction, we obtain the first data dependent regret bound of Ö(VL* K + K) for NeuCBs with our algorithm NeuFastCB (Algorithm 2).
4. Empirical Performance:
Finally, in Section 5 we compare algorithms against baseline algorithms for NeuCBs. Unlike previous works, we feed contexts to the algorithms in an adversarial manner (see Section 5 for details). Our experiments various datasets demonstrate that the proposed algorithms (especially NeuFastCB) consistently outperform existing NeuCB algorithms, which themselves have been shown to outperform their linear counterparts such as LinUCB and LinearTS (Zhou et al., 2020; Zhang et al., 2021; Ban et al., 2022b).
We also emphasize that our regret bounds are independent of the effective dimension that appear in kernel bandits (Valko et al., 2013) and some recent neural bandit algorithms (Zhou et al., 2020; Zhang al., 2021). Further our algorithms are efficient to implement, do not require matrix inversions unlike NeuralUCB (Zhou et al., 2020) and NeuralT'S (Zhang et al., 2021), I), and work even when the contexts are chosen adversarially unlike approaches specific to the i.i.d. setting (Ban et al., 2022b).
NEURAL ONLINE REGRESSION: SETTING AND FORMULATION
Problem Formulation: At round E [T], the learner is presented with an input x, E X' C Rd and is required make real-valued predictions ft. Then, the true outcome Yt
[0, 1] is revealed.
The conditional expectation of ys given X, is given by some unknown function h: X + V, i.e., Ely. xx] = h(xx). Further, the context vectors satisfy ||x,|| s Vt e [T].
Assumption 1 (Realizability).
Neural Architecture: We consider a feedforward neural network with smooth activations as in Du al. (2019); Banerjee et al. (2023) and the network output is given by
f0,; m -1/2 @(m w,, (L) o(. Φ(m -1/ (3x) )..
(I)
where is the number of hidden layers and m the width of the network. Further, (1) E Rmmxd with Rmxm vl (2...., [.} are layer-wise weight matrices with W(( V: Rd is the last layer vector and s(-) is lipschitz and smooth (pointwise) activation function.
define
0. = (vec(W((") ..... (e (TTT
(2)
as the vector of all parameters in the network. Note that 0, E IR,, where = md + (L 1)m² + m total number of parameters.
3

---

Published as a conference paper at ICLR 2024
Regret: At time an algorithm picks 0g B, where B C R is some comparator class, and outputs the prediction f(0g;x)) Consider a loss function & y x y + R that measures the error between x00; and the true output yt- Then the regret of neural online regression with loss E is defined as
T R(T) = Σ (((xxx))
inf E ((;xx)) BEB
t=1
Given the definition of regret in (3), one might wonder if we are assuming that the function h in Assumption is somehow f(0;-) for some 0 B. Wide networks in fact can realize any function h on finite set of T points (see Theorem E. in Appendix E).
Remark 2.1.
Using almost convexity of the loss function for wide networks, Chen et al. (2021) show R(T) (V))) regret. Instead, we work with small random perturbation to the neural model prediction denoted by (see Section 3) with E- = f and consider the following regret:
T Σ Elv. f(0.:x,)) inf BEB
(T)
Σ f(0:
As we shortly show in Section 3, the surprising aspect of working with such mildly perturbed f is that we will get R(T) (log 7'). Further, the cumulative loss with such will also be competitive against the best non- ponpperttdeed f with 6 E B in hindsight (Remark 3.4).
Notation: n (t) (and (t(t) respectively) means there exists constant e such that n S ct (and 2 ct respectively). Further the notation n (t)) means there exist constants C1, C2 > 0 such that c,t t S I eat. The notations ((t), θ(t) further hide the dependence on logarithmic terms.
3 NEURAL ONLINE REGRESSION: REGRET BOUNDS
Our objective in this section is to provide regret bounds for projected Online Gradient Descent (OGD)
with the projection operator I (0) arginf&rezt |6' -112. The iterates are given by
oc+1 II (0. ni Vlyi,, f0 (00)))))). B
(5)
Definition 3.1 (Quadratic Growth (QG) condition). Consider a function J J :RP B and let the solution set be J = (0' 0' E arg ming J [()). }. Then J is said to satisfy the QG condition with QG constant μ1, if ((0) (((') 2 0 1|2 v0 RP \ where 6 the projection of 0 onto T
Remark 3.1 (PL = QG). The recent literature has extensively studied the PL condition and how neural losses satisfy the PL condition (Karimi al., 2016; Liu et al., 2020; 2022). While the Quadratic Growth (QG) condition has not been as widely studied, one can show that the PL condition implies the QG condition (Karimi et al., 2016, Appendix A), i... for p >
J(D) - J(0') <
1 J(O) 2p
(PL) = J(0) - J(0')
P 100 2
00
(QG)
Assumption 2. Consider a predictor g(0;x) x) and suppose the loss E( g(0; xt)), Vt E [T], satisfies
(a) Almost convexity, i.e., there exists O, such that v0,0 0' B.
(Cvtgg(0) x(): 2 Elye,g(0', x()) + (0 0', Vol(u, x.))) -
(6)
(b) QG condition i.e., 3u > O. such that 40 E B O where O
(0, O0, E arginfo ((ve,g(0; ((0:xx1) and 07 is the projection of onto 0, we have
((0,,((0xx.)) E(y,, x.)) > (c) has a unique minima.
# 0 0,
Following (Liu al., 2020; 2022), we also assume the following for the activation and loss function.
Assumption 3. With & := E(y,, De). E. = dee Lipschitz, ie., (ll X, strongly convex, iee. Eyt 2 and smooth, ie., Cr S b, for some X, a, b > 0.
dg. and E. := Lte we assume that the loss E(ye, Dc) is dØ.
4

---

Published as a conference paper at ICLR 2024
Theorem 3.1 (Regret Bound under QG condition). Under Assumptions and 3 the regret of 1. where μi is the QG constant from Assumption 2(b), satisfies ptt
projected OGD with step size Tp-
X2 R(T) o ( 4
TogT) + cT + 2inf BEB
Σ
(()),
(8)
The proof of Theorem 3.1 can found in Appendix C.I.
Remark 3.2. Under Assumption 2(a), Chen al. (2021) show =(T)= + cT. In contrast our bound improves the first term to (log 7) but has an extra term: cumulative loss of the best O, and uses two additional assumptions (2(b) and 2(c)). Note that the third term vanishes if g interpolates and the interpolation loss is zero (holds for e.g., with over-parameterized networks and square loss). Further for peeepparameterieed networks Chen et al. (2021) show that = 1/poly(m), and therefore the eT term is (1) for large enough m. A similar argument also holds for our model.
Next we discuss if Theorem 3.1 can indeed be used for neural loss functions. For concreteness consider the square loss &sq (Yt. f(0x;x))
{yt f(0;; x;))?. Following Liu et al. (2020); Banerjee et al. (2023), we make the following assumption on the initial parameters of the network.
(1) Assumption 4. We initialize Og with Wo,i ~ NO0 az) for E [T.] where on 2
0,
and Vo is a random unit vector with ||vol22 1.
Next we define (0) == f(; x.), V ])] RTxT to be the so-called Neural Tangent Kernel (NTK) matrix at (Jacot et al., 2018) and make the following assumption at initialization.
Assumption 5. (f) is positive definite, i.e., (NTK(6o) ł= A some Àu > 0.
Remark 3.3. The above assumption on the NTK common in the deep learning literature (Du et al., 2019; Arora et al., 2019b; Cao and Gu, 2019a) and is ensured long any two context vectors X, do not overlap. All existing regret bounds for NeuCBs make this assumption (see Assumption 4.2 in Zhou et al. (2020), Assumption 3.4 in Zhang al. (2021) and Assumption 5.1 in Ban et al. (2022b)).
Finally we choose the comparator class = (Frob(B))) ) the layer- wise Frobenius ball around the initialization 9n with radii p. Pi (to be chosen as part of analysis) which is defined
Brob (0o) = {0 E IR" as in (2): vce( vee(W,"))l Il2 S p. E [I], - Volla S p1]. (9)
Consider network x(0: that satisfies Assumption 5 with do initialized as in Assumption 4. Then for B = (Foobb(B)) (6o) we can show the following: (i) Esg satisfies Assumption 2(a) with e = Oppoly L. p.P.) p, (1). /mm) (Lemma 13) and therefore with m = (poly((T, L, p)))), the second term in (8) is 0()) (ii) Esq for wide networks satisfies PL condition (Liu et al., 2022) which implies QG, and therefore Assumption 2(b) is satisfied. (iii) Further the network interpolates (Theorem E. which ensures that the third term in (8) is O, which makes the rhs (log T'). However neural models do not have a unique minima and as such we cannot take advantage of Theorem 3.1 as Assumption 2(c) is violated. To mitigate this, in the next subsection we construct randomized predictor f with Elf] f and show that Assumption 2(a), 2(b) and 2(c) hold in high probability.
3.1 REGRET BOUNDS FOR SQUARED LOsS
To ensure that the loss has a unique minimizer at every time step, we consider a random network with small perturbation to the output. In detail, given the input X,, we define a perturbed network
P f(0,, Xx, E) = (0,; x:) + C
(0. oo)TeyE,
(10)
j=1 m/11
where f(;;; x;) is the output of the network as defined in (1), cp is the perturbation constant to be chosen later, {e are the standard basis vectors and ε = (E1. sp,) is a random vector where Ey is drawn i.i.d from a Rademacher distribution, i.e., P(E, = +1) = Ple, = -1) -1)= 1/2.
(0, $)) has a unique Note that F = f. Further / ensures that the expected loss Eg Esg (Ve, f(0, xx, minimizer (see Lemma 14). However, since running projected OGD Eelsy (yt, /(0, xx,x)) E)) is not
5

---

Published as a conference paper at ICLR 2024
feasible, we next consider average version of it. Let Es, where each E,, is ii.d. Rademacher. Consider S such i..d. draws { ( and define the predictor
s
(is) X e( = Σ
f(0:x,,
(11)
s=1
where f(0;; Xt, Ea) is as defined in (10), We define the corresponding regret with square loss as Rsq (T)
T tsq (v. f(5) (0ci Xe, (Orixe,, (((:s),
min BEB (0o) PiPI
Esg
U/ f(5)
Xv. e(l:s)))
(12)
However, instead of running projected OGD with the loss Esy (B, F(5) X,, e e(lis)))
we use
clan ycs (0))
1
Esq yt F(0; (x)
(13)
S
Note that since Esy is convex in the second argument, using Jensen have
s E lsa ((;, (14)
1 E 2 f(0:x,,,)) ..) - Esy (ve. f(s) (0:x,, (1:))) = Ess ye S
S
Subsequently will show via (14) that bounding the regret with (13) implies bound on (12).
Theorem 3.2 (Regret Bound for square loss). Under Assumption 1, 4 and 5 with appropriate choice of step-size sequence {n.), width m, and perturbation constant Cp in (10), with probability at least (1 +) for some constant C. >> 0, over the randomness of initialization and {=} the regret in (12) of projected OGD with loss CL yt. (())) S G(log m) and projection ball Pipi (Bo) with p p= 0 (2o) and p1 = ((1) is given by Rsy = Olog T).
Proof sketch. The proof of the theorem follows along four key steps as described below. All of these hold with high probability over the randomness of initialization and { 1. A detailed version of the proof along with all intermediate lemmas and their proofs are in Appendix C.2. Note that we do not use Assumptions 2 and 3 and, but rather explicitly prove that they hold.
1. Square loss is Lipschitz, strongly convex, and smooth w.r.t. the output: This step ensures that Assumption 3 is satisfied. Strong convexity and smoothness follow trivially from the definition of the (sq. To show that {sq is Lipschitz we show that the output f(0; x, E) is bounded for any 0 E (B))) Also note from Theorem 3.1 that the lipschitz parameter of the loss, À appears in the log T term and therefore to obtain Oloo T) regret we also ensure that À = O(1)
2. The average loss in (13) is almost convex and has a unique minimizer: We show that with w.r.t.
S = Ollog m), the average loss in (13) is v Strongly Convex (SC) with v/ = O
0 E B.obb (0o). AL E [T] which immediately implies Assumption 2(a) and 2(c).
The average loss in (13) satisfies the QG condition: It is known that square loss with wide networks under Assumption 5 satisfies the PL condition (eg. Liu et al. (2022)) with μ O(1). We show that the average loss in (13) with = O(lo m), also satisfies the PL condition with
4 (1), which implies that it satisfies the QG condition with same μ.
4. Bounding the final regret: Steps 1 and above surprisingly show that with a small output perturbation, square loss satisfies (a) almost convexity, (b) QG, and (c) unique minima in Assumption 2. Combining with step 3, all the assumptions of Theorem 3.1 are satisfied by 2/ Using union bound over the three steps, invoking Theorem 3.1 we get with high probability
T
c(s Ut. (f(exxx,
inf dE Rethoo (9o)
Sq
(S) (ve. (f(0:xe, Ex)) 8x)]
1=1
T
<
2
inf
S
(S)
ue ([(::x(( Ex)) +0(og))))
(15)
BE
(Oo)
J.P1
1=1

---

Published as a conference paper at ICLR 2024
Algorithm 1 Neural SquareCB (NeuSquareCB); Uses Square loss
1: Initialize 0o. Y: {me)
2: for f 1, ..., I" do
3: Receive contexts X,,1:..., Xt,K, and compute Út,a j(s) (0; (0:Xr,, Va E [K] using
equation 11
4: Let b arg min Vt Pt.o (17((1.6-9..)))) and pc, 1 Eass Pt.o
5: Sample amm at ~ Pt and observe output yt,as
6: Update 0c+1 = II (60) (0: T/e V
L/g)) (yian (00 {.))
7:
end for
Finally we show inf in E 2gg (v,, (F(0"; :x; E.)) = =O(1 using the fact that
wide networks interpolate (Theorem E.1) which implies Σ ( ( (ye, (0 x,; E.)) )=m))
(log T)) which using (14) and recalling the definition in (13) implies Rse (T) = (log T) O
Remark 3.4. Note that ΣT= (( (ye. [f(r; =.)) )=))) = (log T) from step-4 above also im-
plies that Σr=1 <Sa (ve. [f(e,; x, {.)] minog BBseb (0o) Σi= Lsq (Ve. ((0,x))) (log T)
and therefore predictions competitive against f as defined in (1) well.
Remark 3.5. Although the average loss in (13) is SC (Lemmaa 6), we do not use standard results from Shalev-Shwartz (2012); Hazan (2021) to obtain (log T') regret. This is because, the strong convexity constant y O /ma. and although OGD ensures O(log T) regret for SC functions, the constant hidden by O scales as y /m. For large width models, m >> T, and therefore this approach does not yield a Oloog 2') bound. The key idea is to introduce bare minimum strong convexity using (10), ensure unique minima, without letting go of the QG condition with μ = O(1).
3.2 REGRET BOUNDS FOR KL LOSS
Next we consider the binary KL loss, defined as (KL, 0.) = y/ In
- (1- ve) In
Ve
-L
1-
((ge)
I-o(
where (v) The-y is the sigmoid function. Following the approach outlined in Section 1. we consider a perturbed network as defined (10). Note that here the output of the neural network is finally passed through sigmoid. As in (11), we will consider combined predictor. With slight abuse of notation, we define the prediction and the corresponding regret with lKL respectively as
o of (0: X e (1:))) = 5
(16)
T
RT..(T) = Σ lKi (yi, o (f(8) Xx,
e e(l:s))))
Σ tRI. (ye, o (f()) (0:) el (1::5))))
min Bibbb (Ba)
Theorem 3.3 (Regret Bound for KL Loss). Under Assumption 4 and 5 for yt E ||,, 2).
0 < 2 < 1, with appropriate choice of step-size sequence {ne ), width m, and perturbation constant Cp- with high probability over the randomness of initialization and {=} the regret of projected OGD with loss (15) (ye, {o(] X1, ex))) = = (xt. (ye. (J xx,)))))) S O(log m) and projection ball P.P1 (Foo with p ((VT/Xo) and = (1) is given by RxL(T") = O TT). The proof of the theorem follows a similar approach as in proof of Theorem 3.2 (See Appendix C.3).
NEURAL CONTEXTUAL BANDITS: FORMULATION AND REGRET BOUNDS
We consider contextual bandit problem where learner needs to make sequential decisions over T time steps. At any round & E [T]. the learner observes the context for arms Xt,,, X,,K E Rdd where the contexts can be chosen adversarially. The learner chooses associated output yt.,, E [0, 1] is observed. We make the following assumption on the output.
o, E [K] and then the
Assumption 6. The conditional expectation of Vt.a given Xt,a is given by h: Rd + [o, 1), Lee Elyr,a [xt,a] h(x1,a)- Further, the context vectors satisfy ||xx,al| S 1, 1 [7], [K].
7

---

Published as a conference paper at ICLR 2024
Algorithm 2 Neural FastCB (NeuFastCB); Uses KL loss
Initialize 0g. 7: {me)
2: for ? = 1, 2, .... I do
3: Receive contexts Xt,1. Xt.K and compute Dt.k. Vk E [K] using (16)
4: Let b, argmin Dt.k- Pt,k K + kE[R] 5: Sample arm a, ~ Pt and observe output yt,as
Be,be
-l.,)) -U.,,) &o E [K], and pt,b, Exeg, Pi,k-
6: Update 0.+1 [Bphh( (0: .7 V (yl,
Ex)
7:
end for
The learner's goal is minimize the regret of the contextual bandit problem and is defined the expected difference hetween the cumulative output of the algorithm and that of the optimal policy:
T
Regcb (T) = (ye.o. - (r,a;)
(17)
where of = arg [i] (x ) is the best action minimizing the expected output in round t. NeuSquareCB and NeuFastCB are summarized in Algorithm 1 and Algorithm 2 respectively. At time t, the algorithm computes f(()) (#: Xt.a: e e(l:))) Va E [K] using (11) (see line 4). then computes the probability of selecting an arm using the gap between learned outputs following inverse gap weighting scheme from Abe and Long (1999) (see line 6) and samples an action a, from this distribution (see line 7). It then receives the true output for the selected arm It,a, and updates the parameters of the network using projected online gradient descent. NeuF HeuFastCB employs a similar approach, except that it uses KL loss update the parameters of the network and uses a slightly different weighting scheme to compute the action distribution (Foster and Krishnamurthy, 2021).
Theorem 4.1 (Regret bound for NeuSquareCB). Under Assumption 6 and 5 with appropriate choice of the parameter % step-size sequence {nt} width m, and regularization parameter cp. with high probability over the randomness in the initialization and {s} the regret for NeuSquareCB with = ((VT/>u), P1 = (1) is given by Regcu (T) S Ō(VKT).
Theorem 4.2 (Regret bound for NeuFastCB). Under Assumption 6 and 5 with appropriate choice of the parameter step-size sequence {1t} width m, and regularization parameter Cp, with high probability over the randomness in the initialization and {=)s=1 the regret for NeuFastCB with = p=0(vTT ((VT/>o)) P1 = (11) is given by Regen(T) S Ó(VL-K + K), where L = E'= Ut.n
The proof of the Theorem 4.1 and 4.2 follow using the reduction from Foster and Rakhlin (2020) and (Foster and Krishnamurthy, 2021) respectively, and crucially using our sharp regret bounds for online regression Section We provide both proofs in Appendix D for completeness.
Remark 4.1. Note that since L < T' then O(VKL*) S O(VKT). Therefore NeuFastCB is expected to perform better in most settings "in practice", especially when 1," is small, i.e., the best policy has low regret. Also note that going by the upper bounds on the regret, especially the dependence on K, NeuSquareCB could outperform NeuFastCB only if L' O(T) and K >> T.
Remark 4.2. In the linear setting, (Azoury and Warmuth, 2001) gives (Tq S O (TT(p)) where is the feature dimension (Section 2.3, Foster and Rakhlin (2020)). This translates to Further with KI. loss, using continuous exponential weights gives ReL (T) O(p T/p) which translates to Regos (T) O( T/p KplogT/p) (Sec- tion 4, Foster and Krishnamurthy (2021)). However, with over- pee-pparameterized networks, (with p >> T), both bounds ((7). Therefore it becomes essential to obtain regret bounds that independent of the number of parameters in the network, which our results do.
Regas (7) < ((VpKT)
5 EXPERIMENTS
In this section, we evaluate the performance of NeuSquareCB and NeuFastCB, without output perturbation against some popular NeuCB algorithms. We briefly describe the settings and the baselines considered here. For more details, scaled-up version of Figure and a discussion on the effect of output perturbation, Appendix G).
8

---

Published as a conference paper at ICLR 2024
X10
covertype
X10
X10
Mag
EE-Ner Net NourafTS
NeuralTS
NeurafTS
Nourakkr
Neurake
Neural-
NBuSquaee
NeuSiquamCC
NauSSquan
NeuF astCB
NeuF aasCB
Neuf astB
1093
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
mushroom
Plants
shutte
X10
X10
X10
EE-Nol
EE Not
EE Not
NeumlLCCB
NeurstuCB
Ne.rsliCa
NouralTS
Nourak-z
Neurak-
Neural-c
NeuBquawwBB
NeuSquaraCB
NeufastCB
Neuf
1000
Rounda
Ruunds
Rounds
Figure 1: Comparison of cumulative regret of NeuSquareCB and NeuFastCB with baselines on openml datasets (averaged over 20 runs).
Baselines and Datasets. For comparison, choose four NeuCB algorithms: (i) Neural UCB (Zhou et al., 2020) (ii) Neural TS (Zhang et al., 2021), (iii) EE-Net (Ban et al., 2022h) and (iv) Neural-c greedy. We consider collection of 6 multiclass classification datasets from the openml.org platform: covertype, fashion, MagicTelescope, mushroom, Plants and shuttle. We follow the standard evaluation strategy as in Zhou et al. (2020); Ban al. (2022b) (see Appendix G for details).
Adversarial Contexts. In order evaluate the performance of the algorithms on adversarially chosen contexts, we feed data points to each of the model in the following manner: for the first 500 rounds, an instance x is uniformly sampled from each of the classes, transformed into context vectors as described above and presented to the model. We calculate the accuracy for each class by recording the rewards of this class divided by the number instances drawn from this class. the subsequent 500 rounds, we increase the probability of sampling instances from the class which had the least accuracy in the previous rounds. We repeat this procedure every 500 rounds.
Results. Figure plots the cumulative regret of all the algorithms across different rounds. All experiments were averaged across 20 rounds and the standard deviation is plotted along with the average performance. Although all the algorithms use a neural network to model the potential non- linearity in the reward, the baseline algorithms show erratic performance with lot of variance. Both our algorithms NeuSquareCB and NeuFastCB show consistent performance across all the datasets. Moreover, NeuFastCB persistently outperforms all baselines for all the datasets.
6 CONCLUSION
In this work, develop novel regret bounds for online regression with neural networks and subse- quently give regret guarantees for NeuCBs. We provide a sharp (log regret for online regression when the loss satisfies almost convexity, QG condition, and has unique minima. We then propose network with a small random perturbation, and show that this surprisingly makes the loss satisfy all three conditions. Using these results we obtain O T') regret bound with both square loss and KL loss and thereafter, convert these bounds to regret bounds for NeuCBs. Separately, we provide lower bound results for Neural UCB (Zhou et al., 2020) and Neural TS (Zhang et al., 2021) and show that oblivious adversary can choose sequence of contexts and a reward function that make their regret bounds (2T'). Our algorithms in contrast guarantee O(VT) regret, are efficient to implement, work even for contexts drawn by an adaptive adversary and does not need to store previous networks (unlike (Ban et al., 2022b)). Additionally,
experimental comparisons with the baselines various datasets further highlight the advantages of our methods and therefore significantly advances the state of the art in NeuCBs from both theoretical and empirical perspectives.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
The work was supported in part by grants from the National Science Foundation (NSF) through awards IIS 21-31335, OAC 21-30835, DBI 20-21898, IIS-2002540 well as a C3.ai research award.
REFERENCES
Y. Yadkii,, D. Pál, and C. Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
N. Abe and M. Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pages 3-11. Citeseer, 1999.
N. Abe, W. Biermann, and M. Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4))263-299 2003.
Agrawal and N. Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135. PMLR, 2013.
Z. Allen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. Advances in neural information processing systems, 32, 2019a.
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via over-parameterizzatoon In International Conference on Machine Learning, pages 242-252. PMLR, 2019b.
S. Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019a.
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019b.
K. S. Azoury and M. K. Warmuth. Relative loss bounds for on-line density estimation with the exponential family of distributions. Mach. Learn,, 43(3))211-244 jun 2001. ISSN 0885-6125. doi: (0.1023/A:10108960222
URL http: /twii o 10. 1023322:
Y. Ban and J. He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 913-923, 2020.
Y. Ban and J. He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, pages 2335-2346, 2021.
Y. Ban, J. He, and C. B. Cook. Multi-facet contextual bandits: neural network perspective. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 35 45, 2021.
Y. Ban, Y. Qi, T. Wei, and J. He. Neural collaborative filtering bandits via meta learning. arXiv 2022a.
preprint arXiv:2201.
Y. Ban, Y. Yan, A. Banerjee, and J. He. EE-net: Exploitation neural networks in contextual bandits. International Conference on Learning Representations, 2022b. URL https:/ / openreview net forum?
A. Banerjee, Cisneros-Velarde L. Zhu, and M. Belkin. Restricted strong convexity of deep learning models with smooth activations. In The Eleventh International Conference on Learning Representations, 2023. URL https: tetttps://ppereeeeeeee http://ppeeeeiieeeeee/eeeeeeeeee
f i INRbk7h01.
Y. Cao and Q Gu. Generalization error bounds of gradient descent for learning over-parameterized deep relu networks. AAAI Conference on Artificial Intelligence, 2019a.
Y. Cao and Q. Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019b.
10

---

Published as a conference paper at ICLR 2024
Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 745-754. PMLR, 10-15 Jul 2018.
X. Chen, E. Minasyan, J. D. Lee, and E. Hazan. Provable regret bounds for deep online learning and control. arXiv preprint arXiv:2110.0780) 2021.
W. Chu, L. Li, Reyzin, and R. Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pages 208-214. JMLR Workshop and Conference Proceedings, 2011.
S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019.
D. Foster and A. Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pages 3199-3210. PMLR, 2020.
D. J. Foster and A. Krishnamurthy, Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems. 34, 2021.
S. Frei and Q Gu. Proxy convexity: unified framework for the analysis of neural networks trained by gradient descent. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances Neural Information Processing Systems, 2021. URL https: httpp:s///peeeeviieeee net/
E. Hazan. Introduction to online convex optimization, 2021.
J. Honorio and T. Jaakkola. Tight Bounds for the Expected Risk of Linear Classifiers and PAC-Bayes Finite-Sample Guarantees. In S. Kaski and J. Corander, editors, Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, volume 33 of Proceedings of Machine Learning Research, pages 384 392, Reykjavik, Iceland, 22-25 Apr 2014. PMLR. URL https: httpp/ppcceeegggeeeeeeep mlr press v33 honoriole html.
A. Jacot, F, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. Advances in neural information processing systems, 31, 2018.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and mooimall-gradien methods under the Polyak-lojasiewiczz condition. In Joint European conference on machine learning and knowledge discovery in databases, pages 795-811 Springer, 2016.
C. Liu, L. Zhu, and M. Belkin. On the linearity of large non lonelin models: when and why the tangent kernel is constant. Advances in Neural Information Processing Systems, 33:15954-15964 2020.
C. Liu, L. Zhu, and M. Belkin. Loss landscapes and optimization in parrpaarmeterizze non- non-linear systems and neural networks. Applied and Computational Hurmonic Analysis, 59:85-116, 2022.
Lojasiewicz. A topological property real analytic subsets (in french). In Les équations aux dérivées partielles, pages 87-89. Coll. du CNRS, 1963.
X. Lu and B. Van Roy. Ensemble sampling. In Proceedings of the 31 International Conference Neural Information Processing Systems, NIPS' 17, page 3260-3268, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 978151086096
B. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathe- matics and Mathematical Physics, 3(4):864-878, 1963. ISSN 0041-5553, doi: https://oi.org URL https: : wwwwwwww.....o..........ooowww// www.sceeeeeneecee.e rect com/ science/
article/pii/ 1tte///0001155533000000
Y. Qi. Y. Ban, and J. He. Neural bandit with arm group graph. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1379-1389, 2022.
Y. Qi. Y. Ban, and J. He. Graph neural bandits. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pages 1920-1931, 2023.
11

---

Published as a conference paper at ICLR 2024
C. Riquelme, G. Tucker, and J. Snoek. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference on Learning Representations, 2018. URL https:
1. Sason. On reverse pinsker inequalities, 2015.
S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@) in Machine Learning, 4(2):107-194, 2012. ISSN 1935-8237. doi: 10.1561/2200000018 URL http:/ /ttp://xxx.// doi. org/ 10. //////////0/00001..1
D. Simchi-Levi and Y. Xu. Bypassing the monster: faster and simpler optimal algorithm for contextual bandits under realizabiliity. ArXív, abs/2003. 12699, 2020.
M. Valko, N. Korda, Munos, I. Flaounas, and N. Cristianini. Finite-time analysis of kernelised contextual bandits. arXiv preprint axXv:1309.6869, 2013.
R. Vershynin. Introduction to the non-asymptotic analysis of random matrices, 2011.
T. Zahavy and S. Mannor. Neural linear bandits: Overcoming catastrophic forgetting through likelihood matching, 2020. URL https: /ttp//ppwweeww.eee/ee/e net Fowommdddrrggeaaeeereeooo..
W. Zhang, D. Zhou, I.. Li, and Q. Gu. Neural thompson sampling. In International Conference on Learning Representation (ICLR), 2021.
D. Zhou, L. Li, and Q. Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pages 11492-11500 PMLR, 2020.
12

---

Published as a conference paper at ICLR 2024
A COMPARISON WITH RECENT NEURAL CONTEXTUAL BANDIT ALGORITHMS
In this section we show that the regret bounds for NeuralUCB (Zhou et al., 2020) and Neural Thompson Sampling (NeuralTS) (Zhang al., 2021) is S2(T) in the worst case. We start with brief description the notations used these works. H the Neural Tangent Kernel (NTK) matrix computed from all the context vectors X [T] [K], and h(x) is the true reward function given a context x. The cumulative reward vector is defined as h (((xx))...,(((xx))
.....
With À the regularization parameter in the loss, the effective dimension d of the Neural Tangent Kernel on the contexts {x defined as:
log det H//A)
log(1 + T/A)
Further is assumed that = A (see Assumption 4.2 (Zhou al., 2020) and Assumption 3.4 in (Zhang et al., 2021)).
A.1 Q(T) REGRET FOR NEURALUCB
The bound the regret for NeuralUCB (Zhou al., 2020) is given by (ignoring constants):
(v dlog (1 1+
TK 1+
(Válog/
TK A xx+x)
Regeb Regcb(T) VT
dálog
+ vĀs
=T ddogg
1+
TK X
+ s + dlog
[+ TK
x )²)
= -BNICA (T, A),
where, À is the regularization constant and S 2 WhT with h = (M(x)),... M(XTK))² We provide two (2(T) regret bounds for NeuralUCB.
The first result creates an instance that an oblivious adversary can choose before the algorithm begins such that the regret bound is I(T)) The second result provides Q((T) bound for any reward function and set of context vectors as long as is (1))
K
|h
Theorem A.1. There exists reward vector h such that the regret bound NeuralUCB is lower bounded as
BruCE (A, 2 VKT.
V2
Proof. Consider the cigen-decompossitonn of H = US where columns of e RTKKTT are the normalized eigen-vectors ) of H and DhH is diagonal matrix containing the eigenvalues {h ( of H. Now,
TK Σ 1=1
TK Σ
S2 hh /UTUHHUTT UTh
(uTN)2E
(18)
(H
A
(
1=1
where & = min(
uu h)
Further observe that we can rewrite the effective dimension as follows:
log
TK II 1=1
111+A
)
A
TK Σ
1+
A(H)
d = log det((I H/A)
1=1
log(1 + TK/A)
log(1 + TK/A)
log
TKTKA
13

---

Published as a conference paper at ICLR 2024
Using these can lower bound BNUCH (T, X) as follows:
TK log
1 + x
(.(H)
TK
BRUCH (T, VT
log 1+
log (1 + TK
X
X
TK
TK log(1 + (H)
TK
+
log
1+
(H)
log (1
TK
A
TK
(H)
TK
TK
VT
log
+
+
log
1+ x
TK
(H)
TK Σ 1=1
(:(H)
2 V
log
1 +
+
log
1
X
\ H
A
TK
1
[1
1
VT
log
1+
+
E
y:log
y/
yi
A i E [TK]. Using this we can further bound BNUCB (T, A) as follows: where y A.(
TK
1
TK
Vilog (1+
BNUCH (T,B) VT
Σ
log
1
+
Y/
VTK
y/
Σ
TK
log
1 y/1
11)
Eyslog
11
1
VK
y/
TK
1
Σ
log
[+ y/
(1 + EMss)
VK
1=1
TK
1
Σ
(1 + Evs)
1=1
Mi
TKK
+ Eyi
VK
1 y/
1=1
2 K....
Recall that & = min(u, (u: h)². Now, consider an h that makes a x/4 angle with all the digen-vectore M4 í E [TK] and therefore { = : Note that for the positive definite assumption of NTK to hold, all the contexts need be distinct and therefore oblivious adversary can always choose such an h. In such case, the regret bound for NeuralUCB is B (T, X) = -(T)).
Remark A.1. Note that the ((T') regret holds for any h whose dot product with all the eigen vectors of H is lower bounded by constant.
Theorem A.2. For any cumulative reward vector h, with as as the condition number of the NTK matrix, the regret bound for NeuralUCB is
h
B (A, T) 2
VKT.
Kk
14

---

Published as a conference paper at ICLR 2024
Proof. Using the same notation in the previous section, we can lower bound S and d as follows:
S 2 Amin H 1
h//2
Xmax H
d= log H/AA) log Amin (I ((A)/
log(1 + 20) TK
log(1 + TK/A)
log (1 TK//))
log (1 + x
Using these we can lower bound SNUCB(T,K) A) as follows:
TK log(1 1 + Ap)
TK
BrucE (T 2 VT
log 1+
log (1 + TK)
X
A
log(1 An
x
TK
+ ||ball2/
TK
log
1+
Amax H)) log (1 +
TK
x
Ao 1
+ |
A
do
TVK
VTK log
log
1
A
Ao
A
TVK
VTK log
[+ hhl2
+
yoo
(1+
#
y
VK
y/
where y = and x Amaxi())
(H) is the condition number of of the NTK. Since y log(1 + 2) s 1 and
Ag
for T, K 2 1, we have
1 - 1
(1
BNUCH (T, TVK K
log
1
(19)
1/
1 +
|
2 TVK
(20)
1
+ y
[bll2
2 TVK
(21)
If h||
is O(1) then BNUCB (T, ) is !(T).
A.2 Q(T) REGRET NEURAL THOMPSON SAMPLING
The bound on the regret for Neural Thompson sampling (Zhang et al., 2021) is given by (ignoring constants):
RegeR (T) CTV(1 + Vlo T log K) (s ( dlog(1 - TK//N) V Addlog(1+ + +TK)
Válog((
:= B(T
We present two lower bounds on Byis (T) below. As NeuralUCB, the first result creates an instance that an oblivious adversary can choose before the algorithm begins such that the regret bound is R(T') and the second result provides an I(T)) bound for any reward function and set of context vectors as long as Ào is (1)).
Theorem A.3. There exists reward vector h such that the regret bound NeuralUCB is lower bounded as
BNUCB (A, A, 2 KT.
2
Proof. For Neural Thompson sampling the regularization parameter is chosen to be À = 1 1+ 1/T (see Theorem 3.5 in Zhang et al. (2021)) and therefore 1 < À < 2 for any T > 1. Therefore
15

---

Published as a conference paper at ICLR 2024
lower bound the effective dimension as,
TK
1+ Ar(H))
log
d log det(I (I + H/A)
log(1 + TK//)
log(1 TK/A)
TK
log 1 ((H))
TK
1+ (H(H)
Σ log
2
:=1
log(1 + TK/A)
log(1 + TK)
TK Σ log
(H)
TK
X:(HH)
Buts (T)
VT
V h
1+
log
1+
2
TK
TK
(H
TK Σ 1=
1+ (,
2 V E
Σ
Σ log
1+
+
log
H
2
2
where recall from equation 18 that
TK Σ A
S2 E
where & min(u (u: h)
Therefore
1
1
BTT 2 VT
Σ Yi log
1
log
1
2y,
TK
TK
1 2y
2 VT
Yo log
1+
log
1+
VTK
2y:
i=1
TK
M V
Σ
Eye log
1
+ log
1
VTK
2y/
2y,
1=1
TK
1
VT
Σ
log
1
(1 + Evi))
VTK
2y/
TK
1/2y:
VT
Σ
(1 + Evi)
VTK
+ 1/2y:
TK
1 + Ey
VT
VTK
+ 2yh
TK"
VTK
TVRS
As in the proof of Theorem A.1, for h making angle of x/4 with all eigen- of H. > 1 which proves the claim.
Theorem A.4. For any cumulative reward vector h, the regret bound for Neural Thompson sampling
A
B (A,s(AT)) T)
TVTK
2 X
16

---

Published as a conference paper at ICLR 2024
Recall, 1 $ A 2 for any T 2 1, and therefore can lower bound the effective dimension as,
d log det (I + H/A) TK log(1 + A0/A)
log Ao/A)
TK
lo [ + T)
log(1 +T//2)
log(1 + TK)
Therefore, using 5 A 2 and S 2 WhTH-'h,
BNIS (T) 2 VT ( VTK log(1 + -do/2) V VTK log(1 (1 + >u/2)
> TVTK + 2u/2)
2 TVTK 2n/2
2a/2
Ao
2 2VVTK 2 Ao
If Ao = ((1), (7) is ((T))
B BACKGROUND AND PRELIMINARIES FOR TECHNICAL ANALYSIS
Before proceed with the proof of the claims in Section 3, we state few recent results from Banerjee et al. (2023) that we will use throughout our proofs. We assume the loss to be the squared loss throughout this subsection.
Lemma (Hessian Spectral Norm Bound, Theorem 4.1 and Lemma 4.1 in Banerjee et al. (2023) ) Under Assumptions 3 and 4, for any x E X, 0 E BSpec (0o), with probubility at least (1 2(L+1) we have
V (0:x11) S
CH and Vm
[Vo 122 2
(22)
where,
CH = 11 + T,y + 1) (1 + pi)
vn max TE(L]
+ Lot max h())
(E(L]
p
h(l) = --1 + +1((0)
Σ 7
7 = 01
Vm
(2 (Se(22 + +1((2)))+1 +1) Bo7Ph(()))a))
Bah(l1) h(11))
max 18h<454
e² = (h(L+ + 1)) + - (1 p1) L+1
(1()))22(L-0)
m
Lemma 2 (Loss bounds, Lemma 4.2 in Banerjee et al. (2023)). Under Assumptions 3 and 4, for
7 = 01 + Vm. each of the following inequalities hold with probability at least (1- 2(1+1)
((0b) S cu,o, and E(O) S Cp for Froob (fu), where Ca.b 2 vi + 2(1 g(b)) and
g(a) a² + (0(0) Σl= a² for any a, b IR
Lemma 3 (Loss gradient bound, Corollary 4.1 in Banerjee et al. (2023)). Under Assumptions 3 and 2((+1) for 0 E p.pt (Oo), with probability at least (1-2(44) m7
we have [| 20/e(0)e S
2. with as in Lemma and Cpair as in Lemma 2.
Lemma 4 (Local Smoothness, Theorem 5.2 in Banerjee al. (2023)), Under Assumptions 3 and 4, BFrob (0o).
with probability at least (1 2(L+1)), v0,0 0' E B
m
E(0')= S (()) (0' - vo(()) + 110' -01 with
B == bo²
CH /prr
(23)
vm
with CH in Lemma 1, e as in Lemma 1, and cory as in Lemma 2. Consequently, is locally B-smooth.
17

---

Published as a conference paper at ICLR 2024
C PROOF OF CLAIMS FOR NEURAL ONLINE REGRESSION (SECTION 3)
C.I REGRET BOUND UNDER QG CONDITION (PROOF OF THEOREM 3.1)
Theorem 3.1 (Regret Bound under QG condition). Under Assumptions and 3 the regret of projected OGD with step size Th-- = 1 where is the QG constant from Assumption 2(b), satisfies ptt'
(?
X2 log T
R(T)= S O
-
+ ET - inf DEB
Σ
(8)
1
Proof. Take any 0' E B. By Assumption 2(a) (almost convexity) we have ((e: f(ye, ((0':xx)) S (0: - 8", Ve(ye. +
Note that for any 0 E B, we have
II
(0") 8 B
S =110" - -0112-
As result, for 0' E B, we have
|10+11 0'112 - 1|0: 011
- |10 1/11 V (0;;; (,;;,,)) - 0/ - 10:- 0
= 21, (0, - 8¹ Vi g (0; x, x,)) + n V Vi(ye g xx)x 1/
S 2mp (E(vr, (00; Elvt, 90';:9900'''' c) + x²²
Rearranging sides and dividing by 20 we get
e(ys, (() l(ye, g(f'; xx)) 110, 01 - |10++1 0013 + 11t x2 +c. (24)
2m
Let 17:- pe.
1. Then, summing (24) over 1,..., we have
T (Vv, g(01xxx)))
R(T) Σ
Σ
elve g(0;; x:))
<
T
110- - 01
1
1
+
X²e²
Σ
T
+
217
21/-1
2
1=1
1=1
COT
110, 0' + 0(2
log T)
+
8
Vm
T
M 4
ΣΣ 110, 0
1
110 0,
1 + 0 log T)) +
(25)
where 02 E arginf, Ely,, g(0; xt)). By Assumption 2(b), the loss satisfies the QG condition and by Assumption 2(c), it has unique minimizer, so that for 1 E [7]
Cly,, g(, xx)) C(v, x0):
1 0: 0:112
(26)
2
E(yr. 9(0'; xx)) e(v.. (0);
H 0' 0 1
(27)
2
Then, we can lower bound the regret as
T
R(T))
Elee, (lve,((0;:00 x0,:
Σ Eyy. ((0':x)))
1=1
T
T
Elye, g(): x(0) > t=1
((0',,(0':xx) ((1.,9(0;xx..)))
/
|10, 8,
flu, g(0::xx)))
(28)
2
18

---

Published as a conference paper at ICLR 2024
from (26) Multiplying (28) by and adding to (25), get
T {yt, ((1;
R())
Σ Cye g(f';
1=1
T
110' 00112 + 7) + eT Eiz (VV. ((0: g(0)x,)))))
1
4
2
O(2² (C ((0;;,(000;))))))) -(y)) O(\ log 1) + ET E f(yr. x(0);
(Wr,9(0% xx)) 0(12 +T.
Since 0' E B was arbitrary, taking an infimum completes the proof.
C.2 REGRET BOUND FOR SQUARE LOSs (PROOF OF THEOREM 3.2)
Theorem 3.2 (Regret Bound for square loss). Under Assumption 4 and 5 with appropriate choice of step-size sequence {n.), width m, and periurbation constant Cp in (10), with probability at least
(1 (t) for some constant C' > 0, over the randomness of initialization and {e} the regret in (12) of projected OGD with loss L
c(S) yy, { X1, E.)) S G(log m) and projection ball BBrob (On) with p = ((v O(vT/>o) and pi ((1) is given by (T) (log
P.p.
Proof. The proof follows along the following four steps.
1. Square loss is Lipschitz, strongly convex, and smooth w.r.f. the output:
This step ensures that Assumption 3 (lipschitz, strong convexity and smoothness) is satisfied. We show that the loss function Esg is lipschitz, strongly convex and smooth with respect to the output f(0); E) inside (fu) with high probability and { We will denote Asy OSq and bsq as the lipschitz, strong convexity and smoothness parameters respectively as defined in Assumption 3.
the randomness of initialization
Lemma For E BBxob(Oo) with probability (1- 2((+1)+1 m
over the randomness of ini- tialization and { the loss (yg f(0; s)) is lipschitz. strongly convex and smooth with respect to output f(0; X,, x), Further the corresponding parameters for square loss, Àsgs Osg and bsg are O(1).
Strong convexity and smoothness follow trivially from the definition of the ksq. To show that tsq Lipschitz we show that the output of the neural network f(0; x, is bounded for any BFrob (0.). Also note from Theorem 3.1 that X² appears the log term and therefore to obtain a Ollog T) regret we must ensure that hsy = O(1), which Lemma does. Note that
using a union bound over E (T] and Lemma it follows that with probability (1- 2(++1)+1)
also lipschitz, strongly convex and smooth with respect to each of the outputs f(0; xr, E.), E [S).
c. yt, {a(f((: x,, {
(9)
s-1)
The average loss in (13) almost convex and has a unique minimizer:
We show that with S = Ologg m), the average loss in (13) is v Strongly Convex (SC) with (00ro((0)) Vt E [Z] which immediately implics Assumption 2(a) (almost convexity) and 2(c) (unique minima).
#/ = O w.r.t.
19

---

Published as a conference paper at ICLR 2024
Lemma 6. Under Assumption and cp = V S8AsO with probability (1
2T(L+2)
over the
randommess of the initialization and {E.1ı-1r (sg ybs [f():x,,E,]]s. is v-strongly convex
with respect to 0 E p.P1 (00). where y = O
3. The average loss in (13) satisfies the QG condition:
known that square loss with wide networks under Assumption (positive definite NTK) satisfies the PL condition (eg. Liu et al. (2022)) with μ O(1). We show that the average loss in (13) with = (log m., also satisfies the PL condition with μ = O(1), which implies that satisfies the QG condition with same ys with high probability over the randomness of initialization E
Lemma 7. Under Assumption with probability (1- 2T(L+1)C)
). for some absolute constant
C> O, L (ve. (((0xx,, satisfies the QG condition over the randomness of the initialization and { with QG constant (().
4. Bounding the final regret.
Steps and 2 above surprisingly show that with small output perturbation, square loss satisfies (a) almost convexity, (b) QG, and (c) unique minima in Assumption 2. Combining with step 3, we have that all the assumptions of Theorem 3.1 are satisfied by the average loss. Using union bound over the three steps, invoking Theorem 3.1 we get with probability (1 T(L+1)C for some absolute constant C > O, with 0" = minge m (Bo) Σ S (S)
1/i {5(0; [x,
yes [[(0(:x
c(9) (v:, yvs [[(00xx,,Ex)]]
(29)
Sq
T
(()) ( U1, (f(0;;x;x,, Olog
$ 2
(30)
Next we bound Σ 1= (v.
using the following lemma.
Lemma 8. Under Assumption 1 and 5 with probability (1- 2T(L+1) over the randomness of
the initialization and {E,)sm we have Stncle (ur. {ī(0):
xt, e,) } s=1) 0(1).
Using Lemma 8 and (29) we have Σ Sg
( Uv, (f(00) e,) {.) = Ollog 7') which using
(14) and recalling the definition in (13) implies Rsy (T) Oloo T)
Next we prove all the intermediate lemmas in the above steps.
Lemma 5. For 0 E BEroh (fo), with probability (1 (1- [1-224114 2(++))+1 over the randomness of initializa- tion and { the loss Esa (ye f(0; Xx, E)) is lipschitz, strongly convex and smooth with respect to its output f(0; xt, e). Further the corresponding parameters for square loss, Asg- OSg and bsg are O(1).
Proof. We begin by showing that the output of both regularized and un an-regularized network defined in (10) and (1) respectively bounded with high probability over the randomness of the initialization and in expectation over the randomness of Consider any 0 E BFoob (0o) and x E A. Then, the
20

---

Published as a conference paper at ICLR 2024
output of the network in expectation w.r.t. Eg'S can be bounded as follows.
2
egos egss
Eg Fe] x,, = + 2 B
m//4
(0- 0o) exey (0 0o)
= =]] + 20
E [EE
vm
j=1
(0)
(0 0o)
$ 21)(0xx)11 + +20
Vm
2r
VT (x))1
100 0o! 1?
171
mm
(0) 2 | (x))1
2
- m
Teg (Lp + p1)²
Vm
(c) 2 (1 p1)
7*+ (0()))0)) 16(0)
Σ 3
m m+
vm rez (Lp + p1)
m
where 7 = 01 + 7 Here (a) follows from the fact that Bless,] = when i + j. and Blers;] =1
when i j. (b) follows from ||0 ool12 S Lp Pl. and (c) holds with probability (1- - j. and follows from the fact that ||v|| S |/vol |l + ||v voll S 1+ P1 and thereafter using the arguments in proof of Lemma 4.2 from Banerjee et al. (2023). Finally with a union bound over t E (7) and using Jensen we get with probability (1 27(+++1
m
01, E)1 1 E [()((xx),))
2
- 2(1+ + p1)2
(1*+10(0)
Σ 7--1 1=1
+
c (Lp + p1)3.
(31)
Vm
and e' differ only at the j-th variable where E is independent copy of e'j Now,
...., Now consider (5)
E Ejtt ... .,,, Ep) that
x) - F(8;x,, e')l = Greg
ml/1 1(0 0o))
eye; (A -0- 0o)² [),]
2Geg
<
m 100 0o),1
By McDiarmid's inequality we have with probability (1 5) over the randomness of (s:)e1
V2rces 1/4
[(0: - Elf(0: x, e)|
Σ (0 00)3
V2crog 110 00112v 90ll2/In(116) In(1/8)
ml 1/4
V20ne
(Lp + p1)//n(1/66)
m
Taking a union bound over E [T], with probability 5 over the randomness of {ei we have
V2cne (Lp + P1)
[I((0xx,,)) (l E)] 5
1/4
Choosing 8 = 1 we get with probability (1 - 1) over the randomness of {
Virre
-
[(00xx,,) - $)
<
(Lp + pi)ppiinmmm
m//4
21

---

Published as a conference paper at ICLR 2024
Combining with (31), we have with probability at least (1- 27(1++2)++1 the initialization and {e:)e= we have
over the randomness of
m
2
1f(0:x,))1s / 2(1 pi)2 8th (7++)0(0)
Σ
+
2
Teg
(Lp
p1)
Vm
Verze (I.p + pi))pi)nnn Vin(mT)
(32)
m//4
Finally taking a union bound over {E.)--1 for S = O(log m) and using the fact that m = ((T5L/A8) we get with probability least (1 (1- 2 over the randomness of the ini-
m
tialization and {e}..1. Vt E [T], [1) yt, (f(0:x, { }mm))) is lipschitz with Asy = (1).
Further 1/g = 1 and therefore the loss is strongly convex and smooth with asg bsg a.s. over the randomness of ( which completes the proof.
27((-2) Lemma 6. Under Assumption 5 and Cp VA with probability (1-
over the randomness of the initialization and {ex) Ch1 (wn [1(0; xe: (x)xxx;)))))))))))) s=1) is v-strongly convex with
m
respect Bryb (0o), where O vm
Proof. From (10) we have a.s.
Vof(0,x,, (of(0:x)
Greg
1/4
(33)
v2f(0,x,,E)) = ())((.))
(34)
Next, with & = (f(0, x,, - V1)
Volsa f (1,
X1, 8)) = VoVof x1,5)
Volso (v., [0. X1, e)) voJ x1. voVo + EVVI x),
where we have used the fact that 6 = and (0,xx vāf(0; x,) from (34).
Consider u Sp-1 the unit ball in RP. Then
8
u Vicls) (3) yt. (f(0xx,, x,, 8.) ) S
Σ 8=1
Vo.((:)
2s Vol x²
Va] )x
U2u
Creg
Cq,i + Creg
En,i + c
Es,
1/4
1/4
i= 1=1
+ +C, u (0;(()))))
S
=VVof(0:x)), u²² + 20 2)
Greg
u.E
ml 174
5
==1
1=1
rgg
U.UrE,,EEss +h, N² Vif(0: x;
(35)
22

---

Published as a conference paper at ICLR 2024
Notice that vs [S], r,
Ex) is a weighted sum of Rademacher random variables and therefore ||ul|2 = 1 sub- saub-gassiin.. Using Hoeffding's 's inequality, for a given t E [T],
s Σ ==1
Se S -5-12
P
r. -
-1 -1
Taking union bound we get [
1 5 2
Tee" <Te -S-01111
p r.
-
<
Further if r is as sub-gaussian, then r (v² ()) sub-exponential with == = 40? (see
Honorio and Jaakkola (2014, Appendix B)) and therefore r is (4v2,4) sub-exponential. Using Bernstein's 's inequality for given E (T'.
1 S
--- S W2 Se - min
Swz
P r
32
==1
Taking a union bound we get for any t E [T]
8
Te 1 min
[22g Swa
P
ET S w2 r
S
Now choosing W1 = W2 = 2.
we get for any t [T]
s
S Te Te--S99 -5%/
P
r.
S
S
2
8=1
P
1
2
E
1
$ Te 1/2 min
8
2
Te 8/8
VS 2 16
Observing that ET, 0, Er 1, combining with (35) and recalling that with probability
1 1)T++1)7 over the randomness of initialization, ||Vo] x,) ||2 em get with proba- v
m
bility at least 1 -e- 2(L+1)T
u V3 Uc. ([(: u (Vof(0;x)) u)² (Vof(0;x()) u)
Grg m2/4
Seg
Asy Cir Vm
+
2
Creg 2m 1/4
Term 7 minimized for (Vof(0;x,)). this back to the above equation we get
and the minimum value is
Substituting
m
VT (5) Sq y/ (f(0)x(
Greg
Geg
2
AsnC
4 4/m
2/m
vm
Geg
Asa CH
4/
Vm
Vm
where the last equality follows because 2 = CH Since S² S/8 for 2 1, we have for 70g z 16 with probability 2Te-TT-- 5/8
2((+1)T m
As / m
(9) v (2
yt, ([(0:x,,<)) ).))
> 0.
23

---

Published as a conference paper at ICLR 2024
Choosing max m, 16), we have with probability (1 27(1++2) initialization and {E,)a=1 we have
over the randomness of
Cmn 0. m
u ViL (9) (ve. (.))
which completes the proof.
Lemma 7. Under Assumption with probability (1 2T(L+1JC)
for some absolute constant C' > 0, Sq ye, (00;),, (=)) satisfies the QG condition over the randomness of the initialization and {e,) with QG constant O())
(S)
Proof. We have
(S) (Me. (x)_ -13 LLs (v. ((::)())))) 1|
V VCL.
S
88) - - v((;x,))))
5
52 ( -ye ls)
(36)
where F(0,xi) Rexd + R such that (F(0, = i(0: xx, E.), 1s an S-dimensional vector of I's and (0),x:) = (V, E.), oof
x,, {x)]]
Now,
P Σ Eeeos's)
(1),,))).s'' (Vf(0:x))
Gug
Σ ey f(;:x() 1/4 j=1
Geg
1/4
j=1
(V)(0:x)) + 1/ E.. (0; + Crez
Greg
ml/4 Ex¹
Cre
(V xt), v[(()x,)) + m//4 (Es, v.((;:)))
2
Creg (E., (0 x.)) + Vm 1/4
reg
(E., Ex)
where E, E S with (E.), = Es.j- Therefore,
2 ENEM
k(0,xi) (vf(0:x)) Vf(0:x)) +
vm
V v1(0;x,)
VS(0: x1) )x Tez
V V TEs
vf(0;;,) x T
V Tf(0;x) T
Grey
+ m 1/4
xf(0xx,) TE, vf(0:x,)
f(0;xx)) Es
V Tf(f:x, x, FE {((;x,)) T
Vf x, )
Vf(0; xx vf((;x,)
vf((xx;, T
Creg
m 1/4
v((0xx,) TES
f000xx,)
v[(0:x))
24

---

Published as a conference paper at ICLR 2024
where E is p S matrix whose columns E,. Next we give uniform bound the smallest eigenvalue of K (0, xx). Consider E S unit sphere in RS We have
Ge u EMEMU Vm
" (0, X2 u = (Vf(0) x vf((:x))) 1s is
Creg m /4
Ug (Vf(0xx,) V
='=1
111
Consider term T. We can lower bound it as follows
A0
(())))),, vf((0; 1s (V (Vf(0;x,) vf(0xx,)) 2
where the first inequality follows because (1g and the second inequality because for any Brrob (0o) with probability (1 2(L+1) over the initialization
m7
2cHUl
V((x Amin (Knin((NN((0) do
T(p + p1) 2 0,
(37)
vm
where the last inequality holds by choosing m 2 (Lotor)) 2(T /1g). To see why (37)
x8
holds observe that using the exact same argument as in (55) and (52) we have
CH T
(NTK(() - (0))l( S. 2/Te
|0 00l12
vm
P.Pi Using the fact that 0 Brob (Bo) we have
2cHel vm
[KNTK(() KNTK(Do)]l2
L(p + p1)
and therefore
Amin (KNTK(()
2 Amin ((NTT((00) - ||KTTK(0) KNTK (60)ll2
2c
2λo
L(p+ + p1) Vm
Next consider term I1. Since every entry of the p matrix ε is i.i.d Rademacher, using Lemma 5.24, Vershynin (2011), it follows that the rows are independent sub-gaussian, with the sub-gaussian norm of the any row [I(EM)) )ells> S C,, where C, is an absolute constant. Further using Theorem 5.39 from Vershynin (2011) we have with probability at least 2exp(-cM(()
Amin 2 /p CMVS-E -
where CM and cM depend on the maximum of sub-gaussian norm of the rows of EM, i.c.. max, [1(EM)))le ll which is an absolute constant. Choosing t vs, for some absolute constant c, with probability at least (1- uniformly for any S we have
Amin (ENTeM)) 2 vp- (OM + 1)V5
Noting that S = max { (16, logm) and p md (L 1)m² + have
m (Cas + 1) mlgmm..
Xmin (TTTEE)
2
Using m 2 64(CMM + 1)2, m logm 2 8v2(CAs + 1), with probability at least (1 ..). uniformly for any E 88-1 we have
a (T(STee)) 2 m/2
25

---

Published as a conference paper at ICLR 2024
Finally consider term III. We have
s
2VScreg
ΣΣ u (Vf((:x))' Vf(0xx,) Exx) m 1/1
Greg
m1/4 Σ U. (B::
Since each Ex.j is sub-gaussian, therefore v/(0xx,) is [V x x (S 2) sub-gaussian with zero mean. Using Hoeffding we have with probability at least - exp(
2V m2/44
2v Scog St m2/4
us V.(xx,)))
Choosing t = 3/ and noting that S = max 16, log m). we get with probability at least (1 m²?
2 SCeg Creg
Σ u (((
-160k (log m) 3/22 m)322 Z
m
m//4
where the last inequality used 1/4 16Gre and m m2/4(log m) -3/2 4v2. Finally get uniform bound over SS-1, we can use standard e-net argument with 1/4 and metric entropy log (see eg. proof of Theorem 5.39 in Vershynin (2011)). Using mílog m) m)- 2 8 log 9, with probability
at least (1 m uniformly for any u E 5 we have
2 2vScre
Σ
U. VVV[(0;)))
1/4
Combining all the terms and using m 2 4, we get with probability (1 2(++1)C) for some absolute
constant C' 0
m
1
1
52 (F(0;x,) ( (F0,x))(((0xx)) s) z
45 -11))ll
8
m
Σ
Lsq yes f(0; x1, X(s
64 log m
s=1
2 2/4 [/ yt {f(0; X1,
(x,)) {a))
where μ 128 where the last incquality follows from m(log m) n-- 2 1. Combining with (36) and using the fact that PL implics QG (see Remark 3.1) along with a union bound over E [T'] completes the proof.
Lemma 8. Under Assumption and 5 with probability (1- (T(++I)
over the randommess of the
initialization and { we have ΣT (S)) yv: (x)))
O(1).
Proof. Consider any 0 E Brobb (fp). We have
s
$
Sq yt. (f(0;x;,es)] )-)
Lsa yt. F(0:x,,
Σ s=1
(y: - f(0; Ex))))
5
25
8=1
2
F (0, 0a) egear
Vi - -f(((ix)) Grg
25
m 1/4
1=1
p
(0 0o eyE
(yc - f(0c; x:)²
2ereg (ye - f(0;;
m//4
j=1
(0 80) T Tyj
2
(38)
icg
5
1/4
8=1
/=1
11
26

---

Published as a conference paper at ICLR 2024
Consider term I.
s
0o) (
CjEss
1
P (0
0o))eas)
m²/4
m
S
Since Eajj is 1 sub-gaussian, I. is 11 0ol12 sub-gaussian. Using Hoeffding's inequality
s
)
r. 2 wi Se 0010////2000-00l1
==1
Taking a union bound we get t E [T]
8
P S
Σ
r. 2 w1
< <Te -e-5//
0ol1o2,
8=1
Next consider term I1.
1
0
00) T
1
8
00 00). J j=1
5
m/14
==1
Further if T is 0s sub-gaussian, then 1 is (v², (x) sub-exponential with 4/20 a = =oo² (see Honorio and Jaakkola (2014, Appendix B)) and therefore I is (4v2 0ol12: 4/10 00113) sub-exponential. Using Bernstein's 's inequality for given E [T],
S ET
min
r
2 W2
S
3210 fo 41e 60
8=1
Taking a union bound we get for any t E [T]
s
1 min
82
Swz
P
r
ET
2 - Te
5210-
410-0011
410
S
==1
Now choosing W1 0 00ll2, u2 = 110 - 0ol12 we get for any t E [T'
9
P
r3 2 110 B0ll2
Te -2122
9
S Te min f $
12
ET?
2 2 110 -001
==1
S Te 8/8
AS 2 16
2 100 - 00.... using the fact that Asg = 1y+ - f00xx,)) = e(1)
Observing that ET,, = 0, EI?
7m
with probability (1 2T(L+1)
(see proof of Lemma 5) and finally combining with (38) we get with 5588 2T(++1)
m
probability at least 1 - T(e
Te 5²
( (,) < Lsg (wz, (0:xx,)) + Geg 10
00l12
+
20reg Asq m²/4
|0
0ol1
2/m
Summing over i. and taking minge
pipl (Bo) over the left hand side we get for any 0 E Broob (0o)
T
min Σ BE P.Pi
(S) L yes (((0 s
Σ Lsg (v,, f00)x:))
Teg
00
00l12 +
20reg Asa
110 10-80p 00112
(Bo)
2/m m
1/4
1=11
27

---

Published as a conference paper at ICLR 2024
From Theorem E. we know there exists & E ( over the randomness of initialization we have f(0, xx) ys for any set of yr [0,1], [T]] which implies Lsg (Ve. f(0;x,)) x,) 0, vt (T]. Therefore
(6g) such that with probability at least (1- 2(++1)
T
T
(S) Sq
yc, [[(00x,,,,,,,))0 50+
Rgg 110 00l12 +
2crogAsq
10' 00ll2
2mm
m//4
(Lp + p1)² + 2Gzg Asy
( O11
(Lp + p1)
(39)
2/m
m/14
where (a) follows because 0' E BBaab (0g) implies 0' Bepte (0g) and (6) follows by choosing
m L/AB))
C.3 PROOF OF THEOREM 3.3
Theorem 3.3 (Regret Bound for KL Loss). Under Assumption and 5 for yt |z,1 =].
0 < = < 1, with appropriate choice of step-size sequence {ne }. width m, and perturbation constant cp. with high probability over the randomness of initialization and {e) the regret of projected OGD with loss ( (ye, {o( Xx, {))))=>)) = E lx (ye. (f e.)) S = O(lg m) and O @(VT/Xo) and (1) is given by RRI((") Ollog T).
projection ball BFrob (0o) with
Proof. The proof of the claim follows along similar lines as in the previous subsection. It consists of following four steps:
Binary KI. loss is lipschitz, strongly convex and smooth w.rt. the output.
We show that (gi (yt,, Uc) lipschitz, strongly convex and smooth with respect to the output BB
Dr = f(0; xx, E) inside p.P. (6)) almost surely over the randomness of initialization and e. We will use AKL, agL and bKL respectively to denote the lipschitz, strong convexity and smoothness parameter for (yt: Ut) (c.f. Assumption (lipschitz, strongly convex and smooth)).
(0o), the loss lxL Exa (yt, [(;; (0))), is lipschitz, strongly convex and smooth with respect to the output f(0; 1(0;,,, E) a.s. over the randomness of initialization and e. Further the parameters AKL, agL and bxt are (1).
Lemma 9.
For A E BFrob((b))
Note
that
Lemma
implies that
1
Σ
lKL (v., (ff: is also lipschitz, strongly convex and smooth a.s. with respect
S
1=1
each of the outputs [0;; xx,)))
2. The average loss at t E [T], ( (o.. is almost convext and has unique minimizer w.n.t.
We show that the random perturbation to output in (10) assures that (()) CKL yes (o))((xx,,,.)))) is strongly convex with respect to 0 BFroh(()) at
strong convexity parameter), which implies that every & [2'] (with very small O (_L (mm) satisfies 2(a) and 2(c).
Lemma 10. Under Assumption 5 and cp = V8AsgCn, with probability (1 (1-27(L+22) 2T(2+2) the randomness of the initialization and {EL) ((S) yt, fo( (o(f((xx is v-strongly convex with respect
m
BFFob (Bo). where = o vm
3. The average loss at / E [T], (()) yr: [o(](( (x,)(()) satisfies the QG condition.
28

---

Published as a conference paper at ICLR 2024
We show that the loss ckil (ye. (o(f(0; xx, x,, {z)))==> satisfies the QG condition (with QG constant 1s = =(1) with high probability over the randomness of initialization and (es (ex)a=1- Lemma 11. Under Assumption 5 with probability (1 ) )
some absolute constant C O, C (ve. [f(0:x(,Es)]== satisfies the QG condition the randomness of the inifialization and {es )= with constant = O(1).
Bounding the final regret.
The above three steps ensure that all the assumptions of Theorem 3.1 satisfied by the loss function <kr (ee (x)) Taking union over the events in the above three steps, invoking Theorem 3.1, get with probability (1 TLC) ) for some absolute constant C 0,
Σ 1=1
KL Ut, (o(f(() <kL'
2
(S) KL ytu (o(i(0;;x, + OllogT).
(40)
where
0"
min
yt, (o (o(((()
8E pipl
Next we bound
Σ
( yr (a(F(0 xx, using the following lemma.
Lemma 12. Under Assumption and with probability (1 TLC) for some absolute constant C' >> O over the randomness of the initialization huve
m
Σ
LL yes [a(J(0'; e.))) =0(1)
Using Lemma 12 and (40) have Σ
(S) KL
(v..
O(log T). which
implies RkL (T) < T).
Next we prove Lemmas 9,10,11 and 12.
Lemma 9. For 0 FFFbbb the loss ex (v., F(0; xx, e)) is lipschitz, strongly convex and smooth with respect to the output [(; xt; e) a.s. over the randomness of initialization and e. Further the parameters AKL, agL and bEL are (1)).
Proof. Consider E BSppec (B6). Now,
kk. = dlKL(V F(0, E),
df(0,x,, x) E)) - (1=))o(((xxx,e) - x1, x(,,
of(0)xx,,))
= (i (0, E)) + o(f(),x,,e)) (f0((((
= =o( xx, x)) M/-
It follows that AKL. < 2 a.s. since of((0, xx, E)), ys E [0, 1]. Further 0 < skk = o(f(0. xx, x))(1 af((0 x1, e))) 1 1/2 a.s. which completes the proof.
29

---

Published as a conference paper at ICLR 2024
Lemma 10. Under Assumption 5 and Cp = v CH, with probability (1 (1- 2T(1.-2)
over the
randommess of the initialization and {E,)s-1 cks) yv
is v-strongly convex
with respect to 0 E B (0o), where v O 1)
vm
Proof. In Lemma 5 we showed that [f;; E) bounded with high probability over the randomness
of initialization and e. Specifically from (32)) we have with probability at least (1 22)++))+1
over the randomness of the initialization and g
2
2(1 p1)2 (*t+ 10(0) Σxte
2 Vm
((0
To (Lp + p1)
/2ereg (Ipp + p1) (1)))))l((n Vl((MN)
m1/4
-maxx(0 x)
(41)
Since m (2(T%/18 it follows that Smax X,, E) x,,
0()). Now E (7), with q :== (fmax (0; x))
(42)
with probability at least (1 2T(++))+1 we have a (f(0,, x,, (a. (1 9)]
Next we show that LxL is strongly convex. Recall that
cki. (v
Σ EKL (f.,
and therefore we have
V vocki Ue x.,,
114 ==1
o(((0.x,ee))
(1 (1- (f
(-0(f(0,xx,E.))
g
Σ
(((l-o(f(0xx,e))))) - (u)
s ==1
1
Σ
[(]] E.)) vt) Vo (0,(0,,,,e.)
(43)
5
where we have used the fact that o'() = o()) -o))). Further the hessian of the loss given by,
Vicca (n, ([([((((xx
1
d (f(0 x,, (ff..x..e)))ofo.x...)........
+ x,, - v.
S d( 9) x., 1..
AxI. (0:x)))
Consider u E SP-1. the unit ball (s) TT Vzclal (ve, (o(f((; x,, {x))]
in R.. We want to show that
0. Now as in the proof of Lemma we can
show that with probability (1 (1-23 27 ()+))
m
2 q(1 - 9) = AKLCH Vm
V3c(()) (yh, X,,
4/m
CKLCH Vm
30

---

Published as a conference paper at ICLR 2024
8AKLCH O(1)
where the last equality follows because &
q(1 -
Lemma 11. Under Assumption 5 with probability (1 ( for some absolute constant C' >> 0, (()) ye {))) satisfies the QG condition over the randomness of the initialization and (s.)xz) with constant μ O(1).
Proof. Recall from (43) that we have,
8 V V (uo (o((((0x,,,,))))))
Σ
(o(((0,x,,))) ve),0x()))
5
and therefore,
s Vocki (v [o(F((0xx;x; = ((F(()x(,Es)) - vo) x1, Ea)
- - (rtp::/)))lalllltfeememooo///e/d
S
52 - (F)) - ytl
where F(0,x.): x1): 1Roxd - R such that (F x1)) o (f(0; E.)), ls is S-dimensional
vector I's and K(0, xt) = (( (V x,, E.), xof())x,, As the proof of Lemma 7 with
probability (1 (T(++
for some absolute constant C² > 0, we have
1 (F(0:x,) yels) K (0xxx))((((x)))) yo4s) 2 2p (()) Mr, [.))) (44) 52 with μ 128 and
8
Esq o ex))) Σ 5=1
5
Now using reverse Pinsker's inequality (see eg. Sason (2015), eq (10)) we have
DKL (ulllr (f00,x,, x,, x),) Esq (sg o (f(0, xx, E.)))
2q
where (pllg) is the KL divergence between p and and o of((0, x1, E)) [q, (1 9)} holds with probability at least (1 (1-21(14)) 2T(1++)+1 Using this we have with probability at least (1 T TLC) for
some absolute constant >>00 0,
(S) KLL yo (o(f((xxx,
-ckii fo(F(0' (x))
Σ DEL (vllo((((,xxx,)a))
(F
S < ( a (f(0,
c (19 yt,
S
2q
29
==1
Combining with (44) we get with probability at least ization and {
(1 TLC
over the randomness of the initial-
V Vockk) (o( ex))) |
2 n/ chill (u,, (or,for( (o(f((:x,,
c/3) cki (o((000 xx, (.),)))) {.)))
Therefore ((5)
ex)) satisfies the QG condition with μ' = O().
31

---

Published as a conference paper at ICLR 2024
Lemma 12. Under Assumption and 5 with probability (1- TLC) for some absolute constant C' 0 over the randomness of the initialization we have
Ecki cki (v,, (x, O(1)
Proof. Recall from the proof of Lemma that using reverse Pinsker's inequality we have with probability least (1 TLC) for some absolute constant C > 0,
cka (v.. (o(f(( x,, =.))I =
1 ( (u.. {ff)(0:x,,
2q
Therefore
Σ (8) LKL (v. (o((((((xx,, (.)x)
(8)
x.000x),)))))) yts fa((f( E.)) e.)) 0(1)
Sq
2g
where the last part follows from 39 the proof Lemma
Finally we can use Theorem E. to conclude that there exists 0 E B (0a) such that with probability
Ye for any set of yt E [g. - g) AL E [T] where is as defined in (42). Without loss of generality assume =
at least (1 2T(++1)) over the randomness of initialization we have (f
(otherwise the predictor can be changed to a [ xx)) for some constant k; that depends
on 2) and therefore we have with probability at least (1 TLC) for some absolute constant C m
minge (00) Et=1 lKL (ye, (f(O:x))) = O.
C.4 AUXILIARY LEMMAS
With slight abuse of notation, we have defined z, = (xx. V1) and C(0;2:) = E(yt. f(0; x:))
Lemma 13 (Almost Convexity of Loss). Under the conditions of Lemma 1, with high probability, vO' E B B (fo).
C(0'; 2.) 2 [(0riz)) + (0' 10'00''' 00, voL(O;;2)) + (0' Oz, VS(0"; 2z)) EE,
(45)
where 6 4(4a0(Lp p1) + p1)
vm for any 0" E 1BFrob (fo), where en and e are as in Theorem and X, are as in Assumption 3 (lipschitz, strongly convex, smooth).
Proof. Consider any 6' (Fo)) By the second order Taylor expansion around 6,, we have B
1 10' - 0.) 82 (((;(b; (0' 02)
c(0l;z;) = [(0;;z)) + (8' - 0., VoL(O(; +
2
002
where 0, = E0' + (1 - 00, for some & E [0, 1]. Since O,, 0' E BBetob (0o), we have
vec( vec(W: (( vec (w) )l| = || vec(W (0) + (1 E) vec vec(W,() vec(W: ||2
s El| vec(W ((0) ve) )/2 + +(1 -) veo (e) vec(Wo")) >|2
s Ep + (1 - E)p - P,
M vollz S V + (1 - -E)v,, - volle S Ell volla + (1 g) - v
< Epr + (1 <) - Pı
and therefore 0, BFobb (0%) which implies 0, E Buc the Taylor expansion, we have
(0o). Focusing on the quadratic form in
(0' 0.)T 02 OZ, z:) (0' 0.) = -0' - 0,)
0f(0;: x1) (f(0xx)))
+ 2 02 f((xx)))))
C 00
002
Tl.
00
202
1=1
a as xt)
02 5(0 x1)
0'
+ t,, 02)
(0) 0z)
n4
00
ag2
Ii
32

---

Published as a conference paper at ICLR 2024
f,, corresponds to the loss Eyy,, f(0;x))) and l. Li denote the corresponding first and second derivatives w.r.t Vr.: = f(0; xt). For analyzing J, choose any 8" E B (.))) Now, note that p.p1
11 1,3 0' 0g 05 xt)
11
00
;f(0";x,)
+ @f(6(;x,) _
;x(0"xx,)
2
8' 11
09
O2 0f(0":X/
0f(0;xx))
0f(0";x))
+a
0' -0,,
00
00
00
a5(0";x,)
0' Oz, 0f(0r:x.)
;5(0";x))
+ 20
0' O2:
00
00
00
Of(0"; x()
Of(0"; xx)
05(0;; x,)
O5(0"; xx)
20 00 12 00
2a
116'
0c1
00
00
00
(0)
2 (8' 8, ff("": x(():x,)) x1)
20g
CH
110 8" 22112 0.112
mm
(8)
16agcm Lp + p1)
2 a (6' 8., <5(0"; x,))
mm
where (a) follows from Proposition since 0. (00) and since [[') I e. and (b)
follows since ||0, 121 110' 0z|12, 110 2 s 2(L pı) by triangle inequality because 0, 8' 8, E Ppppp (0%)-
Eue
For analyzing 12, with Qt, (0' - 00)
00)(0xx)) 862
(0' 0,), we have
02 ((0;xx), (0' 0.) S 110' -0:13
0 f(0;:
CH 0 0.11
4c + pi) vm
0.) 10ua1 -0)) 002
S
002
Vm
since |10-- 0el1 s 2( + p1) by triangle inequality because 0',0, Og E Loter (0o). Further, since [ < A by Assumption 3 (lipschitz, strongly convex, smooth), we have
1 = 2,0 - -1:1Q.. 4(Lp+ + PH
Vm
Putting the lower bounds on 1 and Ly back, we have
(6' - 0.)) ((.))
4(4n0(Lp pı) + A)en + p1)2
(6' 0c) 2 (8' -,, vf(0"xx))
ag²
Vm
That completes the proof.
Lemma 14. Under Assumption 5 and Cwg /8As, with probability (1-2TC (T(++1)
over the randomness the initialization, the expected loss Eets, (v, f(0,x,, x), is v-strongly convex with respect BFrob
P.P. (0o), where O
vm
Proof. From (10) we have a.s.
vof(0,x,,)) Vof(O:x) Grog
6
(46)
ml/1
v2i(0,x,,
(2)((:))
(47)
33

---

Published as a conference paper at ICLR 2024
Next, with E (f(0,x,,E) -M))
-30)
Velsg(ui.f(0. ((0,),,))) = Te
(of(O,
i=1
1
F(0, xr, =
V of xx, e + + V x),
The
1=1
where have used the fact that e 1, and (2f(0,x,,e)
(85(0;x,) from (47). Taking
expectation with respect to E; and using (46) we get
nh
ViJEalsu (sR (Vt, ((,,x,,
E x)
+ (if(0xx)
n4
1
P
(oo(():e))
T
Eg
Vof(8;x,) + Creg
mz/r"1 Ei
Crcs
1/ Ci
Vif(0:x)
74g
n
n
E
Vol Vol((xx) + Crey
m²/4
-i
Vof(0ix))e
2
Greg
Gog
+, V2. (0;x;) EG5}
Vm
D1
Vol((xx,
+ C, (0;((;x,))
where the last equality follows from the fact that B[e,] = and E(E,e,] = f + j and E|a,s,] = 1 for j and therefore e I, the identity matrix. Now consider any u E R2, ||||| 1. We
want to show that 7 VT (s F(B, x,, 8)) >0 O.
Teg Vm
u T (e 5(0, E))
(n, vo](0; +
||u| + VV. x()u
1=1
(a)
Geg
mm
vm
Asq
CH
Vm
where (a) uses the fact that 16/1 < Asq and that (0) S Cu. holds with probability vm
(1 2(I++) from Proposition 1. Further (b) uses the fact that 2eg 2H Finally with m
union bound over [me],t E [T] and noting that was arbitrary conclude that with probability (1 2T(++1) over the randomness of initialization Eglsa (v.. f(0, x,, E)) is v-strongly convex
with / Cm
34

---

Published as a conference paper at ICLR 2024
D PROOF OF RESULTS FOR CONTEXTUAL BANDITS (SECTION 4)
Theorem 4.1 (Regret bound for NeuSquareCB). Under Assumption 6 and 5 with appropriate choice of the parameter ", step-size sequence {nt} width m, and regularization parameter Cp. with high probability over the randomness in the initialization and {E) the regret for NeuSquareCB with p (BVT/V/// P = (11) is given by Regcu(T) ((VKT)
Proof. Choosing 8 = 7 and 7 (T)) (27) in Theorem of Foster and Rakhlin (2020) we get:
E Regen (T) S 4 KTRs (T) + 8/ KTIn(2T)
Using Theorem 4.1 we have with probability at least (1 (1-244 2LC
for some absolute constant 0,
m
E (egee(())) (T)) Ö Ö(VKK(oo T) HT7K88KTlll (n(T)
S (VV)T)
which completes the proof.
Theorem 4.2 (Regret bound for NeuFastCB). Under Assumption 6 and 5 with appropriate choice of the parameter 7, step-size sequence { width m, and regularization parameter Cp. with high probability over the randomness in the initialization and {e} 1 the regret for NeuFastCB with O(VT/>o), = (1) is given by RegcB(T) O(VL-K + K), where L - Ut,et
Proof. Choosing 7 = max( / / (T), 10K) and using Theorem from Foster and Krishna-
murthy (2021) get
Regeb (T) = 40 (T) + 600 RKL (T)
Using Theorem 4.2 we have with probability at least (1 2L.C for some absolute constant C >>> 0,
E (Rgec((T)) (T)] s O(VL* T) + 600000llog Ō((KL KK)
which completes the proof.
Remark D.1. A keen reader might notice that the reduction in (Foster and Rakhlin, 2020) requires us to control (T) = Σ (sg(tn, bt) - Σ'= (sq(M), M(xx)), but our regret guar- antee is for (T) in (12). However, note that in step-4 of the proof of Theorem 3.2 we argued that ΣT Sq yt. xx,))
= -(1) and therefore our regret bound im- plies ΣT, (M,, Dt) S OloogT with ýT (B)) x,, (1:5)) which immediately implies Regs, (T) < O(logT) T). A similar argument follows for Foster and Krishnamurthy (2021).
(S)
35

---

Published as a conference paper at ICLR 2024
E INTERPOLATION WITH WIDE NETWORKS (PROOF OF THEOREM E.1)
In this section, we focus showing that under suitable assumptions, wide networks interpolate any given data. We assume l to be the squared loss throughout this subsection.
+ [0, 1] and any set of inputs X; E &t E Theorem E.1. Under Assumptions and 5, for any
[TT, for f(0;x) of the form equation 1, if the width m = S)(T*), there exists 0 E p.ps vT) and P1 @(1), such that with probability at least (1 (1=2(++)) we have with = 0 Xo
2(2+1)
f(0, xx) h(xx),, Vt [T]; further, there exists 0 B (fo) such that with probability at DiP1
least 2(1 we have [(0,x;) x,) Vt for any of Vt E [0, 1), E [T].
We start with outline of the overall proof, which has four technical steps, some of which follow from direct observations, assumptions, or existing results (especially on the NTK), and some require new proofs.
is sufficient prove the interpolation result showing x(0,x)) yr for any yt. as the result for the interpolation f(0, xz) h(xx) ) follow as special case with h(x,). Further we consider P1 which immediately implies the result for P1 (1)).
The interpolation analysis will utilize the fact that the NTK is positive definite at initialization. For simplicity, Assumption (positive definite NTK) takes care of this aspect for Theorem E.I, with Ao being the lower bound to minimum eigen-vate value of the NTK.
To show existence of which interpolates f(0, xx) Yt. [T], we in fact show that gradient descent on least squares loss with suitably small step size and suitably large width m will have geometrically decreasing cumulative square loss. The decreasing loss along with the fact
that the sequence of iterates 0₂ E BFrobb (0o) with e x ). = 0, i.e., stay within the closed ball, implies existence of E BFFob (Bg) which interpolates the data.
Two key properties need be maintained as the gradient descent iterations proceed: first, as = 0, i.e., the iterates stay within the ball; and second, the NTK corresponding to all 0g need to stay positive definite. As we will show, these two properties are coupled, and the geometric decrease of the loss helps in the analysis of both properties.
discussed above, the iterates Og E BBtob (fo) with p = ((
We define
((0) = Σ
eyy, f(0;
(48)
[=1
Lemma (NTK condition per step). Under Assumptions 5 and 4, for the gradient descent update 8.+1 0, n V ((),) for the cumulative square loss {(() = ΣT (Yn f(0xx,)) with 0, 8,t1 e (eroo((o)) with p = O Au ) O. with probability at least 2(L+1) over the initialization of model,
T n ((0))
Amia KNTK (f--1)) Amin (KNTK((.)) 4cH0²
(49)
vm"
where eи and are as in Lemma 1.
Proof. Observe that KNTK(0) = T( where the Jacobian
0f(0=z)) awar
af(0:)) awi2s
J(Ø)-
RR. (md+
(50)
as(a..)) OWiL2
36

---

Published as a conference paper at ICLR 2024
where the parameter matrices vectorized and the last layer W(L+1) Vo is ignored since will not be doing gradient descent on the last layer and its kept fixed. Then, the spectral norm of the change in the NTK is given by
|| KNTK (0++1) KNTK (0:)ll -10 J(0.) 112
[(( -(00))
J(O.)) -J -((+))) J((.)))(0))
(11(0441)122 + (1((0)))22) (1(())))) -1((0==))
(51)
Now, for any 0 E BBrob(
|J(0))1 (1(0 @f(0;an)
2 (a)
To²
00
where (a) follows from by Lemma 1.
Assuming Oc, 00+1
E
BBib (Oo), we have
[l) (1 VTg, that from equation 51 get
([(N)
(52)
Now, note that
- -(oo) -
(53)
0f (f(0++1;
Of(0;; x.n)
(54)
00
00
2
8 f(0e: mi)
T sup 0,,
|10 - Bell2
002
CHVT
10++1 - 0ell2
(55)
vm
CHVT
11e V(((t) 112
Vm
2en 2enVTe mm
Ne ((0+)
where (a) follows from the mean-value theorem with 0, E {(1 E) + f0r+ some Ç E [0, 1]}. (b) follows from Lemma since á E BPrb (86). (c) follows from the gradient descent update, and (d) follows from Lemma 3. Then, using equation 52, we have
(NII(((+1) - KNTK(O0]l < 4cH mn
vm" vm
(56)
Then, by triangle inequality
Amin (KNTK (0c+1))
2 Amin (KNTK (aarr((0)))(((XTee)))) - ([ KNTK(00)l2
W Xuin (KNTK (KxT(KKKK(B)) - 4cH
vm no (((0))
T
where (a) follows from equation 56. That completes the proof.
Theorem E.2 (Geometric convergence: Unknown Desired Loss). Under Assumptions and
consider the gradient descent update 8,41 Σn (ye - f(0; x; with step size
0, np v((e.) for the cumulative loss ε(0)
1
1) = = min
BN Xu
37

---

Published as a conference paper at ICLR 2024
with 3 as in Lemma 4. Then, choosing width m = Ag
and depth L O(1), with probability at
least (1- (1- 2(L+1)) we have {fr) C p.pp (f0) with 6 vT) ( = 0, for every t,
((0++1) S (1 - 11)00 E(Oo)
(57)
Proof. First note that with probability at least (1- 2(++1) all the bounds in Theorem 1, Lemma 2, and Corollary 3 hold, and so does Lemma since its proof uses these bounds.
Further, we note that for L O(1) we obtain the constant си O(1++ (4 vm )o()))
((1) following Lemma since P1 = O, where the last equality follows from the fact that m
Q T Ag
! and p 0 ((x ). We will use cи C2 for some suitable constant Co 0.
We also note that Ø² O((1 + 1 (1 + (1) + ()(+)))). Then, using the fact that, L = O(),
0 P1 = 0 and m = ( T"
C2 T' ) we obtain that o² O()) We will use e² S c3 for xg
some suitable constant C3 0.
Finally, we observe that Ep..y = O( (+)+ (see definition in Lemma 2). Then, taking the definition of 3 (as in Lemma 4), we have that B = =b²² + - (poly (1 +
+> + p Again,
vm
in similar fashion as in the analysis of the expressions си and p. we have that in our problem setting = (1) since P1 = 0. We will use 3 S C4 for some suitable constant C4 >> 0.
We now proceed with the proof by induction. First, for t = 1, we show that, based on the choice of the step size, 01 E BErob p.pr (0n) for 01 = 0. To see this, note that
(a) 0ll1 = n/| v/( I 200y /E(O))
110
-2 20n Teo = 207720
Ten,av
Ao
(c)
< 20/ Co
Ao
where (a) follows from Lemma 3, (b) from Lemma 2, (c) follows since e and P1 = 0 so
the last layer is not getting updated. Hence, 01 Bpoo (Fo)) We now take the smoothness property from Lemma 4, and further obtain
(fo).
3T
ε(11) Z(Ou) S (01 to vol(On)
+
100
6ull2
S 11 Vol(Bo)
2
3T
Vol(0o)
1|2
2
2
T11T
||
Too(0r))
L 1
(58)
1)
(ol(On))
|
(c)
S
26
KNTK
2
"
Amin (KNTK 11612 2 "ー 40)
"
2
< -720((00)
{(0,) < (1 n/)) ((Og),
where (a) follows from the gradient descent update; (b) follows from our choice of step-size S 1
,N
so that -(1
BnT
< :: (c) follows from the following property valid for any iterate 0, IRP,
2
Vol(0))/ Σ
En Vef(0nxm)
Σ
Cenlen (off = C. KNTK(00))
n=1
n=l
38

---

Published as a conference paper at ICLR 2024
where fj := [C,,,l E RY,, with f/ -(y; - x()):,,)) and li,n (yn, f(0,; (d) follows from the definition of minimum eigenvalue; and (e) follows from the following property valid for any iterate 0, E R",
N
N
1
4
Un
=(0); -4((0))
(59)
n=1
Notice that, from our choice of step-size 7 <
To we have that 1 17 E (0,1).
Continuing with our proof by induction, we take the following induction hypothesis: we assume that
E(0+) s (1 (1- ((0o)
(60)
and that 0,- BBrebbbb with #1 for t..
First, based on the choice of the step sizes, we show that 0z+1 E B (Oo) with pi = 0. To see this, note that, using similar inequalities as in our analysis for the case l 1,
10++1 00l12
110+11
0-112 = Σ nll vol(0))) S 2on Σ ((0+)
T=
-=0
T=0
(0)
Σ
t
(1 -1-m/by 1d-))
Vē(0o) s 2em
VE(B0)
3 2gm
v1 -1770
(0) 40v {(Ob)
VT (c)
Co,
7o S P.
A
where (a) follows from our induction hypothesis, (b) follows from I-V1-sXo <
2 for x <
- and
(c) follows since p O TT Xo ).
Now, we have
Xmin ( ([NTK(()) (0.)) (a) Amin (Kx(K)(((0--1))) 4cn T
-1 ((0x-1)
vm"
T
Amin (KNTK)
2 4cHe21
V (((0,)
Vm
7=0
(6)
2 Au
T 4020"n
Σ (1- 722 (((b)
Vm
==
T' ((0o)
2 Ao 8020
Vm
1 /I 11
73/2
A0
Vm. 1
VI 11i0
3/T
Ao
Aaym
where (a) follows from Lemma 1, (b) follows by the induction hypothesis, and (c) follows with T = 8, C3. Then, with m > 1622 T
X we have
Amiu (K (KNIK (Bi) Au/2.
(61)
39

---

Published as a conference paper at ICLR 2024
Since 9r, 0111 ppp) with P1 O, take the smoothness property and further obtain, using similar inequalities as in our analysis for the case t = 1,
3T
((0++1)- ((0s) (0++1 O2. vol(O.))
11 0el12
(0)
vo6(0.)1 +
3T12T
[oc(or) ||²
-
-1
2
_nI""
)
||
2
(62)
l KNTK (Da)
2
S Aminn (KnTK 112.112
2
( 1) Aa 4l(0.)
2
1(0+1)) (1 n/ (():),
where (a) follows from the gradient descent update and (b) from our recently derived result. That establishes the induction step and completes the proof.
40

---

Published as a conference paper at ICLR 2024
F RELATED WORK
Contextual Bandits: The contextual bandit setting with linear losses has received extensive attention (see for eg. Abe al., 2003: Chu et al., 2011: Abbasi-Yaddoon et al., 2011; Agrawal and Goyal, 2013; Ban and He, 2020; 2021). Owing to its remarkable success, Lu and Van Roy (2017); Zahavy and Mannor (2020); Riquelme et al. (2018) adapted neural models to the contextual bandit setting. In these initial works all but the last layers of DNN were utilized as a feature map to transform contexts from the raw input space to low-dimensional space and a linear exploration policy was then learned on top of the last hidden layer of the DNN. Although these attempts have yielded promising empirical results, no regret guarantees were provided. Subsequently (Zhou et al., 2020) introduced the first neural bandit algorithm with provable regret guarantees that uses UCB based exploration and Zhang et al. (2021) further extended it to the Thompson sampling approach. Both these approaches rely on Kernel bandits (Valko et al., 2013) and have a linear dependence on effective dimension of the (NTK) Neural Tangent Kernel (see Allen-Zhu et al., 2019b; Jacot et al.. 2018: Cao and Gu, 2019b). Moreover both these algorithms require the inversion of a matrix of size equal to the number of parameters in the model each step of the algorithm. Recently, Ban et al. (2022b) attained regret bound independent of d. but makes distributional assumptions on the context. (Qi et al., 2022; 2023; Ban et al., 2021; 2022a) shows the successful application of neural bandits on the recommender systems.
Overparameterrized Models: Considerable progress has been made in understanding the expressive power of Deep Neural Networks in the overparameterized regime (Du al., 2019; Allen-Zhu et al., 2019b;a; Cao and Gu, 2019b; Arora et al., 2019a). It has been shown that the dynamics of the Neural Tangent Kernel always stays close to random initialization when the network is wide enough (Jacot et al., 2018; Arora et al., 2019b). Further Cao and Gu (2019b) demonstrate that the loss function of neural network has the almost convexity in the overparameterized regime while Liu et al. (2020; 2022); Frei and Gu (2021); Charles and Papailiopoulos (2018) study neural models under Lojask--ojasiewicz (PL) Type conditions (Polyak, 1963; Lojasiewicz, 1963; Karimi et al., 2016). Recently, Banerjee et al. (2023) provided bound on the spectral norm of the Hessian of the netowrk over a larger layerwise spectral norm radius ball (in comparison to Liu et al. (2020)) and show geometric convergence in deep learning optimization using restricted strong convexity. Our regret analysis makes use of these recent advances in deep learning.
G DETAILS OF EXPERIMENTS
Baselines. We choose four neural bandit algorithms: (1) NeuralUCB (Zhou et al., 2020) maintains a confidence bound at every step using the gradients of the network and selects the most optimistic arm. (2) NeuralT'S (Neural Thompson Sampling) (Zhang et al., 2021) estimates the rewards by drawing them from a normal distribution whose mean is the output of the neural network and the variance is a quadratic form of the gradients of the network. The arm with the maximum sampled reward from this distribution is selected. (3) EE-Net (Ban et al., 2022b): In addition to employing an Exploitation network for learning the output function, it uses another Exploration network to learn the potential gain of exploring in relation to the current estimated reward. (4) NeuralEppsilon employs the e-greedy strategy: with probability - it chooses the arm with the maximum estimated reward generated by the network and with probability e it chooses a random arm.
Datasets. We consider a collection of multiclass classification based datasets from the openml.org platform: covertype, fashion, Magic Magiccelescope, mushroom, Plants and shuttle. Following the evalua- tion setting of existing works (Zhou et al., 2020; Ban al., 2022b), given an input X; IRd for K-class classification problem, we transform it into dK dimensional context vectors for each arm: x,.1 = (x, 0, O. 0)", x = (O, x,, O, ...... ))")...., Xt,K (0.0..... x, The reward is
defined as 1 if the index of selected arm equals x's ground-truth class; otherwise, the reward is O.
Architecture: Both NeuSquareCB and Ne use a 2-layered ReLu network with 100 hid- den neurons. The last layer in NeuRIG uses a linear activation while NeuFastCB uses a sigmoid. Following the scheme in Zhou et al. (2020) and Zhang et al. (2021) we use a diagonal matrix ap- proximation in both NeuralUCB and NeuralTS to save computation cost in matrix inversion. Both use 2-layered ReLu network with 100 hidden neurons and the last layer uses a linear activation. We perform a grid-search over the regularization parameter À over (1, 1, 0.01) and the exploration parameter v over (0.1, 0.01, 0.001). NeuralEpsilon uses the same neural architecture and the ex- ploration parameter e is searched over (0.1, 0.05, 0.01). For EE-Net we use the architecture from
41

---

Published as a conference paper at ICLR 2024
https://githi: do a grid-search for the step-size over (0.01, 0.005, 0.001).
For all the algorithms also
coverlype
fashion
EE-Net
EE-Net
4000
NeuralUiCB
4000
NeuralUCB
NeuralTS
NeuralTS
Neural-E
Regret
2000
NeuSquareCB
Rogret
NeuSquareCB
NeuFastCB
NeuFasiCB
1000
1000
2000
3000
4000
5000
0
1000
2000
3000
4000
5000
Rounds
Rounds
MagicTelesoope
mushroom
EE-Net
EE-Net
NeuralUCB
4000
NeuralUCB
NeuraITS
NeuralTS
Regret
2000
NeuSquareCB
Neural-e
Regret
2000
NeuSquareCB
Neural-e
NeuFastCB
NeuFasiCB
500
10
-500
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Rounds
Rounds
Plants
shuttle
EE-Not
EE-Net
NeuralUCB
4000
NeuralUCB
NeuralTS
NeuralTS
Neural-g
Neural-g
Regret
2000
NeuSquareCB
Regret
2000
NeuSquareCB
NeuFasiCB
NeuFastCB
0
2000
100
0
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Figure 2: Figure re-plotted for better visualization. Comparison of cumulative regret of NeuSquareCB and NeuFastCB with baselines real- world datasets (averaged over 20 runs). The subplot below each figure plots the regret curve for NeuSquareCB and NeuFastCB again.
42

---

Published as a conference paper at ICLR 2024
G.1 NeuSquareCB AND NeuFastCB
Although our regret bounds are for the regularized network as defined in (10), the results presented in Section 5 are for the un-perturbed network. In this section we compare the un-perturbed network with the regularized one for different choices of perturbation constant Greg / 1/4
covertype
fashion
500
400
NeuSquareCB (o-0)
NeuSquareCB (o-0)
NeuSquareCB (om0.1)
NeuSquareCB (em0.1)
NeuSquereCB (s=0.01)
NauSquareCB (c=0.01)
NeuSquareBB (px0.001)
NeuSquereCB (cx0.001)
Regret
Regret
100
100
0
600
800
Rounds
Rounds
MagicTelescope
mushrcom
C (c=D)
200
NouSquansCB (c=0.1)
Neu.qqarreBB (c=0.01)
NeuSquareCB (c00.001)
Regret
Regret
NeuSquareCB (o=0)
2
NeuSquareCB (cm0.1)
NeuSquareCB (e=0.01)
NeuSqueraCB (es0.001)
200
400
800
200
400
600
800
Rounds
Rounds
Plants
shutlle
200
NuuSquancCB (c=0)
6:00
NauSquancCB (c=0)
NeuSquanCCB (c-0.1)
NeuSquanCB (c-0.1)
NeuSquareCB (c-0.01)
NeuSquareCB (c-0.01)
NouSquareCB (c:0.001)
NouSquareCB (c=0.001)
Rogret
100
Regret
200
200
400
600
900
0
200
400
600
900
Rounds
Rounds
Figure 3: Comparison of cumulative regret of NeuSquareCB for different choices of the regularization 1/4 parameter e Creg/ 1/4 for the model defined in (10) (averaged over 10 runs).
As is evident from Figure 3 and 4, the cumulative regrets attained by the un-perturbed networks (c = 0) are more or less similar to the perturbed one on these data-sets. However, the output perturbation ensured a provable KT) and O(vKL* + K) regret bound for NeuSquareCB and NeuFastCB respectively. For the set of problems our experiments perturbed versions of NeuSquareCB and NeuFastCB behave similar to the perturbed versions, but do come with provable regret bound. In particular, one may be able construct problem where the non-perturbed version performs poorly.
observe that the non-
43

---

Published as a conference paper at ICLR 2024
covertype
fashion
300
300
250
250
200
200
Regret
Regret
150
150
NeuFastCB (cmb)
NeuFasiCB (c-0)
100
NauFastCB (c=0.1)
NouFastCe (c=0.1)
50
NauFastCB (c=0.011)
NauFasiB (c=0.01)
NeuFastCB (c-0.001)
NeuFastCB (c=0.001)
Rounds
Rounds
MagicTelescope
mushroom
NeuFaetCB (c-0)
60
NeuFasttCB (cm0.1)
NouFastCB (c=0.01)
NauFastCB (c=0.001)
Regret
Regret
20
NouFastCB (s=0)
NeuFasICB (ox0.1)
NeuFasICB (o~0.01)
NeuFasiCB (em0.001)
200
400
Rounds
Rounds
Plants
shuttle
250
200
Regrot
Rogret
150
NeuFasICB (ow0)
NeuFasiCB (cx0)
NeuFasiCB (cm0.1)
NeufasiCB (or0 f)
(em0.01)
(om0
NeuFastCB (c=0.001)
NeuFasiCB (c=0 (c=0.001)
200
400
800
800
200
400
600
800
Rounds
Rounds
Figure 4: Comparison of cumulative regret of NeuFastCB for different choices of the regularization parameter e Creg m 1/4 for the model defined in (10) (averaged over 10 runs).
44


Reviews:
[{"review_id": "oLN9U1ntRq", "reviewer": "Reviewer_PXpv", "summary": "This paper studies the contextual bandit problem with the use of a neural network for online regression. The authors build upon recent progress in our understanding of neural networks, providing an online regression algorithm that for the KL and squared loss acheives O(log T) regret a significant improvement over previous O(sqrt(T)) results. Using this, they employ the reduction of contextual bandits to online regression presented in the SquareCB algorithm of Foster/Rakhlin.", "questions": "See above", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- I found the paper to be easy to read, well-presented and interesting.\n- The results are interesting and seem like a potentially important contribution. \n- It was harder for me to gauge the novelty of the approach used to prove the given results.", "weaknesses": "- The main result of this paper is given in section 3, where the authors show that a noise perturbed version of the neural network can be used to obtain a O(log T) regret bound. From what I understood, compared to the past results of Chen which just used Assumption 2a, this result exploited 2b and 2c to gain an improvement. This is akin to the fast rates that one gets for gradient descent run on strongly convex functions vs convex functions. Though the result is natural and intuitive based on Chen, I failed to understand what technical contributions the authors made to achieve the result in Theorem 3.1. Is this a straightforward application of existing results, or did it require a new perspective? Is the noise perturbation the main novelty?  Further discussion would have helped couch this work in the existing literature.\n\n- I was a bit confused about why Section 4 was presented in the context of KL-loss. Presumably it applies to squared loss as well given the results of the previous sections?\n\n- I have some concerns about the experiments. Building on the previous comment, it seems that part of the novelty of this paper is the use of a perturbed neural network. In the experiments you compare your algorithm using KL loss to NeuSquareCB and show an improvement. However, it feels like the natural comparison would be NeuFastCB against a variant using the KL loss where you don’t perturb. Similarly for the square loss. This “ablation”-esque study would highlight the important of the algorithmic contributions you have proposed.\n\nMinor Typos\n\n- theta_t in equation 4 should be theta", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rUxOewJtLS", "reviewer": "Reviewer_eHnV", "summary": "The paper provides $O(\\log T )+\\epsilon T$ regret for online regression when the loss function satisfies $\\epsilon$-almost convexity, QG condition, and has unique minima. The authors show that even though QG with unique minima may not be realistic, adding a suitably small random perturbation to the predictions, makes the losses satisfy QG with unique minima. Using a reduction from contextual bandits to online regression oracles, the authors use the results to show regret bounds for contextual bandits.", "questions": "Please see weaknesses.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper shows nearly-constant regret for online regression under certain assumptions.\n- Some of the assumptions are valid for wide range of networks or can be enforced by perturbing the loss function.\n- The regret bounds for contextual bandits are tight in some cases.", "weaknesses": "- The results require strong assumptions (2.a, 3, 5).\n- The failure probability is large (grows with T) and cannot be controlled (see for example Thm 3.2).\n- The regret bounds for contextual bandits grow with the number of arms rather than a complexity measure of the underlying class of functions. A typical scenario for CBs is when the number of arms is very large or even infinite. This does not recover even the simple result of contextual linear bandits where the regret grows as $\\tilde{O}(\\sqrt{dT\\log K})$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "S7DRvLMigp", "reviewer": "Reviewer_EQUF", "summary": "This paper studies the contextual bandits problem. The paper proposed NeuCB, an algorithm based on applying SquareCB to neural networks with some assumptions. The paper proved a novel online regression guarantee for neural networks satisfying QG condition and some other assumptions. Based on this, the paper converted this into a $\\sqrt T$-type bandit regret bound for NeuCB. Furthermore, the paper presented experiments on various real-world classification datasets to show its advantage over existing neural contextual bandits algorithms.", "questions": "1. In regret bounds Theorems 4.1 and 4.2, what's the dependency of the regret bound w.r.t. width $m$? If there's dependency, could you please write it out? If neither the Theorem nor the algorithm used $m$, then we could omit it.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The online regression bound is novel and could further benefit the community.\n2. The paper presents experiments to corroborate their theoretical findings.", "weaknesses": "1. The paper seems not to mention about whether the reward function $h$ in Assumption 1 is realizable by a neural network. Is it the case?\n2. Similar to most previous NTK bandit paper, the paper made the assumption on both gaussian initialization and lower-bounded eigenvalue of the NTK. This limits the scope of this and all the NTK bandits papers.\n3. The paper is written in a nested way so that I have to chase after the links between theorems, lemmas, and assumptions to figure out the true assumption set of a theorem: for each theorem, I need to consider its assumption and the assumptions in all lemmas/theorems it used.\n4. The bounds in various theorems used $\\widetilde{\\mathcal O}$ without saying what's exactly being omitted by it. I suggest the author complete this part of information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qNz5viUGH1", "reviewer": "Reviewer_uhN1", "summary": "This work provides a solid investigation on neural regression in contextual bandits. One interesting point is to use perturbation to construct a surrogate network output with unique minimizer. In that analysis, the work manage to get a approximate loss to satisfy strong-convexity-like condition (Quadratic Growth condition) to get analysis through. The article is full of useful theoretical insights and enjoyable to read.", "questions": "1. One particular point that draws my attention is to adopt KL loss in the online gradient descent step. Could you make comments on when should we use NeuFastCB and when should we use NeuSquareCB in practice? In particular, how the dimension or datatype of the real dataset impact this decision? \n\n2. Could you provide your comments on why NeuFastCB and NeuSquareCB outperform NeuralTS?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work provides solid investigation on improving online neural regression for better online decision making. The paper also is well-written, easy to read for audience with relative expertise.", "weaknesses": "Maybe not so readable for people without theoretical background.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wsOSP9zXl2", "reviewer": "Reviewer_Gbgm", "summary": "This paper studies neural contextual bandits (CB) with the reduction to online regression under the realizability assumption. \nUsing existing results for wide neural networks, it immediately gets a regret of $O(T^{3/4})$ for neuCB. \n\nWhen the loss function of the online regression satisfies $\\epsilon$-almost convexity, Quadratic Growth condition and uniqueness of minima, this paper provides a $O(\\log T) + \\epsilon T$ regret for the online regression.\n\nThen, since the above result does not directly apply to wide NN due to the violation of uniqueness of minima, this paper proposes a novel trick of adding a small perturbation to the NN prediction. This seemingly simple trick makes the loss satisfy the Quadratic Growth condition with a unique minimum. Consequently, an $O(\\log T)$ regret for the online regression with KL loss and squared loss is established. \n\nFurthermore, this paper provides a lower bound of $\\Omega(T)$ for NeuralUCB and NeuralTS with an oblivious adversary.\n\nFinally, Experimental results show that the proposed algorithms outperform baselines on 6 classification datasets.", "questions": "1. Is it possible to extend the current results to a broader choice of loss functions? It would be great if the authors can elaborate on this.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "**Significance**: this paper is a quite extensive theoretical work on NeuralCB. The theoretical results as well as the techniques are of independent interest. \n\n**Quality**: the quality of the paper is good. Definitions are introduced without ambiguity; the theoretical analysis seems solid to me; experimental details are given. \n\n**Originality**: this paper contains some novel idea. The perturbation trick is a very interesting trick for bypassing the restriction on the uniqueness of minima. \n\n**Clarity**: this paper is very well written. The theoretical proof is divided into steps. A sketch of proof like this make it easier for the readers to follow and understand.", "weaknesses": "I did not detect any major technical flaw or major weakness in this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)