PaperlayerView exact revision on arXiv

Source-linked AI summary

Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data

Colin Wei, Kendrick Shen, Yining Chen, Tengyu Ma

arXiv:2010.03622v5cs.LGstat.ML

TL;DR

Self-training with deep networks succeeds empirically on unlabeled data, but its theory has largely lacked corresponding deep-network guarantees. This paper analyzes self-training across three settings under expansion and separation assumptions, proving high true-label accuracy and polynomial sample complexity while explaining input-consistency methods.

  • Problem

    Existing theoretical understanding of self-training with unlabeled data is limited, while prior analyses do not provide the paper’s unified deep-network treatment across three learning settings.

  • Method

    The paper analyzes population self-training and input-consistency objectives under an expansion assumption on class neighborhoods and a separation condition limiting cross-class overlap.

  • Results

    Under expansion and separation, the analyzed objectives achieve high accuracy on ground-truth labels, with polynomial sample complexity in model margin and Lipschitzness.

  • Takeaways & Limitations

    The analysis provides theoretical intuition for empirically successful self-training algorithms that use input consistency regularization on unlabeled data.

  • Takeaways & Limitations

    The pseudolabel analysis uses weaker expansion than the unsupervised-learning analysis, and its strongest accuracy guarantees do not require low input-consistency regularizer value for all classifiers.

Abstract

from arXiv · show

Self-training algorithms, which train a model to fit pseudolabels predicted by another previously-learned model, have been very successful for learning with unlabeled data using neural networks. However, the current theoretical understanding of self-training only applies to linear models. This work provides a unified theoretical analysis of self-training with deep networks for semi-supervised learning, unsupervised domain adaptation, and unsupervised learning. At the core of our analysis is a simple but realistic "expansion" assumption, which states that a low probability subset of the data must expand to a neighborhood with large probability relative to the subset. We also assume that neighborhoods of examples in different classes have minimal overlap. We prove that under these assumptions, the minimizers of population objectives based on self-training and input-consistency regularization will achieve high accuracy with respect to ground-truth labels. By using off-the-shelf generalization bounds, we immediately convert this result to sample complexity guarantees for neural nets that are polynomial in the margin and Lipschitzness. Our results help explain the empirical successes of recently proposed self-training algorithms which use input consistency regularization.

1 Introduction

The paper develops a unified deep-network theory of self-training across three unlabeled-data settings, using expansion and separation assumptions to explain high ground-truth accuracy and polynomial sample guarantees.

  • The paper addresses limited theoretical understanding of unlabeled-data methods, extending analysis beyond prior linear-model results to deep networks.
  • Self-training with input consistency regularization is studied for semi-supervised learning, unsupervised domain adaptation, and unsupervised learning.
  • Expansion requires each sufficiently small subset within a class to have a neighborhood with substantially larger probability mass, while separation limits cross-class neighborhood overlap.
  • Input consistency regularization promotes local prediction consistency, while expansion magnifies it into global consistency within each ground-truth class.
  • Self-training fits pseudolabels while enforcing input consistency, allowing correctly pseudolabeled regions to denoise incorrect pseudolabels under expansion and separation.
  • The analysis yields polynomial sample complexity guarantees for deep neural networks, with bounds that can be small when classes are separated by large margin.

2 Preliminaries and notations

The preliminaries define the unlabeled and source distributions, ground-truth class structure, learned classifiers, and pseudolabel objectives used in the analysis.

  • P denotes the unlabeled input distribution; domain adaptation additionally uses a labeled-source distribution Psrc and source classifier Gpl.
  • The data are partitioned into K ground-truth classes with disjoint class-conditional supports Pi, and G⋆ assigns each example its unique label.
  • The unlabeled training set contains n i.i.d. examples, while F is a scoring function and G assigns the argmax score, with lexicographic tie-breaking.
  • Pseudolabeling trains a fresh classifier to fit labels predicted by Gpl on unlabeled data, for example through cross-entropy loss.

3 Expansion property and guarantees for unsupervised learning

