# Contrastive Learning Can Find An Optimal Basis For Approximately View-Invariant Functions

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

## Key facts

- Cited by 32 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 54 references that are in the map.
- First posted on arXiv 4 Oct 2022.

## Builds on (most cited first, 29 of 29)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Unsupervised Feature Learning via Non-Parametric Instance-level Discrimination](https://mlsanity.com/paper/1805.01978/) (2018)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Big Self-Supervised Models are Strong Semi-Supervised Learners](https://mlsanity.com/paper/2006.10029/) (2020)
- [Learning deep representations by mutual information estimation and maximization](https://mlsanity.com/paper/1808.06670/) (2018)
- [Temporal Ensembling for Semi-Supervised Learning](https://mlsanity.com/paper/1610.02242/) (2016)
- [VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning](https://mlsanity.com/paper/2105.04906/) (2021)
- [On Variational Bounds of Mutual Information](https://mlsanity.com/paper/1905.06922/) (2019)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization](https://mlsanity.com/paper/1606.00709/) (2016)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Regularization With Stochastic Transformations and Perturbations for Deep Semi-Supervised Learning](https://mlsanity.com/paper/1606.04586/) (2016)
- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Predicting What You Already Know Helps: Provable Self-Supervised Learning](https://mlsanity.com/paper/2008.01064/) (2020)
- [Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods](https://mlsanity.com/paper/2205.11508/) (2022)
- [Contrastive learning, multi-view redundancy, and linear models](https://mlsanity.com/paper/2008.10150/) (2020)
- [Understanding Contrastive Learning Requires Incorporating Inductive Biases](https://mlsanity.com/paper/2202.14037/) (2022)
- [Neural Kernels Without Tangents](https://mlsanity.com/paper/2003.02237/) (2020)
- [Spectral Inference Networks: Unifying Deep and Spectral Learning](https://mlsanity.com/paper/1806.02215/) (2018)
- [NeuralEF: Deconstructing Kernels by Deep Neural Networks](https://mlsanity.com/paper/2205.00165/) (2022)
- [Differentiable Compositional Kernel Learning for Gaussian Processes](https://mlsanity.com/paper/1806.04326/) (2018)
- [Training Neural Networks for Likelihood/Density Ratio Estimation](https://mlsanity.com/paper/1911.00405/) (2019)
- [Learning from Randomly Initialized Neural Network Features](https://mlsanity.com/paper/2202.06438/) (2022)
- [Streaming Kernel PCA with tildeO(√n) Random Features](https://mlsanity.com/paper/1808.00934/) (2018)
- [Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off](https://mlsanity.com/paper/1706.06296/) (2017)

## Built on by (most cited first, 30 of 32)

- [Know Your Self-supervised Learning: A Survey on Image-based Generative and Discriminative Training](https://mlsanity.com/paper/2305.13689/) (2023)
- [On the Stepwise Nature of Self-Supervised Learning](https://mlsanity.com/paper/2303.15438/) (2023)
- [Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression](https://mlsanity.com/paper/2306.00788/) (2023)
- [Rethinking Weak Supervision in Helping Contrastive Learning](https://mlsanity.com/paper/2306.04160/) (2023)
- [Neural Eigenfunctions Are Structured Representation Learners](https://mlsanity.com/paper/2210.12637/) (2022)
- [Spectral Representation Learning for Conditional Moment Models](https://mlsanity.com/paper/2210.16525/) (2022)
- [Non-Parametric Representation Learning with Kernels](https://mlsanity.com/paper/2309.02028/) (2023)
- [Bridging Mini-Batch and Asymptotic Analysis in Contrastive Learning: From InfoNCE to Kernel-Based Losses](https://mlsanity.com/paper/2405.18045/) (2024)
- [Towards Understanding the Mechanism of Contrastive Learning via Similarity Structure: A Theoretical Analysis](https://mlsanity.com/paper/2304.00395/) (2023)
- [The Galerkin method beats Graph-Based Approaches for Spectral Algorithms](https://mlsanity.com/paper/2306.00742/) (2023)
- [Understanding Self-Supervised Learning via Gaussian Mixture Models](https://mlsanity.com/paper/2411.03517/) (2024)
- [Complementary Benefits of Contrastive Learning and Self-Training Under Distribution Shift](https://mlsanity.com/paper/2312.03318/) (2023)
- [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)
- [Infinite Width Limits of Self Supervised Neural Networks](https://mlsanity.com/paper/2411.11176/) (2024)
- [PCA++: How Uniformity Induces Robustness to Background Noise in Contrastive Learning](https://mlsanity.com/paper/2511.12278/) (2025)
- [Representation Learning Dynamics of Self-Supervised Models](https://mlsanity.com/paper/2309.02011/) (2023)
- [Contextures: Representations from Contexts](https://mlsanity.com/paper/2505.01557/) (2025)
- [Spectal Harmonics: Bridging Spectral Embedding and Matrix Completion in Self-Supervised Learning](https://mlsanity.com/paper/2305.19818/) (2023)
- [Spectrally Transformed Kernel Regression](https://mlsanity.com/paper/2402.00645/) (2024)
- [Difficult Examples Hurt Unsupervised Contrastive Learning: A Theoretical Perspective](https://mlsanity.com/paper/2501.01317/) (2025)
- [Adversarial Dependence Minimization](https://mlsanity.com/paper/2502.03227/) (2025)
- [Contrastive Learning as Kernel Approximation](https://mlsanity.com/paper/2309.02651/) (2023)
- [On Linear Separation Capacity of Self-Supervised Representation Learning](https://mlsanity.com/paper/2310.19041/) (2023)
- [Visual Pre-Training on Unlabeled Images using Reinforcement Learning](https://mlsanity.com/paper/2506.11967/) (2025)
- [Theoretical Foundations of Representation Learning using Unlabeled Data: Statistics and Optimization](https://mlsanity.com/paper/2509.18997/) (2025)
- [The Impact of Semantic Pairs on Self-Supervised Representation Learning](https://mlsanity.com/paper/2510.08722/) (2025)
- [Eigenfunction Extraction for Ordered Representation Learning](https://mlsanity.com/paper/2510.24672/) (2025)
- [Radial Basis Function Networks as Projection Heads in Self-Supervised Learning](https://mlsanity.com/paper/2606.21590/) (2026)
- [Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization](https://mlsanity.com/paper/2607.07513/) (2026)

## Abstract (arXiv)

Contrastive learning is a powerful framework for learning self-supervised representations that generalize well to downstream supervised tasks. We show that multiple existing contrastive learning methods can be reinterpreted as learning kernel functions that approximate a fixed positive-pair kernel. We then prove that a simple representation obtained by combining this kernel with PCA provably minimizes the worst-case approximation error of linear predictors, under a straightforward assumption that positive pairs have similar labels. Our analysis is based on a decomposition of the target function in terms of the eigenfunctions of a positive-pair Markov chain, and a surprising equivalence between these eigenfunctions and the output of Kernel PCA. We give generalization bounds for downstream linear prediction using our Kernel PCA representation, and show empirically on a set of synthetic tasks that applying Kernel PCA to contrastive learning models can indeed approximately recover the Markov chain eigenfunctions, although the accuracy depends on the kernel parameterization as well as on the augmentation strength.