Abstract
Self-training and consistency regularization have become cornerstones of modern semi-supervised learning and domain adaptation, yet their theoretical foundations for deep neural networks have remained elusive. This work introduces a unified framework based on a realistic "expansion" assumption—where data points within a class are well-connected via local neighborhoods. We demonstrate that under this assumption, self-training effectively denoises incorrect pseudolabels, achieving high accuracy with polynomial sample complexity and avoiding the curse of dimensionality.
Introduction
Self-training, the process of training a model on its own predictions (pseudolabels), has driven significant empirical breakthroughs in machine learning, exemplified by methods like FixMatch and Noisy Student. However, theoretical understanding has largely been confined to simple linear models or required an exponential amount of data relative to the input dimension. The fundamental question remains: how does a model trained on its own potentially erroneous guesses improve rather than reinforce its mistakes? This paper bridges the gap by analyzing how deep networks exploit the underlying geometric structure of unlabeled data.
Theoretical Framework: Expansion and Separation
The authors propose two key assumptions to model the geometry of data distributions:
- Expansion Assumption: Any small subset of a class must have a "neighborhood"—points reachable via data augmentation or small perturbations—that is significantly larger than the subset itself. This implies that the manifold of a class is well-connected.
- Separation Assumption: The neighborhoods of examples from different classes must have minimal overlap, ensuring the model can distinguish between them.
By combining pseudolabel fitting with input consistency regularization (forcing identical predictions for a point and its neighbors), the authors show that local consistency + expansion = global consistency. The expansion property "magnifies" local consistency across the entire class manifold, allowing the majority of correctly labeled examples to eventually "denoise" the minority of incorrect ones.
Key Insights
Self-Training as Denoising
The theory reframes self-training as a denoising process. Due to expansion, the "mass" of correctly labeled neighbors typically outweighs the "mass" of incorrectly labeled points. This allows the optimizer to converge toward a solution aligned with the ground truth.
Polynomial Sample Complexity
By utilizing "all-layer margin" generalization bounds, the authors prove that neural networks require only a polynomial number of samples relative to the margin and Lipschitzness. This explains why these methods succeed in high-dimensional spaces where traditional non-parametric methods often fail.
The Role of Augmentation
The framework provides a theoretical justification for aggressive data augmentation. Augmentation increases the size of the neighborhood $\mathcal{N}(x)$, which directly improves the expansion factor $c$, leading to tighter accuracy bounds and more robust learning.
Empirical Validation
The paper validates these concepts through both synthetic experiments and standard benchmarks:
- Expansion in Real Data: Using BigGAN to generate high-dimensional image manifolds, the authors verified that the expansion property holds for real-world data like ImageNet. They found that 20% of mislabeled images had a correctly labeled neighbor within a very small $L_2$ distance.
- Domain Adaptation: On Unsupervised Domain Adaptation (UDA) tasks, incorporating the theoretically-inspired AMO algorithm (regularizing all-layer margins) consistently improved performance. For instance, on the STL-10 to CIFAR-10 task, accuracy rose from 58.7% (source only) to 67.0% with the full objective.
Limitations and Future Work
While providing a significant step forward, the theory currently assumes class distributions have disjoint support, which may not hold for ambiguous real-world images. Additionally, the analysis focuses on the global minimizer of the population objective; the specific optimization trajectory of Stochastic Gradient Descent (SGD) remains an open area for research. Future work could also integrate explicit domain alignment techniques often used alongside self-training.
Summary updated