Direct Acquisition Optimization for Low-Budget Active Learning

Venue: NeurIPS_cc_2024_Workshop_BDU
Published: 2024-09-05 07:23:32

Abstract: Active Learning (AL) has gained prominence in integrating data-intensive machine learning (ML) models into domains with limited labeled data. However, its effectiveness diminishes significantly when the labeling budget is low. In this paper, we first empirically observe the performance degradation of existing AL algorithms in the low-budget settings, and then introduce Direct Acquisition Optimization (DAO), a novel AL algorithm that optimizes sample selections based on expected true loss reduction. Specifically, DAO utilizes influence functions to update model parameters and incorporates an additional acquisition strategy to mitigate bias in loss estimation. This approach facilitates a more accurate estimation of the overall error reduction, without extensive computations or reliance on labeled data. Experiments demonstrate DAO’s effectiveness in low budget settings, outperforming state-of-the-arts approaches across seven benchmarks.

Main paper: 
 introduction: 
 Active learning (AL) explores how adaptive data collection can reduce the amount of data needed by machine learning (ML) models (Settles, 2009; Schröder & Niekler, 2020; Ren et al., 2021; Zhan et al., 2022) . It is particularly useful when labeled data is scarce or expensive to obtain, which significantly limits the adaptability of modern deep learning (DL) models due to their data-hungry nature (van der Ploeg et al., 2014) . In these cases, AL algorithms selectively choose the most beneficial data points for labeling, thereby maximizing the effectiveness of the training process even if the data is limited in number. In fact, AL has been broadly applied in many fields (Adadi, 2021) , such as medical image analysis (Budd et al., 2021) , astronomy ( Škoda et al., 2020) , and physics (Ding et al., 2023) , where unlabeled samples are plentiful but the process of labeling through human expert annotations or experiments is highly cost-intensive. In these contexts, judiciously selecting samples for labeling can significantly lower the expenses involved in compiling the datasets (Ren et al., 2021) .Many active learning algorithms have emerged over the past decades, with early seminal contributions from Lewis (1995) ; Tong & Koller (2001) ; Roy & McCallum (2001) , and a shift that focuses more on deep active learning -a branch of AL that targets more towards DL models in more recent years (Huang, 2021) . Depending on the optimization objective, AL algorithms can be classified into two categories. The first category includes heuristic objectives that are not exactly the same as the evaluation metric, i.e. error reduction. Examples in this category are diversity (Sener & Savarese, 2017) , uncertainty (Gal et al., 2017) , and hybrids of both (Ash et al., 2019) . Second category includes criteria that is exactly the same as the evaluation metric, where notable approaches include expected error reduction (EER) (Roy & McCallum, 2001) and its more recent follow-up works (Killamsetty et al., 2021; Mussmann et al., 2022) .Despite the popularity of the first type of AL algorithms, existing works (Mittal et al., 2019; Hacohen et al., 2022) as well as our empirical analysis in Appendix A show that these methods often suffer heavily in low-budget settings, where the total (accumulative) sampling quota is less than 1% of the number of unlabeled data points, making them less suitable for the extreme data scarcity scenarios. In terms of the methods from the second category, their higher running time and reliance on the availability of a validation or hold-out set remain significant limitations, constraining their applicability in many data-scarcity scenarios as well. For example, EER (Roy & McCallum, 2001) re-trains the classifier for each candidate with all its possible labels, where in each time also evaluates the updated model on all the unlabeled data, making its runtime intractable especially for deep Under review as a conference paper at ICLR 2025 3 METHODOLOGY Different from the heuristics-based AL algorithms that optimize criteria such as diversity or uncertainty, DAO is built upon the EER formulation with the selection objective being the largest reduced error evaluated on the entire unlabeled set.More specifically, DAO majorly improves upon two aspects: (1) instead of re-training the classifier, we employ influence function (Cook & Weisberg, 1982) , a concept with rich history in statistical learning, to formulate the new candidate sample as a small perturbation to the existing labeled set, so that the model parameters can be estimated without re-training; and (2) instead of reserving a separate, relatively large labeled set for validation (Killamsetty et al., 2021) , we sample a very small subset directly from the unlabeled set and estimate the loss reduction through bias correction.Labeled Subset Model Estimation < l a t e x i t s h a 1 _ b a s e 6 4 = " F 1 7 l f q l w y K D b b f / 4 v 9 V T q W p x H 5 Q = " > A A A B 7 n i c b V D L S g N B E O y N r x h f U Y 9 e B o P g K e y K r 2 P Q i 8 c I x g S S J c x O Z p M h s 7 P D T K 8 Q Q j 7 C i w d F v P o 9 3 v w b J 8 k e N L G g o a j q p r s r 0 l J Y 9 P 1 v r 7 C y u r a + U d w s b W 3 v 7 O 6 V 9 w 8 e b Z o Z x h s s l a l p R d R y K R R v o E D J W 9 p w m k S S N 6 P h 7 d R v P n F j R a o e c K R 5 m N C + E r F g F J 3 U 7 E S i z z L d L V f 8 q j 8 D W S Z B T i q Q o 9 4 t f 3 V 6 K c s S r p B J a m 0 7 8 D W G Y 2 p Q M M k n p U 5 m u a Z s S P u 8 7 a i i C b f h e H b u h J w 4 p U f i 1 L h S S G b q 7 4 k x T a w d J Z H r T C g O 7 K I 3 F f / z 2 h n G 1 + F Y K J 0 h V 2 y + K M 4 k w Z R M f y c 9 Y T h D O X K E M i P c r Y Q N q K E M X U I l F 0 K w + P I y e T y r B p f V i / v z S u 0 m j 6 M I R 3 A M p x D A F d T g D u r Q A A Z D e I Z X e P O 0 9 + K 9 e x / z 1 o K X z x z C H 3 i f P 2 X Y j 6 A = < / l a t e x i t > [ Power Acquistion EER Estimation < l a t e x i t s h a 1 _ b a s e 6 4 = " c l L 2 T Q W k F v M V Q J K x 4 T C L A X 4 z u X U = " > A A A C A n i c b V B N S 8 N A E N 3 4 W e t X 1 J N 4 C R b B U 0 l E q s e i F 4 8 V 7 A c 0 I W y 2 m 3 b p Z h N 2 J 2 I J w Y t / x Y s H R b z 6 K 7 z 5 b 9 y 0 O W j r g 4 H H e z P M z A s S z h T Y 9 r e x t L y y u r Z e 2 a h u b m 3 v 7 J p 7 + x 0 V p 5 L Q N o l 5 L H s B V p Q z Q d v A g N N e I i m O A k 6 7 w f i 6 8 L v 3 V C o W i z u Y J N S L 8 F C w k B E M W v L N Q 3 e E w Y U R B e x n b o R h F I T Z Q + 6 z 3 D d r d t 2 e w l o k T k l q q E T L N 7 / c Q U z S i A o g H C v V d + w E v A x L Y I T T v O q m i i a Y j P G Q 9 j U V O K L K y 6 Y v 5 N a J V g Z W G E t d A q y p + n s i w 5 F S k y j Q n c W R a t 4 r x P + 8 f g r h p Z c x k a R A B Z k t C l N u Q W w V e V g D J i k B P t E E E 8 n 0 r R Y Z Y Y k J 6 N S q O g R n / u V F 0 j m r O 4 1 6 4 / a 8 1 r w q 4 6 i g I 3 S M T p G D L l A T 3 a A W a i O C H t E z e k V v x p P x Y r w b H 7 P W J a O c O U B / Y H z + A G V B m B g = < / l a t e x i t > ✓xi < l a t e x i t s h a 1 _ b a s e 6 4 = " q i F T v z u 6 0 T M 4 y O o n D i g x t 8 R S J y 0 = " > A A A B 9 X i c b V B N S 8 N A F H y p X 7 V + V T 1 6 W S y C p 5 K I V I 9 F L x 4 r m L b Q x r L Z b t q l m 0 3 Y 3 a g l 5 H 9 4 8 a C I V / + L N / + N m z Y H b R 1 Y G G b e 4 8 2 O H 3 O m t G 1 / W 6 W V 1 b X 1 j f J m Z W t 7 Z 3 e v u n / Q V l E i C X V J x C P Z 9 b G i n A n q a q Y 5 7 c a S 4 t D n t O N P r n O / 8 0 C l Y p G 4 0 9 O Y e i E e C R Y w g r W R 7 t N + i P X Y D 9 K n b M C y Q b V m 1 + 0 Z 0 D J x C l K D A q 1 B 9 a s / j E g S U q E J x 0 r 1 H D v W X o q l Z o T T r N J P F I 0 x m e A R 7 R k q c E i V l 8 5 S Z + j E K E M U R N I 8 o d F M / b 2 R 4 l C p a e i b y T y k W v R y 8 T + v l + j g 0 k u Z i B N N B Z k f C h K O d I T y C t C Q S U o 0 n x q C i W Q m K y J j L D H R p q i K K c F Z / P I y a Z / V n U a 9 c X t e a 1 4 V d Z T h C I 7 h F B y 4 g C b c Q A t c I C D h G V 7 h z X q 0 X q x 3 6 2 M + W r K K n U P 4 A + v z B 1 A L k w 8 = < / l a t e x i t > x i < l a t e x i t s h a _ b a s e = " n F U n U R M O c O J / V A j o p d n g l / Y = " > A A A B n i c b V B N S N A E J U r q / q h L B b B U l E q s e i F V Q e o W y m b p Z h N J I J / Q l e P C j i V / k z X / j t s B W x M P N b Y W Z e k E h h H W / n c L a + s b m V n G t L O t Q P j x q m T j V j D d Z L G P d C a j h U i j e R I G S d x L N a R R I g G t z O / / c S E b F x E n C / Y g O l Q g F o i l B M X / X L F r b p z k F X i a Q C O R r l d v E L M g q Z p M Z P T d B P M a B Z N W u q l h i e U j e m Q d y V N O L G z + a n T s m Z V Q Y k j L U t h W S u / p I a G T M J A p s Z R x Z J a m f i f x v P Y z o Z I U u W K L R W E q C c Z k j c Z C M Z y o k l l G l h b y V s R D V l a N M p R C Z d X S e u i t W q t f v L S v m j M I J A K + D B F d T h D h r Q B A Z D e I Z X e H O k + K O x + L o K T z x z D H z i f P y E j d = < / l a t e x i t > s i < l a t e x i t s h a 1 _ b a s e 6 4 = " H Q d 6 T 1 x + D W n C e c q / 3 X y f 1 p m m i H 4 = " > A A A B 7 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o l I 9 V j 0 4 r G C / Y A 2 l M 1 m 0 6 7 d Z M P u p F B K / 4 M X D 4 p 4 9 f 9 4 8 9 + 4 b X P Q 1 g c D j / d m m J k X p F I Y d N 1 v Z 2 1 9 Y 3 N r u 7 B T 3 N 3 b P z g s H R 0 3 j c o 0 4 w 2 m p N L t g B o u R c I b K F D y d q o 5 j Q P J W 8 H w b u a 3 R l w b o Z J H H K f c j 2 k / E Z F g F K 3 U 7 I 5 C h a Z X K r s V d w 6 y S r y c l C F H v V f 6 6 o a K Z T F P k E l q T M d z U / Q n V K N g k k + L 3 c z w l L I h 7 f O O p Q m N u f E n 8 2 u n 5 N w q I Y m U t p U g m a u / J y Y 0 N m Y c B 7 Y z p j g w y 9 5 M / M / r Z B j d + B O R p B n y h C 0 W R Z k k q M j s d R I K z R n K s S W U a W F v J W x A N W V o A y r a E L z l l 1 d J 8 7 L i V S v V h 6 t y 7 T a P o w C n c A Y X 4 M E 1 1 O A e 6 t A A B k / w D K / w 5 i j n x X l 3 P h a t a 0 4 + c w J / 4 H z + A M 8 B j 0 0 = < / l a t e x i t > . . . < l a t e x i t s h a 1 _ b a s e 6 4 = " H Q d 6 T 1 x + D W n C e c q / 3 X y f 1 p m m i H 4 = " > A A A B 7 X i c b V B N S 8 N A E J 3 4 W e t X 1 a O X x S J 4 K o l I 9 V j 0 4 r G C / Y A 2 l M 1 m 0 6 7 d Z M P u p F B K / 4 M X D 4 p 4 9 f 9 4 8 9 + 4 b X P Q 1 g c D j / d m m J k X p F I Y d N 1 v Z 2 1 9 Y 3 N r u 7 B T 3 N 3 b P z g s H R 0 3 j c o 0 4 w 2 m p N L t g B o u R c I b K F D y d q o 5 j Q P J W 8 H w b u a 3 R l w b o Z J H H K f c j 2 k / E Z F g F K 3 U 7 I 5 C h a Z X K r s V d w 6 y S r y c l C F H v V f 6 6 o a K Z T F P k E l q T M d z U / Q n V K N g k k + L 3 c z w l L I h 7 f O O p Q m N u f E n 8 2 u n 5 N w q I Y m U t p U g m a u / J y Y 0 N m Y c B 7 Y z p j g w y 9 5 M / M / r Z B j d + B O R p B n y h C 0 W R Z k k q M j s d R I K z R n K s S W U a W F v J W x A N W V o A y r a E L z l l 1 d J 8 7 L i V S v V h 6 t y 7 T a P o w C n c A Y X 4 M E 1 1 O A e 6 t A A B k / w D K / w 5 i j n x X l 3 P h a t a 0 4 + c w J / 4 H z + A M 8 B j 0 0 = < / l a t e x i t > . . . < l a t e x i t s h a 1 _ b a s e 6 4 = " M D K F t D j v Y Y d 7 a u h U l L + 8 b B H K 9 j I = " > A A A C F 3 i c b V C 7 T s M w F H X K q 5 R X g J H F o k J i i h K E C m M F C 2 O R 6 E N q o 8 p x b l q r j h P Z D l I V 9 S 9 Y + B U W B h B i h Y 2 / w W 0 z Q N s j W z o 6 5 1 5 f 3 x O k n C n t u j 9 W a W 1 9 Y 3 O r v F 3 Z 2 d 3 b P 7 A P j 1 o q y S S F J k 1 4 I j s B U c C Z g K Z m m k M n l U D i g E M 7 G N 1 O / f Y j S M U S 8 a D H K f g x G Q g W M U q 0 k f q 2 0 w t g w E R O z R t q U u n 1 V h 0 Q Y V H Q t 6 u u 4 8 6 A l 4 l X k C o q 0 O j b 3 7 0 w o V k M Q l N O l O p 6 b q r 9 n E j N K A c z M F O Q E j o i A + g a K k g M y s 9 n e 0 3 w m V F C H C X S X K H x T P 3 b k Z N Y q X E c m M q Y 6 K F a 9 K b i K q + b 6 e j a z 5 l I M w 2 C z g d F G c c 6 w d O Q c M g k U M 3 H h h A q m f k r p k M i C d U m y o o J w V t c e Z m 0 L h y v 5 t T u L 6 v 1 m y K O M j p B p + g c e e g K 1 d E d a q A m o u g J v a A 3 9 G 4 9 W 6 / W h / U 5 L y 1 Z R c 8 x + g f r 6 x f U P p 3 c < / l a t e x i t > 8 > > > > > > > > > > < > > > > > > > > > > : Unlabeled PoolEssentially, when considering each candidate from the unlabeled set, we optimize the EER framework on two of its core components, which are model parameter update and true loss estimation. Additionally, we upgrade EER, which only supports single sequential acquisition, to offer DAO in both single and batch acquisition variants by incorporating stochastic samplings to the sorted estimated loss reductions. We illustrate our algorithmic framework in Fig. 1 . In the following parts of this section, we first introduce a formal problem statement in §3.1, and then dive into each specific component of DAO from §3.2 to §3.5. 
problem statement: 
 The optimal sequential active learning acquisition function can be formulated as selecting a budget number of samples x train t from the current unlabeled set U t at each round t such thatEQUATIONwhere f * represents an optimal oracle that maps from any subset of the unlabeled data x Si ⊂ U t-1 to their ground-truth labels y Si , and f t|x S i ,y S i is the model that has been trained on the union of the current labeled set L t-1 and the current unlabeled candidates x Si ⊂ U t-1 . In addition,L true (f t|x S i ,y S i ) = 1 |Ut-1,i| x∈Ut-1,i ℓ(x; f t|x S i ,y S i )represents the loss estimator that can predict the unbiased error of f t|x S i ,y S i , where ℓ denotes the loss function. It is numerically the same as if f t|x S i ,y S i has been tested on the entire unlabeled set U t-1,i , where U t-1,i = U t-1 \ x Si . Such formulation represents the optimal AL criterion and aligns with any existing sequential active learning algorithm -of which the goal is to select the new data points that can most significantly improve the current model performance (Roy & McCallum, 2001) .Unfortunately, Eq. ( 1) cannot be directly implemented in practice. Because, first, we do not have access to the optimal oracle f * to reveal the labels y Si of x Si ⊂ U t-1 ; second, even if we had f * and therefore y Si , we cannot afford the cost of retraining model f t-1 on each L t-1 ∪ x Si to obtain the updated f t|x S i ,y S i ; and third, we do not have the unbiased true loss estimator L true , which demands evaluating f t|x S i ,y S i on the entire U t-1,i .Therefore, the goal of DAO is to solve the above challenges and efficiently and accurately approximate Eq. ( 1) for the sample selection strategy. It is also worth noting that, when x train t represents a set of newly acquired data points, the above formulation becomes eligible for batch active learning, which is more suitable for deep neural networks (Huang, 2021) .In this section, we address the first challenge when approximating Eq. ( 1). As we do not know the true label or true label distribution p(y|x, f * ) of each unlabeled sample x, the best we can do is provide an approximation for p(y|x). To this end, we introduce the concept of a surrogate (Kossen et al., 2021) , which is a model parameterized by some potentially infinite set of parameters θ. Specifically, p(y|x) can be approximated using the marginal distribution π(y|x) = E π(θ) [π(y|x, θ)] withUnder review as a conference paper at ICLR 2025 some proposal distribution π(θ) over model parameters θ. In other words, we have:p(y|x) ≈ θ π(θ)π(y|x, θ) dθ (2)As the sample selection process continues, new labeled points should also be used to train and update the surrogate model π(θ) for better approximation of the true outcomes.Although ideally, a more capable surrogate is preferred for better ground truth approximations, we acknowledge that the choice of surrogate model can be very sensitive to the computational constraints. Therefore, if running time is at center of the concerns during sample acquisitions, using f t at step t also as the surrogate could be an efficient alternative, as we don't need to update a second model, nor do we need to run forward pass on the both models. However, this will come with the cost that π t never disagrees with f t , which causes performance degradation for the unbiased true loss estimation, which will be illustrated with more details in §3.4. Therefore, in short, we do not recommend replicating f t as surrogate in practice, unless the computational constraint is substantial.At acquisition round t, suppose we have labeled set L t-1 and unlabeled set U t-1 as the results from the previous round t -1, and new sample x i ∈ U t-1 that is currently under consideration for acquisition, the goal of this section is to estimate the parameters of model f t|xi,yi that could has been obtained after training f t-1 on the combined dataset {L t-1 ∪ x i }. In other words, if we suppose the conventional full training converges to parameters θxi , we have:EQUATIONwhere recall that ℓ(x; θ) denotes the loss of θ on x. The core of our approach is that, instead of retraining as showed in Eq. ( 3), we can approximate the effect of adding a new sample as upweighting the influence function by Following Cook & Weisberg (1982) , we have the influence function defined as:I up,params (x i ) := d θϵ,xi dϵ ϵ=0 = -H -1 θ ∇ θ ℓ(x i ; θ)where H θ is the positive definite Hessian matrix (Koh & Liang, 2017) . Next, we can estimate the model parameters after adding this new sample x i , as:θxi -θ ≈ 1 |L t-1 | + 1 I up,params (x i ) = - 1 |L t-1 | + 1 H -1 θ ∇ θ ℓ(x i ; θ)where ∇ θ ℓ(x i ; θ) could be approximated as the expected gradient of sample x i : By a slight abuse of notation of the training loss function ℓ, we denoteEQUATIONIn Eq. ( 4), ŷk and pk represent model's label prediction and likelihood (e.g. confidence) respectively while K represents the total number of classes in the ground truths.In practice, the inverse of H θ cannot be computed due to its prohibitive O(np 2 + p 3 ) runtime (Liu et al., 2021) , with p being the number of model parameters. The computation unavoidably becomes especially intensive when f is a deep neural network model (Fu et al., 2018) . Luckily, we have two optimization methods, conjugate gradients (CG) (Martens et al., 2010) and stochastic estimation (Agarwal et al., 2017) at our disposal.Conjugate gradients. As mentioned earlier, by assumption we have H θ ≻ 0 and ∇ θ ℓ(x ′ ; θ) as a vector. Therefore, we can calculate the inverse Hessian vector product (IHVP) through first transforming the matrix inverse into an optimization problem, i.e.H -1 θ ∇ θ ℓ(x i ; θ) ≡ arg min t t T H θ t -v T tand then solving it with CG (Martens et al., 2010) , which speeds up the runtime effectively to O(np).Under review as a conference paper at ICLR 2025 Stochastic estimation. Besides CG, we can also efficiently compute the IHVP using the stochastic estimation algorithm developed by Agarwal et al. (2017) . From Neumann series, we have A -1 ≈ ∞ i=0 (I -A) i for any matrix A. Similarly, suppose we define the first j terms in the Taylor expansion of H -1 θ asH -1 θ,j = j i=0 (I -H θ ) i = I + (I -H θ )H -1 θ,j-1 we have H -1 θ,j → H -1 θ as j → ∞.The core idea of the stochastic estimation is that the Hessian matrix H θ can be substituted with any unbiased estimation when computing H -1 θ . In practice, we sample n ihvp data points from the existing labeled set L t-1 and use ∇ 2 θ ℓ(x i ; θ) as the estimator of H θ (Liu et al., 2021) . Notice that since n ihvp is usually very small (in our experiments we used n ihvp = 8), it does not create a constraint on the size of the current labeled set, which does not interfere with the low-budget settings.Finally, we can approximate the model parameters after the addition of x i asEQUATIONwhich does not require any re-training. And we will demonstrate in §5.2 that this parameter update strategy provides much better approximations than the naive single backpropagation as seen in the existing AL literature (Killamsetty et al., 2021) .Referring back to Eq. ( 1), the last challenge that we need to address is to gain access to the unbiased true loss estimator L true . In other words, we want to predict the true performance of f t|xi,yi on the unlabeled set U t,i without exhaustive testing. Strictly, such evaluation cannot be drawn until f t|xi,yi is evaluated on the entire unlabeled set U t,i . However, this is infeasible in practice.Such approximation is typically carried out in other approaches (Killamsetty et al., 2021; Mussmann et al., 2022) by randomly sampling a labeled validation set V at the beginning of the entire acquisition process, which will later be used for evaluations in all the subsequent acquisition episodes. Despite the simplicity as well as being i.i.d., which makes the estimated loss unbiased by nature, this approximation method suffers from large variance as the size of V is usually much smaller than U, which unavoidably hurts the acquisition performance. It is also contradictory to the goal of AL in general, especially under the low-budget settings, as discussed in §1.Different from the existing works, we propose to sample a subset C from current L t-1 in each acquisition round based on an alternative acquisition function, and then correct the bias in the loss induced from this acquisition function. In the meantime, we also want to keep the variance low, so that the final corrected loss enjoys both low bias and low variance, which is more preferable than the zero bias but high variance that the random i.i.d. sampling has.Specifically, continuing with the notations from §3.1, let C = {x t,1 , . . . , x t,m , . . . , x t,n C }, where C ⊂ U t-1 , be the subset containing n C samples selected for this true loss estimation at each round t. Farquhar et al. (2021) shows that if x t,m is sampled in proportion to the true loss of each data point, the bias originated from this selection can be corrected through the Monte Carlo estimator RLURE 1 . Following our notations, it takes the form:RLURE = 1 n C n C m=1 v m ℓ (x t,m ; f ) (6)where recall that ℓ denotes the loss of f , and the importance weight v m isEQUATIONwith q * t (m) being the acquisition distribution of index m at round t. Importantly, the variance can be significantly reduced if the acquisition distribution q * t (m) is proportion to the true loss of each Under review as a conference paper at ICLR 2025 data point. Again, this is not feasible as we do not have access to the labels for U t-1 . However, following Kossen et al. (2021) , we can approximate q * t (m) withq t (m) = - y π(y|x t,m ) log f (x t,m )for classification tasks when the loss function is the cross-entropy loss, and where π is conveniently just our surrogate discussed in §3.2. Referring back to the discussion we had on choosing a good surrogate π, with f (x) being designed to approximate p(y|x) as well, the surrogate π should ideally be different from f so that more diversity is introduced in the acquisitions.To put all components together, our loss correction process involves selecting samples in C followingEQUATIONwhere π t-1 is the surrogate model π at round t-1. Finally, the corrected loss s i can be approximated using RLURE asEQUATIONwhere vm , which depends on the choice of x t,m , is the approximated version of the original v m defined in Eq. ( 7). Specifically, vm takes the formEQUATIONwhere q t (m) is the acquisition function defined in Eq. ( 8).In §3.1, we briefly discussed that when x train t represents a set of data points (instead of a single one), the formulation in Eq. (1) essentially represents the batch active learning scenario. Suppose the acquisition budget per round is k, although selecting the top k samples with the lowest estimated losses (or highest expected error reduction) is straightforward, this approach is sub-optimal. This is because top-k acquisition, while effective to some degree due to its greedy nature, overlooks the crucial interactions among data points in batch acquisitions. Specifically, while aiming to select the most informative unlabeled points, top-k acquisition may lead to redundant choices, diminishing the overall benefit of the acquisition.Algorithm 1 Direct Acquisition Optimization (DAO)input Episode t, unlabeled set U t-1 , labeled set L t-1 , model f t-1 , surrogate π t-1 , budget k, n ihvp ( §3.3), and n C ( §3.4) output Acquisition set A t = {x train t,1 , . . . , x train t,k } ▷ Eq. (1) 1: Approximate p(y|x) for all x ∈ U t-1 ▷ §3.2, Eq. (2) 2: Initialize array S where |S| = |U t-1 | 3: for i = 1 to |U t-1 | do 4: Let U t,i = U t-1 \ {x i } 5:Randomly sample n ihvp data points from U t,i 6:Approximate parameters of f t|xi,yi ▷ §3.3, Eq. ( 5) 7:Acquire n c samples from U t,i ▷ §3.4, Eq. (8) 8:Compute s i and add to S ▷ §3.4, Eq. (9) 9: end for 10: Sort S in ascending order 11: if k > 1 then 12:Perturb S ▷ Methods showed in §3.5 13: end if 14: Return top-k samples in S as A t Inspired by Kirsch et al. (2021) , we propose to similarly perturb the original ranking of the estimated true losses so that the batch sampling provides better acquisitions when the most informative data points may be duplicated. Suppose at acquisition episode t, we rank the set of estimated true loss of each unlabeled data point in ascending orders as { ltrue,i } xi∈Ut-1 , such that ltrue,i ≤ ltrue,j , ∀i ≤ j and x i , x j ∈ U t-1 , we can perturb the ranking with three strategies: soft-rank, soft-max, and power acquisition, to improve batch performance from the naive top-k sampling.Soft-rank acquisition. Soft-rank acquisition relies on the relative ordering of the scores while ignoring the absolute score values. It samples the data point ranked at index i with probability p softrank (i) = i -β , where β is the "coldness" parameter and is kept as 1 throughout this paper. It is not hard to notice that p softrank (i) is invariant to ltrue,i , as long as the relative ranking remains the same. More conveniently, with sampled Gumbel noise ϵ i ∼ Gumbel(0; β -1 ), taking the top-k data points from the perturbed ranked list lsoftrank true,i = -log i + ϵ i is equivalent to sampling p softrank (i) without replacement (Huijben et al., 2022) .Soft-max acquisition. In contrast to soft-rank, soft-max acquisition uses the actual scores, i.e., the estimated true losses, instead of their relative orderings. However, this acquisition does not rely on the semantics of the actual values, resulting in the transformed true loss simply being: lsoftmax true,i = ltrue,i + ϵ i where ϵ i remains the same Gumbel noise as in the soft-rank acquisition. Statistically, choosing the top-k data points from this perturbed ranked list is equivalent to sample from p softmax (i) = e βi without replacement.Power acquisition. While neither soft-rank or soft-max acquisitions take the semantic meaning of the actual score values into account when designing the acquisition distribution, power acquisition uses the value directly when determining the perturbed values. Specifically, the power acquisition perturbs the scores as lpower true,i = log ltrue,i + ϵ i where again ϵ i is the Gumbel noise, and choosing the top-k indices from this new list is equivalent to sampling from p power (i) = i β without replacement. Results comparing DAO with different batch acquisition strategies discussed above are showed in Appendix B. Combining all the components, the pseudocode of DAO is summarized in Algorithm 1. 
experiments: 
 We evaluate DAO on seven classification benchmarks including digit recognition datasets MNIST (LeCun et al., 1998) , Street-View House Numbers recognition (SVHN) (Sermanet et al., 2012) , object classification datasets STL-10 (Coates et al., 2011) , CIFAR-10, CIFAR-100 (Krizhevsky et al., 2009) , as well as domain-specific datasets Fashion-MNIST (Xiao et al., 2017) and Stanford Cars (Cars196) (Krause et al., 2013) .Baselines. To ensure fair comparisons, besides baseline methods that we empirically surveyed in Appendix A, we also include other state-of-the-arts AL methods, including Deep Bayesian Active Learning (DBAL) (Gal et al., 2017) and GLISTER (Killamsetty et al., 2021) , where GLISTER is a direct competitor that also optimizes the EER framework. For all the baselines, we used the default/recommended parameters and their official implementations if publically available. In terms of earlier works such as least confidence (Lewis, 1995) , minimum margin (Scheffer et al., 2001) , and maximum entropy (Settles, 2009) , we used the peer-reviewed deep active learning framework DeepAL+ (Zhan et al., 2022) . All experiments are repeated ten times with different random seeds.Implementation details. Throughout the section, we set ResNet-18 (He et al., 2016) as the model f to be trained from scratch. We employed VGG16 (Simonyan & Zisserman, 2014) , initialized with random weights, as our surrogate π. We used stochastic estimation (Agarwal et al., 2017) when estimating the updated model parameters, as discussed in §3.3. We choose n ihvp = 8 when approximating the unbiased estimator of H θ , and set n C = 16 for biased loss correction as in §3.4.Digit recognition. First, we demonstrate DAO's effectiveness through two digit recognition benchmarks: MNIST (LeCun et al., 1998) and SVHM (Sermanet et al., 2012) . MNIST is a collection of handwritten digits consisting of 60k training and 10k test images, while SVHN is a more challenging dataset containing over 600k real-world house numbers images taken from street views. Both datasets contain 10 classes corresponding to digits from 0 to 9. Based on insights from Appendix A, we define a general rule of low-budget setting as one image per class, which translates to initial label size |L MNIST init | = 10 and per-episode budget B MNIST = 10 for MNIST. Given that SVHN is more challenging, and there are ten times more unlabeled images than in MNIST (600k vs. 60k), we experiment both 10 and 100 for our initial labeled size and per-round budget for SVHN. The results are shown in Fig. 2b and 2c . The last part of our experiments involves case studies on applying DAO to domain-specific tasks, which simulates many real-world applications. Specifically, we use Fashion-MNIST (Xiao et al., 2017) and StanfordCars (Krause et al., 2013) , also known as Cars196, in this experiment. FashionMNIST is structure-wise similar to MNIST, comprising 28×28 images of 70k fashion products from 10 categories, with 7k images per category. The training set contains 60k images, while the test set includes the rest. StanfordCars is a large collection of car images, containing 16,185 images with a near-balanced ratio on the train/test split, resulting in 8,144 and 8,041 images for training and testing. There are 196 classes in total, where each class consists of the year, make, model of a car (e.g., 2012 Tesla Model S). The results of both datasets are shown in Fig. 2g and 2h . Results discussion. From Fig. 2 , we notice that the proposed DAO outperforms popular AL state-of-the-arts by a clear margin across all seven benchmarks. Especially, with SVHN, when the budget is extremely low (B = 10, which is 0.0017% of the unlabeled size), DAO leads the performance by a very large gap, indicating its superior capability in the low-budget setting. Such performance does not degrade much as the budget constraint is relaxed. As shown in Fig. 2c , DAO still performs relatively well. The only experiment that DAO does not improve as much is the StanfordCars. However, the accuracy improvement from DAO is more smooth and has less variance, indicating better robustness when applied to the more challenging (StanfordCars has 196 classes) applications.Under review as a conference paper at ICLR 2025To further evaluate the capabilities of the proposed DAO beyond its targeting focus on low-budget AL, we conducted additional experiments with higher budgets on the CIFAR-100 and STL10 datasets. Specifically, we keep the same experimental settings as previously, with the same initial labeled set and per-round acquisition budget, and repeated the process five times with different random seeds. However, we extended the number of rounds in each acquisition from 10 to 50, increasing the budget by five times. And to make the plot more clear, we plot every five rounds. As shown in Fig. 3 , DAO consistently outperforms all other baselines throughout the entire acquisition process, demonstrating superior performance across both low and high budgets.5 COMPONENT ANALYSIS AND ABLATION STUDIES 
ablations on different surrogates: 
 To further understand how the surrogate model impacts the performance of DAO, we conducted additional experiments on CIFAR-10 using different surrogates. Specifically, we compared:(1) VGG16: The surrogate model currently used in the paper draft.(2) ResNet18: An efficient variant of DAO where the main model under training serves as the surrogate, i.e., π t = f t . In this case, the equation for approximating q * t (m), the acquisition distribution of candidate index m at round t (the equation between lines 225 and 226), reduces from cross-entropy to entropy. (3) Sim-pleCNN: A simpler version of ResNet18 with six convolution blocks, each containing one Conv layer followed by BatchNorm and ReLU. and (4) Oracle: An unrealistic setting assuming access to an oracle surrogate model. We used the same experimental setup with CIFAR-10 as in our draft: starting with 10 labeled samples, acquiring 10 samples per round, and continuing for 10 rounds. The was repeated five times with different random seeds.As shown in Fig. 4 , DAO with oracle surrogate performs the best, followed by VGG16 and SimpleCNN. ResNet18 performs the worst among all DAO variants, which aligns with our expectation that performance degrades when π t never disagrees with f t . However, all DAO variants outperform the random and GLISTER baselines by a clear margin. It is worth noting that while the oracle surrogate achieves the best results, the improvement over VGG16 and SimpleCNN is not substantial. We think this is likely because, when selecting samples for the unbiased loss estimation, the acquisition distribution q * t (m) approximated with q t (m) =y π(y|x t,m ) log f (x t,m ), does not solely depend on the surrogate quality. Although in the unrealistic case of an oracle surrogate, this creates an disadvantage, but in practical scenarios, this approximation provides better robustness in preventing the negative impact of poor quality of surrogate on unbiased loss estimation, especially in early stages where models might overfit. Additionally, we provide evaluations of the predictive accuracy of different surrogates on unlabeled set in Table 1 . The results show that when the surrogate differs from the model being trained (i.e., f ̸ = π), its performance does not improve as significantly as that of f , indicating from a different angle that DAO specifically optimizes the sample selection that enhances the performance of the target model f .First, we assess if estimating the model parameters updates through modelling the effect of adding a new sample as upweighting the influence function provides a more accurate model performance approximation than using single backpropagation as seen in GLISTER (Killamsetty et al., 2021) . Specifically, we conduct the experiments on CIFAR-10 ( Krizhevsky et al., 2009) , with initial labeled size |L CIFAR-10 init | = 100 (randomly sampled from the train split), per-episode budget B CIFAR-10 = 1, and number of acquisition episode E = 25. We compare the updated models performance (accu-Under review as a conference paper at ICLR 2025 racy) on the test split of CIFAR-10. Different from the experiments in §4, we do not apply any AL algorithm when acquiring the sample in each round. Instead, we randomly choose B sample in each acquisition round from the unlabeled set and then update the models through both methods with the same selected sample. To access the difference between models updated with our influence function-based method and single backpropagation, we compute the mean squared error (MSE) between the performance of each model and the model updated by conventional full training, which is defined in Eq. (3). As shown in Fig. 5a , the proposed method provides more accurate (smaller mean and median) and more robust (smaller std.) model approximations than single backpropagation, contributing to the performance gain we observe in §4.Next, we conduct ablation studies on replacing the proposed loss estimation ( §3.4) with the average loss of randomly sampled data points. More specifically, we replace the estimated loss s i from averaging the corrected loss (Eq. ( 6)) of the acquired samples via an alternative acquisition criteria (Eq. ( 8)) with averaging losses of the samples acquired uniformly, i.e., at round t, we have s random i = 1 Mrandom Mrandom m=1 ℓ(x t,m ; f t ) where x t,m ∼ U (1, |U t,i |). We choose two M random = 16 and 256, where former provides a direct comparison with our proposed loss estimation approach, and latter represents a brute-force solution that works relatively well but is often infeasible in practice due to intensive running time. The results are shown in Fig. 5b . We see that the proposed method performs even better than the conventional random-sampling loss estimation with large sampling size, while computationally being only 1/8 of the run time. Additionally, the variance of our method is much smaller, indicating more robust loss estimation and thus more robust acquisition performance.We conducted additional ablation studies comparing various stochastic sampling methods as detailed in §3.5. Results are documented in Appendix B. Our findings reveal that the proposed algorithm, even when simply selecting the top k samples without applying any of the stochastic strategies, outperforms existing methods. Performance further improves with the implementation of these sampling strategies. It is important to note that we have not designed specific sampling strategies for our algorithm; instead, we utilized existing methods to showcase the efficacy of DAO framework.In this section, we analyze the criterion optimized by DAO and compare it to common criteria such as diversity and uncertainty, using visual representations of the data samples collected by DAO. The detailed plots are available in Appendix C. Throughout multiple acquisition rounds, the data selected by DAO demonstrate notable diversity with uniform distribution across the sample space. However, in contrast to traditional uncertainty-based methods, selections within a single round by DAO also incorporate elements of uncertainty. This hybrid approach explains the performance improvements observed in §4 over algorithms that solely focus on diversity or uncertainty. 
conclusions: 
 In this paper, we introduced Direct Acquisition Optimization, a novel algorithm designed to optimize sample selections in low-budget settings. DAO hinges on the utilization of influence functions for model parameter updates and a separate acquisition strategy to mitigate bias in loss estimation, represents a significant optimization of the EER method and its modern follow-ups. Through empirical studies, DAO has demonstrated superior performance in both low and higher budget settings, outperforming existing methods by a significant margin across seven datasets. 
 
 Appendix: LURE stands for Levelled Unbiased Risk Estimator 



Reviews: review: title: title: Interesting active learning algorithm and impressive experimental results
main_review: main_review: This paper presents Direct Acquisition Optimization (DAO), a novel active learning algorithm based on expected error reduction (rather than heuristics such as example diversity or model uncertainty).  DAO employs influence functions to approximate the effect of training on candidate unlabeled data, and DAO samples from the unlabeled data for loss estimation and then applies bias correction via LURE (instead of setting aside a validation set beforehand).

The results are impressive, showing DAO out-performing many baseline algorithms including BALD, BADGE, DBAL, and GLISTER on seven benchmark datasets in low-budget settings with a small number of rounds of data acquisition.

The paper is well written, and the topic of active learning is explicitly included in the theme for this workshop.  So, this paper should be accepted.

Nit-picks:
1. Line 60: Is the reference to the appendix intentional?
2. Line 66: "could has been" -> "could have been"
3. Line 70: Delete "recall that"
4. Line 86: This line refers "back" to an equation that hasn't been encountered yet and is in the appendix.  It feels like the paragraphs of the paper have been shuffled and some of the references make less sense now.  The subsequent paragraphs also refer to notation and discussion in appendix C.
5. Line 162: The second sentence in the conclusion should probably be split into two sentences.
6. Line 335: Delete the commas on this line.
7. Line 337: Consider rewriting this sentence as "Hybrid methods, such as BADGE [4], combine both uncertainty and diversity criteria."
8. Line 340: "an hybrid" -> "a hybrid"
title: title: Review of DAO
main_review: main_review: The article Direct Acquisition Optimization (DAO) for Low-Budget Active Learning offers insightful and innovative research proposals in the field of active learning. In general, its approach utilizing  influence functions to update the model parameter, as opposed to retraining the predictor model at each iteration, is innovative and clever. DAO has the potential to be advantageous in overcoming common problems in the EER-methods literature. In particular, it addresses two issues in EER methods: (i) the need to hold out a validation dataset and (ii) the computational expense of retraining the model for each candidate observation. 

DAO's contribution in (i) addresses the fundamental motivation of active learning: a study should utilize its labelling-budget, often extremely constrained, on labelling the most informative observation. As such, labelling and preserving a validation set not used in the training of the predictive model may be wasteful. DAO cleverly overcomes this by its non-need to retrain and revalidate. Note that reading Appendix C was needed to fully understand why this works in their methodology. The author's methods builds on the idea of surrogates, an idea from the related active testing literature. I am not entirely familiar with the active testing literature - it is similar yet different to the active learning literature - but their use of surrogates overcomes the issue of not knowing the true label distribution with a good approximation. It would make the author's methods more clear if their use of surrogates is further explained.

DAO's needlessness to retrain the model on each candidate observation overcomes issue (ii). As EER methods have not been commonplace in deep neural networks due to the large computational cost associated with this training, DAO's circumventing of this expensive retraining has the potential contribute to the active learning literature at large. Section C.3 and E on computational optimization well explains why their parameter update strategy approximates the model parameters well.

Overall, the article outlines their research proposal very well and provides novel methodological improvements to the active learning literature. The following comments below outline additional sections that I found unclear.

In section 2.1, $\hat{\theta}_{x_i}$ is defined in equation (1) as the parameter to which the training model converges to, but

$\hat{\theta}_{\epsilon, x_i}$ 
should be specified in the influence function.

In section 2.2, the authors define a candidate subset $\mathcal{C}$ for oracle labelling as being within the labelled dataset $\mathcal{L}$. However, they later define $\mathcal{C} \subseteq \mathcal{U}$.

The axes of Figure (2) are unclear.

I see from the experimental results of Section 3 that DAO indeed provides a predictive advantage over the other models with less predictive variance. It would be interesting to see the theoretical foundations behind this result, or if this was just the case in the experiments. Likewise, Section E.4 show that DAO incorporates elements of diversity in its acquisition procedure. The connection is clear from the image in Section D but the reasoning behind this finding is not clear. A formalization of how/why DAO integrates acquisition diversity would strengthen the author's promotion of DAO.