PaperlayerView exact revision on arXiv

Source-linked AI summary

Dash: Semi-Supervised Learning with Dynamic Thresholding

Yi Xu, Lei Shang, Jinxing Ye, Qi Qian, Yu-Feng Li, Baigui Sun, Hao Li, Rong Jin

arXiv:2109.00650v1cs.LGcs.CVstat.ML

TL;DR

SSL must use abundant unlabeled data despite limited labeled data and potentially mismatched pseudo-labeled examples. Dash dynamically selects low-loss unlabeled examples using a changing threshold, with theoretical convergence guarantees and benchmark improvements over fixed-threshold FixMatch.

  • Problem

    SSL needs to exploit abundant unlabeled data despite limited labeled data and the possibility that pseudo-labeled examples do not share the labeled data’s distribution.

  • Method

    Dash dynamically retains unlabeled examples whose losses fall below a threshold derived from labeled data and decreased across optimization iterations.

  • Results

    Dash improves FixMatch across benchmarks, with top-1 testing error improvements over FixMatch exceeding 19% on CIFAR-100, 10% on CIFAR-10, and 58% on SVHN under CTA.

  • Takeaways & Limitations

    Dynamic unlabeled-example selection is important for SSL performance, particularly when labeled data is small, while Dash also provides a non-convex convergence guarantee.

  • Takeaways & Limitations

    The convergence analysis assumes unlabeled data is a mixture of the labeled-data distribution P and another distribution Q.

Abstract

from arXiv · show

While semi-supervised learning (SSL) has received tremendous attentions in many machine learning tasks due to its successful use of unlabeled data, existing SSL algorithms use either all unlabeled examples or the unlabeled examples with a fixed high-confidence prediction during the training progress. However, it is possible that too many correct/wrong pseudo labeled examples are eliminated/selected. In this work we develop a simple yet powerful framework, whose key idea is to select a subset of training examples from the unlabeled data when performing existing SSL methods so that only the unlabeled examples with pseudo labels related to the labeled data will be used to train models. The selection is performed at each updating iteration by only keeping the examples whose losses are smaller than a given threshold that is dynamically adjusted through the iteration. Our proposed approach, Dash, enjoys its adaptivity in terms of unlabeled data selection and its theoretical guarantee. Specifically, we theoretically establish the convergence rate of Dash from the view of non-convex optimization. Finally, we empirically demonstrate the effectiveness of the proposed method in comparison with state-of-the-art over benchmarks.

1 Introduction

Semi-supervised learning leverages abundant unlabeled data, but fixed selection thresholds can discard correct pseudo labels or retain incorrect ones. Dash addresses this with dynamic, loss-based unlabeled-data selection and provides convergence guarantees.

  • Motivation: Limited labeled data motivates SSL because unlabeled data is typically more abundant but labeled examples are costly to obtain.This imbalance is a key hurdle for developing and deploying machine learning models.
  • Existing SSL: SSL methods use approaches including consistency regularization, pseudo labeling, generic regularization, and combinations of these techniques.Pseudo labeling creates artificial labels from model predictions for incorporation into training.
  • Problem: SSL success relies on labeled data and pseudo-labeled unlabeled data coming from the same distribution, a condition that may fail in practice.When this condition fails, using unlabeled data can undermine standard SSL training.
  • Problem: Fixed high-confidence thresholds can eliminate correct pseudo-labeled examples or select incorrect ones during training.FixMatch uses a fixed threshold such as 0.95, motivating adaptive selection.
  • Dash: Dash dynamically selects unlabeled examples whose losses fall below a threshold that is adjusted across optimization iterations.The method integrates with existing SSL algorithms, has a non-asymptotic convergence guarantee, and is evaluated on image benchmarks.

2 Related Work

Prior SSL work includes consistency regularization, pseudo labeling, augmentation-based methods, thresholding, and example weighting. Dash differs by using a data-dependent dynamic threshold with a non-convex convergence guarantee.

  • SSL approaches: SSL research includes consistency regularization, entropy minimization, pseudo labeling, safe SSL, and bi-level weighting of unlabeled examples.These approaches leverage unlabeled-data structure or regulate its contribution to training.
  • Pseudo labeling: Pseudo-labeling retains unlabeled images whose highest predicted-class probability exceeds a predefined threshold.The model itself generates pseudo labels for the unlabeled images.
  • Augmentation-based SSL: UDA, ReMixMatch, and FixMatch combine weak and strong augmentations to generate pseudo labels and enforce prediction consistency.The methods differ in their augmentation choices and pseudo-labeling procedures.
  • Fixed thresholding: UDA and FixMatch use fixed thresholds, with UDA setting 0.8 for CIFAR-10 and SVHN and FixMatch setting 0.95 for all datasets.ReMixMatch and UDA also sharpen predicted label distributions to encourage confident predictions.
  • Dash: Dash selects unlabeled data with a data-dependent dynamic threshold and establishes stochastic-gradient-descent convergence guarantees for non-convex optimization.This setting is applicable to deep learning models.

3 Preliminary and Background

