A Lagrangian Duality Approach to Active Learning
Authors: Juan Elenter
Navid Naderializadeh
Alejandro Ribeiro
Venue: NeurIPS 2022 Accept (2022)
Keywords: Active Learning
Lagrangian Duality
Constrained Learning
Convex Optimization

Abstract: We consider the pool-based active learning problem, where only a subset of the training data is labeled, and the goal is to query a batch of unlabeled samples to be labeled so as to maximally improve model performance. We formulate the problem using constrained learning, where a set of constraints bounds the performance of the model on labeled samples. Considering a primal-dual approach, we optimize the primal variables, corresponding to the model parameters, as well as the dual variables, corresponding to the constraints. As each dual variable indicates how significantly the perturbation of the respective constraint affects the optimal value of the objective function, we use it as a proxy of the informativeness of the corresponding training sample. Our approach, which we refer to as Active Learning via Lagrangian dualitY, or ALLY, leverages this fact to select a diverse set of unlabeled samples with the highest estimated dual variables as our query set. We demonstrate the benefits of our approach in a variety of classification and regression tasks and discuss its limitations depending on the capacity of the model used and the degree of redundancy in the dataset. We also examine the impact of the distribution shift induced by active sampling and show that ALLY can be used in a generative mode to create novel, maximally-informative samples.

