Augmentation Alone Leads to Generalization

Abstract

We study self-supervised representation learning with data augmentation, such as contrastive learning and masked image/language modeling. Our main result is that a sufficiently good data augmentation technique alone can lead to good generalization, for which we prove generalization bounds for an arbitrary encoder with a model-free analysis. Our results model the upstream stage as RKHS approximation and the downstream stage as RKHS regression, where the RKHS is fully determined by the augmentation. We identify augmentation complexity as a key ingredient that replaces the model complexity and additionally use it to quantitatively analyze augmentations on real datasets.