Low-Budget Active Learning via Wasserstein Distance: An Integer Programming Approach
Authors: Rafid Mahmood
Sanja Fidler
Marc T Law
Venue: ICLR 2022 Poster (2022)
Keywords: active learning
integer optimization

Abstract: Active learning is the process of training a model with limited labeled data by selecting a core subset of an unlabeled data pool to label. The large scale of data sets used in deep learning forces most sample selection strategies to employ efficient heuristics. This paper introduces an integer optimization problem for selecting a core set that minimizes the discrete Wasserstein distance from the unlabeled pool. We demonstrate that this problem can be tractably solved with a Generalized Benders Decomposition algorithm. Our strategy uses high-quality latent features that can be obtained by unsupervised learning on the unlabeled pool. Numerical results on several data sets show that our optimization approach is competitive with baselines and particularly outperforms them in the low budget regime where less than one percent of the data set is labeled. 

Published as a conference paper at ICLR 2022
LOW-BUDGET ACTIVE LEARNING VIA WASSERSTEIN DISTANCE: AN INTEGER PROGRAMMING APPROACH
Rafid Mahmood' Sanja Fidler 1,2,3
Mare T. Law"
NNVIDIA University of Toronto
3 Vector Institute
(rmahmood, sfidler, marci @nvidia.com
ABSTRACT
Active learning is the process of training a model with limited labeled data by se- lecting core subset of unlabeled data pool to label. The large scale of data sets used in deep learning forces most sample selection strategies to employ efficient heuristics. This paper introduces an integer optimization problem for selecting a core set that minimizes the discrete Wasserstein distance from the unlabeled pool. We demonstrate that this problem can tractably solved with a Generalized Ben- ders Decomposition algorithm. Our strategy uses high-quality latent features that can be obtained by unsupervised learning on the unlabeled pool. Numerical re- sults several data sets show that our optimization approach is competitive with baselines and particularly outperforms them in the low budget regime where less than one percent of the data set is labeled.
INTRODUCTION
Although deep learning demonstrates superb accuracy supervised learning tasks, most deep learn- ing methods require massive data sets that can be expensive to label. To address this challenge, active learning is a labeling-efficient supervised learning paradigm when given large unlabeled data set (Cohn et al. 1994; SSetles] 2009). Active learning uses finite budget to select and label a subset of data pool for downstream supervised learning. By iteratively training a model on current labeled set and labeling new points, this paradigm yields models that use a fraction of the data to achieve nearly the same accuracy as classifiers with unlimited labeling budgets.
The task of selecting points to label is combinatorial optimization problem of determining the most representative subset of the unlabeled data (Sener Savarese 2017). However, estimate the value of labeling point, active learning strategies require informative features from the unlabeled data. Integer optimization models can also grow impractically quickly with the data set size. Nonetheless, optimally selecting which points label can reduce operational costs, especially for applications such as medical imaging where labeling requires time-consuming human expert labor (Rajchl et al., 2016), or domain adaptation where data pools are hard to obtain (Saenko et al. 2010).
In this paper, we introduce an optimization framework for active learning with small labeling bud- gets. To select points, minimize the Wasserstein distance between the unlabeled set and the set to be labeled. We prove that this distance bounds the difference hetween training with a finite versus an unlimited labeling budget. Our optimization problem admits a Generalized Benders De- composition solution algorithm wherein we instead solve sub-problems that are orders of magnitude smaller (Geoffrion) 1972). Our algorithm guarantees convergence can be further accelerated with customized constraints. Finally, to compute informative features, we use unsupervised learning on the unlabeled pool. We evaluate our framework on four visual data sets with different feature learning protocols and show strong performance versus existing selection methods. particular, we outperform baselines in the very low budget regime by a large margin.
globally optimal solution and
Our overall contributions are as follows: (1) We derive new deterministic bound on the difference in training loss between using the full data set versus a subset via the discrete Wasserstein distance. This further bounds the overall expected risk. (2) We propose active learning by minimizing the Wasserstein distance. We develop a globally convergent customized algorithm for this problem using Generalized Benders Decomposition.
(3) We consider low budget active learning for image classification and domain adaptation where up to 400 images can be labeled and show that optimally selecting the points label in this regime improves heusistic-based methods.

---

Published as a conference paper at ICLR 2022
Unisbeted data
Labeled data points
Ours
Boseline (k-centers)
selected points
Encocier
Wasserstel
mixed integer linear program
Encoder
distance
MLP
New MLP
data points
sulfffuueeriieed
repress entation leaming
wow-bulgat supervised learning
Select optimal points to label
Figure 1: (Left) In our active learning framework, we first pre-train our features with self-supervised learning, select samples to label by minimizing the discrete Wasserstein distance, and then train our classifier. (Right) t-SNE plot of the feature space on the STL-10 data set with selected points highlighted. The baseline misses the top right region. See Appendix E.7 for full visual comparisons.
2 PROPOSED MODEL
We first set up the active learning problem and develop the main theory motivating our active learn- ing strategy illustrated in Figure All of our proofs can be found in Appendix A
2.1 PRELIMINARIES OF ACTIVE LEARNING
Consider a C-class classification problem over features E X' and labels y E Y :- (I...., C), where (X, II-II) and 1-I, are metric spaces. With data distribution and a loss function {(x, y: w) X x y R parametrized by w, our goal is to minimize the expected risk minw E[((x, y; w)] In practice, we use a labeled data set {(;; yi) ) of N samples to minimize the empirical risk.
In active learning, we instead have features D = {x and labeling oracle X' - y. Let π E {0, 13 indicate points label given budget B. That is, we may call the oracle B times to create a labeled core set C(TT) == ((x),9(xx)) B j=1 where x, E C(T) is labeled iff n. = 1. An active learning strategy is an algorithm to optimize C(TT). We omit π in the notation for C when obvious.
Active learning strategies can be categorized into uncertainty- based, representation-busee based, or hy- brid. Uncertainty methods determine images to label by using measures of the uncertainty of a classifier (Roth Small 2006 Li Guo 2013, Wang & Shang 2014). Representation methods select a diverse core set of examples spread over the feature space Yu et al. 2006) [Sener& & Savarese
2017 Contardo et al. 2017). Uncertainty estimates and latent features are commonly obtained by
training preliminary classifier for feature extraction with previously labeled data set (Sinha al.
2019 Shui et al. 2020). Other approaches also include pre-clustering (Nguyen & Smeulders 2004]
or few-shot learning (Woodward & Finn 2017].
Sener & Savarese (017) bound the expected risk by a generalization error of training with an un- limited number of oracle calls, the empirical risk of training with a set of B points, and set loss for training with all points versus only the core set. This bound, slightly revised, is
B
N
E[((x, UI w)] S B
Σ (x, ())
B[((x,
1 N
Σ
((x;):
empirical risk
generalization hound
B
((x, () B
w).
core set loss
The generalization bound does not depend on the core set. Furthermore for small B, the empirical risk is always negligibly small. Thus from Sener & Savarese (2017), we can focus on an active learning strategy that specifically minimizes the core set loss.
2.2 ACTIVE LEARNING VIA WASSERSTEIN DISTANCE
As a function of C, the core set loss resembles a distribution matching loss on the empirical risk with C versus D. This motivates an active learning strategy of minimizing distance between
2

---

Published as a conference paper at ICLR 2022
distributions over these two sets (Shui al. 2020). We consider minimizing the discrete Wasserstein
- = be distance matrix over features in D. The discrete Wasserstein distance between C and is denoted by W WCC(F), D) and defined
distance (Villani 2008). Let Dx |||:
X
W(C(T), min r20
Dxx r
r1
1, r B
max A
N 14
B x
A 1 Noltv0l' S
(2)
where (A, B) == Trace(A B) is the Frobenius inner product between real matrices A and B. We then formulate our active learning strategy as the following optimization problem:
min T
W(C(T),
t. [C(+T]] B.
We may also consider alternative distance functions such as divergences. However, since the Wasser- stein distance minimizes a transport between distributions, it can lead to better coverage of the un- labeled set (e.g., (e.g.,(Shui et al. (2020) demonstrate numerical examples). Furthermore, we compute the discrete Wasserstein distance by a linear program, meaning that our active learning strategy can be written as mixed integer linear program (MILP). Finally, the Wasserstein distance induces new bound on the expected risk in training. Specifically, we show below that the Wasserstein distance directly upper bounds the core set loss under the assumption of a Lipschitz loss function.
Theorem 1. Fix w constant. For any > O, if É(x, yi w) is K K-Lipschitz continuous over (X x V, ||||| + =lyl), then 1. N EE e(x, ((xx,)((x); [(x:): w) B Σ j=1 [xx, ((xx)); S (W(C, D) +EKC.
The second term in the bound vanishes for small e. Moreover, Theorem [ assumes Lipschitz con- tinuity of the model for fixed parameters, which is standard in the active learning literature (Sener & Savarese 2017) and relatively mild. We provide a detailed discussion on the assumption in Ap- directly substitutes into the bound of Sener & Savarese 2017), meaning that minimizing the Wasserstein distance intuitively bounds the expected risk.
pendix B Finally, the bound in Theorem dirrectyy
MINIMIZING WASSERSTEIN DISTANCE VIA INTEGER PROGRAMMING
We now present our Generalized Benders Decomposition (GBD) algorithm for solving problem GBD is an iterative framework for large-scale non-convex constrained optimization (Geoffrion I972.. We provide a general review of GBD in Appendix C and refer to Rahmaniani al. (2017) for a recent survey. In this section, we first reformulate problem (3), summarize the main steps of
our algorithm, and show three desirable properties: (i) it has an intuitive interpretation of iteratively using sub-gra uub-gradients of the Wasserstein distance as constraints; (ii) it significantly reduces the size of
the original optimization problem; and (iii) converges to an optimal solution. Finally, we propose several customization techniques to accelerate our GBD algorithm.
3.1
MINIMIZING WASSERSTEIN DISTANCE WITH GBD
Problem 3). which selects an optimal core set, can be re- re-written as the following MILP:
1
1
min
D)
s.t. r1
P
B π T = B
(4)
(E P20
N
Let us define G = T 2 rI = 1/N} and P = {N E (0.1)*
1) N
TTI -B. Problem
equivalent to the following Wasserstein-Maste Problem (W-MP):
min 7 17,
t. 7 inf reg (Dx. +
KA BAERN
(5)
Although W-MP contains an infinite number of constraints controlled by the dual variable X, it can also be re- re-written single constraint by replacing the right-hand-side with the Lagrangian L(T)) of the inner optimization problem. Furthermore, L(т)) is equivalent to the Wasserstein distance:
L(T))= = sup inf NER TEG
DDx - T 1 T (-T--TT)
-r"1)
W(C(T),
B
3

---

Published as a conference paper at ICLR 2022
Main Steps of the Algorithm. Instead of the semi-infinite problem W-MP (5) consider finite set of constraints A C CR and solve a Wasserstein- Raaserstein-Relaxedd Master Problem (W- W-RM)(AA)::
s.t. 7 2 inf { (Dxx + TEG
1 { A
min T.TE
"
Let (1) it) be an optimal solution to W-RMP(A) and let (ni","" be an optimal solution to W-MP. Since W-RMP is a relaxation, f < ry" lower bounds the optimal value to W-MP (and thus also 'f" upper bounds the optimal value to W-MP. By iteratively adding new constraints to A, we can make W-RMP(A) tighter approximation of W-MP, and consequently tighten the upper and lower bounds.
to problem 4 Furthermore, L(#)) = W(C(#)),) D) 2 W(C(F"",
In GBD, we initialize selection # E P and A = 0. We repeat at each iteration E 1,,,.,....
1. Given a solution (i',+') solve the Lagrangian I(+*) to obtain primal-dual transport (f", X²).
2. Update A + A [X*] and solve W-RMP(A) to obtain solution (f'* A²-1).
We terminate when W (C((*)), ff is smaller than a tolerance threshold > 0, or up to a runtime limit. We omit & in the notation when it is obvious.
Interpretation. The Lagrangian is equivalent to computing a Wasserstein distance. Furthermore, the dual variables of the Wasserstein equality constraints are sub-gradients of problem 4 (Rahmani- ani et al. 2017). In each iteration, we compute W (C(#), D) and add a new constraint to W-RMP(A). Intuitively, y, each constraint is a new lower bound on v) using the sub-gradient with respect to म.
contains N + N variables and 2N + constraints where NV (D), making it intractable for most deep learning data sets (e.g.. 50, 000 for 10), W-RMP(A) only contains N + 1 variables and |A| constraints (i.c., the number of constraints equals the number of iterations). In our experiments, we run for approximately 500 iterations, meaning W-RMP(A) is orders of magnitude smaller than (4). Although we must also solve the Lagrangian sub-problem in each iteration, computing Wasserstein distances is a well- studied problem with efficient algorithms and approximations (Bonneel et al.) 2011] Cuturi 2013).
Solving Smaller Problems. The original problem
We discuss our overall reduced complexity in more detail Appendix[D.. [D3
Convergence.
Finally, because the objectives and constraints of W-MP are linear and separable in and ग (see Appendix(C). GBD converges to an optimal solution in finite time.
Corollary 1. Let A = 0 and 40 E P. Suppose in each iteration t e {0, 1,2, ... (CC(#'), D) obtain a dual variable X and compute W-RMP(A t+1 + A U (X+3 to obtain (6)+1) 1)) Then for any E >> 0, there exists a finite ts for which W(C("")) )) ff <E
compute
3.2 ACCELERATING THE ALGORITIM
Since W-RMP(A) is relaxation of W-MP, we can accelerate the algorithm with techniques to tighten this relaxation. We propose two families of constraints which can be added to W-RMP(A).
Enhanced Optimality Cuts (EOC). A given inequality is referred to as an optimality cut for an optimization problem if the optimal solution is guaranteed to satisfy the inequality. Introducing optimality cuts as additional constraints to optimization problem will not change the optimal so- lution, but it may lead to a smaller feasible set. We augment W-RMP(A) with "Enhanced Optimality Cuts" (EOC) in addition to the Lagrangian constraints at each iteration of the algorithm.
Proposition For all t P, let (T, Å, (t) be optimal primal-dual solutions to W W(C(f), D) in problems 7 and 2 Let Di, be elements of Dx. The following are optimality cuts for W-MP:
1
Lower Bound:
17
2
min VELL N
(Di. > 0} n,
(6)
B
1
Triangle Inequality:
2
min
(Di. > 0} प. W(C(+), D)
B
d'E(L..., .N.
x2,EC(F))
N
Dual Inequality:
n 2 W(C(()), D) +
T π
max
(Dirr n, (8)
B
N
B
vell
4

---

Published as a conference paper at ICLR 2022
Inequality (6) is derived from lower bound the Wasserstein distance between two probability distributions. This is a general relationship between 7) and π and can be included as an additional constraint to W-RMP(AA) at the onset of the algorithm. Inequalities respect to a given Ā. In each iteration, when we obtain a new स, we can construct a Triangle and Dual Inequality, respectively, and add them to W-RMP(A) along with the Lagrangian constraints.
and (8) bound 17 and with
From Proposition 1 an optimal solution to W-MP satisfies the inequalities 66 B meaning that including them as additional constraints to W-RMP(A) will still ensure that the optimal solution to W-MP is feasible for W-RMP(A) for any A (and therefore also optimal once A is sufficiently large).
That is, we preserve convergence from Corollary II while tightening the relaxation, which reduces the search space and consequently, the overall number of iterations of our algorithm.
Pruning Constraints (P). Augmenting W-RMP(A) with constraints that are not valid optimal- ity cuts may potentially remove the global optimal solution of W-MP from the relaxed problem. Nonetheless, such constraints may empirically improve the algorithm by aggressively removing un- necessary regions of the relaxed feasible set (Rahmaniani et al. (0177). One simple approach is to use trust region-type constraints that prune neighbourhoods of good versus bad solutions (van Ackooij et al. 2016). We introduce simple set of constraints that remove search neighbourhoods around core sets with high Wasserstein distances and encourage searching near neighbourhoods around core sets with lower Wasserstein distances. We detail these constraints in Appendix D.I]
In Appendix D.2 we provide a full algorithm description and Python pseudo-code. Finally, note that the techniques proposed here are not exhaustive and more can be used to improve the algorithm.
4 COMPARISON WITH RELATED LITERATURE
In this section, compare our optimization problem and active learning strategy with the related literature in active learning, minimizing Wasserstein distances, self-supervised learning, and GBD.
Active Learning. Our approach is closely related Greedy k-centers (Sener & Savarese 2017 which develops a core set bound similar to Theorem I but using the optimal solution to a c-center facility location problem rather than the Wasserstein distance (Woli) 201T). Their bound is proba- bilistic whereas ours is deterministic. Furthermore since facility location is large MILP, [Sener & Savarese (2017) use a greedy approximation to select points. This sub-optimality can incur signif- icant opportunity cost in settings where every point must be carefully selected so as to not waste limited budget. Here, GBD solves our MIIP with an optimality guarantee if given sufficient runtime.
Another related method is Wasserstein Adversarial Active learing (WAAL) (Shui et al. (020), which also proposes a probabilistic Wasserstein distance core set bound. Their bound is proved with tech- niques from domain adaptation and requires a poobabilittic-Lischhi
assumption
the data dis-
tribution itself, whereas our bound uses only linear duality and a weaker assumption: Lipschitz continuity in the loss function. To select points, (Shui et al. (2020) use semi- supervieee adversarial regularizer to estimate the Wasserstein distance and a greedy heuristic to select points that minimize the regularizer. Our algorithm does not need learn custom feature space and can instead be used with any features. Furthermore, we directly optimize the Wasserstein distance and provide a theoretical optimality gap. Numerical results show that optimization outperforms greedy estimation in the low-budget regime and yields a small improvement even in bigh-budget settings.
Minimizing Wasserstein Distance. Problem 3 has been previously studied in active learn- ing (Ducoffe 2018 Shui et al.) 2020) and in other applications such as scenario reduction for stochastic optimization (Heitsch & Römisch (2003) Rujeerapaiboon et al. 2018). The related lit- erature concedes that MILP models for this problem have difficulty scaling to large data sets, ne- cessitating heuristics. For instance scenario reduction, (Heitsch & Römisch (2003) and Rujeer- aapaiboon et al. (2018) equate problem (3) to the k-Medoids Cluster Center optimization problem. They employ the k-medoids heuristic and an approximation algorithm, respectively, on small data sets containing approximately 1, 000 samples. In contrast, our GBD algorithm provides an optimal- ity guarantee and as we show in numerical experiments, scales gracefully on data sets with 75, 000 samples. We review k-medoids and scenario reduction in Appendix E.2
Self-supervised Learning. Active learning selection strategies improve with useful features x e X.. Recently, self-supervised learning has shown tremendous promise in extracting representations
5

---

Published as a conference paper at ICLR 2022
for semi-supervised tasks. For example, model pre-trained with SimCLRv2 on ImageNet (Deng eet al. [2009] can be finetuned with labels from 1% of the data to achieve impressive classification accuracy (Chen et al.] 2020a blc) In contrast, the standard practice in classical active learning is to train a classifier for feature extraction with previously labeled data (Sener & Savarese, 2017] Sinha et al., 2019 Shui et al., 2020), with the previous papers requiring labeling up to 20% of the data to achieve comparable performance to self-supervised pre-training with supervised finetuning. Our numerical experiments verify that self-supervised pre-training can accelerate active learning to competitive accuracy with orders of magnitude less labeled data.
Chen et al. (2020c) use random selection after self supervised learning. With enough points, current active learning strategies achieve similar bottleneck performances (Siméoni et al. 2019). However, the heuristic nature of these strategies leave opportunities the low budget regime. Numerical results show that optimization in this regime specifically yields large gains over heuristic baselines.
Generalized Benders Decomposition (GBD). This framework is commonly used in non-convex and integer constrained optimization (Geoffrionn 1972), since it instead solves sub-problems while often providing an optimality guarantee. However, the vanilla GBD algorithm typically slow to converge for large problems. As result, the integer programming literature proposes improvement techniques such as multiple different types of constraints to tighten the relaxations and heuristics to direct the search (Rahmaniani et al. 2017). These improvements are often customized for the specific optimization problem being solved. In our case, we propose enhanced optimality cuts in Section Decction3.2jja that leverage properties of the Wasserstein distance. Further, our pruning constraints simple techniques that can be used in GBD for arbitrary binary MILPs.
EXPERIMENTS
In this section, we first evaluate our algorithm on solving problem (4) by comparing against the stan- dard heuristic from the scenario reduction literature (Heitsch & Römisch 2003). We then evaluate our algorithm on the following two active learning tasks: (i) low budget image classification where we select images based on features obtained via supervuue learning and (ii) domain adaptation where we select images in an unlabeled target pool using features obtained via unsupervised domain adaptation over a source data pool. For both tasks, we outperform or remain competitive with the best performing baselines on all data sets and budget ranges.
In ablations, we first observe that our approach is effective with different embedding methods (e.g.- self-supervised, domain adversarial, and classical active learning where features are obtained from previous rounds); in each case, we yield improvements over baselines. Second, the acceleration techniques proposed in Section helpp optimize problem 4 faster and often improve active learn- ing. Finally, from a wall-clock analysis, running GBD for more iterations yields better selections, but even early stopping after 20 minutes is sufficient for high-quality solutions.
In this section, we only summarize the main results. We leave detailed analyses for all experiments in Appendix [ Further in Appendix [E.] we include additional experiments including ablations and qualitative evaluation of the selections and t-SNE visualizations of the feature space.
5.1 EVALUATION PROTOCOL AND BASELINES
We evaluate active learning in classification on three data sets: STL-10 (Coates al. 201T), CIFAR-
10 (Krizhevsky) 2009), and SVHN (Netzer et al. 2011). Each data set contains 5, 000, 50, 000, and 73, 257 images, respectively. showcasing when the number of potential core sets ranges from small to large. We initialize with no labeled points and first pre-train our model (i.e., feature encoder head) using the self-supervised method SimCLR (Chen et al. 2020a b). We then employ active learning over sequential rounds. In each round, we use feature vectors obtained from the encoder output to select and label B new images and then train the classifier with supervised learning.
Our domain adaptation experiments use the Office-31 data set (Saenko et al., 2010), which contains 4, 652 images from three domains, Amazon (A), Web (W), and DSLR (D). We use active learning to label points from an initially unlabeled target set to maximize accuracy over the target domain.
We follow the same sequential procedure as above except with a different feature encoding step,
f-DAL, which is unsupervised domain adversarial learning method (Acuna et al. 2021

---

Published as a conference paper at ICLR 2022
Table 1: Head-to-head comparison of our solver using Enhanced Optimality Cuts (EOC) versus k- medoids on the objective function value of problem (4) at different budgets. Lower values are better. For each data set, the best solution at each budget is bolded and underlined. All entries show means over five runs. See Appendix E.2 for standard deviations.
B
10
20
40
60
80
100
120
140
160
180
STL-100
k-medoids
0.290
0.132
0.109
0.110
0.100
0.097
0.092
0.089
0.093
0.087
Wass, EOC
0.281
0.134
0.122
0.116
0.101
0.096
0.092
0.087
0.090
0.085
k-mednids
0.258
0.142
0.118
0.120
0.109
0.104
0.095
0.089
0.099
0.096
CIFAR-10
Wass, + EOC
0.322
0.176
0.125
0.092
0.077
0.097
0.064
0.059
0.072
0.072
SVHN
k-medoids
0.152
0.172
0,164
0.175
0.178
0.179
0,178
0.173
0.173
0.170
Wass. + EOC
0.153
0.093
0.093
0.100
0.098
0.091
0.085
0.080
0.087
0.089
feature encoder for STL-10, ResNet-34 for CIFAR-I0 and SVHN, and Resnet-50 for Office-31. Our head is a two-layer MLP. The downstream classifier is the pre-trained encoder (whose weights are frozen) with a new head in each round. Supervised learning is performed with cross entropy loss. We compute Wasserstein distances using the Python Optimal Transport library (Flamary et al. 202T and solve W-RMP(A) with the COIN-OR/CBC Solver (Forrest & [ 2005). We run our algorithm up to a time limit of 3 hours (and increase to hours for experiments on SVHN). Finally, we implement two variants of the GBD algorithm without the pruning constraints (Wass. EOC) and with them (Wass. + EOC P). See Appendix for details on training and optimizer settings.
We use a Re (He al. 2016)
We compare against the following baselines: (i) Random Selection; (ii) Least Confidence (Settles
2009 Shen et al. [2017] Gal et al., (017); (iii) Maximum Entropy (Settles 2012 (iv) k-Medoids
Cluster Centers (Heitsch & Römisch 2003); (v) Greedy k-centers (Sener & Savarese 2017): : (vi)
Wasserstein Adversarial Active Learning (WAAL) (Shui et al. 2020). The second and third base- lines are uncertainty-basee approaches using the trained classifier in each round, the fourth and fifth are representation-bast based approaches that leverage unsupervised pre-trained features, and the last greedy strategy that approximates the Wasserstein distance with an adversarial regularizer in training. All baselines use the same self-supervised pre-training and supervised learning steps as us.
5.2
MAIN RESULTS
E22 for more results). k-Medoids is a well-known heuristic for prob- lem (Heitsch & Römisch 2003 Rujeerapaiboon et al., objective function values obtained
Objective Function Value (see Appendix
Table 2: Wass. + EOC with limited runtimes versus k-medoids on prob- lem 44) for CIFAR-10. The best so-
2018 Table[] by our algorithm versus k-medoids for STL-10, CIFAR- 10, and SVHN. We especially outperform k-medoids for B 2 120 where the selection problem is large and harder to solve. This gap also widens for larger data sets; for instance on SVHN, we almost always achieve around 2x improve- ment in objective function value. Table 2 k-medoids versus Wass. + Enhanced Optimality Cuts (EOC) on CIFAR-I0 where we force early termination. Even after reducing our algorithm's 's runtime to three minutes, we still achieve high-quality solutions to the optimization problem.
lution for each budget is bolded and underlined. See Appendix F.2 for full results and Appendix E.6 for de- tails on k-medoids runtime. B
k-medoids 3 min.
Wass.
BOC
3 min.
3 hr.
further compares
120
0.095
0.082
0.064
140
0.089
0.073
0.059
160
0.099
0.084
0.072
180
0.096
0.075
0.072
Figure 2 summarizes our methods versus baselines on each data set. For each data set and number of points, our approaches are either competitive with or outperform the best baseline. Table 3 highlights the extremely low budget regime (B- < 40) where every point must be carefully selected. For instance, if we can only label B 10 points, poorly selecting even one point wastes 10% of the budget. Here, our best methods typically outperform the basclines on all three data sets often by large margins (c.g.. 2 4.9% on STL-10 at B = 40, 2 9.1% on CIFAR-10 at B- 20, and 2 5.2% on SVHN at B 40).
Image Classification (Appendix E.3
There is no dominant baseline over all budget ranges and data sets: k-medoids is effective for B < 40 smaller data sets (STL-10) but worse with bigger budgets and data sets (CIFAR-10, SVHN), whereas Random and Greedy k-centers improve in the latter. Furthermore while SimCLR- pretraining improves all baselines compared to classical active learning papers (Sener& & Savarese
7

---

Published as a conference paper at ICLR 2022
STL-10
CIFAR-10
70
70
Accuracy (%)
Accuracy (9%
Random
Confidence
60
Confidence
50
Entropy
Entropy
k-medolds
k-medolds
50
40
k-centers
k-centers
WAAL
WAAL
Wass. EOC
40
Wass. EOC
30
Wass. EOC
Wass. EOC
60
100
120
40 60
100
120
Number Labeled Images
Number of Labeled Images
SVHN
Figure 2:
Low budget active learning on CIFAR-10, SVHN and STL-10 using SimCLR pre-trained features. See Table for detailed re- sults for B < 40. See Appendix E.3 for full results up to B < 180. The solid lines are our models and the dashed lines baselines. All plots show mean + standard error over five runs. Our best models outperform baselines for most budgets.
70
Accuracy (%)
Random
60
Confidence
Entropy
50
k-meddidd
k-centers
WAAL
Wass. + EOC
30
Wass. + EOC
20
40
60
80
100
120
Number Labeled Images
Table 3:
Mean + standard deviation of accuracy results in the extremely low budget regime.
Data set
Random
Confddacee
Entropy
k-medoids
k-centers
WAAL
Wass.
BOC
Wass. EOC
10
30.2
1 6.1
30.2 1 6.1
30.2 1 6.1
45.7 15.5133.5 3.5
37.4 4.4
30.2 1
43.1 1 0.7
41.4.1..2
STL-10
42.8
3.6
37.8
2 42
33.6
50.2224
45.8 4.6
45.8 = 4.0
51.5
1.6
40
51.0
3.16
4.4
50.5=12
53.6 2.9
60.4
58.7
38.0
1.9.7
38.0 9.7
1.97
45.6 5.9
37.0 1:.
38.0
50.7 3.0
L6.8
CIFAR-10
20
51.8 8.5
3T.7 45
3141311
53.7= 7.0
5.9
4..
63.7 1.8
6..3
63.1
47.8 3.1
40.5
65.3
74.7
50.1 = 3.3
73.5
72.7 1.8
10
37.1
1 4.9
37.1
4.9
37.1
35.7 6.7
28.6 4.6
37.1 4.9
37.0 2.8
38.0 1..0..0
SVHN
47.2
36.9 111
41.4
16.1
32.6 12.6:000 6.4
11.5
2.3
48.3
49.4
40
57.5
6.3
48.3
4.3
51.0
68.6 6.3
51.2 4.4
39.8 3.6
63.2 = 6.5
63.8 6.1
- W
100
75
75
70
Accuracy (%)
80
Accuracy
65
Confilence
Brotppy
Accuracy
65
Confilence
Brooay
Confidanco
60-
A-certos
60
Ricortos
40
55
55
200
300
100
200
300
20
20
40
60
Number Labeled Images
Number Labeled Images
Number of Labeled Images
Figure 3: Active learning with domain adaptation for D- W- and D- on Office-31 using f-DAL pre-treeee trained features. The solid line is best model and the dashed lines are baselines. All plots show mean + standard error over three runs. See Appendix E.4 full results.
2017 Shui et al. p020), representation methods (Greedy k-centers, k-medoids) generally outper- form uncertainty methods (WAAL,, Least Confidence, Maximum Entropy) in this setup because classification is now easier, which means that more useful to obtain representative samples of each class than uncertain examples. By optimizing for diverse core set selection, we outperform with the best baseline for nearly all budgets and data sets.
Domain Adaptation (Appendix E.4 Figure 3 previews accuracy on Office-31 for DSLR to Amazon, Web to Amazon, and DSLR to Web; we leave the other cource-target combinations in Appendix E.4 As before, approach either outperforms or is competitive with the best baseline for all budgets and source-target pairs, the baselines are non-dominating over each other, and rep- resentation methods such as ours benefit from strong features and model pre-training. Thus,
8

---

Published as a conference paper at ICLR 2022
Table 4: Mean + standard deviation of accuracy results in the classic active learning setup of Shui et al. (2020). The best method is bolded and underlined.
B
1000
2000
3000
4000
5000
6000
WAAL
57.0 1.2
65.9 + 0.4
73.3 + 0.6
76.7 + 0.8
77.4 + 0.7
81.0 0.2
CIFAR-10
Wass. + EOC +
58.1 = 0.1
68.9 + 0.7
73.2 # 0.2
77.3 + 0.3
79.1 + 0.7
81.0 0.4
B
500
1000
1500
2000
2500
3000
WAAL
69.6
0.9
76.9 0.8
84.2 0.7
86.2 = 1.7
87.5 + 1.0
88.9 + 0.5
SVHN
Wass. + FOC + P
69.3 + 1.1
79.4 + 1.7
84.7 + 0.6
86.3 + 0.6
88.3 + 0.8
89.9 + 0.5
CIFAR-10: GBD Algorithm Bounds
CIFAR-10: Runtime
Upper and Lower Bounds
0.4
Figure 4: (Left) Upper and lower bounds in the first 50 iterations B = 10. (Right) Increasing the wall-clock runtime of the GBD al- gorithm. All plots show mean + standard error over three runs.
0.2
Accuracy (96
70
3 min.
0.0
60
6 min.
Wass.
50
min.
-0.2
Wass.
EOC
Wass.
EDC
40
3 hr.
10
30
50
75 Number Labeled Images
5D
100
Iteration
framework can be plugged into any classification task as long as there a good feature space for optimization; for example, here unsupervised domain adaptation (Acuna al. 2021
Representations from classical active learning (Appendix E.5). Tablee the effect of using features from unsupervised pre-training by presenting accuracy CIFAR-10 and SVHN under classical active learning. We implement the exact setup of and compare against WAAL (Shui et al.) 2020), which was specifically designed for the classical setting. Although the optimization problem is harder than in the low- low-budget setting due to having less useful features and solving for larger B, our approach is still competitive and can outperform WAAL sometimes by up to 3%. This suggests that our algorithm is also effective in classical active learning.
Acceleration Techniques. Figure (left) plots the upper and lower bounds for the first 50 iterations of the vanilla algorithm Wass., Wass. + EOC, and Wass. EOC + P (i.e. including Pruning constraints) for CIFAR-10 B 10. The lower bounds for Wass. are negative, meaning the vanilla algorithm requires a large number of iterations to improve the bounds. Wass. EOC and Wass. + EOC + both improve the lower bounds. At the same time, Wass. EOC + P yields better upper bounds early in the algorithm, but is restricted to local minimum whereas Wass. EOC eventually improves over the heuristic. Thus, Wass. requires many iterations to converge, necessitating our cuts and pruning techniques.
Our algorithm is effective even without convergence. Fig- (right)) plots accuracy on CIFAR-10 10 for Wass. EOC where we terminate different runtimes and use the incumbent solution. Longer runtimes typically yield better results, especially for B < 40 (i.e., sub-optimal selection here wastes > 2.5% of the budget). However higher budgets, setting the runtime as low as 20 minutes is sufficient to obtain high-quality selections, since the marginal value of each new labeled point decreases as the labeled set increases. Note that the baselines typ- ically require between several seconds to minutes to make selections, meaning our algorithm is on average slower to generate selections. Nonetheless, the time cost of selection is still less than model training time, and for some applications, less than human labeling time (Rajchl et al.) (2016), meaning a slightly longer selection time is generally acceptable if we can yield better selections.
Wall-clock Analysis (Appendix E.6
6 DISCUSSION
When the budget for labeling images limited, every point must be carefully selected. this work, we propose an integer optimization problem for selecting core set of data to label. We prove that our problem upper bounds the expected risk, and we develop a GBD algorithm for solving our prob- lem. Under relevant features, formulating a MILP ensures that may find globally optimal core set selections, in contrast to most selection strategies that serve as efficient but ad-hoc heuristics. Our numerical results show that our algorithm is effective minimizer of the Wasserstein distance pared to heuristics. Finally, we show over four image data sets that our optimization is competitive with current baselines in active learning, especially when the labeling budget is low.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
We would like thank David Acuna, James Lucas and the anonymous reviewers for feedback on earlier versions of this paper, and Andre Cire and Jean-François Puget for early discussions on Benders decomposition.
REFERENCES
David Acuna, Guojun Zhang, Mare T. Law, and Sanja Fidler. f-domain adversarial learning: The- ory and algorithms. In Proceedings of the 38th International Conference on Machine Learning, volume 139, pp. 66-75. PMLR, 2021.
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Weed. Massively scalable sinkhor distances via the nyström method. Advances in neural information processing systems, 32, 2019.
Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 2011 SIGGRAPH Asia Con- ference, pp. 1-12, 2011.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. Proceedings of the 37th International Conference Machine Learning, volume 119, pp. 1597-1607. PMLR, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models are strong semi-supervised learners. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pp. 22243-22255, 2020b.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297, 2020c.
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of single-layer networks in unsuper- vised feature learning. In Proceedings of the fourteenth International Conference on Artificial Intelligence and Statistics, pp. 215-223. JMLR Workshop and Conference Proceedings, 2011.
David Cohn, Les Atlas, and Richard Ladner. Improving generalization with active learning. Machine Learning. 15(2):201-221, 1994.
Gabriella Contardo, Ludovic Denoyer, and Thierry Artières. A meta-learning approach to one-step active learning. arXiv preprint arXiv: 08334, 2017.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26:2292 2300, 2013.
Marco Cuturi and Arnaud Doucet. Fast computation of wasserstein barycenters. In International conference on machine learning, pp. 685-693, PMLR, 2014.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hi- erarchical image database. In 2009 IEFE conference on computer vision and pattern recognition, pp. 248-255. Icee, 2009.
Mélanie Ducoffe. Active learning and input space analysis for deep nenworks. PhD thesis, Université Côte d' Azur, 2018
Rémi Flamary. Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanis- las Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy. Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 1-8, 2021. URL CtLhttp::// jmmlr org http://apppsss22///2//
451.html
Christodoulos Floudas and Panos M Pardalos. State of the art in global optimization: Computa- fional methods and applications, volume 7. Springer Science & Business Media, 2013.
10

---

Published as a conference paper at ICLR 2022
John Forrest and Robin Lougee- Lougee-Heimer. CBC user guide. In Emerging Theory, Methods, and Applications. pp. 257-277. INFORMS, 2005.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data. In International Conference on Machine Learning, pp. 1183-1192. PMLR, 2017.
Arthur M Geoffrion. Generalized benders decomposition. Journal of Optimization Theory and Applications, 10(4):237-260, 1972.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEFE Conference Computer Vision and Pattern Recognition, pp- 770-778, 2016.
Holger Heitsch and Werner Römisch. Scenario reduction algorithms in stochastic programming. Computational Optimization and Applications, 24(2):17-2266, 2003.
Alex Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Xin Li and Yuhong Guo. Adaptive active learning for image classificatton.. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 859-866, 2013.
Giulia Luise, Alessandro Rudi, Massimiliano Pontil, and Carlo Ciliberto. Differential properties of sinkhorn approximation for learning with wasserstein distance. Advances in Neural Information Processing Systems, 31, 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. 2011.
Hieu Nguyen and Arnold Smeulders. Active learning using pre-clustering. In Proceedings of the twenty-firs. International Conference Machine Learning, pp. 79, 2004.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 115-6))335-607 2019.
Ragheb Rahmaniani, Teodor Gabriel Crainic, Michel Gendreau, and Walter Rei. The benders de- composition algorithm: A literature review. European Journal of Operational Research, 259(3): 801-817, 2017.
Martin Rajchl, Matthew CH Lee, Franklin Schrans, Alice Davidson, Jonathan Passerat-Palmbach, Giacomo Tarroni, Amir Alansary, Ozan Oktay. Bernhard Kainz, and Daniel Rueckert. Learning under distributed weak supervision. arXiv preprint arXiv:1606.00 01 100, 2016.
Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European Conference on Machine Learning, pp. 413 424. Springer, 2006.
Napat Rujeerapaiboon, Kilian Schindler, Daniel Kuhn, and Wolfram Wiesemann. Scenario reduc- tion revisited: Fundamental limits and guarantees. Mathematical Programming, pp. 1-36, 2018.
Kate Saenko, Brian Kulis, Mario Fritz, and Trevor Darrell. Adapting visual category models new domains. In European Conference on Computer Vision, pp. 213-226. Springer, 2010.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv: 708.0009,,, 2017.
Burr Settles. Active learning literature survey. Technical report, University of Wisconsin-Madiins Department of Computer Sciences, 2009.
Burr Settles. Active learning. Synthesis lectures on artificial intelligence and machine learning, (1):1-114, 2012.
Yanyao Shen. Hyokun Yun, Zachary C Lipton, Yakov Kronrod, and Animashree Anandkumar. Deep active learning for named entity recognition. arXiv preprint vrrXiv:/77..555 2017.
11

---

Published as a conference paper at ICLR 2022
Changjian Shui, Fan Zhou, Christian Gagné, and Boyu Wang. Deep active learning: Unified and principled method for query and training. In International Conference on Artificial Intelligence and Statistics, pp. 1308 1318. PMLR. 2020.
Oriane Siméoni, Mateusz Budnik, Yannis Avrithis, and Guillaume Gravier. Rethinking deep active learning: Using unlabeled data at model training. arXiv preprint crXiv:1911.08177 2019.
Samarth Sinha, Sayna Ebrahimi, and Trevor Darrell. Variational adversarial active learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5972-5981, 2019,
Robert Tarjan. Dynamic trees as search trees via culer tours, applicd to the network simplex algorithm. Mathematical Programming. 78(2):69--177, 1997.
Wim van Ackooij, Antonio Frangioni, and Welington de Oliveira. Inexact stabilized benders' de- composition approaches with application to chance-constrained problems with finite support. Computational Optimization and Applications, 65())x637-669, 2016.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Dan Wang and Yi Shang. A new active labeling method for deep learning. In 2014 International Joint Conference on Neural Networks (IJCNN), pp. 112-119. IEEE, 2014.
Gert W Wolf. Facility location:
concepts, models, algorithms and case studies. Series: Contributions to Management Science: edited by Zanjirani Farahani, Reza and Hekmatfar, Masoud, Heidelberg, Germany, Physica-Verlag 2011.
Mark Woodward and Chelsea Finn. Active one-shot learning. arXiv preprint arXiv: UrXiv:1702.065555 2017.
Kai Yu, Jinbo Bi. and Volker Tresp. Active learning via transductive experimental design. In Proceedings of the 23rd International Conference Machine Learning, pp. 1081-1088, 2006.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
A PROOFS OF STATEMENTS
Proof of Theorem 1. Let D. [[[(x,) [(x)] distance matrix between the labels of points in D. Let CK be the set of K K-Liisshitz functions. Using the Kantorovich-Ruheenstiin Duality Villani 2008), we bound the core set loss by a Wasserstein distance
B Σ j=l
[x M(xi): w)
((x,, ((x))x w)
N
1
$ sup iECx
E(x; f(xx) ; w)
N
1
max A,p
N
N
B ② 1 + p & 1 < (Dxx +D))
= x
s.t.
A
min T20
<(Dx + +DDy),
s.t.
r1= N
r
B
The first line introduces probability masses and upper bounds the objective with supremum over all K K--Lipshhitz functions i Cx- The second line replaces ? with vectors μ and that satisfy the Lipschitz property. The final line takes the dual of the linear program.
Next note that [0(x))) [(xx)) s C, meaning that for any feasible to the Wasserstein problem, have the following inequality:
N
N
DD r
[2(x;) - 2(x:)][T,
i=1 P=l
C
The last equality follows from the constraints in the Wasserstein distance primal program implying 1'r 1. We now rewrite the objective of the linear program
K(Dx cD, r)
((Dx, I) + te(Dy, S (Dx,, 1) + KCs.
Since the second term does not depend r, remove it from the optimization objective and complete the proof.
Proof of Corollary The proof follows from Lemma 2 (see Appendix C). which states that if the objectives and constraints of the optimization problem are (i) separable in the decision variables and (ii) linear, then the algorithm will converge. Problem (4) satisfies the requirements of this lemma, meaning that our algorithm terminates in finite iterations.
Proof of Proposition 1. Let (17*, TT) be the optimal solution to W-MP and let I" be the optimal primal solution W(C(7t"), D). To prove that each inequality is optimality cut, we show that
13

---

Published as a conference paper at ICLR 2022
they met by (n" T²". We first prove the Lower Bound:
2 Dxx: r
T
-
-
N
D
1 ==
min Pe()....))
(DarlDay 0} Σ
1
y=1
min PE(....)
(DiriDay > 0} B²
The second line follows from expanding the trace and noting I π / The inequality follows from taking the minimum over all D and the last line follows from I = /B.
To prove the Triangle Inequality, note that the Wasserstein distance distance metric and then satisfies a triangle inequality by definition. That is, for any # E P.
W(C(==)), ), D) W(C(+), ((C(
The hand-side of the incquality is a Wasserstein distance which can be lower bounded similar to before:
min
Σ
D
((C(('),C(#))
X, Ex(E((+))
S.
T1
B π
r =
B #
min 1'0
Σ
min
(Der)Day 03
Σ
Fie
I'EfI.....
x, EC(()
P=1
S.
r1
B π
r 1 =
B #
1 = (Di > 0)
min ('E(L.....) N) X2 EC(+))
The key difference in this sequence from the previous is that we only consider indices i' where X C(+t). Finally, recall that 17" 2 W(C(m")) Substituting these inequalities and rear- ranging (9) completes the proof.
Finally, to prove the Dual Inequality, note that
1)" Z W(C(F), - W(C(#), W(C(")))
(10)
We lower bound the second term by obtaining an upper bound on the Wasserstein distance:
N
W(C(A),
Dr
N
max #e DE(!.....NN) N)
(Dir)
Σ
P=1
1 (Di.
max "E(l....NN
14

---

Published as a conference paper at ICLR 2022
where the upper bound now follows from taking maximum. Subtracting from both sides lower bounds the second term in (10). Finally, we lower bound (C(+T)), D) by considering the Wasserstein distance dual program
1 k
W(C(T"),
=
max
Aij
N
s.t.
A
x1++u
B -
N
Note that the optimal dual variables (A, ji) for (C(#)) D) are feasible solutions for the Wasserstein dual problem W (C(""),, D) and thus, also lower bound on the Wasserstein distance. Substituting the corresponding objective value into (T0) completes the proof.
B ON THE LIPSCHITZ CONTINUITY ASSUMPTION
Our main result in Theorem D states that the Wasserstein distance upper bounds the core set loss if the training loss function 8(x, y; w) is K-Lipschitz continuous over the data set space X' x y for Lipschitz continuity assumptions are commonplace in the development of active learning theory (Sener & Savarese 2017: (Shui et al.) 2020). We show below that our assumption is relatively mild and can sometimes be satisfied in practice.
fixed model parameters
Our assumption builds from Sener& & Savarese 2017) who require their loss function {(x, y; w to be Lipschitz continuous over the input features X only. They show that convolutional neural networks trained using Mean-Squared Error (MSE) loss meet their assumption. Although we require the loss function be Lipschitz in both the input and output, we can extend the result Sener & Savarese (017)) to show that convolutional neural networks are Lipschitz in the input-output space as well. We first state the Lemma of [Sener & Savarese (2017) before proving our corollary.
Lemma 1 (ennrr& & Savarese (2017)). Consider the C-class classification problem over feature X and me-hot-encodee label y := (ei...., cc} spaces. Let F X + ý be a convolutional layers and n fully connected layers. Then, there exists a constant o > O such that the MSE loss function y( w) == [|F(x; - -yll is continuous in x for fixed y and w.
neural network with n. mnvoouutionalmmappoll---e
VVCIlazete
While the lemma states that [[[;; w) - -yllg is Lipschitz continuous, the proof further implies that by composition, the neural network F Fxx; w) is also Lipschitz continuous with the same constant.
Corollary 2. Consider the metric space (X' x ), ||*|| + elul) using features X and labels y (1...., C}. Let e(y) denote the one-hot encoding of y. The MSE loss function f(x, y: w) [F(x; -0--eeyy e(y))l is Lipschitz continuous in (x, y) fixed w.
Proof. The proof is straightforward extension of Lemma (x',e(y')) e(v')). We bound with the following steps:
Consider two pairs (x, e(v)) and
(xx, ys w) Exx' g':::w)) w)l
(le(y) () [/e(s/) ())l2
le(y) -ev')) F(x'; w) F(x; w)ll2
ee(y) -e(v)) 2112 || w) - F(x; w)ll2
< ly - v'l + VC-I
a (motms)
||x x- 1x1122
C
/C VC-I
max
(Ely v1l + ||x x1112)
C
The first two inequalities follow from applying the Reverse Triangle Inequality and then the Triangle Inequality. The third inequality follows from Lemma [1 and ly vll 2 |e(v) e(v') The final inequality follows from taking the maximum of the coefficients.
Our result holds for MSE loss, specifically. In practice, the Cross-Entrop loss, which does not satisfy this Lipschitz continuity assumption. Nonetheless, the empirical effectiveness of our strategy highlights its usefulness.
15

---

Published as a conference paper at ICLR 2022
C BACKGROUND ON GENERALIZED BENDERS DECOMPOSITION
Generalized Benders Decomposition (GBD) is an iterative algorithm for solving non-convex con- strained optimization problems (Geoffrionn 1972). We summarize the general steps of this algorithm below and refer the reader to Rahmaniani et al. 2017) for a recent survey on this methodology.
Let X C R and y y S R be variables and consider the problem s.t. g(x. = O,
min
y(x,y)
(11)
xE
where f(x, y): Rd Rd + R and g(x, Rdi x Rd + RM are convex functions but X' and } may be non-convex sets. This problem is equivalent to the following bi-level Master Problem (MP):
min nyey
s. 7 inf (S(x,y) + y), gxxxxy)) AA E I
xEX
where 1j is a slack variable which when minimized, is equal to the optimal value of problem (II) This MP can also be re-written with single constraint by replacing the right-hand-side of the inequality with the Lagrangian I(y) == SUPAER" (nfxex(f(x,)) + y))
Although MP contains an infinite number of constraints, we can instead solve a Relaxed Master Problem (RMP):
min 7
s.t. 17
inf (f(x,)) A gx((x))) A XEX
n.yyy
where A C n consists of a finite set of dual variables. Let ,x""""""" be optimal solution to MP and let () ) be an optimal solution to RMP. Then, n S 77" presents a lower bound to MP (and therefore problem [1b). Furthermore, L(ý) 2 f(x", y") gives upper bound. Finally, let & be the minimizer of Ly). Then {) is a feasible solution achieving the above upper bound.
Carefully selecting A will yield tighter relaxations MP (Floudas & Pardalos) 2013). GBD pro- poses iteratively growing A and solving increasingly larger RMPs until the upper and lower bounds converge. We initialize with feasible ý and À 0. Then in each iteration E 1, 2,.,...) we:
1. Given solution (7', )") solve the Lagrangian L(y") obtain primal-dual solutions (x 29)
2. Update + A (X* and solve RMP obtain a solution (f/++1, ( +
The algorithm terminates when L()") if is below tolerance threshold E > 0.
For many problems, the above algorithm will converge in finite number of iterations. This is referred to as Property (P) in the literature (Geoffrion) 1972, Floudas & Pardalos, 2013).
Lemma 2 (Geoffrion )9722.. Consider the non-convex optimization problem (7]. If yx.
+ (x( Generalized Benders Decomposition terminates a finite number of iterations.
fely) and y (1 + g2(y) are separable, linear functions, then for any > 0,
Even so, the number of iterations may be exceedingly long. As result, the modern literature in GBD explores new constraints and heuristics to quickly tighten the relaxation of RMP versus MP. Often, these techniques are customized to the structure of the specific optimization problem (II)
being solved. In Section 3.2
we propose new custom constraints to improve the algorithm.
D DETAILS ON OUR GENERALIZED BENDERS DECOMPOSITION ALGORITHM FOR MINIMIZING WASSERSTEIN DISTANCE
In this section, we provide further details on the GBD algorithm used to solve problem (4). To com- plement the Enhanced Optimality Cuts in Section 3.2 first discuss an additional set of pruning constraints to improve our algorithm. We then detail the full steps of the algorithm and provide Python-style pseudo-code.
D.1 PRUNING CONSTRAINTS
We first define the pruning constraints used to improve our GBD algorithm. These constraints com- plement the Enhanced Optimality Cuts introduced in Section 3.2 additional set of constraints
16

---

Published as a conference paper at ICLR 2022
Algorithm Generalized Benders Decomposition (GBD) for the Minimum Wasserstein Distance
1: Input: budget B; initial core set ft; constraint sets A = 0, p+ = { P & upper bound
B = oc; lower bound B = -o; hyperparameters B 3 tolerance E; maximum time limit T
2: repeat
3: Solve ((C(#). D): : r arg min Problem 1 (A, p)) arg max Problem
4:
A Au i, Å, }
// Update GBD constraint set
5:
if D) I B then
6:
B min W (C((F),))
// Update upper bound on optimal value
7:
P+ U }
// Update Near Neighbourhood set
8:
else
9:
P + P- (
// Update Prune Neighbourhood set
10:
end if
11:
Solve W-RMP(A):
(i, ボ) t arg min T.PE
1
t. 7 B
+ W(C (t,,
B
+
Lower Bound, Eq.
6
Triangle Ineq.. Eq.
V( ( ((+,I,A,)) VT E P+
Dual Ineq.. Eq.
T * 2 8+
T < B.
VT P
12: B < max B, 13: until 7 hours or B <E
// Update lower bound optimal value // Exit at timeout or convergence
used accelerate the algorithm. However, these pruming constraints do not preserve the conver- gence criteria of Corollary | since there is no guarantee that the optimal solution will satisfy them. Instead, these constraints are heuristics that our numerical results empirically show improve the active learning strategy.
Let p+ and P- denote two sets of good and bad candidate core sets म, respectively, and let 8+, 8 E 1) denote two hyperparameters. In each iteration, we obtain candidate Ā and corresponding upper bound W (C D) to the W-MP. If this upper bound is a new incumbent (i.c., is lower than the previous upper bounds) then we update pt ( } and limit the search to within a Hamming ball of size 8+ B around á. Otherwise, we update P U {+} and remove a Hamming ball of size 8- B around ft from the search space. These two pruning techniques can be described by the following linear constraints: Vá E p*, π T 2 3+ and V E P-
π T # < 3
D.2 ALGORITIM STEPS AND PSEUDO-CODE
Algorithm [ details the mathematical steps of the GBD algorithm and Figure provides a Python- style pseudocode snippet. We formulate our algorithm in a loop by iteratively solving our opti- mization problem and adding new constraints. The main dependency of this optimization algorithm lies in an off fff-the-shelf Wasserstein distance computation library (Flamary al. 2021) and a MILP solver (Forrest & Houger-Heimer] (205). Note that rather than running GBD for fixed number of iterations, Algorithm performs iterations until a maximum time limit or until the upper and lower bounds B converge under tolerance Furthermore in the implementation of the algorithm, we may also select hyperparameters for the MILP solver being used to solve each instance of RMP(A). For experiments, only tune the time limit and the minimum optimality gap. That is, we set the solver for W W-RMP(A) to timeout 180 seconds or until the solution finds is within 10% of optimality.
17

---

Published as a conference paper at ICLR 2022
Input features Array of feature vectors
N, = # Total number of points and budget
prev_selected = ... # Array of indices selected in earlier rounds
Calculate distance matrix arcs = pairwise_distance (features)
Define K-RMP MIP model and variables prob mip.
pis [preb.ade) aecbbaddd_arree (var_type-mip.BBl BINARY for in range (N)
eta var
Set objective and constraints
prob.objective mip.minimize (eta) prob +- mip. xsum (pis) B
If we labeled point in an earlier round, then it should be for i in prev_seles selected: prob += pis[i] ==
GBD loop 1b, ub, tol, max_time -inf, inf, 1c-3, 10800 while 1b < tol and current_time () max_time: Run MIP solver to populate pis, eta prob.eptimize()
Compute Wasserstein distance and dual variables with PCT pis_x x Ip.x for p in pisl w_hat, info - ot.emd2 (pis_x / N, ones (N) N, arcs, log-True) lambda_hat, mu_hat = infol'u') ul, infol'v(]
Update bounds 1b, ub max (lb, eta.x), (ub, w_hat)
Add Benders cut prob += eta >= hat mip.xsum( hambda [i] (pisli) pis.xli)) / for in range (N)
Triangle inequality cut prob min Dilil pislil for range )
min w_hat (sum
# Compute coefficients according to Proposition 1
Dual inequality cut max_Di ... Compute coefficients according to Proposition 1 prob eta >= w_hat mip. xsum (lambda_hat
max_Di(i)) + pisli] B hat / N for i in (N)g)(N))
Pruning constraints if ub w_hat:
prob += B aeta_plus <= mip.xsum! pislil pis.xli] for i in range (N)
else: prob beta_minus mip. xsum pis[i] pis.xli] for in range (N)
Output
return where (pis.x 1) All selected indices far
Figure 5: Pseudocode of the GBD algorithm used to solve our optimization problem. The above code uses the Python-Min MIP (mip) and Python Optimal Transport (ot) libraries.)
18

---

Published as a conference paper at ICLR 2022
D.3 REDUCING THE COMPUTATIONAL COMPLEXITY
The original problem (4) is a MILP with N + N variables and 2N + constraints. This problem is too large to solve on standard computers when N 2 50, 000, which is typical for deep learning data sets. Instead in Algorithm ! we repeatedly solve two smaller sub- sub-problems: (i) W-RMP(A) to obtain selections it and (ii) the Wasserstein distance WCC D) to obtain dual variables X
W-RMP(A) is MILP with N + variables and |A| + constraints. Incorporating the Enhanced Optimality Cuts and the Pruning Constraints leads to a MILP with N + 1 variables and 5|A] + constraints. From our experiments, |A] typically on the order of 100, meaning that this MILP contains several orders of magnitude fewer variables and constraints than problem ( We can find an optimal or nearly optimal solution to this MILP in less than 180 seconds for most settings.
Before computing the discrete Wasserstein distance W (C) D), we first need the distance matrix of features Dx For Euclidean distance, computing this has complexity OddN²) where d is the feature dimension. Note that this is one-time cost and that once construct the distance matrix, we can store it in memory for the remainder of the algorithm.
To compute (CC+)), D) in each iteration, use an off-the-shelf solver, POT (Flamary et al., 2021]. POT applies the Network Simplex Algorithm (Tarian 1997), which is an algorithm for solving network flow problems over graphs. Because W(C(#.. D) is a minimum flow over graph with 2NN nodes and N2 edges, our complexity is O(Ng 2)2).
When B is much smaller than N. we can often simply approximate Å. We first remove nodes corresponding to â
rewrite W(C(#), D) as an equivalent network flow with N + B nodes and NB edges, resulting in complexity O(N2(log 2) However, from (2). this problem returns dual variables corresponding only to the B points for which Å; = 1. We can find the remaining dual variables via a c-transform (Peyré et al. 2019), which requires solving a minimization problem over an N-length array for each remaining variable, We refer the reader to Peyré et al. (2019) for details.
This approach does not guarantee an optimal Ò, but we find that it works well in practice.
Rather than exact algorithms, could also approximate W ((C(#), D) with Sinkhorn distances Cu- turi [2133 Peyré et al. (019). These can typically be computed faster than exact approaches and can also be scaled large N with further approximations (Altschuler al., 2019). Moreover, Sinkhorn distances can be slotted directly into the vanilla GBD algorithm by replacing the dual regularizer
with the gradient of the Sinkhorn distance in the Benders constraints (Cuturi & Doucet 2014 Luise al., 2018). However, they may not necessarily satisfy the EOC in Proposition | and thereby prevent further accelerations.
E COMPLETE NUMERICAL RESULTS
This section expands the numerical results summarized in the main paper. Below, we summarize the main points:
details the hyperparameters that were used in our GBD algorithm and opti- mization solver. We also describe model choices and training settings used in our image classification and domain adaptation experiments.
Section B.T
Section E.2 describes our experiments on optimizing problem (4). We first summarize the related scenario reduction literature and highlight the M-Medoids Cluster Center algorithm baseline. We then expand the numerical results from the main paper to show that for gener- ating high-quality solutions problem 44. our approach typically outperforms k-medoids and sometimes by up to 2x. Furthermore, these improvements remain even when we limit our algorithm comparable runtimes with k-medoids.
Section E provides the full table of values for active learning experiments the three image classification data sets. In addition to the results in the main paper, this section shows that our approach is consistently effective even up to budgets of B = 180.
Section E.4 provides the full table of values for active learning with domain adaptation experiments. We evaluate all six source-targe target combinations on the Office-31 data set to show our approach either outperforms or competitive with the best baseline. To further
19

---

Published as a conference paper at ICLR 2022
compare against k-centers, perform statistical t-tests in a head-to-head setting. Our approach statistically outperforms k-centers for more budgets and data sets.
Section 1..5 details our ablation on classical active learning without self-supervised fea- tures. We first describe the experiment setup and then expand on the results in the main paper, showing that our algorithm is effective even without eeffssupervised features and in higher budgets.
Section E.6 provides the full table selection runtimes. Most baselines require at most few minutes select points. We further discuss the downstream effect of our algorithm having longer runtimes in practice.
highlights two additional results not discussed in the main paper. We first ablate the value of customizing the base metric in the Wasserstein distance by showing that Cosine distance yields significant improvements over Euclidean distance on the CIFAR- 10 data set. We then provide a qualitative analysis of our selections by plotting t-SNE visualizations of the feature space as well as samples of images selected. In general, our visualizations show that we can better cover the feature space than baselines.
Section E.7
E.1 METHODS
We first detail hyperparameters for the optimization algorithm, methods for the image classification experiments, and methods for the domain adaptation experiments. All experiments are performed on computers with a single NVIDIA V100 GPU card and 50 GB CPU memory. Our optimization problem is solved on CPU.
Algorithm Settings. When formulating the Wasserstein distance problem, we use Cosine distance (i.e., l2 normalize our features) the base metric for the image classification experiments. Co- sine distance is a better choice than Fuclidean distance here because the features are obtained with SimCLR, which involves maximizing a Cosine distance between different images; that is, the opti- mization and feature generation use the same base metric. We include ablation tests in Appendix E.7 comparing Cosine versus Euclidean distance on CIFAR-10. We test both Cosine and Euclidean dis- tance for the domain adaptation experiments. These experiments use features obtained via f-DAL, which is not necessarily tied to Cosine distance.
We implement the optimization problem using the COIN-OR/CBC Solver (Forrest & Lougee- Heimer, 2005). Since it crucial to run as many iterations as possible obtain better solutions, we set the solver optimality gap tolerance to 10% and a time limit of 180 seconds to solve W-RMP(AA in each itcration. We also warm-start our algorithm with the solution to the k-centers core set, i.c., to = #t-eemeers for image classification and k-centers or k-medoids for domain adaptation. We run Algorithm with æ = 10-3 and = hours for STL-10,, CIFAR-10, and Office-31, and T 6 hours for SVHN, which contains a larger data set. Finally for Wass. + EOC P, we set (x+ ) = (0.6, 0.99). These are only optimization parameters and can be tuned by evaluating the objective function value of the optimization problem.
Image Classification. Table the differences in setup for each the three data sets used in the image classification experiments. For each experiment, we use ResNet feature encoder with BeaichNorrnReLU-Lineee
two-layer MLP
head. The first linear layer has a 64--dimension output in order to reduce the dimensions of the feature space. We use a 64-dimension second layer in the SimCLR pre-training step and 10-dimension second layer during supervised learning. The choice of specific ResNet encoder was made based on the computational requirement of training on single GPU under the required batch sizes.
For each experiment, we use the default test sets to evaluate our strategies. In the SimCLR rep- resentation learning step, we train for 800 epochs with initial learning rate of 0.1 decaying to 0.001. We implement SimCLR following the steps of [hen et al. (2020c) with the following ran- dom data augmentations in their default PyTorch settings: resized crops, horizontal flips, color jitter, and grayscale. For SVHN, we omit the horizontal flips and increase the scale of the crops to (0.8, 1), because this yielded better representations in our experiments. In the supervised learning step, train with cross entropy loss, random crops and horizontal flips, and a batch size 128 with constant learning rate of 0.002 for 1600 epochs.
20

---

Published as a conference paper at ICLR 2022
Table 5: Summary of our setup in the image classification experiments. iterations of each data set, we use only half of the labeling budget.
"In each of the first two
Dataset
Unlabled pool
Budget per itcration
Model
SimCLR batch size
Algorithm runtime
STLIO
5, 000
20
ResNet-18
128
hrs.
CIFARIO
50, 000
20
ResNet-34
512
hrs.
SVHN
73, 257
20
ResNet-34
512
hrs.
Table 6: Summary of our setup in the domain adaptation experiments. randomly split the target set to 70% training and 30% testing sets.
"For each experiment, we
Task
Unlabled pool"
Budget per iteration
Initial solution
Basc
metric
DSLR to Amazon
1, 972
50
k-centers
Euclidean
Web to Amazon
1, 972
50
k-medoids
Euclidean
Web to DSLR
349
10
k-centers
Cosine
Amazon to DSLR
319
10
k-medoids
Euclidean
DSLR Web
557
10
k-medoids
Cosine
Amazon Web
557
10
k-centers
Cosine
Domain Adaptation. Table 6 details the differences in setup for each of the tasks in the domain adaptation experiment. We use ResNet-50 + one-layer bottleneck (Linear-Batee Batchhorm--eeeeeee Dropout) encoder and two-layer classification head Lenear-ReLU-Drrpouut 50 is initialized with Imagenet-pretrann weights. The bottleneck sets the feature space dimension 100. The second layer of the classification head reduces the dimension 31 for the number of classes
The ResNet-
For each experiment, we randomly partition the target data set into 70% for training and 30% for testing. We perform the representation learning step using the full labeled source data set and the unlabeled target training data set. We then perform the supervised learning step using only labeled target training data. The representation learning performed via the unsupervised domain adapta- tion algorithm, f-DAL (Acuna et al., 202I). We train for 20 epochs with 1, 000 iterations per epoch. We use a learning rate of 0.004 decaying stepwise and batch size of 32, which the default parameters of Acuna et al.] (202T). In the supervised learning step, we train with cross entropy loss with the same learning rate and batch size.
E.2 OBJECTIVE FUNCTION VALUE
We evaluate GBD on minimizing the Wasserstein distance by comparing it to the k-Medoids Cluster Center algorithm from scenario reduction for stochastic optimization. We first briefly summarize the scenario reduction problem. We then expand the numerical results in the main paper, showing that for large problem sizes, our algorithm yields better minimizers of the Wasserstein distance.
Background. Consider a general stochastic optimization problem
min Ex-plf(x, w)]
WEW
where fxx w) is an objective function, w E W is the variable to optimize and x ~ P is a random variable, here referred to as a scenario. Given data set D == { of N scenarios, we can solve the Sample Average Approximation (SAA), which corresponds to minimizing the empirical expected value. Machine learning a special case of the above problem where f(x, w) corresponds to the loss function, w to neural network weights, and to training data.
SAA may grow difficult to solve with large data sets, especially if W non-convex or contains integral constraints. Here, scenario reduction is the problem of formulating an approximation of the SAA by using only subset := , constructing this subset by minimizing the Wasserstein distance between C and D. Le.,, by solving problem (4). When N is large, Heitsch & Römischi (2003) propose the k-Medoids Cluster Center algorithm heuristic. Although the algorithm is computationally easy to implement, making
B C of B scenarios. Heitsch & Römisch (2003) consider
21

---

Published as a conference paper at ICLR 2022
Table 7: Head-to-head comparison of our solver versus k-medoids on objective function value of problem (4) at different budgets. For each data set, the best solution for each budget is bolded and underlined. All entries show mean + standard deviation over five runs.
B
STL-10
CIFAR-I0
SVHN
I-medoids
Wass. + BOC
A-medoids
Wass. EOC
k-medoids
Wass.
EOC
10
0.290 1 0.028
0.281
0.005
0.258
0.013
0.322 1 0.012
0.152 1 0.009
0.153 1 0.007
20
0.132 + 0.015
0.134
0.007
0.142 0.013
0.176 1 0.010
0.172 + 0.010
0.093 + 0.010
40
0.109+ + 0.005
0.122
0.007
0.118 + 0.005
0.125 + 0.006
0.164 + 0.005
0.093 + 0.008
60
0.110 + 0.006
0.116 = 0.003
0.120 = 0.005
0.092 + 0.006
0.175 = 0.005
0.100 : 0.006
80
0.100 1 0.007
0.101
0.002
0.109 - 10.003
0.077 1 0.004
0.178 1 0.003
0.098 1 0.007
100
0.097
0.003
0.096
0.002
0.104 0.006
0.097 + 0.003
0.179 + 0.006
0.091 + 0.006
120
0.092
0.004
0.092
0.004
0.093 0.007
0.064 + 0.006
0.178 + 0.004
0.085 0.004
140
0.089
0.004
0.087 0.004
0.089 0.007
0.059 + 0.002
0.173 = 0.004
0.080 0.004
160
0.093 T 0.005
0. 0.090- 0.004
0.099
0.005
0.072 1 0.005
0.173 1 0.005
0 087 0.004
180
0.087 + 0.005
0.085 0.002
0.096 0.004
0.072 + 0.003
0.170 + 0.005
0.089 + 0.004
Table 8: Head-to-head comparison of Wass. + EOC with different runtimes versus k-medoids objective function value of problem (4) for the CIFAR-10 data set at different budgets. The best solution for each budget bolded and underlined and the second best solution is underlined.
k-medoids
Wass. EOC
3 min.
6 min.
20 min.
hr.
3
0,258
0.013
0.352
0.010
0.328 = 0.010
0.337 1 0,008
0.326 1 0.007
0.322 0.012
0.142
0.013
0.198
0.012
0.184 0.003
0.178 + 0.008
0.178 + 0.008
0.176 + 0.010
40
0.118
0.005
0.159 1: 0.010
0.131
0.008
0.126 1 0.003
0.122 1: 0.007
0.125 1 0.006
60
0.120 = 0.005
0.118 = 0.016
0.103
0.006
0.102 + 0.010
0.089 + 0.007
0.092 + 0.006
80
0.109 + 0.003
0.102 + 0.020
0.091
0.008
0.084 + 0.008
0.078 + 0.002
0.077 + 0.004
100
0.104 = 0.006
0.088 = 0.009
0.077 = 0.003
0.076 + 0.007
0.071 :: 0.002
0.097 + 0.003
120
0.095 1 0.000
0.082 1 0.006
0.072 0.006
0.068 1 0.004
0.065 1 0.003
0.064 1 0.006
140
0.089
= 0.007
0.073 0.004
0.068
0.001
0.064 0.004
0.061 + 0.004
0.059
160
0.099 0.005
0.084 0.005
0.079
0.002
0.076 + 0.003
0.075 + 0.004
0.072 0.005
180
0.096
0.004
0.080 0.003
0.075
0.003
0.072 + 0.002
0.072 + 0.002
0.072 0.003
desirable in practice, recently Rujeerapaiboon et al. (018 show that k-medoids can potentially be a poor approximation in the worst case, and also introduce a new approximation algorithm.
Finally, we note that the scenario reduction literature rarely considers problem sizes of the scale in our active learning tasks, with numerical experiments in most cases ranging up to 10 In contrast, the SVHN data set requires N 75, 000.
Comparing the Minimum Wasserstein Distance. Our GBD algorithm directly solves the integer optimization problem (4) rather than a heuristic or approximation algorithm. We compare against k-medoids on minimizing the Wasserstein distance for the three image classification data sets.
Table presents the complete results of our method versus k-medoids for each data set. We run the solver for three hours for STL-10 and CIFAR-I0 and for six hours for SVHN. Although the algorithm has not yet converged, for each data set, our approach is competitive for all settings (except for B < 20 at CI),R-10), and especially outperforms k-medoids for B 2 120. Finally, note that for SVHN, we reduce the objective function value by over half compared to k-medoids.
To further ablate our method, we also compare different runtimes of CIFAR-I0 with k-medoids in Table g Even down to three minutes, we often get better minimizer than k-medoids. Note from Table 12 that k-medoids requires on average several minutes to compute a selection. This suggests that our algorithm may have more general use cases outside of active learning, such as an alternative to k-medoids in scenario reduction.
E.3 IMAGE CLASSIFICATION
Table 9 lists the means + standard deviations of accuracies shown in Figure 2 tently outperform the baselines for both STL-10 and SVHN, with the exception of the first round in STL-10. On CIFAR-10, our models outperform in the first two rounds, but afterwards remain competitive with k-centers (i.e., less than 2% difference in accuracy). On SVHN models sim-
Our models consis-
22

---

Published as a conference paper at ICLR 2022
Table 9: Numerical values of main results in Figure 2 over five runs. The best model for each budget range is bolded and underlined and the second best model is underlined.
All entries show mean + standard deviation
$11-10 10
Random
Confidence
Eatropy
k-medoids
c-centers
WAAL
Wass. + EOC
Wass. EOC +
10
30.2 + 6.1
30.2 6.1
30.2
45.7 3.5
37.4
30.2
43.1 0.7
11.4
20
12.8
+ 3.6
37.8
33.6
2.4
4.6
4.
51.5 2.1
3.6
40
51.0 + 3.4
46.6 +
48.5
3.4
1.2
53.5 2.9
53.6 165--44 4.2
60.4
1.5
58.7
1.8
60
59.1
+ 1.6
55.0
57.2
60.0
59.7
62.9
63.8 1.6
80
62.7
= 1.3
391
2..
2.3
61.111
60
67.9
66.5 1.2
100
65.4
+: 1.1
63.4
63.1 2.2
64.++1
6.72
6244 1.8
69.3
0.4
70.8
1.4
120
67.9
+ 1.1
66.8
06.6
66.3
6..7
64.3 1.5
71.0
1.4
73.3
0.6
140
70.8
2.2
7.00
6.
11
66.7=18
73.0
73
0.5
160
71.1
+ 0.5
2.5
7..4
68.5
1.
67.7=2.0
73.4
73.6
0.5
180
71.3
+ 1.1
71.0 = 1.3
0.6
1.0
71.10
68.6 1.7
73.7 1.1
73.7
0.9
CIFAR-10
Random
Confidence
Eatropy
k-medoids
k-centers
WAAL
Wass.
EOC
Wass. EOC
10
38.0
+ 9.7
38.0 9.7
9.7
4.9
37.0
38.0 9.7
50.7 3.0
46.8
20
51.8
+ 8.5
37.7 + 4.5
3..4+33.
53.7 7.0
5.9
40.9
1.9+555 5.5
63.7 + 4.8
65.3 2.9
40
65.1
+ 3.1
4.1
40.5 6.3
4.0
74.7 4.3
50.1
333
72.7 2..7:10 1.8
60
70.1
- 3.6
5.8
5..0
6.21
7.9
5..
77.6 1.3
78.4
80
74.5
+ 3.9
5.6
5.2
7.0+15
81.0 1.2
62.7=58
80.3
0.9
79.5
100
71.6
+ 3.6
67.8
6,6
0.66
0.6
61. 5.8
81.
412+1.4 1.4
81.5 $1.5400 0.7
120
78.2
+ 2.4
71.0+22
66.4
+4.0++088
82.3
+.33+..77 U.7
65.7 65.7 -37
82.4
0.6
82.1
0.5
140
80.1
1.9
74.2
3.1
4.
0.4
53.0
09.0=11
83.
0.6
160
81.0
- 1.9
75.9
= 3.6
3.7
0.8
83.0
1 0.7
69.0
1.4
83.3
0.7
83.2 + 0.9
180
82.0
4: 1.3
74.9
2.8
74.9 + 3.5
+
83.7
0.6
68.9
1.5
83.4 + 0.6
83.4 1.1
SVHN
Random
Confidence
Entropy
k-medoids
k-centers
WAAL
Wass.
BOC
Wass.
EOC P
37.1
4.9
37.1
37.1
35.7
28.6
37.0
38.0 2.9
20
47.2
+ 4.2
36.9
41.4
J6.1
6.44
4..5=223 2.3
48.3 + 3.6
49.4 4.0
40
57.5
= 6.3
48.3
5.
58.6
51.2
3.6
63.2
13.2:653 6.5
63.8 = 6.1
60
63.8
+ 5.3
5.9
56.1 228
6.0
6.9
47.8
69.4
72.1 6.6
80
61.7
3.7
2..
3.3
70.7
5.4 2.8
73.1 2.5
TTA
100
68.1
+ 2.8
58.5 + 3.3
64.3 2.0
73.6
82.8 + 2.2
52.3 - 2.9
77.6 4 3.1
80.5 3.1
120
72.1
+ 1.8
59.9
67.2
7.5
84.3
1.7
54.9
81.6
82.9
140
78.8 2.1
4.
11
8.0
87.3
3.1
85
87.6
2.6
160
80.4
+ 1.6
68.8 4.0
73.6 + 1.5
8.2
87.6
1.9
58.2 - 1.9
86 9
2.6
87.6
1.8
180
81.2
+ 1.1
69.9
2.5
74.2
1.7
83.3 2.2
S7.3 1.4
62.1
86.7
2.6
88.6
1.2
ilarly outperform in the first four rounds at which point k-centers catches up and the two remain competitive for the rest of training. Note that as the budget increases to = 180 points, all of the methods converge final accuracy.
E.4 DOMAIN ADAPTATION
Table I0 lists the means + standard deviations of accuracies for all of the different source-targes combinations of the Office-31 data set. We summarize the results below.
Amazon as target data set. For both DSLR to Amazon and Web to Amazon, our framework dominates all baselines over the entire budget range. These two domain combinations are the two hardest problems, the unlabeled target data set, Amazon, is much larger than the source data sets and the test accuracy on Amazon is always lower than 80%.
DSLR and Web as target data set. For the other source-target combinations that have smaller and "easier" target domain, our framework still outperforms the extremely low budget regime B < 20 and then remains competitive with k-centers at the higher budgets. It is worth noting that when DSLR or Web are the target domains, the top test accuracies are near 100%, meaning there is little room for variation.
To further compare our framework against k-centees on domain adaptation, Table shows the head-to-head accuracies of our model versus the baseline with t-tests to compare for statistical sig- nificance. The results here further validate our analysis on Table I0 as we are statistically better than k-centers for 15 out of total of 42 tests and k-centers statistically outperforms for only six
23

---

Published as a conference paper at ICLR 2022
Table 10: Numerical values of results domain adaptation. All entries show mean + standard deviation over five runs. The best model for each budget range is bolded and underlined and the second best model is underlined.
DSLR to Amazon
Random
Confidence
Eatropy
k-medoids
h-centers
WAAL
Wass. + EOC
Wass, EOC +
50
45.9 + 3.2
17.5 +: 2.0
17.1 = 2.8
6L.9 2.8
59.7 3.0
46.6
2 2.1
62.5 =
00.0
61.8
+ 1.9
2.3
36.2 1.7
66.9
2.4
2.2
54.6 4.2
67.3
150
68.1
+ 0.2
52.9 2.0
46.9 3.6
68.8 = 0.8
68.0
= 1.5
62.0 + 1.9
71.4 1.0
71.3
200
70.7
+ 0.8
60.3 2.0
55.0 2.6
70.2 = 0.9
70.3
+ 1.5
66.4 2.8
T2.5 1.1
73.8 0.9
1.2
62.1
71.9
71.4
69.5
300
73.2
+ 0.6
69.0 + 1.3
67.4 2.8
72.6
1.0
72.5
1.5
69.8 + 1.4
73.9 + 1.0
75.5 1.3
350
73.8
+ 1.1
72.6 + 1.4
70.4 3.7
73.2
= 1.2
73.1
= 1.5
70.8
+ 0.8
74.7
4
0.8
77.1 1.4
Web to Amazon
Random
Confidence
Entropy
A-medoids
k-centers
WAAL
Wass.
EOC
Wass.
BOC
50
50.4 + 4.0
19.2 +: 6.7
23.4 6.7
64.7 2 2.1
61.9 2.1
50.4 4 33
63.1 3.3
65.9 2.3
3.0
37.5
2.4
+
150
68.4
+ 2.6
50.6 3.2
6.5
70.1 1.4
09.6 2.0
65.5 - 1.3
71.9
+ 1.3
72.8 + 1.3
200
70.9
+ 2.0
5..4
5.3
7.7
71.1
39.5+200
73.8
+ 2.0
74.5 + 1.2
250
72.9 1.7
66.9 3.4
64.5
72.7
0.9
72.7
1.6
70.2 1.8
74.3
1.5
75.7
300
74.6
+ 1.6
69.3
+: 4.0
3.7
73.6
- 1.2
73.9
1.4
72.9 1.8
75.7
1.8
76.0
1.7
350
75.3
+ 1.8
73.1
+: 2.1
72.3 2.6
74.3 = 1.3
74.7
= 0.8
73.7
+ 188
76.4 188
77.0 1.4
Web to DSLR
B
Random
Confidence
Entropy
k-medoids
I-centers
WAAL
Wass.
ROC
Wass. BOC + P
10
31.3
+ 5.2
17.8 + 433
16.4
33.0 = 3.3
26.7
0.9
31.3 1.33-0 5.0
36.4 4.0
30
20
49.8
- 5.2
3.8
09.83.2
41.4 6.8
60.9 - 2.3
42.6
67.3 1.0
67.7 3.9
30
64.3
+ 3.8
5.2
43.1
48.3
4.3
96.8 + 1.2
60.1
6.8
88.4
+ 2.2
88.3 1.4
40
77.4
+ 2.2
58.8
7.1
55.4 8.3
54.5
1.9
99.7
+ 0.3
69.4 5.5
95.0 + 0.8
96.7 2.0
50
81.5
+ 2.7
71.0
5.1
67.0
8.6
61.8
3.3
99.6
0.5
86.0 + 6.2
96.9
0.6
99.0 1.7
85.4
4.7
81.4 2.5
75.5
06.2
3.4
97.7
99.0
70
90.0
+ 3.4
91.5 4: 2.6
85,9 4.9
72.6 = 3.8
100 =
99.9 + 0.3
97.6 4 2.0
100 :
Amazon to DSLR
B
Random
Confidence
Entropy
k-medoids
k-centers
WAAL
Wass.
FOC
Wass. BOC +
10
28.6
+ 5.5
17.5 + 4.9
16.5 = 0.9
30.7 = 4.5
29.4 + 4.0
29.4 +: 5.3
29.1 3.7
31.1 5.9
20
45.4
+ 4.8
8.2
28.2
39.7 2.6
54.8
42.2 6.1
52.6
5.1
56.8 4.9
57.6
+ 2.5
48.0 7.2
44.8
48.2
82.0
56.5
3.2
76.2
40
69.8
+ 2.5
4.98
5..4
5.2
87.4 3.2
70.0 3.6
81.6
1.8
81.9 - 2,8
50
71.7
+ 5.1
70.6
+: 4.0
6.8 65.0
58.5 - 8.0
89.8
1.7
78.6
13.6::31
87.1
3.2
87.0
3.2
+: 4.0
76.6
+ 3.9
72.6
62.0
7.1
2.7
88.4
1.7
80
70
80.8
3.1
83.4
+ 2.7
77.7
6.0
64.8
7.2
92.2
1.4
87.3 + 2.7
90.3
1.3
90.3
3.0
DSLR to Web
B
Random
Confidence
Entropy
I-medoids
k-centers
WAAL
Wass.
EOC
Wass. BOC
10
28.5
+ 2.1
23.3 +: 3.5
22.2 3.2
32.8 = 2.5
30.2 2.8
28.6 2.0
32.4 + 2.6
35.9 + 2.4
20
46.2
+ 2.3
32.7 5.8
30.2 = 4.0
47.8 = 8.0
58.1 + 2.9
45.6 6.7
62. 1
5.4
62.7
5.7
35.8
5.5
52.6
86.6
40
73.2
+ 6.6
51.5 +
44.9 5.3
57.0 5.7
97.2
0.8
71.1 +
93.9 + 2.4
95.6 1.0
50
78.1
+ 5.1
$1.3335
53.7 4.2
59.6 = 7.0
98.0 - 0.9
80.2 3.4
96.6
1.2
96.4 1.5
82.3
- 2.0
69.5 6.8
62517.1
61.6
6.8
$7.7
97.8
0.5
97.5
70
83.5
- 1.5
75.5 6.7
71.8550 5.6
65.8 = 6.7
93.8
0..2332
99.2
97.8
Amazon
Web k-centers
B
Random
Confidence
Entropy
k-medoids
WAAL
Wass.
EOC
Wass. BOC
10
26.4
3.5
14.9 3.2
17.5
31.5 4.0
25.0 + 2.8
26.6
3.1
32.2 2.7
31.7 2.7
20
41.7 + 1.3
31.0 43.2
28.0 6.5
42.2 = 1.8
53.6 3.9
35.6 3.1
57.6 5.7
57.9 1 4.3
30
3.5
4.3
48.1
82.7 2.8
49.8 4.0
74.1
3.9
78.6
40
66.5
5.7
7.4
8.
53.1 1 5.8
87.7 + 3.6
59.7 4.7
80.2
4.2
82.6
50
71.7
3.8
5.77
6.37
58.0 7.0
89.
+ 3.1
74.3 4.0
81.6
16
84.5 3.4
60
75.2
+ 1.2
3.5
68.9
61.8
8.0
89.7
2.6
+
86.9
2.0
84.5
70
76.5
1.0
81.1
77.8 4.2
63.2 5.8
85.9 4.5
4: 2.3
86.4
tests. More specifically, we outperform k-centers on five out of the seven budgets for both DSLR to Amazon and Web Amazon, which is the hardest domain to learn, especially since the source data sets are much smaller than the target. Note that the remaining source-target combinations are easy problems that nominally yield high accuracies with unsupervised domain adaptation, meaning that
24

---

Published as a conference paper at ICLR 2022
Table 11: Head-to-head comparison of Wass. EOC + versus k-centers on domain adaptation with statistical f-tests to compare. The best model for each budget range is bolded and underlined. Tests where Wass. EOC P statistically outperforms k-centers are marked in green and tests where k-centers statistically outperforms Wass. + EOC + P are marked in red.
DSLR to Amazon
B
50
100
150
200
250
300
350
l-centers
59.7 3.0
65.1 1. 2.2
68.0 1
70.3 1.5
71.4 1 74.7 7 1.1
72.5 1
73.1 1 1.5
Wass. BOC+ + P
60.0
2.8
67.3 + 2.8
71.3 + 1.1
73.8 0.9
75.5 - 1.3
77.1 + 1.4
p-value < 0.05
Web to Amazon
50
100
150
200
250
300
350
k-centers
61.9 2.1
67.7 2.9
69.6 1
71.1-22
72.7 1.6
73.9 4 144
74.7 1 0.8
Wass. + EOC+ + P
65.9 2.3
69.9 1.7
72.8 1.3
74.5
75.7
77.0 76.0+1.7
p-value < 0.05
Web to DSLR
B
10
20
30
40
50
60
70
k-centers
26.7
60.9 +
96.8
1.2
9
99.6 0.5
100 +
100 +
Wass. EOC+ + P
30.4 = 1.5
67.7
3.9
88.3 + 1.4
96.7
2.0
99.0 1.7
99.0 = 1.7
100 +
p-value < 0.05
Amazon to DSLR
10
20
30
40
50
60
70
k-centers
29.4 + 4.0
54.8 + 4.3
82.0 + 4.1
87.4 3.2
89.8 1.7
90.6 - 2.7
92.2 + 1.4
Wass. + EOC+1 P
31.1 5.9
56.8
4.9
76.2 4.1
81.9
87.0
89.1 3.8
90.3
p-value < 0.05
DSLR to Web
B
10
20
30
40
50
60
70
k-centers
30.2 2
58.1
93.6 1.3
+ 0.8
98.0
98.2 166
98.6 1.1
Wass. EOC P
35.9
2.4
62.7 1.3
86.6 2.8 X
95.6 = 1.0
96.4 1.5
97.3 =
97.8 = 1.1
p-value- < 0.05
X
Amazon to Web
10
20
30
40
50
60
70
k-centers
25.0 + 2.8
53.6 + 3.9
82.7 2.8
87.7
3.1
89.7 79.7:22 2.6
3.1
Wass. + EOC+ + P
31.7= 2.7
57.9 4.3
78.6
78.6:6.. 6.1
82.6
3.2
3.4
244
87.4 2.5
p-value < 0.05
the marginal value of labeling points is much less for these tasks. For Web to DSLR and DSLR to Web, we statistically better at smaller budgets whereas k-centers is better for medium budgets.
E.5 CLASSICAL ACTIVE LEARNING
Here, we ablate the effect of feature generation by removing unsupervised pre-training and con- sidering classical batch-mode active learning (Sener & Savarese [017]] Sinha al.] 2019 Shui et al. 2020). Our baseline, WAAL, is an alternative active learning strategy that also minimizes the Wasserstein distance but rather by using an adversarial model to estimate the dual distance (Shui et al. 2020). WAAL is designed specifically for classical active learning where self-supervised features are not available.
this experiment, we follow their exact setup to demonstrate (i) that optimization is effective over greedy approach such as WAAL even in even the high-budget setting, and (ii) that optimization still effective when given weaker features via supervised learning as opposed to powerful self-superviser features.
Methods. We initialize our labeled data set with a small randomly selected subset. Then in each round, we first train the classifier using supervised learning the currently labeled pool and then use the final layer of the trained classifier to obtain feature embeddings. These embeddings are then used solve code of /Shi et al. (2020) to implement WAAL without changing any their parameters. We use their recommended model, training, and algorithm hyper-parameter settings.
optimization problem and select the next B points to label. We use the available
25

---

Published as a conference paper at ICLR 2022
Table 12:
Runtime in minutes:seconds for all of the baselines CIFAR-10. Times averaged
over five runs.
B
Random
Confidence
Entropy
k-medoids
k-centers
WAAL
0.03
0.03
0.03
7: 56.81
0.09
0.03
20
0.03
0.02
0.01
15: 22.28
0.15
11.43
40
0,02
0.01
0.01
25.69
1.33
12.18
60
0,04
0.02
0.02
2: 18.51
0.34
11.93
80
0,03
0.02
0.02
18.37
11.97
100
0.03
0.02
0.02
2:21.84
0.54
12.25
120
0.03
0.02
0.01
2:17.18
1.31
11.69
140
0.03
0.02
0.02
2:20.91
1.19
11.73
160
0.03
0.02
0.01
2:18.31
3.50
11.59
180
0.03
0.03
0.02
13.3.
0.74
11.51
In order adapt optimization problem the high-budget setting, make modification to our algorithm. Rather than solving for the entire labeling budget in one problem, we instead optimization problems each for half
randomly partition the data into two subsets and solve of the labeling budget respectively. For example, if we have a previously labeled set of 2, 000 images, an unlabeled pool of 48, 000, and budget of B 1, 000 we randomly split the problem into two sets of 1, 0000 labeled images, 24, 000 unlabeled images, and B = 500 budgets. This ensures that our optimization problem remains manageable in computational size. Furthermore, we implement Wass. + EOC+ P. set (B+ _--)= (0.6, 0.9), and total time limit of T 4 hours for each problem.
Results. From Table 4 for both data sets and all budgets, our approach outperforms the baseline by up to 3%. Recall that WAAL (i) learns a feature embedding that estimates the Wasserstein dis- tance via dual regularization and (ii) uses a greedy uncertainty strategy to select points that minimize the Wasserstein distance of selected points. In contrast, an integer program that to select points that minimize the Wasserstein distance. Our approach can provably obtain optimal solutions. Our performance highlights the value of optimization via im- provement in classification accuracy. Furthermore, we conclude that our optimization problem can be tractably solved in higher budget settings.
standard embeddings and formulate
E.6 WALL-CLLOCK ANALYSIS
Table 12 presents the average runtime for each active learning baseline. The runtimes do not include the first cost of generating features, which occurs for each method except for Random. Nearly every baseline requires only few seconds to make queries. The k-medoids baseline usually requires several minutes due to the cost of computing the distance matrices between points. contrast, we encourage running method for at least 20 minutes and up to several hours.
potential concern for use of our method in active learning is the long run time (i.e., requiring several hours) in contrast to baselines that typically require the order of seconds. In general, combinatorial optimization frameworks for deep learning usually scale poorly with data set size. For example, the nominal MILP does not even fit into memory for large data sets such CIFAR-10 and SVHN. GBD simplifies our problem by permitting a variable runtime and easier computational burdern, while still preserving global optimality. Ultimately, we emphasize that the time cost of selection can be less than model training time and in some applications, less than human labeling time itself (Rajchl al., 2016). Furthermore, the selection is entirely automated and offline from training. Thus, we suggest that it is more practical to ensure the best possible selection regardless of runtime order minimize the real human labor of labeling.
E.7 ADDITIONAL ABLATIONS
Customizing the Wasserstein distance. 6lotss accuracy CIFAR-10 using Wass. EOC with Cosine versus Euclidean distance. The Euclidean alternative outperforms Cosine distance only when B = 10 whereas Cosine distance outperforms the alternative for higher budgets. Using Cosine distance yields better downstream accuracy here because the representation learning step, SimCLR, also maximizes Cosine distance between different images.
26

---

Published as a conference paper at ICLR 2022
CIFAR-10 10: Effect Cos. Dist.
Accuracy (%)
70
60
Euclidean distance
Cosine distance
50
100
125
Number of Labeled Images
Figure 6: Ablation using Cosine distance as the base metric in the Wasserstein distance problem for CIFAR-10.
Wass. EOC
locenters
k-medoids
Random
Wass. + EOC
k-centers
k-medaids
Random
Wass. EOC
k-centers
k-medoids
Random
Figure 7: t-SNE visualizations of the latent space obtained from pre-training. Images selected by each strategy are marked. The first row shows STL-10 at B 10, the second row shows CIFAR-10 at B 20, and the third row shows SVHN at B 20.
Qualitative Analysis. Figure shows t-SNE visualizations of the latent space in the first and second round for S0I.100, CIFAR-10, and SVHN, respectively. In each case, our selection strategy provides a better coverage the entire latent space by selecting points closer to cluster centers and covering most clusters. All of the baselines leave large holes in certain regions of the latent space.
Figures S and 10 show a sample set labeled images by the final round for each data set. In each case, our model covers every class with labeled image within the first two rounds. For example with STL-10, the first round labels two images of dogs instead round corrects for this issue by identifying and labeling two cats. We observe the same trend with airplanes and cars for CIFAR-10. Furthermore, we select images from nearly every class in each round.
cat, and so the second
27

---

Published as a conference paper at ICLR 2022
Figure 8: Images selected for labeling on STL-10 with different methods: Wass. + EOC (top left), k-centers (top right), k-medoids (bottom left), Random (bottom right). The first two rows were selected in the first two rounds and every two rows after were selected in the subsequent rounds.
28

---

Published as a conference paper at ICLR 2022
Figure 9: Images selected for labeling on CIFAR-10 with different methods: Wass. + EOC (top left), k-centers (top right), k-medoids (bottom left), Random (bottom right). The first two rows were selected in the first two rounds and every two rows after were selected in the subsequent rounds.
29

---

Published as a conference paper at ICLR 2022
9
103 31
Y
2:
1 27
34
9
2
1(33
5
653
507
2
1
48
5
5
5
3
6
4
46
5
3
5O
SYAA
38788
18
6
0
33
9
10
K
A
26
6
16
2.849
12
2
9
0
5
9
2
4
2
2
5
06
55
9
3
33
56
15
6
9
16
2225
5
44
30
3
104
3
985
229
12
48
3
2
43
99
997
4
81
93
505
1578
160
58
802
12
1068
Figure 10: Images selected for labeling on SVHN with different methods: Wass. EOC (top left), k-centers (top right), k-medoids (bottom left), Random (bottom right). The first two rows were selected in the first two rounds and every two rows after were selected in the subsequent rounds.
Figure g compares our method versus k-centers, k-medoids, and Random for STL-10. Compared the baselines, we identify and label examples from more classes in the first rounds. While we capture labeled examples of all classes by the second round, the k-centees baseline does not label dog until the third round. Note that the first round, the Random baseline includes three images of dogs, meaning that this baseline at small budgets cannot accurately select diverse set of points. In particular the first rounds, our approach selects unobstructed images that capture the silhouette of each class. For example in the first round we label unobostructed full examples of horse, bird, dog, car, deer, and airplane, whereas the k-centers baseline includes unobstructed bird, deer, airplane, and horse, the k-medoids baseline includes only unobstructed dog and car, and the Random baseline includes an unobstructed ship, dog, and truck. Finally, the pictures selected by all three non-rande non-random strategies appear brighter and sharper average than the Random baseline.
30

---

Published as a conference paper at ICLR 2022
Figure compares method versus the three baselines for CIFAR-10. The samples here display similar trends to the STL-10 example: (i) we more quickly label a diverse set of classes, (ii) our approach identifies unobstructed, clear images in the first rounds, and (ii) the non-random alterna- tives select brighter images more often. Specifically, we cover all classes within the second round; in contrast, the k-medoids baseline requires three rounds first round, we obtain unobstructed images of dog. horse, deer, frog, truck, and airplane, while the k-centers baseline obtains unobstructed airplane, bird, truck, and horse, and the k-medoids baseline obtains an unobstructed frog, horse, truck.
all classes. Furthermore in the
Finally, Figure I0 compares our method versus the three baselines for SVHN. Here in the first round, our model more often selects different classes (i.e., 0, 2, 3, 4. 5, 7, 9) versus the baselines. Furthermore, in the early rounds, our images cover a variety different backgrounds including blue, red, and yellow.
31


Reviews:
[{"review_id": "wj4ybFohKZO", "reviewer": "Reviewer_HRFS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to follow. The authors provide an integer programming based approach for representation-based active learning, which shows empirical advantages over existing ones. I summarize my questions as follows.\n\n1. In section 3.2, the authors compare the size of the original optimization problem in Eq (4) and the relaxed one. In the relaxed problem, however, one needs to compute the Wasserstein distance at each iteration. What is the computational complexity of computing the mentioned Wasserstein distance? It would be great to include the explicit complexity, rather than just saying that ``efficient algorithms exist''.\n2. The author mentioned that the proposed method usually takes longer to make selections. I wonder how well the proposed method performs when it is given the same running time as other baselines, e.g., 3 minutes for both k-medoids and the proposed method?\n", "summary_of_the_paper": "This paper studies active learning from a mixed integer programming perspective. The active learning strategy is representation-based, and aims at selecting a core set that minimizes the Wasserstein distance. Various tricks, e.g., enhanced optimality cuts and pruning, from the integer programming literature are used to accelerate the algorithm. Empirical results show advantages of the proposed algorithm over existing ones.", "summary_of_the_review": "I think overall the approach makes sense, but I didn't find significantly novel contributions, either theoretically or empirically (maybe the authors could point out their novel contributions). As a result, I'll vote for a weak acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aN5iNWVi6hW", "reviewer": "Reviewer_vpVq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n-- Tackles active learning from a slightly different approach.\n-- Wasserstein distance well justified and bounds of the integer optimisation problems are well specified (proof not checked carefully however)\n-- Reasonable improvements over previous approaches: \n-- Well written paper: clear, algorithms and pseudo-code provided for ease of understanding and reproducibility.\n-- Thorough evaluation in low data regime against other SOTA active learning methods, in a number of scenarios (with SSL, classical active learning setting and domain adaptation).\n-- Time and complexity analysis provided\n\nWeaknesses/Potential Areas of Improvement\n-- Stated that there is improvement for high budget settings, but no evidence is provided in the text of that?\n-- In fact, it seems like a trend for a drop-off in performance in terms of accuracy  as budget increases; would be nice to see that even it does occur.\n-- There is limited analysis of scaling to larger unlabelled datasets or datasets with more classes. Skeptical that performance would be good, or that the method would scale well. Although, again training time is often cheaper than labelling so this is not necessarily a problem, but some experiment here would be useful.\n\nOther questions:\n-- Were the features used for greedy k-centers the same as the features used in your approach? Or did you continue to use the VGG16 features that was used in Sener and Savarese?", "summary_of_the_paper": "The paper frames active learning as an integer optimization problem, that minimises the distance Wasserstein distance between unlabelled pool of data. This is done in a feature space (in this case trained using self-supervised methods all the data). The method outperforms existing active learning methods for very small labelling budgets, with theoretical guarantees of integer optimisation problem (although not the performance in terms of model accuracy itself).", "summary_of_the_review": "Well written and polished paper with novel angle on the active learning problem, with some theoretical guarantees and good experimental performance in low budget scenarios. Would like see some additional results, but this a good paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WSv28AUu6CT", "reviewer": "Reviewer_9PdP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strong Points**\n\n- The paper discusses why Wasserstein distance is minimized (Theorem 1).\n- The experiments show the effectiveness of the proposed method in downstream task (active learning).\n- Presentation is clear.\n\n**Weak Points**\n\n- [Effect of the embedding method is not investigated] SimCLR is used for obtaining the encoding but I am curious what happens if other embedding methods are used. Intuitively, the embedding is very important because the proposed method assumes that nearby points in the embedding space have the same label. In the second paragraph of Section 5, the authors say \"our approach is also effective without self-supervised features\"; what is the meaning of this sentence?\n- [Scalability] Scalability of the proposed method seems to be low. The experiments include relatively small datasets. Does the proposed method scale even for datasets including millions of data points or larger budget values? For example, Table includes larger B's results (from 1000 to 6000); how large is the computation cost? This concern is mainly from real application scenarios; ML projects usually have budget to label more than 1000 data points (and much larger unlabeled data pool for which we need to compute Wasserstein distance).\n\n**Questions**\n\n- The inequality in pp.2 seems to be equal. In what sense do you argue that the RHS upper-bounds the generalization error?\n- How do we solve W-RMP? Do we use ILP solver?\n- This paper deals with the batch mode active learning. Is it possible to extend the proposed method to the classical sequential active learning?", "summary_of_the_paper": "This paper proposes a (batch mode) active learning method that chooses a subset of data points to be labeled through approximating the whole dataset in terms of Wasserstein distance, which is an upper-bound of the generalization error. The selection is formulated as a large-scale mixed integer programming, and the authors propose to solve it by the GBD. For acceleration, some additional constraints are proposed. Experimental results show that the proposed method is better (or competitive) than baseline methods like k-center, k-medoids, and WAAL.", "summary_of_the_review": "This paper is well-written and motivated, with a theoretical guarantee.\nBefore seeing the other reviews, I am positive to accept the paper although including some concerns (e.g., scalability).\nPlease answer and clarify my concerns described above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Us6CoVStH8p", "reviewer": "Reviewer_3bUG", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n\nThe paper is well written. It describes the problem in detail. I believe using Wasserstein distance to bound the core set loss is a unique and interesting way of dealing with the active learning problem. The approaches are also backed by strong empirical analysis. I find this a very strong paper. I did not get to check all the proofs but I have checked some of them and they seem correct. \n\nWeaknesses\n\nI dont find any weaknesses of the paper. This seems very relavant work and a strong accept in my view.", "summary_of_the_paper": "This work tackles the problem of active learning. In every iteration the subset of the unlabeled data pool that needs to be labeled is selected by posing it as an Integer Programming (IP) problem that minimizes the discrete Wasserstein distance. Generalized Benders Decomposition algorithm is used to solve this IP through relaxations. It is shown to converge and also some acceleration techniques are provided. All the above are supported through extensive empirical analysis.", "summary_of_the_review": "Overall a strong accept for tackling an important problem.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is an interesting submission, which was overall well received by the reviewers. I would recommend the authors to discuss further the vast modern litterature on efficient computation of Wasserstein distances and their minimization (see, e.g. Peyré and Cuturi 2019, and references therein)
Decision: Accept (Poster)