A Lagrangian Duality Approach to Active Learning
Juan Elenter University of ceansylvania el elenterdeaas upenn. edu
Navid NaderiAlizadeh University of Pennsylvania nnaderi @seas upenn edu
Alejandro Ribeiro University Pennsylvania ar aribeirodseas. upenn edu
Abstract
We consider the pool-based active learning problem, where only subset of the training data is labeled, and the goal is to query batch of unlabeled samples to be labeled so as to maximally improve model performance. We formulate the problem using constrained learning, where set of constraints bounds the performance of the model on labeled samples. Considering a primal-dual approach, optimize the primal variables, corresponding the model parameters, as well the dual variables, corresponding to the constraints. As each dual variable indicates how significantly the perturbation of the respective constraint affects the optimal value the objective function, we use it as a proxy of the informativeness the corresponding training sample. Our approach, which refer to Active Learning via Lagrangian dualitY, or ALLY, leverages this fact to select a diverse set of unlabeled samples with the highest estimated dual variables as our query set. We demonstrate the benefits of our approach in a variety of classification and regression tasks and discuss its limitations depending on the capacity of the model used and the degree of redundancy in the dataset. We also examine the impact of the distribution shift induced by active sampling and show that ALLY can be used in a generative mode to create novel, moximally-informatte samples.
Introduction
One the key drivers of the recent progress in machine learning is the availability of massive, high-quality datasets, which enables training models comprising millions, even billions, of parameters 2 Nevertheless, some areas, such as healthcare, obtaining labeled training data is challenging and/or expensive [ 5 (6). This has given rise to class of approaches, collectively referred to as active learning, whose goal is to minimize the labeling effort for training machine learning models.
Active learning methods aim to improve data efficiency by querying the labels of samples presumed informative, in feedback-driven fashion. In recent years, the pool-based active learning setting, in which queries are drawn from a large, static pool of unlabeled samples has drawn significant attention 7 This is due the abundance of such unlabeled pools and the compatibility of the pool-based setting with the training of deep neural networks.
Most active learners rely on defining notion of informativeness of given sample, such as model uncertainty 10 expected model change [22 [3] expected error reduction [4 [5] However, in the batch setting, where multiple samples are queried simultancously. not contemplating the information overlap between the samples can lead to sub-optimal queries. Consequently, batch diversity needs to be taken into account, often at the expense of individual sample informativeness 16).
In this paper, we demonstrate how a constrained learning formulation of the problem enables the use of Lagrangian duality for detecting informative samples. In particular, we bound the loss incurred by
Conresponiing author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

each sample, and use the dual variables associated to these constraints as measure of informativeness. We show that dual variables are directly related to the variations of the average optimal loss over the entire data distribution, which motivates our approach.
Through an iterative primal-dual strategy, we optimize the model parameters as well the dual variables. We then leverage the learned embedding space [17 [8] to train a dual regression head that estimates the dual variable associated to each unlabeled sample. Our proposed active learning approach, which we refer to as Active Learning via Lagrangian dualitY, or ALLY can then be used to select a diverse and informative set of samples. We also argue that, under certain conditions, the strategy put forward is not severely impacted by the distribution shift induced by active sampling.
We evaluate the performance of ALLY on suite of classification and regression tasks, and show that it performs similar to or better than state-of-the-art batch active learning methods. We further demonstrate how the trained backbone, alongside the dual regression head, enable the generation of novel samples that can be optimized to be maximally informative, shedding light on the interpretability of the proposed active learning framework.
2
Related Work
2.1 Active Learning
The literature on active learning is voluminous and myriad of strategies for the pool-based setting have been proposed [7]. In what follows, we describe some of the approaches most connected to our work.
simple way of measuring model uncertainty by computing the entropy of the predicted class distribution. Designed for the sequential case, Entropy Sampling [10] selects the unlabeled sample with highest associated output entropy. Among the relevant methods is BADGE [15,, which employs a lower bound on the norm of the gradients in the final layer of the network as measure of informativeness. BADGE balances diversity and informativeness by using the K-MEANS+ seeding algorithm to select a batch with large Gram determinant in the gradient space. BAIT [19 builds on traditional, Information Matrix based methods to efficiently select a batch that optimizes a bound on the MLE error in two stage manner. Other methods that propose notions of informativeness BALD (20), which uses the mutual information between predictions and model parameters as an uncertainty measure, and Learning Loss (21]. which trains loss prediction module and queries the samples that hypothetically generate high errors (and, thus, large model updates). VA [22] and WAAL 23 are methodologically similar to (21) in the sense that they all use a multipartite system consisting of a feature encoder, a prediction head and an auxiliary estimator. This is also the case for the strategy presented in this paper.
Some Diversity-promotinn popular approach is to cluster the samples of the unlabeled set and then select informative points from each cluster 24 25 26). In [27], Monte Carlo sampling is used to simulate sequences of length b of the sequential algorithm, and then best-matching combination of the sequences is used to build a batch. A simpler approach is to select the most informative points after a stochastic perturbation of the informativeness scores (28).
approaches are compatible with many informativeness measures. A
Some methods do not enforce informativeness explicitly, but rather query a set of data points that is maximally representative of the entire unlabeled set. Coreset [8. for instance, formulates pool- based active learning as a core-set selection problem, and aims to identify set of points that geometrically covers the entire representation space. To do this, Coreset selects the batch that when added to the labeled set, minimizes the maximum distance between labeled and unlabeled examples. Coreset is compatible with deep neural networks and can be used in both regression and classification settings. Similarly, DAL 229] emphasizes representativeness by framing active learning as binary classification task and selecting queries that maximize the similarity between the labeled and unlabeled set.
2.2 Constrained Learning
The need to tailor the behavior of machine learning systems has led the development of constrained learning theory. A common approach is to use regularization, that is, to modify the learning objective

---

formulate step (ii) above an so as to promote certain requirements. However, choosing the level of regularization through dimensionless weight can be more challenging than setting a constraint level. Furthermore, recent works 30
show that, from a PAC (Probably Approximately Correct) perspective, learning under requirements is as hard as classical learning and that it can be done in practice through primal- dual learners. This has led to numerous applications across several areas of MI such as federated learning [33, fairness [30], stability of neural networks [34 35), adversarial robustness [36] and data augmentation [37
31 32
3 Problem Formulation
3.1 Batch Active Learning
Let D denote a probability distribution over data pairs (æ, y). where x E X S. RDD represents a feature vector (c.g.. the pixels of image) and y E y _ R represents a label or measurement, In classification tasks, y is a subset of N, whereas in regression, ) R.
Initially, L { yx) N2 of data pairs, labeled samples, is available, coming from probability distribution D. This set is used to learn predictor f(x; L) : X - y from a hypothesis class FF. Note that dependence or queries. is selected from a pool of unlabeled samples Ut = [ and sent to an oracle for labeling. The goal is to the select the batch that minimizes the expected loss the natural data distribution. More precisely, we formulate the Batch Active Learning (BAL) problem as
the set used to learn is made explicit. Then, batch B of samples,
B
arg min min E(x,)~ ( (f(x; CUXx; v)],
(BAL)
BÇU: [Bi JEF
where 6, referred to the budget, represents the maximum cardinality of B and {: y x y loss function (e.g., cross-entropy loss or mean- squane error).
is
This process is typically repeated multiple times. At each iteration, two main steps are performed: (i) selecting B and updating the sets: (()) = ((0-1) U B and (1(0) = (t(1)) B, and (ii) obtaining the predictor f with the aggregate set of labeled samples C(O) Steps (i) and (ii) correspond to the outer and inner minimization problems in (BAL), respectively. In what follows, focus on single iteration, and thus obviate the dependence on the iteration ć and the set used to ease the notation.
3.2 Constrained Statistical Learning
Most active learning methods in the literature unconstrained Statistical Risk Minimization (SRM) problem
8
15
20
5
7
38
min E( [ (=) v)]
(SRM)
JEF
Our approach, alternatively, uses a Constrained Statistical Learning (CSL) formulation,
min JEF
(( [e ())
(CSL-a)
s.t. E' (f(x),)) S <(x); a.c.
(CSL-b)
where 8' 3 x
R is a secondary loss function, X - IR is mapping from each data point to a corresponding constraint upper bound, and Da denotes the marginal distribution over X. Note that the objective function in (CSL-a) is the same as in (SM)). but the secondary loss is required to be bounded D almost everywhere.
Letting X= X + denote the dual variable function, the Lagrangian associated to CSLL can be written as
(J = B(awDD [([(()) +
JxY (())((([(()))) - <()))((( dady
= B [((()),)) A(x)) ((a) -
where it is implicitly assumed that the conditional distribution p(y(æ: is a Dirac delta distribution, i... y a deterministic function of æ. This leads the dual problem,
D* max min L (f, A(x))
(D-CSL)
AEA JEF
3

---

where == (A])(z) 2 0, De a.e... There are three main motivations for this infinite programming formulation:
1. Access to variations of P*: As show in Theorem 3.2 this formulation gives access to (e(x)) enabling the use of dual variables as an indicator the informativeness of the training samples.
2. Considering both average and worst-case losses:
The most informative samples often lic in the tails of the distribution D. Those samples appear less frequently in the dataset and thus, models obtained by solving (SRM) achieve low average emrors without learning to classify/regress them correctly. Our formulation bridges the gap between the (SRM) and worst-case Feasibility Statistical Learning (FSL) formulation,
p==min 0 FEF
(FSL-a)
s.t. e(f(z). S <(x), Dz-a.c
(FSL-b)
which considers worst-case loss.
3. Adaptive regularization: For fixed dual variable X, the Lagrangian is a regularized objective, where e' acts regularizing functional. Thus, the max-min formulation in D-CSL can viewed as a regularized minimization, where the regularization weight updated during the training procedure according to the degree of constraint satisfaction or violation.
The dual problem be interpreted finding the tightest lower bound P*. In the general case, D < P*, which known as weak duality. Nevertheless, under certain conditions, D* attains P (strong duality) and
derive a relation between the solution of (D-CSL) and the sensitivity of p* with respect to <(x). See Appendix ?? for more details.
In the following, we define the Fréchet subdifferential of a convex function, which allows us justify the use of dual variables as a measure of informativeness of sample.
Definition 3.1. Let U, V be Banach spaces. The Fréchet subdifferential of functional P: V at U is defined as:
@P(u) = E P(c) - P(u) 2 (z, u) for all v e U),
where U* denotes the topological dual space of U, and (z, v- u) = Es [=(x)(v(x) - u(x))]
Having the above definition, state following theorem, which characterizes the variations of P (the optimum value of CSL as a function of the constraint tightness e(wc).
Theorem 3.2. If the problem CSLL) is strongly dual, then for any x E X. we have
-x(xx) E (e(x))
where (c(x) denotes the Frécher subdifferential of P* with respect to c(x), and (x) the optimal dual variable associated to the constraint on x.
Proof. See Appendix ??.
For any 2o E X, let :æ (x) be a bump function of radius >> 0, centered at Do (i.c., a continuous, radially-inereasing function with support in || æo S r). Theorem 3.2 implies that
Pd (e((a)) 8mo (2)) P* (*((()))
X (wo), :mo (ar))
The problem CCLL typically includes an infinite number of constraints. Theorem implies that the constraint whose perturbation has the most potential impact on the optimal value CCLL) the constraint with the highest associated optimal dual variable. For instance, infinitesimally tightening constraint a neighbourhood æo would restrict the feasible set, causing an increase of the optimal value of (CSL) at rate larger than >((oo). In that sense, the magnitude of the dual variables can be used measure of informativeness. Similarly to non-support vectors SVMs [39], samples associated to inactive constraints (i.c., (wo X xxox) 0}), considered uninformative.

---

3.3 On the Statistical Bias Induced by Active Sampling
In pool-based active learning, the resulting training set may not be representative the natural data distribution D [40] [1].2). This is due to the fact that queried samples are not randomly selected and often lie in the tails of D. Therefore, when performing several active learning iterations, undertake biased version of (BAL):
arg min min B (x,))~a0) [e (U)),)
B
(bBAL)
BCul): [ JEF
where (()) represents the biased distribution underlying the actively sampled set (()) Even though, each iteration, the queried samples have some desired property (e.g., large impact on the expected loss), the learned predictor [xx ( U B) is usually sub-optimal for the natural data distribution.
One way of undertaking the inner minimization in (bAAL) is with the worst-caseffeasiblity formula- tion.
P min JEF
(bFSL-a)
s.t. (((()),)) S c(x), -g...
(bFSL-b)
This formulation is closely related to the constrained formulation in CSL). In Appendix ??, relate the dual problem of (bFSL) with (D-CSL) to argue that the impact of the inconsistency between distributions
method is small. The key observation is that, if the marginal distributions Dx
and ② have the same support, then the respective feasibility formulations are equivalent, regardless of the probability distribution.
4 Proposed Approach
In light of the results mentioned in Section 3.2 on the usefulness of dual variables in constrained statistical learning as measure of sample informativeness, we present our proposed method, ALLY, in this section. We start by introducing a primal-dual procedure to empirically solve the constrained learning problem, and will then proceed describe our active learning algorithm detail.
4.1 Constrained Empirical Risk Minimization
The formulation in (D-CLL) poses two challenges: (i) the distribution D is usually unknown and (ii it is an infinite-dimension problem since optimizes the functional spaces F and A. We handle the former by replacing expectations by their sample means over a set of labeled samples L (ar,, he) described in the classical Empirical Risk Minimization (ERM) theory 43 In order to resolve the latter, we introduce a parameterization of the hypothesis class F as P (fo E O), while we create separate dual variable X, for each training sample æ;, These modifications lead to the Constrained Empirical Risk Minimization (CERM) problem.
38
p+ min deo
iENs (fo(xx))
Σ
(CERM-a)
We
s.t.
E' (fo(axs) wi S es, WEWC
(CERM-b)
This, in turn, results in the corresponding empirical dual problem,
D min i(, A); X20 eEe
(D-CERM)
where X = Piiieeee A > O represents element wise non aon-negativity, c; denotes the constraint upper bound associated to the 7th point-wise constraint, and the empirical Lagrangian, i(0. A), is defined as
((,,)) = We iN
Σ
[((Fo(zs) vi) +
( (C' <)]]
The max-min problem (D-CERM) can be undertaken by alternating the minimization with respect to
0 and the maximization with respect À 44 30 32). which leads to the primal-dual constrained
5

---

Algorithm Primal-dual constrained learning (PDCL)
1: Input: Labeled dataset L. primal learning rate 7p. dual learning rate Yjd, number of iterations T, number of primal steps per iteration Tp. constraint vector
2: Initialize: 0, X + 0.
3: for 1.... ., T do
4: 0
1pp (oL(0,)) (XTP) El (fo (Ii) ;
// Update primal variables (T, SGD steps) I/ Evaluate constraint slacks Update dual variables
5: t
Vc) vi ENc
6: X [) + naSi Vi Nc.
7: end for
8: Return: 0, A.
Algorithm 2 Active learning via Lagrangian duality (ALLY)
1: Input: Labeled set L, unlabeled set U. primal learning rate Tpp dual learning rate 7ds number of PDCL iterations T. number of primal steps per iteration Tp, constraint vector e. // Run the Primal-Dual Algorithm
2: 0", X + PDCL(C, Up, Ua,
U,, T, Tp..).
3: w" + arg min WeT EiENe (fo (x;)) -x7l.. // Train the dual regression head
4: j* + arg maxjeNu Sw (Jar (ar,))
// Find sample with highest dual variable
5: Return: jr
learning procedure in Algorithm Notice that mingge L(, A) the minimum of a family of affine functions on A, and thus is concave. Consequently, the outer problem corresponds to the maximization of a concave function and can be solved via gradient ascent. The inner minimization, however, generally non-convex, but there is empirical evidence that deep neural networks attain good local minima when trained with stochastic gradient descent 45 46). Some theoretical remarks on Algorithm | can be found in Appendix ??.
As shown in Algorithm L the dual variables accumulate the slacks (i.c., distances between the per-sample secondary loss and constraint values) over the entire learning procedure. This allows the dual variables to be used as a measure of informativeness, while at the same time affecting the local optimum to which the algorithm converges. Quite interestingly, similar ideas monitoring the evolution of the loss for specific training samples in order to recognize impactful instances have been used in several generalization analyses [47 48).
4.2 ALLY: Active Learning via Lagrangian Duality
Our proposed active learning algorithm, ALLY, is presented Algorithm (for the case of = Given a set of labeled samples, L, first obtain the model parameters 0* and the dual variables associated to samples in C using the primal-dual constrained learning approach in Algorithm [ Taking a representation learning approach [17
1).
18 49 50), we then partition the model fe- backbone for : X + IRd, where d denotes the dimensionality of the embedding space, and a prediction head fa Rdd + y, such that fe- = fo- fw- and 0* = x² Ubb In order to estimate the informativeness of the samples the unlabeled dataset U, we train dual regression head fw IRd + Rt on the embeddings generated by for by minimizing the mean weean-suaared error
LA(w)
Wel (ff((fo- -x11)
1
Σ
(1)
while the parameters o", hence the embeddings, are kept frozen. It should be noted that the idea of mapping embeddings dual variables is present in other machine learning settings [5]]. Once the
dual regression head trained, we evaluate it on the embeddings corresponding to the unlabeled samples, and identify the sample with the highest predicted dual variable.
As explained in Section 2.1 the batch setting, selecting the b samples with the highest associated dual variables is not optimal, due to the potential information overlap of such samples [7] [6]. Our method is compatible with any batch diversity approach that takes informativeness scores and unlabeled data points (or embeddings) as inputs.

---

4.3
Connection to BADGE 15
The BADGE method [5] uses the gradient of the loss function with respect the parameters the last layer, denoted by LL. as measure of informativeness, i.e.,
(2)
002
where (x) is the hypothetical label of æ. defined ((x) arg maxyey
(2))]y (x) In contrast, as
discussed in Theorem 3.2. to evaluate the informativeness of a given sample, ALLY observes
O
0p
00
HL (.))) [e (fo- [)),
00
Ōc ④
00
de(x)
00
de(x)
There are three main differences between these informativeness measures:
ALLY uses the derivative of the average optimal loss over the entire distribution, whereas BADGE only considers the point-wise derivative. In fact, most strategies evaluate their scoring function, or informativeness measure, on a single sample. Note that the term 0B [ (=).,) is constant for all
ALLY observes the gradient with respect to all model parameters, not only the ones in the last layer.
Aside from the derivative of the loss with respect the model parameters, ALLY also a0 which models how the results of the optimization (i.e.,
considers additional term B<()))
model parameters) change when the constraint function perturbed.
4.4 Interpreting the Informativeness Score of ALLY
Our proposed framework allows us to leverage the trained backbone and dual regression head in generative manner to create novel samples that most informative. Here, focus the MNIST dataset, and use the trained model to generate synthetic images with maximal associated dual variables. We begin by training MLP 10% of the MNIST dataset. Then, similarly (52), perform gradient ascent on images that are initially considered uninformative, so as to maximize their predicted dual variables. The progression of the resulting images is shown in Figure T
As the predicted dual variable increases, patterns corresponding to other digits appear, increasing the uncertainty the true label of the image. For instance, the third column of Figure D shows a handwritten 'I' that is progressively transformed into a blurred superposition Images in the last of Figure [ can be interpreted as lying the tails of the distribution D, or close to the decision boundary the end-to-end model fo. This also suggests that informative samples and
'7, '2 and I
9
3
2
S
3
2
S
3
Z
2
S
Z
Figure 1: Sample generation by maximization of predicted dual variables. The top row shows the initial images from MNIST, which the predictor associates low dual variable. Rows 2-5 display the images resulting from subsequent iterations of gradient ascent.

---

outliers (such as mislabeled samples) may be hard to distinguish. Recent empirical findings indicate that many active learning algorithms consistently prefer to acquire samples that traditional models fail to learn [53] Thus, modifying ALLY in order to avoid sampling these so-called collective outliers (e.g., by setting an upper bound on the dual variable associated to the queries) would be desirable in datasets that are not highly curated.
Experimental Evaluation
5.1
Settings
We consider four image classification tasks and one biomedical, non-image regression task. In the classification setting, we use standard datasets that commonly appear in the active learning literature, namely STL-10 [4] CIFAR-10 [55) SVHN [56] and MNIST [57]. Lacking an established benchmark regression dataset for active learning, we evaluate ALLY on the Parkinsons Telemonitoring dataset (PTD) [58]. In this regression task, the goal is to predict UPDRS (Unified Parkinson's 's Disease Rating Scale) scores from dysphonia measurements such as variation in fundamental frequency. Since measurements in this dataset are the result of a costly clinical trial that requires expert knowledge, this task is prime example in which active learning might be essential.
In all experiments, the initial labeled set Co consists of 200 randomly drawn samples, and the budget is set to either 6 200 or 6 1000. We use a ResNet- 18 architecture [59] with an embedding size of 128. In the case of MNIST and PTD, which are simpler tasks, we use a multi-layer perceptron (MLP) with two hidden layers, each with 256 neurons and rectified linear unit (ReLU) activation, leading to an embedding size of 256. The dual regression head fw is a MLP with 5 hidden layers, ReLU activations and batch normalization.
As done [24 25), to ensure diversity the batch, we cluster the embeddings of the unlabeled samples, i.e., (sa (az (ar))) using the k-MEANS clustering algorithm (60), where k S b is hyperparameter. We then select the samples with the highest associated dual variables from each cluster, while maintaining equity among the number of samples per cluster. As shown in Appendix ??, the performance of ALLY improves with an increased number of clusters k, since it leads to a more diverse batch of selected samples. Therefore, in all our experiments, we set k= b.
Regarding the role of the secondary loss, we opted for generic formulation as the performed sensitivity analysis in Theorem 3.2 holds for various choices of f'. However, in all our experiments, we set (().-) = -). We believe that using unsupervised or self-supervised losses for e is a promising research direction, and we leave it for future work.
We compare our algorithm with Entropy sampling, BADGE, Coreset and BAIT. While Entropy sampling focuses purely on uncertainty, BADGE and BAIT balance both diversity and informativeness with different approaches. Coreset differs from the previous methods in that it focuses on batch representativeness by framing active learning as a coreset selection problem. It has been observed that,
BAIT
Entropy
Coreset
BADGE
Random
ALLY
crlsas
Sunder olocinn
Sinoer va
Figure 2: Accuracy in the test set as a function of the number of training samples in four classification settings and two budgets, 200 (top) and 1000 (bottom). Solid curves represent the mean across five different random seeds, while shaded regions correspond to the standard deviation.
8

---

in some scenarios, several active learning methods fail to consistently outperform Random Sampling We thus include one of the five baselines. As explained in section | ALLY uses primal-dual approach to learn f(x; f. (U)),, while all other baselines are optimized using stochastic gradient descent (ADAM). We adopt the PyTorch 62 implementation of the baselines from [63]
G33 61 29
5.2
Classification
The experiments ST1.-10, CIFAR-10, SVHN and MNIST are all 10-class, image classification
tasks. We use the cross-entropy loss for both ((.,)) and (:) -) and set <(x:) = 0.2, Va. As shown in Figure ALLY exhibits top-2 performance with respect other baselines in STL.-10 (budget 200), SVHN (budget 1000) and CIFAR-10 (budget 200). In these three datasets, the improvement in the number of samples needed by ALLY to achieve 97% of the final accuracy, in comparison with the best baseline, is 9%, 8% and 2%, respectively. In MNIST, however, BADGE and BAIT consistently outperform ALLY. This may be due the fact that the MLP, being less expressive, yields embeddings of lower quality, hindering the prediction of dual variables.
5.3 Regression
We use mean-squared error for both E(.. and ('(,.)) and set e(x)) = 0.1, Vo. As seen in Figure 3 ALLY outperforms both Random and Coreset in this regression task, the gap being larger the beginning of the learning curve. Note that BADGE and Entropy are not applicable, since they are limited to classification scenarios.
kandom
ALLT
Coreeer
267-
264-
03
24+
Figure 3: Mean- geenn-suuare error in the test set function of the number of training samples in the Parkinson's 's telemonitoring dataset.
5.4 Ablation on the Constraint Tightness
Figure 4 illustrates the role e plays in the optimization procedure. For extremely large values of epsilon (e.g.. 20 nats), the constraint slacks become negative for all samples, and thus all dual variables become zero, making them uninformative (analogous to an unconstrained problem). Large values (e.g., 2 nats) can potentially be used to detect outliers. Our ablations suggest that values in the range [1.05pu. 1.25pu). where Pa is the average loss observed when training the model without constraints, work well in practice. The sensitivity of the method with respect the constraint level is impacted both by the task/dataset at hand and the diversity technique used. It reasonable to expect K-means to be less sensitive the constraint level than stochastic perturbations of the informativeness scores.
Epsilin
0.2
85
0.00
Figure 4: Ablation on the value of the constraint tightness c on the performance of ALLY in STL-10 and MNIST.

---

5.5 Dataset Redundancy
We study the performance of ALLY and Entropy Sampling with varying levels of dataset redundancy in STL-10. We define the level of dataset redundancy as the number of copies of each sample present in the training set. We then analyze the evolution of test accuracy over several rounds of active learning with a query budget of 200.
Redundancy
16. 2715 607
Figure 5: Impact of dataset redundancy on the performance of Entropy Sampling (left), ALLY (center) and low-diversity ALLY (right).
We observe that a strategy solely based on informativeness (e.g.. Entropy Sampling) is very sensitive to this type of dataset redundancy. This can be attributed to the fact that, at each round, copies of the most informative samples are queried simultaneously, leading to low batch diversity. Moreover, ALLY appears to be more robust than Entropy Sampling to this type of dataset corruption. This is not surprising, since only one sample is queried from each cluster, avoiding batch information overlap. However, when increasing the number of samples queried from each batch, the performance of ALLY is degraded, resembling that of Entropy Sampling. This experiment suggests that the impact of dataset redundancy active learning strategies is more linked to the diversity technique used than the informativeness measure. Whether this behaviour generalizes to other types of redundancy is left for future work.
6 Concluding Remarks
We presented ALLY, a principled batch active learning method based on Lagrangian duality. Our method formulates the learning problem using constrained optimization and solves it in the Lagrangian dual domain via a primal-dual approach. We leverage the fact that the magnitude of the dual variables be viewed as measure of informativeness of the corresponding training sample, as it indicates the sensibility of the optimum value of the objective function with respect to perturbation in the respective constraint.
Following the completion of the primal-dual learning phase, we employ the learned sample represen- tations, well their respective dual variables, to train dual regression head. This predictor is used to estimate the dual variables associated to unlabeled samples. The resulting informativeness measure is compatible with several batch diversity promoting techniques. Using the k-MEANS algorithm, we demonstrated that this principled method exhibits competitive performance in several classification and regression experiments. We also showed that under certain conditions, the impact of the distribution shift induced by active sampling is small.
In our experiments, we have set the secondary loss to be identical to the primary supervised loss (i.e., cross-entropy loss for classification, and mean-squared error for regression). However, evaluating the performance of ALLY under alternative unsupervised or self-supervised secondary losses is promising future direction. Finally, it would be interesting to evaluate the performance of ALLY under different diversity measures, comparing their computational burden.
7 Acknowldegments
Supported by NSF-Simons MoDI., Award #2031985, NSF Al Institutes program, Award #21 #2112665, and NSF HDR TRipods Award #1934960.
10

---

References
[1] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances Neural Information Processing Systems, volume 33, pages 1877-1901, 2020.
[2] Dmitry Lepikhin, HyoukJoong Lee. Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. GShard: Scaling giant models with condi- tional computation and automatic sharding. In International Conference on Learning Represen- tations, 2021. URL
net. wwt.://frummaaaa ierruum?ddqqre7XXHYYY
[3] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference Learning Representations, 2021. URL http::///ppeneeeeeeneeeeeeeeeeee http://oorrm"iddiiicdddNTTT
[4] Ying Liu. Active learning with support vector machine applied to gene expression data for cancer classification. Journal of chemical information and computer sciences, 44 6:1936-41, 2004.
[5] Steven C. H. Hoi, Rong Jin, Jianke Zhu, and Michael R. Lyu. Batch mode active learning and its application to medical image classification. In Proceedings of the 23rd International Conference on Machine Learning. ICML '06, page 417-424, New York, NY. USA, 2006. Association for Computing Machinery. ISBN 1595933832. doi: 10. 1455444.4444443898
URL /ttpttttt///oi.../. org/ 10. 0115/11134422 1143897
[6] V. Nath, Dong Yang. Bennett A. Landman, Daguang Xu, and Holger R. Roth. Diminishing uncertainty within the training pool: Active learning for medical image segmentation. IEEE Transactions on Medical Imaging, 40:2533425444 2021.
[7] Burr Settles. Active learning literature survey. 2009.
[8] Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach, 2018
[9] Gui Citovsky, Giulia DeSalvo, Claudio Gentile, Lazaros Karydas, Anand Rajagopalan, Afshin Rostamizadeh, and Sanjiv Kumar. Batch active learning at scale. CoRR, 0tnn/2217..1263.. 2021. URL httttt/////xiiis
owwp:/ivii.ooroeeoooooo abs wtwp///0..... 14263
[10] David D. Lewis and William A. Gale. A sequential algorithm for training text classifiers. CoRR, abs/cmp-1g/94007020, 1994. htLp:ttp:///axtt org/ abs//cmp-1g/9400022
[11] Ehsan Elhamifar, Guillermo Sapiro, Allen Yang, and S. Shankar Sasrty. A convex optimization framework for active learning. In 2013 IEFE International Conference on Computer Vision, pages 209-216, 2013. doi: 10. 10.1109/CC222203333..
[12] Burr Settles, Mark Craven, and Soumya Ray. Multiple-instance active learning. In J. Platt, D. Koller, Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems, volume 20, Curran Associates, Inc., 2008.
neur ppf
[13] Wenbin Cai,, Ya Zhang, and Jun Zhou. Maximizing expected model change for active learning in regression. In 20/3 IEEE 13th International Conference on Data Mining, pages 51-60, 2013. doi: 10.1109/CDDM.2013.104
[14] Nicholas Roy and Andrew McCallum. Toward optimal active learning through sampling estimation of eтror reduction. In Proceedings of the Eighteenth International Conference on Machine Learning, ICML '01, page 441 1-444, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ISBN 1558607781.
[15] Jordan T. Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. CoRR, http//99.003677 2019. URL httt:://ar/tt /ttp:////aaii..//aa org/ abs /90/ 03671

---

[16] K. Brinker. Incorporating diversity in active learning with support vector machines. In Proceed- ings of the 20th International Conference on Machine Learning (ICML 2000). 2003.
[17] Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):
1798-1828, 2013.
[18] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1rXiv:1807.033 8770077748, 2018.
[19] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham M. Kakade. Gone fishing: Neural active learning with fisher embeddings. CoRR, abs/2106.09675. 2021. URL https
7/arxiv. seaxivv.rg//ai awwpaaas//.. 09675
[20] Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. CoRR, abs/l 703.02910, 2017. URL /ttp:////arxx
http:///wwxiii..rrrb//////////// 02910
[21] Donggeun Yoo and In So Kweon. Learning loss for active learning. CoRR, abs/1905.03677.
2019. http //axii org/ abs/aa///..// 03677
[22] Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. CoRR, abs/1904.00370,, 2019. Utt.bttp://axxii.rrrg
1904. 00370
[23] Changjian Shui, Fan Zhou, Christian Gagné, and Boyu Wang. Deep active learning: Unified and principled method for query and training. CoRR, abs/1911.09162, 2019. URL http'
//arxiv. ottp http://b///911......
11t//9111..0 09162
[24] Fedor Zhdanov. Diverse match active learning. CoRR, abs/1901.05954, 2019. URL
http://arxxvv.rrg/ wtwpor/ggg////ooaa/////// 05954
[25] Zalán Bodó, Zsolt Minier, and Lehel Csató. Active learning with clustering. In Isabelle Guyon, Gavin Cawley, Gideon Dror, Vincent Lemaire, and Alexander Statnikov, editors, Active Learning and Experimental Design workshop In conjunction with AISTATS 2010, volume 16 of Proceedings of Machine Learning Research, pages 137, Sardinia, Italy, 16 May 2011. PMLR. /Rtppttts///ppoceeedinn https/mmmm..eeeee////ooooooo
getees/v16/boods http:////o/ooooooee//o html
[26] Xueying Zhan, Qingzhong Wang, Kuan-hao Huang, Haoyi Xiong, Dejing Dou, and Antoni B. Chan. A comparative survey of deep active learning, 2022. URL https://axxxx org/ abs/ 2203. 13450]
[27] Javad Azimi, Alan Fern, Xiaoli Chang-Fern. Glencora Borradaile, and Brent Heeringa. Batch active learning via coordinated matching, 2012. URL https: org/ abs/ 11/// 6458
[28] Andreas Kirsch, Sebastian Farquhar, and Yarin Gal. A simple baseline for batch active learning with stochastic acquisition functions. CoRR, abs/2106. 12059, 2021. URL htttss://ara::
org/abs/21e0 12059
[29] Daniel Gissin and Shai Shalev-Shwartz. Discriminative active learning. CoRR, abs/1907.0033
2019. htRp:ttp:://// http:://araaa /wtpvv.r/vvvvv// org/ ab9/ 09347
[30] Luiz F. O. Chamon and Alejandro Ribeiro. Probably approximately correct constrained learning, 2021.
[31] Luiz F. O. Chamon, Santiago Paternain, Miguel Calvo-Fullana, and Alejandro Ribeiro. Con- strained learning with non-convex losses. CoRR, abs/2103.05134, 2021. URL https
/ /aaxxiv.rgg/ab/////v 011111113111113111
[32] Ferdinando Fioretto, Pascal Van Hentenryck, Terrence W. K. Mak, Cuong Tran, Federico Baldo, and Michele Lombardi. Lagrangian duality for constrained deep learning. ECML/KKDD (5), pages 118-135, 2020. URL https:t//tiioooorreeet org/ 10. 1007 3- 030-67670-4_8
[33] Juan Cerviño, Luana Ruiz, and Alejandro Ribeiro. Training stable graph neural networks through constrained learning. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4223-4227, 2022. doi: 10.1
[34] Zebang Shen, Juan Cervino, Hamed Hassani, and Alejandro Ribeiro. An agnostic approach to federated learning with class imbalance, International Conference on Learning Representa- tions, 2022. URL http://e//peeeeeeeeeeeeeeoooooor wtt.://www........oooooooooddoo.
12

---

[35] Raghu Arghal, Eric Lei, and Shirin Saeedi Bidokhti. Robust graph neural networks via probabilistic lipschitz constraints. CoRR, abs/2112.07575, 2021. htttp::///axx/ org/
abs 2tss/211.07755
[36] Alexander Robey, Luiz Chamon, George J. Pappas. Hamed Hassani, and Alejandro Ribeiro. Adversarial robustmess with semi-infinite constrained learning. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 6198-6215. Curran Associates, Inc., 2021. URL httpps::/ppoceediinngg htw.eeeriinnnnn...si...... wwwprips.ccppppppeeeee cc/pappr/202///ilee 377e1
pdf
15031 [37] Ignacio Hounie, Luiz F. O. Chamon, and Alejandro Ribeiro. Automatic data augmentation via invariance-conntrained learning. URL httttttts:///atii httt:p::/aarai..or//aa/////22/
[38] V.N. Vapuik. An overview of statistical learning theory. IEEE Transactions on Neural Networks, 10(5):988-99) 999, 1999. doi: 10.1109/22.886-4
[39] Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3): 273-297, 1995.
[40] Sebastian Farquhar, Yarin Gal, and Tom Rainforth. On statistical bias in active learning: How and when to fix it, 2021. URL htttt://aaxxxii http:/iv..rrg/b///00000 11665
[41] Sanjoy Dasgupta. Two faces of active learning. Theoretical Computer Science, 412(19):1767 1781, 2011. ISSN 0304-3975. doi: http::/dbii.rr///....66......000
URL /htpps Algorithmic
www..aciencedieer Learning Theory (ALT 2009).
[42] Chelsea Murray, James Urquhart Allingham, Javier Antorán, and José Miguel Hernández- Lobato. Addressing bias in active learning with depth uncertainty networks... not. CoRR, abs/2112 12.06926, 2021. URL htt..https://// //apxivv///xvv.... http://wwwvv.v......//// orw.oogg///aa....o /bs/2/12...... 221.222122.6226666
[43] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, USA, 2014. ISBN 1107057132.
[44] L. Hurwiez K. J. Arrow and H. Uzawa. Studies in linear and non-linear programming, by
k. j. arrow, 1. hurwiez and h. uzawa. stanford university press, 1958. 229 pages. Canadian Mathematical Bulletin, 3(3):196-199) 198, 1960. doi: 10. 10.017780064355022552.
[45] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. CoRR, abs/1611.03552 2016. URL/http/ //arxiv. arrzxv..orgg/bs/11111 03530
[46] Devansh Arpit, Stanislaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, al. A closer look at memorization in deep networks. In International Conference on Machine Learning, pages 233-242 PMLR, 2017.
[47] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J. Gordon. An empirical study of example forgetting during deep neural network learning. In International Conference on Learning Representations, 2019. URL https //openreview htt.:eenneettooourreedommmmm
[48] Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. CoRR, abs/1803.00092, 2018. URL lttt:://arxiii org/ abs/ 1803.00942
[49] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Com- puter Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16, pages 776-794. Springer, 2020.
[50] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020.
[51] Harikrishna Narasimhan, Andrew Cotter, Yichen Zhou, Serena Wang, and Wenshuo Guo. Approximate heavily-conssrrineed learning with lagrange multiplier models. In Advances in Neural Information Processing Systems, volume 33, pages 8693-8703, 2020.
13

---

[52] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adver- sarial examples. Yoshua Bengio and Yann LeCun, editors, 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URI.http://arxiv org aa//1412a/112////// 1112. .672
[53] Siddharth Karamcheti, Ranjay Krishna, Li Fei-Fei 0001, and Christopher D. Manning. Mind your outliers! investigating the negative impact of outliers on active learning for visual question answering. In Chengqing Zong. Fei Xia. Wenjie Li 0002, and Roberto Navigli, editors. Proceedings of the 59th Anmual Meeting of the Association for Computational Linguistics and the I 11th International Joint Conference on Natural Language Processing, ACL/JJCNLP 2021, (Volume 1: Long Papers), Virtual Event, August 1-6, 2021, pages 7265 0005-728110 Association for Computational Linguistics, 2021. ISBN 778-1-954085-522 52-7. URL pettps://aclanthooog.
org /tt//222..cclll
564
[54] Adam Coates, Andrew Ng, and Honglak Lee. An analysis of single-layer networks in unsu- pervised feature learning. In Geoffrey Gordon, David Dunson, and Miroslav Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 215-223, Fort Lauderdale, FL. USA. 11-13 Apr 2011. PMLR. URL URL https::/ mlr www....reessv11cctttteeee html
[55]
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009. Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. URtphtpp://ufion http://///ddlll.saffofrrroo stanford wtw.ooussnumberr//ippe0.... htw.:/00i..ouuueuuubrrrr.....e
[56)
[57] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http
7/yann. .ecun..ecnn.mmmmm cow exde/ htom/exxb/mmiiss//
[58] Athanasios Tsanas, Max A. Little, Patrick F. McSharry, and Lorraine O. Ramig. Accurate tele- monitoring of parkinson's 's disease progression by noninvasive speech tests. IEEE Transactions on Biomedical Engineering, 57(4):884-893, 2010. doi: 10.1109/TMME.2099000 20360000
[59] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2016.
[60] Stuart Lloyd. Least squares quantization pem. IEEE transactions on information theory, 28 (2):129-133) 137, 1982.
[61] Yonatan Geifiman and Ran Ylniv... Deep active learning over the long tail. CoRR, abs/1711.00941 2017. URL
wtt.ooog//bbb////// 00941
[62] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary De Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024 8035. Curran Associates, Inc., 2019. URL http: http:::pppppsssaappeeee// wtw.::/sss.eriir.ccccceopoaa o
9015-pytorch: an pdf
library.
[63] Yao-Yur Yuan Yang, Shao- Chuan Lee, Yu-An Chung, Tung-En Wu, Si-An Chen, and Hsuan-Ties Tien Lin. libact: Pool-based active learning in python. Technical report, National Taiwan University, October 2017. URL http:/thhw..ccc//tuuuaaaaa/aaaaa
available arXiv preprint
https://arxiv: wwt.:oorrabb////.o//o.//
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "qWhUnDLO6kd", "reviewer": "Reviewer_Jf6f", "summary": "This paper proposes a new algorithm for batch-mode active learning, which is the problem of selecting and labeling a batch of unlabeled data points in order to yield the best possible improvement in a downstream model once trained. This algorithm uses Lagrangian duality in convex optimization to obtain an informativeness measure for every labeled data point; it then trains a model to predict the informativeness of unlabeled data and selects the most informative points from different clusters in the feature space. The algorithm demonstrates some improvement over classification and regression baselines.", "questions": "- Does strong duality actually hold in your empirical results? If not, how large is the duality gap? Moreover, how would a lack of strong duality affect the Frechet subdifferential result in Theorem 3.2?\n- How does this method scale to and perform in larger data sets, e.g., ImageNet?\n- The mathematical comparison vs BADGE is interesting. A useful ablation would be to compare the correlations between BADGE and ALLY embeddings. This is important because the theory doesn’t necessarily hold with non-convex losses or hypothesis classes.", "limitations": "Limitations are briefly discussed. Societal impact isn't discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n**Strengths**\n\n- Using Lagrangian dual variables as an informativeness measure is a novel idea. Moreover, the idea of estimating the dual variables for unlabeled data points presents an interesting approach to capture this informativeness.\n\n\n\n**Weaknesses**\n\n- The batch active learning problem (BAL) is written as selecting a set of points that minimizes the training set loss. However, this is incorrect and we typically want to minimize out-of-sample error/test loss (e.g., see Sener & Saverese ’18). Note that when we select what data points to train, we void any iid or distribution assumptions and thus, minimizing train loss does not guarantee low test loss. \n- The methodology is heavily motivated by an assumption of strong duality, which holds only for convex loss functions and hypothesis sets.\n- The idea of using 3 models, e.g., a feature encoder, a classifier head, and an auxiliary estimator, has been explored in several works, e.g., VAAL (Sinha et al ’19), WAAL (Shui et al ’20). \n\n\n**References**\n\nSinha, Samarth, Sayna Ebrahimi, and Trevor Darrell. \"Variational adversarial active learning.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2019.\n\nShui, Changjian, et al. \"Deep active learning: Unified and principled method for query and training.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2020.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KsqkRqQdTeA", "reviewer": "Reviewer_fegS", "summary": "This paper tackles the pool-based active learning problem using a constrained learning formulation. The authors use the dual variable corresponding to each labeled data point as a measure of its information, and they train another model to predict the dual variable for the unlabeled data to determine which ones are the most informative, i.e., if the most informative ones are labeled and learned, the overall performance of the model will improve the most. The authors have also done experiments on classification tasks with images and a regression task with Unified Parkinson’s Disease Rating Scores. Additionally, there is a visualization of the relationship between the dual variable and the informativeness.", "questions": "### \n\n1. The constrained optimization formulation can be think inversely where larger $\\lambda$ corresponds to the data point that we do NOT want to include in learning. Here, we assume that including one data point in the learning process makes the model enjoy a lower loss on this specific data point. It is intuitive that having a stricter constraint will let the minimum of the objective function value becomes larger (i.e., worse) which means the overall loss is larger. Therefore, learning a data point with large $\\lambda$ forces the model forgetting other information and the overall loss will only decrease more because of this learning. In this way, we want to learn the data with $\\lambda=0$ because they do not hinder the minimization of the overall loss. Why is this explanation incorrect?\n2. For the Batch Active Learning setting, Line 98, why the loss is evaluated on only the training dataset (already labeled + actively labeled)? I think we want the model to be good on any data from the population, not specifically on the ones we want to label.\n3. We know that $\\lambda$ depends on the derivative of $P$ in terms of $\\epsilon$, but the derivative only captures the slope. Adding a newly labeled data point in model training may cause a large change of $\\epsilon$. Is there any result on the second order derivative of $P$?\n4. For Line 123, when you say ‘The most informative samples often lie in the tails of the distribution’, how do you define the informativeness strictly or specifically?\n5. In the Abstract, Line 14, ‘(we) also discuss its limitations depending on the capacity of the model used’. Could you point out where the discussion is?", "limitations": "The authors have not discussed the limitation or the societal impact of their method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Major strengths:\n\n1. This paper provides a new type of solution for active learning from a novel perspective of the usage of the dual variable in constrained optimization. Although Theorem 3.2 can be obtained straightforward with the Lagrangian function, it is very insightful to connect this formulation to the active learning problem where labeling and learning a new data point is explained as a way to satisfy a stricter constraint on the loss of this data point.\n2. I would like to emphasize the merit of the simplicity of the formulation and analysis in this paper. Although the only requirement for Theorem 3.2, the strong dualality of CSL, is still strong, it leaves a space for readers to adapt the general idea in this paper to their own problem settings.\n\nMinor strengths:\n\n1. This paper is well-written.\n2. The authors provide the ablation study for the constraint tightness.\n\nMajor weakness:\n\n1. Theorem 3.2 could be wrong. The proof in Appendix B has some issues. For Line 577, $\\lambda$ depends on $\\epsilon$ but this is not shown. This affects the derivation in Line 580 where there is $\\epsilon$. Also, the sub-gradient is not defined in the way as shown in Line 580. In general, this could be potentially fixed, but I still think it is a major problem because this is the crucial reason why one want to use the dual variable as the information indicator.\n\nMinor weakness: \n\n1. The citations in Line 87-88 are not correct.\n2. The citations in the Appendix are missing, e.g., Line 558, 571-572, 585, etc.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Hp1AEaZxPkN", "reviewer": "Reviewer_GJBg", "summary": "Batch active learning improves the sample qualities (avoid sample collapsing due to incremental improvement of the backbone model) and enables parallel oracles.  This paper tried to solve a critical issue for active learning. Unlike existing works, this paper proposed to solve the problem as a constrained learning problem and the algorithm solves the objective duality form.", "questions": "Continue with the cons of the pros and cons, it will be stronger if the authors could provide an empirical analysis of the query costs. For example, what is the wall-clock time of querying N examples to provide to the oracles? Practitioners of this method should have a clear understanding what is the overhead and when should use this proposed method. ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThe motivation is clear and well motivating.\nThe presentation is good and easy to follow.\nThe method proposed is interesting.\n\nCons:\n\nDid not provide asymptotically analysis and empirical analysis about the query cost. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ENUBPpL1qmF", "reviewer": "Reviewer_v7Ec", "summary": "The authors present a new active learning algorithm by formulating AL as a constrained statistical learning algorithm (CSL). In the CSL formulation the objective is to minimize loss on the data distribution subject to an auxiliary loss being upper bounded by epsilon everywhere. The authors then consider the Lagrangian of the optimization problem to derive a primal-dual algorithm to solve the optimization problem over the labeled dataset. The dual variables, obtained for the labeled dataset, are then generalized over the unlabeled pool by using a 2-head neural net, where one head predicts the labels and another head predicts the dual variables. This neural net is used to generalize the value of the dual variables to the entire unlabeled pool. The sample with the maximum dual variable is then chosen for labeling in the next round and this process is repeated. The authors provide an interpretation of the dual variables and also demonstrate the efficacy of their methods against a few baseline algorithms. The paper is well written and was easy to follow.", "questions": "1. What is the reason for formulating the AL problem as a CSL problem ? Can we reason about this choice of formulation from a statistical viewpoint?\n2. The role of the auxiliary loss function was unclear to me? What would the advantage be of choosing an auxiliary loss function to be different from the main loss function?\n3. Algorithm 2 chooses the unlabeled point with the maximum value of lambda as the data point to label next. Section 5.2 shows that lambda is a score of informativeness and large values of lambda are associated with very noisy samples. While I see wisdom in designing the algorithm to be noise seeking, would it be better to interpret lambda as probabilities and sample in proportion to lambda (favouring noisy samples in general) instead of choosing the sample with largest lambda? This would allow one to use importance weights in the CSL formulation and allow for optimizing an unbiased loss function.\n4. While I understand the reason for the simplistic choice of epsilon ( epsilon(x) = c), can the authors suggest other possible choices? Would it be possible to design sensible heuristics or apply simple, unsupervised learning algorithms apriori to get good choice for epsilon and then use this choice in the algorithms? If yes, what would such heuristics or unsupervised algorithms look like?\n5. The constant choice of epsilon and section 4.3 are at odds with each other. In Section 4.3, eqn 3, the authors take gradient w.r.t. epsilon. But, all experiments are with a constant epsilon. Furthermore,  it was not clear to me what the term \\grad \\theta/\\grad epsilon that  appears in equation 3 captures? Could the authors shed some light here and interpret what this additional term do?\n6. Are the networks retrained after addition of every single sample? If yes, are the old network values used to warm start training? A bit more clarity on the tricks used to train the network and compute optimizations would be useful.", "limitations": "Computational limitations of repeatedly training the network were not addressed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is well written and easy to follow.\nThe algorithm is pretty simple and intuitively sound. \nThe framing of active learning problem as a constrained statistical learning problem is innovative.\nThe experimental results look good.\nOn the whole I like the paper and I think it puts forward an interesting formulation and I can see quite a bit of follow up work stemming out of this work.\n\nWeaknesses:\nThe motivation to frame AL as a CSL problem is not clear to me. In general the paper, while being good on the optimization front, does not do a good job in connecting the formulation to statistical principles.\n\nSome design choices (such as choosing a constant epsilon) are not well explained. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept