Dash: Semi-Supervised Learning with Dynamic Thresholding

In plain words

Semi-supervised learning trains a model with a few labelled examples and many unlabelled ones. A common trick is to let the model label the unlabelled examples itself and then learn from the labels it feels sure about. The trouble is that its guesses are sometimes wrong, and a fixed "only keep confident guesses" cut-off throws away many correct guesses while still letting some wrong ones through.

Dash changes only the rule for which unlabelled examples count. Each example is kept only when its loss is below a cut-off, and the cut-off starts loose and gets tighter as training goes on. The authors plug this rule into an existing method, FixMatch, and report better accuracy on several image benchmarks, most clearly when there are very few labels. They also give a convergence proof for a simplified version of the method.

TL;DR

• Dash keeps an unlabelled example in an SGD step only if its loss is at most a threshold rho_t §4, eq. 13 §4, eq. 18.
• rho_t decays geometrically with the iteration count, starting from an estimate taken from the labelled data §4, eq. 15 §4, eq. 17.
• Author-reported: Dash beats FixMatch in all 20 paired settings in Tables 1 and 2, with the largest gains at the smallest label counts tab. 1 tab. 2 §6.3.
• The convergence result (Theorem 1) covers a simplified loss without augmentation and assumes a loss in [0, 1] §5.
• No official code was found [see Paper vs code].

Problem

Unlabelled data helps semi-supervised learning only if its pseudo labels come from the same distribution as the labelled data. When pseudo labels are wrong, using them can hurt compared with plain supervised training §1.

FixMatch selects unlabelled examples with a fixed confidence of 0.95 §3.2. The authors show, for CIFAR-100 with 400 labels on Wide ResNet-28-8, that this cut-off drops many correct pseudo labels and keeps wrong ones fig. 1. Their Dash curves start by keeping more wrong pseudo labels than FixMatch, then drop more of them later fig. 1 (b).

Classical convergence analysis of SGD on the labelled-plus-unlabelled objective assumes that all training examples come from one distribution, which the wrong pseudo labels violate §1 §4.

Method

Dash is a wrapper around a FixMatch-style pipeline. FixMatch supplies the pseudo labels and the two losses. Dash changes only which unlabelled examples enter the gradient §4 §6.2.

Losses.

1. Supervised loss on labelled data: cross-entropy on the weakly augmented image §4, eq. 12.
2. Unsupervised loss for one unlabelled example: the pseudo label is the argmax of the prediction on the weakly augmented image §3.2, eq. 7; the loss is the cross-entropy between that label and the prediction on the strongly augmented image §3.2, eq. 9 §4, eq. 13.
3. Unlike FixMatch, the selection signal is this whole loss, which uses both views. FixMatch selects on the weak-view confidence alone §3.2, eq. 10 §4.

Warm-up. Run SGD on labelled data only for T_0 steps, starting from w_0, to get w_1 alg. 1 §4.

Estimate of the initial scale. In practice rho_hat is the mean cross-entropy of w_1 over the labelled set §4, eq. 17. The paper states that the analytic formula for rho_hat (eq. 16, also eq. 25 in the theorem) is for the analysis only §4 §5.

Threshold. rho_t = C * gamma^-(t-1) * rho_hat, with C > 1 and gamma > 1 §4, eq. 15 alg. 1.

Selection stage. For t = 1..T: draw n_t = m * gamma^(t-1) unlabelled examples alg. 1 §4; average the gradients of those with loss at most rho_t §4, eq. 18; take one SGD step with learning rate eta §4, eq. 20.

Alternative gradient. The paper also gives a form that adds a labelled gradient term to the same step, and says this is practical when N_l is small §4, eq. 19. The experiments use eq. 18 §6.2.

Equation numbers [eq. N] count numbered displays of the main text in TeX order. They were not checked against a compiled PDF; appendix equations are cited by appendix section.

# Dash  [alg. 1]
# Input:  labelled set, unlabelled set with FixMatch pseudo labels
# Output: weights after the selection stage

def dash(
    labelled,
    unlabelled,
    eta0,
    m0,
    T0,
    C,
    gamma,
    eta,
    m,
    T,
):
    # Warm-up: SGD on labelled data only, T_0 steps  [alg. 1] [§4]
    weights = initial_weights()
    for step in range(T0):
        batch = sample(labelled, m0)
        weights = weights - eta0 * mean_supervised_grad(weights, batch)
    # Estimate rho_hat from the mean labelled loss at w_1  [§4, eq. 17]
    rho_hat = mean_supervised_loss(weights, labelled)
    for t in range(1, T + 1):
        # Draw n_t = m * gamma^(t-1) unlabelled examples  [alg. 1]
        batch = sample(unlabelled, m * gamma ** (t - 1))
        # Threshold shrinks geometrically with t  [§4, eq. 15]
        rho_t = C * gamma ** (-(t - 1)) * rho_hat
        grad = truncated_gradient(weights, batch, rho_t)
        # Plain SGD step with the truncated gradient  [§4, eq. 20]
        weights = weights - eta * grad
    return weights

