Neural Active Learning Beyond Bandits
Authors: Yikun Ban
Ishika Agarwal
Ziwei Wu
Yada Zhu
Kommy Weldemariam
Hanghang Tong
Jingrui He
Venue: ICLR 2024 poster (2024)
Keywords: Active Learning
Neural Active Learning
Contextual Bandits
Neural Contextual Bandits
Primary area: general machine learning (i.e., none of the above)

Abstract: We study both stream-based and pool-based active learning with neural network approximations. A recent line of works proposed bandit-based approaches that transformed active learning into a bandit problem, achieving both theoretical and empirical success. However, the performance and computational costs of these methods may be susceptible to the number of classes, denoted as $K$, due to this transformation. Therefore, this paper seeks to answer the question: "How can we mitigate the adverse impacts of $K$   while retaining the advantages of principled exploration and provable performance guarantees in active learning?" To tackle this challenge, we propose two algorithms based on the newly designed exploitation and exploration neural networks for stream-based and pool-based active learning. Subsequently, we provide theoretical performance guarantees for both algorithms in a non-parametric setting, demonstrating a slower error-growth rate concerning $K$ for the proposed approaches. We use extensive experiments to evaluate the proposed algorithms, which consistently outperform state-of-the-art baselines.

Published as a conference paper at ICLR 2024
NEURAL ACTIVE LEARNING BEYOND BANDITS
Yikun Ban', Ishika Agarwal', Ziwei Wu', Yada Zhu?, Kommy Weldemariam',
Hanghang Tong', Jingrui He'
University of Illinois Urbana-Chani Stbana-Champaign. IBB Research [yikunb2, ishikaa2, ziweiwu2, htong, jingrui) @illinois.edu (yzhu, kommy) uum.ibm.com
ABSTRACT
We study both stream- based and pool-based active learning with neural network approximations. A recent line of works proposed bandit-based approaches that transformed active learning into a bandit problem, achieving both theoretical and empirical success. However, the performance and computational costs of these methods may be susceptible to the number of classes, denoted as K, due to this transformation. Therefore, this paper seeks to answer the question: "How can we mitigate the adverse impacts of K while retaining the advantages of principled exploration and provable performance guarantees in active learning?" To tackle this challenge, we propose two algorithms based the newly designed exploitation and exploration neural networks for stream-based and pool-based active learning. Subsequently, we provide theoretical performance guarantees for both algorithms in a non-parametric setting, demonstrating a slower error-growth rate concerning K for the proposed approaches. We use extensive experiments evaluate the proposed algorithms, which consistently outperform state-of-the-ad baselines.
INTRODUCTION
Active learning is one of the primary areas in machine learning investigate the learning technique on small subset of labeled data while acquiring good generalization performance compared to passive learning [9]. There are mainly two settings of active learning: stream- based and pool-based settings. For the stream- based setting, the learner is presented with an instance drawn from some distribution in each round and required to decide on-the-fly fly whether or not to query the label from the oracle. For the pool-based setting, the learner aims to select one or multiple instances from the unlabeled pool and hand them over to the oracle for labeling. It repeats this process until the label budget is exhausted (51). The essence of active learning is to exploit the knowledge extracted from labeled instances and explore the unlabeled data to maximize information acquisition for long-term benefits.
Using neural networks (NNs) to perform active learning has been explored extensively in recent works [48 12 56 6]. However, they often lack a provable performance guarantee despite strong empirical performance. To address this issue, a recent line of works [58] 14] proposed the bandit- based approaches solve the active learning problem, which equipped with principled exploration and theoretical performance guarantee. In contextual bandits [38 68]. the learner is presented with K arms (context vectors) and required to select one arm in each round. Then, the associated reward is observed. [58] [4] transformed the online K-class classification into a bandit problem. Specifically. in one round of stream- based active learning, data instance x, E RRd is transformed into K long vectors corresponding to K arms, matching K classes: Xt, |x 0
...., Xt. [0 o [ where Xt, E BR A [K]. Then, the learner uses an NN model to calculate score for each arm and selects an arm based on these scores. The index of the selected arm represents the index of the predicted class. This design enables researchers utilize the exploration strategy and analysis in contextual bandits to solve the active learning problem. Note [58] [4] can only handle the stream-based setting of active learning.
However, bandit-based approaches bear the following two limitations. First, as the instance x, is transformed into K arms, it is required calculate a score for all K arms respectively, producing a cost of K times forward- -rovaad-ropaattion computation of neural networks. This computation cost is scaled by K. Second, the transformed long vector (arm) has (Kd) dimensions, in contrast to the

---

Published as a conference paper at ICLR 2024
Table 1: Test accuracy and running time compared to bandit-based methods in stream-based setting.
Adult
MT
Letter
Covertype
Shutle
Fashion 10
# Number of classes
2
2
2
Accuracy
NeurAL-NTK [58]
80.3 0.112
76.9 1 0.15
79.3 1 0.21
61.9 1 0.08
95.3 0.20
64.5 1: 0.16
I-NeurAL [14]
84.2 0.22
79.4 - 0.16
82.9 + 0.06
65.2 i 0.19
99.3 10.12
73.5 + 0.28
NEURONAL-S
0.51 84.8
83.7 0.17
86.5 1 0.16
74.4 0.19
99.5 0.09
83.2 10.38
Running Time
NeurAL-NTK (8
163.2
1.31
259.4 + 2.48
134.0 + 3.44
461.2 + 1.26
384.7 = 1.86
1819.4 10.84
I-NeurAT. [14
102.4
7.53
46.2 + 5.58
232.2 + 3.80
1051.7 5.85
503.1 + 9.66
1712.7 + 12.8
NEURONAL-S
54.7=3221
10.5 = 0.39
9.41
166,4 = 0.59
101.222.33
116.3 3.39
d dimensions of the original instance as the input of the NN model. This potentially amplifies the effects of K on an active learning algorithm's 's performance. We empirically evaluate [58] [4] as The results indicate noticeable degradation in both test accuracy and running
shown in Table [ time as K increases.
In response, in this paper, we aim mitigate the adverse effects of K on the bandit-based approach in active learning. Our methods are built upon and beyond [14). [14 adopted the idea of [3] to employ two neural networks, one for exploitation and another for exploration. As previously mentioned, these two neural networks take the transformed K Kd-dimension arm as input. Moreover, in each round, [ decomposed the label vector Yz {0, 1] K into K rewards (scalars), necessitating the training of two neural networks K times for each arm. Next, we summarize our key ideas and contributions to reduce the input dimension back to d and the number of forward propagations to in each round while preserving the essence of exploitation and exploration of neural networks.
Methodology. (1) We extend the loss function in active learning from 0-1 loss to Bounded loss, which is more flexible and general. Instead, [58 14 restricted the loss to be 0-1 loss, because they had to define the reward of each class (arm) due to their bandit-based methodology. (2) We re-designed the input and output exploitation and exploration neural networks to directly take the d-dimension instance as input and output the predicted probabilities for K classes synchronously, mitigating the curse of K. The connection between exploitation and exploration neural networks is also reconstructed beyond the standard bandit setting. In other words, we avoid the transformation of active learning the standard bandit setting. This is the first main contribution of this paper. (3) To facilitate efficient and effective exploration, we introduce the end-to-end embedding (Definition[4.) as the input of the exploration neural network, which removes the dependence of the input dimension while preserving the essential information. (4) In addition to our proposed stream- algorithm, referred to NEURONAL-S, we also propose pool-based active learning algorithm, NEURONAL-P. We bring the redesigned exploitation and exploration network into pool-based setting and propose a novel gap-inverse- -essee--bseed selection strategy tailored for pool-based active learning. This is our second main contribution. Note that the stream-base based algorithms cannot be directly converted into the pool-based setting, as discussed in Appendix
Theoretical analysis. We provide the regret upper bounds for the proposed stream-based algorithm under low-noise conditions on the data distribution. Our results indicate the cumulative regret of NEURONAL-S grows slower than that of (58) concerning K by a multiplicative factor at least O(VTlog(1 Ao)) and up O(Vnd), where An is the smallest eigenvalue of Neural Tangent Kernel (NTK) and m is the width of the neural network. This finding helps explain why our algorithms outperform the bandit-based algorithms, particularly when K is large, as shown in Table I In the binary classification task, our regret bounds directly remove the dependence of effective dimension d, which measures the actual underlying dimension in the RKHS space spanned by NTK, discussed in Sec. [ We also provide a performance analysis for the proposed pool- algorithm in the parameeriiic setting, tailored for neural network models. In contrast, previous works focus on the regime either parametric settings that require a finite VC dimension BD or a linear mapping function assumption [8 64 28 The above theoretical results are our third main contribution. In
addition,
Empirical evaluation. In the end, we perform extensive experiments to evaluate the proposed algorithms for both stream- based and pool- algorithms compared to state-of-the-an baselines. Our evaluation encompasses various metrics, including test accuracy and running time, and we have carried out ablation studies to investigate the impact of our fourth main contribution.
and label budgets. This is
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Active learning has been studied for decades and adapted to many real-works applications 553 There are several strategies in active learning smartly query labels, such diversity sampling 67], and uncertainty sampling [69; 62. 41). Neural networks have been widely used in various
scenarios 40,
26 27 55; 60]. The Contextual bandit is a powerful tool for decision-making 49 50] and has been used for active learning. Works that use neural networks to perform active learning, according to the model structure, can be classified into online-learning- -ased
39
13 10:
45 6 and bandit-based [58] [4] methods. For most of the methods, their neural models take the instance input and calculate the predicted scores for each class synchronously. For example, 56 66 5 exploit the neural networks for active learning to improve the empirical performance. As mentioned before, this type of related work often lacks the principled exploration and provable guarantee in a non-parametric setting.
6 35
54
The primary focus of theoretical research in active learning is to determine the convergence rate of the population loss (regret) of the hypothesis produced by the algorithm in relation to the number of queried labels N. In the parametric setting, the convergence rates of the regret are of the form vNV122 + e V/N where is the population loss of the best function in the class with finite VC- 65). With the realizable assumption (i.e., when the Bayes dimension, e.g.. [29 20 47 63
optimal classifier lies in the function class), minimax active learning rates of the form N "+1 shown in [30 36] to hold for adaptive algorithms that do not know beforehand the noise exponent a (Defined in Sec. 5). In non-parametric settings, [44 42 70 worked under smoothness (Holder continuity/smootnnnsss) assumptions, implying more restrictive assumptions on the marginal data distribution.
are
B(+++)
42 70) achieved the minimax active learning rate N 2345 for 3-Holder classes, where exponent plays the role of the complexity of the class of functions to learn. [8 644 (28)
focused on the pool-based setting and achieve the ( )x++1/+++2 minimax rate, but their analysis are built on the linear mapping function. (37] investigated active learning with nearest-neighbet classifiers and provided data-dependent minimax rate based on the noisy-margin properties of the random sample. (32] introduce the expected variance with Gaussian processes criterion for neural
active learning. [58) and [4] represent the closest works related to the analysis of neural networks
in active learning. Both (58) and our work utilized the theory of NTK, making their results directly comparable. [14] established a connection between their regret upper bound and the training error of neural network function class. However, they did not provide a clear trade-off between the training error and the function class radius, making it challenging to compare [4] with our theoretical results.
PROBLEM DEFINITION
In this paper, we consider the K-class classification problem for both stream-based and pool- pool-based active learning.
Let X' denote the input space over RR and y represent the label space over {0, 10. D is some unknown distribution over X' x y. For any round E [T] (1,2,...,, T), an instance x, is drawn from the marginal distribution Dx. Accordingly, the associated label yt is drawn from the conditional distribution Dy x,, in which the dimension with value indicates the ground-truth class of x,. For the clarity of presentation, we use Ye,k A E [K] to represent the K possible predictions, ie., yr,1 = [1, ........... O]T "..,...., ,t, = [0, [0. 1]]
Dr, the learner is required to make a prediction yr To E [K] based on some function. Then, the label y, is observed. A loss function é x y - [0, 1]. represented by (y,,,, Yr), reflects the quality of this prediction. We investigate the aan-arammtric setting of active learning. Specifically, we make the following assumption for the conditional distribution of the loss. Assumption 3.1. The conditional distribution of the loss given x, is defined by some unknown function h: X [0, 1] K such that
Given an instance
Vk E [K], Ey.-Driss [C(yt,A, = h(x:)[[)) where (xx [k] represents the value of Dax
(3.1)
kit dimension of h(x:).
Assumption 3.1 is the standard formulation in [4]. Related works [4: restricted E to be 0-1 loss. In contrast, only assume E is bounded for the sake of generality.
3

---

Published as a conference paper at ICLR 2024
Stream-based. For stream-basee based active learning, at each round t E [T], the learner receives instance X, ~ Dx. Then, the learner is compelled to make a prediction y and at the same time, decides on-the-fly whether or not to observe the label yt-
Then, the goal of active learning is to minimize the Population Cumulative Regret. Given the data distribution D and the number of rounds T, the Population Cumulative Regret is defined as:
Retrram (T)
E (I)
E (x...++)>D
[e vil]]
(3.2)
where Ye, is the prediction induced by the Bayes-optimal classifier with respect to x, in round t, i.e, h = arg minke[k] [k). The Population Regret reflects the generalization performance of a model in T rounds of stream-based active learning.
At the same time, the goal of the learner is to minimize the expected label query cost: N(T) = E [L [,], where I, is indicator of the query decision in round t such that 1, 1 if y: is observed: I 0, otherwise.
T
Pool-based. The goal pool-based active learning is to maximize the performance of a model with limited label budget given the pool of instances. In round, assume there an instance pool P. = {x1, x...... XB} with B instances, which are drawn from Dx. Then, for any x, E Pr. the learner is able to request label from the conditional distribution Y: ~ Dyix, with one unit of budget cost. The total number of queries is set as Q. Let y, be the prediction of E P, by some hypothesis. Then, the Population Cumulative Regret for pool-based active learning is defined as:
R Rooo (Q) = Σ 1=1 (XLY))D
[1 (y (x..i)~D
E [ M(y)
(3.3)
where 1s* = arg minke[K] [ b(xx)(k) Rooo (Q) (Q)
reflects the generalization performance of model in
Q rounds of pool-based active learning.
PROPOSED ALGORIHTM
In this section, we present the proposed algorithms for both stream-based based and pool-based active learning. The proposed NN models incorporate two neural networks for exploitation and exploration. The exploitation network directly takes the instance as input and outputs the predicted probabilities for K classes synchronously. instead of taking the transformed K long vectors as input and computing the probabilities sequentially. The exploration network has a novel embedding as input to incorporate the information of K classes in the exploitation network simultaneously instead of calculating K embeddings for K arms sequentially as in bandit- approaches.
Exploitation Network f.. The exploitation network fi is neural network which learns the mapping from input space X' to the loss space [0, 1]k In round E [T], we denote the network by (: 0!),, where the superscript of 0, indicates the network and the subscript indicates the index of the round after updates for inference. is defined fully-connected neural network with L-depth and
m--idthh
(W] f (x 0') == Lm //..................)))
R
(4.1)
where W E R.mxd W E mm for 2 < S I. 1, W E Kx
0²
(ve((W]) ..... veo(WL) E R", and the ReLU activation function (xx max x). We randomly initialize 0² denoted by 01. where each entry is drawn from normal distribution N (0.2/m) for Wi, [L 1]. and each entry is drawn from (0, 1/(Km)) for W..
Note that we take the basic fully-connected network as an example for the sake of analysis in over- parameterized networks, and f can be easily replaced with other advanced models depending on the tasks. Given an instance x,, f, (x,; 0 can be considered as the estimation for E(y Yt), k E [K].
In round f, after receiving the label yr. conduct stochastic gradient descent to update 0² based on the loss function Le,1 (0.), such as Lr (0.) = ElEJK] (fi (x;; ())()) - ((y., /2, where (x:; 0)) [k]] represents the value of the t dimension of fz (x);
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 NEURONAL-S
Input: T,K, f1, f2. n, 72 (learning rate), (exploration para.), 5 (confidence para.), S (norm para.)
2 1: Initialize 0. 02 02 0 0 - 0g S2 = (0 0,1
2: for -= 1, ...,, do
3: Receive an instance X2 ~ Dx
4: f(x;: 0,) f (xx: 0,) + f/ (o(((x)): 02)
5: h = arg [ f(x;; [kk
6:
arg min pe (f R f(x;; [k)
7: Predict NtR
I = 1x] Oe 1b: fxx;; (xx;0))({{)) < 2y E {0,1]; B, KS² + (3T
8:
9:
Observe yt and e, if I, l: N1, otherwise
10:
0 2++ 0, 1n v Lt, (
0 4+1 0; - 1/2 Vo 2
12:
P4+1 = -t U (0 0.+1)
Draw (0/+1: 02 1)+1) uniformly from 24+1
14: end for
return 0r
Exploration Network fz. The exploration network & learns the uncertainty of estimating fi (+; (')) In round & E [T), given an instance X, and the estimation (x; 0!),, ) the input of fe a mapping or embedding (xx,) that incorporates the information of both x, and the discriminative information of 0:- We introduce the following embedding o(x:):
Definition 4.1 (End-to-end Embedding). Given the exploitation network (((:0)) and an input context Xs, its end-to-end embedding is defined as
o(x;) = (o(W)x)) .vec( .vec(V (ve (x;; (x):))))) E Rm
(4.2)
where the first term is the output of the first layer of f, and the second term is the partial derivative of f with respect to the parameters of the last layer. 6(x1) is usually normalized.
The first term of (W)x)) T can be thought of an embedding to transform X; E Rd into another space in I" as the input dimension d can be a very large number. Thus, we leverage the representation power of fr and minimize the dependence on d for fz. The last layer might play the more important role in terms of classification ability [46] and hence we only take the gradient of the last layer which incorporates the discriminative information of 0,, to reduce the computation cost.
Then, specifically, given an embedding ((x:), fg is defined as:
(x(x(x));0) 0²) == W
E RK
(4.3)
where W [m W E mmxm for 2 S -- W R Km 0²
[vee (Wee TJ E Re2, and the ReLU activation function (xx = max (0, x).
Similarly, we randomly initialize 0² denoted by 07. where each entry is drawn from Normal distribu- tion N (0, 2/m) for W?, E [L 1]. and each entry is drawn from NO,, 1/Km) for W
In round after receiving yt, the label for training is the estimated error of (:; 0 [k]. represented by ()(y - (xx; (k])) Therefore, we conduct stochastic gradient descent to update 0², based the loss (0,) such Lr,((0)) Σσe[K] (fx()(x)); [
(e(Y),..y)) - (x; 12))) /2, where fa(o(x;;; [?) represents the value of the 1 dimen- sion of fo (x(x)); 0?).
Stream- based Algorithm. Our proposed stream-based active learning algorithm is described in Algorithm T In round, when receiving data instance, calculate its exploitation-exploratio
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 NEURONAL-P
M,? Input: Q. Q.B.K. K, f1 f2. m, 147
1: Initialize 07.0
2: for = 1, 1,2..... Q do
3: Draw B instances, Pt, from Dx
4: for x; E P.do do
5:
f(x;; 0,) = f (x; 0 + (x) 0 k= = arg min fxx;; 0z)
6:
7:
Ao arg min KE[ }) f(x;; (R:)
8:
wi f(x;; 0x) f(x;; [k*)
9:
end for
w; min Wi
11:
For each i # i,
P: = 1 -.==iii Pi
13:
Draw one instance from P. according to probability distribution P formed by pr
14:
Query x,, Predict Y and observe yt
15:
Update 0², 0² Lines 11-12 in Algorithm
16:
end for
return 0Q
score and then make a prediction (Lines 3-7), where ko is used in the decision-maker (Line 8). When I 1. which indicates that the uncertainty of this instance is high, we query the label of this data instance to attain new information; otherwise, we treat our prediction as the pseudo label (Line 9). Finally, we the SGD to train and update the parameters of NN models (Lines 10-13). Here, draw the parameters from the pool Ω for the sake of analysis to bound the expected approximation error of round. One can the mini-batch SGD avoid this issue in implementation.
Pool-based Algorithm. Our proposed pool-based active learning algorithm is described in Algorithm 2 In each round, we calculate the exploitation and exploration scores, and then calculate the prediction gap w for each data instance (Lines 4-9). Then, we form distribution of data instances (Lines 10-13), P. where Lines 11-12 are inspired by the selection scheme in (2). The intuition behind this is as follows. The prediction gap w; reflects the uncertainty of this data instance. Smaller wi shows the larger uncertainty of x,. Thus, the smaller w;, the higher the drawing probability p; (Line 11). Finally, we draw data instance according to the sampling probability P and conduct SGD to update the neural networks.
5 REGRET ANALYSIS
In this section, we provide the regret analysis for both the proposed stream-based and pool-based active learning algorithms.
studied active learning in binary classification, where the label space ) E [0, 1] can be parametrized by the Mammen-Tsybanee exist absolute constants c > O and a 2 O, such that for all 0 < 6 < 1/2, x E X, k E {0, 1}. ((] 1 <) < c For simplicity,
Existing works such as [38 42 70
low noise condition [3]: There
interested in the extremes: a 0 results in no assumption whatsoever on D while a = oo gives the hard-margin condition on D. These two conditions can be directly extended to the K-class classification task. Next, we will provide the regret analysis and comparison with [58].
Our analysis is associated with the NTK matrix H defined in C.I There are two complexity terms in [58] as well as in Neural Bandits [68] 12). The assumption H. > A is generally held in this literature to guarantee that there exists solution for NTK regression. The first complexity term is S
Vh H where h = [h], [2], (((x)))),,,,,,,, [K]] E RT S to bound the optimal parameters in NTK regression: there exists 0* R2' such that (xx))[k] (Vof(x;; 0" [k], 00 01)
and 0 0, ||l < S. The second complexity term is the effective dimension d, defined d =

---

Published as a conference paper at ICLR 2024
dog which describes the actual underlying dimension in the RKHS space spanned by NTK. (1+T))
58 used the term Lи represent d: Lи log det + H) dllo(1 + TK). We provide the TK log(1 + >o) S LH S ((dd)).
upper bound and lower bound of LH in Appendix C
First, we present the regret and label complexity analysis for Algorithm T in binary classification, which is directly comparable [58].
Theorem 5.1. [Binary Classification] Given T, for any 8 (0,1), Ao
suppose K
||xe|22 = 1, [7]. H AnI, m 2 D(poly(T, L, S) log(1/6)) 7 = 7/2 = O m Then, with
probability at least 5 over the initialization of 0) 0% Algorithm 7 accieves the following regret bound:
R Rstream (T) - ((5e) 2+d
Tatz
N(T) S ((S) 0+2 T'o23 o+2
Compared 158
and T and further improve the regret upper bound by multiplicative factor LH #42 For the label complexity N(T), compared to [58], Theorem 5.1 removes the term δ LH T ata and further improve the regret upper bound
Theorem 5.1 removes the term ①
[La
by a multiplicative factor LH =1z.
Next, we show the regret bound for the stream- stream-based active learning algorithm (Algorithm I in K Kllassiification without any assumption on the distribution D (Tsybakov noise a 0).
Theorem 5.2. "Stream-basedl Given for any d E (0, 1), An > O, suppose ||xeIla =
H Z AoI m 2 ((poly(T, K, L, S) log(1/6)), 71 = -/2 = O mvTK)) Then, with probability at least over the initialization of 0). 07. Algorithm achieves the following regret bound:
Ratroam (T) O(VT) (VKS+ V
where N(T) & O(T).
Theorem 5.2 shows that NEURONAL-S achieves a regret upper bound of (VTK).) Under the same
condition (a 0), (58 obtains the regret upper bound: Rastraam (T) Ô (VTIHS vTIN).
This core term is further bounded by Ö(VT VTK log(1 + Ao) < (VTLHS) < Ö(VTmdKS)) Concerning K, Theorem 5.2 results regret-growth rate (KKÖ(VTS. contrast with VK ((VTmdS) at most [58). Therefore, our regret bound has slower growth rate concern- ing K compared to (58 by multiplicative factor at least O ( Tog(1( + Ao)) and up to Ö ((Vmd) md). In binary classification, we reduce the regret bound by ō Õ(VT i.e., remove the dependency of d. and further improve the regret bound by multiplicative factor at least O( + Ao))-
The regret analysis of 14 introduced two other forms of complexity terms: Ö(VT (VT v)). ).) the data-dependent term interpreted as the minimal training error function class on the data, while is the function class radius.
3 had implied that when v has the order of Opooy((T)), μ
can decrease to (1). But, their regret bounds also depend on Opp). This indicates that their regret analysis is invalid when v has O ). Since 14 did not provide the upper bound and trade-off of J and y or build the connection with NTK, their results are not readily comparable to ours.
For the label complexity, Theorem 5.2 has the trivial ((T) complexity which the same as 15814
This turns into the active learning minimax rate of N(T) which indeed the best rate under 21. Next, we provide the analysis under the following margin assumption.
16
30
36
Assumption 5.1 (14)
Given an instance x, and the label y., has unique optimal class if there
exists > 0 such that
VU E [T], h(x
(5.1)
where k* arg minke(k] [kx and & arg (in h(x.) [A).

---

Published as a conference paper at ICLR 2024
Assumption 5.1 describes that there exists unique Bayes-optimal class for each input instance. Then, we have the following theorem.
Theorem 5.3. [Stream-based]. Given for any å (0, Ao > O, suppose ||x 1l2 - 1, [T], H = doI, m 2 Q(poly(T, K, L) log((/6)), 1n = 722 = O mVTK ) and Assumption 5.1
holds. Then, with probability at least over the initialization of 0 O Algorithm Machieess the following regret bound and label complexity:
Rastram (T) S O(KK52 + log(3T/66)/o), N(T) S SO(KS² + logg337/6)//))
(5.2)
Theorem 5.3 provides the regret upper bound and label complexity of ((K52) for NEURONAL-S
under margin assumption. With a + xo, [58] obtained (LH(H + 5²)) S (mdd +2)
Therefore, with margin assumption, the regret of NEURONAL-S grows slower than (58 by
multiplicative factor up to O ((md) with respect to K. 14 achieved Ō(v² + (1), but the results are not directly comparable to ours, as discussed before.
Theorem 5.4 (Pool-based). For any 1 > 8 > 0, Ao 0, by setting μ Q and 7 /
suppose ||xe|12 = 1 for all instances, H ス AgL. m 2 Mipoly(Q, K, L, R) log((/6)), 1 = 722 = Then, with probability at least - over the initilization of 01, 0% Algorithm accheves:
mLK
(v
R Reoot (Q) S O O(VQKS)+
logg(28 + ( (oogl(oo33))
K
Theorem 5.4
provides a performance guarantee of ((QQKS) for NEURONAL-P in the non- parametric setting with neural network approximator. This result shows that the pool-based algorithm can achieve regret bound of the same complexity as the rrrcambbased algorithm (Theorem (.2) with respect to the number of labels. Meanwhile, Theorem 5.4 indicates the O(VI/Q) minimax rate in the pool-based setting which matches the rate (a = 0) in 8 64 28). However, the results in [8 (4 (28] only work with the linear separator, i.e., they assume h as the linear function with respect to the data instance x. Note that [58 14 only work on stream-basee active learning.
6 EXPERIMENTS
In this section, we evaluate NEURONAL for both stream- based and pool- bose- settings on the follow- ing six public classification datasets: Adult, Covertype (CT), MagicTelescope (MT). Shuttle (24). Fashion [6]], and I Letter [18. For all NN models, we use the same width = 100 and depth T. 2. Due to the space limit, we move additional results (figures) to Appendix A
siream-based Setups. We use two metrics to evaluate the performance of each method: (1) test accuracy and (2) cumulative regret. We set T = 10, 000. After T rounds of active learning, we evaluate all the methods on another 10, 000 unseen data points and report the accuracy. As MT does not have enough data points, we use 5, 000 data points for the evaluation. instance is randomly chosen and the model predicts label. If the predicted label is wrong, the regret is 1; otherwise 0. The algorithm can choose to observe the label, which will reduce the query budget by one. We restrict the query budget avoid the situation of the algorithm querying every data point in the dataset, following [4]. The default label budget is 30% x T. We ran each experiment 10 times and reported the mean and std of results. We use three baselines for comparison in the brsedd setting: (1) NeurAL-NTK (58), (2) I-NeurAL [1]. and (3) ALPS [22]. Due to the space limit, we reported the cumulative regret and more details in Appendix A.I
each iteration, one
-baed Results. To evaluate the effectiveness of NEURONAL-S, first, we report the test accuracy of bandit-based methods in Table which shows the generalization performance of each method. From this table, we can see that the proposed NEURONAL-S consistently trains the best model compared to all the baselines for each dataset, where NEURŌNAL-S achieves non-trivial improvements under the same label budget with the same width and depth of NN models. Compared to bandit-based approaches, NeurAL-NTK and I-NeurAL, NEURON AL-S has new input and output, which enable us to better exploit the full feedback in active learning instead of bandit feedback and to explore more effectively. The results of ALPS are placed in Table 3 ALPS manages to select the best pre-trate are-trained hypotheses for the data. However, the model parameters are fixed before the online active learning process. Hence, ALPS is not able to take the new knowledge obtained by queries into account and its performance is highly limited by the hypothesis class. Table shows the running time
8

---

Published as a conference paper at ICLR 2024
Table 2: Testing accuracy (%) and running time on all methods in Pool-based Setting
Adult
MT
Letter
Covertype
Shuttle
Fashion
Accuracy
CoreSct BADGE
76.7 1.13
15.1 + 0.79
80.6
0.63
62.6 = 3.11
97.7 0.41
80.4 0.08
76.6
7166 0.81
81.7
0.57
64.8 = 1.02
98.6 0.39
DynamicAL
72.4
67.8
63.2 0.31
54.1 0.12
1
54.5 : 0.19
ALBL
1
73.9
81.9 0.47
65.3 - 0.14
98.6 0.37
77.6 0.32
NEURONAL-P
79.1 0.04
0.12 81.3
83.7 0.07
67.6 0.21
99.5 0.01
81.1 0.13
Running
Time
CoreSet
43.1 43.1
4.42 119.3
228.3
6.51
32.5 + 10.94
10.9 + 2.22
33.1
6.32
BADGE
159.5 + 4.61
212.5 9.32
484.8 + 7.04
545.7 + 9.32
1.13
437.8 4: 5.32
DynamicAL
24.3 +: 5.21
821.5
382.3 = 3.13
621.6 1 3.21
483.4
413.2 1: 7.14
ALBL
315.8 + 4.31
343.5
271.3
6.32
481.3 + 5.21
63.2 + 2.16
92.1 3.42
NEURÓNAL-P
17.2
140.1 3.69
133.7 = 12.8
14.1 5.81
15.6 8.03
25.5 1 7.80
of NEURONAL-S compared to bandit-based approaches. NEURONAL-S achieves the best empirical performance and significantly saves the time cost. The speed-up is boosted when K is large. This is because of NEURONAL-S's new NN model structure to calculate the predicted score synchronously. In contrast, bandit-based approaches calculate the score sequentially, of which the computational cost is scaled by K. We also conduct the ablation study for different label budgets the active learning setting placed in Appendix A
Pool-based Setups. We use the test accuracy to evaluate the performance of each method. Following [57]. use batch active learning. In each active learning round, we select and query 100 points for labels. After 10 rounds of active learning, we evaluate all the methods on another 10, 000 unseen data points and report the accuracy. We run each experiment 10 times and report the mean and standard deviation of results. The four SOTA baselines are: (1) CoreSet [52], (2) BADGE [6], (3) DynamicAL
57. and (4) ALBL
33
Pool-based results. To evaluate the effectiveness of NEURONAL-P, we report the test accuracy of all methods in Table[2] Our method, NEURONAL-P, can consistently outperform other baselines across all datasets. This indicates that these baselines without explicit exploration are easier to be trapped in sub-optimal solutions. Our method has a more effective network structure (including the principled exploration network), allowing us to exploit the full feedback and explore new knowledge simultancously in active learning. Moreover, we use the inverse gap strategy to draw samples, which further balances exploitation and exploration. CoreSet always chooses the maximal distance based on the embeddings derived by the last layer of the exploitation neural network, which prone to be affected by outlier samples. BADGE also works using the seed-based clustering method, and it is not adaptive to the state of the exploitation network. DynamicAL relies the training dynamics of the Neural Tangent Kernel, but the rules it uses might only work on the wverpaaaaeeterized neural networks based on the analysis. ALBL is a hybrid active learning algorithm that combines Coreset and Conf (55). ALBL shows a stronger performance but still is outperformed by our algorithm. As mentioned before, these basclines do not provide theoretical performance guarantee. For the running time, as there are B samples in a pool in each round, NEURONAL-P takes () to make selection. For other baselines, CoreSet takes () In addition to (2B) cost, BADGE and DynamicAL need to calculate the gradient for each sample, which is scaled by O(B). Thus, BADGE and DynamicAL are slow. ALBA is slow because it contains another algorithm, and thus, it has two computational costs in addition to neural models. We also conduct the hyper-parameter sensitivity study for different label budgets in the active learning setting placed in Appendix(A.. A.2
the last layer of the exploitation network
7 CONCLUSION
In this paper, we propose two algorithms for both stream-based and pool-based active learning. The proposed algorithms mitigate the adverse effects of K in terms of computational cost and performance. The proposed algorithms build on the newly designed exploitation and exploration neural networks, which enjoy tighter provable performance guarantee in the non- non-parametric setting. Ultimately, we use extensive experiments to demonstrate the improved empirical performance in stream- and pool-based settings.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
This work is supported by National Science Foundation under Award No. IIS-2117902, IIS-2002544 IIS-2134099, Agriculture and Food Research Initiative (AFRI) grant no. 0220067021-3299//rrooo accession no. 1024178 from the USDA National Institute of Food and Agriculture, MIT-IBM Watson AI Lab, and IBM-Illinois Discovery Accelerator Institute new model of an academie-industry partnership designed to increase access to technology education and skill development spur breakthroughs in emerging areas of technology. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.
REFERENCES
[1] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
[2] Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3-11, Citeseer, 1999.
[3] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameetriizaton. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
[4] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. exact computation with an infinitely wide neural net. In Advances Neural Information Processing Systems, pp. 8141-8150, 2019.
[5] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34, 2021.
[6] Jordan Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agar- wal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv:1906.033: 03671, 2019.
[7] Pranjal Awasthi, Maria Florina Balcan, and Philip M Long. The power of localization for efficiently learning linear separators with noise. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pp. 449-458, 2014.
[8] Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pp. 288-316. PMLR, 2013.
[9] Yikun Ban and Jingrui He. Generic outlier detection in multi-armed bandit. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 913-923, 2020.
[10] Yikun Ban and Jingrui He. Local clustering in contextual multi-armed bandits. In Proceedings of the Web Conference 2021, pp. 2335-2346, 2021.
[11] Yikun Ban, Jingrui He, and Curtiss Cook. Multi-facet contextual bandits: A neural network perspective. In The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singupore, August 14-18, 2021, pp. 35-45, 2021.
[12] Yikun Ban, Yunzhe Qi, Tianxin Wei, and Jingrui He. Neural collaborative filtering bandits via meta learning. ArXiv abs/2201. 13395, 2022.
[13] Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. EE-net: Exploitation-exploratiin neural networks in contextual bandits. In International Conference on Learning Representations, 2022. URL wtRlhtttss:.. :/ttttss:///preeeeee ew net.
10

---

Published as a conference paper at ICLR 2024
[14] Yikun Ban, Yuheng Zhang, Hanghang Tong, Arindam Banerjee, and Jingrui He. Improved algorithms for neural active learning. In Alice H. Oh, Alckh Agarwal. Danielle Belgrave, and Kyunghyun Cho Advances in Neural Information Processing Systems, 2022. URL https: //tp::///eeeeviieeeeeeee ew net. formm? IaterriTaCiiict
[15] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32: 10:60666-40846 2019.
[16] Rui M Castro and Robert D Nowak. Minimax bounds for active learning. IEEE Transactions on Information Theory, 54(5):2339-235 2008.
[17] Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiy Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 34, 2021.
[18] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 international joint conference neural networks (IJCNN), pp. 2921-2926. IEEE, 2017.
[19] David A Cohn, Zoubin Ghahramani, and Michael I Jordan. Active learning with statistical models. Journal of artificial intelligence research, 4:129-145, 1996.
[20] Sanjoy Dasgupta, Daniel J Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
[21] Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Selective sampling and active learning from single and multiple teachers. The Journal of Machine Learning Research, 13(1):2655-200 2697, 2012.
[22] Giulia DeSalvo, Claudio Gentile, and Tobias Sommer Thune. Online active learning with surrogate loss functions. Advances in Neural Information Processing Systems, 34, 2021.
[23] Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, and Dacheng Tao. Exploring representativeness and informativeness for active learning. JEEE transactions on cybernetics, 47(1): 26, 2015.
[24] Dheeru Dua, Casey Graff, et al. Uci machine learning repository. 2017.
[25] Dylan Foster and Alexander Rakhlin. Beyond ucb: Optimal and efficient contextual bandits with regression oracles. In International Conference Machine Learning, pp. 3199-3210. PMLR, 2020.
[26] Dongqi Fu, Dawei Zhou, and Jingrui He. Local motif clustering on time-evolving graphs. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pp. 390-400. ACM, 2020.
[27] Dongqi Fu, Dawei Zhou, Ross Maciejewski, Arie Croitoru, Mareus Boyd, and Jingrui He. Fairness-aware clique-preserving spectral clustering of temporal graphs. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023 4 May 2023, pp. ACM, 2023.
(28) Claudio Gentile, Zhilei Wang, and Tong Zhang. Achieving minimax rates in pool-based batch active learning. In International Conference on Machine Learning, pp. 7369-7367. PMLR, 2022.
[29] Steve Hanneke. bound on the label complexity of agnostic active learning. In Proceedings of the 24th international conference Machine learning, pp. 353-360, 2007.
[30] Steve Hanneke. Adaptive rates of convergence active learning. In COLT. Citeseer, 2009.
[31] Steve Hanneke et al. Theory of disagreement- based active learning. Foundations and Trends in Machine Learning, 7(2-3):131-309 2014.
11

---

Published as a conference paper at ICLR 2024
[32] Apivich Hemachandra, Zhongxiang Dai, Jasraj Singh, See-Kiong Ng. and Bryan Kian Hsiang Low. Training-free free neural active learning with mnttaliizaionnrroustmn guarantees. In Interna- tional Conference Machine Learning, pp. 12931- 1-1991. PMLR, 2023.
[33] Wei-Ning Hsu and Hsuan-Tien Lin. Active learning by learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 29, 2015.
[34] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571 85800, 2018.
[35] Yoon- Yeong Kim, Kyungwoo Song, JoonHo Jang, and Il-chul Moon. Lada: Look-ahead data acquisition via augmentation for deep active learning. Advances in Neural Information Processing Systems, 34, 2021.
Yoon-Yeong
[36] Vladimir Koltchinskii. Rademacher complexities and bounding the excess risk in active learning. The Journal of Machine Learning Research, 11:2457-2433 2485, 2010.
[37] Aryeh Kontorovich, Sivan Sabato, and Ruth Umnrr. Active nearest-neighbet learning in metric spaces. Advances in Neural Information Processing Systems, 29, 2016.
[38] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
[39] Lihui Liu, Boxin Du, Jiejun Xu, Yinglong Xia, and Hanghang Tong. Joint knowledge graph completion and question answering. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1098- 1108, 2022.
[40] Lihui Liu, Blaine Hill, Boxin Du Fei Wang, and Hanghang Tong. Conversational question answering with reformulations over knowledge graph. arXiv preprint arXiv:2312.17269 2023.
[41] Zhuoming Liu, Hao Ding, Huaping Zhong, Weijia Li, Jifeng Dai, and Conghui He. Influence selection for active learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9274 9283, 2021.
[42] Andrea Locatelli, Alexandra Carpentier, and Samory Kpotufe. Adaptivity to noise parameters in nonparametric active learning. In Proceedings of the 2017 Conference on Learning Theory, PMLR, 2017.
[43] Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 1766):1008- 1999.
[44] Stanislav Minsker. Plug-in approach to active learning. Journal of Machine Learning Research, 13(1), 2012.
[45] Jooyoung Moon, Jihyo Kim, Younghak Shin, and Sangheum Hwang. Confidence-aware learning for deep neural networks. In international conference on machine learning, pp. 7034-7044. PMLR, 2020.
[46] Eliya Nachmani, Yair Be' Be'ery, and David Burshtein. Learning to decode linear codes using deep learning. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 341-346. IEEE, 2016.
[47] Aldo Pacchiano, My Phan, Yasin Abbasi Yadkori, Anup Rao, Julian Zimmert, Tor Lattimore, and Csaba Szepesvari. Model selection in contextual stochastic handit problems. Advances in Neural Information Processing Systems, 33:10028-10337, 2020.
[48] Remus Pop and Patric Fulop. Deep ensemble bayesian active learning: Addressing the mode collapse issue in monte carlo dropout via ensembles. arXiv preprint arXiv:1811.03897 2018.
[49] Yunzhe Qi. Yikun Ban, and Jingrui He. Graph neural bandits. Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1930, 2023.
12

---

Published as a conference paper at ICLR 2024
[50] Yunzhe Qi, Yikun Ban, Tianxin Wei, Jiaru Zou, Huaxiu Yao, and Jingrui He. Meta-learning with neural bandit scheduler. Advances in Neural Information Processing Systems, 36, 2024.
[51] Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM computing surveys (CSUR), 54 (9):1-40, 2021.
[52] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 00489, 2017.
[53] Burr Settles. Active learning literature survey. 2009.
[54] Wei Tan, Lan Du, and Wray Buntine. Diversity enhanced active learning with strictly proper scoring rules. Advances in Neural Information Processing Systems, 34, 2021.
[55] Dan Wang and Yi Shang. A new active labeling method for deep learning. 2014 International joint conference neural networks (IJCNN) pp. 112-119. IEEE, 2014.
[56] Haonan Wang, Wei Huang, Andrew Margenot, Hanghang Tong, and Jingrui He. Deep active learning by leveraging training dynamics. arXiv preprint arXiv:21 100:211000061,,, 2021.
[57] Haonan Wang, Wei Huang, Ziwei Wu, Hanghang Tong. Andrew J Margenot, and Jingrui He. Deep active learning by leveraging training dynamics. Advances Neural Information Processing Systems, 35:25171-22 -51144, 2022.
[58] Zhilei Wang, Pranjal Awasthi, Christoph Dann, Ayush Sckhari, and Claudio Gentile. Neural active learning with performance guarantees. Advances in Neural Information Processing Systems, 34, 2021.
[59] Tianxin Wei and Jingrui He. Comprehensive fair meta-learned recommender system. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1989-1999, 2022.
[60] Tianxin Wei, Bowen Jin, Ruirui Li, Hansi Zeng. Zhengyang Wang, Jianhui Sun, Qingyu Yin, Hanqing Lu, Suhang Wang. Jingrui Hc, et al. Towards universal multi- personalization: A language model empowered generative paradigm. The Twelfth International Conference on Learning Representations, 2023.
[61] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. 2017.
[62] Donggeun Yoo and In So Kweon. Learning loss for active learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 93-102, 2019.
[63] Chicheng Zhang. Efficient active learning of sparse halfspaces. In Conference on Learning Theory, pp. 1856-1880. PMLR, 2018.
[64] Chicheng Zhang and Yinan Li. Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise. In Conference on Learning Theory, pp.
PMLR,
2021.
[65] Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Efficient active learning of sparse halfspaces with arbitrary bounded noise. Advances in Neural Information Processing Systems, 33:7184- 7197, 2020.
[66] Yuheng Zhang, Hanghang Tong, Yinglong Xia, Yan Zhu, Yuejie Chi, and Lei Ying. Batch active learning with graph neural networks via multi-agent deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence, 36:9118-91 18-9126, 2022.
[67] Fedor Zhdanov. Diverse mini-batch active learning. arXiv preprint arXiv: /90/.095444 2019.
[68] Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11592-11502. PMLR, 2020.
13

---

Published as a conference paper at ICLR 2024
[69] Jingbo Zhu and Matthew Ma. Uncertainty-bast active learning with instability estimation for text classification. ACM Transactions on Speech and Language Processing (TSLP), 8(4):1-21, 2012.
[70] Yinglun Zhu and Robert D Nowak. Active learning with neural networks: Insights from nonparametric statistics. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances Neural Information Processing Systems, 2022. URL https:// openreview net pww/ Eorum - 2 LRMMgkcoCni)
14

---

Published as a conference paper at ICLR 2024
A EXPERIMENTS DETAILS
In this section, we provide more experiments and details for both stream-basee and pool-based settings.
Ads
Cvartooe
Tarsoe
376
Megic'a leccze
Latte
Stutte
Reati
1705
Figure 1: Regret comparison on six datasets in the stream- based setting. NEURONAL-S outperforms baselines most datasets.
A.1
STREAM-BASED
Table 3: Test accuracy of all methods in stream- stream-based setting
Adult
MT
Letter
Covertype
Shuttle
Fashion
NeurAL-NTK (58
80.1 + 0.06
76.9
0.1
79.6
0.23
62.1 + 0.02
96.2
64,3
I-NeurAL
84.1 0.29
79.9 : 0.14
82.9 4: 0.04
0.16
99.3 10.07
73.6 1: 0.29
ALPS
75.6 - 0.19
35.9
+ 0.76
73.0
: 0.41
36,2
i: 0.25
78.5 0.21
74.3 1 0.01
NEURÓNAL-S
84.7 + 0.32
83.7
0.16
86.8 0.12
74.5 + 0.15
99.7 + 0.02
82.2 +0.18
Baselines, Given an instance, NeurAL-NTK is a method that predicts K scores for K classes sequentially, only based on the exploitation NN classifier with an Uppee-Contideecce-Bonl On the contrary, I-NeurAL predicts scores for K classes sequentially, based on both the exploitation and exploration NN classifiers. NeurAL-NTK and I-NeurAL query for label when the model cannot differentiate the Bayes-optimal class from other classes. Finally, ALPS makes a prediction by choosing hypothesis (from set of pre-trained hypotheses) that minimizes the loss of labeled and pseudo-labeled data, and queries based on the difference between hypotheses.
(UCB).
Implementation Details. We perform hyperparameter tuning on the training set. Each method has couple of hyperparameters: the learning rate, number of epochs, batch size, label budget percentage, and threshold (if applicable). During hyperparameter tuning for all methods, we perform a grid search over the values {0.0001, 0.0005, 0.001) for the learning rate, (10, 20, 30, 40, 50, 60, 70, 80, 90) for the number of epochs, {32, 64, 128, 256} for the batch size, (0.1, 0.3, 0.5, 0.7, 0.9} for the label budget percentage and {1, 2, 3, 4, 6, 7,8, 9} for the threshold (exploration) parameter. Here are the form (learning rate, number of epochs, batch size, label budget the final hyperparameters percentage, and the turning hyperparameter): NeurAL-NTK. and ALPS use {0.001, 40, 64, 0.3, 3}. and I-NeurAL uses {0.001, 40, 32, 0.3, 6). For NEURONAL-S, we set μ = for all experiments and conduct the grid search for y over (1, 2, 3, 5,5,6, 8, 9}. In the end, NEURONAL-S uses (0.0001,44 40, 64, 0.3, 6} for all datasets. We set = as the norm parameter for NEURONAL-S all the time.
Cumulative Regret. Figure shows the regret comparison for each of the six datasets in 10,000 rounds of stream-based active learning. NEURONAI-S outperforms baselines most datasets. This
15

---

Published as a conference paper at ICLR 2024
demonstrates that our designed NN model attains effectiveness in the active learning process, which consistent with the best performance achieved by NEURỘNAL-S in testing accuracy.
Ablation study for label budget. Tables 4 to 6 show the NEURONAL-S in active learning with different budget percentages: 3%, 10%, 50 %. NEURONAL-S achieves the best performance in most of the experiments. With 3% label budget, almost all NN models are not well trained. Thus, NEURONAL does not perform stably. With 10% and 50% label budget, NEURONAL achieves better performance, because the advantages of NN models can better exploit and explore this label information.
Table 4: Test accuracy with 3% budget in stream-based setting
Adult
Covertype
Fashion
MagicTeelscope
Letter
Shuttle
I-NeurAL NeurAL-NTK
79.4%
52.8%
51.9%
72.3%
74.6%
93.0%
23.9%
1.56%
11.9%
32.9%
42.8%
70.6%
ALPS
24.2%
36.8%
10.0%
64.9%
72.7%
79.4%
NEURONAL-S
79.9%
65.6%
69.7%
77.3% %
74.2%
99.8% %
Table Test accuracy with 10% budget in stream-based setting
Adult
Covertype
Fashion
MagicTelescope
Letter
Shuttle
I-NeurAL NeurAL-NTK
80.5%
55,4%
71.4%
77.9%
81.8%
99.2%
70.5%
59.9%
38.7%
34.3%
53.8%
75.9%
ALPS
24.2%
36.8%
10.0%
35.1%
79.9%
79.4%
NEURÓNAL-S
79.5%
71.3%
81.3%
82. %
81.8%
99.8%
Table Test accuracy with 50% budget in stream-based setting
Adult
Covertype
Fashion
Magic'
Letter
Shuttle
I-NeurAL NeurAL-NTK
83.4%
65,9%
82.5%
77.9%
85.8%
99.7%
76.9%
73.1%
56.8%
81.6%
79.3%
97.1%
ALPS
75.8%
36.8%
10.0%
64.9%
81.5%
79.4%
NEURONAL-S
84.6%
75.9%
85.4%
86.4 %
86.9%
99.8%
A.2 POOL-BASED
Baselines. BADGE uses gradient embeddings to model uncertainty. if the gradient in the last neural network layer is large, the uncertainty is also large. They pick random points to query using the k-meanss++ algorithm and repeat this process. DynamicAL introduces the concept of training dynamics into active learning. Given an instance, they assign it pseudo-label and monitor how much the model changes. They query for the label of the point with the biggest change in the training dynamics. CoreSet has a simple but powerful approach. The algorithm chooses points to query based on the loss over the labeled points and the loss over the unlabelled points, i.c., the core-set loss. ALBL is a hybrid active learning algorithm that combines Coreset and Conf [55].
Implementation details. For all methods, we conduct the same grid search the stream-based setting for the learning rate and number of epochs. For NEURONAL-P, we perform grid search over H.Y (500, 1000, 2000).
Testing accuracy. Figure 2 shows the average test accuracy at each round. NEURONAL-P can outperform baselines in few query rounds. Our method utilizes highly effective network structure, including the principled exploration network and CoreSet, which solely relies on the embeddings derived from the last layer exploitation neural networks to select samples based maximum distance, our approach avoids susceptibility to outlier samples. Similarly, BADGE also operates on the last layer of the exploitation network using the seed- based clustering method, lacking adaptability to the state of the exploitation network. DynamicAL's approach relies on the training dynamics of the Neural Tangent Kernel that usually requires very wide neural networks. ALBL is blending approach, but still suffers from the limitation of CoreSet.
selection strategy. Unlike
16

---

Published as a conference paper at ICLR 2024
Civetooe
HagiChiaangee
B258
SIDCE
Opecinnt
Figure 2: Test accuracy versus the number of query rounds in pool-based setting on six datasets. NEURONAL-P outperforms baselines on all datasets.
Ablation study for μ and 7. Table shows NEURONAL.PP with varying ls and values (500, 1000, 2000) on four datasets. Intuitively, if and is too small, NEURONAL-P will place more weights on the tail of the distribution
P. Otherwise, NEURŌNAL-P will focus more on the head of the distribution of P. From the results in the table, it seems that different datasets respond to different values of μ and 7. This sensitivity study roughly shows good values for μ4,
Table Testing Accuracy on four datasets (Letter, Adult, Fashion, and MT) with varying p and y in pool-based setting
Letter
Adult
7
500
1000
2000
500
1000
2000
500
80.9%
81.7%
80.5%
500
79.9%
79.4%
78.9%
1000
77.9%
83.9%
78.9%
1000
79.1%
79.7%
79.0%
2000
81.7%
81.8%
80.1%
2000
79.4%
79.4%
79.7%
Fashion
MT
Y
500
1000
2000
500
1000
2000
500
80.3%
80.5%
79.5%
500
79.5%
80.9%
80.6%
1000
80.5%
80.6%
80.4%
1000
80.2%
80.9%
80.1%
2000
80.8%
80.9%
80.7%
2000
80.5%
80.6%
81.3%
B STREAM-BASED VS POOL-BASED
To answer the question "Can one directly convert the stream-based algorithm to the pool-based setting?", we implemented the idea that one uniformly samples data from the pool to feed the stream-based active learner. Denote the new algorithm by Neu-UniS, described follows.
Neu-UniS: In a round of pool-based active learning, we uniformly draw a sample from the pool and feed it to the ftream-based learner. If the stream-based learner decides query the label, it costs one unit of the label budget; otherwise, we keep uniformly drawing a sample until the stream-based train the neural model based on the sample and label. We keep doing this process until we run out of the label budget. In this algorithm, the stream-based learner is NEURONAI-S (Algorithm I in the manuscript).
learner decides to query the label. Once the label is queried,
17

---

Published as a conference paper at ICLR 2024
Under the same setting used in our pool-based experiments, the testing accuracy of Neu-UniS compared to our pool-based algorithm NEURONAL-P is reported Table
Table 8: Test Accuracy of Neu-UniS and NEURONAL-P
Adult
Covertype
Fashion
MT
Letter
Shuttle
Neu-UniS 78.0
59,4
78.6
71.3
79.4
97.9
NEURONAL-P
79.9
66.9
80.9
81.3
83.9
99.6
Why does NEURONAL-P outperform Neu-UniS? Because Neu-UniS does not rank data instances and only randomly chooses the data instances that satisfy the query criterion. All the stream- based algorithms have one criterion to determine whether to query the label for this data point, such as Lines 8-9 in Algorithm satisfy the criterion, then Neu-UniS will randomly choose from the 100 data points, because uniformly draw a data point and feed it to freamm-asee learner each round.
Suppose there are 200 data points. If the 100 data points among them
On the contrary, NEURON AL-P has a novel component (Lines 10-12 in Algorithm 2) to rank all the data points, and then draw a sample from the newly formed distribution, to balance exploitation and exploration. To the best of our knowledge, this is the first inverse-gap gap weighting strategy in active learning. Thus, its analysis is also novel.
In summary, stream- based algorithms cannot directly convert into pool-based algorithms, because they do not have the ranking component which is necessary in the pool-based setting. Existing works [58 22 [4] only focus the stream-based setting and [52 6 57 only focus pool-based setting. We could hardly find existing works that incorporate both stream-based and pool-based settings.
C UPPER BOUND AND LOWER BOUND FOR LH
Definition C.I (NTK 58). (x all i,j j [T. define
Let N denote the normal distribution. Given the data instances
E
EN
H 20.3 (x), Xz), A
2
E%11 2E 2.. (b)) HJy = 2H Bu E.y.
Then, the Neural Tangent Kernel matrix defined as H (H" 1/2
Then, define the following gram matrix G. Let g(x; 0o) Vef(z; 0o) RP and G [9(x1,1: /m...m........... g(xT,K; 0o)/ /m] E RPXTK where p = mmdd++d-n (L-2)) Therefore, we have G = G G. Based on Theorem 3.1 in 4, when m 2 Q(T*K* (0TK////)) with probability least 1 5, we have
G - H S.
Then, we have the following bound:
log det(I + H) = log det (I+ (H-
^ (
log dcg G) (I+ G)- H G))
log (I |
H G|
(C.I)
(I+ +T+G)+V7|H-C
(ea)
log G) +1
18

---

Published as a conference paper at ICLR 2024
where (c1) is because of the concavity of log det(:),, (e2) is by Lemma B.1 in [68] with the choice of m, and (ex) is by the proper choice of e. Then, Lи can be bounded by:
log dct + H) & log det G) +1
log det(I + GGT)
TK
log det I+
g(x; (x) 0o) 7mm
(2))
S loglll1111 + ((TK)/P)) +1
where (ei) is because of det(I+ G G) det GG and (e2) is an application of Lemma 10 and [x;;;;; 12 S O(vmL) with 2. Because p = m + mkd + m² x (L - -2), we have
Ln = log det(I H) I (mKdd).
(C.2)
For the lower bound of LH, we have
LA log det + H) log (Amiu (I (I+ H) TK log(1 + Au)-
(C.3)
D PROOF OF THEOREM 5.2 AND THEOREM 5.3
First, define the general neural structure:
f(x;; 0) Vm LO W W-11.... (Wix;))) BK
(D.1)
where 0 [vec W1) ..... vec W TI RR. Following
L5 given an instance x, we define
the outputs of hidden layers of the neural network:
gt,0 g o (WB..-)), L - 1].
Then, we define the binary diagonal matrix functioning as ReLU;
Dr. diag(1 ( (Wig..-))).... I(
Accordingly, the neural network is represented by
f(x;; 0) V
D W,)x,,
E=
and we have the following gradient form:
Fw.f(xt Vm [g W D., W.),, mm 1.m.g.1-1111111 L.
Let 0 be the random initialization of parameters of neural networks. Then, we define the following neural network function class: Given constant R. 0, the function class is defined
B(0,, R2) 10 E R² ||0 01112 S R/m²/3)
(D.2)
Lemma D.I (33 With probability at least O(TL) expl- (1(mmm////) given w s Ol..9%2[oog(m) 3/2), J. for all 0, 0' E B(,, R), E [T). [T- 1]
||B < (1))
D - D'ylla & (/Lw)/3mm)
Lemma D.2. With probability at least 1 (xxp 2 L.), uniformly over any diagonal
matrices ....... D D E [-1,1]mxx with at most 233 non-zero entries, for any 0, 0' E ((01;w) with
3//2), we have the following results:
19

---

Published as a conference paper at ICLR 2024
(1) II + D., W S O(VL)
(D.3)
TEL
1-1
(2)
II (
D W 50
(D.4)
VK
T=U1
L-1
L-1
w/ [3133L2/log(m /log(m)
33)
WL II
(D,, + D. W, We
II
D W
5o
(D.5)
VK
7=4
r=41
Proof. Based on Lemma D.1 with high probability at least (nLL) exp( expe-eppppppapppee - |D',,+
D D lb s (Ow m))lo Applying Lemma 8.6 proves D.3
Then, by lemma 8.7 in
3 with 2/3 L) to W and W the results hold:
L-1
L-1 D W. W
w//3 L2 v m log(m)
Vm
W
I (D' Lr
+
(
0
K
7=4
r=
w/33 V Vm log(m)
m
D W,
D
(
0
17
K
r=h
(D.6)
Moreover, using Lemma D.I gain, we have
w/3 v mm log(m)
(W7. )
(D' or + + W
<O(VLw) S0
VK
(D.7)
L-1 II D. W
w/3 v m log(m)
(w w
S sO(VLW) 50
v K
Then, combining D.6 and D.7
leads the result. For, it has
L-1 WT
L-1
L-1
(D., (D., + D W
WL
II
(D., + W.,,W, w
II D w!!)
r=4
1=
I (1)
II
w
r=h
w//3
m log(m))
1 VK
+ 0
O
VK
VK
where (a) is applying the and Lemma 7.4 in B. The proof is completed.
Lemma D.3. Suppose the derivative of loss function L' < O(1). With probability at least 1 - O(TKL?) expl 2/3 L)}, for all t E [T]. l|e 0 < and w - ((L-=(log(m)) -3), suppose (0)ll2 5 VK, holds uniformly that
[ol((x; 0)]l S (m)Lm)
(D.8)
|Vof(x; [k]] < O(v ((VLm)
(D.9)
[Voc( (V 1)m
(D.10)
Proof. By Lemma D.I the result holds:
IV 0)]lr IlVmge,.-1la O(vm).
20

---

Published as a conference paper at ICLR 2024
For / E [L 1], the results hold:
L-1
Ww, =x)=== V W. II Dr, W+ll
r=++1
L-1
= =/m 1B,1-1ll1 [|
II
Dir W
r=1+1
v Vm VK
0
Thus, applying the union bound, for / E [L], E (T]. hs E [K] it holds uniformly that
K +
[e[(xx;)]] S f(x:
=((VLm)
K
m
Let eg be the k-th basis vector. Then, we have
[of(x;;)]|]]l S
Σ ex f(x O(VLm)
These prove (.8) and D.9.. For Wr., r., the result holds:
Vw, L. (0)lrr (0) IIV,,, (0VKm))
For / E [L - 1], the results hold:
VV 1l0 S O(Vm).
Therefore, VoC. = V IV S L
Lemma D.4. With probability at least - O(TI, (ampp=O(mm2/3/p] I.)] over random initial-
ization, for all [T], and 0, 0' satisfying |0 01112 S w and 100 0112 la w with w S 0L0-8(log m] -3/2),, it holds uniformly that
w/ m (mg(m)
[f(x;: 0'][]] f(x;; 0)[ [of((x 0' -01 50
||0 0'1l2-
VK
Proof. Let Fxx;; [A][ 0)[k] (Vof(x; 0)1k), 0) and ex BK be the k-th basis
vector. Then, we have
L-1
f(x;; [k) F(x;; [')[k] = --vm
wz( Σ
D W. W.,.,, Wi)guz1
1-1
T=/+1
me
WL -g,..1)
Using Claim 8.2 in 3. there exist diagonal matrices D E RR with entries in [-1,1] such that |D//llo I 2/3) and
gt -
8 81.-11
I DD' + WW,,,,, (D', + +D)+ -W)g--1
r-ll1
21

---

Published as a conference paper at ICLR 2024
Thus, have
1-1
[[x;; ['][ - Fxx;; 0')[[ = V m
Wt D. Wi)
m
ek
WL(
Σ
Dú, W, (W, Wi)g.111
r=H+1
wVg
w/3 m log(m)
g W Will2
VK
IA
w1/3 1 V m log(m)
|00
0'1
VK
where (a) is applying (.5) and (b) is based on Lemma
D.1 The proof is completed.
Define (0) = || 0) - lell2 and Lt = [[(;; [b] [,[k]], where I, E RRK represents the corresponding label to train.
Lemma D.5 (Almost Convexity). With probability at least 1 O(TL2K)
L) over
random initialization, for any 6 > O and all t. [7], and 0, 0' satisfying 0 0 ll2 S w and |0'
0 112 S w with w S O (2 L 9/4 (Kmllog mil -3/8) AOLL "log m] 3/2), holds uniformly that
K
(0) 2 (0) + Σ (o), 0' - -6.
Proof. Let (0) be the loss function with respect to f(x;; 0') [k]. By convexity of C, it holds uniformly that
(0) (0)
L/ (0) (f(xx; f(x;: ()())
K
(1)
(V]( 0)
(1, [f(x;; 0¹) [K] f(x:; [} (V](x;; 0)[4,, 0- -0)1
K
(VoL,,((), -0)
f(x;; [K]
f(x;: 0)[4 (V((x; 0' 0)
km
w//3 1,3 v mm lo) m)
O.
VK
(VoL,,
where (a) is due the convexity of Li, (b) is application of triangle inequality, (c) is because of the Sauchy-Schward inequality, (d) is the application of Lemma D.4 and (e) is by the choice of w. The proof is completed.
Lemma D.6 (Loss Bound), With probability least 1 O(TL"K) exp
[(mw2/3 L)] over random
initialization and suppose R. n, m satisfy the condition in Theorem 5.2
the result holds that
T
Σ c. < Σ (((0))
(D.11)
t=1
t=1
22

---

Published as a conference paper at ICLR 2024
where 0* arginnfeBs0,. R) Et= (i(
Proof. Let = ( (Kmm) 33/ [log m such that the conditions of Lemma D.5 are satisfied. Next, we aim to show |0: 01 22 S w, for any t E [T]. The proof follows a simple induction. Obviously, 0 is in B R). Suppose that 0,, ................................ .., Or BiO,, R). We have, for any t e (T),
T
T
T - Σ (Kmm)
|0r - 01112 -
Σ
00 0,112 S
n VL.
1=1
R
ST (-V LKM)
Sw
mVTK
when m > L KK 9). This also leads to vm S w.
In round f, therefore, based on Lemma D.5 for any 10: 0 I w. it holds uniformly
K
L.(0.) - -.(0)) S k
0, 0') +
Then, it holds uniformly
(a) (0: 02+1, O: - 0')
(.))) - (,))
+
(b) |10, 0111 + 0,
0.41
1 00+1 - -0'12 +
2n
|10, 0'113
|1:+1
0'
12
+ 2nl VoL. +
2m
JV
11
11113
00+1
tn(K + - 1)m +
21
where (a) is because of the definition of gradient descent, (b) is due the fact 2(A, B) ||
|| || B- (c) is by |10, 1121 = Ve, < O(1 + 1)m).
Then, for T rounds, have
T Σ
T
(O.)
Σ
(())
1=1
(4)
10
0'113
T Σ
T
+
110 0/11((
+
Σ
[L + K - 1)mm + Te
2m
27
2m
(=2
1=1
|0
111
+
(L K 1)mm + Te
21
t=1
R²
+ T(K + 1)mm+ + Te
2ml
(b)
0 (VTKR)
where (a) is by simply discarding the last term and (b) is setting by n mVTK' 5 K, and
VR The proof is completed.
T
23

---

Published as a conference paper at ICLR 2024
Lemma D.7. Let G [ (o)[1), (o, fo, 0u) (I]/ homlll//m E R
Let H be the NTK defined in. Then, for any 0 < I 1, suppose m 92( T (og(TKL/61) then with probability at least have
||G G S Ao/2;
G G G 2 H/2
Proof. Using Theorem 3.1 in 4. for any 0 and 8 (0. 1), suppose = 12( 1 (0 for any j [T], k, k E []], with probability at least - 6, the result holds;
(Ve,,((x; [k), Ve. [xy; (o)(k))))))))))))))))))) /)/m / Hu. S. Then, take the union bound over [T] and [K] and set result hold
with probability at least 1 8, the 2TK.
do
T K T K G G ==
(Ve, f(x; 0o)[k,, Ve, f(x;; (0)(k))))KK))/ H. 12
A STKE= 2
where = 1 1 K log(T" MOTTTKKLLL K2L/11).
Lemma D.8. Define = [e(y [(yT,KKYTT)] E RTK and S' H- u. With probability at least 8, the result holds:
inf OEB(0G:S))
L.(0) VTKS'
Proof. Suppose the singular value decomposition of is PAQ P T Q E RTTK then, A > 0. Define 0 =6, + PA Q u/ym. Then, we have
RXXRK E
PA-'Q'
VmG -00 QAP PA Q u=u.
which leads
K (((y,,, -
Σ
- Oo)l = 0.
t=1
Therefore, the result holds:
| - -00-3 = u QTQAA22 u/m G) S u u/m
(D.12)
Based on Lemma D.4
given w mirz and initialize f(x;; 0o) + 0, we have
R
T
T K
Σ
(0)
<
Σ
ye (xx -b)) + +TK- o ( m mml((m)) ||0 0olla
1=1
k=1
T
K
yrik] - 0u)kk) 0- -b0) + +TK - 3 log(m)
1=1
[y]
00)1 ((x; -0)1 + +TK
-TKKO ((/mm 1/24/33 13 vm (mg(m)
T K
Σ
y [k]
fxx: -b01 + VTKR
k=l
24

---

Published as a conference paper at ICLR 2024
where (a) is by the choice of m 2 Si(T K R²). Therefore, by putting them together, we have
((( - VTKS.
OE
where = vu
D.I MAIN LEMMAS
Lemma D.9. Suppose m,m, 112 satisfy the conditions in Theorem 5.3 probability at least - 8 over the initialization, it holds uniformly that
For any 5 (0, 1), with
T
E DxnD
(u: =x(((x)):0))) 11766-1
T
0o
K 5) 2 T
2l0g(3/8)
T
where
H4-1 fxr: Vr |= is historical data.
Proof. This lemma is inspired by Lemma 5.1 in [3 For any round [T], define
V = [| 0 (u: - fi (x:; (xx; 0,)))22 A 11]
(D.13)
-[(((((;); 0) (u, fx 0, A
Then, we have
B =E [ (xx:;; 0 (u: - fi (xx, 0. E (fx((())) 03) (u, (x 12 1|F-11
(D.14)
where F,-1 denotes the r-algerra generated by the history H4-1- Therefore, (ViH=1 the martingale difference sequence. Then, applying the Hoeffding- Azuma incquality and union bound, have
T
T
2 2log(1/0) 1/6)
V1
E.V
(D.15)
T
T
t=1
As I is equal to 0, with probability at least we have
E
[[]()(()):
03) (u. (xi( 0.))122 A1]
7
log( 1/8) 2lo((1/8)
(D.16)
[a( (ur fi (xx: 0, 12222 +
7
For 1z applying the Lemma D.6 and Lemma D.8 to 0², we have
I s O(VTKS))
(D.17)
25

---

Published as a conference paper at ICLR 2024
Combining the above inequalities together and applying the union bound, with probability at least 1- 6, we have
[(((((()); (u. (x,; 02))
D1
(D.18)
K /
2 1og(2/0)
<0
S' +
T
Apply the Hoeffiding Azuma inequality again on s" due to E[S"] = S, the result holds:
[f(( 0;) (u, f (x, 0.))112 A
E1
K (
2 2loo(3/5)
+ 2V T
where the union bound is applied. The proof completed.
Lemma D.10 is an variance of Lemma D.9
Lemma D.10. Suppose m, 91 112 satisfy the conditions Theorem 5.3
For any (0, 1), with
probability at least 8 over the random initialization, for all & [T] it holds uniformly that
E (x.y))
(x;; 0+)) (u: - -f2(b(x)); 0
177-11
(v===
K
2 log (3g(3T/5)
(D.19)
0
S + +2
t
t
where u, (t)y ,.y..)...... H (x,, yr 1 is historical data, and the expec- tation is also laken over (0) 07).
y(),
Proof. For any round E [t). define
[[x(((x)): (u,- - fx;: 0.))
V,
E
(> DDD
(D.20)
[f((((x)); ( 0- - (u, - -x((x; : 01))11211
Then, we have
[[][0(x)); - (u, - (x,; 0'
EVV
E
(x,
[f2()xx)); 0 -u, - fx 1|FF-
(D.21)
E (x
where F, denotes the o-algebra generated by the history H H4-1- Therefore, {V+ are the martingale difference sequence. Then, applying the Hoeffding-AAum inequality and union bound,
we have
2 llog(1/0)
P
B F
8
(D.22)
As J equal to with probability at least
we have
[1E((0((;): (ur - (x 0. A1
(D.23)
(a(x((x)) -
-uu, - fx(x;; T. +
log log(11/)
26

---

Published as a conference paper at ICLR 2024
Based on the the definition of 0 0 0 in Algorithm | have
E (x),)))>
(x;; (xx; - (u, (x 0 A
.2)
(D.24)
E X.
|lfi (xxxxi 0²) (u, fx(xx;0,)) (1))
Therefore, putting them together, we have
E [xx: 02-1) (u: fx 02)) A
(N..s))
2 log(11
[xxx (u, (x 01)1la +1
(D.25)
1
I2
For 12, which is an application of Lemma D.6 and Lemma D.8 we have
1e S O(VtKS))
(D.26)
where (a) is because of the choice of m.
Combining above inequalities together, with probability at least 8, we have
E
[| (x1: 1 + fz(o(x));0) u
(ND
0 (V +V
log (log(2T/0)
(D.27)
where we apply union bound over ó to make the above events occur concurrently for all T rounds. Apply the Hoeffding-Azume inequality again on S' completes the proof.
Lemma D.11.
Suppose m. m, 71, 122 satisfy the conditions in Theorem 5.3
For any å (0,1), 1,
with probability at least over the random initialization, for all t [T]. when I = holds uniformly that
E x
[b])
E xx~Dx
[k('))
Proof.
As I = 0. we have
[x;;; [.)
f(x;; 0.) [k) f(;;; 0,) f(x;; 0,)[k=1 2 2y,,.
In round t, based on Lemma D.10 with probability least 1 8, the following event happens:
Ea [4, [K], E. [ 0+)[ h(x+) s 3.
(D.28)
xx>Dx
When Eo happens with probability at least 1 - 8, we have
E
0.) B v
[n(x,) S E [f(x; (x) + Be
xi
xinDx
xINDx
(D.29)
E [f(x; 0.) B. E [(x;) [k9]
S E [f(x; 0.);: +
Xx
xi~Dx
X.-Dx
Then, with probability at least 8, have
E
[bxx [kx]] 2
[f(x;: 0.) f(x; (.) 23,
xx-Dx
x,>Dx
(D.30)
> 2y 23,
>0
where the last incquality is because of 7 > Then, similarly, for any e ([K] \ (īe, A)))) we have E [h(x))[k] - h(xx)] 2 0. Thus, based on the definition of h(x;)[k") we have xx~Dx
E [b]]x)[]]]=
E [h(x:)[A*]]. The proof is completed.
xx~Dx
27

---

Published as a conference paper at ICLR 2024
Lemma D.12. When 2 T =
holds that 2(7 + 1),3, S
e²
Proof. To achieve 2(7 + 1)3, S there exist constants C1 C2, such that
4(7 1)2 [KS +
62
KS
log 2log(33)) (3//))
S 2( +
The proof is completed.
Lemma D.13. Suppose m. Th, satisfy the conditions in Theorem 5.3 Under Assumption _ for any 8 (0, 1),7 > with probability at least 1 8 over the random initialization, when 2 T, holds uniformly:
E
[1] = 0,
x
E xi>Dx
[k*]] = EE [h(x,) [}].
X.>Dx
Proof. Define the events
t T. [h(x))]] -(x,)
x,-Dxx
& T,
E Dx
[(xx; 0,) [k| f(x(i 0,)
(D.31)
Σ t T.
E x
f(x: 0 [k*]
f(x;: [o] <2yB,
The proof is to prove that ε₁ will happen. When Eo Eq. (D288) happens with probability least
1 - 8, we have
E
[x
[k*]]] -,, s E h(x;)
- E
[f(x; 0,) B [f(x; 0,) 3,
X X. Dx
x,>Dx
x.-Dx
(D.32)
E
- B, s E
[bxx,),111]
E xx~Dx
x,>Dx
Therefore, we have
E xx
S E. [((x; (x)k=1])(k*]]] + +3, +, (xxx:())( B. x,>Dx
xxx
<
0.)[k' f(xri 0()x;0)][k9] + 2B, xx
E
Suppose El happens, we have
E Xew Dx
- < 2(7 + 1)3,, (xx;)
Then, based on Lemma D.12 when T,2(7 1) < Therefore, we have
E X, Dx
ln(x:))k*) - [A:]]] < 2(7 + 1) Se.
This contradicts Assumption 5.1 i.e., hx*,))
e. Hence, & will not happen.
Accordingly, with probability at least 1 - 5, the following event will happen
ε2 = { t2 T, E
f(x;; [k) - f(x: 0.][ 2 2r
(D.33)
xx
Therefore, have Eff(x,; 0.) [b)]
[f[( 0.) [k-]]
28

---

Published as a conference paper at ICLR 2024
Recall that k- arg [ h(xx)]k]] and ie arg maX f(x;; 01) [k]. As
vk ([K] {1))), fxx; [x) - f(x:: [k-
Ak E ([K) \ (K)),
E [(x;; 0.) [t]] - xx~Dx
[ [k)[
xx
have
Ak E ([K) (kF)),
E [[(x;;0)((
> E
[[(x;; [b]]
x,<Dx
x,
Based on the definition of k we have
X [xx;; 0.) =
[(x;; 0.)
[maxf((x; [k]]
(D.34)
X,
X. iE|k]
This indicates & happens with probability at least Ó.
Therefore, based on &g and D.34), the following inferred event &g happens with probability at least
1 6:
[f(:; 0,) - f(x;; (A) 2 2//3, }
Eg
T. IE X
Then, based on Eq. D.32
we have
[l((x,) [k]
[R*1) 2 [x[ [k] B. 1 (F[((xx (+)[k="] + 3.)
= [x, (b] [k) -23,
(D.35)
_ 2(7 1),3,
0
where Ej is because &g happened with probability at least 1 6. Therefore, we have
E x [[]]
[k]]] > O.
x.
Similarly, prove that
vk E ([K) (6)))
E
[xxx
[h(x)) [k|] > 0.
xx
Xx
Then, based the definition of k., we have
E
[h [x]
E X
[xx])
mmax [x]]]
X
X. kE[K]
Thus, the event E happens with probability at least 8.
D.2 LABEL COMPLEXITY
Lemma D.14 (Label Complexity Analysis). For any 8 E (0.1), 2 1, suppose m satisfies the conditions in Theorem 5.2 Then, with probability at least - 6, we have
Nr ST.
(D.36)
Proof. Recall that x,, = max x.. JE(k) f(x;; [k), and X2,5 = maxx de(// f(x;; [k).
With probability at least 1 - 8, according to Eq. (D.28) the event
E0 E [t], [K],
E xx
[If(x,;,))00 - h(x, [+=]] S S
happens. Therefore, we have
E
h(x,) [k]] - B, S E
f(x; 0.] S E
h(x,)) [k]] + 3 E [h(x;)[A+]]] B,
x
xx
x xx
E hhxx)) G, < E
[f(x;: 0.) [k]]
<
xx
xx
xx~Dx
29

---

Published as a conference paper at ICLR 2024
Then, have
IF
[[(x;; (c)
f(x;; [b)]]
E [b]
E [1(x)
[x()))[[)]] + +3,
Xe
xr~Dx
x,
(D.37)
E xx
[f(x;: (e]
f(x;: [1)
E
[b{x,
E x,>Dx
[xxx]]]]]]] 23,
xx>
Let
= E X,nDx
[x]
E
[x(x))[k)]] Then, based on Lemma D.12 and Lemma D.13
xx
when 2 T, we have
2( + 1)3, S 6 1
(D.38)
For any t E [T] and t < T, we have
E
[L] < 1.
x
For the round t T. based Lemma D.13 it holds uniformly
E Xx
[h(x,)
E [bxx)][+=]]] = q. Then, based on D.37 we have Xe~Dx
Eg [[(x;; (.)(k] f(x;; 0x) 6 -23, 2 27,
(D.399
where E2 because of Eq. D.38).
According to Lemma D.13 when T, E [[(x; 0,)[=]] =
[f(x;; (.] Thus, it holds
xi<Dx
x,>Dx
uniformly
f(x;: 0x) - f(x;;
T.
Then, for the round f T, we have
[T]] =
x,>Dx
Then, assume T > T, have
N
Σ
E
Lff(x;:0) (x) ((xx00)][K9) [[]]=]]<]]] < 2/
Xe
1=1
T
(D.40)
<
Σ
E
1[f(xx; f(x;; < 2y
D
1=T+1
T + O.
Therefore, have Nr < ST.
Theorem 5.2. /asream-based)). Given T, for any (0, An > O, suppose ||x||22 = 1, (T). H. > Aol. m 2 Q(poly(T, L, S) log log(1/5)), m = = 0 (((/)R) Then, with probability at least 1 over the initialization of 0.. 02 Algorithm Dachives the following regret bound:
Rytream (T)T)()) (VKS+ 22log(3T/5)
where N(T) & O(T).
30

---

Published as a conference paper at ICLR 2024
Proof. Define R.
I x,
[xxx)]]]]
h(x,)(k*']]
T Σ
Retream (T)
RI = 1VL, =0)
max R (I [[ = 0))
E [[]f(xx;)--11 [1l12]
(x..y))oDD
K V..
(0( 13T((3//))
2210
+0
t
(OTTR))+OV21olmm (V2Tlog(3T/))
5O + +0
where (a) is based on Lemma D.1l
R1 = 0) = 0. The proof is completed.
Theorem 5.3. /Stream-based). Given T, for any 8 E (0,1),7 1, Ao 0, suppose [|x|||2
1, E (T]. Hz AoI, m 2 Qipoly(T, K, L) log(1 (1))))))))))))))))))) m = =12 = O TTK and Assumption
5.1 holds. Then, with probability at least ô over the initialization of 0 0 Algorithm 1 achiives the following regret bound and label complexity:
Ratream (T) < O(KKS + log((3//)))e)) N(T) S SO(KS + logo
(5.2)
Proof. Given T, we divide rounds into the follow two pars. Then, it holds that
Rytream (T) Σ
T
T
RT = +)+
Σ
R. = 0)
(D.41)
1=T+1
Σ
E
[hxx))
[k]
[k*
Σ
E
[((;, [k] hxx))(²))
x
xx
I=
For I1, it holds that
R1 (01=1)= 1)
E [ h(xx [A=]]
xx>Dx
[b(x))
f(x;: [,)[k] + f(x;; 0.) [xx]]][a]]]]
=
xx>Dx
(a)
Ι E
[h(x)) f(x;: (x) - f(x;; [k)(k=] - [x*1]
xx>Dx
E
[lb(x:) [ f(x:; (x) + E
[[)(x;;0.){A') [xxx)
xx>
X.
2 E [[]h(x;) f(x;; 0.) [
Xx
<
[|]:(( 0,-1) - uulla
S + +0
(
2 2log(31/8)
0
T
31

---

Published as a conference paper at ICLR 2024
where (a) is duo the selection criterion of NEURONAL and (6) is application of D.10 Then,
K
. +0 2 21og(37/5)
1
Σ 0
(
t=1
(2VV 1) 1)[vKS+ + / (log(33/0)
For 12, we have (1; -0 Therefore, holds that:
[x((;) - based Lemma D.13
X, Dx
R Reream (T) 5 (2 / 2log (3Tg6)
The proof is completed.
E ANALYSIS BINARY CLASSIFICATION
First, we provide the noise condition used [58].
Assumption E.1 Hlammen-Tssbaleee low noise 43 58 0, such that for all 0 < 1/2, X,K {0, 13.
There exist absolute constants and
P([((x)[4]
6) S C
2
Then, provide the following theorem.
Theorem 5.1. [Binary Classification) Given T, for any 5 E (0, Ao 0. suppose K
||xe||2 1, [T]. H AgI, m 2 M(poly(T, L, log( (og(118)),, 1n = 1/2 = 0 (_m) ( Then, with
probability at least 8 over the initialization of 0%, 0g Algorithm accheves the following regret bound:
Rstream (T) S ((S5) ( T(s)))tttaat
N(T) < Of
In comparison, with assumption
58 achieves the following results:
Retream (T) < θ (LH
LH
2(
Taiz 412
+ (
N(T) < δ IA प + δ IL [I (
For the regret Rutream (T), compared to 158 Theorem 5.1 removes the term Ö
[L
2fa++1) 112
Tatx
and further improve the regret upper bound by a multiplicative factor LH a+1
For the label complexity N(T), compared [58). Theorem 5.1 removes the term Ö (nn o T oi and further improve the
regret upper bound by multiplicative factor TA .ीz, It noteworthy that La grows linearly with respect T, i.e., LH > 7 Tlog(1 + 2o).
Proof. First, define
4, hxxx)) - h(x,)
7, l(xi; [R] s(x:; [A) ]+ + +23,
(E.1)
T
T. = Σ
Ex [1{2 < <
t=1
32

---

Published as a conference paper at ICLR 2024
Lemma E.1. Suppose the conditions of Theorem 5.1 are satisfied. With probability at least 1 6, the following result holds:
Nr I O Te + o (52 + +log(3T/66)
Proof. First, based on Lemma D.11 with probability at least 1 - 6, we have 0 0 A. A. S 48,
Because Å 2 0, then A, I 43, implies A, I 4
Then, we have
I = 111A: S 43,}
< 1, S 43,,4, 2 + + S 43, <
16 x 2
A A1+1145 1
Thus, we have
T N
Dx [, & 133,
3 A 2) +
t=1
(161,3) A 1 +
1
[=1
16
< z
(25 + 2og (3T/ /8)) + T.
0 (2S + 2log (3 (T /8)) + Te
The proof is completed.
Lemma F.2. Suppose the conditions of Theorem 5.1 are satisfied. With probability at least 5. the following result holds:
RT So cT + 1 (52 + log(3T/5))
Proof.
Ry
E
[(xx))
hxx,)[[*]]]
D
E [|A+|]
X
E
|||
> +f]+
Σ
|ALIIAL S SeH
xx
D.
1=
33

---

Published as a conference paper at ICLR 2024
where the second term is upper bounded by <Te, For the first term, have
[
> eH
X1 xi
E | (2)
Ae
X
E 11 I ACC
Σ E |A/ > 28,H Ae xi>Dx
X
t=1
4,8%
1=1
00
(25 2olog(37/0)
where the second term (a) zero based on the Lemma D.13 The proof is completed.
Then, because Xi,..., XT are generated i.i.d. with Assumption E. 58 with probability at least - ò, the result holds:
Then, applying Lemma 23 in
log T 8
T. 37c + O(log
Using the above bound of T. back into both Lemma E.1 and Lemma the two bounds separately complete the proof:
E.2
and then optimizing
R S 50(S2 + +log(3T/6) # T T )
N O((S² 1og (8) + T T
F ANALYSIS FOR POOL-BASED SETTING
Define (.,)
[[f(x;; 0.) u, 13/2, (.,((,)) = (f(x;; 0.)[k] ux(k)))/2. and
Lemma F.1 (Almost Convexity). With probability least O(TL2K) cxpl 2(mw over random initialization, for all t E [T], and 0, 6' satisfying l|e 0 ll2 S w and 0 0,112 S w with S O [log m)- -3/2), it holds uniformly that
K
2.(0') 2 L.(0)/2+ Σ (O)
0)
where w O ((Kmlog
34

---

Published as a conference paper at ICLR 2024
Proof. Let (0) be the loss function with respect to f(x;; [k:]. By convexity of Le, it holds uniformly that
[|[(x 0¹) uzll3/2 2 ||[(x;;; 0) u. 12112/2
(0) (F(x:: [k) f(x:; (k))
(6)
K
2
(VF(xx 0)
(0) [f(x;; [k] f(x;; 0)( (Vf(x;; 0) 0- -0)]
(
K
CI, 0)
K
(f((x;;)) -u, [A] [[(x;; O') f(x;; [k[]] (Vi(x; 0)[4), O' 0)))
k=1
K
-) 0)- -0 (WA/S m log m)
m)
Vo (o -')
f(x;; 0)[6] u,(k:l
VK
(oor, 0' 0) -0 wW//3 133 Vm log m) Σ
K
[f((x;: 0)[{]] un [R:]
K
where (a) is due to the convexity of Lt, (b) is an application of triangle inequality. (c) is because of the Cauchy-Schward inequality, and (d) is the application of Lemma D.4 and Lemma D.3 (e) is by the fact S x² + 1. Therefore, the results hold
|| [[((;;;)) 0¹) - us! u11l/22 2 [|f(x;; 0) -u.12/2
K
-0; 0') o w//3 1,3 / m log m.)
VoCr,
[[f(xx; 0) -u.12
K
w/33 1,3 v m /mlog m)
K
K
4
K
Vo ( (0). 0' - 0)
[|x 0) - -1
km1
w//3 v log m)
K
VK
where (a) holds when 0 (4 (4-3/4 K 3/8 (m (ml -3 -/1).
In the end, when w S 0 (4-3//1 3/1 (m m log m) 3/8 9/1 9/1,3/1) 3/. the result hold:
[[[;;; 0') ur 1212/22 [|f(x; 0) ue 1B11/4
K
VoLr,(0),0) 0) -c
The proof is completed.
Lemma F2. With the probability at least OTTL2 9Mm0-90mm22/3 L)] over random initializa-
tion, for all E [T], 110' 01ll S andw - OLL 9/2 1 [log m] -3), the results hold:
f(x;; 0') log
35

---

Published as a conference paper at ICLR 2024
Proof. Using Lemma 7.1 in B1, we have gt,L-1 I (1), Then, Based on the randomness of W
the result hold: f(x,; 0') S log (analogical analysis as Lemma 7.1). Using Lemma 8.2 in [3], we have L-LL-1 S O11), and thus f(x(;0') I log m
Lemma F.3 (Loss Bound), With probability at least -xp- L.) over random initialization, holds that
Σ
-uell/2
inf ('e)(
Σ E1(((x;;)) -url/ 4LKR²
(F.1)
where 0" aaraannnnneeee anginfessee... 1 (O)
Proof. Let 0O < ((Kmlogm) 3/8 99/42//4) such that the conditions of Lemma D.5 are satis- fied.
The proof follows a simple induction. Obviously, 01 is in Bi0 R). Suppose that 01, 02, ....... Or Bi0,, R). We have, for any E (T),
T (c.)
0 - 01l12 -
01+1 01112 -
nl
1=1
$ 17
[f(x; 01) - us uell2-
Vo, fx:: 0,)12
S 17 v Lm
[[((x(00)) uel12
3V
7) LmT log m
where (a) is applying Lemma
F2 and (b) holds when 2 -
Moreover, when m < 9). it leads
vma < round t, based on Lemma D.5
for any ||0, 0' 0/122/2 < w. it holds uniformly
[[ 0,) uz 1 [|f(xx; 0') - -u.13/2 <
VoLe, 0. -6)) +
km
Then, holds uniformly
[|f(x; O₂) uz
1/12//4 1 [|f(x(; 0¹)
uu u²12/2
(0) (0, 0,+1,
0')
+ c
(b) 110, 0'
1/
0 0c+1
112
1
0'112
+
21
(0)
0,, 0'
0--1
0'113
K
m/ll
Vo, Lr, (0,))
2n
00
0'
00,-1
0'133
+
(f(x;; 0.)[k]- -u.())
Vo. f(x:: kk] +
21
A=
0
0'
|0,-1
0'113
mpmL
(f(xx; (k) ur (k:)))
27
k=
0
0'
0
-1
0'113
0.) uu
21
36

---

Published as a conference paper at ICLR 2024
where (a) is because of the definition of gradient descent, (b) is due to the fact 2(A, B) = ||A
| || B (c) is by ||0, 01+1l12 2 = ( Lm))
Then, for T rounds, have
r
T
[f(x;; 0.) -ull2/4
Σ
[xx; 0*)
ue 121l2/2
1=1
100
0'112
Σ
10: 0'112( 211
+
mmIK]][(xx(;) 01) uel12 Te
2n
21
10
MML. [f(x;; 01) - -1 -11122 11122 + Te
21
R2
T
Σ 2mm
+ m1LLK
[f((x; 01) - -ull2 Te
T
LRRLK +
[[f(x;;;) 0.) 1
where (a) is by simply discarding the last term and (b) is setting by v) mLK and e KRAL Based on the above inequality, taking the infimum over 0' E B00x.. R), the results hold
T
[|[(x;; 0.) uu uu.l//8
inf or 0'EB(0
[[((x;;0) uzll2/2 + 5LKKK 123
The proof is completed.
Lemma F4. Let R St Vu hu With probubility at least ((T(2()))p))))))) expl-S(mmu L)] the result holds that
inf (EB(Bo:R)
C.(0) (
Vo, f(x;; (n))))))) pose the singular value decomposition of is PAQ P REXTK A E gTKXTK QU QERKKI then, A > 0.
Proof. Let G =
Vor((x; [o][ V E RPXTK Sup-
Define 0" Og + PA--O. u/ m.. Then, we have
G TO0 -0) PA- qu==u
This leads to
T
K
[ - PVo - -0o) 0.
Therefore, the result holds:
|10 - =u==- TA -2-2QQae AaQQQQQu//mam u/m u [G 2n u/-m (F.2
37

---

Published as a conference paper at ICLR 2024
Based on Lemma D.4
and initialize (x;; 00) 0, [T], we have
T
K
Up(b:] Vo. f(x;; [k] - - - ( 2
(0)
(u,[k] f. (x)10 -00))²
+TK- O ( L Lm log(m)
t=1
(u,[k] (V. fxx 00) 00))² +TK O(('' // L log(m))
(u.(k] - (ox) 00))2 + OLLK)
$ {(LK)
Because 0º E00,, S"), the proof is completed.
Lemma F55. Suppose m. m, satisfy the conditions in Theorem for all L [Q]. it holds uniformly that
5.4 With probability at least 1 8,
O(LKS t
(lgg(1/0)
()(((())): (h(x+) (xx: S
+21
(F.3
u, = (I), ((),,K,)))), - = (x..yr)1z is historical data, and the expectation is also taken over (0) P
Proof. Then, applying the Hoeffding-Azume incquality as same as in Lemma D.6 we have
[x(d(x)): 02)) - (h(x,) - fū 02)) A1]
(x((((=): 02) -u, ((xx=:0))11 + log(1/8)
2 llg((1/))
(F.4)
[f(()(x)) P?) (u, fx(x;; (xxx:))))11 + -
t
13 INE
(LLKS
(1g((
OLLKS
2 1og(1/8)
+21
where (a) is an application of Lemma F3 and Lemma F.4 and (b) is applying the Hoeffding-Azuma
inequality again S". The proof is complete.
Lemma F6.. Suppose m, Mi 122 satisfy the conditions in Theorem 5.4 the result holds:
With probability least 1 8,
Q ?
Σ
Σ
pi(h(x))
[k+)
p (f(x;; (k) (Ax)))
1=1 x.EP.
1=1 x, x.
QKS + (log((/)))
Proof. For some 1) 0, we have
38

---

Published as a conference paper at ICLR 2024
Q
Σ
ps (b(()x))[[] (x*))) - Σ ([]((x;0))[k - hxx,)[(=))
X
Σ Pil(h(x;) [xx,) (f(xxx;: 0.][k'] hxxx)[(*)]+
P
p:[(h(x;)[R] f(x;; 0.) + (f(x;; 0.) h(x;)]l+*)> (f((x;;; 0,)[k*] [xxx)[k*)))]
1= x:EP:
Σ
[h((x()))() f(x;; 0:) + (f(x;; [x) -xxx))[=*)) (f(((x:: 0.)(a') (xxx))(a1)
1= X.EP:
(0)
Σ pi(h(x,) f(x;; 0x([() + Q
4n
1= x;
(
Iu 0,)11 O(oo(())))))) + Q
4n
2 @K5 + 0(log(10)) + Q
4n
1 where (a) is application of AM-GM: r722 < 7 and (b) is application of Lemma F.7 based on Lemma F55 Then, replacing 17 by completes the proof.
(c) is
Lemma F.7. (Lemma 2. (25)) With probability 1 - 8, the result holds:
Σ
Σ prllf(x;; 02)
h < 2 [f(x;; 0.) - -ueli + (oloo((//)).
EE
Finally, we show the proof of Theorem 5.4
Proof. Assume the event in E7
holds. We have
R Reool (Q) =
Σ
E (x..y.)-D
yc)]
(x.Y))DD
E
[h(x;) [
E
[xxx))(
Xx
Σ
pa( + (g22))
x.EP,
where (a) is application of Azuma-Hoeffdiae Hoeffddng inequality.
Next, applying Lemma and Letting & VQKS² Ollog(1/))) have
39

---

Published as a conference paper at ICLR 2024
7 Q
Σ n((((x;0))k]] - -(())) + Q + 22Q log(2/0) + g
Repoo (Q) S
4
(=1 x.EP,
p: 0.); 1xx)) o +
Σ x.EP:
+
1n
27
[f 0.) uell + 7og 100s(00'1/0 1)/4+
Q + /2Q1og(2/0) +
2
7
(0) 7 KS² + + log(26 1/44 Q + 22Qlog(2/8) + VQK2 + O(log(1/0))
-
2
Q
< VOIQKS KS22
01log(8 + 2(v2Q
where (a) follows from
F.6 (b) follows from
F.7
(c) is based on Lemma H5 and we apply the union
bound to the last inequality and choose
KSZ Therefore:
(v
Q K
Reoot (Q) (((VQK)
-log(0 + (3))))))))(//
log(3/6))
The proof is complete.
40


Reviews:
[{"review_id": "t822iisOUn", "reviewer": "Reviewer_73vR", "summary": "The paper presents two algorithms for active learning using neural network approximations, specifically designed for stream-based and pool-based scenarios. The goal of these algorithms is to address the challenges posed by the number of classes (K) in bandit-based approaches, such as performance degradation and increased computational costs.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is both intuitive and theoretically sound. It introduces a new exploitation network and exploration network that take the original instance as input and simultaneously output the predicted probabilities for K classes. This approach eliminates the need to transform the instance into DK long vectors. The paper provides theoretical performance guarantees, showing a slower error-growth rate as K increases. Furthermore, it demonstrates that the proposed algorithms achieve the optimal active learning rate under different noise conditions.", "weaknesses": "From a theoretical perspective, the core difference between existing methods that transform instances into DK long vectors is not clear.", "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": "FiCVE5RgRX", "reviewer": "Reviewer_5FNs", "summary": "This paper builds on prior work by Wang et al., 2021 on neural active-learning with performance guarantees. As in that work, the authors construct two neural networks -- an exploitation network and an exploration network which is trained to fit the residuals (noise) of the exploitation network -- and sum their outputs to estimate the expected loss of each class given the context.\n\nOn the applied side, what makes this work different from Wang et al.'s is that the neural proposed in this paper jointly predicts the expected losses for all actions (classes) simultaneously. Whereas Wang et al. apply their neural networks to a context+action vector for each class individually. This makes inference K times faster for the authors' new method, where K is the number of classes. Additionally, the inputs to the neural network are K times shorter than in Wang et al. because they don't need to use a kronecker product construction to encode the chosen action (class) on the input side. And the smaller dimensionality also makes everything more efficient.\n\nThe authors then propose and analyze two algorithms for active learning which both utilize the signal & noise trained neural networks. The first algorithm is for the stream-based setting in which one example arrives at a time and the learner can either can either request a label or not, and there is a budget imposed on how many labels can be requested. The second algorithm applies to the pool-based setting where a set of examples is presented at each instance and the learner can request a label for one example in the set. For both settings the authors aim to minimize the population cumulative regret, which is the regret of the true / out-of-sample model performance of the learned model accumulated over the course of learning, minus the same for the Bayes optimal classifier.\n\nOn the theory side, the authors utilize the neural tangent kernel framework to derive lower and upper bounds on the cumulative population regret for two regimes of Mammen-Tsybakov noise: the hard margin regime and the unrestricted regime. The derived bounds improve those of Wang et al., 2021 by a factor of as much as O(md) where \"m\" is the network width and \"d\" is the input dimensionality. The authors also provide regret and label complexity bounds for the case where a unique Bayes optimal classifier exists. All bounds depend on a quantity related to the underlying dimension of the neural tangent kernel and another quantity related to the data.\n\nFinally, the authors present experiments comparing their active learning algorithms (NeurOnAL-S and NeurOnAL-P) for the stream and pool-based settings on several UCI datasets and FashionMNist against other neural active learning methods. The methods they compare against are: I-NeurAL (Wang et al., 2021), ALPS, BADGE, ALBL, CoreSet, DynamicAL. NeurOnAL-S/P generally outperform all others in terms of both test accuracy and running time, making for compelling empirical results.", "questions": "For the pool-based setting, I am interested to know why the authors chose cumulative population regret as their subject of analysis rather than the simple regret? With pool based learning, one typically doesn't care about the performance of the intermediate models constructed during training, only the last model.\n\nI'm also curious about the use of the exploration and exploitation networks and why they are better able to model the signal and the noise. In particular, using the gradients of the exploitation network as inputs to the exploration network -- why does this work? Is there any theoretical explanation (not just intuition) that justifies how this helps fit the noise?\n\nFinally, I am trying to understand the statement in section 5 that\n\n          h(x_t)[k] = <Grad f(x_t, theta*)[k], theta* - theta1>.\n\nIs this an assumption or does such a theta* always exist? And if it always exists, is it the same theta* for all \"t\" and \"k\"?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The theoretical bounds for the proposed method are quite an improvement over those for the method presented in Wang et al. 2021. The empirical wins, both on increased test set accuracy and decreased running time, for the stream and pool-based settings also demonstrate siginificant improvement over multiple prior approaches.", "weaknesses": "One weakness of the proposed method is that it is demonstrated with a particular neural network structure (an MLP) and the authors do not state whether it can be used with arbitrary network structures, and if it can, then how the bounds might change (I realize this would be very difficult analysis). But some discussion around how general the approach is would make this paper much less niche/narrow.\n\nA related weakness is that the bounds are in terms of quantities (S and L_H) that are difficult for practitioners to quantify or trade off in order to find the network architecture for their problem.\n\nIn the experiments, I did not see stated which subsets of data were used to tune hyperparameters. One might therefore worry that hyperparameters were tuned to give good test performance.", "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": "WdVrtK2jWM", "reviewer": "Reviewer_Jpt8", "summary": "This paper studies active learning using newly designed exploration and exploitation neural networks. Instead of transforming the instance into $K$ arms and then calculating scores for them, they directly input the original instance into the network, hence avoiding the cost of $K$ time forward-propagation and dimension multiplication due to embedding. As a result, they present theoretical guarantees with a slower error-growth rate, concerning $K$. Besides, extensive simulation results are presented.", "questions": "- May I ask the reason behind limiting the experiments to five iterations? Was it influenced by computational constraints or other considerations?\n- What's the main difficulty of analyzing settings other than $\\alpha = 0$? What do the authors expect different levels of $\\alpha$ to influence the theoretical results intuitively?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "# Origionality\n- The idea of exploration-exploitation networks is not so novel but related works are covered in detail. It originates in [10] and is then adopted by [11], which is one of the works this paper is compared to. \n- The idea of reducing the dimension to $d$ is novel considering the literature starting from [10].\n# Quality\n- The theoretical proofs seem to be concrete. \n- The experiments are extensive and detailed. They validate the performance and computation efficiency claimed.\n# Clarity\n- The paper is in general well-written and smooth to follow, with the exception of some proofs in the supplementary material. \n# Significance\n- The proposed algorithms are of interest as the input is more coherent and the performance is great.", "weaknesses": "- The main originality seems to be theoretical proofs rather than network structures. However, the proofs heavily depend on NTK techniques. \n- The experiments were conducted only five times, which could potentially impact the reliability of the results. I would appreciate seeing outcomes derived from a greater number of runs. \n- The theoretical results are only for the setting where the Tsybakov noise $\\alpha = 0$, making it less comparable to existing literature, except when compared to [48] indirectly as $\\alpha \\rightarrow \\infty$.", "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": "6YveLMbsL1", "reviewer": "Reviewer_4Q6h", "summary": "The paper investigates active learning strategies using neural networks for both stream-based and pool-based scenarios. It addresses the challenge of mitigating the adverse impacts of the number of classes ($K$) on active learning performance. The authors propose two algorithms that incorporate neural networks for exploration and exploitation in active learning, providing theoretical performance guarantees. Experiments demonstrate that these algorithms consistently outperform existing baselines.", "questions": "Please refer to the above Weaknesses section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and easy to follow.\n\nThe paper studies an important and interesting problem of how to do active learning in two settings. The proposed algorithms based on exploitation-exploration NN have some novelty.\n\nI checked parts of the proof and feel they should be correct. While I am not familiar with this line of theoretical work, I would refer to other reviewers' opinions for evaluation.", "weaknesses": "I have no major concern on the current manuscript.\n\nOn minor issue: I feel it is better if the authors could explain how your work and the previous literature (e.g. bandit-based algorithms) decide whether to observe the label for each sample in detail. How your work is different from the existing literature on this problem?", "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)