The bound makes augmentation quality explicit and gives a mechanistic account of the accuracy-versus-label-count curve through augmentation quality, verified in a controlled model where the constants are known.
Abstract
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 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.
Self-supervised learning relies on so-called data augmentations $\phi(x)$ of unlabeled datapoints $x$ --- for example, masking random pixels in an image $x$ --- that should leave the label of $x$ invariant and are often used to learn a lower-complexity invariant subspace $\cal V$ for downstream tasks. In practice, such augmentations $\{ \phi_l(x_i) \}$ are pooled together to learn $\cal V$, despite obvious inter-dependencies between different augmentations $\phi_l(x), \phi_k(x)$ of the same datapoint $x$. However, theoretical works on the subject typically consider procedures that avoid such dependencies, and are therefore limited to operate on smaller subsets of independent data. We show in this work that pooling augmentations together, despite inter-dependencies, is a better alternative than the baseline of partitioning the data into subsets of independent data. More precisely, in the context of estimating $\cal V$, the statistical estimation error bounds for pooling are never worse than the partitioning baseline, and in some cases --- such as masking or noise injection-based augmentations over a shallow neural network --- naive pooling leads to faster rates in terms of the number of augmentations. The benefits of pooling are particularly prominent when the correlations between different augmentations $\phi_l(x), \phi_k(x)$ have mild effects on estimation or help decrease the estimation variance. The analysis, therefore, yields new insights into the success of pooling augmented samples in self-supervised pre-training, and provides an intuition behind the practical preference towards using many augmentations.
Maximilian Fleissner, Debarghya Ghoshdastidar, Samory Kpotufe· 0 citations
C-Score, a compact framework that evaluates training behavior in three complementary spaces: prediction, feature representation, and optimization, suggests that clean accuracy alone is insufficient for evaluating SSL robustness in open-world environments, and that internal diagnostic signals are necessary for more reliable robustness assessment under unlabeled contamination.
Tsao-Lun Chen, Chicheng Fu, Han-Yi Chou et al.· 0 citations
Conditional diffusion models have become a powerful and flexible framework for learning complex conditional distributions from labeled data. In practice, however, acquiring high-quality labels is costly and time-consuming, leaving large volumes of unlabeled data unused. To address this, we introduce label-augmented conditional diffusion (LACD), a simple and effective approach that incorporates unlabeled examples by assigning them a designated trivial label and performing joint denoising score matching over the augmented dataset. We provide sufficient conditions guaranteeing population-level identifiability of the target conditional distribution under this scheme. Moreover, we establish rigorous statistical guarantees: when sufficiently many unlabeled samples are available, the sampling distribution produced by LACD converges strictly faster than the purely supervised estimator in total variation distance, and at least as fast in Wasserstein-1 distance. Extensive experiments on synthetic, image, and tabular benchmarks corroborate our theory and show substantial gains in sample efficiency and generative performance compared with the purely supervised estimator.
Jin Su, Yuan Gao, Yong Zhou et al.· arXiv.org· 0 citations
Semi-supervised learning (SSL) aims to effectively utilize a small amount of labeled data together with a large volume of unlabeled data to improve learning performance. Among various SSL strategies, label propagation has been widely adopted due to its ability to diffuse label information across data points via graph structures. However, most existing label propagation-based SSL methods struggle with high-dimension-low-sample-size (HDLSS) data, as they rely on pairwise similarity measures that fail to capture the complex relationships among samples in such settings. To overcome this limitation, we propose a novel deep SSL framework that enhances label propagation using tensor-based similarity, enabling the modeling of high-order relationships among multiple samples. Specifically, we first pretrain a feature extraction network using the labeled data to obtain initial feature representations. Subsequently, tensor label propagation and fine-tuning of the feature extraction network are conducted iteratively. In the tensor label propagation module, pseudo-labels for the unlabeled samples are estimated more accurately by leveraging high-order similarity. These pseudo-labels, along with the original labeled data, are then used to fine-tune the pretrained network, resulting in more robust and discriminative feature representations across all samples. By embedding high-order structural information into the SSL pipeline, our method significantly enhances the prediction performance from limited labeled data in the HDLSS setting. Extensive experiments on multiple HDLSS datasets demonstrate the superiority of our approach compared to recent baselines.
Hongmin Cai, Jiali Sun, Fei Qi et al.· IEEE Transactions on Neural...· 0 citations
A novel PML method, namely Wasserstein Partial Multi-Label Learning with dual Label Correlation Perspectives (Wpml3cp), solved by the gradient descent with an augmented Lagrange multiplier technique, and empirical results demonstrate that Wpml3cp and Wpml3cp-D can outperform the PML baselines in various noisy levels.
Ximing Li, Yuanchao Dai, Bing Wang et al.· ACM Transactions on Knowledg...· 0 citations
Data augmentation plays a central role in self-supervised learning, as the quality and diversity of augmented views strongly influence the learned representations. However, most existing self-supervised methods rely on fixed stochastic augmentation pipelines, while more adaptive alternatives often require expensive policy search, adversarial training, or additional optimization procedures. In this paper, we propose a lightweight learnable augmentation framework based on Extreme Learning Machines (ELM) for self-supervised visual representation learning. The proposed module predicts image-dependent transformation parameters and applies them through a differentiable augmentation operator, enabling joint optimization with the representation model while introducing minimal additional computational overhead. The framework is integrated into three representative self-supervised learning methods: SimCLR, BYOL, and SimSiam. Extensive experiments on CIFAR-10, CIFAR-100, and Tiny ImageNet show that the proposed method consistently improves linear evaluation performance relative to reproduced baselines across most settings. In particular, the method yields notable gains on CIFAR datasets and remains effective on the more challenging Tiny ImageNet benchmark. A per-class difficulty analysis further shows that the proposed augmentation strategy substantially improves performance on hard classes, indicating stronger robustness to challenging categories while maintaining competitive overall performance. In general, the results demonstrate that lightweight learnable augmentation can effectively enhance self-supervised representation learning across different frameworks and datasets.
