RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning
Authors: Krishnateja Killamsetty
Xujiang Zhao
Feng Chen
Rishabh K Iyer
Venue: NeurIPS 2021 Poster (2021)
Keywords: Efficient Semi Supervised Learning
Semi Supervised Learning
Data Efficient Learning
Robust Learning
Coresets

Abstract: Semi-supervised learning (SSL) algorithms have had great success in recent years in limited labeled data regimes. However, the current state-of-the-art SSL algorithms are computationally expensive and entail significant compute time and energy requirements. This can prove to be a huge limitation for many smaller companies and academic groups. Our main insight is that training on a subset of unlabeled data instead of entire unlabeled data enables the current SSL algorithms to converge faster, significantly reducing computational costs. In this work, we propose RETRIEVE, a coreset selection framework for efficient and robust semi-supervised learning. RETRIEVE selects the coreset by solving a mixed discrete-continuous bi-level optimization problem such that the selected coreset minimizes the labeled set loss. We use a one-step gradient approximation and show that the discrete optimization problem is approximately submodular, enabling simple greedy algorithms to obtain the coreset. We empirically demonstrate on several real-world datasets that existing SSL algorithms like VAT, Mean-Teacher, FixMatch, when used with RETRIEVE, achieve a) faster training times,  b) better performance when unlabeled data consists of Out-of-Distribution (OOD) data and imbalance. More specifically, we show that with minimal accuracy degradation, RETRIEVE achieves a speedup of around $3\times$ in the traditional SSL setting and achieves a speedup of $5\times$ compared to state-of-the-art (SOTA) robust SSL algorithms in the case of imbalance and OOD data. RETRIEVE is available as a part of the CORDS toolkit: https://github.com/decile-team/cords.

RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning
Krishnateja Killamsetty
Xujiang Zhao Feng Chen Department of Computer Science The University of Texas at Dallas Richardson, Texas, USA
Rishabh Iyer
[krishnateja. killamsetty x xujiang-e.. zhao, feng. chen,rishabl, htw.eeeaaaba.errardaaaaaaaaaaa edu
Abstract
Semi- superviie learning (SSL) algorithms have had great success in recent years in limited labeled data regimes. However, the current state-of-the tht-hhh-tttt SSL algorithms are computationally expensive and entail significant compute time and energy requirements. This can prove to be huge limitation for many smaller companies and academic groups. Our main insight is that training data instead of entire unlabeled data enables the current SSL. algorithms to con- verge faster, significantly reducing computational costs. In this work, we propose RETRIEVE coreset selection framework for efficient and robust semi-supervised learning. RETRIEVE selects the coreset by solving mixed discrete-continnuu bi-level optimization problem such that the selected coreset minimizes the labeled set loss. We use one-step gradient approximation and show that the discrete optimization problem is approximately submodular, enabling simple greedy algo- rithms to obtain the coreset. We empirically demonstrate several real-world datasets that existing SSI. algorithms like VAT, Mean-Teacher, FixMatch, when used with RETRIEVE, achieve faster training times, b) better performance when unlabeled data consists of specifically, we show that with minimal accuracy degradation, RETRIEVE achieves a speedup of around 3x in the traditional SSL setting and achieves a speedup of 5x compared state-of-the-art (SOTA) robust SSL algorithms in the case of imbalance and OOD data. RETRIEVE available as a part of the CORDS toolkit: https://githut wwt.ccc..ccccccc team Soeam/co cords
subset of unlabeled
(OOD) data and imbalance. More
Introduction
Deep learning algorithms have had great success over the past few years, often achieving human superhuman performance in various tasks like computer vision [10], speech recognition [18), natural language processing (5), and video games [45). One of the significant factors attributing to the recent success of deep learning is the availability of large amounts of labeled data
(55). However, creating large labeled datasets is often time-consuming and expensive in terms of costs. Moreover, some domains like medical imaging require domain expert for labeling, making it nearly impossible to create large labeled set. In order to reduce the dependency semi-sun suni-iseereieee learning (SSL) algorithms ? were proposed to train models using large amounts of unlabeled data along with the available labeled data. Recent works semi-supe semi-supervised learning algorithms can achieve similar performance to standard supervised learning using significantly fewer labeled data instances.
the availability of labeled data,
42 56
53) show that
Reseet EfficienT and Robust sem1 ceml-supFrVisee |Farning
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, the current SOTA SSL al- gorithms are compute-intensive with large training times. For example, from our personal experience, train- ing WideResNet model [60] on CIFARIO [27] dataset with 4000 la- bels using the SOTA Fix.Maac al-
Labeled Set
Labeled Set
Labeled Set
In Distribution
000
Unlabeled Set
Unlabeled Set
Uniabeled Set
gorithm [53] for 500000 iterations single
(a) Traditional SSL
(b) SSL with OODs
(c) Imbulanced SSL
takes around four days RTX2080Ti GPU. This also implies increased energy consumption and an associated carbon footprint [54]. Fur- thermore, it is common tune these SSL. algorithms over a large set of apper-parameters, which means that the training needs to be done hundreds and sometimes thousands of times. For example, 44 performed hyperparameter tuning by running 1000 trails of Gaussian Process-bass based Blackbox optimization [16] for each SSL algorithm (which for 500000 iterations). This process implies significantly higher experimental turnaround times, energy consumption, and CO2 emissions. Furthermore, this is not something that can be done most universities and smaller companies. The first problem we try address in this work is: Can we efficiently train semi-super ceni-supervised learning model on coresets of unlabeled data to achieve faster convergence and reduction in training time?
Figure 1: )Unlabeled with the distribution the labeled set, (b) Unlabeled set containing OOD instances, (c) Unlabeled where the class distribution is imbalanced
Despite demonstrating encouraging results on standard and clean datasets, current SSL algorithms perform poorly when OOD data class imbalance is present in the unlabeled set 44 g This performance degradation can be attributed to the fact that the current SSL algorithms assume that both the labeled and unlabeled set are sampled from the same distribution. A visualization of OOD data and class imbalance in the unlabeled set is shown in Figure | Several recent works (59 17 proposed to mitigate the effect of OOD in unlabeled data, turn improving the performance of SSL algorithms. However, the current SOTA robust SSL method [17] is 3X slower than the standard SSL algorithms. further increasing the training times, energy costs, and CO2 emissions. The second problem we try to address in this work is: In the case where OOD data or class imbalance exists in the unlabeled set, can we robustly train an SSL model on coresets of unlabeled data achieve similar performance to existing robust SSL methods while being significantly faster?
Speed Degradation
Degeadation
5.12
5.22
5,21
5.11
5.12
1.37
4
0-
-0:40
ALUS
1.78
0..8
(2050
13650
13053)
(905)
(505)
(205))
13653
CHPÁRLLO (000-255))
(000 2013
CIFÁRIOO
CIFÁRLO (1md-109))
Essended
VAT
VAY
VAT
VAT
VAT
Traditional SSI.
(b) Robust SSL
Figure 2: Comparison of RETRIEVE with VAT, FixMatch, and MT on CIFAR-10 and SVHN: contrast the accuracy degradation with speedup compared to the base SSL or robust SSL (DS3L) approach. We observe speedups of 3x in standard SSL case with 0.7% accuracy drop and 2x speedup with accuracy drop. In the robust SSL case, observe 5x speedup compared DS3L 17 while outperforming it in terms of accuracy.
To this end, we propose RETRIEVE, coreset selection framework that enables faster convergence and robust training of SSL algorithms. RETRIEVE selects coreset of the unlabeled data resulting in minimum labeled set loss when trained upon in semi-supervised manner. Intuitively, RETRIEVE tries to achieve faster convergence by selecting data instances from the unlabeled set whose gradients are aligned with the labeled set gradients. Furthermore, RETRIEVE also achieves distribution matching by selecting coreset from the unlabeled set with similar gradients the labeled set.

