RETRIEVE: Coreset Selection for Efficient and Robust Semi-Supervised Learning
Year: 2021

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 RETRIEVE1, 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× in the traditional SSL setting and achieves a speedup of 5× 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.

heading: 1 Introduction
text: Deep learning algorithms have had great success over the past few years, often achieving human or 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 a domain expert for labeling, making it nearly impossible to create a large labeled set. In order to reduce the dependency on the availability of labeled data, semi-supervised learning (SSL) algorithms [7] were proposed to train models using large amounts of unlabeled data along with the available labeled data. Recent works [42, 56, 4, 53] show that semi-supervised learning algorithms can achieve similar performance to standard supervised learning using significantly fewer labeled data instances.
1coResets for EfficienT and Robust semI-supErVised lEarning
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
However, the current SOTA SSL algorithms are compute-intensive with large training times. For example, from our personal experience, training a WideResNet model [60] on a CIFAR10 [27] dataset with 4000 labels using the SOTA FixMatch algorithm [53] for 500000 iterations takes around four days on a single RTX2080Ti GPU. This also implies increased energy consumption and an associated carbon footprint [54]. Furthermore, it is common to tune these
SSL algorithms over a large set of hyper-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-based Blackbox optimization[16] for each SSL algorithm (which runs 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 at most universities and smaller companies. The first problem we try to address in this work is: Can we efficiently train a semi-supervised learning model on coresets of unlabeled data to achieve faster convergence and reduction in training time?
Despite demonstrating encouraging results on standard and clean datasets, current SSL algorithms perform poorly when OOD data or class imbalance is present in the unlabeled set [44, 8]. This performance degradation can be attributed to the fact that the current SSL algorithms assume that both the labeled set 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 1. Several recent works [59, 8, 17] were proposed to mitigate the effect of OOD in unlabeled data, in 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 to achieve similar performance to existing robust SSL methods while being significantly faster?
To this end, we propose RETRIEVE, a 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 a 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 a coreset from the unlabeled set with similar gradients to the labeled set.

heading: 1.1 Our Contributions
text: The contributions are our work can be summarized as follows:
• RETRIEVE Framework: We propose a coreset selection algorithm RETRIEVE for efficient and robust semi-supervised learning. RETRIEVE poses the coreset selection as a discrete-continuous bi-level optimization problem and solves it efficiently using an online approximation of single-step gradient updates. Essentially, RETRIEVE selects a 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 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 3× speedup with accuracy degradation of around 0.7%. RETRIEVE also achieves more than 4.2× 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 2× speedup (see VAT Extended bar plot in Figure 2a). RETRIEVE also consistently outperforms simple baselines like early stopping and random sampling.
• RETRIEVE in Robust SSL: 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 5× faster. RETRIEVE also significantly outperforms just VAT and random sampling.

heading: 1.2 Related Work
text: 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, 11, 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-minimization component forces the model instances to have low-entropy predictions on unlabeled data instances to ensure that the classes are well separated. One can achieve entropy minimization by directly adding the entropy loss component on the unlabeled class prediction or using methods like Pseudo-Labeling to enforce it implicitly. Mean-Teacher [56] approach uses a consistency regularization component that forces the predictions of the exponential moving average of the model to be the same as 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 a 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 is 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 a supervised learning setting is by reweighing each data instance and jointly learning these weights along with the model parameters. Safe-SSL (DS3L) [17] is a recently proposed SOTA method for robust SSL learning. DS3L is similar to 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 it a bi-level optimization problem. In this regard, both RETRIEVE and Safe-SSL approach solves a bi-level optimization problem, except that RETRIEVE solves a discrete optimization problem at the outer level, thereby enabling significant speedup compared to SSL algorithms and an even more considerable
speedup compared to safe-SSL (which itself is 3× 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 to achieve robust performance and a distributionally robust model to deal with OOD [8].
Coreset and subset selection methods: Coresets [13] 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 on 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, 51, 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, 57, 58].

heading: 2 Preliminaries
text: Notation: DenoteD = {xi, yi}ni=1 to be the labeled set with n labeled data points, and U = {xj}mj=1 to be the unlabeled set with m data points. Let θ be the classifier model parameters, ls be the labeled set loss function (such as cross-entropy loss) and lu be the unlabeled set loss, e.g. consistencyregularization loss, entropy loss, etc.. Denote LS(D, θ) =
∑ i∈D
ls(θ, xi, yi) and LU (U , θ,m) =∑ j∈U milu(xj , θ) where m ∈ {0, 1}m is the binary mask vector for unlabeled set. For notational convenience, we denote lsi(θ) = ls(xi, yi, θ) and denote luj(θ) = lu(xj , θ).
Semi-supervised loss: Following the above notations, the loss function for many existing SSL algorithms can be written as LS(D, θ) + λLU (U , θ,m), where λ is the regularization coefficient for the unlabeled set loss. For Mean Teacher [56], VAT[42], MixMatch [4], the mask vector m is made up entirely of ones, whereas for FixMatch [53], m is confidence-thresholded binary vector, indicating whether to include an unlabeled data instance or not. Usually, LS is a cross-entropy loss for classification experiments and squared loss for regression experiments. A detailed formulation of the loss function LU used in different SSL algorithms is given in Appendix C
Robust Semi-supervised loss: However, for robust semi-supervised loss, the mask vector m is replaced with a weight vector w ∈ Rm 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(D, θ) + λLU (U , θ,w), where λ is the regularization coefficient for the unlabeled set loss. The state-of-the-art robust SSL method, Safe-SSL [17] poses the learning problem as:
outer−level︷ ︸︸ ︷ w∗ = argmin
w LS(D, argmin θ (LS(D, θ) + λLU (U , θ,w))︸ ︷︷ ︸
inner−level
) (1)
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
w LS(D, θ − α∇θLS(D, θ)− αλ∇θLU (U , θ,w)
Safe-SSL also uses a single-step gradient approximation to solve the outer level problem as well. As discussed before, the optimization problem of the Safe-SSL [17] 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-SSL.

heading: 3 RETRIEVE framework
text: In RETRIEVE, the coreset selection and classifier model learning on 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 a semi-supervised manner, and every Rth epoch, a new coreset is 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 θt be the classifier model parameters and the St be the coreset at time step t. Since coreset selection is done every R epochs, we have St = Sbt/Rc, 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:
LS(D, θt) + λt ∑ j∈St mjtlu(xj , θt) (2)
where mjt is the mask binary value associated with the jth point based on model parameters θt and λt is the unlabeled loss coefficient at iteration t. Note that objective function given in Equation (2) is dependent on the SSL algorithm used in RETRIEVE framework. If gradient descent is used for learning, the parameter update step from time step t to t+ 1 is as follows:
θt+1 = θt − αt∇θLS(D, θt)− αtλt ∑ j∈St mjt∇θlu(xj , θt) (3)
where αt is the learning rate at iteration t. The update step for mini-batch SGD is similar, just that it does the above on minibatches of the dataset.

heading: 3.1 Problem Formulation
text: The coreset selection problem of RETRIEVE at timestep t is as follows:
outer−level︷ ︸︸ ︷ St = argmin
S⊆U :|S|≤k LS
( D, argmin
θ
( LS(D, θt) + λt ∑ j∈S mjtlu(xj , θt) )
︸ ︷︷ ︸ inner−level
) (4)
where k is the size of the coreset and mjt is the binary value associated with the jth instance based on model parameters θt. k is a fraction of the entire dataset (e.g. 20% or 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 a discrete subset selection problem. However, solving the inner-optimization problem naively is computationally intractable, and, we need to make some approximations.

heading: 3.2 One-Step Gradient Approximation
text: To solve the inner optimization problem efficiently, RETRIEVE adopts a one-step gradient approximation based optimization method similar to [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 is to jointly optimize the model parameters and the subset as the learning proceeds. After this approximation, the coreset selection optimization problem becomes:
St = argmin S⊆U :|S|≤k LS(D, θt − αt∇θLS(D, θt)− αtλt ∑ j∈S mjt∇θlu(xj , θt)) (5)
However, even after this approximation, the above optimization problem (Equation (5)) is NP-hard.
Theorem 1 Optimization problem (Equation (5)) is NP hard, even if ls is a convex loss function. If the labeled set loss function ls is cross-entropy loss, then the optimization problem give in the Equation (5) can be converted into an instance of cardinality constrained weakly submodular maximization.
The proof is given in Appendix B. The given Theorem 1 holds as long as ls is a cross-entropy loss irrespective of the form of lu. Further, Theorem 1 implies that the optimization problem given in Equation (5) can be solved efficiently using greedy algorithms [37, 38] with approximation guarantees. RETRIEVE uses stochastic-greedy algorithm [22, 38] to solve the optimization problem Equation (5) with an approximation guarantee of 1−1/eβ− inO(m log(1/ )) iterations wherem 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:
f(θt,S) = −LS(D, θt − αt∇θLS(D, θt)− αtλt ∑ j∈S mjt∇θlu(xj , θt)) (6)
Notice that during each greedy iteration, we need to compute the set function value f(θt,S ∪ e) to find the maximal gain element e that can be added to the set S. 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.

heading: 3.3 RETRIEVE Algorithm
text: To make the greedy selection algorithm efficient, we approximate the set function value f(θt,S ∪ e) with the first two terms of it’s Taylor-series expansion Let, θS = θt − αt∇θLS(D, θt) − αtλt ∑ j∈S mjt∇θlu(xj , θt). The modified set function value with Taylor-series approximation is as follows:
f̂(θt,S ∪ e) = −LS(D, θS) + αtλt∇θLS(D, θS) T met∇θlu(xe, θt) (7)
where met is the binary mask value associated with element e. Note that the term met∇θlu(xe, θt) can be precomputed at the start of the greedy selection algorithm, and the term ∇θLS(D, θS) needs to be computed only once every greedy iteration, thereby reducing the computational complexity of the greedy algorithm.
Algorithm 1: RETRIEVE Algorithm Input: Labeled Set: D, Unlabeled Set: U , Reg. Coefficients:
{λt}t=T−1t=0 , Learning rates: {αt} t=T−1 t=0
Input: Total no of epochs: T , Epoch interval for subset selection: R, Size of the coreset: k Set t = 0; Randomly initialize model parameters θ0 and coreset S0 ⊆ U : |S0| = k; repeat if (t%R == 0) ∧ (t > 0) then St = GreedySelection(D,U, θt, λt, αt, k)
else St = St−1
Compute batchesDb = ((xb, yb); b ∈ (1 · · ·B)) from D Compute batches Stb = ((xb); b ∈ (1 · · ·B)) from S *** Mini-batch SGD *** Set θt0 = θt for b = 1 toB do
Compute mask mt on Stb from current model parameters θt(b−1) θtb = θt(b−1) − αt∇θLS(Db, θt)− αtλt
∑ j∈Stb mjt∇θlu(xj , θt(b− 1))
Set θt+1 = θtB t = t+ 1
until t ≥ T return θT ,ST
A detailed pseudo-code of the RETRIEVE algorithm is given in Algorithm 1. RETRIEVE uses a greedy selection algorithm for coreset selection, and the detailed pseudo-code of the greedy algorithm is given in Algorithm 2. RETRIEVE can be easily implemented with popular deep learning frameworks [47, 1] that provide auto differentiation functionalities. In all our experiments, we set R = 20, i.e., we update the coreset every 20 epochs.

heading: 3.4 Additional Implementation Details:
text: In this subsection, we discuss additional implementational and practical tricks to make RETRIEVE scalable and efficient.
Last-layer gradients. Computing the gradients over deep models is time-consuming due to an enormous number of parameters in the model. To address this issue, we adopt a last-layer gradient approximation similar to [2, 39, 24, 23] by 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 it on the entire unlabeled dataset for a few epochs similar to [23]. Warm starting allows the classifier model to have a

heading: 2.5 5 10
text: 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 = κTkm epochs where k is coreset size, T is the total number of epochs, κ 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.
3.5 Epochs vs. Iterations Algorithm 2: GreedySelection Input: Labeled Set: D, Unlabeled Set: U , Model Parameters:
θt, Learning rate: αt Input: Regularization Coefficient: λt, Budget: k Initialize St = ∅ Setm = |U| Compute mask values m based on current model parameters θt for e ∈ U do
Compute θe = me∇θlu(xe, θt) for i = 1 to k do
Compute θS = θt−αt∇θLS(D, θt)−αtλt ∑ j∈S mjt∇θlu(xj , θt)
Compute∇θLS(D, θS) V ∼ Sample dmlog(1/ )e instances from U best− gain = −∞ for e ∈ V do
Compute gain ĝ(e) = αtλt∇θLS(D, θS) T me∇θlu(xe, θt) if ĝ(e) > best− gain then Set s = e Set best− gain = ĝ(e)
St = St ∪ s U = U \ s
return St
Most of the existing SSL algorithms are trained using a fixed number of iterations instead of epochs. However, for easier comprehension of the RETRIEVE algorithm, we use the epoch notation in our work. A single epoch here meant a pass over random mini-batches of data points, such that the total number of data points encountered 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.

heading: 4 Experiments
text: Our experimental section aims to verify the efficiency and effectiveness of RETRIEVE by evaluating 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
mean test accuracy and the standard deviations was given in Appendix (G, H). For a 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 discuss baselines that are 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) [42] and FixMatch [53]. The baselines considered are RANDOM (where we just randomly select a subset of unlabeled data points of the same size as RETRIEVE), CRAIG [39, 23] and FULL-EARLYSTOP. CRAIG [39, 23] was actually proposed in the supervised learning scenario. We adapt it to SSL by choosing a 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 a subset of mini-batches instead of data instances for efficiency and scalability. Similarly, we use the per-batch version of GRADMATCH proposed in [23] adapted to SSL setting as another baseline. For more information on the formulation of CRAIG and GRADMATCH in the SSL case, see Appendix D, E. Again, we emphasize that RANDOM, CRAIG, and GRADMATCH are run with early stopping for the same duration as RETRIEVE. 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 a 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 RETRIEVE 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 a baseline in Robust SSL scenario.
2.5 5
Speed Up→
0
2
4
R el
. T
es t
E rr
o r → RETRIEVE BayesianCoreset
1000 instances with 100 instances from each class, an unlabeled set of 73257 instances, a test set of 26032 instances. For IMDB and ELEC datasets, we use the labeled and unlabeled splits following the work [41]. For CIFAR10 and SVHN datasets, we use the Wide-ResNet-28-2 [60] model that is commonly used in SSL [44, 53]. For MNIST, we use a variant of LeNet [31] (see Appendix F for details). For IMDB and ELEC datasets, we use a model comprising of Word Embedding layer, LSTM model, and two-layer MLP model following the architecture given in the work [41]. Similar to the work [41], we initialize the embedding matrix and LSTM model weights using a pretrained recurrent language model using both the labeled and unlabeled data. For Image datasets, with RETRIEVE(and baselines like RANDOM, GRADMATCH and CRAIG), we use the Nesterov’s accelerated SGD optimizer with a 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 FULLEARLYSTOP, we use the Adam optimizer [25] and follow the experimental setting from the SSL papers [53, 42, 56].
2https://ai.stanford.edu/ amaas/data/sentiment/ 3http://riejohnson.com/cnn_data.html
For Text datasets, with RETRIEVE(and baselines like RANDOM, GRADMATCH and CRAIG), we set the hyperparameter values following the work [41]. 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 CIFAR10, 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 a 6-class dataset, with classes 1-6 as ID and classes 7-10 as OOD. We denote the OOD ratio=Uood/(Uood + Uin) where Uin is ID unlabeled set, Uood is OOD unlabeled set. For CIFAR10, we use a labeled set of 2400 instances and an unlabeled set of 20000 instances, and for MNIST, we use a 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-10. For CIFAR-10, we use a labeled set of 2400 and an unlabeled set of 20000 instances.
Traditional SSL Results: The results comparing the accuracyefficiency 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, Mean-Teacher, and FixMatch. For warm-start, we set kappa value to κ = 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, 4d, 4e,
4c) shows the plots of relative error 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 RETRIEVE 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 a performance loss of 0.7% and 0.3% using VAT on CIFAR10 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 CIFAR10 and SVHN datasets. Additionally, RETRIEVE achieves a speedup of 3.8x with a performance loss of 0.7% using FixMatch on the CIFAR10 dataset. Sub-figures(6a, 6b) shows the plots of relative error vs speedup both w.r.t full training (i.e., 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 a performance loss of 0.5% and 0.6% for 30% subset of IMDB and ELEC datasets. Figure 5 shows the results comparing the BAYESIANCORESET method [6], adapted to the SSL setting with RETRIEVE using the VAT algorithm for 20% and 30% CIFAR10 subsets. The results show that RETRIEVE achieves better performance than the SSL extension of the BAYESIANCORESET 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 log-likelihood 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 BAYESIANCORESET that is not meant for GPU usage in our
experiments. Hence the speedups of the BAYESIANCORESET approach can be further improved with efficient code implementation. Subfigure 4h shows that RETRIEVE achieves faster convergence compared to all other methods on CIFAR10 for 30% subset with Mean-Teacher. Subfigure 4g shows the extended convergence of RETRIEVE on CIFAR10 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 of 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, 4b, 4d, 4e, 4c). We observe that RETRIEVE matches the performance of VAT while being close to 2× faster in running times (and correspondingly energy efficiency). We repeat this experiment with MT in the Appendix G. Also, more detailed results with additional convergence plots and tradeoff curves are in Appendix G.
Robust SSL Results: We test the performance of RETRIEVE on CIFAR10 and MNIST datasets with OOD in the unlabeled set and CIFAR10 dataset with the class imbalance in both labeled and unlabeled sets. sub-figures 7a, 7b shows the accuracy plots of 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 in the OOD scenario. Next, sub-figure 7c shows the accuracy plots of RETRIEVE for different class imbalance ratios of 10%, 30% and 50% on CIFAR10 dataset. The results show that RETRIEVE with VAT outperforms all other baselines, including DS3L [17] (also run with VAT) in the class imbalance scenario as well. In particular, RETRIEVE outperforms other baselines by at least 1.5% on the CIFAR-10 with imbalance. Sub-figure 7d shows the time taken by different algorithms on the CIFAR10 dataset with a 50% class imbalance ratio. The results show that CRUST did not perform well in terms of accuracy and speedups achieved compared to RETRIEVE. Except for MixUP, CRUST is similar to 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 to the fact that the hypothesized labels used for MixUP in the earlier stages of training are noisy. Furthermore, as stated earlier, CRUST was developed to tackle noisy labels in a 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 to the other baselines. In particular, RETRIEVE is 5x times faster compared to DS3L method. Other detailed results (tradeoff curves and convergence curves) are in Appendix H.

heading: 5 Conclusion and Broader Impacts
text: 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 a scalable stochastic greedy algorithm. Empirically, we show that RETRIEVE is very effective for SSL. In particular, it achieves 3× speedup on a range of SSL approaches like VAT, MT, and FixMatch with around 0.7% accuracy loss and a 2× speedup with no accuracy loss. In the case of robust SSL with imbalance and OOD data, RETRIEVE outperforms existing SOTA methods while being 5× faster. We believe RETRIEVE has a 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.

heading: 6 Acknowledgments and Disclosure of Funding
text: 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 1815696, 1750911, 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.

Review summaries:
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). The 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. The 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. 

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.

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.