# Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 74 of its 118 references that are in the map.
- First posted on arXiv 1 Jun 2023.

## Builds on (most cited first, 30 of 74)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Barlow Twins: Self-Supervised Learning via Redundancy Reduction](https://mlsanity.com/paper/2103.03230/) (2021)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Improved Regularization of Convolutional Neural Networks with Cutout](https://mlsanity.com/paper/1708.04552/) (2017)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [What Makes for Good Views for Contrastive Learning?](https://mlsanity.com/paper/2005.10243/) (2020)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Implicit Regularization in Deep Matrix Factorization](https://mlsanity.com/paper/1905.13655/) (2019)

## Built on by (most cited first, 20 of 20)

- [InfoNCE: Identifying the Gap Between Theory and Practice](https://mlsanity.com/paper/2407.00143/) (2024)
- [Tracing the Representation Geometry of Language Models from Pretraining to Post-training](https://mlsanity.com/paper/2509.23024/) (2025)
- [Non-Parametric Representation Learning with Kernels](https://mlsanity.com/paper/2309.02028/) (2023)
- [Weighted Point Set Embedding for Multimodal Contrastive Learning Toward Optimal Similarity Metric](https://mlsanity.com/paper/2404.19228/) (2024)
- [Understanding Self-Supervised Learning via Gaussian Mixture Models](https://mlsanity.com/paper/2411.03517/) (2024)
- [Provable Benefits of Unsupervised Pre-training and Transfer Learning via Single-Index Models](https://mlsanity.com/paper/2502.16849/) (2025)
- [Harnessing small projectors and multiple views for efficient vision pretraining](https://mlsanity.com/paper/2312.10725/) (2023)
- [A Theoretical Characterization of Optimal Data Augmentations in Self-Supervised Learning](https://mlsanity.com/paper/2411.01767/) (2024)
- [Disentanglement of Variations with Multimodal Generative Modeling](https://mlsanity.com/paper/2509.23548/) (2025)
- [Representation Learning Dynamics of Self-Supervised Models](https://mlsanity.com/paper/2309.02011/) (2023)
- [Enhancing the Resilience of Graph Neural Networks to Topological Perturbations in Sparse Graphs](https://mlsanity.com/paper/2406.03097/) (2024)
- [Contextures: Representations from Contexts](https://mlsanity.com/paper/2505.01557/) (2025)
- [Spectrally Transformed Kernel Regression](https://mlsanity.com/paper/2402.00645/) (2024)
- [Adversarial Dependence Minimization](https://mlsanity.com/paper/2502.03227/) (2025)
- [AudioMosaic: Contrastive Masked Audio Representation Learning](https://mlsanity.com/paper/2605.14231/) (2026)
- [Why all roads don't lead to Rome: Representation geometry varies across the human visual cortical hierarchy](https://mlsanity.com/paper/2509.13459/) (2025)
- [Beyond Augmentation: Leveraging Inter-Instance Relation in Self-Supervised Representation Learning](https://mlsanity.com/paper/2510.22322/) (2025)
- [Eigenfunction Extraction for Ordered Representation Learning](https://mlsanity.com/paper/2510.24672/) (2025)
- [Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization](https://mlsanity.com/paper/2607.07513/) (2026)
- [An Analysis of Self-supervised Pre-training with Dependent Samples](https://mlsanity.com/paper/2609.05031/) (2026)

## Abstract (arXiv)

Data augmentation is critical to the empirical success of modern self-supervised representation learning, such as contrastive learning and masked language modeling. However, a theoretical understanding of the exact role of augmentation remains limited. Recent work has built the connection between self-supervised learning and the approximation of the top eigenspace of a graph Laplacian operator, suggesting that learning a linear probe atop such representation can be connected to RKHS regression. Building on this insight, this work delves into a statistical analysis of augmentation-based pretraining. Starting from the isometry property, a geometric characterization of the target function given by the augmentation, we disentangle the effects of the model and the augmentation, and prove two generalization bounds that are free of model complexity. Our first bound works for an arbitrary encoder, where the prediction error is decomposed as the sum of an estimation error incurred by fitting a linear probe with RKHS regression, and an approximation error entailed by RKHS approximation. Our second bound specifically addresses the case where the encoder is near-optimal, that is it approximates the top-d eigenspace of the RKHS induced by the augmentation. A key ingredient in our analysis is the augmentation complexity, which we use to quantitatively compare different augmentations and analyze their impact on downstream performance.