The paper defines population expansion and class separation assumptions that support unsupervised learning guarantees, then shows how parametric neural-network objectives convert these guarantees into finite-sample results. The analysis also covers richer distributions and explains why consistency regularization and stronger augmentation can improve class-aligned representations.

  • Expansion property: Expansion requires low-probability subsets within each class to have neighborhoods with proportionally larger probability, capturing connectivity in input space.The definition is population-based and is related to Cheeger and small-set expansion; it need not hold on empirical training samples.
  • Expansion property: The theory additionally assumes that ground-truth classes are separated with high probability under the transformation-based neighborhood model.The separation condition is expressed through a small population consistency loss for the ground-truth classifier, bounded by µ.
  • Expansion property: Mixtures of isotropic Gaussians satisfy concrete expansion and separation conditions, while the framework also extends to log-concave distributions and richer-than-Gaussian families.The Gaussian example gives (0.5, 1.5)-expansion and approximate separation under a suitable minimum mean distance; the analysis also includes mixtures of manifolds.
  • Expansion property: Population expansion can hold even when empirical examples are mutually distant, so nearest-neighbor clustering fails while the parametric method can recover mixture components with polynomial samples.The stated recovery error is O(1/poly(d)), and the required mean separation is nearly information-theoretically optimal in the example.
  • Population guarantees for unsupervised learning: For unsupervised learning, a consistent classifier predicting every class with decent probability aligns learned labels with ground-truth classes up to permutation.The objective uses only unlabeled data and leverages expansion and separation; the constraint compares predicted-class probabilities with input-consistency loss.
  • Finite sample guarantees for deep learning models: Off-the-shelf neural-network generalization bounds yield finite-sample guarantees polynomial in model margin and Lipschitzness, unlike prior nonparametric bounds exponential in dimension.The result applies when ground-truth classes are separable by a neural network with large robust margin.
  • Finite sample guarantees for deep learning models: Input consistency can explain empirically useful representations because expansion propagates local stability across classes, while stronger augmentation enlarges neighborhoods and improves the expansion factor.The regularizer also corresponds to consistency against adversarial examples within the paper’s framework.

4 Denoising pseudolabels for semi-supervised learning and domain adaptation

The paper analyzes pseudolabel-based self-training for semi-supervised learning and unsupervised domain adaptation under expansion and separation assumptions. Its objective combines input consistency with pseudolabel fitting, and its minimizers can denoise pseudolabels and attain high ground-truth accuracy.

  • Problem: The analysis considers unlabeled data with a pseudolabeler, where student classifiers must address potentially inaccurate pseudolabels that could otherwise be amplified.The framework applies to semi-supervised learning and unsupervised domain adaptation.
  • Assumptions: Assumption 4.1 requires expansion on sets smaller than the pseudolabeler’s maximum class-conditional error, with c > 3 accounting for worst-case pseudolabel mistakes.The assumption requires ā < 1/3 and defines c as min{1/ā, c̄}.
  • Objective: The population objective combines the input consistency regularizer RB(G) with L0-1(G, Gpl), the loss for fitting pseudolabels.This objective is related to recent successful semi-supervised learning algorithms.
  • Guarantee: Under expansion and separation, minimizing the objective yields a classifier that denoises pseudolabels and improves ground-truth accuracy.Lemma 4.2 bounds Err(G) by the objective value L(G), while Theorem 4.3 establishes the corresponding guarantee for minimizers.
  • Finite-sample scope: The finite-sample result follows by applying generalization bounds to Theorem 4.3.The paper notes that the domain-adaptation error bound has an additional dependence on Err(Gpl) because its expansion and consistency requirements are weaker.
  • Proof intuition: The proof uses expansion to enlarge a set of jointly mistaken examples into same-class neighbors that disagree with the pseudolabeler, producing a counting contradiction.In the zero-consistency case, N⋆(V) \ M(Gpl) is contained in the student’s disagreements with correctly pseudolabeled examples.

5 Experiments

The experiments provide empirical evidence for the paper’s denoising intuition and test components of the theoretical objective.

  • Empirical evidence: Figure 3 supports the intuition that self-training succeeds by denoising incorrectly pseudolabeled examples with correctly pseudolabeled neighbors.The experiments also include a GAN study described in Section D.1.
  • Ablations: Ablation studies show that components of the theoretical objective (4.1) improve performance.

6 Conclusion

The paper proposes expansion as a basis for analyzing self-training with deep networks and argues that the assumption is realistic, especially for vision datasets. It also identifies extending the assumptions to source-target alignment as future work.

  • Conclusion: The proposed expansion assumption enables a unified analysis of self-training for semi-supervised and unsupervised learning with deep neural networks.
  • Conclusion: The authors describe the expansion assumption as realistic for real-world datasets, particularly in vision.
  • Future work: Extending the assumptions to domain-adaptation methods based on aligning source and target domains remains an open question.

A.1 Relaxation of expansion assumption for pseudolabeling

