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

arXiv: https://arxiv.org/abs/2607.07513 · HTML: https://mlsanity.com/paper/2607.07513/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 33 references that are in the map.
- First posted on arXiv 8 Jul 2026.

## Builds on (most cited first, 23 of 23)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Big Self-Supervised Models are Strong Semi-Supervised Learners](https://mlsanity.com/paper/2006.10029/) (2020)
- [Data-Efficient Image Recognition with Contrastive Predictive Coding](https://mlsanity.com/paper/1905.09272/) (2019)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap](https://mlsanity.com/paper/2203.13457/) (2022)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Contrastive Learning Can Find An Optimal Basis For Approximately View-Invariant Functions](https://mlsanity.com/paper/2210.01883/) (2022)
- [Sample Efficiency of Data Augmentation Consistency Regularization](https://mlsanity.com/paper/2202.12230/) (2022)
- [Generalization Analysis for Contrastive Representation Learning](https://mlsanity.com/paper/2302.12383/) (2023)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Semi-Supervised Learning: the Case When Unlabeled Data is Equally Useful](https://mlsanity.com/paper/2005.11018/) (2020)
- [Label Propagation with Weak Supervision](https://mlsanity.com/paper/2210.03594/) (2022)
- [Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering](https://mlsanity.com/paper/2307.11030/) (2023)
- [Can semi-supervised learning use all the data effectively? A lower bound perspective](https://mlsanity.com/paper/2311.18557/) (2023)
- [Harnessing small projectors and multiple views for efficient vision pretraining](https://mlsanity.com/paper/2312.10725/) (2023)
- [Contextures: Representations from Contexts](https://mlsanity.com/paper/2505.01557/) (2025)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [How does Labeling Error Impact Contrastive Learning? A Perspective from Data Dimensionality Reduction](https://mlsanity.com/paper/2507.11161/) (2025)

## Abstract (arXiv)

Self-supervised learning matches supervised accuracy from a fraction of the labels, but the labeled-sample efficiency behind this has lacked a theoretical explanation. We provide one. Data augmentation induces a similarity graph on the unlabeled data, so downstream learning on that graph is graph-Laplacian-regularized learning. We prove a fast transductive rate, O(1/nL) in the number of labels, in place of the supervised O(1/√nL), by carrying the leave-one-out stability apparatus of Johnson and Zhang (JMLR 2007) over to the augmentation graph, and without the unrealistic assumptions of limit-based analyses (exact kernel, generalizing features). The bound makes augmentation quality explicit: the expected error is at most C/nL + RDA(y), where the data-augmentation alignment error RDA(y) is proportional to the graph-cut mass of augmentations that cross a label boundary, so good augmentations let few labels suffice. The analysis uses a streamlined loss that drops the projector, negative-sample, and orthogonality overhead of standard objectives yet still recovers the top-K ideal features in the infinite-data limit, the augmentation-kernel eigenspace studied by Zhai et al. The bound gives a mechanistic account of the accuracy-versus-label-count curve through augmentation quality, verified in a controlled model where the constants are known.