Research map / Learning theory and algorithms / Kernels and regression theory

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

ICLR 2024 · Learning theory and algorithms › Kernels and regression theory · approach: Statistical perspectives on generalization · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Builds an RKHS approximation/regression framework for augmentation-based self-supervised learning, deriving model-free generalization bounds governed by an augmentation complexity and a trace gap.

Problem

Theoretical understanding of the exact role of data augmentation in self-supervised representation learning, separated from encoder model complexity, since prior generalization bounds depend on encoder function class complexity.

Approach

Shows that augmention-"soft invariant" target functions lie in an augmentation-induced RKHS; pretraining is viewed as approximating this RKHS's top-d eigenspace and downstream linear probing as RKHS regression. Derives nonparametric bounds for arbitrary encoders via the trace gap and augmentation complexity (sup norm of the kernel), with no model complexity term.

Key results

• Augmentation complexity for random masking on the hypercube is bt_r^2 = (2-alpha)^{d_X}, with block masking giving a smaller bound.
• On QNLI the highest test accuracy is at mask rate 0.15 and on SST-2 at 0.40, with a sweet spot between too-weak and too-strong augmentation.
• The second bound shows the trace gap for the empirical top-d eigenspace converges at O(N^{-1/2}) to lambda_{d+1}.

Measured effects reported in the paper

Surprising findings

• Strong augmentation shrinks the generalization gap but overly strong augmentation (SST-2 above 0.40 mask rate) hurts training accuracy and can break the assumption.

Limitations

• Augmentation complexity can grow exponentially with input dimension in the worst case.
• Analysis covers only the average encoder, not the original encoder applied directly downstream.
• Requires full access to p(a|x) and assumes the target function lies in the augmentation-induced RKHS.

Experimental setup

Datasets: wikipedia-simple QNLI SST-2

Benchmarks: QNLI SST-2

Metrics: test accuracy train-test accuracy gap augmentation complexity (log of K_X 99th percentile)

Baselines: spectral contrastive loss bounds (HaoChen et al. 2021)

Builds on: spectral contrastive learning augmentation graph theory (HaoChen et al.) kernel PCA

Closest papers by meaning

• An Augmentation-Aware Theory for Self-Supervised Contrastive Learning (ICML 2025 · similarity 0.88)
• Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style (NeurIPS 2021 · similarity 0.87)
• You Don’t Need Domain-Specific Data Augmentations When Scaling Self-Supervised Learning (NeurIPS 2024 · similarity 0.86)
• Data Augmentation with Diffusion for Open-Set Semi-Supervised Learning (NeurIPS 2024 · similarity 0.86)
• Self-supervised Representation Learning from Random Data Projectors (ICLR 2024 · similarity 0.85)
• A Statistical Theory of Contrastive Learning via Approximate Sufficient Statistics (NeurIPS 2025 · similarity 0.85)