The proof relaxes expansion to a class-restricted additive condition and shows that pseudolabel error on robust, jointly misclassified regions is bounded by q. Combining this with robustness and pseudolabel-fitting conditions yields a ground-truth error bound.

  • Definitions and setup: The analysis restricts neighborhoods to examples sharing the same ground-truth class and defines the robust set SB(G) using B-transformations.This class-restricted neighborhood supports the expansion argument, while SB(G) contains inputs whose predictions remain unchanged throughout their neighborhoods.
  • Definitions and setup: The relaxed assumption requires every subset of S with probability above q to expand by an additive amount α.The paper interprets this as sufficiently large neighborhoods for sufficiently large subsets.
  • Ground-truth error bound: Under additive expansion, pseudolabel fitting, and robustness, Theorem A.2 bounds Err(G) by 2(q + RB(G)) plus pseudolabel disagreement minus Err(Gpl).When pseudolabel error is at most Err(Gpl) and the theorem condition holds, the bound simplifies to Err(G) ≤ 2(q + RB(G)).
  • Bounding robust joint errors: If both G and Gpl err on a robust example, expansion produces a neighborhood where pseudolabel loss penalizes G, bounding the jointly erroneous robust region by q.The argument uses the set U of same-class neighbors outside M(Gpl), then combines expansion with the pseudolabel-loss constraint.

A.2 Proof of Theorem 4.3

This section converts the paper’s multiplicative expansion assumption into the additive form needed by Theorem A.2. The resulting class-conditional bounds are averaged across classes to obtain Lemma 4.2 and then Theorem 4.3.

  • Reduction to class-conditional bounds: The proof defines Mi(Gpl) as incorrectly pseudolabeled examples within ground-truth class i and reduces Theorem 4.3 to a class-conditional error bound.The reduction applies Theorem A.2 separately to each class before averaging.
  • Converting expansion assumptions: Lemma A.7 shows that Assumption 4.1 implies (q, α)-additive expansion on Mi(Gpl) for any β ∈ (0, c −1].The proof applies multiplicative expansion to subsets whose class-conditional probability exceeds βPi(Mi(Gpl)).
  • Final theorem implication: Theorem 4.3 follows because G⋆ has pseudolabel loss Err(Gpl) and robustness RB(G⋆) ≤ µ under Assumption 3.3.This connects the theorem’s ideal classifier to the pseudolabeler error and the assumed robustness parameter.
  • Class-conditional guarantee: Applying Theorem A.2 yields a class-conditional bound relating pseudolabel disagreement and robustness to (c −1)Erri(Gpl).The argument treats the cases for the class-conditional loss separately and then uses the resulting inequality.

B Proofs for unsupervised learning

The unsupervised-learning proofs convert multiplicative expansion into constant expansion and use robust predicted clusters to construct a permutation aligning predicted and ground-truth classes. They also address class overlap and illustrate expansion for Gaussian and transformed settings.

  • Expansion and alignment: The proof uses (q, ξ)-constant-expansion, requiring sufficiently large sets that do not contain more than half of any ground-truth class.This relaxed expansion notion is then connected to robust class alignment.
  • Expansion and alignment: A robust predicted cluster contains a majority of one ground-truth class, yielding a unique permutation π mapping predicted classes to ground-truth classes.Lemmas B.4 and B.5 establish existence and uniqueness of this class correspondence.
  • Accuracy from robustness: If robust error is below ξ, the permutation-misaligned region has probability at most max{q, RB(G)}.The proof shows that excessive misalignment would expand into additional robust points, contradicting RB(G) < ξ.
  • Accuracy from robustness: Multiplicative expansion implies constant expansion, which gives a small unsupervised error guarantee when the classifier satisfies the required robustness and class-mass conditions.The conversion is proved for c ≥ 2 and 1 ≤ c < 2, then applied through Lemma B.7 and Theorem 3.6.
  • Examples and overlap: Minimal class overlap can be handled by redefining ground-truth labels as the most likely labels and using truncated class-conditional distributions.The resulting analysis changes the bounds only by a small amount when overlap is minimal.
  • Examples and overlap: For Gaussian distributions, isoperimetry identifies halfspaces as the least-expanding sets, while separated regions provide the needed expansion and class separation.The paper also reduces the transformed-data example to the Gaussian case through the stated neighborhood relation.

C.1 End-to-end guarantees

The paper extends its population guarantees to finite training sets for unsupervised learning, semi-supervised learning, and unsupervised domain adaptation using neural-network generalization bounds.

  • Finite-sample scope: The finite-sample results cover unsupervised learning, semi-supervised learning, and unsupervised domain adaptation.The theorems use ˜O(·) for multiplicative factors that are poly-logarithmic in n and d.
  • Unsupervised learning: Theorem C.1 gives a high-probability population unsupervised-error guarantee for neural networks under the assumptions of Theorem 3.6 and Section 3.3.The network is parameterized as F(x) = Wpφ(···φ(W1x)···), and the guarantee holds with probability 1 − δ over the training sample.
  • Domain adaptation and semi-supervised learning: Theorem C.2 provides high-probability finite-sample guarantees for unsupervised domain adaptation and semi-supervised learning under Assumption 4.1.Its bound combines empirical pseudolabel-margin and input-robustness terms, with the remaining quantity described as a low-order term.

