One-shot Active Learning Based on Lewis Weight Sampling for Multiple Deep Models
Authors: Sheng-Jun Huang
Yi Li
Yiming Sun
Ying-Peng Tang
Venue: ICLR 2024 poster (2024)
Keywords: active learning
Lewis weight sampling
machine learning
deep learning
Primary area: general machine learning (i.e., none of the above)

Abstract: Active learning (AL) for multiple target models aims to reduce labeled data querying while effectively training multiple models concurrently. Existing AL algorithms often rely on iterative model training, which can be computationally expensive, particularly for deep models. In this paper, we propose a one-shot AL method to address this challenge, which performs all label queries without repeated model training. Specifically, we extract different representations of the same dataset using distinct network backbones, and actively learn the linear prediction layer on each representation via an $\ell_p$-regression formulation. The regression problems are solved approximately by 
sampling and reweighting the unlabeled instances based on their maximum Lewis weights across the representations. An upper bound on the number of samples needed is provided with a rigorous analysis for $p\in [1, +\infty)$. Experimental results on 11 benchmarks show that our one-shot approach achieves competitive performances with the state-of-the-art AL methods for multiple target models.

Published as a conference paper at ICLR 2024
ONE-SHOT ACTIVE LEARNING BASED ON LEWIS WEIGHT SAMPLING FOR MULTIPLE DEEP MODELS
Sheng-Jun Huang', Yi Li', Yiming Sun & Ying-Peng Tang
College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics' School of Physical and Mathematical Sciences, Nanyang Technological University² {huangsi, Langyp)&nuaa enu.en {yili, riming005Jentu.. edu.
ABSTRACT
Active learning (AL) for multiple target models aims to reduce labeled data query- ing while effectively training multiple models concurrently. Existing AL algo- rithms often rely on iterative model training, which can be computationally expen- sive, particularly for deep models. In this paper, we propose one-shot AL method to address this challenge, which performs all label queries without repeated model training. Specifically, we extract different representations of the same dataset us- ing distinet network backbones, and actively learn the linear prediction layer on each representation via an l, tp-regression formulation. The regression problems are solved approximately by sampling and reweighting the unlabeled instances based their maximum Lewis weights across the representations. An upper bound on the number of samples needed is provided with rigorous analysis for benchmarks show that our one-shot ap-
p [1, +oo). Experimental results proach achieves competitive performances with the state ofth-affth AL methods for multiple target models.
INTRODUCTION
The rapid advancements in deep learning have led to a substantial increase in demand for extensive labeled data points effectively train high-performance models. However, data labeling remains costly due to its reliance on human labor. To address this challenge, active learning (AL) (Settles, 2009; Ren al., 2021) has emerged an effective strategy for mitigating annotation expenses. This approach estimates the potential utility of different unlabeled instances in improving the per- formance of a target model and selectively queries the labels of the most beneficial instances from the oracle (i.e., an expert who can provide the ground-truth label). A typical practice of AL conducts label querying and model updating iteratively to exploit the insights from model decisions, i.e., se- lecting one small batch of instances based on the model predictions and updating the target model each iteration until the labeling budget is exhausted (Cohn et al., 1994; Huang et al., 2014). This paradigm has been widely applied in real-world scenarios (Hoi et al., 2008; Shi & Zhou, 2023).
Recently, there has been a significant surge in the demand for the deployment of machine learning systems diverse eesource-constraingg devices (Deng al., 2020; Gou et al., 2021; Menghani, 2023). For example, speech recognition and face recognition systems usually need to support var- ious types of machines with varying computing and memory resources. As result, the task of training multiple models with varying complexities using the same labeled dataset has arisen (Cai al., 2019), leading to a setting of AL where there are multiple target models be learned simultaneously (Tang & Huang, 2022).
Tang & Huang (2022) provide both theoretical and empirical evidence showcasing the potential of AL in alleviating the substantial data labeling burden associated with training multiple target models. They propose an iterative AL algorithm DIAM and validate its effectiveness for multiple deep models. However, the use of iterative AL methods results in a significant increase in model training cost. This due to the requirement of training multiple deep models at each query iteration. A potential solution is increasing the querying batch size of conventional batch-mode AL methods.
'll authors contributed equally this work. Ying-Peng Tang the corresponding author.

---