# Truncated gradient  [§4, eq. 18]
# Average the gradients of examples whose loss is at most rho_t
def truncated_gradient(weights, batch, rho_t):
    # Per-example selection loss  [§4, eq. 13]
    losses = [unsup_loss(weights, x) for x in batch]
    # Keep only examples at or below the threshold  [§4, eq. 13]
    kept = [x for x, loss in zip(batch, losses) if loss <= rho_t]
    # The paper does not define the case len(kept) == 0  [§4, eq. 18]
    total = sum(grad_unsup(weights, x) for x in kept)
    return total / len(kept)

# Unsupervised loss of one unlabelled example  [§3.2, eqs. 7, 9] [§4, eq. 13]
def unsup_loss(weights, x):
    # Hard pseudo label from the weakly augmented view  [§3.2, eq. 7]
    label = argmax(predict(weights, weak_augment(x)))
    # Cross-entropy against the strongly augmented view  [§3.2, eq. 9]
    probs = predict(weights, strong_augment(x))
    return cross_entropy(label, probs)

Experimental schedule §6.2. No selection in the first 10 epochs (threshold infinite). After that the threshold decays every 9 epochs, with gamma = 1.27 and C = 1.0001, and is floored at 0.05. The experiments predict soft labels, sharpened with temperature 0.5. Once the threshold reaches the floor, labels become one-hot.

Equivalence check §4. FixMatch's rule max(h_i) >= tau is the same as keeping examples whose weak-view loss -log(max(h_i)) is at most -log(tau). For tau = 0.95 this bound is about 0.0513.

Hyperparameters

Theory constants (Theorem 1) §5: T_0 = log(2 F(w_0)/a) / log(1/(1 - eta_0 mu)); m_0 = 4 G^2 / (delta mu a); m from eq. 24; rho_hat from eq. 25.

Results

Author-reported. Setup: image classification with the benchmarks CIFAR-10, CIFAR-100, SVHN and STL-10 §6; top-1 error, mean and standard deviation over 5 trials §6.3. Baseline numbers are taken from the FixMatch paper, and RYS from Ren et al. §6.3. Hardware is not stated.

CIFAR-10 and CIFAR-100 tab. 1 (top-1 error %, Wide ResNet-28-2 for CIFAR-10 and Wide ResNet-28-8 for CIFAR-100; mean ± std):

SVHN and STL-10 tab. 2 (top-1 error %, Wide ResNet-28-2 for SVHN and Wide ResNet-37-2 for STL-10; mean ± std):

Headline points, as stated by the paper §6.3:

• Dash has the best reported error on CIFAR-10, SVHN and STL-10 tab. 1 tab. 2.
• On CIFAR-100, Dash is comparable to ReMixMatch. ReMixMatch is better at 400 labels (44.28 vs 44.83 with CTA; 44.76 with RA). The authors attribute this to ReMixMatch's distribution alignment; with it, Dash reaches 43.31% at 400 labels, reported only in the text §6.3.
• Relative to FixMatch, the largest gains come at the smallest label counts §6.3.

Ablation: gamma tab. 3 (CIFAR-10, CTA only; top-1 error %):

The best value differs by label count (1.1 at 250, 1.2 at 4000). The paper says the main-run value 1.27 is not the best and that Dash is not very sensitive to gamma in a range §6.4.

Ablation: pseudo-labeling as pipeline tab. 4 (CIFAR-10, top-1 error %):

Both PL numbers are the baselines from tab. 1. No standard deviations are given §6.4.

Paper vs code

No official code.

Searched: the paper has no code link in its text or footnotes except https://github.com/google-research/fixmatch §6.2 fn., which is the upstream FixMatch codebase used as the pipeline, not Dash code. The raw arXiv metadata has no comments field. GitHub repository searches for "Dash semi-supervised", "dynamic thresholding", "fixmatch dynamic threshold" and "Dash" within the alibaba organisation returned no Dash implementation.

Pitfalls

