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

1.1 Our Contributions

• RETRIEVE selects unlabeled instances to minimize labeled-set loss, using gradients aligned with labeled data to support faster convergence and distribution matching.The framework formulates coreset selection as a discrete-continuous bi-level optimization problem.Source: §1 · p. 2, §1.1 · p. 3
• Across VAT, Mean-Teacher, and FixMatch, RETRIEVE achieves close to 3× speedup with around 0.7% accuracy degradation, and can match VAT with 2× speedup after more iterations.The contribution summary also reports more than 4.2× speedup with slightly higher accuracy degradation.Source: §1.1 · p. 3
• For robust SSL with OOD data and imbalance, RETRIEVE with VAT outperforms DS3L while running around 5× faster.The authors also report that it outperforms VAT and random sampling.Source: §1.1 · p. 3

1.2 Related Work

• Prior SSL methods use consistency regularization and entropy minimization, while robust SSL includes reweighting methods such as DS3L and coreset work targets gradients, validation loss, or representative subsets.The related-work discussion also covers Mean-Teacher, VAT, and FixMatch.Source: §1.2 · pp. 3–4

2 Preliminaries

• The labeled set contains n labeled points and the unlabeled set contains m points; the model uses parameters θ, with separate labeled and unlabeled losses.The labeled loss may be cross-entropy, while the unlabeled loss may be consistency-regularization or entropy loss.Source: §2 · p. 4
• Standard SSL combines labeled-set loss with a regularized unlabeled-set loss, using an all-ones mask for Mean Teacher, VAT, and MixMatch, and confidence-thresholded masks for FixMatch.The regularization coefficient is λ.Source: §2 · p. 4
• Robust SSL replaces the unlabeled-instance binary mask with a learned weight vector, and Safe-SSL uses a one-step gradient approximation to estimate its inner solution.Safe-SSL also approximates the outer-level problem with a single gradient step; RETRIEVE instead uses discrete outer-level subset selection.Source: §2 · pp. 4–5

3 RETRIEVE framework

• RETRIEVE selects a coreset every R epochs, trains on it with the labeled data, and adapts the selected subset as training proceeds.The subset is held fixed between selection steps.Source: §3 · p. 5

3.1 Problem Formulation

• The coreset has size k, a fraction of the unlabeled set; selection uses labeled-set loss, while solving the inner optimization naively is computationally intractable.The outer-level choice is a discrete subset-selection problem.Source: §3.1 · p. 5

3.2 One-Step Gradient Approximation

• A one-step gradient approximation makes co-optimization tractable, and with cross-entropy labeled loss the problem can be treated as weakly submodular maximization for greedy selection.The problem remains NP-hard; stochastic greedy has an approximation guarantee of 1−1/eβ−ϵ in O(m log(1/ϵ)) iterations.Source: §3.2 · pp. 5–6

3.3 RETRIEVE Algorithm

• Greedy selection is costly because it repeatedly evaluates labeled-set loss; RETRIEVE approximates the set-function value and precomputes unlabeled gradients to reduce that cost.The labeled-loss gradient is computed once per greedy iteration.Source: §3.2 · p. 6, §3.3 · p. 6

3.5 Epochs vs. Iterations

• Experiments use R = 20, so the coreset is updated every 20 epochs.The paper defines an epoch as a pass over random minibatches totaling the coreset size; thus the iteration count varies with subset size.Source: §3.3 · p. 6, §3.5 · p. 7

3.4 Additional Implementation Details:

• A last-layer gradient approximation reduces RETRIEVE’s computation by using only the classifier’s final-layer gradients.The method also warm-starts the classifier on the entire unlabeled dataset for a few epochs, with the same warm start used for standard-SSL baselines.Source: §3.4 · pp. 6–7
• Figure 4 reports that RETRIEVE outperforms the baselines in the speedup–accuracy-degradation tradeoff across the traditional SSL tasks shown.Its FixMatch comparison also reports the best energy–accuracy tradeoff, and the convergence plots show faster convergence than the baselines and full training.Source: Figure 4 · p. 7

Experimental Setup

• The algorithm-selection procedure takes labeled and unlabeled sets, model parameters, regularization, and a coreset budget as inputs, then selects unlabeled instances using labeled-set loss gradients.The supplied algorithm excerpt shows sampling unlabeled instances and evaluating gradients of the labeled-set loss.Source: §4 · p. 7
• Experiments cover traditional SSL, OOD robustness, and class imbalance, using image and text datasets and comparisons with SSL, coreset-selection, and robust-SSL baselines.Traditional SSL tests VAT, Mean-Teacher, and FixMatch; robust scenarios use VAT and compare against DS3L and L2RW, among other baselines.Source: §4 · pp. 7–8

Traditional SSL Results

