One-Round Active Learning through Data Utility Learning and Proxy Models
Authors: Jiachen T. Wang
Si Chen
Ruoxi Jia
Venue: Accepted by TMLR ()

Abstract: While active learning (AL) techniques have demonstrated the potential to produce high-performance models with fewer labeled data, their application remains limited due to the necessity for multiple rounds of interaction with annotators. This paper studies the problem of one-round AL, which aims at selecting a subset of unlabeled points and querying their labels \emph{all at once}. A fundamental challenge is how to measure the utility of different choices of labeling queries for learning a target model. Our key idea is to learn such a utility metric from a small initial labeled set. We demonstrate that our approach leads to state-of-the-art performance on various AL benchmarks and is more robust to the lack of initial labeled data. 

In addition to algorithmic development and evaluation, we introduce a novel metric for quantifying `\emph{utility transferability}' -- the degree of correlation between the performance changes of two learning algorithms due to variations in training data selection. Previous studies have often observed a notable utility transferability between models, even those with differing complexities. Such transferability enabled our approach, as well as other techniques such as coresets, hyperparameter tuning, and data valuation, to scale up to more sophisticated target models by substituting them with smaller proxy models. Nevertheless, utility transferability has not yet been rigorously defined within a formal mathematical framework, a gap that our work addresses innovatively. We further propose two Monte Carlo-based methods for efficiently comparing utility transferability for different proxy models, thereby facilitating a more informed selection of proxy models.

Published in Transactions on Machine Learning Research (11/2023)
One-Round Active Learning through Data Utility Learning and Proxy Models
Jiachen T. Wang' Princeton University
tinnhooonn@@@rriitton..dl
Si Chen Virginia Tech
chersis@ut.co edu
Ruoxi Jia"
ruonifia @rt edu
Virginia Tech
Reviewed on OpenReview: https: // openreview. net/ forum? id= 8HQCOMRa79
Abstract
While active learning (AL) techniques have demonstrated the potential to produce high- performance models with fewer labeled data, their application remains limited due the necessity for multiple rounds of interaction with annotators. This paper studies the problem of onc-round AL, which aims at sclecting subset of unlabeled points and querying their labels all al once. A fundamental challenge is how to measure the utility of different choices of labeling queries for learning target model. Our key idea is to learn such a utility metric from a small initial labeled set. We demonstrate that our approach leads to statc-of-the-art performance on various AL benchmarks and more robust to the lack of initial labeled data. In addition to algorithmic development and evaluation, we introduce novel metric for quantifying 'ulilily Iransferabilily" the degree of correlation between the performance changes of two learning algorithms due to variations in training data selection. Previous studies have often observed a notable utility transferability between models, even those with differing complexities. Such transferability enabled our approach, as well as other techniques such coresets, hyperparameter tuning, and data valuation, to scale up to more sophisticated target models by substituting them with smaller proxy models. Nevertheless, utility transferability has not yet been rigorously defined within formal mathematical framework, gap that our work addresses innovatively. We further propose two Monte Carlo- based methods for efficiently comparing utility transferability for different proxy models, thereby facilitating a more informed selection of proxy models]
1 Introduction
While the past several decades have witnessed the potential of active learning (AL) methods to produce pegfomerforeecc models with fewer labels, they are often slow and even infeasible in practice. Specifically, for existing AL methods to be effective, they require many rounds of interaction with the annotators and the interaction in different rounds must be adaptive, in the sense that the choice of the instances in one round depends on the responses to the labeling requests in all the previous rounds. However, for tasks in which it takes significant time and resources to label the queried instance (e.g., in scientific experimental design, it would take days or even months to obtain feedback from wet-lab or physics experiments (Botu & Ramprasad] 2015 Nord et al. 2016 Yang et al. 2019)), ) adaptive interaction over many rounds is inefficient. Moreover, in practice, there typically waiting time before labeling queries are responded to, simply due the fact that potential data annotators may not respond promptly upon request. For example, in marketing applications, can actively request feedback by sending surveys to customers (annotators), but the customers may not
*Correspondence Jiachen T. Wang and Ruoxi Jia. Jiachen T. Wang did the work Harvar University.

---

Published in Transactions on Machine Learning Research (11/2023)
Data utility function U
Target model
Unlabeled dataset S.
Annotation
Labeled dataset
Training
Evaluation
Score
2 Step 1 Data utility learning
Validation data
Unlabeled pool
0.5
Data utility model 0
0.6
0.9
0.1
Step 2 Data utilityy optimization
Figure 1: Overview of DULO.
be responsive (Sharp et al. 2011p. If the overall task is to be completed within a certain time frame, this effectively limits the number of rounds of interaction.
This paper focuses on onc-round AL-a special AL problem where only a single round of interaction is allowed. Specifically, the learner required select a set of unlabeled instances and query their labels all at once. Importantly, this setting features high throughput and time efficiency the selected instances labeled completely in parallel. A fundamental question in one-round AL is: How can measure the utility of different subsets of unlabeled data points and select the one with the highest utility while adhering to some given labeling budget?
be
A natural idea to approach the one-round AL problem is to adopt data utility metrics from state-of-ther art multi-round AL methods (Wei et al.) 2015 Ash et al. 2019 Killamsetty et al. 2020) and use them to perform onc-round selection. A commonality of most of these data utility metrics is that they rely on hypothesized labels assigned by the temporary target model that is trained the currently available labeled instances. For multi-round AL, the size of labeled instances will grow to by the annotators; as result, the hypothesized labels will become more accurate over time and the data utility metrics based on hypothesized labels will, in turn, become more reliable. However, in one-round setting, the classifier used for generating hypothesized labels can only be trained on a small initial labeled set and thus the hypothesized labels are highly unreliable. Hence, directly adapting multi-round AL methods to one-round setting suffers unstable and unsatisfactory performance. There are only very few existing works in the field of AI. focusing on the one-round setting. Most of them, however, either make too strong too weak assumptions about the initial labeled data points. For example, Contardo et al. (2017) assumes largo-size labeled pool comprising classes that do not appear in the unlabeled pool, and Yu el. al. (2006); Gu et al. (2012); Shoham & Avron (2020); Jin et al. (2022) consider a very restricted setting where no initial labeled data points are given. On the contrary, this work considers a more reasonable setting where there are few initial labeled data points given.
rounds of labeling requests are responded
The contributions of this work are summarized as follows.
(1) New algorithm for one-round AL. We propose Data Utility function Learning and Optimization (DULO), model-agnostie one-round AL framework (illustrated by Figure 1] Our framework is grounded the notion of a data utility function, which maps any given set of unlabeled instances to some performance measure of the target model trained on the set after being labeled. Onc-round AL can be naturally formulated as a problem of seeking the set of unlabeled instances that maximizes the data utility function. We propose lo learn a model to approximate the data utility function, and present a blockwise stochastic greedy algorithm to efficiently select data that optimizes the learned model. As this model trained to predict data utility without label information, thus circumventing the limitation caused by unreliable hypothesized labels. To improve scalability, leverage the prozy model technique which uses smaller proxy model in place of the larger target model to perform data utility learning. To further address the concern about the computational
The proxy "model" here means the overarching learning algorithm that used for accelerating active learning.
2

---

Published in Transactions on Machine Learning Research (11/2023)
efficiency of data utility learning, in Section 3.2.1 we show that it is not necessary to learn the utility of large data subsets as the variance of utility over different subsets of a given size diminishes as the size increases.
(2) Characterizing and measuring utility transferability for selecting proxy models. The proxy model- idea above builds upon a popular observation that the choice of training data often affects the performance of different models in similar ways. Specifically, the data that are more useful for training one model are usually also more useful for training another, even when the two models are of different complexities. Indeed, this observation has been leveraged to improve efficiency in various applications, including AL, coreset selection, data valuation, among others (ewiss & Catlett 1994 Coleman et al. 2019 Nath et al. 2021 Jia
ct al. 2019 Wang et al. 2023). Despite the broad applicability, principled ways of mcasuring the correlation of data utility between different models are still lacking. Towards this end, we formalize the notion of ulility transferabilityy which characterizes to what extent a proxy model mimics the target model's performance variations when trained over different subsets. We further develop two Monte Carlo methods to efficiently compare the strength of transferability for different proxy models, which could facilitate the selection of a better proxy model.
(3) Experiments. We evaluate DULO to select data from a class-imbalanced pool, a notse-contaminated pool, and unlabeled pool that exhibits natural variations of data quality. We show that our approach outperforms state-of-art batch AL strategies across different settings and datasets. In addition, it is more robust to the lack of initial labeled data.
2 Related Work
According to whether the samples are selected iteratively or not, AL approaches can be classified into two main categories: One-Round Active Learning and Multi-Round Active Learning.
Multi-Round AL. Multi-round active learning has been widely studied in the past, where one can send selected unlabeled data to be labeled to the oracle, updale the querying strategy (usually partially trained model), and choose new unlabeled data depending on the updated querying strategy. We refer the readers to (Ren et al.) 2021 for a more comprehensive survey of multi-round AL. Earlier studies of multi-round AL focused on the sctting where only one example is selected in each round, c.g., (Schohn & Cohn 2000
Fine et al. 2002). Batch AL was later proposed to improve label acquisition efficiency by querying multiple examples in each round. Most of seate-of-the-ate multi-round AL methods rely on partially-trained classifiers to generate hypothesized labels for unlabeled points and further use them prioritize them for selection. For instance, BADGE (Ash al. 2019) samples a batch of unlabeled points with large and diverse gradients, but to calculate the gradients, unlabeled data need to be assigned with some hypothesized labels. Filtered Active Submodular Selection (FASS) (Wei et al. 2015) selects unlabeled data points by optimizing the predicted performance of a Ce-Nearest-Neighhbbene classifier or Naive Bayes, which can be calculated analytically only given the hypothesized labels of the unlabeled points. GLISTER (Killamsetty et al. 2020) formulates the active learning problem as bi-level optimization, which seeks unlabeled points that lead to the highest validation performance when these points and corresponding hypothesized labels are used for training. These approaches suffer unsatisfactory performance in the early rounds the classifier used for generating hypothesized labels is trained on limited labeled data. In contrast, our data utility metric estimates the unlabeled data's usefulness without the need of hypothesized labels.
One- Round AL. One-round active learning is a much less studied field compared with the multi-round setting, as it cannot benefit from the feedback of the labeling oracle. However, such techniques are useful when frequently querying the labeling oracle is not possible or time-consuming, e.g. as cited by (Gu et al. 2012 Contardo al., 2017) when using Amazon Mechanical Turk (AMT). An existing one-round AL approach is to derive an upper bound on the prediction error of the target models and then select unlabeled data by minimizing the bound. However, such derivation is possible only for specific models, such linear regression (Yu et al. 2006 Gu et al.) 2012) and graph-based predictive model (Guillory & Bilmes] 2009 By contrast, our work proposes a general-purpose approach for one-round AL and does not restrict the type of target models. Another idea of enabling one-round selection is via meta-learning (Contardo et al.) 2017]. However, unlike our work, this work assumes a largo-size labeled pool comprising classes that do not appear in the unlabeled pool. Shoham & Avron (020) selects unlabeled data in one-round via optimizing a V-optimality criterion for kernel ridge regression. Jin et al. (022 proposes one-round AL technique for
3

---

Published in Transactions on Machine Learning Research (11/2023)
image segmentation tasks based on contrastive learning and diversity-basee querying strategy. Compared to
our work, Yu et al. (2006); Gu et al. (2012); [Shoham & Avron (2020); Jin et al. (2022) consider a slightly
different setting where no initial labeled data points are given and their algorithms are specialized to specific target models or applications.
3
One-Round AL via DULO
3.1 Algorithm
In this section, we will formalize the problem of one-round AL and present our algorithm to solve the problem via optimizing a learned data utility metric.
One-round AL problem setup. Let the feature and the label space be denoted by X and V, respectively. A ground-truth labeling function (or the oracle) f X' -> y returns the ground-truth label for any given input feature. A one-round AL algorithm is given a pool of unlabeled data points U { a set of labeled data points L == {(1,, (f (x,)) and a budget M. It then selects subset S of size M from the unlabeled pool to request their labels such that the performance of target model trained on the labeled data is maximized. In particular, the initial labeled data should be small and particularly, insufficient for training a high-performance model.
We define a data utility function (DUF) as a mapping from an unlabeled set to a real number indicating the utility of the set. We follow a typical AL goal and consider the performance of the model trained on the unlabeled data after labeling as its utility score. Formally, let S {=,)[=1 denote a set of features. A learning algorithm A is (potentially randomized) function that takes a training set S = {(z,, (z:))) input and returns classifier f. A metric function takes classifier as input and outputs its performance. u(f) usually measures f's ability to generalize, such as validation loss or accuracy. Given A, u, and f", a DUF is defined as UA...f-(S*) = EA (((((() E (*))))] When context, is clear, we omit subscripts and simply write US**).
One can formulate one-round AL problem as an optimization problem that seeks an unlabeled set maximizing the DUF: argmax |= =M,,* US*) where U is the unlabeled pool and M is the labeling budget. Note that each evaluation of (S*) requires labeling S and training on the labeled instances. Therefore, an unlabeled set selection problem cannot be solved by evaluating the DUF on different choices of unlabeled sets and picking the best one. We propose to train a parametric model Ū (referred to as a data utility model hereinafter) to approximate DUFs based on the initial labeled data. Overall, the proposed algorithm, DULO, proceeds in two stages: (1) learning Ô from initial labeled data and (2) optimizing Ô over the unlabeled pool to select the most useful points.
Stage 1: Data utility learning. Learning a DUF consists of two steps: utility sampling and utility model training. The initial labeled data set L = ((x, (x:))) is randomly partitioned into a training set for and a validation set Leat. In the utility sampling step, we randomly sample subsets S, from Cir, apply the training algorithm A on S, and obtain the model f. ~ A(S.). We then calculate the validation accuracy (or loss) of f on Eeat, which gives u(fi). Let Sf denote the set of features in Se. Then, we could score each S, with its utility u(ft). We will refer to the scored subsets {(S), u(ft))) as utility samples. In the utility model training step, we will learn model I to approximate the DUF U using the utility samples. Since U is set function, its output is invariant to input permutation. There has been extensive work modeling such functions, either by designing neural network architectures that are permutation-invarint in nature (Zahcer et al., 2017) or imposing permutation invariance as a soft constraint via regularization (Alieva et al. 2021 b. Our data utility learning framework is flexible to incorporate different modeling strategies for set functions and can benefit from the advances of set function learning. In our experiments, we instantiate the utility model U by DeepSets (Zaheer et al. 2017 a popular model for set function to showcase the AL result enabled by data utility learning.
Stage 2: Data utility optimization. With the learned utility model 0, we will then solve the following optimization problem to select the most useful unlabeled points:
argmnax Ü(5)),
(1)
4

---

Published in Transactions on Machine Learning Research (11/2023)
The challenges for solving the problem above are three-fold. First, the above problem is combinatorial optimization problem. Finding the global optimal solution is NP-hard in general. Second and more subtly, when the selection budget M is much larger than the size of the initial labeled set N (which is a typical AL scenario), even an optimal solution to the maximization of U in 1 cannot ensure selecting the truly useful data (i.e., the one that maximizes U). During the utility learning stage, the maximal size of the input sets that Ö could be trained on is N. Hence, Ü cannot generalize to unseen unlabeled sets of size much larger than N as effectively those sets of size less than N. Thus, the solution to ( may not be close to the solution argmax|ss U(S*). Third, evaluation time of Ü increases with the input size.
To tackle these challenges, propose a Blockwise Stochastic Greedy (BSG) algorithm. Specifically, at each iteration, we first sample (without replacement) a subset B C u (called a block) from the unlabeled pool u. The block size B [B] should be chosen such that the Ū has both good generalizability and efficient. evaluation. We select MB
[ data points from each block. Within each block, we run stochastic greedy algorithm, which also proceeds iteratively. Specifically, in each sub-iteration, we randomly select a subset Z C B (without replacement) and find the data point within Z such that achieves the highest marginal contribution to unlabeled set R that already selected within B, i.c., e = argmax, Ü(R {e)) (R). The runtime of BSG is O(4)) in terms of the number of evaluations of Ü. In Section 5.3.5, we conduct an ablation study of how varying block sizes influence active learning performance, and we empirically validate that B = [rr is a great heuristic to ensure both computational efficiency and high data utility for practical use.
The pseudo-code of DULO is provided in Appendix A It is worth noting that although unlabeled data is selected block-by-block DULO is completely different from multi-round batch-mode AL, since it does not require the data points selected in the previous blocks to be labeled before we select data points from the current one. Therefore, data selection within different blocks is fully parallelizable.
3.2 Computational Considerations
Since our goal is to develop a one-round AT. tool for realistic ML tasks, scalability is crucial. While the
ResNet50 ResNet18
SP=0.9
optimization part of DULO can be made scalable via the BSG algorithm, the computation time of data utility learning still remains a major hurdle. Specif- ically, constructing size-T set of utility samples requires retraining a target model for T times. In our ablation study (Section /.3.3), we found that for DUF to be learned accurately, the number of utility samples required (i.e., the number of target model retraining required) is of the order of the size of the initial labeled data. The overhead of retraining in- creases with (1) the size of the retrained model and (2) the size of sets that are trained on.
SP=0.923 201
SP-0.95 AO
VGG11
SP=0.907 dr
SP=0.95
SP=0.97
8
18616
SP=0.872
SP=0.925
5P=0.918
2
5P=0.932
SmallCNN
ResNet18
ResNet50
VGG11
Figure 2: Example of the correlation between data utilities for commonly used models for CIFAR10. The values in both x- and y-axis are test accuracy. 'SP" stands for Spearman's correlation coefficient.
To improve the efficiency of data utility learning for large target models, we propose to use a separate, less computationally intensive prory model in place of the much larger and more accurate target model to generate utility samples. Besides, retraining of a proxy model could be further accelerated by parallelization without any communication overhead. This sooe--moel-bbaaee idea builds on important phenomenon observed in many past works [Lewis & Catlett 1994 Coleman et al. 2019 Nath et al. 2021) that the points that are more useful for one learning algorithm are usually also more useful for another, or in other words, the relative data utility scores of different data subsets are transferable between models. Figure 2 illustrates such utility transfcrability, where the x and y-axis of each point represent the accuracy of two different models trained on a given subset and different points are trained on different subsets. Although expensive classifier's accuracy is much higher than less expensive classifier, the accuracies of two
5

---

Published in Transactions on Machine Learning Research (11/2023)
classifiers are positively correlated. The observation of utility transferability has been also leveraged to boost efficiency in other applications, including coreset selection (Lewis & Catleti 1994| Coleman et al. 2019);
hyperparameter tuning (Nath et al, 2021) and data valuation (Jia et al.] 2019) Despite its wide adoption, how to measure utility transferability remains an open question (Wu & Zhang. 2021). In Section we will rigorously characterize the transferability and present ways to measure it, which could further facilitate the selection of proxy models.
3.2.1 Do We Need To Learn the Utility for Large Subsets?
As discussed earlier, the inefficiency of data utility learning also grows with the size of subsets used for retraining proxy model. However, as these subsets are randomly selected from the initial labeled data and the initial labeled data are often limited in practice, the size of these subsets being trained on is usually small. The readers may worry that if the initial labeled dataset is large, one needs to perform many slow retrainings on many large subsets. In this section, we show that this is not necessary as the variance of utility over different subscts of a given size diminishes as the size increases.
Recent empirical observations (Hestness et al. 2017 Rosenfeld al. 2019 Kaplan et al. 2020 Hashimoto
2021) show when the data size is large, the generalization error of a neural network is strikingly predictable with merely the information of data size. The relationship between error and size consistently follows a power-law. Despite the past works on the scaling law phenomenon, they have been mostly focused on an empirical study of how the average model performance over different subsets of a given size changes as the size increases. However, in the context of active learning, we are interested in the confidence interval of the performance prediction. If the confidence interval is narrow for a given data size, it means that different subsets of that size would result in similar model performance. In that case, it does not matter which subsets of that size are selected and therefore, we do not need to perform active learning at the size.
In this section, we lake a step lowards analyzing the confidence interval of scaling law-based performance prediction and present the first analysis for a class of deep neural networks whose output behavior closely mimic linear models. Remarkably, this class includes pretrained networks as well as sufficiently wide deep neis (Achille el al., 2021 Mu et al. 2020 Lee et al.] 2019). In these scenarios, a deep neural network can be transformed into an equivalent linear model trained with a simple quadratic loss but still reaches a performance similar to the original model. Therefore, we can approximate deep neural networks' DUF's by analyzing the equivalent linear model. Specifically, given a model (x), let wy denote an initial set of weights (e.g., pre-trained on ImageNet for image classification task). Following Achille et al. (2021) we consider a linearization flint (x) of the network fw fx(x) given by the first-order Taylor expansion of fw(x) around wo: fx) = fwo (x) + V fw. (x) (x) - -wo) If the weights w do not move too much from the initial pre-trained weights Wo during fine-tume tuning, then flin( (x) will remain a good approximation of the network while becoming linear in w (but still remaining highly non-linear with respect to the input x). Effectively, this is equivalent to training a linear classifier using the gradients z, := Wwfwa (x:) as features (Mu et al., 2020). (Achille et al.) 2021) showed that equivalent performance can be obtained by replacing the loss function with the regularized least-squares loss Ei= ( - f (x,))] + ?/! The advantage of this equivalent formulation of neural networks is that the optimal weights w can now be written in closed-form.
Theorem 3.1. The DUFs for linearized neural network with mean squared error (MSE) metric trained on a i.i.d sampled dalaset S of size n whose gradient distribution Vwlwo (x.) is subganssian follows USS) = =n -IC + O 00(n3//2 (To((/)))) with probabilily at least 8 over the choice of S for sufficiently large C is constant depending on test data.
Implication of Theorem 3.1 for Data Utility Learning. The term On 13/2 Vlog(1/8) in Theorem 3.1 3/2
shows that the confidence interval shrinks as the data size grows larger. That is, the performance variation between different subsets become neglectable in large-data regime and hence it is not crucial to learn the difference and choose among different subsots. This implics that we can safely focus data utility learning on the small-data regime, and performing data utility learning on relatively small subsets is a win-win for both efficiency and data selection effectiveness.
6

---

Published in Transactions on Machine Learning Research (11/2023)
4 Measuring Utility Transferability
Data utility's transferability across different learning algorithms is an intuitive concept that has been employed to boost computational efficiency in numerous applications that require model retraining (Lewis & Catlett 1994 Coleman et al. 2019: Jia et al. 2019 Nath et al., 2021). However, to the best of our knowledge, the notion of transferability has not been formally defined before. In this section, we delve into this concept and introduce its first formalization. Subsequently, we present two heuristics aimed at estimating the transferability between two learning algorithms. These guidelines are useful in selecting appropriate proxy models. Specifically, given a set of candidate proxy models, all within a predetermined computational constraint (i.e., the clock time of retraining for nultiple times is appropriate), one can pick the model with the highest (estimated) utility transferability against the target model.
Formalization. For a given datasct D == ((r (=:))] and binary vector a E {0,1]", write Da {(.;, (1;))) = }} as the subset of 'D that is selected by the non-zero entries in a. Let W. == A(D.), representing the model obtained by applying the learning algorithm A on Da. In this section, we assumee A is deterministic for simplicity and roadability. Therofore, U(f2;(a; = 1}) = u u(wa). We start by formally defining utility transferability.
Definition 4.1. Given dataset D, we say two learning algorithms A and Ā are p- p-utility transferable if Pra.9 [T 3) > 0] 2 p where
TAsnAo (a,;;)))(u(x)))) - ulwaa) (u((s)) - u(((a))
(2)
and (), ~ Unif((O, x Unif((O, 1))""
The parameter reflects the 'extent' of transferability. When 1, w and w have perfect utility transferability. We describe two efficient methods to measure transferability. The uniform distribution in the definition results from the Maximum Entropy Principle. Although a proxy model can preserve the target model's selection result as long as the maximal utility subset on the proxy model is also the maximal utility subset on the target model, we do not know the maximal utility subsets a priori. Hence, the uniform distribution over pairs of subsets is the most reasonable prior in Definition 4.1 When the context is clear, we omit the learning algorithm pairs A1 and dataset D, and simply write B).
4.1 Two Heuristics for Estimating Utility Transferability
A naive of comparing the transferability of different proxy models with target model is by training the target and proxy models on all possible data subsets and computing p by calculating the fraction of (a, p)pairs that satisfy (2). This naive approach is clearly infeasible as both the target and proxy models need to be retrained on exponentially many subsets. Here, we propose two heuristics to evaluate the transferability. These heuristics can be used as a guideline for selecting proxy models.
Vanilla Monte Carlo (VMC) Method. One natural idea is to use a Monte Carlo approach to estimate p. We can randomly sample m subsets Da....., Dam: train the target model and proxy models on each of Day, and then count the number of (i, (paiis such that T(a 0zy) > 0, i,j 1,.... m. The Monte Carlo estimation of p
is thus P = Eistejem [[T())))))20] which is unbiased with sample variance Var(ş) = (((1-)) - m(m-1)/2
Suppose that we are given a pool of K proxy model candidates, then the proxy model selection time is roughly m (Ek= & + target), where T & and Tiarget are average computation time for training k-th candidate proxy model and the target model, respectively. Proxy models often chosen such that the training time is neglectable compared to the target model. So the computational time of proxy model selection is dominated by mTTargett i.c., retraining the target model for m times. When p= 1/2, if we want Var(p) < 10-4 (so the slandard deviation < 10-²), m Ry 75. On the other hand, directly learning the data utility model without the proxy model technique requires training the target model for thousands of times. Hence, leveraging a proxy model for data utility learning and (if allowed) spending extra computational budget selecting the most suitable proxy model is in general more recommendable than directly retraining the target model for the sake of efficiency.
7

---

Published in Transactions on Machine Learning Research (11/2023)
Lower Bound Estimation Based (LBEB) Method. We develop another Monte- Carlo based approach
to select proxy models from the perspective of the lower bound of Pra.s [T(or, (3) > 0J. First notice that Pra, [a, 3) > 0] = 2 (a, Pro (T(a, > 0j. Therefore, we can sample Da.:... Do
as before and du
try to bound E.. Præ [T(a () >0 0]. By first-order Taylor expansion, we have u u(ws)) rl( (uaa)
(33
.)) =
Za
ow. der
Bu. Own (3 a)) Let B a. We have (u(wp) - u(ww)) (u(wØ) u(wa)) 2 aau
Own.
8v
da
x)
8ha de
8u Beta
& =
( Dre
T Du awia 2) ))²
Bura 8n 2) =7 (wwa)
)
_ au Owa
awra 0o
2. Let Σ
(duia)
T
Du
T
Ou
(Bwa do
Data
do
If the learning algorithm Wi is ERM style gradient-based algorithm, then @ww T
can be computed by implicit
aaa function theorem (similar to the technique used in (Koh Liang 2017)). ) Pr, [=" > 0] indicates the degree of transforrability between two modcls. Since we are particularly interested in the transferability between two models of different. sizes, E is asymmetrie. But note that 2² > 0 if and only if == )² > O. Hence, can instead analyze the symmetric matrix A == + ET_ We derive lower bound of the probability for which z" Az > 0.
Theorem 4.2. For any fined E 10, let S = (3 -3)= A(3 - -a). We have Prp-Und(((0.13)- 0] N 1 - exp runtime, respectively.
exx
" where cn and are function of A and and can be compuled in O(k) and O(n)
The exact computation of es and μ is deferred to Appendix B.2 due to space constraints. From this theorem, we know that the lower bound of Prę.-umit( [=" A 0] can be thus characterized by the ratio C(A(a), = -'T x² transferability. A larger value of this quantity implies stronger transferability.
Ei and the quantity E C(A(a:), os) can be used an efficient measure for
We compare the effectiveness of these two approaches in Section 5.2
5 Evaluation
In this section, we first evaluate the two building blocks of DULO: (1) the effectivenoss of using data utility model to predict the performance of model trained on a given dataset, and (2) the effectiveness of the two heuristics proposed in Section 4 for measuring the transferability between learning algorithms. Finally, we evaluate the performance of DULO and compare it with the existing round AL strategies and the state-of-the-at batch AL strategies in one-round setting.
5.1 Performance of Data Utility Prediction
We empirically evaluate the quality of data util- ity prediction from a trained DeepSet-based utility model. Specifically, we randomly sample data sub- sets of the same size from the initial labeled training data fer ('seen data') and unlabeled pool U ('unseen data'), and test the performance of the trained data.
MNIST
CIFAR10
Predicted Accuracy (%)
80
Predicted Accuracy (%%
Seon Data
Spen Data
60
Unseen Data
30
Unseen Data
40
20
20
utility model Ô in predicting the test accuracy of proxy models trained on the subset. As Figure 3 shows, the predicted test accuracy is highly corre- lated with actual test accuracy. The mean square error of the prediction for unscen data is < 0.0024 for MNIST dataset and < 10-4 for CIFAR1O dataset. We also note that Ō will slightly underestimate the utility of high-quality dataset and overestimate the utility of low-quality datasot. However, the overall trend is preserved, as the Spearman cocfficient is 0.933 for MNIST and 0.913 for CIFAR10. Implementation details and additional results on more datasets are shown in Appendix D.2
(a)
80
(b)
20
30
True Accurany (%)
True Accuracy (%)
Figure 3: Prediction of the trained data utility model on validation subsets. "Seen data" indicates the elements in the validation subsets are used during utility model training; "unseen" indicates otherwise.
8

---

Published in Transactions on Machine Learning Research (11/2023)
5.2 Estimating Utility Transferability
In Figure we empirically evaluate the effectiveness of VMC and L.BB proposed in Section to measure transferability. Specifically, for 8 most commonly used models for CIFAR10 and MNIST, train them on the
Misordered Model Pairs (%)
60
VMC
LBEB
same m subsets of the full datasets, compute P = Eisresem ([T(a,)))>))) m(m-1)/2 and Σn= ((A(a)),a.) for each pair of models. We set m S 90 in the experiment. To establish the ground truth, train 8 different models on and rank each pair of models
40
20
5000 (> 90) subsets of according to p computed over = 5000. We then rank each pair of models according to the VMC and the LBEB method, and the performance of transfcrability measurements is evaluated by the number of misordered pair of model pairs, with respect to the ground truth translerability ranking. As we can see, both methods are able to achieve a low misorder rate (< 18%) when m 2 60. For small m, LBEB method achieves better performance in measuring transfcrability.
25 # of Samples
50 75
Figure 4: VMC method vs. LBEB method to compare trans- ferability between models. The error bar indicates the standard deviation across 10 runs of ran- dom set sampling.
5.3 Active Learning
Protocol. We evaluate the performance of different AL strategies on different types of models and a varied amount of selected data points. We evaluate the robustness of DULO on different practical scenarios such as imbalanced or noisy unlabeled datasets. We also test the performance on real-world datasets and provide insights into the sclected data. Finally, we perform ablation studies for the sample complexity and hyperparameters for DULO. A potential variant. for DULO that is combined with Uncertainty Sampling is deferred to Appendix D.5.1
Datasets & Proxy Models & Implementation. We summarize the dataset and proxy / /target model settings in Table [ The proxy models are selected based on the tradeoff between the utility I transferability with the target model and computational budget. All of the Ltr and U are sampled from the corresponding datasets' original training data, where the sampling distribution uniform unless otherwise specified. For all datasets, we randomly sample 4000 subsets of Lir and use the corresponding proxy model to generate the training data for utility learning. We set stochastic greedy optimization's 's precision parameter e = 10-3 and optimization block size B 2000 in all experiments. For each experiment setting, repeat DULO and other baseline algorithms 10 times to obtain the average AL performance and error bars. We defer the dalaset. descriptions, model architectures, hyperparameters and other experiment details to Appendix D
Choosing proxy models. The proxy models in our experiments are shown in Table were judiciously chosen by weighing both utility transferability with the target model and computational feasibility. For each dataset, we assessed two proxy model architectures that are sufficiently different for a more meaningful comparison. From these, our selection favored the model that offers superior balance between transferability and computational efficiency. To provide greater clarity, we also include the alternative proxy models considered. When both proxy models displayed similar computational runtime or both were comfortably within our computational constraints, we naturally gravitated towards the model exhibiting superior transferability. In cases where one model might have shown marginally better transferability but came at a considerably steeper computational price (for instance, 1e for CIFAR10), we opted for the model that ensured a more practical runtime.
baselines: (1) FASS (Wei et al. 2015) first filters out the data samples with low uncertainty about predictions. It then selects a subset by first assigning cach unlabeled data a hypothesized label with the partially-trained classifie''s prediction and optimizing Nearest. Neighbor submodular function on the unlabeled dataset with hypothesized labels. (2) BADGE (Ash et al.) 2019) first generates hypothesized labels and selects a subset based on the diverse gradient embodding obtained with the hypothesized samples. (3) GLISTER (Killamsetty et al.) 2020) also generates hypothesized labcls and performs discrete bi-level optimization problem on the hypothesized samples. (4) Coreset (Sener & Savarese 2017) tackles active learning through the lens of core-set selection.
Baselines. We consider the state-of-the-art batch AL well one-round AL strategies
9

---

Published in Transactions on Machine Learning Research (11/2023)
Dataset
[Grr]
Cuall
Selected Proxy Model (time/ / () Alternative Proxy Model (time/ / () Target Model (time)
MNIST
300
300
LR (0.75 hrs / (..32)
KNN (0.1 hrs / (.718))
TeNet (1.5 hrs)
CIFAR10
500
500
SmallONN (0.9 las 0.824)
MLP (0.4 has 0.778)
Small VGG (12 hrs)
USPS
300
300
SVM-RBB (1 min / 0.794)
SVM- Linear (1 min / 0.752)
LR (8 min)
PUBFIC83
500
500
LeNet (1 hrs / 0.872)
MLP (0.6 hrs 0.697)
Small VGG (18 hrs)
CIFAR.100
1000
1000
SmallCNN (2 hrs 0.844)
18 (11 hrs / 0.848)
ResNee50 (1.5 day)
IMDb
1000
1000
Small RNN (1 day / 0.8)
Bag of Word + KNN (0.4 las / 0.63)
LSTM (12 days)
Table 1: Datasct and Model Scttings. The 'time' in the table means the rough clock time for training 4000
proxy/larget models. p means the proxy model's estimated utility transferability with the target model using
LBEB method from Section 4
Unbalanced Dataset
Noisy Dataset
MNIST
CIFAR10
MNIST
CIFAR10
Labeling Budget
500
1000
5000
10000
500
1000
5000
10000
DULO
89.89 (0.39) 92.36 (0.30)
52.97 (1.03)
60.81 (0.35)
90.36 (0.27)
91.03 (0.10)
58.49 (1.00)
66.11 (0.36)
Random
88.83 (0.53)
90.79 (0.56)
49.82 (0.16)
57.86 (1.23)
88.12 (0.43)
89.56 (0.23)
41.93 (5.97)
46.86 (7.82)
FASS
88.82 (0.43)
91.11 (0.32)
48.17 (3.06)
57.85 (2.50)
88.24 (0.61)
90.41 (0.83)
52.12 (0.56)
61.45 (1.14)
BADGE
88.99 (0.37)
91.00 (0.33)
48.82 (2.09)
56.51 (1.32)
87.23 (0.54)
89.03 (0.34)
55.35 (1.16)
64.38 (0.18)
GLISTER
88.89 (0.62)
91.37 (0.50)
47.56 (1.68)
55.14 (0.54)
86.54 (0.46)
89.68 (0.75)
54.05 (0.93)
60.90 (2.97)
CoreSet
89:20 (0.31) 90.39 (0.15)
51.14 (0.81)
55.78 (0.57)
89.28 (0.11)
89.68 (0.12)
53.07 (1:34)
62.53 (0.74)
TED
88.51 (0.15) 89.54 (0.13)
87.79 (0.27)
89.11 (0.15)
EBM
88.42 (0.09)
89.64 (0.03)
88.08 (0.16)
88.46 (0.34)
Table 2: Performance comparison of DULOO with other baselines on imbalanced and noisy datasets. For each
labeling budget, we plot the accuracy (in %) of models trained on the selected dataset. Standard errors are shown in '()
Contrary to relying on hypothesized labels, this method leverages an upper bound, independent of data labels, to substitute the conventional coreset loss. (5) Transductive Experiment Design (TED) (Yul
et al. 2006 selects the samples that minimize the expected predictive variance of ridge regression on the
data. (6) Error Bound Minimization (EBM) (Gu et al. 2012) derive a deterministic, label-independent
out-of-sample error bound for Laplacian regularized Least Squares trained on subsampled data, and select a subset of data points to label by minimizing the derived upper bound. (7) Random is setting where we randomly select a subset from the unlabeled pool.
FASS, BADGE, GLISTER, and Coreset are initially designed for multi-round AL, but they can be exlended to the one-round setting by only performing round of data selection. The implementation details for the basclines are deferred to Appondix [.4]
Remark 5.1. Since the considered baselines such as BADGE and GLISTER have been shown to outperform simple techniques like uncertainty sampling [Settles 2009) we do not compare them in this work. Morcover, we do not compare with the one-round AL technique proposed in Jin et al. (022) as it is specialized to the specific application. We do not compare with the one-round AL technique proposed in (Shoham & Avron (2020) as its implementation has not been released, and it is uncertain how the Gram matrix of the infinite NTK is computed based on the paper's description.
5.3.1 Results on Imbalanced and Noisy Dataset
We artificially generate class-imbalance for MNIST unlabeled datasct by sampling 55% of the instances from one class and the rest of the instances uniformly across the remaining 9 classes. For CIFAR10's unlabeled dataset, we sample 50% of the instances from two classes, 25% instances from another two classes, and 25% instances from the remaining 6 classes. The results for MNIST and CIFAR10 dataset are shown in Table 2 As we can see, DULO siguificantly outperforms the other baselines. By examining the data points selected by different strategies, we found that DULO can indeed select more balanced dataset, thereby leading to higher performance.
To create noisy datasets, we inject Gaussian noise into images in random subsets of data. The noise scale refers to the standard deviation of the random Gaussian noise. For MNIST, we add each of the noise scales
10

---

Published in Transactions on Machine Learning Research (11/2023)
DULO
Random
FASS
BADGE
GLISTER
CoreSet
USPS
88.43 (0.28) 87.56 (0.41) / 0.005
$7,09 (0.41) / 0.0
87.00 (0.60) / 0.0
87.38 (0.52) / 7.0
87.663 (0.396) / 0.002
PubFig83
51.55 (0.66)
50.87 (1.01) / 0.027
49.29 (2:95) 0.100
50.29 (1.16) 0.003
51.5 (2.18) 0.014
50.837 (0.586) 0.003
CIFAR100
77.18 (0.42)
76.02 (0.46) 0.003
75.91 (0.99) 0.005
76.2 (1.27)
0.037
73.44 (1.38) / 0.000
76.106 (0.518) / 0.0
IMDb
88.25 (0.44)
87.95 (0.52) 0.098
88.12 (0.2) / 0.179
88.13 (0.15) 0.259
88.13 (0.15) / 0.216
87.8/33 (0.308) 0.015
Table 3: Datasets with Natural Quality Variations. The selection budget for USPS, PubFig83, CIFAR100 and IMDb are 1000, 2000, 25000 and 20000, respectively. The p-values for paired t-test for the comparison between DUL.O and each of the baseline are shown after '/". Notably, the majority of these p-values are below the 0.05 threshold, signifying that DULO's improvement over the basclines is statistically significant in most scenarios.
of 0.25, 0.6, and 1.0 25% unlabeled data (i.e., 75% of the unlabeled data are noisy and there are 3 different noisy levels). For CIFAR10, we add noise to 25% unlabeled data points with noise scale 1.0. Table 2 shows that DULO putperforms other baselines by more than 1% for every data selection size, and is very close to, or sometimes even better the performance on a randomly selected clean dataset. To get more insights into the selection process, we inject an MNIST image together with its three noisy variants of different noise scales into the MNIST unlabeled dataset and examine their selection order in DULO, shown in Figure (a). DULO tends to select clean, high-quality images early and able to sift out noisy data.
5.3.2 Results on Datasets with Natural Quality Variations
We study the effectiveness of different AL strategies on datasets from different domains, including USPS, PubFig83, CIFAR100, and IMDb dataset. These datasets usually contain some natural variations in data quality. The results are shown in Table We can that DULO consistently outperforms all other baselines in almost all of the settings and all labeling budgets. Figure 5 (b) illustrates the images selected in different ranks by DULO. We can see that the points selected earlier have higher image quality; especially, the last. five selected '6' digit images tend to be blurry and some could easily be confused with other digits. The last ten selected images contain four '1's, which is because USPS is class-imbalancee dataset, and there are more 'I's than other classes. Figure 5 (c) shows the rankings of 3 images within an optimization block. As we can see, the early face images selected by DULO contain complete face features, while the later ones either contain more irrelevant features or are corrupted. Additional experiments on MNIST and CIFAR1O can be found Appendix D.5.4
#573 #1183 #1396 #1927
#1 #1001 #2000
6
(b)
First five '6's:
Last ten images:
666 666
Last five
6 1
4
(c)
Figure 5: Selection ranks for different images in a greedy optimization block. (a) MNIST, (b) PubFig83, (c) USPS.
5.3.3 Ablation Study of Size of Utility Samples
Model Accuracy (%)
The overhead of data utility learning hinges on the size of utility samples for training proxy models. Figure t shows the one-round AL performance for data utility models trained with different amounts of utility samples.
90
88
T-250
T=2000
We find that the performance is nearly optimal as long as the number of utility samples is above 500, which only takes around 12 min to generate. Therefore, practical guideline for setting the size of initial labeled dataset is 10-50 data points per class, and for setting the number of utility samples is at least 2x the total number of initial labeled dataset.
T=500
3000
86
40000
T=1000
0
500
1000
Selected Data
Figure 6: Effect of # utility sam- ples on DULO performance.
11

---

Published in Transactions on Machine Learning Research (11/2023)
5.3.4 Robustness to Scarcity of initial labeled Data
Table | shows the one-round AL performance for utility models trained with different amount of initial labeled training data points [C Note that here the largest possible training samples for the proxy model varies, but for fair comparison, still train the classi- fiers with 300 initial labeled training samples together with selected data points. We fix the block size and mumber of subsets sampled for utility training in the experiments. As we can see, near-optimal performance could be achieved even when there are only 100 la- beled training data points. When | too large, the trained utility model's performance might degrade due to insufficient train- ing samples compared with input size. When |Ctrl is too small, the generalizability of utility model to large sets would be worse and at the same time, the block size has a small upper limit, which can capture less data interaction.
Labeling Budget
500
1000
DULO with [Co-] 50
86.15
(0.39)
87.22 (0.31)
DULO with [a- 75
88.07 (0.28)
88.79 (0.30)
DULO with En. 1100
90.36 (0.21)
(0:27)
DULO with C. 200
90.26 (0.27)
91.26 (0.21)
DULO with C.. -300
90:36
(0.27)
91.03 (0:10)
DULO with C.. = 550
90.63
(0.31)
91.12 (0.32)
DULO with [C,,1 =
11.00=0000 1000
89.58 (0.26)
91.00 (0.20)
Table 4: Performance of DULO with
utility models trained with varying sizes of initial labeled training data [trl
5.3.5 Ablation Study of Optimization Block Size
Figure 7 (a) shows the one-round AL performance
CIFAR, Noisy
Elliciency vs. Accuracy 1
with different optimization block sizes B. As we can see, both too small and too large block sizes can degrade the performance of one-round active learn- ing. This is because when B is too small, the data. utility model fails to capture interactions between data points selected from different. blocks. When B is too large, the data utility model has a large gen- cralization error it never sees such large dataset during its training time. Although the stochastic optimization algorithm runs in ((141) regardless of the block size (without parallelization), individual DeepSets evaluation time increases significantly with a larger input set. Figure 7 (b) shows the runtime vs accuracy plot with different block sizes. We can see that when B is too large, it suffers from both poor utility and inefficiency. However, we find wide range of B that achieves both good efficiency and high data utility (the points located on the right of the figure), which is around [Cell (|Corl = 500 for CIFAR10 in our setting). This servers as heuristic choice of B. In this range, the block size. is small enough so that DeepSets models generalize well on input sets of block sizes, while also being large enough so that the utility model could capture most of the data interactions.
Model Accuracy (%)
10
60
LogiSeccodaa
5000
5-4000
50
0 1300
6
De 183
40
4 .0--
30
5000
10000
50
55
60
(a)
Selected Data
(b)
Accuracy (%)
Figure 7: Ablation Study: (a) compares DULO's per- formance with different optimization block sizes, and (b) studies the relationship between efficiency and AL performance for different block sizes when the number of selected data is 6000.
6 Conclusion & Future Works
This work proposes a general framework for one-round AL, an important AL setting where only one round of label query is allowed, via DUF learning and optimization as well as the use of proxy models. We develop a principled approach for selecting the proxy models. Our evaluation shows that it outperforms existing baselines across various datasets and models.
There are two assumptions underlying our approach: (1) the labels of the initial labeled dataset are correct and (2) the labeled and unlabeled datascts should share the same label space. While these two assumptions usually hold in practice, extending DULO to noisy initial labeled data and varied label settings would be interesting future directions.
12

---

Published in Transactions on Machine Learning Research (11/2023)
Acknowledgments
This work is supported by Amazon-Virinnia Tech Initiative for Efficient and Robust Machine Learning, the National Science Foundation under Grant No. IIS-2312794, NSF IIS-2313130, NSF OAC-2239622, and the Cisco Award. We are grateful to anonymous reviewers at TMLR for their valuable feedback.
References
Alessandro Achille, Aditya Golatkar, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Lqf: Linear quadratic fine-tuning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15729-15739, 2021.
Ayya Alieva, Aiden Aceves, Jialin Song, Stephen Mayo, Yisong Yuc, and Yuxin Chen. Learning to make decisions via submodular regularization. In International Conference on Learning Representations, 2021.
URL http:///pppprreeie..ntttttorrrrt
___
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alckh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. arXiv preprint arXiv: 03671, 2019.
Jock A Blackard. Comparison of neural networks and discriminant analysis in predicting forest cover types. Colorado State University, 1998.
Venkatesh Botu and Rampi Ramprasad. Adaptive machine learning framework to accelerate ab initio molecular dynamics. International Journal of Quantum Chemistry, 115(16):1074-100) 2015.
Si Chen, Tianhao Wang, and Ruoxi Jia. Zero-round active learning. arXiv preprint ar arXi::2107.06700 2021.
Cody Coleman, Christopher Yeh, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Selection via proxy: Efficient data selection for deep learning. arXiv preprint ar Xiv:11906. 1829, 2019.
Gabriella Contardo, Ludovic Denoyer, and Thierry Artières. meta-learning approach to one-step active learning. arXiv preprint arXiv:1706. 08334, 2017.
Shai Fine, Ran Gilad-Bachrach, and Eli Shamir. Query by committee, linear separation and random walks. Theoretical Computer Science, 284(1):25 51, 2002.
Quanquan Gu, Tong Zhang, Jiawei Han, and Chris Ding. Selective labeling via error bound minimization. Advances in neural information processing systems, 25:323-331 2012.
Andrew Guillory and Jeff A Bilmes. Label selection graphs. Advances in Neural Information Processing Systems, 22:691-699, 2009.
Tatsunori Hashimoto. Model performance scaling with multiple data sources. In International Conference Machine Learning, pp. 4107 4116. PMLR, 2021.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Pat- wary, Mostofa Ali, Yang Yang, and Yanqi Zhou. Deep learning scaling is predictable, empirically. arXiv preprint ar Xiv: 7122 00409, 2017.
Ruoxi Jia, David Dao, Baxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task-specific data valuation for nearest neighbor algorithms. arXiv preprint Xrx: 08619, 2019.
Qiuye Jin, Mingzhi Yuan, Qin Qiao, and Zhijian Song. One-shot active learning for image segmentation via contrastive learning and diversity-based sampling. Showledge-Based Systems, 241:108278, 2022.
Jared Kaplan, Sam McCandlish, Tom Henighan, Tom Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei, Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. Glister: Gener- alization based data subset selection for efficient and robust learning. ar preprint N.N.:2002.100630 2020.
Pang Wei Koh and Percy Liang. Understanding black- box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894. PMLR, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied document rocognition. Proceedings of the IEEE, 56(11):277-2222 1998.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. Advances in neurol information processing systems, 32:8572- -8822, 2019.
David Lewis and Jason Catlett. Heterogeneous uncertainty sampling for supervised learning. In Machine learning proceedings 1994, pp. 148 156. Elsevier, 1994.
Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proceedings of the AAAT Conference on Artificial Intelligence, volume 29, 2015.
Fangzhou Mu, Yingyu Liang, and Yin Li. Gradients as features for deep representation learning. arXiv preprint ar Xiv:20004 05529, 2020.
Vishwesh Nath, Dong Yang, Ali Hatamizadeh, Anas A Abidin, Andriy Myronenko, Holger R Roth, and Daguang Xu. The power of proxy data and proxy networks for pyper-parameter optimization in medical image sogmentation. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 456 465. Springer, 2021.
Brian Nord, Adam Amara, Alexandre Réfrégier, La Gamper, Lu Gamper, В Hambrecht, C Chang, Jaime E Forero-Romero, Santiago Serrano, Carla Cunha, et. al. Spokes: An end-to-end simulation facility for spectroscopic cosmological surveys. Astronomy and Computing, 15:1-15, 2016.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathicu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Seikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825 22:8825-2830, 2011.
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.
Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. arXiv preprint arXiv:1909. 12673, 2019.
Greg Schohn and David Cohn. Less more: Active learning with support vector machines. In ICML, volume 2, pp. 6. Citeseer, 2000.
Ozan Sener and Silvio Savareso. Active learning for convolutional neural networks: A core-set approach. arxiv preprinl arXi::1 000800 2017.
Burr Settles. Active learning literature survey. 2009.
Anne Sharp, Patrick Moore, and Katherine Anderson. Are the prompt responders to an online panel survey different from those who respond later? Australasian Journal of Morkel & Social Research, 19(1), 2011.
Neta Shoham and Haim Avron. Experimental design for overparameterized learning with application to single shot deep active learning. arXiv preprint arXiv:2009.1884 2020.
Jiachen T Wang, Yuqing Zhu, Yu-Xiang Wang, Ruoxi Jia, and Prateck Mittal. Threshold knn-shapley: A linear-time and davacc--rrendlyy approach to data valuation. arXiv preprint rrXte:2308.157000 2023.
Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In
International Conference on Machine Learning, pp. 1963. PMLR, 2015.
14

---

Published in Transactions on Machine Learning Research (11/2023)
Wentao Wu and Ce Zhang. Towards understanding end-to-end learning in the context of data: machine learning dancing over semirings & codd's table. In Proceedings of the Fifth Workshop on Dala Management. for End- To- End Machine Learning, pp. 1 4, 2021.
Kevin K Yang, Zachary Wu, and Frances H Arnold. Machine-learning-gnideed directed evolution for protein engincering. Nature methods, 16(8))687-694, 2019.
Kai Yu, Jinbo Bi, and Volker Tresp. Active learning via transductive experimental design. In Proceedings of the 23rd international conference on Machine learning, pp. 1081-1088, 2006.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets. Xiv preprinl orXiv: 703. 06114, 2017.
15

---

Published in Transactions on Machine Learning Research (11/2023)
A Pseudocode of the Proposed One- Round AL Algorithm
Algorithm 1: DULO for One-Round AL
input L initial labeled data, A - training algorithm for classifier S, u metric function, Au training algorithm for utility model U, T number of utility samples, U unlabeled data pool,
M labeling budget, optimization block size, E precision paramcter for stochastic greedy algorithm.
autput::Sedecteed selected set.
Split L into training set Ler and validation set Lvat. // Data Utility Learning
a Initialize set utility sample Su = 0.
for t I do
Randomly choose a subset St = f (S()) S. Ltr-
Train classifier ft 1 A(S:) (or ft A(S)) if A stochastic). Su Sv U ((T,, u( Lval)))
end
Train 0 + (v(SS).
10 // Data Utility Optimization
11 Initialize Sselected = 0, U' = U.
12 while |Seeterted < M do Sample B U' of size B.
13
14
R
15
while |R| <
MB do
[|]
16
Sample Z C B of size
M
1 log(1/s)
Find argmax eZ (RU(c))
18
R R+1 RU (e)
end
20
Sselected &- Seelected U R. u' + + R.
21
end
23
return Sselected
Remark A.1 (Proxy Model Selection). If pool of candidate proxy models that meet given computational budget (i.e., efficiently trainable for thousands of times) is available, then we can pick the one with the highest (estimated) utility transferability against the target model. The utility transferability can be estimated by the two methods proposed in Section 4
Remark A.2 (Comparison with Zero-round Active Learning (Chen al. 2021 The zero-round AT approach in Chen et al. (2021) is based on leveraging labeled data from related domains (i.e., source domains) which may not necessarily be from the target domain. This requires the existence of such domain-specific labeled datasets. In many practical scenarios, finding a source domain that is sufficiently related to the target domain can be challenging, and domain adaptation might not yield the desired results due to the vast differences between source and target domains. From this perspective, one-round AL is more flexible as it allocates some budget to label a few samples from the target domain directly, thereby ensuring the model has direct information related to the target and isn't wholly reliant on domain adaptation.
16

---

Published in Transactions on Machine Learning Research (11/2023)
B Proofs
B.1 Theorem 3.1
Theorem 3.1 (Restate)). The DUF's for linearized neural network with mean squared error (MSE) metric trained i... sampled dataset S of size whose gradient distribution Vw.wo (x;) is subgaussian follows
Vlog(1/0) n2/2
U(S) =n
with probability least 1 - 8 over the choice of S for sufficiently large n. C' is constant depending test data.
with the major differences in the regularization term of linear regression. We first change the notation to the traditional one used in linear regression: write B w- wo E IRd, X = Z E gnxd, y Y fwo (X) E Rd, we have
Proof. The proof follows from (Hashimoto 2021
8 = (X"X X
(4)
Assuming = X3 t for some B R ~ o(0,o²1). Then the covariance of 3 3 with respect to becomes
(8 - B) -3)
3)7]
(5)
= B -B(((XTx + A1) X"y-3)((X"X X) -1 y - B)7]
(6)
[ + 1 + MI) 8) () BY +X
(7)
= E |xTx + A1) (x-(x++ - (x"x + AT)
3) (x AT)
-1
(8)
E =[(xTX x -x))-1 &- 13)T x + A1)
(9)
= (x"x + X1) XTT Elee (XTX+
(10)
= xx + X + -
(11)
= 0² (x AT) _o² 2o +x) -1)
(12)
Denote A x + AL. Assume 0² for simplicity. If each data point x, in X i..d. sampled from some subgaussian distribution x; ~ p. Let X* Raxdd be some test data. Now want to bound the expected loss
1
E (ar0-B3]13 X.c
L(n)
(13)
17

---

Published in Transactions on Machine Learning Research (11/2023)
First, by fixing X, define B - 3 we can that
(3 =31[]]
E
(14)
E ftr xx=xxXX xxxXxe)) x(e
(15)
E tr (x* x=ee e]
(16)
= tr x x (
(17)
tr (x (A-1 - 13)
(18)
tr X Atr (x- x (A-1)))
(19)
The challenge now is thus to estimate Ex[A- and Ex )?)
Define Σ = E[X"X]/m Since X is drawn from some subgaussian distribution, by matrix concentration
inequality, with probability with at least 1- ā we have
|x'Xn Ellop S (oVlo((1/8)
(20)
Vn
for sufficiently large n. Let A XT Xn - Σ. Therefore A == A) + AI = n ((E+ An+
By equality (P+Q)-1- = p-1 + -
p (-Q(-)))) we have
X ( + -1) +
A-1 = n
(21)
T1
[ + - ( n )
11
( + 1 +
Σ
(22)
1=1
1( and since m E + 1 2 mmnn (2) which is a constant, we know that this series converge for sufficiently large n. In this case, the first term the dominant onc.
whenever ||A(E+ + 1 1 1. Since || + - op < n
||
E tr (x A-]
(23)
=t x - (2 + n - + n BB E tr x x
22 [
11-
(24)
1=1
where the second term is dominated by
x- x II+ 1 (-A(I+ > 11)-))
tr
(25)
x x X + X ( + A 2
2 tr
(26)
5 <d|x x 11
( 1) -1
| llop
(27)
= ( (Vog((10)
/
(28)
Vn
18

---

under the condition of Published in Transactions on Machine Learning Research (11/2023)
So
E tr (x*TX*-AX = (xxxX~11> + - 1 + 0
Vlog(1/0)
(29)
n2/2
n
-r x + -
Vlog(1/0)
+
(30)
n23/2
n
By a similar argument, we have
E [ (x-x = -rr xxxxx" (x 11) .ー )) +0
(log(1/5)
(31)
n3
Therefore
[nn)
(32)
n tr xx*xx 1 n 22r xxTxx 21)) +0
Vlog(1/8)
(33)
m
n
n2/22
Sct = nX, we have
Vlog(1//) (1/0)
L(n) tr XX* +0
(34)
n3/2
V.VoVololo log(1/0)
Xn | x - -1l C
(35)
Vn
where this event happens with probability at least 1 5. So the expected loss has diminishing return grows with high probability for sufficiently large n.
B.2
Theorem 4.2
Theorem
4.2 (Restated). For any fixed {0, 1)", let S (8- -33-a a A(B a). We have
41
Pr fo.Uni((O.1))"
S 0] 2 1 exp
(36)
2 T 2
2
km
where Cs and a are function of A and and can be computed in O(k) and O(n) runtime, respectively.
Proof. Since ~ Unif({O, 1))", therefore Br - a; Unif((0,1)) if a; = 0, and B; - -a; Cnif((-1,0)) if ag 1. Let B -aa Denote S₃ Eij=1 I,Aizz
S = x Ax.
Ty Agg
(37)
i=1
19

---

Published in Transactions on Machine Learning Research (11/2023)
We first note that μ B[S,] can be easily computed as
# S[Sp]
(38)
E
2 Aija
(39)
Au E
+ Σ
Ais E [2:]] E [zy]
(40)
1=1
Σ
Aa Σ
Ai E2
[0 E [mg)
(41)
1=1
Define
Y2 Ss - 13 (Sa)
(42)
Then it's easy to that for all & 2 0 we have
E E Mn] Y
(43)
so the sequence of (Yo, Ii...., Yx) is martingale. Also,
|Y Y&l
(44)
|St+1 Sk - E [Sk+1 Sk]l
(45)
1841841* 2xx+1
01 - 11+1N+19
20u+1
0i
(46)
1841141112211 - 1/22 + 2xk+1
04 -B
200+1
a1,b+14
(47)
Ik+1
0++16418841 + 12
0++1N+112+
2
Σ
a B[zs]
(48)
2m
Let
k-1
-
Ck =
sup Bk
Ih
F + 2
asSx B[a;]
(49)
1=1
Since everything is linear, en could be efficiently computed in O(k) as
1 ak.k + 2 [x))
by E
ag E [x:]
(50)
C₁ max (lbul,
(51)
F(Ix)
ae.FF(ax)
+
max(0, (g -bk
(52)
F(xx)
(n. ((sse) + 2
min 0; F(x:)) bb
(53)
where F(xx)= if 2h Uni 1)), and F(xx) = -1 if on Uni)((-1,0))
20

---

Published in Transactions on Machine Learning Research (11/2023)
By Azuma's inequality, have
E²
Pr Pr S = E[S,] - S exp
(54)
2 22 km C
2
By setting
E[[s]] we have
[s
Pr [ Ax S 0 s exp
(55)
22 C
We note that the value of cg depends the order of rows/columns of A. Therefore, in practice, further improve this bound by randomly sample many different permutations and get the smallest value.
21

---

Published in Transactions on Machine Learning Research (11/2023)
C Stochastic Greedy Algorithm
For completeness, we briefly introduce the stochastic greedy algorithm (SG) from (Mrzasoleiman et al. 2015 here, and refer the readers to the original work for a more thorough introduction. The stochastic greedy algorithm is a simple approach that, for each iteration, randomly selects a subset of data and then finds the best data point within that subset. This approach was originally proposed for maximizing submodular functions. In the context of optimizing utility model (i.e., the trained DeepSets model), the "best data point" within each randomly selected subset refers to the data point, with the highest marginal contribution USS {z]) - (S), where S is the set of data points selected in previous iterations. The pseudo-code is outlined in Algorithm 2
The main distinction between this approach and the vanilla greedy algorithm is that the candidate data points to be selected in each itcration of stochastic groedy algorithm is a smaller, randomly selected subset instead of all unselected data points. Thus, this approach is more efficient than vanilla greedy optimization and the runtime linear in the number of dataset size achieve 1/e optimization guarantee for monotone submodular functions is precision parameter).
Although SG provides no theoretical approximation guarantee for general functions, experiments show that it achieves high empirical performance on DUFs. We conjecture that this is because DUFs usually exhibits diminishing return property similar to submodular functions. Exploring different approaches for optimizing data utility models are interesting future directions.
Algorithm 2: Stochastic Greedy Optimization for Utility Model
input dataset D, trained utility model Ü 2 IR, target selection size k, precision parameter for stochastic greedy algorithm E.
output: set SCD s.t. [S] k.
S < 0.
for t t= 1....... h do
Sample R C \ of size I2 log(1/s) k
Find argmax,eR (s)
Su
end
return S
22

---

Published in Transactions on Machine Learning Research (11/2023)
D Additional Experiment Settings
D.1 Transferability Evaluation
Figure 2 shows examples of the transferability of data utilitics between different learning algorithms. The dataset here we use is CIFARIO. For each point in the figures, we randomly sample 5000 CIFARIO images and add Gaussian noise to random portion of the images. We then record the test accuracies of different. model architectures trained on the dataset.
For the experiment in Section 4 that compares VMC and LBEB in measuring transferability, we use 5 models on CIFAR10 and 3 models on MNIST. Specifically, for CIFAR10 we use ResNet18, ResNet50, VGG11, VGG16, and a small CNN model is used as the proxy model for CIFARIO dataset, which has two convolutional layers, each is followed by a max pooling layer and a ReLU activation function. For MNIST we use logistic regression,
LeNet and slightly larger CNN model which has six convolutional layers. There are (2) + (2) = 13 model pairs in total, and we want to rank the transfcrability of those 13 model pairs. we train them on the same
subsets of the full datasets, and compute p Eieeesm (7((0)))))0) and Σi= C(A(as,), az) for each pair of mmm211/2
models. We set S 90 in the experiment. To establish the ground truth, train 8 different models on 5000 (> 90) subsets of MNIST/ /CIARROO,,, and rank each pair of models according to P computed over m = 5000. We then rank each pair of models according to the VMC and the LBEB method, and the performance of transferability measurements is evaluated by the number of misordered pair of model pairs, with respect to the ground truth transferability ranking.
du 0u das. We use the similar trick In the computation of E C(A(az), as), need to first compute Za Sw. da
in inftuence function technique (Koh & Liang 2017) based on implicit function theorem, which involves the
Since this may be computationally expensive for large models, we follow the widely used heuristic and only choose use the last layer of the model. We compute the exact Hessian matrix in experiment, and the Hessian inverse computation can be further accelerated with techniques such as conjugate gradient (Koh & Liang, 2017). For the computation of es and μt, since they depend on the permutation of matrix A and a, we randomly sample 2000 permutations and pick the maximum value of C(A(a:)..s).
computation of Hessian inverse (bre,
0²,
D.2 Implementation Details for Figure 3 and Additional Results
In Figure 3 all sampled subsets are of the same size, where for MNIST the size is 250 and for CIFAR10 the size is 350. For each subset sampling, we first uniformly randomly generate a real value E [1,20] for cach class, and then draw a distribution sample from Dirichlet distribution Dir(an...., where K represents the number of classes. We draw a subset. with different class sizes proportional to p. This sampling design is to ensure the diversity of class distributions in the sampled subsets.
Additional results on CIFAR100 and IMDb dataset are shown in Figure g As we can see, these more intricate datasets align with previously observed tendencies: Ô tends to slightly underestimate the utility for high-quality subsets and overestimate for low-quality subsets. Notwithstanding, the overarching trend remains consistent, with the Spearman correlation cocfficient between the predicted and actual model performance is 0.828 for C1FAR100 and 0.86 for IMDb. We conjecture that due to the inherent challenges of these tasks, neural networks might tend to fit a constant value approximating the mean of the target values. Delving deeper into the intricacies of this phenomenon offers an intriguing avenue for future research.
D.3 Details of Datasets Used in Section
MNIST. MNIST consists of 70,000 handwritten digits. The images are 28 x 28 grayscale pixels.
CIFAR10. CIFAR10 consists of 60.000 3-channel images in 10 classes (airplane, automobile, bird, cat, deer, dog, frog, horse, ship and truck). Each image is of size 32 x 32.
23

---

Published in Transactions on Machine Learning Research (11/2023)
CIFAR100
IMDb
45
35
Predicted Accuracy (%)
Seen Data
Predicted Accuracy (%)
Seen Data
Unseen Data
Unseen
40
30-
35
25
30
25
20
20
30
40
20
30 True Accuracy (%)
25
35
(a)
(b)
True Accuracy (%)
Figure Prediction of the trained data utility model on validation subsets. "Seen data" indicates the elements in the validation subsets are used during utility model training; "unseen" indicates otherwise, The Spearman correlation coefficient between the predicted and actual model performance is 0.828 for CIFAR100 and 0.86 for IMDb.
USPS. USPS is real-life dataset of 9,298 handwritten digits. The images 16 x 16 grayscale pixcls.
The dataset is class-inbalanced with more and than the other digits.
PubFig83. PubFig83 is a real-life dataset of 13,837 facial images for 83 individuals. Each image resized to 32 x 32.
CIFAR100. CIFAR100 is similar to CIFAR10 except it has 100 classes.
IMDB. The IMDb datasel consists of 50,000 movie reviews, each marked as being positive or negative review.
D.4 Implementation Details
Target Models & Proxy Models. A small CNN model is used as the proxy model for CIFARIO and CIFAR100 datasets, which has two convolutional layers, each is followed by max pooling layer and a ReLU activation function. LeNet model is the proxy model for PubFig83 dataset, and we also used it to test the AL performance for MNIST in the experiment. LeNet is adapted from (LeCun et al. 1998), which has two convolutional layers, two max pooling layers and one fully-connected layer. A mini VGG mode is used evaluate AL performance on CIFAR10 and PubFig83, which has six convolutional layers, and each of them is followed by batch normalization layer and ReLU layer. We use Adam optimizer with learning rate 10-3, mini-batch size 32 to train all of the aforementioned models for 30 epochs, except that train LeNet for epochs when using it for testing AL performance on MNIST. We also use the support vector machine (SVM) to evaluate AT performance on the USPS dataset. We implement SVM with scikit-learn Podregosa et al. 2011 h and set the L2 regularization parameter to be 0.1. For IMDb, we use LSTM model Tollows from PyTorc Lutoria M as the targel model, which use pretrained word embedding. smaller RNN model adapted from the same source is used as the proxy model. All other training details follow from the same tutorial.
All of our experiments are performed on Tesla K80 GPU.
DeepSets as Architecture for Utility Learning. A DeepSets model is function Ú(S) = plE o(z)) where both and are neural networks. In our experiment, both & and p networks have 3 fully-connected layers. For MNIST and USPS, we set the number of neurons to be 128 in each hidden layer. For CIFAR10
24

---

Published in Transactions on Machine Learning Research (11/2023)
MNIST, Unbalance
MNIST, Noisy
92.5
Model Accuracy (%)
1000
Model Accuracy (%)
p=1000
8 1200
90
B- 1200
90.0
8= 1400
B 1400
A 1600
88
P 1600
87.5
A 1800
p 1800
B= 2000
B 2000
86
85.0
(a)
500
1000 (b)
0
500
1000
# Selected Data
# Selected Data
Figure 9: Ablation Study: the performance of DULO when we run greedy optimization on the / most uncertain samples of the current classifiers.
and PubFig83, we set the number of neurons in every hidden layer be 512. We set the dimension of set features (i.e., the output of network) for DeepSets models to be 128 in all experiments, except for USPS dataset the set feature number is 64. We use the Adam optimizer with learning rate 10-5, mini-batch size of 32, Bi 0.9, and 32 0.999 to train all of the SeepSets-basel utility models. For IMDb dataset, the utility learning as well as baseline algorithms is performed on the embedding of the corresponding sentence encodings.
The size of the utility samples chosen uniformly at random from the training set. This design because in stochastic greedy optimization, the utility model needs to predict the utility for subsets of all sizes smaller than the block size. It is interesting future work to investigate whether different sampling strategy further improve performance.
Baseline Implementation. In terms of the baseline batch AL approaches, we set / in FASS be the size of unlabeled dataset after parameter tuming. We set the learning rate in GLISTER to be 0.05, following the original paper. We test these baselines with open-source implementationf] The model performance is evaluated on the hold-out test set associated with each dataset. For TED algorithm, we follow the original paper and set the coefficient for & regularizer as 0.1. For EBM algorithm, we set the coefficient for & regularizer and manifold regularization as 0.1 and 0.01, respectively.
D.5
Additional Results
D.5.1 Combining DU with Uncertainty Sampling
Traditionally, AL techniques like uncertainty sampling (US) and query by committee (QBC) have shown great promise in several domains of machine learning (Settles 2009). However, in the task of multi-round batch AL, naive uncertainty sampling fails to capture the interactions between selected samples. Simply choosing the most uncertain samples may lead to a selected set with very low diversity. Filtered Active Submodular Selection (FASS) (Wei et al.] (2155) combines the uncertainty sampling method with submodular data subset selection framework. Specifically, at every round 1, FASS first selects candidate set of 8 most uncertain samples among unlabeled data, and then runs greedy optimization on appropriate submodular objective (with the hypothesized labels assigned by the current model). It is natural to ask whe we should also combine DULO with uncertainty sampling by only performing greedy optimization on the most uncertain samples. We evaluate the performance of DULO when we first filter out data points that the current classifier has high confidence about, and preserve a candidate set of 3 most uncertain samples on which we run stochastic greedy optimization. We show the performance of different. values of 3 on class-imbalanced and noisy MNIST dataset in Figure where = [24] 2000 coincides with the setting of the original DULO algorithm. As we can see, for all settings studied in experiments, B = 2000 consistently outperforms oth smaller values of B. Hence, using uncertainty sampling to pre-process unlabeled samples does not seem to lead to better performance in our one-round AL framework. We conjecture that this is because we only
http:///ghhab..cm///ellllttaatm
25

---

Published in Transactions on Machine Learning Research (11/2023)
Covertype, Logistic Regression
MNIST, Logistic Regression
0.100
0.4
Ground Truth
Ground Truth Scaling Law
Scaling Law
0.075
Var(Error)
0.3
Var(Error)
0.050
0.2
0.025
0.1
0.000
(a)
20000
40000
60000
(b)
0
2000
1000
6000
# Data Points
# Data Points
MNIST, CNN
CIFAR10, CNN
0.10
Ground Truth
0.06
WWW M
Ground Truth
Scaling Law
Scaling Law
Var(Error)
Var(Error)
0.04
0.05
0.02
0.00
2000
4000
6000
2000 4000
(c)
(d)
# Data Points
# Data Points
Figure 10: Illustration of the scaling law prediction for different datasets and different architectures. The heavier orange dashed line corresponds to the variance of model test loss predicted by the scaling law. The "error" the y-axis refers to cross entropy loss. In the figure, "CNN" refers to a small CNN model adapted from PyTrrch tutorial https: htt.a///ttaats..oooooooooo/////a
tutorial. html
have very few labeled samples at the beginning. In that case, the performance of the initial classifiers is pretty poor and their uncertainty outputs are not informative.
D.5.2 Do We Need To Learn DUF in Large Data Regime? Predict Utility Variance with Scaling Law
In this section, we show the practical implication of our Section 3.2.1 and Theorem 3.1 Many recent
literature on the Scaling Law of Model Performance (Hestness el al. 2017 Rosenfeld et al. 2019 Kaplan et al., 2020: Hashimoto 2021) propose to predict model performance on the large data regime by fitting a function log(error) a log(n) + C, where n is the dataset size, and a and C are parameters to be fitted. Our Theorem 3.1 suggests that there may also be certain scaling law style relationship between the dataset size and the variance of model performance, where the randomness is due to the i.i.d. sampling of dataset from natural distribution. TThus, we can predict the variance of model performance on the large data regime by first fitling a function log( (or(Var(er)or)) x -a log(n) + C' in the small data regime (where training a model is fast), and then extrapolating the prediction to large data regime (where training a model is slow). Based on the prediction, one can determine whether it is worth performing active learning for given data acquisition budget. If the predicted utility variability is small, then active learning strategies may only bring small improvements upon random sampling. Tn that case, it could be not that worthwhile performing active learning.
Experiment. We wish to scale datasets while preserving the original distribution. Thus, given a dataset D, 10%. For each r, we
we subsample subsets whose cardinalitics are r|D), where 0.1%, 0.2% 99.9% subsample 10 subsets uniformly al random from the original dataset. We train a model on each of the subsets and compute the variance of model loss on a hold-out test set for a given cardinality. We then fit a function log( (Vrr((()))))) R aa log(n) + on the cardinalitics that are of 0.1%, 0.2%, ..., 4.9%, 5% of the original dataset, and use the learned function to predict the utility variance for cardinalities that are of 5.1%, 5.2%, 9.9%, 10% of the original dataset. Figure 10 shows the result of scaling law prediction on three different.
26

---

Published in Transactions on Machine Learning Research (11/2023)
Unbalanced Dataset
Noisy Dataset
MNIST
CIFARIO
MNIST
CIFAR10
Labeling Budget
1000
5000
10000
500
1000
5000
10000
DULLO Selected Proxy Model
89.89 (0.39) 92.36 (0.30)
52.97 (1.03)
60.81 (0.35) 90.36 (0.27)
91.03 (0.10) 58.49
(1.00)
06.11 (0.36)
DULO Alternative Proxy Model
88.83 (0.16)
91.57 (0:25)
50.62 (0.58)
59.34 (0.34)
89.20 (0.42)
90.58 (0.04)
56.92 (0.35)
63.51 (0.43)
Random
(0.53)
(0.16)
(1:23)
(0.13)
(0.23)
(3.97)
(7.82)
FASS
88.82 (0.43)
91.11 (0.32)
48.17 (3.06)
57.85 (2.51l)
18.24 (0.61)
90.41 (0.83)
52.12 (0.36)
61.45 (1.14)
BADGE
88,99 (0.37) 91.00 (0.33)
18.82 (2.09)
56.51 (1.32)
87.23 (0.54)
89.03 (0.31)
55.35 (1.16)
61.38 (0.18)
GLISTER
68.89 (0.62)
91.37 (0.50)
47.56 (1.68)
55.14 (0.54)
86.54 (0.46)
89.68 (0.75)
54.05
60.90 (2.97)
CoreSet
89.20 (0.31)
90.39 (0.15)
51.14 (0.81)
56.78 (0.57)
89.28 (0.11)
89.68 (0.12)
53.07 (1.31)
62.53 (0.74)
TED
(0.15)
(0.
87.79 (0.27)
89.11 (0.15)
EBM
88.42 (0.09) 89.64 (0.03)
88.08 (0.16) 88.46 (0.34)
Table 5: Performance comparison of DULO with other baselines on imbalanced and noisy datasets where include the performance of DULO when using alternative proxy models. For cach labeling budget, we plot the accuracy (in %) of models trained on the selected dataset. Standard errors are shown in '():
datasets (Covertype [Blackrrd 1998). MNIST, CIFAR10) with different model architectures. As we can see, the scaling law generally performs well for predicting the variance of model test loss in the large data regime.
Discussion. Overall, the consequence of Section 3.2.1 and Theorem 3.1 two-fold. First, it provides theoretical understanding of data utility function (DUF): the data utility becomes more predictable by the size of training data when the size gets larger. Thus, in AL, the choice of unlabeled data sets matters more when the selection budget is smaller. Second and more importantly, it provides practical guidance for designing the input size of data utility model in one-round AL. The computational overhead of data utility learning grows with the size of subsets used for model retraining. The result. in Section 5 shows that performing data utility learning on relatively small subsets is a win-win for both efficiency and data selection effectiveness (as the utility of larger sets has much less variance).
D.5.3 Evaluate Alternative Proxy Models
To emphasize the advantage of selecting proxy models with higher utility transferability, we additionally evaluate the performance of DULO when using the alternative proxy model shown in Table [ and we show the result in Table 5 The results clearly show that DULO, when paired with the selected proxy model, outperforms its counterpart with the alternative model. Notably, even when using the alternative proxy model, DULO's performance remains competitive with other baselines.
D.5.4 Experiments Regular setting of MNIST and CIFAR10
The one-round AL performance on MNIST and CIFAR10 without any data corruption shown in Table G Intriguingly, this setting, the performance across all methods, including the random selection baseline, is quite close each other. We conjecture that this is because of the high curation quality of datasets like MNIST and CIFAR10. Nevertheless, DULO consistently demonstrated competitive performance compared with other baselines for most of the cases.
D.5.5 Runtime
We report the running clock time for all basclines we use Table While DULO is not as efficient multi-round AL techniques, it aligns with our expeclations for a one-round AL approach. Given the intrinsic nature of one-round AL, it demands more computations and greater information extraction from the initial labeled dataset. However, it's worth highlighting that DULO holds marked computational edge over traditional one-round AL methods. This is because these earlier techniques necessitate the computation of the inverse of the Fisher information matrix, a process that is highly computationally heavy for high-dimensional data.
27

---

Published in Transactions on Machine Learning Research (11/2023)
MNIST
CIFAR10
Labeling Budget
500
1000
5000
10000
DULO
96.47 (0.11)
96.89 (0.08)
61.72 (1.71)
68.98 (0.62)
Random
95.23 (0.17)
96.43 (0.22)
61.31 (1.71)
08.25 (0.61)
FASS
94.73 (0.05)
96.45 (0.22)
61.70 (1.74)
69.03 (0.64)
BADGE
94.34 (0.29)
96.86 (0.08)
60.78 (1.67)
68.77 (0.56)
GLISTER
95.99 (0.18)
96.49 (0.07)
61.10 (1.66)
69.24 (0.64)
CoreSet
96.45 (0.11)
96.94 (0.08)
61.03 (1.69)
69.51 (0.58)
TED
95.13 (0.20)
96.07 (0.20)
EBM
95.22 (0.12)
96.39 (0.24)
Table 6: Performance comparison of DULO with other baselines on clean datasets. For each labeling budget, we plot the validation accuracy (in percentage) of models trained on the selected dataset. Standard errors are shown in '()'
MNIST
CIFAR10
Labeling Budget
500
1000
5000
10000
DULO
0.75 hrs
0.75 hrs
0.9 hrs
0.9 hrs
FASS
6.474
6.621
33.147
69.283
BADGE
19.39
37.163
336.722
636.26
GLISTER
5.236
12.707
35.336
67.158
CoreSet
2.652
3.566
38.641
62.645
TED
289.436
1170.006
1 day +
1 day +
EBM
286.618
1201.159
1 day + 1 day +
Table 7: Average Runtime (in seconds) for DULO and different baselines in selecting a fixed amount of data points on MNIST and CIFAR10 dataset, with the setting described in Section 5.3.1 The clock time is recorded when running on an NVIDIA A100 80GB GPU and an AMD 64-Core CPU Processor.
28


Reviews:
[{"review_id": "9zqoz27Jm1", "reviewer": "Reviewer_Diou", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The DULO algorithm introduces a new approach by utilizing data utility prediction to evaluate the scores of subsets, subsequently selecting the optimal subset from the unlabeled pool for active learning.\n2. The authors present some strategies, including the proxy model technique and the blockwise stochastic greedy algorithm, to enhance the efficiency of the DULO algorithm.\n3. The authors address some of the concerns related to the computational efficiency of the DULO algorithm in Sections 3.2 and 4.\n\nWeakness：\n1. The data utility model in the DULO algorithm is trained on T utility sample pairs which are obtained by training T network classifiers separately. Although the authors claim that it's efficiently trainable for thousands of times ($T=4000$ is suggested in the paper), this assumption seems rather impractical, especially in large-scale scenarios.\n2. While the paper suggests substituting the target model with a proxy model as a solution to lower down the computational complexity, it doesn't completely solve the computation cost concerns related to the size of utility samples. Moreover, it seems unclear how to select the proxy model empirically (the authors specify proxy models in the experiment section), even if the authors introduce a section named \"Measuring Utility Transferability\" discussing about how to measure the effectiveness of proxy models.\n3. This paper needs to discuss and compare with existing algorithms in terms of time complexity from an algorithmic perspective, and in terms of the tradeoff between accuracy and running time from an experimental perspective.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a new algorithm named DULO tailored for one-round active learning. The key idea is to train a data utility network on labeled training set which serve as a metric for selecting the most useful data points from the unlabeled pool for active learning. Recognizing the computational challenges of the DULO algorithm, the authors propose to use a small proxy model as an alternative. Moreover, the authors discuss how to measure the utility transferability for the selection of proxy models. The authors conduct comprehensive experiments to evaluate the performance of the proposed DULO and provide some ablation studies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It seems that training T=4000 proxy models to obtain utility samples is impractical especially for large-scale datasets and models. Is it possible to efficiently train for thousands of times while meeting a given computational budget in very large-scale cases?\n- The \"Measuring Utility Transferability\" section explores how to choose a more suitable proxy model to approximate the performance of the target model. However, the experiment section does not provide guidance for selecting a proxy model, but instead specifies it in Table 1. So, where is the role of Measuring Utility Transferability reflected in empirical practice? In other words, how to choose a suitable proxy model when facing a new dataset that can both assess accuracy well and have acceptable running time?\n- Does the proxy model also have a trade-off between accuracy and running time, and how to control the risk of overfitting to the small-size validation set?\n- It's not very clear why the blockwise stochastic greedy algorithm (BSG) in DULO works, and it seems more like an empirical method. Does the algorithm converge? What is its algorithmic complexity?\n- The randomness in BSG (including the selection of blocks B and the selection of subset Z), does it cause instability in the experimental results? To be specific, this paper mentions that the candidate data points to be selected in each iteration of the stochastic greedy algorithm are a smaller, randomly selected subset instead of all unselected data points. Does this smaller, randomly selected subset on the greedy algorithm introduce instability in convergence while accelerating the process?\n- Analyze the time complexity of the DULO algorithm. Compare and discuss it with the algorithmic complexity of the baseline methods.\n- Besides accuracy, can the experimental section evaluate the running time of baseline methods under the same settings? (Compared to the DULO algorithm's time consumption in Table 1)\n- In the 5.2.1 experiment section, do more complex datasets (such as cifar100, IMDb) also show the same tendency?\n", "broader_impact_concerns": "This paper does not need to add a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GkFKkQ6s5J", "reviewer": "Reviewer_mDNd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper is overall quite well written.\n- The idea of One Round Active learning seems important and this is one of the few works to study this for general class of models.\n- The proposed method is natural and the proposed method outperforms existing baselines on a wide variety of dataset settings like noisy and imbalanced data.\n\n- Some of the writing is not clear and I have detailed specific points below.\n- I think some of the baseline comparisons are missing which I have outlined below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- This paper proposes an algorithm for one round Active learning where there is an initial small set of labelled data given and one needs to select datapoint amongst a given set of unlabeled data in one shot.\n- They propose a method to learn utility functions for different subsets of the data and then optimize the learned utility function in an approximate way which is a NP hard problem.\n- They also formalize the notion of utility transferability across algorithms and propose methods to measure utility transferability for different proxy models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The authors mention there are approaches with multiple rounds of active learning but they might be bad because with few labels, the hypothesizes labels might be wrong. But, it still might be good to add some of them as baselines. \n- Also, the authors say that some one round active learning approaches work for linear or kernel regression and the authors also in their work say that deep networks can be approximated by linear methods under appropriate assumptions. So, it might be good to add those as baselines too.\n- The authors use a block size for optimization of the utility function and that leads to some approximation to the problem. Is there some way to also quantify how much approximation does that lead to? Probably, for some size that is low enough so that we can try all possible combinations and how how does this blockwise approach hurt?\n- I didn’t understand the line on Page 5 in the last paragraph where the authors say we “need to retrain the target for about 5 times the size of the initial labeled data”.\n- The authors say that with increasing data set sizes, the points selected do not really matter. But, Theorem 3.1 is for random subsets of data, right? As the dataset becomes larger, I understand that random subsets would have similar accuracy but the best subset still should have a higher accuracy?\n- It was hard to follow the formalism in section 4. I am confused about definition 4.1. First, is the transferability defined on algorithms or models? The introduction talked about proxy models. The organization of this section could be improved. It is somewhat hard to read. Moreover, are the proxy models that are experimented with in this work selected by the method proposed in this section?", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YQkpkyg2NJ", "reviewer": "Reviewer_hRdt", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The idea of one-round AL setting is pretty interesting and useful, and the findings of Figure 2 about the utility transferability would aslo be meaningful, the accuries of shallow DNNs and deeper DNNs are positive correlated, which could help reduce the computational cost in AL sampling processes.\n\nWeakness: The experimental settings of this paper are somewhat not reasonable. \n- The baselines' chosen: The authors have already discussed the shortcomings of multi-round AL like BADGE, FASS, GLISTER in Related Work part, said these methods suffer unsatisfactory performance in the early rounds as the classifier used for generating hypothesized labels is trained on limited labeled data. The authors also mentioned some AL methods related one-round AL. However, in experiments, the authors only adopted multi-round AL strategies like BADGE, FASS, GLISTER as baselines and force them to use one-round setting, which is unfair. The authors should compare their proposed methods with baselines that closer to one-round settings.\n- This papers has overlap with zero-round AL [r1], the author should discuss the differences between this two papers and illustrate in the case that there is already a zero-round AL model, the existence of one-round AL is necessary.\n- Although noisy and imbalance data settings are more challenge, it is still need to compare the AL methods on standard data settings.\n\n\n[r1] Chen S, Wang T, Jia R. Zero-Round Active Learning[J]. arXiv preprint arXiv:2107.06703, 2021.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work presents a novel general framework for one-round active learning (AL), an essential AL setting where only a single round of label query is allowed. The framework is based on data utility function (DUF) learning and optimization techniques, along with the utilization of proxy models. Notably, a principled approach for selecting the proxy models is developed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Required change are list here:\n\n- In the experiments, the authors still conduct experiments very similar to multi-round AL settings like Figure 6, line chart is not appropriate for this task since it looks like multi-round AL settings, should use tables instead;\n- Add more baselines that close to one-round AL setting;\n- Discuss the difference between this submission and [r1];\n- Add more experiments on standard data settings;\n- The proposed method is not a great improvement compared with the baselines in Table 2, it's better to add a paired t-test to evaluated if the proposed model is significantly better than baselines.\n", "broader_impact_concerns": "This submission does not contain Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The main claims are solid, the paper is well-written, and it has an audience in the TMLR community. The authors have responded in detail to the reviewers' requests, and all of the reviewers were in favor of acceptance following the author response. I agree with them, and feel it is appropriate to accept the paper as-is.

*Dear authors:* Please do not forget to change the red-colored text back to black text for the final version.
Decision: Accept (poster)