Published as a conference paper at ICLR 2024
Nevertheless, this may lead to redundant querying (Yang & Loog, 2019). A more cost-effective strategy could be one-shot or single-shot querying, which selects the required number of unlabeled instances and makes all label queries within one iteration devoid of re- re-training the models.
Most existing one-shot AL methods query a representative set of instances using the distance be- tween feature vectors (Yang & Loog, 2019; Viering et al., 2019; Jin et al., 2022; Shoham & Avron, 2023). However, this approach faces challenges when handling multiple deep models, as the same instance can exhibit different feature representations in different models. This phenomenon arises due to the intrinsic representation learning of deep models, where data representations are implicitly optimized during the training process and varied network architectures yield distinct embeddings. These embeddings may contain abundant information to facilitate data selection. However, such information has not been well exploited by existing one-shot AL methods. Therefore, they may not yield optimal performances in the setting of multiple models.
In this paper, we propose a one-shot AL method for multiple deep models, accompanied by a rigor- ous theoretical analysis. Our method is based on the fact that deep model can be viewed as linear prediction layer (i.e., multiple neuron models) and a nonlinear feature extractor (i.e., the network backbone). Therefore, training multiple deep models can be described as learning linear prediction layers from the outputs of distinct network backbones. In this way, active learning from diverse data representations can be formulated as optimizing shared sampling matrix to minimize the error of each linear predictor. To facilitate computing and analysis, we consider the learning of the pre- diction layer as an lp regression problem with p (0, +00). Notably, particular emphasis on the case of p = 2, i.e., the squared loss, which is one of the most commonly used loss functions in deep learning. Specifically, suppose that there are models and A' E Rnn (j - I, k) is the feature matrix obtained by feeding the dataset into the j-th network backbone. Let R + R be an L-Lipschitz function with f(0)
empirical studies place
Typical choices of f are activation functions such as ReLU, Sigmoid, and so on. We abuse the notation and apply f to vector E I" coordinatewise, i.e. l((v) = (f(w)).... ((,..,(((,.))) f(,,)))² Suppose that y² y'.... y E IR" are e label vectors and the task is to minimize the loss Σi=1 (1((0))))) y 1i over 01
A E Rd for all models j simultaneously. Since the construction of S is independent of yy .....y" y",
henceforth assume that e = 1, with a single label vector E IR". Therefore, we seek a shared reweighted sampling matrix S such that we can, from the labels of the sampled instances Sy, approximately solve the regression problem ming ( yll for all models j simultaneously.
The simplest case is when there a single model, i.c., 1. In this case, Gajjar al. (2023a) are the first to study the problem of actively learning a single neuron model. They cast the problem as a least-squares regression problem (i.e. p = 2) mine Il (AA) E1l and find an @ such that
(A - y1 s C. (A)) y + cLL (100)12).
where 0* arg ming ([A(A)) y/1 is the minimizer, C' an absolute constant and an accuracy parameter. Recall that L is the Lipschitz constant of f. Gajjar et al. (2023a) also show that the additive term <L''|AA0 [/2 is necessary. For k > and general p. we seek approximate solutions 0l....,. Og with the following error guarantee of a similar form on each individual model:
() U1l < C. (llf(A'')) yll + eL! ( (1p),
(1)
where 0 arg ming (A' -yl is the minimizer for model and C = C(p) > is constant depending only on p.
Gajjar et al. (2023a) construct S to be a leverage score sampling matrix and solve Ā = arg mingeg (S) Sylı with E = {0 ||AA0| < |Syll/(eL))). At the core of their argument lies the classical fact that such an S gives an Ez subspace embedding for A, i.c., ||SAA0] ||2 s ||A0||e for all 0 simultancously. In fact, it is not necessary to sample the rows of A according to the exact leverage scores (A).... Tn (A); any sampling probability propor- tional to l 2 T((A) for i-th row will suffice, with the number of samples being proportional to E, 4. This very fact motivates us to tackle the task of data selection from diverse representa- tions by sampling the rows according to the maximum of leverage scores across A''s, i.e., let- ting 4 ~ max, (A)))). Solving for each model j by Ø = arg minngeg ()) - Sy 1 with E = (0 ||SA000| < |Syll / (({l)) will then achieve (1) for = 2. This indicates that the queried instances are effective in learning each of the linear predictors, which fits our problem well. A potential caveat is that the number of samples needed will be proportional to
2

---

Published as a conference paper at ICLR 2024
E,t,~ max, (A²),, which could be as large kd. However, empirical studies show that this is not the case for real-world datasets (see Section 3.2) and our approach will thus be efficient.
For general p, instead of leverage scores, it is natural to consider Lewis weights, which can be seen as generalizations of leverage scores for general p (see Section 3.1 for the definition). It is known that an C, Lewis weight sampling matrix S give an lp subspace embedding. i.e., ||S.A0|pp = || lp for all 0 simultaneously (Cohen & Peng. 2015). The approach mentioned above extends to general p naturally, attaining (1) for general p. by sampling according to the maximum Lewis weights and solving an fp-regression problem for T with an e--version of E
Theoretical Results. For k 1, the latest result is to use O(d/c*) queries Gajjar et al. (2023b), with an analysis specific to p y= 2. We generalize the approach to the l, Lewis weight sampling for p 2 1 and extends it to k 2 1, giving the following theorem.
Theorem 1.1 (Informal version of Corollary 3.6). Let wi (A').... ...., Wn (A') denote the Lewis weights of A and T = max]e[M] w;(A') Suppose that T = poly(d). There exists a random- ized algorithm which samples
"T log d, (e-'T -10) log" dllo(d/e)
p=1 p and p
unlabeled instances and outpuss solutions 01 ..... @+ E TRd such that (1) holds for all j E [k] with probability at least 0.9.
Note that for single matrix A E Raxd, i the sum T == Ex (A( = d and so Theorem 1.1 implies a sample complexity of (ddmmx(p/211) /et), recovering the result in Gajjar et al. (2023b) for p = 2.
Empirical Findings. Extensive experiments are conducted on 11 classification and regression benchmarks with 50 distinct deep models. In Section 3.2, we empirically observe that the sum of the maximum leverage scores grows very slowly the number of models increases. This result reveals the strong correlation among the leverage scores of different deep representations, providing direction for interpreting deep representation learning (Kornblith et al., 2019; Nguyen al., 2020). In Section 4, we validate the effectiveness of our method with fine-tuning and vanilla learning sce- narios of deep models for both the lg-regression loss and cross-entropy loss. The results show that our method outperforms other one-shot baselines. Even when comparing with the state-of-the-an iterative AL methods for multiple models, our approach achieves competitive performance.
2 RELATED WORK
Active learning has been extensively studied in the past decades (Settles, 2009; Ren et al., 2021). With limited query budget, many methods try to query the labels of the most useful instances for a target model by designing effective selection criteria, which commonly depend on two notions, informativeness and representativeness. Informativeness-uue target model has highly uncertain prediction (Lewis & Gale, 1994; Yan & Huang, 2018; Kirsch et al., 2019), while representativenness bassed criteria prefer instances which can help reduce the distribution gap between the queried instances and the entire dataset (Dasgupta & Hsu, 2008; Chat- topadhyay et al., 2012; Sener & Savarese, 2018). While most existing methods focus on improving the performance of a specific target model, Tang Huang (2022) extend the setting of AL to mul- tiple target models. In this scenario, the active learner seeks to enhance the performance of every target model simultaneously by selective querying. Their work demonstrates that the query com- plexity of AL for multiple models can be upper bounded by that of an appropriately designed single model. Based on this insight, they propose an iterative algorithm called DIAM, which queries the labels of the instances located in the joint disagreement regions among multiple models. Although the method effective, a significant concern is the substantial cost incurred by training multiple deep models at each iteration.
criteria prefer instances where the
To reduce the computational cost of repetitive model training, one-shot AL algorithms have been proposed to query all useful instances in a single batch, thereby avoiding the need for model updates. Yang& & Loog (2019) employ existing AL methods with labudo-labeligg to obtain a candidate set of diverse instances, and select the queries based on the feature distance between unlabeled instances and candidate instances. Viering et al. (2019) select representative data points by the kernelized discrepancy methods, e.g., Maximum Mean Discrepancy (MMD) (Borgwardt et al., 2006), and give
3

---

Published as a conference paper at ICLR 2024
error bounds under different assumptions data distribution. Jin et al. (2022) propose one-shot AL method for deep image segmentation. Their approach uses self-supervised learning to obtain more informative representations and selects diverse instances based on clustering results and feature distances. In addition, Coreset (Sener & Savarese, 2018) and Transductive Experimental Design (Yu et al., 2006) are implicit one-shot AL methods. However, all the aforementioned one-shot AL. methods cannot handle the distinct representations of multiple deep models.
Although most existing AL methods rely on heuristics lacking theoretical analysis. AL with Lewis weight sampling has been well studied for active f--regression problems mine A0 yllp. where the matrix A E Raxd is fully accessible while the lahel vector y E IR" needs to be queried (Chen & Price. 2019; Chen & Derezinski, 2021; Parulckar et al., 2021: Chen et al., 2022: Musco al., 2022). Provable guarantees are obtained for -aprrxiapo solutions, i... || -yllp S (1++)]lAA0- Bllp. where O' is the output of the algorithm and 0* the true minimizer. For p 1, Parulekar et al. (2021) show that Ode-dd (o))d( samples suffice. For p = 2. Chen & Price (2019) solve the problem optimally with O(d/e) queries. For p E (1, 2), Chen & Derezinski (2021) propose the first algorithm to solve the problem with sublinear query complexity. i.c., O dd log d). For p 2, Musco et al. (2022) show that O log" d loog"=(d/e)) queries suffice. Recently, Gajjar al. (2023a) extend such sampling method to the single neuron model for p = 2. which inspires our work. They establish a multiplicative constant-facter error bound of the form (1) using (d?//c4) samples. This has been further improved to (dde*) in Gajjar et al. (2023b).
3 OUR APPROACH
3.1 PRELIMINARIES
Suppose that the dataset has n instances @ Onn and each a; has a ground-truth label y:- The given data consist of small labeled set L. = {(a,, vt) )= used for model initialization, and a large unlabeled set U = (Ra++ used for active querying. Here, n = nu + ny and it is assumed that ny < nu. A neural network can be viewed as the composition of a network backbone and a linear prediction layer O E Rdd composed by an activation function f(-). The prediction of the network is given by (AA), where A E Raxd is the feature matrix obtained by feeding the dataset into the network backbone. Denote by y E IR" the corresponding label vector that needs to be queried. In our theoretical analysis, we assume that d & n, A has full column rank, the network backbone is fixed during the learning of 0 and f is L-Lipschtiz continuous with ʃ(0) = 0.
Notation.
We always assume that p > O. The lp norm of a vector f is defined to be |0 = E> 0 P
where O, is the i-th coordinate of O. When p < 1, this is not norm, nevertheless, it remains well-defined quantity and we shall abuse the notation and denote by ||0||p 1p--
For matrix A, the operator norm of A is defined as || suPeER (0) || 2/ ||0|| For integer
2 1, we use [ni] to denote the set 21, ... nI.. and a St,4.... 6 if there exists a constant C' depending only on t1 t2.... such that a S cb. We also write ,2...... b if a St,, b and b St,,2.... a.
..... We write
#1 )b if (1 -)b < < (1 (1++)) e)b
Lewis Weights Sampling. We shall define the Lewis weights and state a classical result that Lewis weight sampling gives subspace embeddings, which is the starting point of our algorithm.
Definition 3.1 (lp Lewis Weights). Suppose that A E Radd and its i-th row is a, E Rd. The Lewis weights of A are W1,.... Wn such that w, = (a (A aa,) 8, where W is a diagonal matrix with diagonal elements W1, .2,..., Wp.
We remark that Lewis weights satisfy that (A) E 10 and Σ (A) d. When p 2, Lewis weights are exactly the leverage scores. Next, we define lp subspace embedding and sampling matrix. Then, we state the result that Lewis weight sampling gives subspace embeddings.
Definition 3.2 (Ep Subspace Embedding). Let E 1) be the distortion parameter. A matrix S E mx is said to be an Ep e-suuspace-embeddaee matrix for A E Ruxd if holds simultaneously for all vectors 0 E Rd that (1 (1-e) A0 < ||AA I, < (1 + A01|
Definition 3.3 (Sampling Matrix). Suppose that PI..... Pr. 2 0 such that p1 + P2 + ....... + P.. and e),-.. en are the standard basis vectors of IR= A matrix S E Rm is called reweighted
4

---

Published as a conference paper at ICLR 2024
sampling matrix if the rows of S are i.i.d copies of random vector X, where X (mp,) -/me
with probability Pj. = 1...., n. The number m of rows S is called the sample size.
Lemma 3.4 Coonsaant-factrr Subspace Embedding, (Cohen & Peng, 2015, Theorem 7.1)). Given A 1=dd Suppose that t, 2 Bwc all [m]. where
log d log 1
0 p<p<..p
B Z log
p 1,2
d "log + log
2 2<p< 00
sampling parameter. Let m Ei= li S S E R=x" is reweighted sampling matrix with sampling probability ps ta for all then is lp -subspuce-embeddingg matrix for A with probability at least - 5_
m
We note that our main theorem only requires constant-factie subspace embedding property of the sampling matrix S and, therefore, embeddings. The case of < 2 is proved by Cohen & Peng (2015) and the case of > 2 is originally due Bourgain al. (1989).
ignore the dependence in the bounds for lp subspace
3.2 AN EMPIRICAL OBSERVATION
Recall that the sample size maximum Lewis weight sampling proportional to Σ, max, (A'). We would like first to examine this sum across representations as it will determine the potential query savings. In the following empirical studies, we mainly consider the case of p = (i.e., squared loss), where the Lewis weight becomes exactly the leverage score.
We conduct experiments on 11 datasets. Due to the space limitation, the empirical settings, dataset specifications and more results are deferred to Appendix D. We report the results of MNIST, CIFAR- 100 and CelebA datasets below in Figure 1. We plot the theoretical upper bound and the exact values of the sum of the maximum leverage score of each instance across different representations.
The results show that the exact sum grows very slowly as the number of models increases in both classification and regression tasks. This suggests highly consistent discrimination power of most instances across different representations, as the leverage score measures how hard an instance can be linearly represented by others. Therefore, our algorithm is cost-effective. Leverage scores also provide a possible direction to interpret the behavior of deep representation learning, as prior works have discovered any simple form of correlation among the diverse representations obtained by different model architectures (Kornblith et al., 2019; Nguyen et al., 2020).
3.3 THE ALGORITHM
Based on our empirical observations, we propose to sample and reweight unlabeled instances based on their maximum Lewis weights across multiple representations. Specifically, given the feature matrices of the labeled and unlabeled instances (denoted by {LA} and {U>} } respectively), our algorithm begins with calculating the Lewis weights the unlabeled instances based on each of their feature representations. Next, normalized maximum Lewis weight among multiple represen- tations for each unlabeled instance is obtained:
maX wi (U
P
Tuu iml
maxjEld wu()))'
i i= 1,..., Bu-
moximmm
upper
pmn of moximum wwwragee xcon
upper
pmn moxtmum
40300
upper
4E000
40200
20000
20283
20200
20
20
20
45
number models
number models
number models
(a) MNIST
(b) CIFAR- 100
(c) CelebA
Figure 1: The trends of the sum of the maximum Lewis weights with = 2 among multiple repre-
sentations as the number deep models increases.
5

---

Published as a conference paper at ICLR 2024
Algorithm The Proposed Algorithm.
Input: Feature matrices of labeled and unlabeled instances L2,03 (j 1,..., k), query budget т.
Output: Trained linear models 0- ........ 0% Initialize: p. + zero vector of length nui Q an empty list; m 0
1: P: - maxi<isk w; (U3) for = ,,..., Ru
2: P; t P for -........ nh
3: while Q has fewer than distinct elements do
4: q gx<samp --mplee a number from [n.]] with replacement with probability Pi.... ......PP Pr...
5: m 4- 1- +1
6: append y to Q
7: if the label of q-th unlabeled instance is unknown then
8:
3g + query the label of q-th unlabeled instance
9: S zero matrix with shape (nu + m) (n4 n.)
10: S., + 1 for 1, ........7.
11: S1tm, 2:tn + (m . po.) po.) 1/p for 1,...,
12: y + ,
Un.. Ø7
for 1,... do
14:
AP
15: @
arg min ||Sf(A')) - -Syllp where E {= |SA011 (S
16: return 0
6
In the querying phase, we conduct i.i.d. sampling with replacement on the unlabeled set using a probability distribution p. The sampling process is repeated until distinct unlabeled instances sampled. Let Q denote the set of indices of unlabeled instances that are selected for label query. We reweight each of the instance with index E Q by (m p//_-// Finally, both the initially labeled instances with weight and the reweighted queried instances will be used update each of the target model. Note that, although Q may contain repeated entries, each instance will be queried only once and reoccurrences will not incur additional query cost. We present our algorithm in Algorithm 1.
3.4 THEORETICAL GUARANTEES
Our main result follows, which can be seen the guarantee for single model.
Theorem 3.5. Let p 0, f(0) be an L-Lipschitz function with f(0) 0, A E Raxd be the data matrix and y E g be the target vector. Consider a reweighted sampling matrix S with with row sampling probability Pt m.
is where l,,..., are some quantities and Ex4 44
Suppose that t1...., E satisfy that 142 2 (A), where
logl Ei= 14); B Zp ( 1-1.0) log" t.) p> and + 1.
p=
(2)
Then, if S is reweighted sampling matrix as described above and = arg minger [[ Syllp where E (0 || < ||Syll/((eTP)
holds with probability at least 0.9 that
(A0r - y1 < (AO") - -ull + +eL *LL||A00||!
where 0" = arg mine [I((A) -yl,, and C 0 a constant depending only on p.
The proof of Theorem 3.5 is deferred Appendix A. Our analysis also suggests that an subsspace embedding can be obtained using Ö(d/e²) samples, removing the log factor in (Woodruff & Ya- suda, 2023), which may be of independent interest. See Appendix B for discussions. Below we show the guarantee for multiple models, which follows easily as corollary of Theorem 3.5.
Corollary 3.6. Let .t,...,Ar An E Raxd be data matrices and T Ein maxjelK w,(A)). Let (() be L-Liscchitz function with f(0) 0 and R2 be the target vector. There exists algorithm that makes
(e-Allog(T/6
p p=1
m ~p (e 4Tamuxx 1100 log² d llog(dT/e).
(3)
p >> and p
1

---

Published as a conference paper at ICLR 2024
queries and outputs solutions 0- ..... 6t R such that (1) holds for all j E [k] with probability at least 0.9.
Proof. Let B max, (A') then for any fixed j. it holds that 4 2 Buor(A)). Also, m Σ,t, 3T. The sampling probability ps t//m max, (A')/T, which is exactly our sampling scheme in Algorithm Take
log d. d -1.0 log" d /log(dT/e), p> 0 and p +
p=1
then 3 satisfies the condition (2) in Theorem 3.5, whence the conclusion follows.
Remark. The proof of Corollary 3.6 implies the same guarantee for Algorithm 1 if T is set to be the quantity for m in (3). Indeed, the proof of Corollary 3.6 shows that the guarantee holds as soon as the variable in Algorithm reaches the desired amount in (3), which allows double counting of identical sampled rows; setting to be the same value will only result in a larger number m of samples and the guarantee will persist.
4 EXPERIMENT
In this section, we conduct experiments to validate the effectiveness of our method', Due to the space limitation, some empirical settings and experimental results are presented in the appendix.
Empirical Settings. We incorporate two learning scenarios in our experiments, i.e., fine-tuning and vanilla deep learning. The first one is a common learning scenario for big models. It first pre-trains the model on preliminary tasks. Then, the weights of the network backbone are fixed, and only the prediction heads are fine-tuned on downstream tasks. This setting aligns well with our problem formulation. The second scenario the default learning scheme, i.e., updating all the parameters of the network with the training dataset.
We employ 50 distinct network architectures as the target models. These architectures are published by recent NAS method OFA (Cai al., 2019) for accommodating diverse resource-constraint devices, ranging from NVIDIA Tesla V100 GPU to mobile devices. aligns well with our problem setting. We conduct experiments on 11 datasets, including classification benchmarks: MNIST (LeCun et al., 1998), Fashion-MNIST (Xiao et al., 2017), Kuzushiji-MNIST (Clanuwat et al., 2018), SVHN (Netzer et al., 201 1), EMNIST-letters and EMNIST-digits (Cohen al., 2017), CIFAR-10 10 and CIFAR- 100 (Krizhevsky, 2009); and 3 regression benchmarks: Biwi (Fanelli et al., 2013), FLD (Sun et al., 2013) and CelebA (Liu al.. 2015). The specifications of the datasets and model configurations are deferred to the Appendix E. The active learning settings are outlined as follows.
For the scenario of vanilla deep learning, we conduct performance comparisons on the classi- fication benchmarks. Specifically, 3000 instances are sampled uniformly from the training set to initialize the models. The other compared methods will then select 3000 unlabeled instances from the remaining data points for querying at each iteration, while our method conducts one- shot querying with budgets of 9000 and 15000 instances. The cross-entropy loss employed in model training. In this scenario, the one-shot methods also query 3000 instances per batch for better comparison. However, these methods select batches independently.
For the fine-tuning scenario, uniformly from the training set to fine-tune each network. Then, we fix the backbone parameters and actively query the labels among the remaining instances. Afterwards, 50 linear prediction layers with mean squared error (MSE) loss and ReLU activation function are trained on the updated labeled dataset, utilizing the features extracted by different network backbones. this scenario, all the compared methods have the same query budgets of 3000 and 6000 instances.
use the regression datasets. Initially, 500 instances are sampled
We compare our algorithm with the following methods in the vanilla deep learning scenario.
(iterative) DIAM (Tang & Huang, 2022): The state-of-the-art iterative AL method for multiple target models, which prefers the instances in the joint disagreement regions of multiple models.
'll experiments conducted on machine with four GeForce RTX 3090 graphic cards and an Intel Xcon Gold 5317 CPU. The source code is included in the supplementary material for experiment reproducibility.

---

Published as a conference paper at ICLR 2024
200 SCCATT 22V
4003 100a 1363
80:00
2003
400
R000
100
4000
15.00
(a) MNIST
(b) Kuzushij-MNNST
(c) Fashion-MNIST
(d) SVHN
maan eouurecy
HOST accurcc
number of Queris
number zuer
Furbect qucfiic
number quetics
(e) CIFAR-10
(f) CIFAR- 117AR-100 100
(g) EMNIST-letters
(h) EMNIST-digits
Figure 2: Results of Performance comparison in classification datasets. The error bars indicate the standard deviation of the performances of multiple models.
(iterative) Entropy (Lew is & Catlett, 1994): This strategy selects instances with the highest pre- diction entropy. We follow the implementation in (Tang & Huang, 2022) to adapt it to multiple models. It queries the instances with the highest mean prediction entropy.
(iterative) QBC (Seung al., 1992): This strategy selects the instances that the target models have the most inconsistent predictions. The inconsistency is evaluated by KL divergence. (one-shot) Coreset (Sener & Savarese, 2018): This strategy selects the most representative in- stances. We follow the implementation in (Tang & Huang, 2022) to adapt it to multiple models. It solves the coreset problem based the features extracted by the supernet in OFA. (one-shot) Random: This strategy selects instances uniformly from the unlabeled pool.
In the fine-tuning scenario, fewer existing methods available. Specifically, compare algorithm with Coreset, Random and QBC methods. Although QBC is usually implemented in an iterative fashion, employ large query batch size for it unify the query settings.
Our method selects and reweights the unlabeled instances based on the leverage scores (i.e., 2) in both scenarios. Note that, in the fine-tuning scenario, implementations remove the constraint E' in Line 15 in Algorithm for better examination of the practicability. In the vanilla deep learning scenario,
the default training scheme of deep models replace Line 15 in Algorithm The mean accuracy and the mean MSE are used to evaluate the performances of multiple target models for classification and regression tasks, respectively.
Experiment Results. We report the performance comparison results in Figure 2 and Figure 3. In the scenario of vanilla deep learning, we can observe that our one-shot method achieves comparable performances with the other iterative AI. methods in most cases. This phenomenon indicates that our method can significantly reduce the costs of training multiple deep model while preserving its proficiency in the ability of query saving. QBC is the worst one. We find that it causes severe class imbalance according to the results in Table 5 in appendix. This may explain its inferior performances. Coreset is usually worse than Random. Note that, the problem settings of Sener & Savarese (2018) and our work are different. there are 50 distinct target networks to be learned in
Table 1: Comparisons on the running time between our method and the other baselines with query budget 15000 instances. The running time includes data querying and model training (GPU hours).
MNIST
F.MNIT
K.MNNITT
SVHN
CIF.10
CIF.100
EMN.I.
EMN.d d.
DIAM QBC
46.643
47.597
46.765
52.228
45,493
53.532
73.522
120.840
23.937
24.419
24.502
26.011
25.541
30.498
36.280
40.231
Entropy
24.060
24.293
24.455
25.792
25.173
28.655
34.291
42.719
Our 5,299
5,366
5.354
5,605
5.350
5.57
9.717
12.711
Coreset
5,200
5.201
5.285
5,466
5.450
5,745
8.984
11.043
Random
4.317
4.333
4.402
4.583
4.567
4.712
7.317
8.027
8

---

Published as a conference paper at ICLR 2024
DRC
Cuasd
2006
Racker
0.70
210
MS5
6.364
6624
CDE
6692
6455
0:750
meithods
methods
methods
(a) Biwi (3000 instances)
(b) FLD (3000 instances)
(c)
CelebA (3000 instances)
8:750
0.00-
M5G
6650-
MEE
6004
6:354
CMI
6492
6646
2.80
3046
0.00
201a
6:350
methods
methods
methods
(d) Biwi (6000 instances)
(e) FLD (6000 instances)
(f) CelebA (6000 instances)
Figure 3: Results of performance comparisons in regression datasets with different query budgets.
our experiment. The Coreset implementation of Tang & Huang (2022) solves the coreset problem based on the features extracted by the supernet. A drawback of this approach is that the selected instances may not be usefuul for other models, because the data representations are different. We believe this the reason that why Coreset is less effective than Random in our setting. Entropy method achieves comparable performances with Random. The reason may also be evidenced by the results in Table in the appendix that their class imbalance ratios are highly consistent, implies that the mean entropy scores tend to have an extremely small standard deviation. The performances of DIAM are less stable. It is effective in the datasets associated with MNIST, but fails on the others. This deficiency has not been observed in method.
In the scenario of fine-tuning, Figure shows that our approach outperforms than the other baselines with different querying budgets in terms of achieving better mean MSE. These results indicate that our method is effective and robust to different query budgets, it can effectively identify the desired number of useful unlabeled instances under diverse representations to learn linear prediction layers.
We further examine the running time of different AL methods. The results are reported in Table 1. For the one-shot methods Coreset and Random, we report their running time of one-shot querying 15000 instances. It can be observed that the cost of repeated model training is prohibitive AL. for multiple deep models, demonstrating the advantages of one-shot querying. Among the active selec- tion methods, DIAM is the slowest approach because it selects instances based on the predictions of the unlabeled dataset in the latter half of training epochs of each target model. Generating the predictions from multiple models could be expensive, particularly with large unlabeled pool. QBC and Entropy exhibit similar time costs. Both of them need feed the unlabeled instances into 50 models to obtain their predictions.
In the fine-tuning scenario, all the compared methods conduct one-shot querying and linear pre- diction layers are trained with the same computational costs. As result, the running time of the compared methods is comparable. The results are deferred to Table the appendix.
5 CONCLUSION
In this paper, we propose a one-shot AL algorithm for multiple deep models. The task is formulated as seeking a shared reweighted sampling matrix approximately solve multiple fp-regression prob- lems for neuron models on distinct deep representations. Our approach is to sample and reweight the unlabeled instances based on their maximum Lewis weights across different representations. We establish an upper bound on the number of samples needed by our algorithm to achieve constant- factor approximations for multiple models and general p. Our techniques on the one hand substan- tially improve the upper bound on the number of samples of (Gajjar et al., 2023a) in the case of single model and = 2, on the other hand remove the log factor in (Woodruff & Yasuda, 2023) for Lewis weight sampling to obtain jy-subspace-embeeddin on 11 benchmarks and 50 deep models. We observe that the sum of the maximum Lewis weights with p grows very slowly the number of target models increases, providing direction for interpreting deep representation learning. The performance comparisons show that our algorithm achieves competitive performances with the otate-of-the-art AL. methods for multiple deep models.
Extensive experiments are conducted

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
S.-J. Huang is supported in part by the National Science and Technology Major Project (2020AAA0107000), the Natural Science Foundation of Jiangsu Province of China (BK20222012, BK2021 1517), and NSFC (62222605). Y. Li is supported in part by the Singapore Ministry of Ed- ucation (AcRF) Tier grant 200--22P22112-0000 and Tier grant RG75/21. Y.-P. Tang was supported in part by the China Scholarship Council during his visit to Nanyang Technological Uni- versity, where most of this work was done.
REFERENCES
Karsten M. Borgwardt, Arthur Gretton, Malte J. Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alexander J. Smola. Integrating structured biological data by kernel maximum mean dis- crepancy. In Proceedings of the 14th Annual International Conference on Intelligent Systems for Molecular Biology, pp. 49-57, 2006.
J. Bourgain, J. Lindenstrauss, and V. Milman. Approximation of zonoids by zonotopes. Acta Math- ematica, 162:73 - 141, 1989. doi: 10.1007/BBF2239233. URL
D007/BF023928
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In Proceedings of the 7th International Con- ference on Learning Representations, 2019.
Rita Chattopadhyay, Zheng Wang, Wei Fan, Ian Davidson, Sethuraman Panchanathan, and Jieping Ye. Batch mode active sampling based on marginal probability distribution matching. In Pro- ceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 741-749, 2012.
Cheng Chen, Yi Li, and Yiming Sun. Online active regression. In Proceedings the 39th Interna- tional Conference on Machine Learning, pp. 3320-330000 3335. PMLR, 2022.
Xue Chen and Michal Derezinski. Query complexity of least absolute deviation regression via robust uniforn convergence. In Proceedings of the 34th Anmual Conference on Learning Theory, pp. 1144-11777 119.. PMLR, 2021.
Xue Chen and Eric Price. Active regression via linear-sample sparsification. In Proceedings of the 32nd Annual Conference Learning Theory, pp. 663-695. PMLR, 2019.
Tarin Clanuwat, Mikel Bober- Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature. arXiv cs.CVV/812..1718. 2018.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik. EMNIST: an extension of MNIST to handwritten letters. arXiv es. N.CCV//1702.00373 2017.
Michael B Cohen and Richard Peng. Lp row sampling by Lewis weights. Proceedings of the 47th Annual ACM Symposium on Theory of Computing, pp. 183-192, 2015.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning. 15(2):201-2211 1994.
Sanjoy Dasgupta and Daniel Hsu. Hierarchical sampling for active learning. In Proceedings of the 25th International conference Machine learning, pp. 208-215, 2008
Lei Deng, Guoqi Li, Song Han, Luping Shi, and Yuan Xie. Model compression and hardware acceleration for neural networks: A comprehensive survey. Proceedings of the IEEE, 108(4): 485-532, 2020.
Gabriele Fanelli, Matthias Dantone, Juergen Gall, Andrea Fossati, and Luc Van Gool. Random forests for real time 3d face analysis. International journal of computer vision, 101:437-458, 2013.
10

---

Published as a conference paper at ICLR 2024
Aarshvi Gajjar, Christopher Musco, and Chinmay Hegde. Active learning for single neuron models with lipschitz non-lincarities. In Procedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 4101-4113. PMLR, 2023a.
Aarshvi Gajjar, Xingyu Xu, Chinmay Hegde, and Christopher Musco. Improved bounds for agnostic active learning of single index models. In RealML Workshop NeurIPS, 2023b.
Jianping Gou, Baosheng Yu, Stephen Maybank, and Dacheng Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 1291178918199 2021.
Steven C. H. Hoi, Rong Jin, Jianke Zhu, and Michael R. Lyu. Semi- semi-supprvised SVM batch mode active learning for imgge retrieval. In Proceedings of the 21st IEEE Conference on Computer Vision and Pattern Recognition, 2008
Sheng-Jun Huang, Rong Jin, and Zhi-Hua Zhou. Active learning by querying informative and representative examples. IEEE Transactions on pattern analysis and machine intelligence, 36 (10):1936-1999) 2014.
Qiuye Jin, Mingzhi Yuan, Qin Qiao, and Zhijian Song. One-shot active learning for image segmen- tation via contrastive learning and diversity-based sampling. Knowledge-Batd Based Systems, 241: 108278, 2022.
Andreas Kirsch, Joost van Amersfoort, and Yarin Gal. Batchbald: Efficient and diverse batch ac- quisition for deep bayesian active learning. In Proceedings of the 33rd Conference on Neural Information Processing Systems, pp. 7026-7037, 2019.
Simon Kornblith, Mohammad Norouzi, Honglak Lee, and Geoffrey Hinton. Similarity of neural network representations revisited. In Proceedings of the 36th International conference on machine learning, pp. 3519-3529. PMLR, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2324 1998.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 1991.
David D Lew is and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine Learning: Proceedings of the 11th International Conference, pp. 148-156. Elsevier, 1994.
David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. In W. Bruce Croft and C. van Rijshergen (eds.), Proceedings of the 17th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, pp. 3-12. ACM/Springer, 1994.
Ziwei Liu, Ping Luo. Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In 2015 IEEE International Conference on Computer Vision, 2015.
Gaurav Menghani. Efficient deep learning: A survey on making deep learning models smaller, faster, and better. ACM Computing Surveys, 55(12):1-37, 2023.
Cameron Musco, Christopher Musco, David P Woodruff, and Taisuke Yasuda. Active linear gression for E, norms and beyond. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, pp. 744-753. IEEE, 2022.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. In NIPS 20/ Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Thao Nguyen, Maithra Raghu, and Simon Kornblith. Do wide and deep networks learn the same things? uncovering how neural network representations vary with width and depth. In Proceed- ings of the 8th International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2024
Aditya Parulekar, Advait Parulekar, and Eric Price. LI regression with lewis weights subsampling. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2021.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang. A survey of deep active learning. ACM computing surveys, 54(9):1-40, 2021.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. In Proceedings of the 6th International Conference on Learning Representations, 2018.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madison, 2009.
H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In Proceedings of the 5th annual workshop Computationnal learning theory, pp. 287-294, 1992.
Haochen Shi and Hui Zhou. Deep active sampling with self-supervised learning. Frontiers of Computer Science, 17(4):174233, 2023.
Neta Shoham and Haim Avron. Experimental design for overparameterized learning with appli- cation to single shot deep active learning. IEEE Transactions Pattern Analysis and Machine Intelligence, 2023.
Yi Sun, Xiaogang Wang, and Xiaoou Tang. Deep convolutional network cascade for facial point detection. In Proceedings the 26th IEEE Conference on Computer Vision and Pattern Recog- nition, pp. 3476-3483, 2013.
Ying-Peng Tang and Sheng-Jun Huang. Active learning for multiple target models. In Proceedings of the 36th Conference Neural Information Processing Systems, 2022.
Roman Vershynin. High-Dimenssioal Probability: An Introduction with Applications in Data Sci- ence, volume 47. Cambridge University Press, 2018.
Tom Viering, Jesse H Krijthe, and Marco Loog. Nuclear discrepancy for single-shot batch active learning. Machine Learning, 108(8-9):156111559 2019.
David P Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 Anmual ACM-SIAM Symposium on Discrete Algorithms, pp. 4622 4666. SIAM, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist a novel image datasct for benchmark- ing machine learning algorithms. arXiv 1t.LL//700.0077777 2017.
Yifan Yan and Sheng- Jun Huang. Cost-effective active learning for hierarchical multi-labed classi- fication. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2962-2968, 2018
Yazhou Yang and Marco Loog. Single shot active learning using pseudo annotators. Pattern Recog- nition, 89:22-31 31, 2019.
Kai Yu, Jinbo Bi, and Volker Tresp. Active learning via transductive experimental design. In Proceedings of the 23rd International conference Machine learning, pp. 1081-1088, 2006.
A PROOF OF THEOREM 3.5
We first need a simple inequality.
Fact A.1. Suppose that a, b and p > It holds that (a+by) + byd < 2)0-11(aP + PP).
Let OPT - -ming ||A0
y/lp- Theorem 3.5 is proved by the following chain of inequalities. p (A)
[(Aθ) y
< 21p-1 <|| ([|(())) - f(A00) I" OPT?)
(B)
x 2|v 2210-11 (S(AA) SF(AA>)|" + +2IRR*
12

---

Published as a conference paper at ICLR 2024
(C)
3 2 22011122--1|||(S(AA ST(A)) -wy( C,OPT + LRR
(D)
K 2 [O2 (OPT" + cLP [|A0*1]) - C1OPT + 2DR
C(OPT cL ||001
where incqualities (A) and (C) use Fact A.I, inequality (D) uses (Gajjar et al., 2023a, Claim 1).
Inequality (E) follows from that
R == max(] A0" A0 IPP)
S
A0
|
+ ||00||"
(EA)
P
-
2 SA0
+
||
(EB) 2
|
||
<LP
(BC)
I 100
||0
cLP
(ED)
< 100 2 [If(AA0) - =11 + -PP 11
+ 11A0001
CTP
100 2 p-11 [[{(A))) v1l
1000 (100-22
210-21m-11
+1 ||A0011 Ip:
eLP
where inequality (EA) holds because S is a subspace embedding matrix for A, inequality (EB) is from the constraint our approximate solution Line 16, inequality (EC) holds with probability at least 49/50 by Markov's 's incquality and inequality (ED) follows from Fact A.I.
We shall prove inequality (B) in the following lemma. We note that the following lemma proved in (Gajjar al., 2023a, Lemmata and 3), but their sampling complexity is O(d//e)) with an additional d factor compared with ours. We improve their result by using the reduction technique and removing the e-net argument.
Lemma A.2. Suppose that E Raxd and tn....,t E R. such that t; 2 (wx((A for all i and p 1. Let Exte 4 and S E RRxx be reweighted sampling matrix of with row sampling probabilities p1...., Pni where pt 4.11 If
d
1
3Z
logg d log m + log
2²
then with probability at least 1 and fixed constant R > 0, it holds for all pairs of vectors 01, O2 Rd with ||0 Ilp & R and A 11 < R that
|Sf(AO)) (f((A2)) | [If(A0) f(A02) + tel
Proof. Let [(A0)) f(A02) and y AO A02. Denote T to be the set B(R) B(R) 02) ||SAA|l1, S R, S|0021 R). We shall try to upper bound
E
max (0, O,)TT
|| 12 ||>||||
for L = llo-=oog g.
Since taking the f-th moment of the maximum is convex function and E ||Sx>] symmetrization trick yields that
||> 1bp
the
L0t 1 To mpss
E max
|||50| -|
2 E
max (01.02)E7
(..T.)ET
where T3's 's are Rademacher variables.
It follows from Lemma 3.4 that S is a } -usbsppace embedding matrix of A with probability at least 1 1-8 8/2. Furthermore, by Lemma A.4, with probability at least - 8/2, the Lewis weights of SAA is upper bounded by 1 Let & denote the event on S that the above two conditions hold. Then Pr(E) 2 1 8. We assume the following proof is conditioned on E.
13

---

Published as a conference paper at ICLR 2024
Next, we prove the conditional expectation over S and when conditioned & satisfies that = ( (IIRR))
)1
W
1
E
max E2T
Tk
(4)
S,a
(0,
mpix
Once (4) established, would follow Markov's inequality that
Pr
max (TT
|| ||>||| l| 2 EL g
Es, [max (0) ||| - ||>=1131)* [
(cL*RR)e
el 1) lapp
BsS
ma Ek= ah mpii
3
2 2
(eLPRR)e
$ 2
(by (4))
(PLE
6.
and then a union bound that
|| | 2 eTP RTPR 8 < <20,
Pr max EE)
(0,
which would complete the proof after rescaling ō to 8/2.
Now we focus on the proof of (4), which mostly follows the same approach of Theorem 15.13 in Ledoux & Talagrand (1991).
Let
f(a 01) f(a 02)
a 01
a. O2
k E [m].
UR
(mpi, 3/PP
(mpir
1/p
Then u = Sx and x = Sy. We also denote
A
max 0.)ET
Fxl axlu4
so (4) can be rewritten
E [ (5UP))
5,0
We shall split the sum in A into two parts: large Lewis weights and small Lewis weights. Specif- ically, we define A wy (SA)/d be the reweighted Lewis weight of SA and J {k [m] A
m
First consider those coordinates not in (small Lewis weights).
2 S LP Σ AulA ux S max LPR",
max (0T.0))T
Σ
ok
oxluR
Σ
Ri
kdJ
where the last inequality follows from the fact (see (Ledoux & Talagrand, 1991, Lemma 15.17)) that
| ukl I m 1
max k
(5)
and (by the definition of B(R)) that | p < 2R.
Next we consider the coordinates in (large Lewis weights). We have
Σ AeOu "uu
max E2)
max (0, 02)ET
REJ
REJ
Σ kej
d3 (2)0T
14

---

Published as a conference paper at ICLR 2024
where the second line follows from the fact that reweighted Lewis weights of SA are upper bounded by dØ By the triangle inequality, we have
E 18]
2 muax((1 (1, 3) IP
+
1
E
max (0,.0s)ET
Σ
pup u/ P &
d3
KEJ
2
mm 1 RD
I
m
d3
0
where
==
max E2T
Σ KEJ
VAROKAA uu
To bound E, [E] we introduce the associated distance 5( 02), (0) (()) so that it is enough to bound by the estimated entropy of B(H).. We define the distance to be 8 (², 02), (0,, 02))
A $
U(a -
02))
\ * 01) - M(a 05)1
12
=EN AM KEJ
(6)
m&ii
mp
Σ
Ax "uol"" - 1xx 22/1
REJ
and the norm
A P aaa
0
||0||] == max kej
(mps.) )
By the tail bound of Dudley's integral (see e.g. (Vershynin, 2018, Theorem 8.1.6), it holds that
E ((T, de + 2- diam (T) & s exp(-=2).
According to Lemma A.3, it holds that
{ (log ((B()) B,, E)) de. For 2, the entropy estimate in (Ledoux & Talagrand, 1991, Proposition 15.18) gives that - L"R"
(log (T, E)) S d_nux LPR
L (log (BB(), B,, e))
d
- LRR-- I/ (log (BB(), B,, - R 1)) t
(C (dlog 1+ RVd R
))
$/2
de + (
2nd R2 (
1
S d PR
( d
de
S d I Rp log Vlogm.
For 1 < < < 2, it follows from the entropy estimate in (Ledoux & Talagrand, 1991, Proposition 15.19) and similar argument to that for p 2 2 that
1o (log N(T 8, de S d L' log d //lomm m.
By the property of subgaussian variables (see egg. (Chen et al., 2022, Proposition 4.12)), we have E [ < K¹ ('EEmaaax (1 LP P + max(( f 1 R2 log d m))
Hence, given (18), as long as 3 > 20+1e E 2 K2 maxl 4 1.00 (log( (log(1/8) 1/8) - log d log m). follows that
E[A-1E] < 22
2p mma I. RD)
1
+
d3
15

---

Published as a conference paper at ICLR 2024
2
L' 1P
Kdttaxt v. :)) L (ve +
log lo/ m)
+
d3
vd3
IPPR
+ (EL
(1g(1/6) + log' d'logm) (c..
Therefore, taking expectation over S while conditioned on E, we have that Es [A98] C Rescaling E c/2 completes the proof of (4), as desired.
Lemma A.3. Let 6((0), 02), 02)) and |10|| be as defined in (6) and (7), respectively, It holds that
d - 0111, | + 10: 02113)
2 2, 1 1 p S 2.
02)) 2
IPR - -611, + |00- - 0211,)
Hence (T), the diameter of the subspace T, at most O +
Proof. For p 2 2, we have
((0,, 02), (2),
(A)
5
\ uu - -xe F2 211
? pux 1-
1
+ 12
10-12
KEJ
2
A (a 0 -0 01) + Xx (a. 02 a.. (1]
(B)
p Σ A/ 3
(mpir.)
KEJ
Axx 2x 2---2 + 12 "20
1202 20-2
A (a 01 aT
Xx (aa 02 a., 022)
(C)
S 2p 1 2 22 RP-2
pd
A
(mps)))
KEJ
A ux 1 + 1 o
(D)
< 20 1 2--1ppp "pd" p-2
2 p2 (1(0 - 0111, + 110 -b11,) Σ A "oxl" + +1 3 pp
kEJ
(E)
2 22p pd L 2 (10) 0 || + 00 - 00
where the inequality (A) follows from lal2- [6|2 S p(la|=11 1 + |b| - b/. (B) follows from triangle inequality and (a + 6)2 < 2(a² + 62). (C) follows from (5) and (E) is obtained by ||ul|p V ||S [|p + ||SA02llp < 2R.
For < < 2, we have
8² ((01, 02), (0' 02))
$ "unl"
A A
ukk X Pu
((1
+ 1x "ul!" 1-12
KEJ
$ max
|>g u/ Ax= up Σ
Aa 1
uu Ax #/ul 2 2 (12
# uu 2p-2 + 1 - 21/1 22
kEj
kEJ
< [P
11 |1, + 100 0²
A Pe Nx ))())) zيع
REJ
do > uu 1) +
Ael2g 2 2 20-2
KEJ
16

---

Published as a conference paper at ICLR 2024
& [1 fill, + 100 02
del "xll + >xl22 P2p z
NEJ
dkl2g ukk ux
3
A u 10)
20 2012
kEJ
KEJ
< 2,2 - 111 + ||02 - 021ls)P,
where we use Hölder's inequality Ilfglla I Ilf with a 2-p line.
P
and B = 2p-2 in the third
For p 2 2, the diameter of T is upper bounded by
(0, E. (0, 6((01. 02).(((,, 02))
max
- 2 3p-1 pd L (100 0ills + 1102 - 0,1,)
s 2 _ pd L'R"
where we use the fact that |0] 0i s 3 R from (5). For s 2, the diameter of 7 is upper
bounded by L (1 li + ||0- - - = dà LPR RD where we obtain ||0 - 0111, - db R from (5).
Lemma A.4. Suppose that A E Raxd and tn E I. such that t, Bw,(A) for all i. Let
m = E, and E mg be a reweighted sampling matrix of with row sampling probabilities
pr,-.. Pas where = 4. m B 2 e -2 log a/4 then the Eg Lewis weights of SA are upper bounded
by with probability at least 1 -
Proof. Let a, E Rax1 be the i-th row of Without loss of generality, suppose W1- Ia- = a. a, ||. We claim that (1-1-AA)--- A)-
Hence, the Lewis weights of A are a (A W1-
a₁ bE Wie
T
1-3
(1 - e) 1
1 31 (1+
mipi
1=1
Bi 1
1-
holds with probability at least 1 8. Let Xx
win
and then we have E EXg Ir- First,
Pic
|l,,, 11
1-
we have E Xx = la and Xr - Iall2 5 1 +
wigld Wic
+ 3 Besides, we have that
|E (Xa 14)112 = || - -aa) (Xx - Laill2
|E Xx Iall2
ai a T
Wig.
Wix
La
Piv
Pin
2
n
Wiig
1-2/2 +
a:a! Wii
Pi
i=1
2
m
<
1 +
3
By matrix Chernoff bound, it follows that
- -mc2
Pr
(X+
Ia)
2
2
< ed
1+d+ (1+ d) ee/3
km
2dexp (-3e?)
Setting 8 ( log ) guarantees the failure probability to be most 6, proving the claim. Therefore, we have that
d 1 #
d 1-
(1-)
Ia 1
Σ
ain (mpr))
Win dpiz
3 (1 + 26)
Ia
}
(mpry)
m
17

---

Published as a conference paper at ICLR 2024
holds with probability at least - 6. Hence, it follows that
a:
Oii
dpss
ik
(mpx) S (1 2c)
d
Wiz dpis.
2/p
(mpi)
(mpr))
Wik
(mpi,)
m
Applying (Chen et al., 2022, Lemma A.2) and setting gives that w; (SA) S dp;
Lemma A.5. Ler pr > and p * 1. Suppose that A Rnxd and w, < 1/3 for all i and 3 > 1. Let A = =a 51 x= oz o:l(Ax):lbb where 01,..., on are independent Rademacher
variables. Then the following tail bound holds:
d --,00
Pr
A
[log d +2] S <2exp(-2*).
3
Proof. The tail bound is proven by Dudley's 's integral tail bound
{ sup X₁ ~ LET
Pr
NI, d, e)de + diam(T) < 2 2xxp(=>²),
where N(T, d, e) is the e-covering number of T and diam(T) is the diameter of the space T. In our setting. T is the subspace {v = =Ax : x E Rd). From (Ledoux & Talagrand, 1991, Equa- tion (15.17) and (15.18)), the diameter is bounded by d By Dudley's 's integral, we have E, $ Jo /In N(T, d, e)dc. The upper bound of the integral was proven in (Ledoux & Tala- grand, 1991, Theorem 15.13). assuming that (:(A) < d/n. The same proof can go through when the upper bound of wx(() s 1/3, with (Ledoux Talagrand, 1991, (15.17)) replaced with
3d nax
2
EA <
+
E,
2n
d3
where
E
E
sup
Σ
Wi
|.,11''
d
W
F
Am
21
iEJ
In the proof of Ledoux & Talagrand (1991), X; is our //
and the factor M is replaced with 1 due d
the change of Lewis weights upper bound from m2
AT to
The main difficulty is upper bound E, which is again done by using Dudley's integral. The argu- ment to upper bound the integral in (Ledoux& & Talagrand, 1991, Theorem 15.13 still goes through when the upper bound of Lewis weights is changed, yielding that E < Ca log d /lol n. Combining the diameter of T and the inequality for A gives us the result.
B SUBSPACE EMBEDDING
We note that there are mainly two kinds of Ep Lewis weight sampling. The first kind is to retain or discard each row independently. Specifically, the i-th row of A is retained with probability pt and discarded with probability 1 Pt- The resulting sampled matrix SAA has a random number of rows. The second kind has fixed, prescribed number m of sampled rows. Each sample i.i.d. chosen to be the i-th row of A with probability t./m, where f1, t, are weights satisfying that Σ, t, m. We use sampling of the second kind (recall Definition 3.3) in our algorithm. However, our main result (Theorem 3.5) still works for the first kind of sampling matrices, see Appendix C for details.
In this section, we give the sample complexity for l, subspace embedding with distortion + e for p > 2, using both kinds of sampling schemes.
For p > 2, Woodruff & Yasuda (2023) consider the first kind of sampling and give a sample com- plexity of 0 d (log" d'log n + log })) for fp-subspace sesuubppace-mmbeddnngg
This the first result for p > 2 that has an e dependence, as the only prior result was O( -5/0/2 log d) with an - depen- improve
dence (Bourgain et al., 1989). Still, based on the result of Bourgain et al. (1989),
18

---

Published as a conference paper at ICLR 2024
the analysis of Woodruff & Yasuda (2023) and remove the undesired log factor in their sample complexity. We have the following theorem.
Theorem B.1. Let A E Ruxd 2 < < xc and 0 < e, < 1. Let P; = min 13 where is
Pp Lewis weight of a, for A and B s2( s(d2 (log d + log 21) be the oversampling parameter. Let S nx be the reweighted sampling matrix in which the i-th row
(p:) (p.)1:e'4 with prob. pi
S
with prob. 1 pi-
With probability at least 1- S has M a (log² d loog? _ +log })) nonzero rows and || ||SAx|
(1 = =) ||A
We only sketch the changes in the proof Woodruff Yasuda (2023). First, in the sampling we do not use y-one-sided Lewis weights but the exact Lewis weights of A. True Lewis weights do affect the symmetrization trick. After the symmetrization step, we remove the part of flattening matrix A in their proof. Instead, we claim: (1) By Theorem 7.3 in (Bourgain et al., 1989), 5 is -subspace embedding matrix of A. (2) By Lemma A.3 of (Chen et al., 2022), Lewis weights of SA are uniformly upper bounded by 3. Conditioned on (1) and (2), suffices to prove
m
E 5,0
max
Σ
(S(())) Se.
S
This Ł-th moment upper bound can be derived in the same fashion as the end of the proof of Lemma A.2. Then applying the Markov inequality gives us AxS (1 + e) with proba- bility at least 1 - 8.
The next theorem gives the sample complexity for lp subspace embedding for p > 2 in which samplings are i.i.d. and the probability of every a; being sampled is wa/d.
Theorem B.2. Let A E Randd 2 < p < oo and < 6,8 1. Suppose that the Ep Lewis weights of are Wi,.... Wn. Let p. = w:/d and S E mm
reweighted sampling matrix whose i-th row S. = 1 e.j with probability Pj. Set m = 2 + (log? log log })), then with probability
at least 8, we have |ISAA] + c) ||
We only highlight the necessary changes in the proof of Theorem B.2.
The symmetrization step goes through in the same fashion as the long chain of inequalities in the proof of Lemma A.2.
By Theorem 7.3 of (Bourgain et al., 1989), S is --susspace embedding matrix of A.
By Lemma A.4, Lewis weights SA are uniformly upper bounded by g- The left steps are the same as the changes mentioned for Theorem B.1.
C RESULT FOR THE OTHER SAMPLING METHOD
In this section, we prove that our main result Theorem 3.5 still holds if the reweighted sampling matrix S is defined to be of the first kind:
C with prob. p;
S
0,
with prob. 1- Pi:
where p; Iw, and 2 - (log² dlog + log })). Accordingly, Lines 3-8 of Algorithm are changed to the following lines.
1: for = 2, ..... do
2: if a; is sampled with probability p: = Bu, then
3: S p; 1/p and query the label of a,
Compared to the proof of Theorem 3.5, the following modifications needed: (1) (1) Theorem B. a 1/2-subspace embedding matrix A. (2) To show that Lemma A.2 holds, we observe that by Lemma A.3 of (Chen et al., 2022), Lewis weights of SA are uniformly upper bounded by 3
19

---

Published as a conference paper at ICLR 2024
Boare value
licenl Ville
AUT IOTERNTTTOO
1200
6003
2043
madel:
rumber modeo
(a) MNIST
(b) Kuzushij-MNNSST
(c) Fashion-MNIST
(d) EMNIST-letters
4LP of ofwaddiuu
eard vokce
2200
2003
(e) EMNIST-digits
(1) SVIIN
CIFAR-10
(h) CIFAR-100
2011
Tumber
namber models
number maree
Biwi
FLD
CelebA
Figure 4: The trends of the sum of the maximum Lewis weights with 2 among multiple repre- sentations as the number of deep models increases.
D DETAILS OF EMPIRICAL OBSERVATION
To address the challenges of distinct representations from multiple deep models, one solution is to sample the unlabeled instances by their maximum Lewis weight among different representations. Recall that the sample size proportional to the sum of sampling probabilities, this strategy will not save the number of queries if the sum of the maximum Lewis weights is k times larger than that a single regression problem. Therefore, we would like first to examine the sum of maximum Lewis weights across representations it will determine the potential query savings. In the following empirical studies, we mainly consider the case of p = 2 (i.e., squared loss), where the Lewis weight becomes exactly the leverage score.
Empirical Settings. We conduct experiments on 11 datasets, the details are summarized in Table 3. For each dataset, we randomly sample 3000 instances to train the models with 20 epochs, then extract features for the whole dataset and calculate their leverage scores. We use the squared loss in model training and keep all other settings the network architectures as the target models. These architectures are published by a recent NAS method OFA (Cai et al.. 2019) for accommodating diverse resource-constrain devices, ranging from NVIDIA Tesla V100 GPU to mobile devices. To demonstrate the distinctness of these models, we report the initial performances of the models on the classification datasets in Table 2. can be observed that the model performances are significantly diverse. It aligns well with our problem
the OFA project. We employ 50 distinet
Table 2: Summary of the initial performances of 50 deep models on the classification datasets. We report the mean accuracy, standard deviation of the accuracies, maximum and minimum accuracy in the table.
Dataset MNIST
mean accuracy
std. deviation
maximum
minimum
94.79
4.39
97.61
72.99
F.NNISTT
81.76
3.03
85.09
67.32
K.MNIST
74.79
7.94
85.61
51.31
CIFAR-I0
48.54
3.36
53,01
36,92
CIFAR-100
11.34
2.14
16.85
7.63
SVHN
45.53
7.62
60.98
31.88
EMNIST-I,
70.04
14.21
83.23
25.84
EMNIST-d.
95.12
3.64
97.76
76.13
20

---

Published as a conference paper at ICLR 2024
Table 3: The specifications of the datasets used in the experiments.
Dataset
# #Training
#Testing
#Label
Task
MNIST (LeCun et al., 1998)
60,000
10,000
10
Classification
Fashion- MNNSS (Xiao et al., 2017)
60,000
10,000
10
Classification
Kuzushiji-MNIST (Clanuwat et al., 2018)
60,000
10,000
10
Classification
SVHN (Netzer et al., 2011)
73,257
26,032
10
Classification
EMNIST-dige -dgitts Cohen et al. (2017)
240,000
40,000
10
Classification
EMNIST-letters (Cohen al., 2017)
88,800
14,800
26
Classification
CIFAR-TO (Krizhevsky, 2009)
50,000
10,000
10
Classification
CIFAR- Krizhevsky (2009)
50,000
10,000
100
Classification
Biwi (Fanelli et al., 2013)
10,317
5,361
2
Regression
FLD (Sun et al., 2013)
13,466
249
10
Regression
CelebA (Liu et al., 2015)
162,770
19,962
Regression
setting. Figure I shows the theoretical upper bound and the exact values of the sum of the maximum leverage score of each instance across different representations.
Results. We first plot the upper bound of the sum of the maximum leverage scores across multiple representations as the number of models increases. For matrices A A!...., A of n rows, it clearly holds that >; max, (Aa) S E E; ( Σ, 13 S min{E; rank(AA)), n). This upper bound is plotted in red color, which grows almost linearly until it reaches the number of instances n.
We examine the exact values of the sum of maximum leverage scores across multiple representa- tions. All figures show that the exact sum grows very slowly as the number of models increases. This suggests highly consistent discrimination power of most instances across different representations, as the leverage score when p 2 is exactly the leverage score, which measures how hard instance can be linearly represented by others. Therefore, a small number of discriminating examples suffices to effectively train multiple models. leverage scores also provide a possible direction to interpret the behavior of deep representation learning, as prior works have not discovered any simple form of correlation among the diverse representations obtained by different model architectures (Kornblith et al., 2019; Nguyen et al., 2020).
E DETAILED EXPERIMENTAL SETTINGS AND ADDITIONAL RESULTS
E. DETAILED SETTINGS
All experiments are run on two GPU servers, each equipped with four GeForce RTX 3090 graphic cards, an Intel Xeon Gold 5317 CPU and 128 GB Memory. The details of the datasets are presented in Table 3. The configurations of 50 deep models are specified in Table 4. Note that the network dentition and pre-trained weights of each configuration can be downloaded from the GitHub page of the OFA project (Cai et al., 2019).
We follow the training settings of (Tang & Huang, 2022) in our experiment of the vanilla deep learning scenario. Specifically, at each query iteration, each target model will be initialized with the pre-trained weights on ImageNet and trained for 20 epochs on the labeled dataset with batch size 32. SGD optimizer is employed with learning rate 1.5 x 10 momentum coefficient 0.9 and weight decay factor 3 x 10-5, A dropout rate of 0.1 is used in the training process.
In our experiments of the fine-tuning scenario, we train linear prediction layer with ReLU activa- tion function using mean squared loss. The training specifications are introduced as follows. The SGD optimizer is employed with learning rate of 10-3 and weight decay coefficient of 10-1 The layer is trained for 30 epochs with training batch size 128. We set the random seed to 0 for reproducibility. Please refer to the submitted source code to reproduce our results.
The implementations of each compared method are introduced as follows. We use the code in (Tang & Huang. 2022) to implement DIAM, Coreset and Entropy methods. Specifically, DIAM first ob- tains the predictions of the unlabeled instances using the models in the latter half of training epochs of each target network. Then, it selects the batch of instances that multiple models have inconsistent
21

---

Published as a conference paper at ICLR 2024
Table 4: The names of the model specifications used in the experiments. The network dentition and pre-trained weights of each configuration can be downloaded from the GitHub page of the OFA project (Cai al., 2019).
_oop1 1 @ @...0f.itttnee)) 75
fops topi @ 79.6. winnttnnneee
flops 389M_topl @ 79.1 wfinetune@777
LG-G8 lat@@4m2m 24ms_tomsllll @
25
LG-G8 lat @ 16ms_top/ @ 74.7 114.7_finettue@22
LG-G8 @ Ims_topl 1007.30.finetunnn @2
LG-G8 lat 8ms_ @ @71.1_
25
lat Saedge.lat@88ms @ar.lattttmstopp 10..::66...fmmmmm @5
s7edge @8ms topl @74.7 finetune @ 25
s7edge lat@4Ims top @7..1 finetune
s7edge @at@22mm topl @70.5 finetune @55
note8 lat@65ms top1 @76.1 finetune 25
note8_late (alllat@4msssttt @ 774.9_fnneune @ 25
note8 note8_lat
note8 @ 22ms_top @ 70.4 4f..4_fnnctueeeeeee 25
note 0000@644msssoppp ww..:topp@@0.......
note10_late 1011:latt@00msopppp @9.77 _f..t.iee
@7
noteI0_lat44Ims.u (tt.:p//@00......tttuuueemeeeee
lotel0llat 30ms 70..784ffiiee
@ 75
note 22mmmmppppppppmmmmmmmmmpmmpppppm @76.
note10_aate 6mp f....e.teeeteeeeeeeeemm
@25
note10_lat@ 1tet0olat@@Immstopp/ooo hwwssttpp @7..p__.3...ffll wwt.....nn..n..eeee.. @2
note10 lat 8ms topl @71.4 finetune @
pixell l 143ms 1133msttoppee @80.1 finetuue
pixell lat 132ms top1 @798 finetune @7
pixell lat@ 79ms top1 @78.7 finetune
@ (0..9_.nnetnueee @ 75
pixell_lat@40mms..0 @ @7..9_finetullll @ 25
_..n_fiitt @5
pixell @71.4.innttuee @25
pixel2 lat 62ms topl 75.8 finetune @25
pixel2 15m top1 @74.77.inctune @25
finctune
pixel2 1axel2.lat@333 35ms 35msttmmmpppppl 73.4 finetune @5
pixel2 lat Ialllattmssssuss top1 @71.5. finetune @ @77.5.iinttue
1080ti 1580ti-guu64@ 27ms
76.4_finetune@255
2e50ti.gpuu4@22mms... _opp @ 75.3_finctune@22
1080ti (880ii_pu64@@ 15ms_top copp @ @3.8 f....f.fttuue@22555
1080ti-gpu6444 12ms sop1 @ @72.6 2..__finetunee 25
1100-gpu60 11ms [mss @76.1 1.6.1_.inttuee@2222
#100-gpu64 9ms topl @ 75.3 1553_finetune@"
v100-gpu64 @ 6ms_topl @ 73.00_fneturm
25
v100 v100-gpu64@5ms.top) @ 6.66_fnnetueeeeee @5
tx2 x22-gpu16en 1 96ms_tpl @77..__fnnttulll @25
x22.gpul6@80ms.oog wttpp@p.4.ffntuuum...
tx2 epul6@417 4s topl @72.9 finetune @ @25
tx2 gpul6@35mm 35ms topl @ 70.3 finetune @25
epu lat@ 17ms topl @75.7 finetune 25
epu lat@ 15ms topl @74.6 finetune 25
cpu_lat@ Ims_topl @
@55
cpu_lat@ @ t0pl @71.1_ffneeteee _finetune@@
predictions. Coreset selects data points based on the representation of the pre-trained super-net in OFA. Entropy calculates the entropy scores of unlabeled instances based on the predictions of each target model. Subsequently, it selects the instances with the highest mean entropy scores across multiple model predictions.
E.2 ADDITIONAL RESULTS
E.2.1 STUDY ON MEAN PERCENTAGE OF COVERED INSTANCES
We further examine how many instances with high leverage scores under the representation of single model can be covered by the maximum leverage score sampling. The statistics are calculated as follows: We first get the intersection between the sets of instances that have the top 1% highest leverage score under the representation of model j (denoted by 15) and top 1% highest Maximum leverage score (denoted by I'). Then, divide the cardinality of this subset by the number of t% unlabeled instances. Finally, we calculate this value for each j E [k) and compute the average to obtain the percentage of covered instances, i.e.,
74
We report the mean percentage of covered instances of deep models Figure 5. can be observed that x(10) is about 30% on most datasets (except for Biwi), that is, 0 covers on average about 30% of the instances with high leverage scores of each representation for most datasets. For all datasets, increases, x(t) increases rapidly. These phenomena suggest that sampling modest number of instances by maximum leverage scores can effectively train multiple deep models, as there significant fraction of instances with high leverage scores shared across different models.
22

---

Published as a conference paper at ICLR 2024
20 Mo
MMM www.um wO
MM
(a) MNIST
(b) Seeushij-MMNIS
(c) Fashion-MNIST
(d) MANNIST-eeteess
AVD
0%
EMNIST-digits
(1) SVHN
CIFAR-10 10
(h) CIFAR- 100
(i) Biwi
(i) FLD
(k) CelebA
Figure 5: The mean percentage of shared data between instances having the highest maximum leverage score and those having the highest leverage score under the representation a specific deep model.
E.2.2 STUDY ON THE CLASS IMBALANCE RATIO
Another metric of interest for AL classification algorithms is the class imbalance ratio, which is defined max. Eie(n, I[ c}/ min, Eie Ily c), where Il is the indicator function. Some active query strategies may cause severe class imbalance, rendering them hardly generalizable to other target models and learning tasks. This issue becomes more significant for multiple target models, In this experiment, we examine the class imbalance ratios of different AL methods in the classification tasks. Specifically, we compare the ratios after the third AL iteration, where total of 12000 labeled instances are present, including the initially labeled set. The results are reported in Table 5.
We can observe that our proposed method consistently produces a balanced labeled dataset. Its class imbalanced ratio is very close to that of the Random sampling. On the other hand, Coreset suffers from the class imbalance, suggesting that the training instances with different classes exhibit diverse intra-class distances under deep representation. This implies that the instances sampled by Coreset may have a large distribution gap with the dataset. Entropy obtains a similar class imbalance ratio that of Random, which might appear counter-intuitive. given that Entropy prefers the instances near the decision boundary and such instances are typically less likely to be class- balanced. possible reason is that the mean entropy scores of the unlabeled instances may have a small standard deviation, potentially diminishing the advantages of using Entropy for identifying the most informative instances, the setting of multiple target models.
23

---

Published as a conference paper at ICLR 2024
Table 5: The class imbalance ratio of different query strategies.
MNIST
F.MNIST
K.MNIST
SVHN
CIF.10
CIF.100
EMN.L
EMN.d.
DIAM
2.007
3.250
1.472
2.121
1.525
4.390
2.216
2.811
QBC
1.867
6.721
1.987
4.474
5.212
13.607
9.178
10.664
Coreset
3.561
3.708
2.116
2.330
1.871
6,000
5.375
4.491
Random
1.262
1.091
1.067
3.008
1.062
1.511
1.092
1.222
Entropy
1.331
1.077
1.091
3.052
1.087
1.439
1.088
1.166
Our
1.217
1.081
1.050
2.993
1.098
1.440
1.109
1.209
Table 6: Rumning time (hours) of the methods in regression benchmarks. The running time includes model training and data querying.
Methods
Biwi
FLD
CelebA
Random
1.217
1.383
1.202
Coreset
1.483
1.883
3.667
Our
1.551
1.850
5.817
QBC
1.632
1.800
4.110
24


Reviews:
[{"review_id": "mUqDD56gm9", "reviewer": "Reviewer_KBY8", "summary": "This paper proposed a one-shot active learning algorithm which only queries the unlabelled target data once, which is in contrast to the existing AL algorithms that often rely on iterative model training. This one-shot query can reduce computation costs from repeated training, especially for deep models. Specifically, the authors extract representations of the same dataset using distinct network backbones and learn the linear prediction layer on each representation via an $\\ell_p$-regression formulation.", "questions": "I have some questions and comments, and I hope the authors can try to clarify.\n\n1. My first question is about the one-shot query. I do admit that it will reduce the computational burden; however, I'm wondering whether the performance will be comparable with the traditional iterative training procedure.\n2. In the empirical setting part, I'm confused about the setting of *50 distinct architectures*. Since it's noted in the footnote that all the experiments were conducted with the same GPU and CPU, I'm wondering whether it's still necessary to employ such method?\n3. As I mentioned in the weakness part, more recent baselines should be compared to demonstrate the effectiveness of the proposed method.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper tackles the one-shot active learning, which is an interesting idea since the iterative training procedure of active learning can indeed be computationally expensive. The proposed method is theoretically rooted and technically sound. Besides, the source code showed that the proposed algorithm seems to be reproducible.", "weaknesses": "My primary concern is about the problem setting. As a motivation, the authors claim that the iterative training of traditional active learning can be computationally expensive, and the same instance can have different representations through distinct backbones. However, in the proposed method, the dataset was pre-processed with 50 different models to get the representation, which, in my view, is still computationally expensive. Thus, I found the motivation for one-shot active learning is somehow weak.\n\nMy second concern was about the empirical evaluations. The baselines are compared in the empirical evaluations. Only DIAM was published in the past two years. Some recent Deep AL method is missing in the empirical evaluation. \n\nFurthermore, the benchmark datasets evaluated in the paper are somehow simple. More complex and challenging dataset, e.g. CIFAR100, which was widely compared in the AL literature, should also be tested.", "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": "gGucTvhrJ0", "reviewer": "Reviewer_pbqA", "summary": "This paper explores the domain of one-shot active learning for multiple target models. The authors introduce a novel active learning approach that leverages Lewis weights across representations from various target models. The authors provide both sample complexity analysis and empirical results. The empirical results indicate that the proposed method achieves performance comparable to those of iterative active learning methods.", "questions": "a. What's the method's performance on larger datasets such as CelebA?\n\nb. How does the proposed method compare with state-of-the-art general active learning methods in the multi-model setting?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "a. This paper delves into a compelling and practical setting, one-shot active learning for multiple models, which holds significance in real-world scenarios.\n\nb. The proposed approach, employing maximum Lewis weights, is both innovative and well-grounded. The sample complexity analysis presented in the paper is sound, with the derived bound improving upon prior results by a factor of d.\n\nc. The paper's empirical results are promising. The authors compare their proposed approach with several iterative baselines, including the state-of-the-art method DIAM, demonstrating a substantial improvement in efficiency without sacrificing performance.", "weaknesses": "a. While the empirical results are promising, the datasets used in the experiments are relatively small for deep learning models. It would be valuable to assess the method's performance on larger datasets, such as CelebA, to evaluate its scalability and generalizability.\n\nb. A more comprehensive evaluation could include an assessment of how the proposed approach compares with state-of-the-art general active learning methods in the multi-model setting, e.g., BADGE[1]. \n\nc. The paper's writing, particularly in Section 3.1, may benefit from further refinement. The section lists several definitions but offers limited explanations and intuitions, which may challenge readers who are unfamiliar with these terms and concepts, hindering their comprehension of the paper.\n\n[1] Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv:1906.03671, 2019.", "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": "ToSllyz7kS", "reviewer": "Reviewer_ecLZ", "summary": "The paper discusses the use of a one-shot method for active learning to save on the running time of retraining models. The base of the algorithmic development is a solution to the p-th regression problem involving the sampling matrix . The authors also show improvement on prior work for p=2 from O(d^2/e\\(\\epsilon^4) to O(d/(\\epsilon^4)). Empirical results are presented on comparison with other AL algorithms, showing comparable results and reduced running time.", "questions": "1.\tWhat is p in the in the experimental settings?\n2.\tWhy are you starting with 3000 points for initialization? Isn’t that too much (e.g. for MNIST)? Does actual active learning start of with a random 3000 points? isn’t there too much redundancy in querying 3000 point on each query step?\n3.\tHow come random performs better than other AL methods? E,g, Coreset in cifar 10? This does not correspond to the results reported in Senar et. al.\n4.\tWhat is L^2 in (1)? Is it the Lipschitz constant?\n5.\tCan you please show me where your claim about a reduced sample complexity for p=2 is proven? I’ve looked at the supplemental material and still haven’t seen it. If this is indeed a result it should also be addressed in your theorems, just as Gajjar et. al. do….", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.\tClaims improvement on prior work in terms of sample complexity\n2.\tReduced running time for the one-shot approach vs AL.\n3.\tAn approach that tackles real problem of having multiple models", "weaknesses": "1.\tPresentation is poorly motivated in many cases\n2.\tThe empirical results cover a rather limited scope of data sets, most are MNIST types data sets and some curves don’t reflect SOTA (see questions below). The experimental setting is also counterintuitive for active learning scenarios.\n3.\tI am missing the connection between the theoretical & algorithmic construction and the empirical validation.\n4.\tClarity: \na.\tIt isn’t clear what is the relation between the A matrix, the models and the data. Sometimes A is referred to as data and sometimes it is referred to as a model\nb.\tWhy is the reweighting done by sqrt(mp_q)^-1? What is the motivation\\intuition for that?", "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": "dE2RLga2nT", "reviewer": "Reviewer_QZho", "summary": "This study introduces a one-shot AL approach aimed at reducing the computational overhead caused by iterative model training. The strategy for sampling unlabeled instances leverages the maximum Lewis weights across various representations. The authors validate their method on eight classification and regression benchmarks, employing 50 deep learning models to demonstrate its efficiency.", "questions": "- Can this method be generalized to situations where different models have differen norms in their training objective functions?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- This work aims to present a more comprehensive framework, applicable to multiple models and multiple error norms. \n- The paper is well-structured and easy to follow.\n- The motivation behind the sampling strategy is easy to comprehend.", "weaknesses": "- If the results from the empirical study suggest that as the number of models increases, the sum of the Lewis weights grows very slowly, this may indeed imply that the information between different models might not be so \"distinct\". If I understand correctly, isn't there a certain gap between this and the motivation mentioned in the introduction?\n- In the experiments, why are the baseline settings different for the classification task and the fine-tuning regression task, with the former being iterative and the latter one-shot? \n- In the experiments, the running time of data querying and model training for different methods in classification benchmarks was presented. What about in the fine-tuning scenario?\n- Why isn't there a one-shot method for multiple models in the baseline?", "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)