Search papers, labs, and topics across Lattice.
This paper establishes a theoretical foundation for the efficiency of semi-supervised learning through data augmentation by demonstrating that it can achieve a fast transductive rate of \(O(1/n_L)\) in labeled samples, compared to the traditional \(O(1/\sqrt{n_L})\) in supervised learning. The authors leverage a similarity graph induced by data augmentation to facilitate graph-Laplacian-regularized learning, while also addressing the limitations of previous analyses that relied on unrealistic assumptions. Their findings reveal that the quality of data augmentations directly influences the number of labels needed for effective learning, providing a clearer understanding of the accuracy-label count relationship in semi-supervised settings.
Fast transductive rates in semi-supervised learning can be achieved with fewer labels than previously thought, thanks to the power of data augmentation.
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/n_L)$ in the number of labels, in place of the supervised $O(1/\sqrt{n_L})$, 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/n_L + R_{\mathrm{DA}}(y)$, where the data-augmentation alignment error $R_{\mathrm{DA}}(y)$ is 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 result explains the observed accuracy-versus-label-count curve rather than only bounding a generalization gap.
Mila