C.2 Proofs for Section 3.3

The proofs establish generalization guarantees for deep neural networks using all-layer margin analyses, covering standard and robust margins through covering-number and Rademacher-complexity arguments.

  • Generalization guarantees: Theorem C.3 gives a high-probability guarantee for neural-network classifiers defined by the argmax of multilayer network outputs.The result holds uniformly over networks in the specified class after drawing the training sample.
  • Function classes and complexity: The proof analyzes a fixed neural-network function class whose layers range over specified weight-matrix classes.The class is represented as F(x) = W_pφ(···φ(W_1x)···), with operator norms and covering numbers controlling complexity.
  • Margin-based proof strategy: The proof bounds robust all-layer-margin generalization through a modified ramp loss and Rademacher-complexity estimates.The ramp loss is composed with the robust margin, and Dudley’s theorem is used after constructing an L2(P_n)-cover.
  • Margin stability: A case analysis shows that the robust margin changes by at most the network-function distance when the predicted class differs between two networks.When predictions agree, an existing margin result applies; when they differ, both robust margins are bounded by the function distance.
  • Uniform bounds: The argument extends across margin thresholds by discretizing thresholds and applying a union bound, while analogous bounds cover other all-layer-margin variants.The resulting bounds include low-order and poly-logarithmic terms, with complexity depending on layer weight-matrix norms.
  • Margin lower bounds: Lower bounds for standard and robust all-layer margins are obtained when the activation has a Lipschitz derivative and the relevant classification margins are positive.The analysis reindexes activations as layers and uses norms of preceding-layer outputs in these bounds.

D.1 Empirical support for expansion property using GANs

The GAN experiment finds neighborhoods around mislabeled examples with substantial probability mass and tests whether VAT-based self-training denoises those examples.

  • Experimental setup: The experiment uses 128 by 128 BigGAN images grouped into 10 ImageNet-derived superclasses.Images are sampled uniformly within each superclass for the neighborhood and self-training experiments.
  • Neighbor construction: A projection objective combines image distance with negative classifier cross-entropy to find GAN-generated neighbors in the classifier’s mislabeled set.The optimization starts from the original image’s latent variable and produces a nearby generated image.
  • Empirical expansion: 20% of sampled images have a mislabeled-set neighbor within ℓ2 distance 19.765, corresponding to an average per-pixel change of 0.024.The resulting neighbors are reported to be visually similar to the original images.
  • Empirical expansion: The mislabeled set has probability 0.0626 while its neighborhood has probability 0.2, supporting the expansion assumption’s additive form.The neighborhood is induced by an ℓ2 radius of 19.765.
  • Self-training outcome: After VAT-based self-training on 10,000 additional unlabeled images per superclass, the new classifier reaches 95.69% validation accuracy.The same classifier supplies pseudolabels for the additional unlabeled data.
  • Denoising evidence: On the filtered subset c M′, the self-trained classifier achieves 67.27% accuracy, with higher accuracy for examples closer to their initializing neighbors.The filtering excludes cases where the original neighbor was already misclassified.

D.2 Pseudolabeling experiments

The pseudolabeling experiments incrementally add components of the theoretical objective and evaluate whether these additions improve self-training and denoising behavior.

  • Experimental design: The domain-adaptation experiments compare incremental objectives to demonstrate the effect of adding each theoretical component.The evaluated progression targets the ideal objective in equation (4.1).
  • Pseudolabeling baseline: PL trains a new classifier on target-domain pseudolabels produced by a source-trained classifier.The source model is trained on labeled source data before generating target pseudolabels.
  • Input consistency: PL+VAT fits pseudolabels while regularizing adversarial input robustness with a VAT loss on the target domain.The perturbation set is modeled as an ℓ2 ball around each input.
  • Robust all-layer margin: PL+VAT+AMO applies adversarial perturbations to hidden layers to regularize the robust all-layer margin and encourage training-set robustness to generalize.AMO is added because the theoretical guarantees concern the population loss.
  • Pseudolabel handling: PL+VAT+AMO+MinEnt allows the classifier to ignore a fraction of pseudolabels and applies min-entropy loss to those examples.This is intended to encourage robustness even where predictions do not match the pseudolabeler.
  • Results and scope: Table 1 reports validation accuracy on six unsupervised domain-adaptation benchmarks, with performance improving as theoretical-objective components are added.The experiments are intended to validate the theory rather than achieve state-of-the-art benchmark results.
Loading 2010.03622v5…