The paper formulates SSL as non-convex classification with labeled and pseudo-labeled data, then reviews FixMatch’s fixed-threshold pipeline. Fixed thresholding may select too many incorrect or discard too many correct pseudo-labeled examples.

  • 3.1 Problem Setting: The problem setting maps inputs x ∈ X ⊆ R^d to labels y ∈ Y and minimizes an expected random loss over the data distribution.The model parameters are learned by minimizing the objective F(w).
  • 3.1 Problem Setting: For K-class classification, the paper uses cross-entropy loss, without requiring the loss to be convex in the model parameters.This non-convex formulation supports applications including deep learning.
  • 3.1 Problem Setting: SSL combines labeled data with unlabeled examples assigned pseudo labels, typically using supervised and unsupervised losses weighted by λ_u > 0.Different constructions of the unsupervised loss produce different SSL methods.
  • 3.2 FixMatch: An SSL Algorithm with Fixed Thresholding: FixMatch generates pseudo labels from weakly augmented images and computes unsupervised cross-entropy on strongly augmented versions.The method uses an indicator to retain only selected unlabeled examples.
  • 3.2 FixMatch: An SSL Algorithm with Fixed Thresholding: FixMatch retains unlabeled examples only when their highest predicted-class probability exceeds the fixed threshold τ = 0.95.The resulting unsupervised loss uses the pseudo label and confidence-based selection.
  • 3.2 FixMatch: An SSL Algorithm with Fixed Thresholding: A fixed threshold may select or discard too many unlabeled examples with wrong or correct pseudo labels, motivating a threshold that changes across optimization iterations.The paper introduces dynamic thresholding to address this selection issue.

4 Dash: An SSL Algorithm with Dynamic Thresholding

Dash dynamically selects unlabeled examples during SSL training by retaining those with losses below an iteration-dependent threshold. It combines a labeled-data warm-up with a selection stage using truncated stochastic gradients and provides a non-convex convergence guarantee.

  • Loss and selection: The method can use FixMatch pseudo labels while evaluating the full loss involving both weakly and strongly augmented images.FixMatch uses a fixed confidence threshold, whereas Dash retains examples according to the unsupervised loss that incorporates both augmentations.
  • Motivation and guarantee: The dynamic selection addresses distribution mismatch and incorrect pseudo labels, for which standard SSL optimization can degrade performance and lacks a clear guarantee.The paper motivates dynamic selection because labeled and pseudo-labeled unlabeled data may not share a distribution; it establishes convergence for SGD in the non-convex setting.
  • Dynamic thresholding: Dash selects unlabeled examples whose losses fall below a threshold that decreases over optimization iterations.The threshold depends on t, with ρt defined as a decreasing function; retained examples contribute to training.
  • Dynamic thresholding: The threshold is initialized from labeled-data loss information, using the averaged labeled loss as a practical estimate of bρ.Theoretical estimation of bρ is intended for convergence analysis, while practice uses the averaged loss from Dl.
  • Algorithm: Dash has a warm-up stage on labeled data followed by a selection stage that applies SGD to dynamically filtered unlabeled data.The warm-up also estimates bρ; the selection stage samples from Du and computes truncated stochastic gradients.
  • Algorithm: Dash updates parameters with mini-batch SGD after computing a truncated stochastic gradient from selected unlabeled examples.At each iteration, the algorithm samples nt = mγ^(t−1) examples, sets ρt = Cγ^−(t−1)bρ, computes gt, and applies the SGD update.

5 Convergence Result

Dash’s convergence analysis assumes unlabeled data mix the labeled-data distribution with a second distribution and imposes standard smoothness, bounded-gradient, and PL conditions. Under these assumptions, the method converges with high probability and achieves O(1/ϵ) sample complexity.

  • Assumptions: Unlabeled examples are modeled as a mixture of the labeled-data distribution P and another distribution Q, sampled with probabilities q and 1−q.
  • Assumptions: The analysis assumes bounded, unbiased stochastic gradients, an L-smooth objective, and a Polyak–Łojasiewicz condition with parameter µ > 0.
  • Convergence guarantee: Under Assumptions 1 and 2, C > 1, F(w∗) = 0, and suitable step-size conditions, Theorem 1 provides a high-probability convergence guarantee for Dash.
  • Convergence guarantee: For T = log(bρ/ϵ) / log(γ), Dash reaches optimization error F(wT +1) ≤ ϵ.
  • Sample complexity: The resulting total sample complexity is O(1/ϵ), matching the supervised-learning rate obtained for standard SGD under the same assumptions.

6 Experiments