---

1.1
Our Contributions
The contributions are our work can be summarized as follows:
We propose coreset selection algorithm RETRIEVE for efficient and robust remi-superrvieed learning. RETRIEVE poses the coreset selection as discrete-continuon bi-level optimization problem and solves it efficiently using an online approximation of single-step gradient updates. Essentially, RETRIEVE selects coreset of the unlabeled set, which, when trained using the combination of the labeled set and the specific unlabeled data coreset, minimizes the model loss on the labeled dataset. We also discuss several implementation tricks to speed up the coreset selection step significantly (c.f.. Section 3.3 Section 3.4
RETRIEVE Framework:
RETRIEVE in Traditional SSL: We empirically demonstrate the effectiveness of RETRIEVE in conjunction with several SOTA SSL algorithms like VAT, Mean-Teacher. and FixMatch. The speedups obtained by RETRIEVE are shown in Figure 2a Specifically, we see that RETRIEVE consistently achieves close to 3x speedup with accuracy degradation of around 0.7%. RETRIEVE also achieves more than 4.2 x speedup with a slightly higher accuracy degradation. Furthermore, when RETRIEVE is trained for more iterations, RETRIEVE can match the performance of VAT while having a 2x speedup (see VAT Extended bar plot in Figure 2a). RETRIEVE also consistently outperforms simple baselines like early stopping and random sampling.
We further demonstrate the utility of RETRIEVE for robust SSL in the presence of OOD data and imbalance in the unlabeled set. We observe that with the VAT SSL algorithm, RETRIEVE outperforms SOTA robust SSL method DS3L (17] (with VAT) while being around 5x faster. RETRIEVE also significantly outperforms just VAT and random sampling.
RETRIEVE in Robust SSL:
1.2 Related Work
Semi-supervised learning: Several papers have been proposed for semi-supervised learning over the past few years. Due to space constraints, we do not talk about generative [50] 48 26
19 30 3
and graph-based [62] 33 methods for SSL in this work. We instead focus on the main components of the existing SOTA SSL algorithms, viz., a) consistency regularization and b) entropy minimization.
The consistency regularization component forces the model to have consistent prediction given an unlabeled data point and its perturbed (or augmented) version. The Entropy cuttooy-minimization component forces the model instances to have low-entropy predictions unlabeled data instances ensure that the classes are well separated. One can achieve entropy minimization by directly adding the entropy loss component the unlabeled class prediction using methods like Pseudo-Labeling
enforce it implicitly. Mean-Tean Teacher (56) approach uses consistency regularization component that forces the predictions of the exponential moving average of the model to be the same the model prediction of the augmented unlabeled images. VAT 42 instead computes the perturbation of the unlabeled data point that changes the prediction distribution the most and enforces the model to have the same prediction on both unlabeled data instance and unlabeled data instance with computed perturbation as a form of consistency regularization. MixMatch [4] uses K standard image augmentations for consistency regularization and enforces entropy minimization by using a sharpening function on the average predicted distribution of K augmentations of unlabeled data instances. FixMatch [53] induces consistency regularization by forcing the model to have the same prediction on weakly augmented and strongly augmented image instance. Furthermore, FixMatch [53] also employs confidence thresholding to mask unlabeled data instances on which the model's prediction confidence below a threshold from being used in consistency loss.
Robust Semi-supervised learning: Several methods have been proposed to make the existing semi-supervised learning algorithms robust to label noise in labeled data and robust to OOD data in the unlabeled set. A popular approach [49 [52 to deal with label noises and class imbalance in su- pervised learning setting is by reweighing each data instance and jointly learning these weights along with the model parameters. Safe-SSL (DS3L) [77 is a recently proposed SOTA method for robust SSL learning. DS3L is similar the reweighting in the supervised case and adopts a reweighting approach to deal with OOD data in the unlabeled set. Safe-SSL uses a neural network to predict the weight parameters of unlabeled instances that result in maximum labeled set performance, making a bi-level optimization problem. In this regard, both RETRIEVE and Safe-SSL approoch solves bi-le optimization problem, except that RETRIEVE solves discrete optimization problem at the outer level, thereby enabling significant speedup compared to SSL algorithms and an even more considerable
3

---

1933 &
Sy.
Grendy Secaal
D
$4,80
93D
90D
SCD
800
900
92D
Runnic SSL, sigrttinion &
Ramning SEL algrrthm R-aaach
Rapeal tines
Repocts
Figure 3: Flowchart of RETRIEVE framework, where coreset selection performed every epochs and the model is trained on the selected coreset.
speedup compared to safe-SSL (which itself is 3x slower than SSL algorithms). In contrast to safe-SSL and other robust SSL approaches, RETRIEVE achieves both efficiency and robustness. Other approaches for robust SSL include UASD (9] uses an Uncertainty aware self-distillation with OOD filtering achieve robust performance and distributionally robust model to deal with OOD [8
Coreset and subset selection methods: Coresets [3 are small and informative weighted data subsets that approximate original data. Several works [57 39 24 23 have studied coresets for
efficient training of deep learning models in the supervised learning scenarios. CRAIG (39] selects representative coresets of the training data that closely estimates the full training gradient. Another approach, GLISTER 24 posed the coreset selection as optimizing the validation set loss for efficient learning focused generalization. Another approach, GRAD-MATCH [23] select subsets that approximately match the full training loss or validation loss gradient using orthogonal matching pursuit. Similarly, coreset selection methods [57 5 2 24 were also used for active learning scenario, where a subset of data instances from the unlabeled set is selected to be labeled. Finally, several recent works have used submodular functions for finding diverse and representative subsets for data subset selection 34 21
2 Preliminaries
Notation: Denote D = {x; y/ 3 to be the labeled set with n labeled data points, and U = {I, fj=1 be the unlabeled set with data points. Let 0 be the classifier model parameters, le be the labeled set loss function (such as cross-entropy loss) and l,, be the unlabeled set loss, e.g. consistency- regularization loss, entropy loss, etc.. Denote (Ds 0) = E. Nzs vi) and (1,, 0, m) =
SED
Em,lu(z;;00 where m E 1] the binary mask vector for unlabeled set. For notational jEU
convenience, we denote (0) I (Zz, Ya, f) and denote (0) = (T. 0).
Semi-supervised loss: Following the above notations, the loss function for many existing SSL algorithms can be written as Ls(D, 0) + ALu (M, 0, m.). where À the regularization coefficient for the unlabeled loss. For Mean Teacher [56] VAT 42, MixMatch (4] the mask vector is made up entirely of ones, whereas for FixMatch (53), m is seneddnnce-theshhllee binary vector, indicating whether include an unlabeled data instance or not. Usually, Ls is cross-entropy loss for classification experiments and squared loss for regression experiments. A detailed formulation of the loss function Ly used in different SSL algorithms given Appendix
Robust Semi-supervised loss: However, for robust semi suniisupervised loss, the mask vector m is R denoting the contribution of data instances in the unlabeled set. The weight vector w is unknown and needs to be learned. The weighted SSL loss is: Ls 0) XLa (14, 0, w), where À is the regularization coefficient for the unlabeled set loss.
replaced with weight vector
The state-of-the the robust SSL. method, Safe-SSI.
poses the learning problem as:
outer-level
w argmin (D argmin (Ls(D,0) 0) + ALU 0, w)))
inney level
In order to solve the problem at the inner level efficiently, Safe-SSL. 17 method uses a single-gradient step approximation to estimate the inner problem solution. The weight vector learning problem after
the one-step approximation is: w argmin (D, - V V (D, (V (,,0, w)
8

---

Safe-SSL also uses single-step gradient approximation to solve the outer level problem as well. As discussed before, the optimization problem of the Safe-SSL [T7] algorithm involves continuous optimization at both inner and outer levels, whereas for RETRIEVE, the outer level involves a discrete optimization problem which makes it significantly faster than Safe-SSI.
RETRIEVE framework
In RETRIEVE, the coreset selection and classifier model learning the selected coreset is performed in conjunction. As shown in the Figure 3 RETRIEVE trains the classifier model on the previously selected coreset for R epochs in semi-supervised manner, and every R epoch, selected, and the process is repeated until the classifier model reaches convergence, or the required number of epochs is reached. The vital feature of RETRIEVE is that the coresets selected are adapted with the training. Let O, be the classifier model parameters and the S, be the coreset at time step t. Since coreset selection done every epochs, we have S S(/R) or in other words, the subsets change only after R epochs. The SSL loss function on the selected coreset at iteration t is as follows:
coreset is
Ls(D,0.) 0.) Xe Σ mzjhu (xy, 0c)
JES.
where mgt the mask binary value associated with the j point based on model parameters and A is the unlabeled loss coefficient at iteration I. Note that objective function given in Equation (2)
dependent on the SSL. algorithm used RETRIEVE framework. gradient descent used for learning, the parameter update step from time step to t + 1 is as follows:
0.+1 = 0 a+ Vo LoVoss(D.A)))) - oz Σ m Volu 0z)
(3)
JES,
where a is the learning rate iteration t. The update step for mini-batch SGD is similar, just that it does the above on minibatches of the dataset.
3.1 Problem Formulation
The coreset selection problem of RETRIEVE timestep & is follows:
oater-level
S, argmin Ls D, argmin (Ls(D,0. + No > Emgdllas 0t))
scui|Sisk
JES
inner-leve -leeel
where & is the size of the coreset and my is the binary value associated with the jth instance based model parameters O,. l is fraction of the entire dataset (e.g. 20% 30%), and the goal is to select the best subset of the unlabeled set, which maximizes the labeled loss based. The outer level of the above optimization problem is discrete subset selection problem. However, solving the inner-optimization problem naively is computationally intractable, and, we need to make some approximations.
3.2 One-Step Gradient Approximation
To solve the inner optimization problem efficiently, RETRIEVE adopts a one-step gradient approxi- mation based optimization method similar 14 49 More specifically, RETRIEVE approximates the solution to the inner level problem by taking a single gradient step towards the descent direction of the loss function. The idea here to jointly optimize the model parameters and the subset as the learning proceeds. After this approximation, the coreset selection optimization problem becomes:
S
argmin Ls(D, 02 a, VoLs(D,0) - a.di - scu.SSKk
Vol 0z),
(5)
jES
However, after this approximation, the above optimization problem (Equation (5) is NP-hard.
5

---

Theorem 1 Optimization problem (Equation {5) NP NP hard, even if is a convex loss function. the labeled set loss function Ig is cross-entropy loss, then the optimization problem give in the Equation { can be converted into instance of cardinality constrained weakly submodular maximization.
The proof is given in Appendix B The given Theorem D holld as long as l2 is a cross-entropy loss irrespective of the form of Lu. Further, Theorem [ implies that the optimization problem given in
Equation (5) can be solved efficiently using greedy algorithms [77 with approximation guarantees.
RETRIEVE uses stochastic- grreicy algorithm [2, 38 to solve the optimization problem Equation (5) with an approximation guarantee of 1 1/ee - c in (m log(1/c)) iterations where m is the unlabeled set size and / is the weak submodularity coefficient (see Appendix B
And the set function used in
stochastic greedy algorithm is as follows:
= -LL -
aide Σ VoluVol jES
(6)
Notice that during each greedy iteration, we need to compute the set function value f S U e)) to find the maximal gain element e that can be added to the set This implies that the loss over the entire labeled set needs to be computed multiple times for each greedy iteration, making the entire greedy selection algorithm computationally expensive.
3.3 RETRIEVE Algorithm
To make the greedy selection algorithm efficient, we approximate the set function value f(e,, e)) with the first two terms of it's Taylor-series expansion Let, g = A: as VoLss 0.)
arde Σ mn VoluzT(()) The modified set function value with Taylor-series approximation is JES
as follows:
-Is((, V
(o m.t Volu( 0c)
(7)
where met is the binary mask value associated with element Note that the term met Vol by (Te 0,)
can be precomputed at the start of the greedy selection algorithm, and the term VgLg (D, 8 needs to be computed only once every greedy iteration, thereby reducing the computational complexity of the greedy algorithm.
Algorithm 1: RETRIEVE Algorithm
A detailed pseudo-code of the RETRIEVE algo- rithm is given in Algorithm [ RETRIEVE uses greedy selection algorithm for coreset selection, and the detailed pseudo-code of the greedy algo- rithm is given in A RETRIEVE can be easily implemented with popular deep learning frameworks [47 [1] that provide auto differenti- ation functionalities. In all our experiments, we set R 20, i.c., we update the coreset every 20 epochs.
Imput: Labeled Set: D. Unlabeled Set: 14, Reg. Coefficients:
[Ae [-=) 1-= 1. Learning rates: {or H
Input: Total of epochs: T, Epoch interval for subset selection:
R. Size of the coresct: k
Sct So C u [So] k:
Randomly initialize model parameters Bu coreect
repeat
if (1% == 0 (t 0) then
L S, Greeddy U4 6s, Xe, as.
=
Compute batches D, = (1), d E (1 (I... B)) from
D
3.4 Additional Implementation Details:
Compute batches Stt = ((ro): E (I... B)) from Mini-batch SGD
In this subsection, discuss additional imple- mentational and practical tricks to make RE- TRIEVE scalable and efficient.
Set 0zo = 02
for to do
Compute mask on S.c from current model parameters 1:(0-1)
Ozs 0ee 1) (DL.(Ds.0))
Last-layer gradients. Computing the gradi- ents over deep models is time-consuming due to an enormous number of parameters in the model. To address this issue, adopt a last-layer gra- by
acd: Σ m, Vola (. 1)) Se
Set P P.B
2 t+
until
T
dient approximation similar to 2 39 24 23
return 0r, ST
only considering the last classification layer gradients of the classifier model in RETRIEVE, By simply using the last-layer gradients, we achieve significant speedups in RETRIEVE.
Warm-starting data selection: We warm start the classifier model by training on the entire
unlabeled dataset for a few epochs similar to (23). Warm starting allows the classifier model to have

---

RANDOM
RETRIEVE
FULL
FULL-Earlystop
CRAIG
GradMatch
Dorratation
Acc. Degretation
Degradation
L.5
Arc. Deggmsation
5.0
2.5
0.5
0.00
Speed
Speed
Speed Up->
Speed
(a) CIPARIO-VAT
(b) SVHN-VAT'
(c) CHHARIO-Faaacch
(d) CIFARIO-MI
-90
90-
Avc. Degralatin
2.5
Apc. Degralatium
%
Toxt Aceumny
85
80
80
0.003
6
75
10 15 20 25 30
20
Spood Up
CO2 Emsisious
Hos)
(c) SVHN-MT
(f) FixMatch CO2 Emissions
(g) VAT Convergence
(h) MT Convergence
Figure 4: A comparison of RETRIEVE with baselines (RANDOM, CRAIG, FULL, and FULLEARLYSTOP in the traditional SSL setting. SpeedUp vs Accuracy Degradation, both compared to SSL for (a) VAT on CIFAR-10 10, (b) VAT on SVHN, (c) FixMatch on CIFAR-I0, 10. (d) MT on CIFAR- -10, and (e) MT on SVHN. We observe that RETRIEVE significantly outperforms existing baselines in terms of accuracy degradation and speedup tradeoff compared to SSL.. Plot (f) also compares the CO2 emissions among the different approaches on FixMatch, showing again that RETRIEVE achieves the hest energy-accuracy tradeoff. Plots (g) and (h) are the convergence results comparing accuracy with the time taken. Again, we see that RETRIEVE achieves much faster convergence than all baselines and full training.
good starting point to provide informative loss gradients used for coreset selection. More specifically, we train the classifier model on the entire unlabeled set for Tw = <f' epochs where l is coreset size, T is the total number of epochs, K is the fraction of warm start, and m is the size of the unlabeled set. To be fair, we consider all baselines in the standard SSL setting with the same warm start.
m
3.5 Epochs vs. Iterations
Algorithm 2: GreedySelection
Input: Labeled Set: Unlabeled Set: 14, Model Parameters:
Most of the existing SSL algorithms are trained using fixed number of iterations instead of epochs. However, for easier comprehension of the RETRIEVE algorithm, we use the epoch no- tation in our work. A single epoch here meant pass over random mini-batches of data points, such that the total number of data points encoun- tered is equal to the size of the coreset of the unlabeled data. For example, if the unlabeled set size is 50000 and the unlabeled batch size is 50, then a single epoch over 100%, 50%, and 30% subsets are equivalent to 1000, 500, and 300 iterations, respectively.
Or, Learning
Input: Regularization Coefficient: Aee Budget:
Initialize S, =
Set m = [64]
Compule mask
mn on current motel parameters 0,
for 14 do
Compute 0. m. Volu 0c)
for 1 k do Compute 6 8, ar Vol. - ardi > m, (s),( 3CB
Compute Le 83)
V ~ Sample [miog[1/e]] instances from 14 best gain = -o for e E V do Compute gain g(e)
a.d. VoLs 83)7 m. Val. 8c) if ((e) best gain then
Set e Set best gain ū(e)
Experiments
S. S, U 4 = \
Our experimental section aims verify the effi- ciency and effectiveness of RETRIEVE by evalu- ating RETRIEVE through three semi-supervised learning scenarios a) traditional SSL scenario with clean data, b) robust SSL with OOD, and c) robust SSL with class imbalance, to demonstrate the efficiency and the robustness of RETRIEVE. Furthermore, our work's experimental scenarios are very relevant in terms of research and real- world applications. We have implemented the RETRIEVE algorithmic framework using PyTorch [46). We repeat the same experiment for three runs with different initialization and report the mean test accuracies in our plots. A detailed table with both
return St
7

---

mean test accuracy and the standard deviations was given in Appendix H. For fair comparison, we use the same random seed in each trial for all methods. We explain implementation details. datasets, and baselines used in each scenario in the following subsections.
Baselines in each setting. In this section, we diseuss baselines that used in all the scenarios considered. We begin with the traditional SSL scenario. In this setting, we run RETRIEVE (and all baselines) with warm-start. We incorporate RETRIEVE with three representative SSL methods, including Mean Teacher (MT) [56], Virtual Adversarial Training (VAT) 22 and FixMatch [53]. The baselines considered are RANDOM (where we just randomly select subset of unlabeled data points of the same size as RETRIEVE), CRAIG [39 23) and FULL-EARLY
CRAIG [39 23 was
actually proposed in the supervised learning scenario. We adapt it to SSL by choosing representative subset of unlabeled points such that the gradients are similar to the unlabeled loss gradients. We run the per-batch variant of CRAIG proposed in (23, where we select subset of mini-batches instead of data instances for efficiency and scalability. Similarly, we use the per-batch version of GR TRADMATCH proposed in (33 adapted to SSL setting as another baseline. For more information on the formulation of CRAIG and GRADMATCH in the SSL case, see Appendix D B Again, we emphasize that RANDOM, CRAIG, and GRADMATCII are run with early stopping for the same duration as RETRIVVE. In FULL-EARLYSTOP baseline, we train the model on the entire unlabeled set for the time taken by RETRIEVE and report the test accuracy. In the traditional SSL scenario, we use warm variants of RETRIEVE, RANDOM, CRAIG for SSL training because warm variants are better in accuracy and efficiency compared to not performing warm start - see Appendix G for careful comparison of both. Robust SSL with OOD and Imbalance: In the robust learning scenario for both OOD and imbalance, we analyze the performance of RETRIEVE with the VAT [42 algorithm. Note that for the Robust SSL scenario, we do not warm start the model by training for a few iterations on the full unlabeled set because training on an entire unlabeled set(containing OOD or class imbalance) creates a biased model due to a distribution mismatch between labeled set and unlabeled set. We empirically compare not warm starting the model with warm starting in Appendix H In the robust SSL case, we compare RETRIVVE with two robust SSL algorithms DS3L [17 and L2RW [49]. DS3L (also called Safe-SSL) is a robust learning approach using a meta- weight network proposed specifically for robust SSL. We adapt L2RW(Learning to Reweight), originally proposed for robust supervised learning, to the SSL case and use it as a baseline. Similarly, we adapt the robust coreset selection method CRUST 40 originally proposed to tackle noisy labels scenario in supervised learning to SSL setting and use it as baseline in Robust SSL scenario.
Datasets, Model architecture and Experimental Sctup: We begin by providing details common across the three scenarios. We perform experiments on the following im-
1
Rel. Test Error
RETROVER
age classification datasets: CIFAR- 10 (2 (60000 in-
stances), SVHN (43) (99289 instances) and the follow- ing sentiment analysis datasets: IMDB (36 (10000 in- stances), and ELEC 20 I 246714 14 instances) datasets. We use a modified version of the ELEC dataset where the duplicate sentences are removed. For CIFAR-10, we use labeled set of 4000 instances with 400 instances from each class, an unlabeled set of 50000 instances, a test set of 10000 instances. For SVHN, we used a labeled set of 1000 instances with 100 instances from each class, an unlabeled set of 73257 instances, test set of 26032 instances. For IMDB and ELEC datasets, we use the labeled and unlabeled splits following the work [41). For CIFAR1O and SVHN datasets, we use the Wide-ResNeet-2822 [60] model that is commonly used in SSL for details). For IMDB and ELEC datasets, we model comprising of Word Embedding layer,
2
0
2.5
Speed Up-
Figure 5: Performance comparison of RETRIEVE vs Bayesian Coreset using VAT for 20% and 30% CIFARIO subsets
44 53 For MNIST, we use a variant of LeNet BD (see Appendix F
LSTM model, and two-layer MLP model following the architecture given in the work 41 Similar to the work 411,, we initialize the embedding matrix and LSTM model weights using pretrained recurrent language model using both the labeled and unlabeled data. For Image datasets, with RE- TRIEVE(and baselines like RANDOM, GRADMATCH and CRAIG),
use the Nesterov's accelerated SGD optimizer with learning rate of 0.03, weight decay of 5e-4, the momentum of 0.9, and a cosine annealing (35) learning rate scheduler for all the experiments. For the FULL and FULLEARLY we use the Adam optimizer (25) and follow the experimental setting from the SSL papers 53 42 56].
Chttpss//ai.stanffrrr edu/ amaas//datu/sentmmenn/ hhat://tiesoommson.commmaa wttpo////oooooooaaoaaaaaaaaaaa htta
8

---

For Text datasets, with RETRIEVE(and baselines like RANDOM, GRADMATCH and CRAIG), we set the hyperparameter values following the work [4T] Similarly, for the robust SSL baselines, we use the settings from the corresponding papers 17 For all our experiments using image datasets, we use a batch size of 50 for labeled and unlabeled sets. Next, we discuss the specific settings for the traditional SSL scenario. For CIFARIO, 10, we train the model for 500 epochs, and for SVHN, we train the model for 340 epochs on an unlabeled set. Note that we mention the epochs here because the number of iterations depends on the size of the unlabeled sets since that would determine the number of mini-batches. For a fair comparison, we train all algorithms for a fixed number of epochs. Next, we look at robust SSL for OOD. In this scenario, we consider the presence of OOD in the unlabeled set. We introduce OOD into CIFAR- 10 following [44), by adapting it to a 6-class dataset, with 400 labels per class (from the 6 animal classes) as ID and rest of the classes as OOD (ID classes are: "bird", "cat", "deer". "dog", "frog". "horse", and OOD data are from classes: "airline", "automobile", "ship", "truck"). Similarly, we adapt MNIST (32) to 6-class dataset, with classes 1-6 as ID) and classes 7-10 as OOD. We denote the OOD ratio= (Mood + Uia) where Uin is ID unlabeled set, Uood is OOD unlabeled set. For 1I,AR10, we use labeled set of 2400 instances and unlabeled set of 20000 instances, and for MNIST, we use labeled set of 60 instances and an unlabeled set of 30000 instances. Finally, for robust SSL for class imbalance, we consider imbalance both in the labeled set and unlabeled set. We introduce imbalance into the CIFAR- 10 dataset by considering classes 1-5 as imbalanced classes and a class imbalance ratio. The class imbalance ratio is defined as the ratio of instances from classes 1-5 and the number of instances from classes 6-.0. For CIFAR-10, we use a labeled set of 2400 and an unlabeled set of 20000 instances.
Traditional SSL Results: The results comparing the accuracy- efficiency tradeoff between the different subset selection approaches are shown in Figure 4. We compare the performance for different subset sizes of the unlabeled data: 10%, 20%. and 30% and three representative SSL algorithms VAT, Teacher, and FixMatch. For warm-start, we set kappa value to K 0.5 (i.e.. training for 50% epochs on the entire unlabeled set and 50% using coresets). Our experiments use a R value of 20 (i.e., coreset selection every 20 epochs). Sub-figures 4a 4b 4cb shows the plots of relative
RANDOM
RETRIEVE
FULL
FULL-Earlystp
CRAIG
GzulMalh
2
3
Speedd Up
(a) 30% IMDB-VAT
(b) 30% ELEC-VAT
Figure 6: A comparison of RETRIEVE with baselines (RANDOM, CRAIG, GRADMATCH, FULL, and FULLEARLYSTOP the tradi- tional SSL setting for text datasets. SpeedUp vs Accuracy Degrada- tion, both compared to SSL for (a) VAT on 30% IMDB, (b) VAT on 30% ELEC.
4e
vs speedup, both w.r.t full training (i.e., original SSL algorithm). Sub-figure 4f shows the plot of relative error vs CO2 emissions efficiency, both w.r.t full training. CO2 emissions were estimated based on the total compute time using the Machine Learning Impact calculator presented in 29 From the results, it is evident that RTTRIEVE achieved the best speedup vs. accuracy tradeoff and is environmentally friendly based on CO2 emissions compared to other baselines (including CRAIG and FULLEARLYSTOP), In particular, RETRIEVE achieves speedup gains of 2.7x and 4.4x with performance loss of 0.7% and 0.3% using VAT on CIFARIO and SVHN datasets. Further, RETRIEVE achieves speedup gains of 2.9x, 3.2x with a performance loss of 0.02% and 0.5% using Mean-Teacher on CIFAR 10 and SVHN datasets. Additionally, RETRIEVE achieves a speedup of 3.8x with a performance loss of 0.7% using FixMatch on the CIFARIO dataset. Sub-figures(6al 6b) shows the plots of relative error vs speedup both w.r.t full training (i.c., original SSL algorithm) on IMDB and ELEC datasets for 30% subset size. In particular, RETRIEVE achieves speedup gains of 2.68x and 2.5x with performance loss of 0.5% and 0.6% for 30% subset of IMDB and ELEC datasets. Figure 5 shows the results comparing the BAYESIANCORESER method (6], adapted to the SSL setting with RETRIEVE using the VAT algorithm for 20% and 30% CIFARIO subsets. The results show that RETRIEVE achieves better performance than the SSL extension of the BAVESIANCORESET selection method in terms of model performance and speedup. One possible explanation for it is that the BAYESIANCORESET approach was not developed for efficient learning but instead was developed to capture coresets that try to represent the logeliieldoood of the entire dataset that MCMC methods can further use. We would also like to point out that we used the original code implementation of BAYESIANCORESEET that is not meant for GPU usage in our

---

RETRIEVE
VAT
DSSL
L2RW
SUPERVISED
CRUST
80
Text Acmuato
77.5
Test Accuracy
95
Test Accuracy
75
Time Taken Ho)
70
65
75.0
90
60
30.2
0.25
0.50
0.75
0.25
0.50
0.75
0.1
0.3
0.5
17.3
0OD Ratin
0OD Ratio
Class Imbalance Ratio
(a) VAT CID
(h) VAT MNIST 0OD
- (c) VAT CIFARIO Imh
L (d) VAT CIFARIO Imh Timings
Figure 7: Subfigures (a) to (c) compare the performance of RETRIEVE with baselines (ineluding DS3L. and L2RW) for different OOD ratios (a.b) and imbalance ratios (c). We that RETRIEVE outperforms both baselines in most the cases. Furthermore, RETRIEVE achieves this while being close to faster than VAT (the SSL algorithm) and 5x faster than the robust SSL algorithms (DS3L and L2RW).
experiments. Hence the speedups of the BAYESIANCORESET approach can be further improved with efficient code implementation. Subfigure 4h shows that RETRIVVE achieves faster convergence compared to all other methods on CIFAR10 10 for 30% subset with the extended convergence of RETRIEVE on CIFARIO for 20% and 30% subsets using VAT, where the RETRIEVE is allowed to train for larger epochs to achieve comparable accuracy with Full training at the cost losing some efficiency. Note that the points marked by * in subfigure 4g denote the actual training endpoint, i.e. the usual number of epochs/iterations used to obtain points in subfigures (4a 4 We observe that RETRIEVE matches the performance of VAT while being close to 2x faster running times (and correspondingly energy efficiency). We repeat this experiment with MT
Subfigure 4g shows
4b
in the Appendix G Also, more detailed results with additional convergence plots and tradcoff curves
are in Appendix G
Robust SSL Results: We test the performance of RETRIEVE on CIFARIO and MNIST datasets with OOD in the unlabeled set and CIFARIO dataset with the class imbalance in both labeled and unlabeled sets. sub-figures 7a 7b shows the accuracy plots RETRIEVE for different OOD ratios of 25%, 50% and 75%. The results show that RETRIEVE with VAT outperforms all other baselines, including DS3L 17], a state-of-the-art robust SSL baseline the OOD scenario. Next, sub-figure shows the accuracy plots of RETRIEVE for different class imbalance ratios of 10%, 30% and 50% on CIFAR- 10 dataset. The results show that RETRIEVE with VAT outperforms all other baselines, including DS3L 11 (also run with VAT) in the class imbalance scenario as well. In particular, RETRIEVE outperforms other basclines by at least 1.5% on the CIFAR-10 with imbalance. Sub-figure 7 shows the time taken by different algorithms the CIFAR10 dataset with 50% class imbalance ratio. The results show that CRUST did not perform well terms of accuracy and speedups achieved compared to RETRIEVE. Except for MixUP, CRUST is similar CRAIG, which did not perform well compared to RETRIEVE in a traditional SSL setting. Furthermore, the performance gain due to MixUP for coreset selection in the SSL setting is minimal. The minimal gain can be attributed the fact that the hypothesized labels used for MixUP in the earlier stages of training are noisy. Furthermore, stated earlier, CRUST was developed to tackle noisy labels in supervised learning setting and is not developed to deal with OOD or Class Imbalance in general. The results show that RETRIEVE is more efficient compared the other baselines. In particular, RETRIEVE is 5x times faster compared to DS3L method. Other detailed results (tradcoff curves and convergence curves) are in Appendix H
5 Conclusion and Broader Impacts
We introduce RETRIEVE, a discrete-continuous bi-level optimization based coreset selection method for efficient and robust semi-supervised learning. We show connections with weak-submodularity which enables the coreset selection in RETRIEVE to be solved using scalable stochastic greedy algorithm. Empirically, we show that RETRIEVE very effective for SSL. In particular, it achieves 3x speedup on range of SSL approaches like VAT, MT, and FixMatch with around 0.7% accuracy loss and a 2x speedup with no accuracy loss. In the case of robust SSL with imbalance and OOD data, RETRIEVE outperforms existing SOTA methods while being 5x faster. We believe RETRIEVE has significant positive societal impact by making SSL algorithms (specifically robust SSL.) significantly faster and more energy-efficient, thereby reducing the CO2 emissions incurred during training.
10

---

6 Acknowledgments and Disclosure of Funding
We would like to thank NeurIPS area chairs and anonymous reviewers for their efforts in reviewing this paper and their constructive comments! RI and KK were funded by the National Science Foundation(NSF) under Grant Number 2106937, a startup grant from UT Dallas, and a Google and Adobe research award. FC and XZ were funded by National Science Foundation(NSF) under Grant Numbers 181 13666, 1750911, 1, and 2107449. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation, Google or Adobe.
References
[1] M. Abadi, Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, Ghemawat, G. Irving. M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow: system for large- scale machine learning. In 12th USENIX Symposium Operating Systems Design and Implementation (OSDI 16), pages 265-283, 2016.
[2] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In International Conference Learning Representations, 2020.
[3] M. Belkin and Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clus- tering. In Proceedings of the 14th International Conference Neural Information Processing Systems: Natural and Synthetic, NIPS'O1, page 585-591, Cambridge, MA, USA, 2001. MIT Press.
[4] D. Berthelot, N. Carlini, I. Goodfellow, N. Papernot, A. Oliver, and C. Raffel. Mixmatch: A holistic approach to semi-supervised learning, 2019.
[5] O. Bojar, R. Chatterjee, C. Federmann, M. Fishel, Y. Graham, B. Haddow, M. Huck, A. Jimeno- Yepes, P. Koehn, A. Martins, C. Monz, M. Negri, A. Névéol, M. L. Neves, M. Post, M. Turchi, and K. Verspoor, editors. Proceedings of the Fourth Conference on Machine Translation, WMT 2019, Florence, Italy, August 1-2, 2019 Volume 1; Research Papers. Association for Computational Linguistics, 2019.
[6] T. Campbell and T. Broderick. Bayesian coreset construction via greedy iterative geodesic ascent. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 698-706. PMLR, 10-15 Jul 2018
[7] O. Chapelle, B. Schlkopf, and A. Zien. Semi-Supervised Learning. The MIT Press, 1st edition, 2010.
[8] K. Chen, L. Yao, D. Zhang, X. Chang, G. Long, and S. Wang. Distributionally robust semi- supervised learning for people-centric sensing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3321-3328, 2019.
[9] Y. Chen, X. Zhu, W. Li, and S. Gong. Semi supirvupe learning under class distribution mismatch. Proceedings of the AAAI Conference on Artificial Intelligence, 34((4))3569-3577 Apr. 2020.
[10] D. Cireyan, U. Meier, and J. Schmidhuber. Multi-column deep neural networks for image classification, 2012.
[11] A. Coates and A. Ng. The importance of encoding versus training with sparse coding and vector quantization. In Proceedings of the 28th International Conference on Interna- tional Conference on Machine Learning, ICML. page 921-928- Madison, WI, USA, 2011. Omnipress.

---

[12] A. Das and D. Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Confer- ence on International Conference on Machine Learning, ICMI'11, page 1057-1064, Madison, WI, USA, 2011. Omnipress.
[13] D. Feldman. Core-sets: Updated survey. In Sampling Techniques for Supervised or Unsupervised Tasks, pages 23-44. Springer, 2020.
[14] C. Finn, P. Abbeel, and S. Levine. Model-agnostic meta-leaming for fast adaptation of deep networks. International Conference on Machine Learning, pages 1126-1135. PMLR, 2017.
[15] K. Gatmiry and M. Gomez-Rodriguez. On the network visibility problem. abs/181 2018.
CoRR,
[16] D. Golovin, B. Solnik, S. Moitra, G. Kochanski, J. E. Karro, and D. Sculley, editors. Google Vizier: A Service for Black-Box Optimization, 2017.
[17] L.-7.. Guo, Z.-Y. Zhang, Y. Jiang, Y.-F. Li, and Z.-H. Zhou. Safe deep semi-supervised learning for unseen-class unlabeled data. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3897-3906. PMLR, 13-18 Jul 2020.
[18] R. Hershey, J. Rennie, P. A. Olsen, and T. T. Kristjansson. Super-human multi-talker speech recognition: A graphical modeling approach. Comput. Speech Lang., 24(1):45-66, Jan. 2010.
[19] G. E. Hinton and R. R. Salakhutdinov. Using deep belief nets to learn covariance kernels for gaussian processes. Platt, D. Koller, Singer, and S. Roweis, editors, Advances Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008
[20] R. Johnson and Zhang. supervuper convolutional neural networks for text categorization via region embedding. Advances in neural information processing systems, 28:919-927, 2015.
[21] V. Kaushal, R. Iyer, S. Kothawade, R. Mahadev, K. Doctor, and G. Ramakrishnan. Learning from less data: A unified data subset selection and active learning framework for computer vision. 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 1289 1299. IEEE, 2019.
[22] R. Khanna, E. Elenberg, A. Dimakis, S. Negahban, and J. Ghosh. Scalable greedy feature selection via weak submodularity. In Artificial Intelligence and Statistics, pages 1560-1568. PMLR, 2017.
[23] K. Killamsetty, D. Sivasubramanian, B. Mirzasoleiman, G. Ramakrishnan, A. De, and R. Iyer. Grad-match: A gradient matching based data subset selection for efficient learning, 2021.
[24] K. Killamsetty, D. Sivasubramanian, G. Ramakrishnan, and R. Iyer. Glister: Generalization based data subset selection for efficient and robust learning, 2021.
[25] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
[26] D. Kingma, S. Mohamed, D. Jimenez Rezende, and M. Welling. Semi-supervised learning with deep generative models. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[27] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
[28] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[29] A. Lacoste, A. Luccioni, Schmidt, and Dandres. Quantifying the carbon emissions of machine learning, arXiv preprint arXiv: 2019.
12

---

[30] B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[31] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L.. D. Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 144):541-551, 1989.
[32] Y. LeCun and C. Cortes. MNIST handwritten digit database. 2010.
[33] B. Liu, Z. Wu, H. Hu, and S. Lin. Deep metric transfer for label propagation with limited annotated data, 2019.
[34] Y. Liu, R. Iyer, K. Kirchhoff, and J. Bilmes. SVitchboard II and ViS I: High-qualig limited- complexity corpora of conversational English speech. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
[35] I. Loshchilov and Hutter. SGDR: stochastic gradient descent with restarts. CoRR, abs/1608.03983. 2016.
[36] A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. N. and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 142-150, Portland, Oregon, USA, June 2011. Association for Computational Linguistics.
[37] M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization techniques, pages 234-243 Springer, 1978.
[38] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy. In Proceedings of the Twenty-Ning -inth AAAI Conference on Artificial Intelligence, AAAI'15, page 1812-1818. AAAI Press, 2015.
[39] B. Mirzasoleiman, J. Bilmes, and J. Leskovec. Coresets for data-efficient training of machine learning models, 2020.
[40] B. Mirzasoleiman, K. Cao, and J. Leskovee. Coresets for robust training of deep neural networks against noisy labels. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 11465-11477. Curran Associates, Inc., 2020.
[41] T. Miyato, A. M. Dai, and J. Goodfellow. Adversarial training methods for semi-supervised text classification. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[42] Miyato, ichi Maeda, M. Koyama, and S. Ishii. Virtual adversarial training: A regularization method for supervised and semi-supervised learning, 2018.
[43] Y. Netzer, T. Wang. A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[44] A. Oliver, A. Odena, C. Raffel, E. D. Cubuk, and I. J. Goodfellow. Realistic evaluation of deep semi-supervised learning algorithms, 2019.
[45] OpenAI, C. Berner, G. Brockman, B. Chan, V. Cheung, Dębiak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, R. Józefowicz, S. Gray, C. Olsson, J. Pachocki, M. Petrov, H. P. d. O. Pinto, J. Raiman, T. Salimans, Schlatter, J. Schneider, S. Sidor, I. Sutskever, J. Tang,
F. Wolski, and S. Zhang. Dota 2 with large scale deep reinforcement learning, 2019.
[46] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. De Z. Lin, Desmaison,
L. Antiga, and A. Lerer. Automatic differentiation in pytorch. 2017.
13

---

[47] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, Kopf, E. Yang. Z. DeVito, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, I.. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. H. Wallach, Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[48] Y. Pu, Z. Gan, R. Henao, X. Yuan, C. Li, A. Stevens, and L. Carin. Variational autoencoder for deep learning of images. labels and captions. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[49] M. Ren, W. Zeng. B. Yang, and R. Urtasun. Learning reweight examples for robust deep learning. In International Conference on Machine Learning, pages 4334-4343, PMLR, 2018,
[50] T. Salimans, I. Goodfellow. W. Zaremba, V. Cheung, A. Radford, X. Chen, and X. Chen. Improved techniques for training gans. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[51] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. In International Conference Learning Representations, 2018.
[52] J. Shu, Q. Xie, L. Yi, Q. Zhao, S. Zhou, Z. Xu, and D. Meng. Meta-weight-net: Learning explicit mapping for sample weighting. In Advances in Neural Information Processing Systems, 2019.
[53] K. Sohn, D. Berthelot, C.-L. Li, Z. Zhang, N. Carlini, E. D. Cubuk, A. Kurakin, H. Zhang, and C. Raffel. Fixmatch: Simplifying semi-supervised learning with consistency and confidence, 2020.
[54] E. Strubell, A. Ganesh, and A. McCallum. Energy and policy considerations for deep learning in nlp, 2019.
[55] C. Sun, A. Shrivastava, S. Singh, and A. Gupta. Revisiting unreasonable effectiveness of data in deep learning era, 2017.
[56] A. Tarvainen and H. Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results, 2018.
[57] K. Wei, R. Iyer, and J. Bilmes. Submodularity data subset selection and active learning. In International Conference on Machine Learning, pages 1954-1963, 2015.
(58) K. Wei, Y. Liu, K. Kirchhoff, C. Bartels, and J. Bilmes. Submodular subset selection for large-scale speech training data, In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3311-3315. IEEE, 2014.
[59] Y. Yan, Z. Xu. I. W. Tsang, G. Long, and Y. Yang. Robust semi-supervisee learning through label aggregation. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[60] S. Zagoruyko and N. Komodakis. Wide residual networks, 2017.
[61] H. Zhang, M. Cisse, Y. N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk mini- mization, 2018.
[62] X. Zhu, Z. Ghahramani, and Lafferty. Supirsuper learning using gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning, ICML'03, page 912-919. AAAI Press, 2003.
14


Reviews:
[{"review_id": "nds2QwemB-K", "reviewer": "Reviewer_rNnr", "summary": "In this paper the authors propose a framework to select a subset of unlabeled data for semisupervised learning using a greedy selection approach.  The authors show the effectiveness of their method by extensive experimentaion on real world data sets. They show that their method gives significant speedups in traditional semi supervised learning tasks with very less drop in accuracy. For Robust SSL where the unlabeled data has out of distribution points or class imbalance , their method actually outperforms the state of the art with a significant speedup.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 proposes a framework to select a subset of unlabeled data for semisupervised learning. The subset selection and the learning task are done together by solving a bilevel discrete-continuous optimization problem. The authors show that the task of subset selection can be done using a greedy approach as the function is weakly submodular. They demonstrate the effectiveness of the framework with extensive experimentation\n\nSignificance:\nThe task of labeling data is very costly. Hence semisupervised learning is important . However the state of art algorithms for SSL are expensive and for Robust SSL even more so. Hence the problems addressed in the paper are well motivated.\n\nOriginality:\nFrom the theoretical point of view, the paper is not that novel. The main theoretical contribution, I believe, is the framework itself and the proposal of the subset selection problem along with learning as a bilevel optimization and proving it weakly submodular. The proof of theorem builds up on existing techniques. Also traditionally the word \"coreset\" is used when there are some provable guarantees(in terms of sample size, approximation etc.). However in this paper either there are no such guarantees or at least they are not clearly highlighted in the writing.\nThat being said , the paper, does a very good task in the experimentation. The experiments are done on large real world datasets and also the subset is used with atleast 3 state of the art techniques. Most of the details and setup is stated clearly. The subset is compared with random sample, early stopping  and also CRAIG (which was proposed for supervised learning. Modifying that for SSL is also a minor contribution). Advantage is shown not only in terms of convergence time but also in tems of CO_2 emission.  Experiments for Robust SSL beat the state of art method both in terms of time and accuracy. \n\nClarity and Quality:\nI didnot go through the proof in details but it looks ok. I would suggest to highlight the theoretical contributions more in the writing and make them clear. Also in writing there is sudden change in tense (from present to past tense) on lines 266 and 268. In terms of empirical results this is a very good paper and will be of interest to ML community in general and specifically to the ML practitioners and ML engineers. Also the appendices are quite detailed and give a good overview of state of art SSL algorithms.\n\nQuestion: Just as the authors have modified CRAIG for the semisupervised setting, is it possible to modify the CRUST algorithm used to work with nosiy labels ( Baharam et al Neurips 2020. ) for Robust SSL?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "For limitations please refer to the above section.\n\nI donot see any major potential negative impact of this work.\n\nFor improvement please highlight the technical challenges in theory and your theoretical contributions more in writing. Also would be good to give more details (related work) about traditional coresets and contrast your coresets with traditional ones.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "mezD5vyNJM7", "reviewer": "Reviewer_3kHQ", "summary": "This paper proposes RETRIEVE to address the computational cost issue in previous semi-supervised learning (SSL) algorithms. The key idea is to train SSL on a subset of unlabeled data (coreset) instead of the entire unlabeled data. To do so, it must solve the problem of selecting the coreset efficiently and effectively. RETRIEVE tackles this problem by solving a two-level optimization problem such that the selected coreset minimizes the labeled set loss. This paper evaluates RETRIEVE on two settings---traditional SSL and robust SSL---and demonstrates its improvement in terms of speed, energy consumption, and CO2 emissions compared to prior work.", "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": "**Originality**: The proposed method is new. The novelty of RETRIEVE is to train on coreset of unlabeled data rather than on the entire unlabeled data. The challenge is then how to select the high-quality coreset effectively and efficiently. They use greedy selection and Taylor approximation. Generally speaking, the novelty of this work is incremental:\n- The subset selection problem is NP-hard in general [1]. \n- The connection with submodular optimization has been demonstrated before [2].\n\n[1] Balas Kausik Natarajan. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):227–234, 1995.\n\n[2] Baharan Mirzasoleiman, Jeff Bilmes, and Jure Leskovec. Coresets for data-efficient training of machine learning models. In International Conference on Machine Learning, pages 6950–6960. PMLR, 2020.\n\n**Quality**: The submission is technically sound. The claims in the contribution list are well supported by theoretical analyses and empirically results.  I like the extra measurement in terms of energy consumption and CO2 emissions. The related work is adequately cited. \n\n**Clarity**: This paper is well-written and easy to follow. The problem is also well-motivated from the introduction by asking two questions. The experimental details are also very specific such that reproducing the results should be possible. \n\n**Significance**: Empirically, RETRIEVE outperforms prior work in two different settings. I would recommend the authors to add releasing code link in the revision.\n\nHere are a few questions:\n- Can RETRIEVE generalize to machine learning methods other than deep neural network? For instance, logistic regression, graident boosting tree? \n- If no to the above question, would it be a limitation of this work?\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper does not discuss any limitation. I would recommend to add limitations in the revision, which definitely exist. The paper mentions positive societabl impact in terms of less energy consumption and CO2 emissions during training, which is good.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "5E8C9bdZA2i", "reviewer": "Reviewer_fgXZ", "summary": "In this paper, the authors propose a coreset selection framework, called RETRIEVE, that aims to improve the efficiency and robustness of semi-supervised learning (SSL).\nThe main insight that underlies RETRIEVE is that effective selection of a subset of unlabeled data - instead of using the entire unlabeled data - and training on such a carefully selected subset can enable current SSL algorithms to converge faster and significantly reduce the computational cost of the learning process.\nThe study empirically demonstrates that RETRIEVE can reduce the training time and improve the performance for out-of-distribution or imbalanced data for various SSL algorithms.\n", "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": "GENERAL COMMENTS\n\nThis study presents the potential benefits of employing coreset selection schemes in the context of semi-supervised learning.\nEvaluation results based on a number of benchmarks show that the proposed coreset selection scheme, RETRIEVE, may potentially improve the performance of various SSL algorithms - especially, for out-of-distribution (OOD) data and imbalanced datasets.\nHowever, the evaluation results are somewhat limited and further evaluations of RETRIEVE, as well as comparisons with other coreset selection schemes, would be needed to demonstrate the benefits of RETRIEVE in a more convincing manner.\nThere are also a number of ambiguities in the paper that need to be clarified.\n\n\nDETAILED COMMENTS\n\n1. Figure 1 is not very informative in its current form.\nThe authors may want to consider removing it and instead provide a better explanation in the main text or try revising the figure to make it more informative.\n\n2. \"Accuracy degradation\" is not clearly defined and its use is a bit confusing.\nFor example, when the accuracy is improved (despite the speedup), it is shown as \"negative\" accuracy degradation.\nIt would be better to show the \"accuracy\" or \"accuracy improvement\" rather than \"accuracy degradation\" to make it easier to understand.\n\n3. In the caption for Figure 2, does \"Efficient SSL\" refer to \"Traditional SSL\"?\nIn other places of the paper, the authors typically refer to \"Traditional SSL\" and \"Robust SSL\", and it would be better to use consistent terminology throughout the paper.\n\n4. In lines 77-79, what does it mean that RETRIEVE \"minimizes the performance on the labeled dataset\"?\nPlease rephrase to make the meaning clear.\n\n5. It is unclear what is meant by \"Equation (5) can be solved efficiently using greedy algorithms [30, 31] with approximation guarantees.\"\nWhat are the mentioned \"approximation guarantees\"?\nThis requires further elaboration.\n\n6. In the performance evaluation results, only Craig was tested and compared with the proposed coreset section scheme.\nTo demonstrate the advantages of RETRIEVE, performance should be evaluated for other combinations of recent coreset selection algorithms (e.g., Bayesian coreset as well as other coreset selection schemes discussed in lines 129-137) with SSL.\n\n7. It is mentioned (lines 287-289) that \"for the Robust SSL scenario, we do not warm start with the full unlabeled set for training\" and that this is \"because training on an entire unlabeled set containing biases which instead hurts the model performance\"\nPlease provide further insights underlying this statement.\nAlso, this sentence appears to be broken and needs to be rephrased.\n\n8. Please clearly explain how the speed-up and the accuracy degradation were evaluated.\nFurthermore, explain what the data points shown in the figures represent.\n\n9. Despite the importance in the proposed greedy algorithm, connections with weak-submodularity and its implications are not discussed in detail (e.g., lines 366-367)\nPlease elaborate.\n\n10. Is there a way to balance the trade-off between speed and accuracy when integrating RETRIEVE into SSL algorithms?\n\n\n----------------------------\n\nNOTE:\n\nThe original rating has been updated after reviewing the authors' point-by-point response to the above comments.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss limitations of the current work and also discuss any potential negative societal impact in the supplementary material.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "-ZdF5tBPntN", "reviewer": "Reviewer_k5XM", "summary": "This work extends previous approaches for coreset selection to the problem of semi-supervised learning (SSL). Experimental results show the approach has good performance even in settings with data imbalance and out of domain training data\n", "questions": "", "limitations": "", "rating": 7, "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": "This work extends previous approaches for coreset selection to the problem of semi-supervised learning (SSL). Experimental results show the approach has good performance even in settings with data imbalance and out of domain training data\n\nOriginality/Significance: Straightforward application of previous ideas from methods like CRAIG and GLISTER to the problem of SSL. This may have impact in the SSL community but I think it's significance for data summarization/selection is rather limited.\n\nClarity: Well organized overall, good review of related work that unifies SSL algorithms under a common framework and distinguished the proposed approach from previous SSL methods\n\nQuality/Methodology: Proposed method appears to improve consistently over previous work, but authors should compare against GLISTER and GRAD-MATCH\n\nQuestions:\n- How would the method perform on data from non-image domains?\n\n---\nEDIT: The authors fully addressed my main questions about additional baselines and problem domains. Therefore I am increasing my score to 7", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limited discussion of limitations/societal impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes RETRIEVE to address the computational cost issue in previous semi-supervised learning algorithms. It is well-written and well-motivated. The proposed idea is incremental but technically sound. The claims are well supported by theoretical analyses and extensive experimental results.
Decision: Accept (Poster)