• Selection signal differs from FixMatch. Dash selects on the loss of the strongly augmented view against the weakly derived label §4, eq. 13. FixMatch selects on weak-view confidence §3.2, eq. 10. Reusing FixMatch's selection code does not give Dash.
• Analytic rho_hat is not used. Eq. 16 (eq. 25 in the theorem) needs G, mu, a, a_0, b, theta, q and delta. None is estimated in the paper. Experiments use the labelled-loss mean instead §4, eq. 17. The paper gives no argument that this mean fits the theory.
• Time to reach the floor depends on rho_hat, which is not reported. From rho_t = C gamma^-(t-1) rho_hat and the 0.05 floor §6.2, the number of decays is about ln(rho_hat / 0.05) / ln(1.27). With rho_hat = 1, which is the scale in fig. 2 fig. 2, that is about 13 decays, roughly 117 epochs after the first decay. This is our arithmetic from the stated values.
• Empty selection is undefined. Eq. 18 divides by the number of kept examples §4, eq. 18. The paper does not say what happens when none passes the threshold. Guard against division by zero.
• Hard versus soft pseudo labels. Section 3.2 and eq. 13 use one-hot argmax labels §3.2, eq. 7 §4. The experiments use soft, temperature-sharpened labels until the floor, then one-hot labels §6.2. The paper does not say which label the selection loss uses while the labels are soft.
• Two gradient forms. The experiments use eq. 18 §6.2. Eq. 19 adds a labelled term, normalised by N_l plus the kept count §4, eq. 19. Eq. 19 is described as the practical form, but experiments name eq. 18.
• Algorithm schedule versus experiments. n_t = m gamma^(t-1) grows exponentially alg. 1. The experiments follow the FixMatch protocol with fixed batches §6.2. The paper does not map one schedule onto the other.
• Symbol gamma has two meanings. It is the threshold decay in the algorithm and experiments (1.27) §4, eq. 15 §6.2. The proof of Theorem 1 sets gamma = 1 / (1 - eta mu / 2) app. A. The paper does not show the theorem applies at gamma = 1.27.
• Theory is a simplified setting. The analysis assumes a loss in [0, 1] §5, although the experiments use cross-entropy, which is unbounded. It sets f_s = f_u = f, which drops the augmentations §5. It also assumes a bounded gradient (G), a PL condition (mu) and a Tsybakov-type condition on the second distribution, with constants b and theta that are not estimated §5, eq. 23.
• Proof bookkeeping is not fully checked. Lemma 1 holds with probability 1 - 5 delta, the induction uses 1 - (4t+1) delta, and Theorem 1 states 1 - (4T+1) delta app. A §5. The final step of the induction is asserted ("by the setting of rho_hat") and its algebra is not shown app. A.
• Ratios in the text do not match the table. The paragraph in §6.3 lists CIFAR-100, CIFAR-10 and SVHN, with error reductions of "19%, 10%, and 58%" for CTA and "4%, 8%, and 23%" for RA. From tab. 1 and tab. 2, the reductions are about 19.6% (CIFAR-10, 40 labels, CTA), 10.2% (CIFAR-100, 400, CTA) and 59% (SVHN, 40, CTA). For RA they are about 4.3% (CIFAR-10, 40), 8.4% (CIFAR-100, 400) and 23.5% (SVHN, 40). The percentages fit the order CIFAR-10, CIFAR-100, SVHN. These are our calculations from the tables.
• Several "best" claims are within one standard deviation. Example: CIFAR-10, 40 labels, CTA: Dash 9.16 ± 4.31 vs FixMatch 11.39 ± 3.35. SVHN, 40 labels, CTA: Dash 3.14 ± 1.60 vs FixMatch 7.65 ± 7.65 tab. 1 tab. 2. No significance test is reported §6.3.
• Baselines are copied, not rerun. Baseline numbers come from the FixMatch paper, and RYS from Ren et al. §6.3. The compute cost of Dash versus FixMatch (warm-up, extra loss evaluation) is not reported §4 §6.
• Ablations cover one setting. The gamma sweep uses CIFAR-10 with CTA only tab. 3 §6.4. The pseudo-labeling ablation covers two CIFAR-10 settings and has no standard deviations tab. 4.
• Distribution-alignment result is text-only. The 43.31% figure for Dash with distribution alignment on CIFAR-100 (400 labels) appears only in the text, with no standard deviation §6.3.
• STL-10 unlabelled data is out-of-distribution. The paper points to this as a case where Dash works well §6.1 §6.3. The 1000-label setting in tab. 2 is the table header; the text does not state the STL-10 label count separately.

Lineage

• Builds on: FixMatch (Sohn et al., 2020), used as the pipeline for pseudo labels and losses §3.2 §6.2. This paper's bibliography gives no arXiv id for it. Pseudo-labeling (Lee, 2013) also keeps pseudo labels above a confidence threshold §2.
• Compared against: MixMatch, UDA, ReMixMatch, FixMatch, Π-Model, Pseudo-Labeling, Mean Teacher and RYS (Ren et al., 2020, a bi-level weighting method) §6 tab. 1 tab. 2.
• Superseded by: not stated.