• Across image and text benchmarks, RETRIEVE achieves speedups with small reported accuracy losses for VAT, Mean-Teacher, and FixMatch.Reported examples include 2.7× speedup with 0.7% performance loss for VAT on CIFAR-10, and 3.8× with 0.7% loss for FixMatch on CIFAR-10.Source: §4 · p. 9

Robust SSL Results

• RETRIEVE outperforms robust SSL baselines in most tested OOD and imbalance cases, while running close to 2× faster than VAT and 5× faster than DS3L and L2RW.For CIFAR-10 with imbalance, it outperforms other baselines by at least 1.5% and is 5× faster than DS3L.Source: §4 · p. 10

Traditional SSL Results

• RETRIEVE’s convergence plots show faster convergence than other methods in one Mean-Teacher setting and near-2× faster VAT training at comparable performance.The extended VAT runs allow more epochs to reach comparable accuracy to full training, with reduced efficiency.Source: §4 · p. 10

Conclusion

• RETRIEVE is formulated as discrete-continuous bi-level coreset selection and solved with an online single-step gradient approximation and stochastic greedy selection.The paper connects the optimization to weak submodularity.Source: §5 · p. 10
• Traditional SSL experiments report 3× speedup with around 0.7% accuracy loss, and 2× speedup with no accuracy loss across the stated SSL approaches.Source: §5 · p. 10
• For robust SSL with OOD data and imbalance, RETRIEVE is reported to outperform existing state-of-the-art methods while running 5× faster.The conclusion also identifies reduced training CO2 emissions as a potential societal impact.Source: §5 · p. 10

A.1 Code

• Code for RETRIEVE with VAT and Mean-Teacher is available in CORDS, while FixMatch code is in a separate repository with a planned transfer to CORDS.Source: §A.1 · p. 16

A.2 Licenses

• The supplementary material reports MIT licensing for RETRIEVE repositories and some underlying code, while DS3L and L2RW repositories have unknown licenses.The listed datasets are publicly available, with stated licenses, and are reported to contain no personally identifiable information.Source: §A.2 · p. 16

B Proof of Theorem 1

• The optimization problem in Equation (5) is NP-hard even when the labeled-set loss is convex; with cross-entropy labeled loss, it becomes cardinality-constrained weakly submodular maximization.Source: B Proof of Theorem 1 · p. 16
• Unlike GLISTER’s stated cross-entropy setting, the proof establishes weak submodularity with an SSL inner-level objective and either cross-entropy or squared unlabeled-set loss.Source: B Proof of Theorem 1 · p. 16

B.1 Proof Sketch

• The proof sketch organizes the argument around notation, α-submodularity, greedy approximation guarantees, and loss-specific lemmas.It treats cross-entropy and squared loss cases for RETRIEVE.Source: §B.1 · p. 16

B.2 Notation

• The gain of adding elements to a set is defined as the change in the set function, and RETRIEVE’s optimization problem is shown to be approximately submodular.The definition is G_{θ,v}(s) = f(θ, v ∪ s) − f(θ, v).Source: §B.2 · p. 17

B.3 α-submodularity

• The proof bounds labeled and unlabeled data-point norms by R; for cross-entropy labeled loss, this gives α = 2R^2/(2R^2+1).The paper describes the bounded-norm condition as common in convergence analysis.Source: §B.3 · p. 17

B.4 α-submodularity of RETRIEVE

• With cross-entropy labeled loss, the optimization problem is cardinality-constrained α-approximate submodular maximization for cross-entropy unlabeled loss (α = 2R^2/(2R^2+1)) and squared unlabeled loss (α = R^2/(R^2+1)), where R is the maximum l-2 norm across both data sets.Source: §B.4 · p. 17

B.5 Proof

• The proof decomposes the objective into a positive modular term and a monotone term, then establishes α-submodularity for their sum.The proof identifies the second term as not necessarily submodular and derives its α-submodularity under bounded data norms.Source: §B.5 · p. 19
• For coreset selection with cross-entropy labeled loss and squared or cross-entropy unlabeled loss, any greedy algorithm achieves a 1 − e^(−(1−α)) approximation factor.Source: §B.5 · p. 21

C.1 Notation

• Many SSL objectives combine labeled-set loss with a weighted unlabeled-set loss; FixMatch uses confidence thresholding to mask unlabeled examples.Mean Teacher, VAT, and MixMatch use an all-ones mask in the stated formulation.Source: §C.1 · p. 22, §C.5 · p. 23

C.2 Mean-Teacher; C.3 VAT

• Mean Teacher uses an exponential moving average of model parameters to generate stable unlabeled targets, while VAT uses perturbations chosen to maximize prediction-distribution KL divergence.Mean Teacher’s unlabeled loss is squared loss; VAT’s is KL divergence.Source: §C.2 · p. 22, §C.3 · p. 22