Dash is evaluated on standard semi-supervised image-classification benchmarks using FixMatch-based pseudo-labeling, matched training protocols, and multiple unlabeled-data selection settings. It achieves strong results across datasets, especially when labeled data are scarce, while ablations support integration beyond FixMatch.

  • Experimental setup: Dash is compared with state-of-the-art SSL baselines on CIFAR-10, CIFAR-100, SVHN, and STL-10 across ten labeled-data settings.The experiments use the same labeled-image sets as the baselines.
  • Models and hyper-parameters: The experiments use Wide ResNet backbones, FixMatch for pseudo-label generation, CTAugment or RandAugment for strong augmentation, and the same training protocol as FixMatch.Training uses 1024 epochs, batch size 64, SGD with momentum 0.9, and cosine learning-rate decay.
  • Evaluation: Testing error rates are averaged over five independent trials with standard deviations using the same random seeds as the baselines.Results are reported as top-1 testing error rates.
  • Results: Dash has the best performance on CIFAR-10, SVHN, and STL-10, while remaining comparable to ReMixMatch on CIFAR-100.ReMixMatch is slightly better with 400 labels, whereas Dash with RandAugment is slightly better with 2500 and 10000 labels.
  • Results: 3.96% top-1 testing error is achieved by Dash with CTA on STL-10.The paper identifies this as state-of-the-art performance and also reports strong results with out-of-distribution unlabeled images.
  • Results: Dash consistently outperforms FixMatch, with improvements exceeding 19%, 10%, and 58% using CTA on CIFAR-100, CIFAR-10, and SVHN respectively in low-label settings.Using RandAugment, the corresponding improvements are 4%, 8%, and 23%.
  • Ablation study: Dash is not highly sensitive to γ within a tested range and improves Pseudo-Labeling, especially when the number of labeled images is small.The γ ablation tests values 1.01, 1.1, 1.2, and 1.3 on CIFAR-10.

7 Conclusion

The conclusion presents Dash as a generic dynamic unlabeled-data selection scheme for SSL. It reports empirical benefits with FixMatch and a convergence guarantee under non-convex optimization.

  • Conclusion: Dash dynamically selects unlabeled examples whose losses do not exceed a threshold at each optimization step.The threshold changes during training.
  • Conclusion: Dash is a generic scheme that can be integrated with existing semi-supervised learning methods.The conclusion specifically demonstrates integration with FixMatch.
  • Conclusion: Experiments show that dynamic unlabeled-example selection improves FixMatch on semi-supervised image-classification benchmarks.The conclusion presents this as evidence for the importance of dynamic thresholding in SSL.
  • Conclusion: The theoretical analysis establishes a convergence guarantee for Dash under non-convex optimization.

A Proof of Theorem 1

The proof of Theorem 1 separates the analysis of the warm-up solution from convergence of the subsequent iterations. It assumes that the unlabeled dataset is sufficiently large.

  • Proof strategy: The proof has two parts: analyzing the properties of w1 learned in the first step and analyzing convergence across later iterations.
  • Assumption: The theoretical setting assumes that the number of unlabeled examples, Nu, is sufficiently large.

A.1 Properties of Solution w1

The solution-property analysis first states a lemma for the warm-up stage, then bounds stochastic-gradient deviation and the resulting objective value under smoothness and step-size assumptions.

  • Warm-up solution: Lemma 1 analyzes w1 obtained by running the warm-up stage of Algorithm 1 under a condition on η0.The lemma is stated for δ ∈ (0, 1).
  • Gradient analysis: Lipschitz continuity of the gradient supports the objective-function bound used in the proof.
  • Gradient analysis: The update ut+1 = ut − η0 gt and the assumptions, including η0L ≤ 1, yield the intermediate descent relation.
  • Probability bounds: Unbiased stochastic gradients and concentration inequalities provide a high-probability bound on gradient deviation.The cited bound holds with probability 1 − 5δ.
  • Objective bound: The gradient-deviation bound is used with the objective inequalities to further bound F(uT).
  • Threshold bound: The resulting bound makes the condition in (23) applicable and supports the corresponding high-probability statement involving bρ.

A.2 Analysis of Iterative Algorithm

The analysis proves by induction that Dash’s objective decreases geometrically with high probability. It combines dynamically thresholded sample selection, concentration inequalities, and non-convex optimization analysis to establish this guarantee.

  • Inductive objective bound: The proof establishes by induction that F(w_t) ≤ b_ρ γ^−(t−1) with high probability at every iteration.The base case follows from Lemma 1, while the inductive step proves the corresponding bound for F(w_{t+1}).
  • Thresholded sample selection: Dash divides sampled unlabeled-data examples into A_t from P and B_t from Q, retaining those in each set whose loss is below ρ_t.The threshold is ρ_t = Cb_ρ γ^−(t−1) with C > 1, and the selected examples used to compute g_t are formed from the retained subsets.
  • High-probability bounds: Hoeffding, Markov, and concentration inequalities bound the sizes and selection errors of the retained subsets with high probability.The proof separately controls the retained examples from A_t and B_t and bounds the relevant conditional expectations.
  • Thresholded sample selection: The dynamically adjusted threshold selects increasingly many unlabeled examples relevant to the labeled data while keeping selection mistakes bounded by a constant.This supports optimization progress using the selected unlabeled examples.
  • Non-convex optimization step: Using L-smoothness, the update w_{t+1} = w_t − ηg_t, convexity of the squared norm, and the stated assumptions, the analysis derives objective progress.The gradient expectation relation and concentration bounds connect the selected-sample gradient to the population objective.
Loading 2109.00650v1…