Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

Jul 16, 2026

A new theoretical analysis demonstrates that data augmentation in semi-supervised learning can achieve a fast O(1/n_L) error rate with respect to the number of labeled samples, improving over the standard supervised O(1/√n_L) rate. The bound explicitly connects error to the quality of augmentations, measured by the graph-cut mass of augmentations crossing label boundaries. This work provides a mechanistic explanation for how augmentation quality influences the trade-off between accuracy and label count.

Why it matters: This is the first theoretical result to explain the labeled-sample efficiency of self-supervised learning, offering insights that could help reduce annotation costs in practice.

Full story at: arXiv Statistical ML ↗