C.4 MixMatch; C.5 FixMatch

• MixMatch sharpens predictions across augmentations before mix-up, whereas FixMatch compares weakly and strongly augmented predictions using confidence-thresholded examples.MixMatch uses squared unlabeled loss; FixMatch uses cross-entropy.Source: §C.4 · p. 23, §C.5 · p. 23

D CRAIG Algorithm for SSL; E GRADMATCH Algorithm for SSL

• CRAIG and GRADMATCH select unlabeled subsets intended to match the full unlabeled-set gradient with a weighted sum of selected-example gradients.The experimental formulations use per-batch variants, selecting mini-batches rather than individual examples.Source: D CRAIG Algorithm for SSL · pp. 23–24, E GRADMATCH Algorithm for SSL · pp. 24–25

F.1.1 Traditional SSL scenario; F.1.2 Robust SSL scenario

• Traditional SSL experiments use CIFAR-10 and SVHN, while robust SSL experiments use CIFAR-10 and MNIST.The paper states that these datasets are publicly available and contain no personally identifiable information.Source: §F.1.1 · p. 25, §F.1.2 · p. 25

F.2 Traditional SSL baselines; F.3 Robust SSL baselines

• Traditional SSL comparisons include RANDOM, CRAIG, and FULL-EARLYSTOP; robust SSL comparisons include DS3L and L2RW alongside RETRIEVE.Traditional baselines use warm-start, while the robust setting described here runs without warm-start and uses VAT.Source: §F.2 · p. 26, §F.3 · p. 26

F.4 Experimental Setup

• The experiments implement RETRIEVE with Mean Teacher, VAT, and FixMatch using open-source PyTorch implementations or adaptations.The paper also describes implementation sources for DS3L and L2RW.Source: §F.4 · p. 26
• Most experiments use WideResNet-28-2 with Nesterov accelerated SGD and cosine annealing; MNIST OOD uses a two-layer CNN and a lower learning rate.The learning rate is 0.03 generally and 0.003 for MNIST OOD.Source: §F.4 · p. 26

G.1 RETRIEVE-WARM vs RETRIEVE

• RETRIEVE-WARM is reported as more efficient and effective than RETRIEVE in traditional SSL, and is used for those experiments.The comparison is shown for Mean Teacher and VAT on CIFAR-10 with a 30% subset fraction.Source: §G.1 · p. 26, Figure 8 · p. 28

G.2 Test-Accuracies, Training times and Standard deviations

• Tables 5–10 report top-1 test accuracy, training time, and standard deviations for VAT and Mean-Teacher on CIFAR10 and SVHN, and FixMatch on CIFAR at 10%, 20%, and 30% subset fractions.Source: §G.2 · p. 29

G.3 MT extended convergence plot

• On CIFAR10 at 30% subset fraction, Mean-Teacher with RETRIEVE matched original performance at 1.8X speedup and exceeded it at 1.5X speedup.Source: §G.3 · p. 29

G.4 Energy savings

• 3.1X energy efficiency versus original VAT accompanied 0.78% accuracy degradation on CIFAR10.The energy comparison covers subset fractions of 10%, 20%, and 30%.Source: §G.4 · p. 30

H.1 RETRIEVE-WARM vs RETRIEVE

• RETRIEVE was more efficient and effective than RETRIEVE-WARM in robust SSL; on CIFAR10 OOD at 50% OOD, it achieved 79% accuracy in 17.03 hrs versus 78.8% in 18.2 hrs.The comparison also covered MNIST OOD and CIFAR10 imbalance, each at a 50% OOD or class-imbalance ratio.Source: §H.1 · p. 30

• RETRIEVE with VAT outperformed all compared baselines, including DS3L, in class imbalance, by around 1.5% on CIFAR-10 with imbalance.The reported robust-SSL comparisons cover CIFAR10 OOD, MNIST OOD, and CIFAR10 imbalance; standard deviations are also provided.Source: §H.2 · p. 30

I Broader Impacts and Limitations

• RETRIEVE does not reduce SSL training memory requirements and needs additional memory for coreset-selection gradients.The authors say this makes running RETRIEVE on low-memory devices significantly harder without proper memory handling.Source: I Broader Impacts and Limitations · p. 30
• The authors believe RETRIEVE's faster, more energy-efficient SSL training can reduce training energy consumption and CO2 emissions.They note this is particularly relevant because state-of-the-art SSL approaches such as FixMatch are computationally expensive.Source: I Broader Impacts and Limitations · p. 30
• The authors suggest RETRIEVE can enable faster, more energy-efficient hyperparameter tuning in SSL approaches.They describe using smaller training subsets as a step toward Green-AI.Source: I Broader Impacts and Limitations · p. 32