Contrastive Learning Can Find An Optimal Basis For Approximately View-Invariant Functions
Authors: Daniel D. Johnson
Ayoub El Hanchi
Chris J. Maddison
Venue: ICLR 2023 poster (2023)
Keywords: contrastive learning
self-supervised learning
representation learning
kernel
kernel PCA
positive definite
eigenfunction
spectral clustering
invariance
Markov chain
minimax optimal

Abstract: 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 reinterpeted 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.

Published as a conference paper at ICLR 2023
CONTRASTIVE LEARNING CAN FIND AN OPTIMAL BASIS FOR APPROXIMATELY VIEW-INVARIANT FUNCTIONS
Daniel D. Johnson 1.2 Ayoub El Hanchi', Chris J. Maddison University of Toronto, GGoggle Research (ddjohnson, ae han, cmaddi s @cs. mess.toronto.ed
ABSTRACT
Contrastive learning is a powerful framework for learning self-supervised represen- tations that generalize well to downstream supervised tasks. We show that multiple existing contrastive learning methods can be reinterpreted learning kernel func- tions that approximate a fixed positive-pair kernel. We then prove that 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 based on de- composition of the target function in terms of the eigenfunctions of positive-paii 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 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 well the augmentation strength.
INTRODUCTION
When using a contrastive learning method such as SimCLR (Chen et al., 2020a) for representation learning, the first step is to specify the distribution of original examples p(2) within some space 2 along with a sampler of augmented views p( ( Z = z) over a potentially different space A. For example, p(Z) might represent dataset of natural images, and p(A[Z) random transformation that applies random scaling and color shifts. Contrastive learning then consists finding a parameterized mapping (such neural network) which maps multiple views of the same image (e.g. draws from ~ (Al = z) for a fixed z) close together, and unrelated views far apart. This mapping can then be used define a representation which is useful for downstream supervised learning.
The success of these representations have led to a variety of theoretical analyses of contrastive learning, including analyses based on conditional independence within latent classes (Saunshi et al.) 2019), alignment of hyperspherical embeddings (Wang & Isola 2020), conditional independence structure with landmark embeddings (Tosh et al.) 2021), and spectral analysis of an augmentation graph (HaoChen et al. 2)22). Each of these analyses is based on a single choice of contrastive learning objective. In this work, we go further by integrating multiple popular contrastive learning methods into a single framework, and showing that it can be used to build minimax-oplimal representations under a straightforward assumption about similarity of labels between positive pairs.
Common wisdom for choosing the augmentation distribution p( (A|Z) is that it should remove irrele- vant information from Z while preserving information necessary to predict the eventual downstream label Y; for instance, augmentations might be chosen to be random crops or color shifts that affect the semantic content of an image as little as possible (Chen et al.) 2020a). The goal of representation learning then to find a representation with which we can form good estimates of Y using only few labeled examples. In particular, we focus on approximating a target function g : A ++ Rn for which g(a) represents the "best guess" of Y based on a. For regression tasks, we might be interested in a
We focus finite but arbitrarily large Z and A, e.g. the set of 8-bit 32x32 images, and allow 2 # A.

---

Published as a conference paper at ICLR 2023
target function of the form g(a) = E| al. For classification tasks, if Y is represented as one- hot vector, we might be interested in estimating the probability of each class, again taking the form g(a) A al, the most likely label, taking the form g(a) argmax,, p(Y y a). In either case, we are interested in constructing representation for which can be estimated well using only small number of labeled augmentations (a, vt) Since usually do not have access the downstream supervised learning task when learning our representation, our goal is to identify a representation that enables us to approximate many different "reasonable" choices of g. Specifically, we focus on finding single representation which allows us to approximate every target function with a small positive-pun pair discrepancy, i.e. every g satisfying the following assumption:
Assumption 1.1 (Approximate fiew-Invariances Each target function g : A R satisfies
(a) | ( - 9(a2)) S,
for some fixed e E o0), where p+ 02) E, ((01)2))((app1))
This is a fairly weak assumption, because to the extent that the distribution of augmentations preserves information about some downstream label, our best estimate of that label should not depend much on exactly which augmentation is sampled: it should be approximately invariant to the choice of a different augmented view of the same example. More precisely, as long as the label Y is independent of the augmentation A conditioned on the original example Z (i.e. assuming augmentations are chosen without using the label, as is typically the case), we must have g: g:A- (((((A)) - {(A)))² < 2E (e(A)- Y (see Appendix A). For simplicity, we work with scalar and Y I;; vector-valued Y can be handled by learning a sequence of scalar functions.
Our first contribution is to unify number of previous analyses and existing techniques, drawing connections between contrastive learning, kernel decomposition, Markov chains, and Assumption 1.1 We start by showing that minimizing existing contrastive losses is equivalent to building an approximation of a particular positive-pair kernel, from which a finiteddimensionll representation can be extracted using Kernel PCA (Schölkopf al., 1997). We next discuss what properties representation must have to achieve low approximation error for functions satisfying Assumption [.I and show that the eigenfunctions of Markov chain over positive pairs allow us to re-express this assumption in a form that makes those properties explicit. We then prove that, surprisingly, building Kernel PCA representation using the positive-pair kernel is exactly equivalent to identifying the eigenfunctions of this Markov chain, ensuring this representation has the desired properties.
Our main theoretical result is that contrastive learning methods can be used to find a minimax- optimal representation for linear predictors under Assumption 1.1 Specifically, for fixed dimension, we show that taking the eigenfunctions with the largest eigenvalues yields basis for the linear subspace of functions that minimizes the worst case quadratic approximation error across the set of functions satisfying Assumption 1.I and further give generalization bounds for the performance of this representation for downstream supervised learning.
We conclude by studying the behavior of contrastive learning models on two synthetic tasks for which the exact positive-pair kernel is known, and investigating the extent to which the basis of eigenfunctions can be extracted from trained models. As predicted by our theory, we find that the same eigenfunctions can be recovered from multiple model parameterizations and losses, although the accuracy depends on both kernel parameterization expressiveness and augmentation strength.
2 CONTRASTIVE LEARNING Is SECRETLY KERNEL LEARNING
Standard contrastive learning approaches can generally be decomposed into two pieces: a param- eterized model that takes two augmented views and assigns them real-valued similarity, and contrastive loss function that encourages the model to assign higher similarity to positive pairs than negative pairs. In particular, the InfoNCE/ / NT-XEnt objective proposed by Van den Oord et al.) (2018) and [Cee et al. (020a)) and used with the SimCLR architecture, the NT-Logistic objective also considered by Chen et al. (2020a) and theoretically analyzed by Tosh al. (202I) and the Spectral Contrastive Loss introduced by HaoChen et al. (2021) all have this structure.
II we have dataset of labeled un-augmented examples (zi, y1), we can build a dataset of labeled augmenta- tions by sampling one or more augmentations of each example in our original dataset.
2

---

Published as a conference paper at ICLR 2023
Postive-Piir Kemel (ground truth)
Roiat o1)
NT-XEnt
Loss
log
Retuf u21+ Kalutar)
(Chen et al.
2020at Van den
Kernel
Ko(a1, exp(ho((x)) J Tolaa)ir) a2(().02)
Oord al. 2018
Minimum
p-luina) Cjuil plac)plas)
K-(
K
logotlog Rolat az))
High similarity
Low similarity
NT-Logistic
Loss
(Chen et al. 2020a Tosh 2021
+ +B log ol (- log Rotai .annnaa5)))
Paramneeerized Kernel (leared)
Kernel
Rolai. = (xp())((1)) a.(a),a))
holoaa))) ho(a2)/r)
Minimum
p_luine)
play)p(a))
Spectral HaoChen et
Loss
E 2Rolat at)
+ E (RolaT
R
K
Kernel
R Ralaj 02) (a(a:) "T( hha(oa)
2021
Minimum
R.(a). =
P- (u)
High similariy
Low similarity
p(a1)a(A2)
The positive-paii pair ker- nel K_ assigns high similarity to likely positive pairs. Contrastive learning methods learn parame- terized kernels Ka which assign high similarity to nearby points in learned embedding space.
Figure 1:
Table I: Existing contrastive learning objectives, reinterpreted as learning parameterized approximations of K "Minimum" de- notes the population minimum of the loss over all kernel functions (not necessarily representable using the shown parameterization). Cla,] a weaaadenee--la--epeeeeeeee
proportionality constant, with C/a1] Clas whenever p+ (01, u2) O. See Appendix B for derivations and discussion of other related objectives.
The similarity between the two augmented views commonly taken to be the dot product of outputs of neural network, e.g. (a1))) ) ha (a2). However, a surprising pattern emerges if we instead interpret the exponentiated dot product cxp(hg hi (a2)))/T] (T) as the similarity for the NT-XEnt and NT--Loistiic objectives, treating the exponential and temperature term as part of the model instead of part of the objective. As shown in Table the three losses now share the same population minimum: the probability ratio p+ (ai, a2)/p(a) )p(a2).
Intriguingly, the expressions (a))) (ho))) and ( both satisfy the definition of Mercer kernel (also called a positive-defintee kernel): each implicitly computes the inner product between feature vectors (Ø(a1), o(a2)) under some transformation ø A + IR (where d may be Mercer
infinite). Furthermore, the probability ratio p+ (a (2)/p(())p((a)) can be interpreted kernel as well:
Definition 2.1. The positive-pair kernel associated with distributions p(z) and p(a|z) is the ratio
p+ pa(a1,000 p(a1)p(az) (6+
K+ K+ .2)
where p4(a1, (2) = Eg ((aaal))((aaala))) and o4 : A + R the transformation
(a)
plale)) p( p(a)
p(al= pl= 21)
p(a)
p(o)
Here, the magnitude of the dot product between vectors 6+(a)) and (a2) reflects the relative likelihood of data points and d2 being drawn from positive pair negative pair. In particular, aj and 02 have zero probability of being a positive pair, 64 (41) and o (az) are orthogonal.
As shown in Figure I we thus reinterpret the three contrastive learning methods in Table aas kernel learning methods, in that they produce parameterized positive-definil kernel functions which approximate this positive-pai kernel. By investigating properties of this kernel, we can thus hope to build a better understanding of the behavior of contrastive learning.
3 KERNEL PRINCIPAL COMPONENTS ARE MARKOV CHAIN EIGENFUNCTIONS
We start by investigating the geometric structure of the data under KG, and how we could use Kernel PCA to build natural representation based this structure. We next ask what properties would
3

---

Published as a conference paper at ICLR 2023
5
2
2
6
3
3 1
3
3 1
2 1
2
2
2
8
2
\
\
1
2006
8.5T0
As 0.475
1643
A
(b) l: = 10 (ttrnnger aug.)
5
s
An m 000
0.053
0.790
A 0.747
As 0.728
5.317
(a) 20 (medium augmentations)
(c) k- = 50 (weaker aug.)
tions at three strengths (k- = 10, 20, 50). At each step we condition t-pixel-subsampling augmenta- augmentation de (middle row) to sample an uncorrupted example 2, (top row), then sample a++1 from 2 so that (az, a++1) is positive pair. Below, we plot the five slowest-varying cigenfunctions f1, ....... fs at each step of the chain, labeled with their eigenvalues AI...., ......,,s... Às Weaker augmentations lead to slower mixing, smoother eigenfunctions, and eigenvalues closer to 1.
Figure 2: Samples from the positive-pair Markov chain for MNIST
want this representation to have, and use a Markov chain over positive pairs decompose those properties in a convenient form. We then show that, surprisingly, the representation derived from K4 exactly corresponds the Markov chain decomposition and thus has precisely the desired properties.
3.1 SUMMARIZING K+ WITH KERNEL PRINCIPAL. COMPONENTS ANALYSIS
(a+) o+ (a2)) where o+ is defined in Equation 2.1 Unfortunately, the "features" (a) R121 are very high dimensional, being potentially as large as the cardinality of [2]. A natural approach for building a lower-dimensional representation use principal components analysis (PCA): construct the (uncentered) covariance matrix Σ [p(a)
Recall that for any d1 and 0g have (a
[] || and then diagonalize it Σ U UDT to determine the principal components {m,, o),, (uz, oi.,...> of our transformed data distribution o+ (A), i.e. the directions capturing the maximum variance of 64 (A). We can then project the transformed points o+ (a) onto these directions to construct sequence of "projection functions" h;(a) u, o(a).
Conveniently, it is possible to estimate these projection functions given access only to the kernel function K_ .2) (a)) (a2)), by using Kernel PCA (Schölkopf et al. 1997). Kernel PCA bypasses the need to estimate the covariance in feature space. directly producing the set of principal component projection functions h1, /2,... and corresponding eigenvalues of 2 ....... such that (a) measures the projection of Φ+ (a) onto the ith eigenvector of the covariance matrix, and of measures the variance along that direction.
The sequence of principal component projection functions gives us view into the geometry of our data when mapped through (A).
thus natural to construct d-dimensional representation r A + Rdd by taking the first d such functions r(a) Ta (a), ha (a))), ha(a)). and then use this for downstream learning. as is done in (kemeel) principal component regression (Rosipal et al. |001] Wibowo & Yamamoto, 2012). In practice, we can also substitute our learned kernel Kg in place of free to choose d trade off between the complexity of the representation and the amount of variance of Φ+ (A) that we can capture.
K4. Note that
3.2 DECOMPOSING INVARIANCE WITH THE POSITIVE- PAIR MARKOV CHAIN
What properties might we want this representation to have? If we wish to estimate functions satisfying Assumption 1.1 for which Ep (z) [[g(a:) [(9(())))) - [ is small, might hope that Eps (a1.az) [[lr(a])= - r(a)) [ is small. But this is not sufficient to ensure we can estimate g with high accuracy; as example, constant representation is unlikely to work well. Good representation learning approaches must ensure that the learned representations are also expressive enough to approximate (for instance by using negative samples or by directly encouraging diversity in VICReg Bardes et al. (202T)), but is not immediately obvious what means to be "expressive enough" if all we know about g is that it satisfies Assumption 1.1
4

---

Published as a conference paper at ICLR 2023
We can build better understanding of the quality of representation by expanding g in terms of a basis in which Ep, (a),az) [((()))- 9{())) admits a simpler form. In particular, convenient decomposition arises from considering the following Markov chain (shown in Figure starting with an example at, sample the next example 04-1 proportional to how likely (at, 0++1) would be positive pair, i.e. according p+ (a++1 (0)) =
(o(a)+1/z)p(( (a). Note that, to the extent that some function g satisfies Assumption [.]] we would also expect the value of to change slowly along trajectories of this chain, i.c. that g(a)) s g(az) R g(az) ...,, and thus that in general g(ar) Ep (a: 1|a.) [g(a.-))] This motivates solving for the eigenfunctions of the Markov chain, which are functions that satisfy E, (ac-1la.) [f(())1)] (af) for some E [0. 1].
As shown by Levin & Peres (2117 Chapter 12), the Si form an orthonormal basiş for the set of all functions A + R under the inner product (f.
[f(a) in the sense that 0 for i * j. Then, for any A + IR, if we
(F(a)))(( = 1 and (a) let c; = Epta) [f)())(()) we must have g(a) E, (afi and Epco) (a))) Σ. G. Further- more, this particular choice of orthonormal basis has the following appealing property:
Proposition 3.1. g A + R and c, ([.f((a))(())) then
Ep [g((a)) - (((2)) || 122-2x))
See Appendix C for a proof, along with derivation of the orthonormality of the basis. One particular consequence this fact is that the eigenfunctions with eigenvalues closest to are also the most view-invariant. Specifically, setting g fi reveals that
E (an.aa) (Li(ar) [i(a2)) = - 22;.
(4)
More generally, if g satisfies Assumption 1.1 Equation 3 implies that 21 X1) e
e, and thus g must have coefficients e; concentrated on eigenfunctions with X; close to 1. Indeed, 0 (i.e. if g perfectly invariant augmentations) then the only eigenfunctions with nonzero weights must be those with A 1. If we want to approximate using a small finitediimensional representation, we should then prefer representations that allow to estimate any linear combination of the eigenfunctions for which A is close to 1.
3.3 KERNEL PCA RECOVERS THE BASIS OF POSITIVE-PAIR EIGENFUNCTIONS
Surprisingly, it turns out that the representation built from kernel PCA in Section 3. h.T precisely the desired property. In fact, performing kernel PCA with K (over the full population) is exactly equivalent to identifying the eigenfunctions of the Markov transition matrix P.
Theorem 3.2. The output (hi, (h2, oZ).... of population- level Kernel PCA under K2, and the orthonormal basis of eigenfunctions Ji of P with eigenvalues >; satisfy of = > and hafa)
o.f((a) =x/²2 222 fe(a) for all and all E A (up to reordering and multiplicity of eigenspace
See Appendix for proof. This theorem reveals a deep connection between the (co) (co)variance of the dataset under our kernel K_ and the view-invariance captured by Assumption I.1 In particular, if we build a representation r(a) [hi (a), ha(a), -.... ha(a)] using the first d principal component projection functions, this representation will directly capture the d cigenfunctions with eigenvalues closest 1, and allow us to approximate any linear combination of those cigenfunctions using a linear predictor.
4 EIGENFUNCTION REPRESENTATIONS ARE MINIMAX OPTIMAL
We now give more precise analysis of the quality of this representation for downstream supervised fine-tuning. We focus on the class of linear predictors on top of a k-dimensional representation
3 As long as we scale them appropriately and choose orthogonal functions within each eigenspace. In other words, when some eigenvalues have multiplicity > 1, the h, and fa are not uniquely determined, but free choose them such that they satisfy this relationship.
5

---

Published as a conference paper at ICLR 2023
191
28 Forebactt et Curfiiee
Truncation Fimr
Cooftdaantoo
Bound Ayg0ge plall
Trancadin tiglaa-ga paiial
Figure 3: (a) We can expand an arbitrary function 9 AA R as linear combination of eigen- functions, here using the toy problem described Section and Figure 4 (b) Taking partial sums using only the first d eigenfunctions yields series of increasingly good approximations of (c) The positive-pair discrepancy of g is a linear combination of the eigenvalues of the corresponding eigenfunctions. (d) Under Assumption I.] we can bound each coefficient based on its contribution to the total positive-pair discrepancy. (e) This can be used to bound the error of approximating g with small subset of eigenfunctions. By Theorem 1 this ordered basis admits the smallest such bound.
r: A + Rdd e.g. we will approximate g with a parameterized function gg(()) 3 ra)) It turns out that the representation consisting of the d eigenfunctions (fi,..., sa} with largest eigenvalues (Ai...., Aa) the best choice under two simultaneous criteria.
Theorem 4.1. Let F, {a rTa)) B RA) be the subspace of linear predictors from representation r, and S. be the set of functions satisfying Assumption 1.1 Let (a) [fi (a), f2(a)...., fa(a)] be the representation consisting of the d eigenfunctions of the positive pair Markov chain with the largest eigenvalues. Then Frr maximizes the view invariance of the least-invariant unit-norm predictor in F,g:
Fy4 argmin dim(F)=d GEF, E[g(a)?]=1
max
Ept ((=)))
(5)
Simultaneously, Ffz minimizes the (quadratic) approximation error for the worst-case target target function satisfying Assumption T.I for any fixed
F argmin
max min gES. BET
Ep(a) :
(6)
dim(F)=d
Equation 5 states that the function class F,r has an implicit regularization effect: it contains the functions That change as little as possible over positive pairs, relative to their norm. Equation 6 reveals that this function class is also the optimal choice for least-squares approximation of function satisfying Assumption I.I. Together, these findings suggest that this representation should perform well as long as Assumption holds.
We make this intuition precise as follows. Consider the loss function ((), y) := := - w/. and the associated risk R(g) = E [e((o(A), Y)] of predictor g A + R. Let g" E argmin R(g) be the lowest-risk predictor over the set of functions A - R, with risk R = R(g"), and assume
satisfies Assumption 1.1 Expand g" linear combination of the basis of eigenfunctions (fi),=l as g" = E!4 87 and define the vector 3 := ( 35) by taking the first d coefficients.
Proposition 4.2. Let Yi)L be i.i.d. samples, choose R 2 and consider the constrained empirical risk minimizer BR E argmin excess risk of 3R is bounded by:
1(8, - Y.}. Then the expected
E [[E(3R)
2dR Vd(113"122 R)+ + V 2(1 Xd+1)
E
<
Vn
where {(g) == RR(B) -R" is the excess risk and (x)+ max max(x,0) 0}-

---

Published as a conference paper at ICLR 2023
Note that 1|3 = Ei= 8:22 > ,3² (a)) if choose R² 2 (a)) then the second term vanishes. The third term bounds the error incurred by using only the first d eigenfunctions, since |82 < - by Equation 3 and motivates choosing d to be large enough that X4+1 is small.
See Appendix foor proofs of Theorem 4.1 and Proposition 4.2
5 RELATED WORK
Our work closely connected to the spectral graph theory analysis by HaoChen et al. (2021), which focuses on the eigenvectors of the normalized adjacency matrix of an augmentation graph, introduces the spectral contrastive loss, and shows that its optimum recovers the top eigenvectors up to an invertible transformation. We go further by arguing that the Spectral Contrastive, NT-XEnt, and NT- Logistic losses can all be viewed as approximating K+, and showing that the resulting eigenfunctions minimax-optimal for reconstructing target functions satisfying Assumption [.] (Indeed, the eigenvectors analyzed by HaoChen et al. are equal to eigenfunctions scaled by p(a) 1/2; see Appendix C.3) ) Our work is also related to the analysis of non-linear CCA given by Lee et al. (2020), which can be seen as an asymmetrie variant of Kernel PCA with K+. We note that Assumption 1.] can be recast in terms of the Laplacian matrix of the augmentation graph; similar assumptions have been used before for label propagation (Bengio et al., (2066) and Laplacian filtering (Zhou & Srebro 201T). This assumption is also used as a "consistency regularizer" for semi-supervised learning (Sajjadi al. 2016
Laine & Aila 2016) and self-superrised learning (Bardes et al.) 2021).
There have been number of other attempts to unify different contrastive learning techniques in single theoretical framework. [Balestriero & LeCun (2022) describe a unification using the framework of spectral embedding methods, and draw connections between SimCLR and Kernel ISOMAP. Tian (2022) provides a game-theoreti, theoretirricc unification, and shows that contrastive losses are related to PCA in the inpur space for the special case of deep linear networks.
Techniques such as SpIN (Plau et al. 2018) and NeuralEF (Deng al., 2022 have been proposed to learn spectral decompositions of kernels. When applied to the positive-pair kernel K4, it is possible to rewrite their objective in terms of paired views instead of requiring kernel evaluations, and the resulting decomposition is exactly the orthogonal basis of Markov chain eigenfunctions fi- Interestingly, modifyyng Neural EF in this manner yields an algorithm that closely resembles the Invariance-Covvaiincc Variance-Invariancee Covariance regularization (VICReg) self-supervised learning method proposed
by [ardes et al. (202T), as we discuss in Appendix E.2] See also Appendix [8.4 for discussion of other connections between the positive-pair kernel and objectives considered by prior work.
6 EXPERIMENTS
remains determine how well learned approximations of the positive-pair kernel succeed at recovering the eigenfunction basis in practice. We explore this question on two synthetic testbed tasks for which the true kernel K2 can be computed in closed form.
Datasets. Our first dataset a simple "overlappiig regions" toy problem, visualized in Figure 4 We define A to be a set of grid points, and Z to be a set of rectangular regions over the grid (shaded), We set p( Z to be a uniform distribution over regions, and p(AlZ = z) to choose one grid point contained in random. For more natural distribution of data, our second dataset is derived from MNIST (LeCun et al. 2010), but with a carefully-chosen augmentation process so that computing K4 is tractable. Specifically, digits, and define p( A Z = 2) by first transforming 2 using one of a finite set of possible rotations and translations, then sampling subset of k pixels with replacement from the transformed copy. The finite set of allowed transformations and the tractable probability mass function of the multinomial distribution together enable us compute K_ by summing over all possible E Z. (Samples from this distribution for different values of ic are shown in Figure
choose p(Z) to uniformly select from small subset Z of MNIST
Model training and eigenfunction estimation. We train contrastive learning models for each of these datasets using a variety of kernel parameterizations and loss functions. For kernel parame- terizations, we consider both linear approximate kernels K (a) a²) = hoaa))Thn(2)) hg(a2), where he may be normalized to have constant norm hho(a) or be left unconstrained, and hypersphere-
7

---

Published as a conference paper at ICLR 2023
140
[b))
Figure 4: (a) Toy "overlapping regions" contrastive learning task, where A is the set of cross markers, and Z is the set of shaded blue rectangles. (b) 2D embedding space learned by minimizing a contrastive loss with rational quadratic kernel head Kg. (c) The first 14 eigenfunctions of the true positive-pair Markov chain. (d) The first 14 principal component projection functions for the learned kernel K2 extracted using Kernel PCA. Diagonal colored lines denote alignment between the learned functions and the true eigenspaces, which increases as K approaches K+. (e) Evaluations of the the learned projection functions over the entire latent embedding space using Kernel PCA, showing that it can embed points not seen during training.
based approximate kernels Ro(ai, 02) - exp(ho(ai) ha(a2)/T b E IR, IR+ are learned. We also explore either replacing b with learned per-example adjustment so s0(a1) + s0(22) or fixing it to zero. For losses, we investigate the XEnt, Logistic, and Spectral losses shown in Table Il and explore using a downweighted Logistic loss regularizer for the XEnt loss to eliminate the underspecified proportionality constant in minimizer of the XEnt loss.
(aa((a)()) / + b), where [/a[aa]]² 1 and
For each approximate kernel and also for the true positive-pate pair kernel K+, we apply Kernel PCA to extract the eigenfunctions f, and their associated eigenvalues A We use full-population Kernel PCA for the overlapping regions task, and combine the Nyström method (Williams & Seeger (2000) with large random subset of augmented examples to approximate Kernel PCA for the MNIST task. We additionally investigate training Neural EF model (Deng et al., 2022) to directly decompose the positive pair kernel into principal components using a single model instead of separately training a contrastive learning model, as mentioned in Section We modify the Neural EF objective slightly to make it use positive pair samples instead of kernel evaluations and to increase numerical stability. See Appendix E for additional discussion of the eigenfunction approximation process.
We then measure the alignment of each eigenfunction f. of our learned models with the corresponding eigenfunction / of K+ using the formula (f((a) (a)]², where the square is taken since eigenfunctions are invariant to changes in sign. We also estimate the positive-pair discrepancy Ep. [f)(a))) {² for each approximate eigenfunction.
Results. We summarize a set of qualitative observations which are relevant to our theoretical claims in the previous sections. A representative subset of the results are also visualized in Figure 5 See Appendix [.. for additional experimental results and a more thorough discussion of our findings.
Linear kernels, hypersphere kernels, and NeuralEF can all produce good approximations of the basis of eigenfanctions with sufficient tuning, despite their different parameterizations. The relationship between approximate eigenvalues and positive-pain discrepancies also closely matches the prediction from Equation 4 Both of these relationships emerge during training and do not hold for randomly initialized model. Additionally, for fixed kernel parameterization, multiple losses can work well. In partieular, we were able to train good hypersphere-bort based models on the toy regions task using either the XEnt loss or the spectral loss, although the latter required additional tuning to stabilize learning.
Constraints on the kernel approximation degrade eigenfunction and eigenvalue estimates. We find that introducing constraints on the output head tends to produce worse alignment between eigenfunctions, and leads to eigenvalues that deviate from the expected relationship in Equation 4 Such constraints include reducing the dimension of the output layer, rescaling the output layer for a linear kernel parameterization to have a fixed L2 norm (as proposed by HaooChen et al. (2021). or fixing b to zero for hypersphere kernel parameterization (as is done implicitly by Chen et al. (2020a).
8

---

Published as a conference paper at ICLR 2023
Oualipeing agai
Repershers 20140
Ceatupery agin
Ronigree Tereeree deaa cad (onli uneal
Logal
Figure 5: Eigenfunction and eigenvalue estimation accuracy for a selection of models on our two synthetic tasks. Top row: Alignment between the eigenfunctions of K+ and those of each kernel approximation, with perfect alignment shown as a block diagonal matrix. Bottom row: Relationship between learned kernel eigenvalue À and the corresponding positive- -aiir discrepancy ((f(()))) - f(a2))²], with the relationship predicted by Equation shown with a dashed line.
Weaker augmentations make eigenfunction estimation more difficult. Finally, for the MNIST task, we find that as we decrease the augmentation strength (by increasing the number of kept pixels k), the number of successfulll-rrcoovres eigenfunctions also decreases. This may be partially due to Kernel PCA having worse statistical behavior when there are smaller gaps between eigenvalues (specifically, more eigenvalues close to 1), since we observe this trend even when applying Kernel PCA to the exact closed-fore K4. However, we also observe that the relationship predicted by Equation f starts to break down as well for some kernel approximations under weak augmentation strengths.
7 DISCUSSION
We have shown that existing contrastive objectives approximate the kernel K+. and that Kernel PCA yields an optimal representation for linear prediction under Assumption I.I We have further demonstrated on two synthetic tasks that running contrastive learning followed by Kernel PCA can yield good approximate representations across multiple parameterizations and losses, although constrained parameterizations and weaker augmentations both reduce approximation quality.
Our analysis (in particular Theorem 4.1 assumes that the distribution of views p(A) is shared between the contrastive learning task and the downstream learning task. In practice, the distribution of underlying examples p(Z) and the augmentation distribution p( (Z) often change when fine- tuning self-supervised pretrained model. An interesting future research direction would be to quantify how the minimax optimality of our representation is affected under such distribution shift. Our analysis also focuses on the standard "linear evaluation protocol". which determines representation quality based on the accuracy of linear predictor. This measurement of quality may not be directly applicable to tasks other than classification and regression (e.g. object detection and segmentation), or to other downstream learning methods (e.g. fine-tuning or k-nearest-neighhorr) In these other settings, our theoretical framework not directly applicable, the view-invariant features arising from Kernel PCA with K4 would be useful.
we might still hope that
Additionally, our analysis precisely characterizes the optimal representation all we know about our target function g is that it satisfies Assumption I.1 but in practice we often have additional knowledge about g. In particular, Saunshi et al. (2022) show that inductive biases are crucial for building good representations, and argue that standard distributions of augmentations producing many eigenvalues very close to one. Interestingly, this is exactly the regime where the correspondence between the approximate kernels and the positive-pair kernel K+ begins to break down in our experiments. We believe this opens up a number of exciting opportunities for research, including studying the training dynamics of parameterized kernels Kg under weak augmentation regime, analyzing the impact of additional assumptions about g and inductive biases in Ko on the minimax optimality of PCA representations, and exploring new model parameterizations and objectives that trade off between inductive biases and faithful approximation of K
approximately disjoint,
More generally, the authors believe that the connections drawn in this work between contrastive learning, kernel methods, principal components analysis, and Markov chains provide useful lens for theoretical study of self-supervised representation learning and also give new insights toward building useful representations in practice.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
We would like to thank David Duvenaud, Daniel Tarlow, and Lechao Xiao for providing feedback on this manuscript, and the ICLR 2023 reviewers for their additional suggestions and comments. We would also like to thank the reviewers and organizers of the ICML 2022 workshop on Pre-traing training: Perspectives, Pitfalls, and Paths Forward for providing a venue for an earlier version of this work.
REFERENCES
Ehsan Amid, Rohan Anil, Wojciech Kotlowski, and Manfred K Warmuth. Learning from randomly initialized neural network features, arXiv preprint arXiv:2202.0644 06438, 2022.
Francis Bach. Learning theory from first principles, 2021.
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. arXiv preprini arXiv:2205. 1508, 2022.
Adrien Bardes, Jean Ponce, and Yann LeCun. VICReg: ization for self-supervised learning. In International Conference Learning Representations, 2021.
Invariance-Covvriaane regular-
Yoshua Bengio, Jean-françcois Paiement, Pascal Vincent, Olivier Delalleau, Nicolas Roux, and Marie Ouimet. Oft-pl-sample extensions for LLE, Isomap. MDS, Eigenmaps, and spectral clustering. Advances in neural information processing systems, 16, 2003.
Yoshua Bengio, Olivier Delalleau, and Nicolas Le Roux. Label propagation and quadratic criterion. In Semi-Supervised Learning, 2006.
Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
James Bradbury. Roy Frostig. Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman- and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL
http:: / ccm/ wwwm//ooolee/////ooooooooooo
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp.
1597-1607. PMLR, 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton. Big self-supervised models strong semi-supervised learners. Advances in neural information processing systems, 33:22243 22255, 2020b.
Zhijie Deng, Jiaxin Shi, and Jun Zhu. Neuralef: Deconstructing kernels by deep neural networks, In International Conference on Machine Learning, 2022.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning an invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06), volume 2. pp. 1735-1742. IEBE, 2006.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- sele-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34, 2021.
Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Mare van Zee. Flax: A neural network library and ecosystem for JAX, 2020. URL http://github com/ http////ooll//ll...a
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchille Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: 06670, 2018.
10

---

Published as a conference paper at ICLR 2023
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel:
Convergence and
generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction:
Risk bounds, margin bounds, and regularization. In NIPS, 2008
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6908 2014.
Samuli Laine and Timo Aila. Temporal ensembling for semi- semi-supervised learning. arXiv preprint arXiv:1610.02224. 2016.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online].
Available: http://ynm.lecun.ccm www.u..com//xx///miss..r. 2. 2010.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps:
Provable self-supervised learning. arXiv preprint arXiv:2008 01064, 2020.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathemat- ical Soc., 2017.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representa- tions in vector space. arXiv preprint 130.3313 2013.
George V Moustakides and Kalliopi Basioti. Training neural networks for likelihood/density ratio estimation. arXiv preprint arXiv:1911. 1et::1911.00005. 2019.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 271-279, 2016.
David Pfau, Stig Petersen, Ashish Agarwal, David GT Barrett, and Kimberly Stachenfeld. Spectral inference networks: Unifying deep and spectral learning. In International Conference Learning Representations, 2018
Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference on Machine Learning, pp. 5171-5180.
PMLR, 2019.
Roman Rosipal, Mark Girolami, Leonard J Trejo, and Andrzej Cichocki. Kernel pea for feature extraction and de-noising in nonlinear regression. Neural Computing & Applications, 10(3): 231-243, 2001.
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep semi-super learning. Advances in neural information processing systems, 29, 2016.
Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Confer- ence on Machine Learning, pp. 5628-5637 PMLR, 2019.
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint 220.::2202..10.377 2022.
Meyer Scetbon and Zaid Harchaoui. A spectral analysis of dot-product kernels. In International Conference on Artificial Intelligence and Statistics, pp. 3394-3402. PMLR, 2021.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Kernel principal component analysis. In International conference on artificial neural networks, pp. 583-588. Springer, 1997.
Vaishaal Shankar, Alex Fang, Wenshuo Guo, Sara Fridovich-Kan Keil, Jonathan Ragan-Kelley. Ludwig Schmidt, and Benjamin Recht. Neural kernels without tangents. In International Conference on Machine Learning, pp. 8614-8623. PMLR, 2020.

---

Published as a conference paper at ICLR 2023
Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. Advances in neural information processing systems, 29, 2016.
Bharath Sriperumbudur and Nicholas Sterge. Approximate kernel PCA using random features: Computational statistical trade-off, arXiv preprint (1.Kv::1706.629000 2017.
Nicholas Sterge, Bharath Sriperumbudur, Lorenzo Rosasco, and Alessandro Rudi. Gain with no pain: Efficiency of kemel-PCA by Nyström sampling. In International Conference on Artificial Intelligence and Statistics, pp. 3642 -3622. PMLR, 2020.
Shengyang Sun, Guodong Zhang, Chaoqi Wang, Wenyuan Zeng, Jiaman Li, and Roger Grosse. Differentiable compositional kernel learning for Gaussian processes. In International Conference on Machine Learning, pp. 4828 4837. PMLR, 2018.
Yuandong Tian. Deep contrastive learning is provably (almost) principal component analysis. arXiv preprint arXiv:2201.12668, 2022.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In Algorithmic Learning Theory, pp. 1179-1206. PMLR, 2021.
Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, and Raman Arora. Streaming kernel PCA with OV))) random features. Advances in Neural Information Processing Systems, 31, 2018.
Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: 03744,,88 2018.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp. 9929-9939. PMLR, 2020.
Antoni Wibowo and Yoshitsugu Yamamoto. A note on kernel principal component regression.
Computational Mathematics and Modeling, 23(3):30--377, 2012.
Christopher Williams and Matthias Seeger. Using the Nyström method speed up kernel machines. Advances in neural information processing systems, 13, 2000.
Andrew Gordon Wilson, Zhiting Hu, Ruslan Salakhutdinov, and Eric P Xing, Deep kernel learning. In Artificial intelligence and statistics, pp. 370-378. PMLR, 2016.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 773--3742, 2018.
Xueyuan Zhou and Nathan Srebro. Error analysis of Laplacian eigenmaps for semi-supervised learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 901-908. JMLR Workshop and Conference Proceedings, 2011.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
Justification of Assumption 1.1
14
Existing objectives are minimized by the positive-pair kernel
15
B.1
NT-XEnt and the InfoNCE objective
15
B.2 Logistic losses and NT-Logistic
16
B.3
The Spectral Contrastive Loss
17
B.4
Other Related Objectives And Connections to the Positive-Paii Kernel
18
Relationship between positive-pair kernel and Markov chain eigenfunctions
19
Notation
19
Proof of Correspondence Between Kernel PCA And Markov Chain Eigenfunctions
19
Relationship to the eigenvectors of the symmetrized adjacency matrix
22
C.4
Recovering proportionality constants
23
Generalization properties of the eigenfunction representation
24
D.I Min-max optimality of eigenfunctions
24
D.2 Generalization bound for linear prediction with the eigenfunction representation
27
Eigenfunction estimation techniques
29
E. Combining Contrastive Learning With Kernel PCA
29
Direct Eigenfunction Extraction, And Connections to VICReg
30
Experiment Details
32
Additional Eigentunction Estimation Results
32
Training Details: Overlapping Regions Task
34
Training Details: MNIST with Multinomial Augmentations
35
Downstream Supervised Learning On MNIST
38
F55
Principal Components Analysis of Spectral- Loss Linear Kernel Model on ImageNet
39
13

---

Published as a conference paper at ICLR 2023
A JUSTIFICATION OF ASSUMPTION 1.1
In this section we expand on the justification of Assumption 1.1 given in Section !
Recall that during contrastive learning we have distribution p(Z) of original examples, and distribution p(A|2 Z 2) of augmented views for each original example z. Then, at downstream supervised learning time, additionally have distribution p(Y y =) of labels y for each original example 2. (For simplicity we assume that the distribution of p( Z) remains unchanged during the downstream learning step. We also assume y is a scalar; the vector case can be derived by independently estimating each element of Y with separate target function.)
Since the distribution of augmented views is typically defined via random perturbation of Z without using Y, the augmented views A are conditionally independently of the label Y given the original example Z, so we have joint distribution p(a. 2) p(z)p(a|= (()pp)))) When we draw pair of augmented views for the same original example, we instead have joint p(01; d2, y/ =) = p(=)p((1(=)pp(1)) =)p(ul=). We also have some target function 9 A - we trying to approximate. For instance, might want to approximate Bayes-optimat predictor of Y under some loss function, such as g(a) = E|Y|A= = a] for the quadratic loss.
Common wisdom states that p(AlZ) should remove irrelevant information from Z without removing (much) information about Y (most of the time). This means that, if augmentations are chosen appropriately,
expect E (g((A) - Y to be small under our joint probability distribution for an appropriate choice of
We then expand the left-hand side of Assumption 1.1 as
[[(a(A,) - 9(A2)) = E [(((((A)) - Y) - (g(A2) 1))
[[(o(A1) - = - - () -Y) (0(A2) YY (9(A)
Furthermore, due the law of total expectation combined with our conditional independence assumptions, we know that
([(a(AA)-))(r Y)] = Ez,y [A [(((A)) - -
E2,y EA,,A [(g(A1) - Y)| Y))
[((AA)((((A))) ((o(A2) Y) z.Y]]
E2,y EA [[g( ()) V) y1 2
We then conclude that
[[(a(A)) {(A2)) = 21E (o(A) - r) -2E (((AA) () y)
s 2TE (o(AA Y)
Thus, Assumption 1.] holds whenever (g(A) - Y) < f.c. Intuitively, if it possible to estimate Y with high accuracy using deterministic function, then that function must satisfy Assumption 1.1
Note that Assumption defined even if we never specify Y and work only with the joint distribution p(A1, This is particularly useful because it allows us to quantify over all possible choices of in a sensible way with minimal knowledge about the label distribution itself.
itself may still hold even if is not good estimate of Y. and is well
14

---

Published as a conference paper at ICLR 2023
B EXISTING OBJECTIVES ARE MINIMIZED BY THE POSITIVE-PAIR KERNEL
In this section, we show that the positive-pair kernel is the optimum of the objectives shown in Table (although this optimum is not unique for cross-entropy loss), and discuss some connections to other objectives considered by previous work. Throughout this section, we use p ((Z) to denote the true data distribution over unperturbed examples, p(A Z) to denote the distribution of augmented views conditioned on particular unperturbed example, and p( (( to denote the marginal distribution of augmented views, e.g.
a) Σ P = al =2)
2E2
We use p+ A2) to denote the positive pair distribution induced by p( and p(A|Z), defined by 02l 2 z). p+ (Ai 01, A2 = =02 = Σ =z= = =a / =)p(A
ZEZ
For notational convenience, we will use shorthand p(=) for p(Z - =), p(a) for p(A = a), p+ (a1, for p4 (Ai = d1, A2 = d2). and so on.
B.I NT-XENT AND THE INFONCE OBJECTIVE
The NT-XEmt objective described by Chen et al. (2020a) (and previously used by Sohn (2016); Van den Oord et al. (018): Wu et al. 2018) has the form
ha(aa)) [no(as)
exp
CNT-Xem (0) E (af l~p (2))
log
Mo(aa) hg(a + En; exp hola, ) hala,
exp
of (PAA)
For simplicity, we assume that all of the negative samples a, are drawn independently from the marginal distribution when computing the loss for at and az (In practice, implementations often generate negative samples by taking elements of other positive pairs, e.g. (a)) ~ ( (ag .7) ) ~ P+ (ag o7) ), and so on.)
We can decompose this objective into two parts: an InfoNCE-like loss (Van den Oord al. 2018)
ba(ataa)
LIstANCE Ro) (at --)- (A1.A)) (((A)
log Rolat, at) + Eo; Rolat,a7) ,77)
combined with a particular parameterized function
Ro(a1, 02) = exp ho(ai) The
where he A + B=+1 maps inputs to points the n-dimensional hypersphere.
We first observe that Ro(aj, 02) defines positive definite kernel, within the family of "dot product kernels". Indeed, when ho is restricted to the unit hypersphere, this parameterization is equivalent to kernel)
the
kernel (also called
(aiba(ai) - ho (22))) = cxp(1//) exp (- [1ha (a1) - (a2)
Ra(a1, a2) exp
2r
using the identity (ah) 22(a2)112 = 2 (h) ha((2)) Although this kernel is positive definite, it has "infinite dimension" and cannot be expressed as an inner product of finitedimmensional embedding vectors; nevertheless, we can still run algorithms such as Kernel PCA on finite dataset. (See BaccBachhoa [2021 Chapter 7) for some additional background on positive-definite kernels, and Scetbon & Harchaoui (202I) for discussion of other dot product kernels on the unit hypersphere.)
We next discuss the minimum of the NT-XEnt objective, under the unconstrained setting where allow Ko (a 02) to be an arbitrary symmetric function. The InfoNCE loss, in its more general form,
15

---

Published as a conference paper at ICLR 2023
not necessarily symmetric: it is based distribution of contexts p(C), positive samples p(A[C),
and negative samples drawn from the marginal distribution P(A), and given by
folc,at)
(nfoNCE( -B -o-plo) mD(A)
log f(c, Ea; Sa(c,a7)
Van den Oord (0188) show that every minimizer of this objective is of the form
f.(c,a) p(ale) b(c) p(a)p(c)
p(a,c) c)
b(e)
p(a)
for some function b(c) that does not depend on In other words, holding c fixed, f-(c, x p(a.e) Intuitively, this because the exact probability of a+) being the positive pair given e and the {at aj ..... ag}
p(a)p(e))
J is also proportional to this density ratio, and the InfoNCE objective cross-entropy objective for identifying the positive pair. (See also Poole et al. (2019) for different proof.)
In the case of the NT-XEnt contrastive objective, we choose the context C to be one of the aug- mentations AT. and the positive sample to the other augmentation A drawn according to p+ (AJ1 ).)) We furthermore restrict our attention to symmetric functions Kg, e.g. functions for which a2) Kolaz, a1). In this case, the minimizer is
(a 02) P+ (2), M(1)) a2) b(a2).
p(a1)p(az)
p(an)p(az)
so we must have b(a1) = b(a2) for any pair (a1, a2) for which p+ (a1, 02) > 0.
we assume that the positive pair Markov chain irreducible, e.g. that there is single communicat- ing class and it is possible to reach any augmentation in A from any other augmentation over a long enough trajectory, then the function b(a) must be constant everywhere, and thus
(+ a2) B
(a1, 02) (a1, a2) p(a1)p(a2)
for some B E R++ In this case, R. is equivalent to K4 up to scaling constant.
the Markov chain has multiple communicating classes (e.g. if the augmentations can partitioned so that augmentations always come from the same partition), the function b(a) may assign a different value to different communicating classes. Nevertheless, any such minimizer still kernel, since we can write it as
p(ai/e1) p(11)
p(o2le1) p(a.)
p(as) p(a1 (22) (P(22)
p(az)
p(eales) p(22) p(a2)
(x1, Vb(ar)
p(a1)
Vb(a2)
p(es 2012 JN ((
plaz 2 p(1)2))
p(a1)
p(a2)
(Vb((a) - (ai), vb(a2) 2+ (a2)
Indeed, such minimizer is equivalent K4 except that it scales the inner product by the value of b(a) for each communicating class. It is still possible to extract the set of Markov chain eigenfunctions from the set of principal components of this kemnel, although one must correct for the scaling factor when computing the cigenvalues; see Appendix C.4 for details. Alternatively. one can ensure unique minimum by combining the NTTXenn/InfoNCF loss with either the spectral or logistic losses (discussed below).
B.2 LOGISTIC LOSSES AND NT-LOGISTIC
Logistic losses have also been proposed for contrastive learning, including the NT-Logistic objective described in Chen al. (2020a) and other versions described by Mikolov et al. (2013) and Tosh
16

---

Published as a conference paper at ICLR 2023
al. 2021 Such losses take the form
Logistic (fo) = B (at az -pp (A. A2) | log o ofogofaaa a
+ a ~(()), ~p(A) log o (a a2))
where negative samples are drawn independently from the marginal distribution (4). Tosh et al. (2021) motivates this loss based a binary classification: choose a label Y be 0 or with probability 1/2 each, sample a positive pair (2),02) ~ P+ (A1, A2) if Y = and a negative pair a1 ~ p(A). 02 ~ p(A) Y = O, then use a learned model predict Y given the pair. The minimizer of this loss is then the conditional log- ratioo
r(Y 1|a,, 02) log
p(a1, 0z Y 1)p(Y=
fa 02) log
p(Y = 0/ a2)
p(a1. 0zlY 0)p(Y = 0)
p+ (a1, 02)
(2)
log ((11)p(a)
log p(a1)p((z)
For the particular case of the NT-Logistic objectíve, we parameterize So as
fo(a1, 02) = log Ro(a1, ho hal ( (a()
where we again define
Ro(ai, exp (ho(ar) ha((2)
The optimum (if we ignore the constraints of this particular form of K and minimize over all functions of two variables) is then
K. (41, a2) = (+ a2)
p(a1) (p)))(()))))))
Note that in this case there no proportionality constant.
B.3 THE SPECTRAL CONTRASTIVE Loss
HaoChen et al. (02I)) propose the Spectral Contrastive Loss an alternative to other contrastive losses with provable performance guarantees. The loss is defined as
LSpectmil (Ro) -2 (aa aB Jup) (A1.A2)
[Roaat,
+ E ap(d), ~p(a)
Rolaj , az
where they choose
Ro(ai, a2) = ha
for a learned embedding function hg : A + Rdd. We note that this directly satisfies the definition of a kernel, in that it is inner product in transformed space. One interesting property of this kernel approximation is that it can be negative, whereas the exponential-based kernel approximations the previous sections are always nonnegative.
HaoChen et al. show that this loss can be rewritten as
Lspectral (o)) = Σ
(- 2p+ (-2p+
( 02) + Rooon))
01.02
(+(aa,,2)) az)
Σ
p(a, (((2)
a1.0g
aa)
p(an)p((z)
01.02
Σ 01-92
(+(01, 02)
Voloa))oo))Rolanaa) C.
vp(ai)p(az)
where C' == Eay
C=E
P (a) [2)
is constant independent of the model.
p(a))p(a2)
17

---

Published as a conference paper at ICLR 2023
If we again ignore the constraints on Kg. the minimum of the spectral loss must occur when
P+ P+ (2) = - Vlla))poo))Ro((.. vp(a))p(az)
for all 01 and dg, in other words, when
Ro(an, 02) = P- p- (2) K (=)
p(a1)p((z)
HaoChen et al. continue by expanding their definition of Kg for a fixed representation d, and showing that it relates to the spectral decomposition of particular augmentation graph. It turns out that this decomposition is equivalent to our decomposition in terms of eigenfunctions except for scaling factor of p(a) we discuss this connection more in Appendix C.3
B.4 OTHER RELATED OBJECTIVES AND CONNECTIONS TO THE POSITIVE- KERNEL
p(u,0) has information-thheorticc interpretation the We note that the log-probability ratio log p(u)p(u)
pointwise mutual information between two random variates u and We can thus view the positive- pair kernel K+ as being exponentiated version of the pointwise mutual information between two views A₁ and A2. This ratio has been shown to be an optimal critic for mutual information estimation (Poole et al. 2019 Nowozin et al., 2016 Hjelm et al. 2018).
Moustakides Basioti (2019) describe several cample-based estimators for probability ratios between arbitrary densities mass functions. These estimators can be seen generalizations of the the contrastive losses in Table 1 with the goal of estimating the ratio between the positive and negative pair distributions.
The VICReg semi-supervised learning technique can be reinterpreted terms of the positive-por kernel particular form of kernel decomposition method. See Appendix B.2 for discussion of this connection.
Although the parameterized kernels in Table I have fairly simple form, some prior work has considered more sophisticated parameterizations for learning kernels with neural networks (Wilson al. 2016 Sun et 2018). There have also been recent works related reinterpreting existing
neural network models as kernels (Jacot et al., 20188] SShankar et al. 2020 Amid et al.) (022).. It would be interesting compare the properties of these other kernel parameterizations with the implicit kernels involved in contrastive learning methods.
Finally, we note that early approaches to contrastive learning such as DrLIM (Hadsell 2006) were motivated in part by removing limitations of previous spectral embedding techniques, which required explicitly selecting an input-space distance metric or kernel function (e.g. [Bengio al. (2003)). Our analysis reveals that that, for modern contrastive learning methods, choosing the distribution of augmentations can still be seen as implicitly defining kernel function of this form. Conveniently, however, we do not need to be able to evaluate this kernel to train contrastive learning models; we only need to sample augmentations.
18

---

Published as a conference paper at ICLR 2023
C RELATIONSHIP BETWEEN POSITIVE-PAIR KERNEL AND MARKOV CHAIN EIGENFUNCTIONS
In this section, describe the relationship between the positive-pair kernel principal components and the Markov chain eigenfunctions in more detail.
C.I NOTATION
We start by introducing some notation that will be useful.
Throughout, we will identify functions f A + RR as vectors f RAA which will allow us to use matrix notation for many of the relevant quantities. We will also use e; to represent the vector that has one at the ith position and zeros in all other positions.
will let
Dz
P(Z(2)))
DA (ing(p((a).,((2))))).. p(a))...... ));
be diagonal matrices containing the marginal probabilities of each element in Z and A, respectively, under the true data distribution. We will assume that the distribution has full support, and thus both Dz and D are invertible. We also define the matrices
|Z,,Alza- = p(2,a)
[Pz-Alzza p(alz)
( = pp((a)
[Pa,zla,= = ((
=
Equivalently
P =D= Di P7,A,
Pzt Pz, D
PALZ (PZ+A))
PA-Z= (Pz-A)
From these, we can construct the positive pair probability matrix
PA. PA-z Dz P
[PA.AlL = p(A = A2 = Σ - = j1z).
C.2 PROOF OF CORRESPONDENCE BETWEEN KERNEL PCA AND MARKOV CHAIN EIGENFUNCTIONS
The positive-pair kernel. Writing the positive-pair kernel K4 in matrix form, such that [K+]k = K (i.j), definition (2)
p- .221 becomes the matrix equation play )p(as)
K+ DD PAAADA
One way to expand K4 is as a product
K2 = PA-
( (D!/"P2-ADD) = =
where 4 =xx is matrix whose columns are given by d+:
Φ, - D 22/22P.eo PZ (a1(a1) (a2)
p(an (2)) /
plan/z1)
p(a))
p(az)
p(a
p(a (2g) p(=g)
p(agl 2g) ((())
p(a Al [2)) p(2a)
p(01)
p(22)
p(a
p(113121) p(a 2)
p ) (()22 p(a2)
p(a |2 p(
p(a1)
p(9(A)
19

---

Published as a conference paper at ICLR 2023
Equivalently, we have (+(a) = Cc
Since (a1 a2) = (a1) Φ+ (a2), o+ is called a feature map for K Note that there are multiple possible feature maps for K+: given any orthonormal matrix Q, the function ΦQ(a) Qo+ (a) is also a feature map for the kernel, since
Φ0((1) (a(aa)"do(a))) = ++ (a) Q
(a)T Q6+ (a) - o+ (a) TooTTee (a) = K+ (an, 02).
Performing kernel PCA under K is equivalent to performing ordinary PCA over any of its feature maps (since the principal component projection functions are independent of the particular feature map chosen). We thus focus on analyzing the principal component projection functions for the feature map o..
The population level principal components are the eigenvectors the (uncentered) covariance matrix
Σ (6)+ (a) (a) T e $I] = o Bpa) [ = DDD
Note that working with the uncentered principal components, is commmon for kernel PCA: we do not subtract the mean before computing the covariance. Since 2 is positive semidefinite, it can be diagonalized as
Σ = U diag(o") @J = ESauan
where U = [U1 Ug,..., Ug. is orthonormal and diag(o²)
................. .o)) is diagonal matrix of eigenvalues (here k = |Z] is the dimension of the feature map). Each of the vectors u, one of the population principal components of the transformed distribution e+ giving the directions of maximum variance, and the of measure the variance in that direction.
Given new augmentation A. principal component directions as h (a) = u. (a).
then compute the projection of (a) into each of these
The Markov Chain. We now redirect our attention the positive pair Markov chain. The Markov chain transition matrix is defined by [PA-Alosиa P- (a1 (22), or in matrix form
PALA PA.ADA.
We are interested in the left eigenvectors f PA-A dal, of this matrix PA- or equivalently the right eigenvectors of its transpose PT P P PA given by PA-Aff X,f, Observe that then
D PA.Af d,f,
equivalently
1/2 1/ (D PAA'" = (D)/²T.)
It follows that 22, f, is eigenvector of the symmetric matrix
M M= PA.A
with the same eigenvalue A; (We note that the matrix M is exactly the symmetrized adjacency matrix described by HaoChen et al. (2021).)
We can now diagonalize M as M VAVT where orthogonal, and then write
V
2 1
D1/22, fg
1222 [fi
f.) m= 2
where
F f
fg
fal.
Consider an arbitrary function A + R, and let g E IR. be its vector form, so that g(a) ga
gTe,. Also define c; (((() and (ei C2 cx] Then
E [g(a) eal =E Te. = Dag V D
20

---

Published as a conference paper at ICLR 2023
must have
g g= (
and thus g(a) = Gf((a).. Additionally, we see that
EE [g(a)²] E [g e.e, gl - c- DAF'
c c (D 12 ( F)c = =iv
Note that this also implies that the functions f; are orthonormal under the base measure p(a). e.g.
[a)) = 1 and (a) (a)] = 0 for *
We can now prove our main results from Section
Proposition 3.1. g A - R and c, = ([fi(a)g(()) then
E (a) 9(az)) (22--20)c
(3)
Proof. Observe that
Epp (9l02) - (0(01)-9(00) 9((2)))
= Epp - 2g((1)9(a2) + )(az)²
= 2E [s(a) -1 [9(ar)g(a2))
= 2 Σ oi -2EE_ (0(a1)g(02)
Expanding the second term, we have Ep, (((a))
EEp
[g eag e g Eyp
(eay e22 g
PA.AB
-g DD =
=g =DD DI
=c (TFFF///VA D 2 Fc
=C](D) F) VAV F)c -c
=c Σ Xc..
We conclude that Ep,, ( = 22 -1.)cc.
Theorem 3.2. The output (h1, (12, oā)... of population-level Kernel PCA under K_, and the orthonormal basis of eigenfunctions fo of P with eigenvalues X; satisfy of = x and hz(a)= a.fi(a) fe(a)
(/2(((()) for all and all A (up to reordering and multiplicity of eigenspaces
Proof. Consider the matrix B = 1/2 where 4 =D'//P2-aa2 described above. Take the singular value decomposition B = UT1/2VT where U and V are orthonormal and A7/2 is diagonal. Now observe that
BB T DDDA = E,
and
11/201 2 11/2 = 24
11/22 (DA PA.ADA)) D
DA 1/2 1/2 PA.A 1/22 M.
'In other words, when some eigenvalues have multiplicity 1, the h, and fa are not uniquely determined, but free choose them such that they satisfy this relationship.
21

---

Published as a conference paper at ICLR 2023
Thus, Σ and M must have the same eigenvalues. Diagonalize Σ and M in terms of U and V and define (a) and fi(a) according to that diagonalization. We then have
h,(a) un (a
UT 24e, U.e
= UT (BD Co
= =CTUT (UA D ca
-TAAVVTT DA" 1
cT A/2 (DA Co
= AT/22FT ea
A/2 [f] 1, ea = A S((a.
fz] ea
One interesting consequence of this relationship is that the positive-pair kernel is fully determined by the eigenfunctions and their eigenvalues, and we can write the kernel function directly as a weighted dot product of this representation:
Proposition C.1. For any a1, 02 E A. we have
(2)) = Σ {fflla)ff(o2))
where the fi and X as defined in Section 3
Proof. Using the matrix notation and definitions described above, algebraic manipulation shows that K (a1, u2)
ea: K eaz
Ca. (D PA.ADA Coz
Gas D 1/2 1/ MD 1/2 eaz
Ca, D 1A D 1/2 Coz
Cu, DA (
1/2 eu2
Ca, FAFT Bo2
Σ (.lla)))
C.3 RELATIONSHIP TO THE EIGENVECTORS OF THE SYMMETRIZED ADIACENCY MATRIX
Interestingly, the matrix M described above is exactly the symmetrized adjacency matrix discussed by [HaCChen et al. 2021). HaoChen et al. motivate their loss as estimating the cigenvectors of up to scaling term by 1/a) due to prior work showing that eigenvalues give information about clustering structure in graphs.
The connection between the symmetrized adjacency matrix M and the positive-pair Markov chainis well known; indeed, HaoChen et al. briefly discuss the cositive-pair Markov chain in their Section 2, and [evvn & Peres (2017) Chapter 12) introduce the matrix M when discussing the spectral decomposition of general symmetric Markov chain.
One way of thinking about this reweighting is as a change of measure. The eigenvectors orthonormal with respect to the counting measure over A, e.g. if you sum squared values over all of A. you obtain 1, and the dot product of different eigenvectors the eigenvectors f, (or, equivalently, the eigenfunctions f.) of the Markov chain are orthonormal with respect to the measure p(A), e.g. if you take the expectation of squared values over random augmentations, you obtain and the uncentered covariance of different eigenfunctions is zero
zero. On the other hand,
22

---

Published as a conference paper at ICLR 2023
We believe that using ((4) measure is natural choice, since it allows to reason about expected values in straightforward way. From this perspective, the p(a) scaling terms are desirable feature the learned representation that allow us to directly reason about optimality with respect to Assumption 1.1
We note that our Assumption 1.I could alternatively be expressed in terms the bubbability-weighhee Laplacian matrix of the augmentation graph, given by L = D PA.A. Indeed, we have
Ep- - g(az)) 2g Lg.
C.4 RECOVERING PROPORTIONALITY CONSTANTS
As described in Appendix B.] minimizing the NT-XEnt / InfoNCE loss may not exactly produce the positive-pail -ariieeeparrree kernel K+, but may instead learn a scaled version
(a a2)
z(a1) o+ (a1), vz(a2) ( V a2).
where =: A + R- is some function which is constant on each communicating class on the Markov chain. (Since (+ 02) whenever a1 and 02 are in separate communicating classes, we could equivalently say K. (a1, .2) = =(a1) KK(aa 02) = =(a2) K (21,
When the Markov chain has one communicating class, K, is simply scaled version of K In this case, all of the principal component projection functions for K, are still the cigenfunctions of the Markov chain, but the eigenvalues may be scaled by that constant. The true eigenvalues of the eigenfunctions { 2(1 X.).
then be estimated using equation Equation which states that [a(({(a1))
When the Markov chain has multiple communicating classes,
partition the eigenfunctions that each eigenfunction is nonzero on single communicating class. Since the scaling function acts scaling factor for each communicating class, the principal component functions will then be scaled copies of these partitioned eigenfunctions. We can then similarly estimate the true eigenvalues for each of these eigenfunctions using Equation
23

---

Published as a conference paper at ICLR 2023
D GENERALIZATION PROPERTIES OF THE EIGENFUNCTION REPRESENTATION
D.1 MIN-MAX OPTIMALITY OF EIGENFUNCTIONS
We now prove the min-max optimality of the eigenfunctions with respect to their L2 norm. (We note that these results are closely related to the Courant Courant-Fischer- -ess-ei---eeeeeee Weyl min-max principle (Bhatial 2013 Chapter IIII, which characterizes the eigenvalues and cigenvectors of a Hermitian matrix in terms of a similar adversarial game.)
Theorem 4.1. Let Fr = {a + rT((a)
Bd) be the subspace of linear predictors
from representation r, and Se be the set of functions satisfying Assumption 1.1 Let ra [f) (((o)....fa(())) be the representation consisting of the d eigenfunctions of the positive pair Markov chain with the largest eigenvalues. Then Feg maximizes the view invariance of the least-invarians unit-norm predictor in Frg:
F argmin dim(())dd GEF, E[g(a)11=1
max
Ept -
(5)
Simultaneously, F,z minimizes the (quadratic) approximation error for the worst-case targel function satisfying Assumption 1.1 for any fixed e:
BEF Ep(c) (o(() (pco) - )(
Frg argmin max min
(6)
dim(F)=d geS,
Proof. We will start by deriving Equation 6 and derive Equation afterward. We can think of Equation equivalent to the following adversarial game:
1. Player chooses a dimension-d subspace F C A + R of functions.
2. Adversary chooses function g A R with fixed level of invariance [[( g(az))) = 2g' (DA - PA.A)g = c. Without loss of generality, we let = 2 so that g (DA - PA.Agg = 1; other values of e will just lead to scaling the function g.
3. Player chooses the best و F to minimize El(ğ(a) g(a))
We can analyze this game by working backward from the innermost step. step 3. Given the function class F and adversarially chosen target function g, choosing 9 to minimize the expected squared error is equivalent to finding the orthogonal projection of g into F with respect to the measure p(A), e.g. with respect to the weighted L2 norm L(2;p(A)) More precisely, we want
argmin ((((a)) (00aa)-9(())) -{a)) argmin(g 8) DA(g g) gET
get
(D - D122 g) T(D 1/2 g)
argmin
DEF
But this is just finding the g F which minimizes 1ID1/2/ g orthogonal projection of the vector 22 g into D2/²F, under the ordinary L2 norm.
1/2 gll2.
2 This is given by the
We can now define R as the orthogonal projection operator on 1 F, such that Rh E 1/2 (e.g. D- Rh Rh F), and for 11/2fe D (e.g. f F), have 12/2f RD (e.g. f DJ 1/2 RD! Observe that R is real and symmetric, and has eigenvalue with multiplicity d and all other eigenvalues are O. Since R characterizes the subset, we will find it convenient to redefine our objective for the initial player as choosing R, and then letting F =D 1/2 RD g:gg:g... e:::::g440
We then have
g = argmin B((((v) o(v)) = D 1/2 RD
gef
24

---

Published as a conference paper at ICLR 2023
and the cost is
B[([()) - g(u)) -DX2 (D) -
8 g) -
(R
- =g ( 2
= g (I-)
We next consider step 2. Given R. what should the adversary pick? Letting L = DA - the adversary is constrained to pick such that Lg (L (L 1. We note that L is not full rank: particular, any eigenvector of M with eigenvalue is an eigenvector of of eigenvector zero. Any function chosen by the adversary must then be the sum of two parts:
a component in in the range of L, of the form (D+)1/2 u where ||u||2 = 1 and represents the Moore-Penrond pseudoinverse,
and component in the null space of L.
Overall, we can thus write = (Lt) 1/2 u h where ||u||2 and Lh = 0. Similarly, the response g must also have components, one in the range of L and in the null space of L. There are then two cases. F does not span the entire null space of L., the adversary can force an arbitrarily high approximation error by choosing
be in the null space L but not F. On the other hand. if F spans the entire null space of L, the player can always perfectly approximate h, and so the adversary is forced maximize cost by using u. In particular, they will pick
argmax (LT) u) T 2222(1 RR) (( u)
|1l|2=1
argmnaxu' T (11) D (I -R)D (LI) [|]|=1
-argmax T Au ||u|2=1
where A is the matrix (LI) (1- R)D (LI)a/2 The optimal choice for u is an eigenvector of A with maximal eigenvalue, and the cost then that maximal eigenvalue. But observe that M is similar to the following:
A A~ ((I)) 1/2 (
1/2 1113)
(I
(T (T-R) R.) (D := A'
Similar matrices have the same eigenvalues, so the maximum cost attainable by the adversary the maximal eigenvalue of A'.
Finally, we consider step 1. Which It should our player choose to minimize this maximum cost? They should first ensure the cost is finite, by choosing R to span the null space of D= I., 1/2 (Note that if is less than the dimension of this null space, there is no choice that ensures a finite cost; in this case every representation has unbounded worst-case approximation error.) Afterward, they should ensure that A' has the smallest maximum cigenvalue. The sorted vector of eigenvalues of A'
is bounded below by the vector obtained by matching the largest eigenvalues of
with the smallest of (I R)) (Bhatia 2013 exercise III.6.1 1..14 Let d' be the dimension of the null space of D 1/2 1/ 1/2 1/2 Then R has d eigenvalues with value 0 (i.e. 0 is an eigenvalue with multiplicity d). Of these, d" must be used span this null space, and the remaining - d' (if any)
wtw.sllotttts///c /noth, stekeechhagge www.gee...oo//ogge.e.eeeee lona 3/e genoell lea- of-tttttteeeeee te-ttth---rrccc of tww- symnerrio-.... net-nes
25

---

Published as a conference paper at ICLR 2023
can be used to reduce the eigenvalues of A'. Thus, the largest eigenvalue of A' is always least as big as the (d - d' + 1)-th largest cigenvalue of 1/) We can attain this bound by setting R to exactly capture the (d- dimmenisiin subspace of 1 1/2 spanned by its top eigenspaces, along with the d'-dimensional null space of D 1/2 LD 1/2
But the combination of the null space of LD and the top eigenspace of (D2
just the space spanned by the d eigenvectors of D D/ LD with the smallest eigenvalues. Furthermore,
DĀ 1 LD = D PA
= =I- 1/2 PA,A, 1/2 = -I-M- M,
so we are looking for the eigenvectors of M with the largest eigenvalues, where M is the matrix described in Appendix C
Thus, the player should choose F such that D1/23 F spans the top d-dimensional eigenspace of M, e-g. they should choose functions of the form D-1//2 v; where the Vi are the eigenvectors of M with largest eigenvalue. But these are exactly the left eigenvectors f, of the positive pair Markov chain, which how r is defined. We conclude that F,g the optimal choice for the player, and thus Equation 6 holds.
Indeed, we can conclude something further: Ad+1 is the (d + 1)th eigenvalue of the positive pair Markov chain (the variance along the (d + 1)th principal component of the positive-pair kernel), then 1 as long as d 2 d", (1 > is the (d d' + 1) 1t eigenvalue of (D 1/2 which is exactly the worst-case approximation error for Frg against any function with [[(((v]) - ((2)) = 2g Lg 2. Scaling by if [[((((1) ((v2)) then the worst case error is / Adt1). In other words.
Ep(a) (o(a) ((a)) ?| 2(1 - xa+1)
max DES.
min SEF
We now return our attention to Equation game:
This equation can also be formulated as an adversarial
1. Player chooses a rank-d subspace C A - of functions.
- D 2. Adversary chooses a function with unit norm E[ğ(v)?] - [[(((())) ((v2)) 2g Lg.
maximize
We can again identify the choice of F with the choice of the orthogonal projection matrix R on 1//2= F. We know I F, so we can write g =
Also note that for any h (not even necessarily in F), D ///DD//2 1/2 F. Now suppose we choose an h so that ([h(a) h Dah = 1, and
A 1/2h. Then
define g 1/2 RD)
g T
DAg = 1 DT RD DA(D= (2
= h 2 R//222220
h
< h 1D) hh
because At has eigenvalues at most 1. So, the following are equivalent:
choosing F with [v) <
choosing h R with (v) < 1 and letting & 12 RD
26

---

Published as a conference paper at ICLR 2023
We also note that there is advantage to the adversary from picking function such that Elğ(u) 1. So we can reframe step 2 as choosing h so that [[h(v)? 1, to maximize
2DD
L (DT|/2RD'''
We can further reparameterize by letting |||| 1. We then have cost
D 1/2 u, so that B[h(v)²] = is equivalent to
C = 2g RD "
=2u -22JRR (RDR LD
1/2 1/2 Ru
The choice that maximizes the cost is then eigenvector of
(1. 22D
(T. (1./22
with maximal eigenvalue, and the cost is times the maximum eigenvalue of B. But note that B has the same eigenvalues as
B' = (11D (LUED
= L//2 RD 1/2 1/2
since R² R. And B' is similar to
B" D DD
so B and B" have the same eigenvalues.
We now consider step What should the player choose for R? By similar eigenvalue-of-pree of-rrduuct argument as used for Equation 6 regardless of the choice of R the largest eigenvalue of B" must always be at least as big as the dth smallest eigenvalue of D 11122 LD LD because R has eigenvalue 1 with multiplicity d. We can attain this minimum cost by choosing R to project into the eigenspace spanned by the eigenvectors of D 1/2 D/1/2 LD 1/2 with the smallest eigenvalues.
But observe that the smallest eigenvalues and corresponding cigenvectors of D LD = I-M are exactly the largest eigenvalues and corresponding eigenvectors of M - 11/2
PA.AD
L, which as we argued above, is exactly the set of eigenfunctions fi used to construct rd.
In this case, the optimal cost itself is determined by the largest eigenvalue of D LD 1/2 (times two), so obtain
max Ep- [((a)) {(az)) = 2(1 - -da).
hET,
-1
D.2 GENERALIZATION BOUND FOR LINEAR PREDICTION WITH THE EIGENFUNCTION REPRESENTATION
Proposition 4.2. Let Y.Y be i.i.d. samples, choose R 2 and consider the constrained
empirical risk minimizer OR E arg E8 r Vi). Then the expected excess risk of 3R is bounded by:
E [(((R))
<
2dR Vn
+ Vd(1131112 R)+ + V 2(1 \d+1)
8
where {() = R(B) -R* is the excess risk and (x)+ max max(x,0) 0}.
27

---

Published as a conference paper at ICLR 2023
Proof. We start by decomposing the excess risk as:
R(3R)- R²
(R((R))
inf 11
R(B)) + (niin inf R(3) - R(3) |101|
-(3))-((8))) + (R(8)) - R*)
The first term is the estimation error, which we can readily bound by first noting that:
B (A) E Σ M(A)
Σ
B[A(AA)]
then noticing that our loss is 1-Lipschitz, and finishing with the standard Rademacher complexity argument for constrained linear classes Kakade et al. (2008) to get:
R((RR) inf 118
R(3)
2dR
VT
The second term is approximation error term due the use of constrained linear class instead of 9"
the full linear class, Define 3 : max 18 la/ R, Then we can bound this second term by:
inf - - R(8*)(()))) & R(33) - R((3)
|
< E ( -A
(8)
< E
$ vd(II - R)+
where the second inequality follows from the 1-Liipchitzzes of the loss, the third by Cauchy-Schward inequality, and the last by Jensen's 's inequality.
The third and last term is an approximation error term due to the use of the function class given by the span of the first d eigenfunctions (f:) We can bound it as follows:
R(8") - R² s E (A)),))))) (A)Il
Bl((r (A))²] S 2(1 Ad+1)
where the first inequality follows from the 1-Lipschitznes of the loss, the second from Jensen's inequality, and the last by first noticing that the function h(a) == (r) satisfies h argmings... EE (A) g" [A))²] (since it is the projection of g" onto Fry under the norm
||>|| := (AA) ). then appealing the proof of Proposition 4.1 Combining the bounds of
equations and (9) we obtain the stated generalization bound.
28

---

Published as a conference paper at ICLR 2023
E EIGENFUNCTION ESTIMATION TECHNIQUES
In practice, we do not generally have access to the closed form for K+ or the the full population of our examples, but instead only have access to dataset of positive pairs (a1,02) drawn from the distribution p+ (01, (2) (or, more commonly, a dataset of examples z and sampling algorithm for p( p()(Z)). In this section we discuss some approaches for approximating the optimal eigenfunction representation from these samples.
E.1 COMBINING CONTRASTIVE LEARNING WITH KERNEL PCA
Our analysis in Sections 2 and motivates the following procedure:
1. Train a contrastive learning model using an existing contrastive learning objective.
2. Using the equations in Table 1 identify the approximate kernel Re, which will hopefully be similar to the positive-pair kernel K4 assuming we have converged to a solution to the objective.
3. Perform (or approximate) Kernel PCA using Kg and large set of individual views drawn from p(A).
4. Use the first d extracted principal component projection functions h; : A + R to construct representation, possibly normalizing by a, to obtain the orthonormal basis fs(a) o, (a())
We note that applying a rotation matrix to the optimal representation does not affect the expressivity of that representation. is thus sufficient to identify the subspace spanned by the first d principal component projection functions. If the representation dimension d is known in advance, it may be possible to adjust the contrastive learning method to accomplish this without requiring a separate PCA step. In particular, when using the spectral contrastive loss with a d-dimensional linear kernel head, the population minimizer the loss will exactly correspond to the best d-dimensional approximation of K4. This means that the output layer representation will be exactly the of principal component projection functions rotated by some orthogonal matrix.
On the other hand, including the PCA step makes it possible to decouple the representation dimension from the kernel approximation method, which may be advantageous if the learning dynamics of different parameterization or loss are better, or if d is not known in advance. The PCA step also makes it possible to diagnose how well the learned representation is capturing properties of K by checking the extent which Equation is satisfied.
Directly applying kernel PCA can be expensive for large datasets, due to the need to decompose the full Gram matrix of kernel similarities. A more computationally-fiinntii approach to first approximate K₂ with a lower-rank approximation, such as the Nyström method WWlliams & Seeger 2000), and then perform PCA over that approximation (Sriperumbudur & Sterge 2017] Ullah et al. 2018 Sterge et al.] 2020). This can be especially useful when the dataset is much larger than the number desired cigenfunctions.
We note that approaches based on Kernel PCA may be numerically unstable in the presence of many eigenvalues close 1, since small kernel estimation errors may be amplified by the eigendecom- position process. Although we were able to apply these techniques to models trained on our two synthetic datasets, we have been so far unable obtain a reliable estimate of the eigenfunctions for real-world datasets such as those considered by Chen et al. (2020a). In particular, we attempted to apply the Nyström method to a pretrained SimCLR model ran into numerical precision issues and were unable to form a good approximation of the learned hypersphere-bee based kernel Kg. See also Appendix
F.3m for preliminary analysis of model with constrained-non linear kernel head on ImageNet; although we were able to run Kernel PCA with this model, does not appear to be good approximation of K_.
29

---

Published as a conference paper at ICLR 2023
E.2 DIRECT EIGENFUNCTION EXTRACTION, AND CONNECTIONS VICREG
An alternative strategy for estimating the eigenfunctions fi is to combine the contrastive learning and Kernel PCA steps into a single parameterized model. This is possible using parameterized spectral decomposition techniques such as SpIN (Plau et al. 2018) or NeuralEF (Deng et al. 2022).
We note that these techniques are usually motivated extracting the eigenfunctions of the kernel daz, or in other words, solving the eigenfunction
operator T[f((a)) = f K (a1, equation
xafi(an)= / K(ai, (2) daz.
In this case, substituting the form of K+ reveals that this is equivalent to finding the eigenfunctions of the positive pair Markov chain:
Xefi(an)= Σ K4 (2) =
Σ
D+ 02)
si fi(a2)p(a2)
p(a1) ((a))p(a))
pt (+(an, u2) p(an)
f(((2)
p(azla1)fi((2)
Eazla [fa())]
Connections between NeuralEF and VICReg. We now describe more detail how to apply the NeuralEF technique to estimate the basis of eigenfunctions of the positive pair Markov chain. The NeuralEF approach approximates the eigenfunctions f. of a kernel K by solving an asymmetric set
of constrained optimization problems fy = argmax,, R35 Ei=o R² subject to the constraint that Cj = where where
Rae
Rij = Σ (laa 01 02
c = =
Substituting the positive-pair kernel K+ (a1, a2)
p+ (2))02) reveals an alternative form for the Riş plai)p(as) p((2))
terms, allowing us to apply NeuralEF using samples from p+:
R₂ Σ ((l) P+(e1,a)) f (pa)) = (p- [aa)) p(ai)p(as)
Interestingly, the resulting algorithm closely resembles the Barrane-Invarrine--Cvvaiai larization (VICReg) self-supervised learning method proposed by Bardes et al. (2021): the Cj- = 1 constraint ensures each function has sufficient variance, the R2 term reduces the covariance between
regu-
features, and maximizing R,j = are as invariant possible between positive pairs. (Note, however, that the asymmetrie weighted R²; covariance penalties Ris NeuralEF ensure that eigenfunctions are recovered in the correct order without interfering with one another.)
Eif, (f)) (a2)) over positive pairs leads to representations that
Stabilizing NeuralEF for contrastive learning. Althoug the NeuralEF-based approach works well when R3 large for all i, the method becomes numerically unstable when R&s small. And since R2 Ry A; this makes it difficult to recover eigenfunctions whose eigenvalues X; are close to zero.
To enable recovery of all eigenfunctions, including those with X; = 0, we do not directly apply Neural EF to K4 in our experiments. Instead, we construct modified kernel with the help of modified positive pair distribution
Pmix (a), 02) = 0.5p (a), 02) + 0.5p(a)) = ail
where [[a a1l is when 01 02 and 0 otherwise. Conceptually, with probability 50%, sample a positive pair (a), a2) as normal, and otherwise, we sample a single augmentation aj and then choose 02 a1-
30

---

Published as a conference paper at ICLR 2023
The corresponding positive-pate pair Markov chain transition matrix can be written
mmix 0.5P + 0.51.
follows that the eigenfunctions for this modified distribution are the same as those for our original positive pair distribution, but the eigenvalues are transformed according Xmt 0.5A, 0.5. We can thus apply Neural EF to the corresponding kernel K K+ (a1, 02) Pmix (11, 42) (2((p((a) (tp(((()((()))))) (p((2), and recover the original X, by inverting this transformation.
Substituting this into the Neural EF objective, we obtain
f((1)) Pmix (mix(a) 02) ((02)p((1)p(aa)) p(a1)p(az)
Rmix Σ
d1, d2
(1( P+ (a 02)
0.5
Σ
ij
((2)(())))))))))())))))) (02)p(a1))((2)
p(a1) ((2))
plar)1102= anl (22)p((()))( p(a1)p(us)
0.5 Σ
f((a))
01
0.5 Σ
(a), a2) +.5
Σ Hoailf/oo0)laa)llle ail a1, az
G1, 82
0.5 Epp (2))02) (f((1)) + 0.5 Byto)) [Aaa)f
We then estimate remix in each minibatch by averaging over minibatch positive pairs for the first term and over all minibatch augmentations for the second term. (In practice we drop the 0.5 scaling factor in the loss.) We find that this modification greatly stabilizes the Neural EF objective when estimating large numbers of cigenfunctions, and in particular makes it possible to learn cigenfunctions of K with eigenvalues that are very small even zero.
31

---

Published as a conference paper at ICLR 2023
(6-32) B learned
(d=32) b leames, XEnt Logisik
Unear (d=64), Random Inkiaizztion
Linwar (d=64), Spectral
Trus siperfunciion
Random inkalization
Neural EF (dm644
1rut Dapmoaces
20-
20-
20
10
33
10
30
20 Lowmes Fipenfunctione
32
20
Eiaelunction
Leamed Egentnncians
Leamed
Leamed Eipertancioon
230 0039
1.5
1.0
1.0
0.5
0.3
2.0
Eger aa
Egenvsttc A
Eggeroluc
Bistnouie
E
Hypeesphete (di12)
Hypersphere leammdd Logatic
Hypersphere blcarred. Spectral
hypershhere
Hyperssh kamed, Xint + Log shit
lcamed.
b- Xfint + Logistic
Linear (d-18)) Spectral
constraint (10). Spectral
Thes compasse
Xfint
20
20
20
El0hi- Sailgg
Eyenwali
Figure 6: Figenfunction and eigenvalue estimation accuracy the overlapping regions task, for a selection of models. Top row: Alignment between true eigenspaces and the learned kernel principal components, with perfect alignment shown as block diagonal matrix. Bottom row: Relationship between learned kernel eigenvalue À and the corresponding positive-paii discrepancy Ep+ [(f(as) - {[ with the relationship predicted by Equation shown with dashed line.
F EXPERIMENT DETAILS
In this section we describe our experiments and their results in more detail. We start by presenting the full set of results summarized in Section Gl Figure We then describe details regarding model training. We conclude with some additional preliminary results regarding supervised learning with Kernel PCA representations on MNIST and eigenfunction extraction on ImageNet.
F.1 ADDITIONAL EIGENFUNCTION ESTIMATION RESULTS
Overlapping regions task. Results for our full set of models on the "overlapping regions" task are shown in Figure
We find that, under suitable losses, linear kernels, hypersphere kernels. and NeuralEF can all produce good approximations of the basis of eigenfunctions, despite their diferent parameterizations. Specifically, unconstrained-noome linear kernels with the spectral loss, hypersphere kernels with learned bias under either a XEnt-Logistic loss mixture or the spectral loss, and the NeuralEF eigenfunction estimation method all produce eigenfunction estimates that are reasonably aligned to true eigenfunctions, and eigenvalue estimates that are close to the true eigenvalues. However, especially for eigenspaces with similar eigenvalues, the eigenfunctions occasionally appear in the incorrect order, and have a small amount of mixing between eigenspaces. The relationship between approximate eigenvalues and positive- pair discrepancies also closely matches the prediction from Equation
We note also that alignment with the basis of eigenfunctions emerges during training, and is not simply a property of the model architecture, as evidenced by the lack of alignment when applying Kernel PCA to randomly initialized models.
The loss function used influences the learning dynamics and final result. Using the XEnt loss alone produces reasonably-wer aligned eigenfunction decomposition, but has eigenvalues scaled by
32

---

Published as a conference paper at ICLR 2023
Uheaf
pyperanere e 1126, Soile, Hypamptenn Godda
(b) & 10 (stronger aug.)
10
14 Pinwniry
20
250
250
256
56
260
16
150
(c) k 50 (weaker aug.)
20 (medium augmentations)
Figure 7: Alignments and discrepancy relationships for principal component functions on MNIST task for three augmentation strengths. Top row: Alignment (squared dot products) of the first 20 principal component functions between runs of Kernel PCA on different kernels, with perfect alignment corresponding to a diagonal matrix. (Left column shows alignment between two independent runs of Kemnl PCA on the true kernel K..) Middle row: Relationship between eigenvalue À and positive-pan -eiir discrepancy for the first 256 principal components (omitting any with = 0), with the prediction from gray dashed line. Bottom row: Ordered eigenvalues for each approximation,
Equation 4 shown relative to those of the true kernel (dashed line).
constant, since the XEnt loss only measures ratios between kernel evaluations and thus only recovers the kernel up to a constant factor (discussed in Appendix B.T]. The Logistic loss alone appears to lead to inferior decomposition quality, although eigenvalues are in the right order of magnitude. Interestingly, the spectral loss seems to work even for hypersphere kernel approximations, although found it to be the most unstable; successfully training hypersphere kernel with the spectral loss required initializing the bias b to a large negative number.
Constraints the kernel approximation degrade eigenfunction and eigenvalue estimates. For the hypersphere kernel, fixing the bias b to zero led to eigenvalues that were abnormally small, whereas reducing the dimensionality the hypersphere from 32 both degraded eigenfunction alignment and led to deviations from Equation 4 For the linear kernel, using a smaller dimension led estimating only the eigenfunctions with larger eigenvalues, and imposing a norm constraint of [| = 10 both reduced the number of accurately -cppturdd eigenfunctions and caused the eigenvalues be smaller than predicted by Equation
MNIST task. Figure
Results for our full set of models at three augmentation strengths are shown in
We compare two types of hypersphere kernel parameterization: "global scale" version using exp(ho(a1) (az)) + b) and "local scale" version using exp(ho(a1) he((2) (/////rr /r + s0())) + sp(az)). The second is more expressive, but the first is closer to that considered by prior work such as Chen et al. (2020a). (Note that most work with hypersphere-basse
models fixes b = 0, but also uses the XEnt loss alone, which is not affected by the value of b. We include b and include the Logistic loss to assess how well the models can recover the correct values of the eigenvalues.).
Note that, although can exactly evaluate K4 any pair of augmented views, the space A (containing all multisets of & pixels) is too large to enumerate, preventing us from exactly computing the exact eigenfunctions of K4. Instead, use Kernel PCA the "ground truth" eigenfunctions. To better understand the impact of this step, we also include a comparison between two independent runs of Kernel PCA on K.,.
large set of samples to estimate
Weaker augmentations make principal component estimation difficult. We find that Kernel PCA can more reliably recover principal components with large gaps between eigenvalues, and is influenced
33

---

Published as a conference paper at ICLR 2023
by random noise as eigenvalues become closer together. In particular, augmentation strength decreases, there are more eigenvalues close to 1, and it becomes more difficult to identify the most significant principal components. Due to the stochasticity of Kernel PCA, it is difficult to accurately identify eigenfunctions even when given direct access to K+ and two runs of Kernel PCA begin to diverge as eigenvalues decrease. Figenfunction quality degrades even faster when comparing results of Kernel PCA for learned model and for K+: the learned models only allow recovery of a few principal components accurately at larger augmentation strengths.
More expressive kernel approximations recover more eigenfunctions. We observe that the linear kernel head and Neural EF method are able recover larger number of eigenfunctions accurately compared to hypersphere kernels, and have eigenvalues that lie closer to the Equation I prediction. Additionally, we find that adding per-example scale function 8p to the hypersphere kernel leads to more correcely-reovveeedd eigenfunctions and fewer outlier eigenvalues.
Learned models have faster eigenvalue decay than K+- In general, the eigenvalues of learned kernels decay faster than the eigenvalues of the true positive-pair kernel K+, Interestingly, however, the eigenvalues still appear to follow the relationship predicted by Equation A for sufficiently expressive models and sufficiently strong augmentations. This suggests that the learned models are approximately capturing a subset of the positive-paii cigenfunctions.
We note that both the linear-kernel-iee hhad model and the NeuralEF model exhibit sharp change in eigenvalue near the 100th eigenfunction: the first shows a sudden drop to zero, whereas the second shows strange "jumps" larger eigenvalues. We believe this corresponds identify additional directions of variation, leading to a lower-rank kernel approximation than expected. For NeuralEF, this manifests as essentially repeating earlier eigenfunctions instead of finding new orthogonal directions.
failure to
The authors believe that one promising research direction for finding better self-supervised learning techniques would be to develop more stable or better-conditioned lincar approximations of the positive-pait kernel, building on the spectral contrastive loss or NeuralEF. In particular, we see this as evidence that the parameterizations we used are not able to form good approximations of the true minimizer of the respective objectives. We hope that such techniques could be developed by combining ideas from the kernel methods and superviee learning communities, and that they would lead to useful representations for downstream supervised learning as suggested by our analysis.
F.2 TRAINING DETAILS: OVERLAPPING REGIONS TASK
For each of the models visualized in Figure 6 we use a simple three-layer MLP with hidden layer sizes [64, 128, 256] which maps from the two-dimensional location of each grid point to the final kernel-dependent output embedding. We train all methods for 12,000 steps using a batch size of 1024 perpenddentl--saaplle positive pairs per iteration, using the Adam optimizer (Kingma & Ba 2014) with a desane-decay learning rate schedule.
For the hypersphere kernel head Ko(ai,a>) regularization penalty encouraging b be small, which stabilizes training with the XEnt loss (since the loss is otherwise independent of b). When using the "XEnt Logistic" loss mixture, we combine the two losses using a weight of 0.9 for XEnt and 0.1 for Logistic.
exp(he(ai) (02)) + b). we include small hep(hh((a)TTa(a)//F
For all methods other than Neural EF, we used batch normalization for the first 6,000 iterations, then interpolated between the current batch statisties and the average from previous batches for 2,000 more iterations, and finally trained for 4,000 iterations using frozen batch norm statistics alone (e.g. in "inference" mode), which we found slightly improves eigenfunction quality. For Neural EF, we keep batch normalization at all steps, and in particular use L2 batch normalization for the output embedding as proposed Deng et al. (022).
To extract eigenfunction estimates from our kernel models, we compute estimates of the eigenfunc- tions and cigenvalues by performing population kernel PCA over the values of the kernel across all elements of A, weighted by p(a). For the NeuralEF model, we instead directly use the model's outputs as the eigenfunctions, and use running averages of Ra to approximate eigenvalues.
For Figure d we compute the alignment between eigenfunctions by taking their squared uncentered covariance E (a)) Note that by Theorem 3.2 this is equivalent to the square of the coefficient
34

---

Published as a conference paper at ICLR 2023
C2 for the function fy expanded in terms of the basis of eigenfunctions fi: consequently have Since the specific choice of eigenfunctions is not uniquely determined when there are multiple eigenfunctions with the same eigenvalue, we sum the alignments for all eigenfunctions that have the same eigenvalue, leading to the block-diagonal structure shown in 6 We computed the positive-pair discrepancy for each approximate principal component function by analytically summing over all possible positive pairs.
Σ, {a) Eff [a)²]
Population look-up table variant In Figure 4 we use modified procedure to improve visualiza- tion quality. Instead of using a MLP, we instead directly learn a lookup table of positions &a E I² and scale modifiers &a E [-5.0, 5.0] for each point A, and use rational quadratic kernel head
Ro(ai, 02) = e (1- 1|vag
Vaz 1|
2a
where a is a learnable parameter. (The size of each marker in Figure S represents the learned scale; we find that using the scale modifier improves eigenfunction quality, and note that more tightl-cllsteree points tend to have slightly smaller scales.)
We train using full-batch variant the XEnt and Logistic losses. For the XEnt loss, we compute
CxEar (0)
Σ p- (a1, a2) log (a(()))))
where
(a a1) & (o
(Here weighting the kernel by p(a2) can be viewed as the population equivalent sampling set of negative pairs as the number of negative pairs approaches infinity.) For the logistic loss, we analytically compute
Logistic (0) E
pi (af ,at) [-
log (log Rolaf aa)))
E ((TT)((77)
[- log (ogoollogg log Rolaj a (]
by summing over all possible positive and negative pairs. We use relative weights of 10 Logistic
We population kernel PCA over the set AA to identify the principal component functions. We then extend the principal component functions fi : A - IR across the full embedding space h; : RR > R
(ignoring the scale parameter for simplicity) according to
hu(v) = Ro(e, A) Ro(A, f((A),
where Ro(v, A) is the vector
| -0
cn
2nx
|| - Vag
22
Ro(v,A) A)
2cx
La (1
11u-va Va LAl
11?
2cx
A), A) is the Gram matrix of the sequence [Q1...., Ay] (in other words, the matrix elements are defined by [Ro(A, = Ro(as, a,)), denotes the Moore-Penrose pseudoinverse, and (:(A) the vector [fr) fi(a2) [a) this equation implicitly projects each point onto the appropriate principal component of the kernel. For numerical stability reasons, we regularize the pseudoinverse (A, by additionally removing cigenvalues very close to zero.
F.3 TRAINING DETAILS: MNIST WITH MULTINOMIAL AUGMENTATIONS
Our goal in designing our task was to construct distributions Z(Z) and p(A[Z) such that the exact positive-pain kernel could be computed, and that the Markov chain would mix between different unperturbed dataset examples E Z without changing the label too frequently.
To this end, constructed task follows:
35

---

Published as a conference paper at ICLR 2023
Define Z to be particular subset of the MNIST dataset, and choose p(Z) ) to be the uniform distribution over Z. We consider two choices for 2: randomly selecting 512 images from each of the ten digit classes (used for comparisions between models), and randomly selecting 1024 images from the digits O, 1, and (used for visualizations of the eigenfunctions).
For each image, generate 64 pertubed copies, by randomly blurring, translating, and rotating digits by small amount. Add a small constant to each pixel so that pixel has value zero, then normalize each such copy so that its pixel values sum to
To generate an augmentation of an image 2 E according to p(A = 2), first choose one of the 64 copies of 2, then sample set of k pixel locations with replacement from the distribution represented by that copy, where determines the augmentation strength. This means we are more likely to sample pixel locations which were within the original digit, although due to the perturbations described above the pixels may be scattered around the digit.
Our set A is thus the set of all 28 x 28 images for which all pixels have a nonnegative integer value, and the total of all pixels is k. (Due to the low pixel density, to improve visibility in our figures we render each pixel as a box 5x its original size, with shading indicating overlap of these boxes. However. when giving input to the model, we directly input this sparse pixel reprsentation, without the 5x multiplier.)
Given a particular augmented example a, we can compute p(a|z) for any E by summing over each of the 64 copies of and using the closed-form PDF of multinomial distribution. We can then compute p(=[a) by normalizing over all possible z, and use this to exactly compute the positive-pair kernel feature map 64. We selected the perturbation parameters such that there was nontrivial uncertainty in = given each o; in other words, we made sure the positive pair Markov chain mixed well between examples.
F.3.1 MNIST MODEL ARCHITECTURES
For the majority of our experiments, we used three-block variants of a ResNet- 18 model followed by a two 128-dimensional fully-connected layers and final output layer.
Linear kernel: We used kernel parameterization Ra(01, 42) ha hh ha and the spectral loss, with he as the output of the final layer. We set the dimension of the final layer to 512. We trained this model using the spectral contrastive loss.
Hypersphere kernel, global scale: We used kernel parameterization exp(ho(a;) T ha(4))/T= T++ b), where hg is computed by normalizing the output of the final layer to lie on the unit hypersphere, and i is learned scalar. We set the dimension of the final layer to 32. We optimized the temperature and scale jointly with the model parameters. For the loss function, we used weighted combination of 0.9 times the NT-XEnt loss and 0.1 times the NT-Logistic loss.
Hypersphere kernel, individual scale: We used kernel parameterization exp(ho(a1)) (a2)/ (oopho(()""h(aa))/r1++ + s0(a)) + (az)). We set the dimension of the final layer to 33, and defined hgg by taking the first 32 entries and normalizing them to lie on the unit hypersphere. We then defined 89 to be 5 x lanh(v33) where V33 is the 33rd entry of the final layer. We again optimized the temperature T jointly with the model parameters. The scale parameter allows the model to adjust the magnitude of the kernel on basis, which can be used to scale the eigenvalues of the principal components or to correct for differences in likelihood between points (since the magnitude of K4 depends the marginal likelihood of each point). For the loss function, we again used a weighted combination of 0.9 times the NT-XEnt loss and 0.1 times the NT-Logistic loss.
Neural EF model: We set the dimension of the final layer to 512, and used L2 batch normalization on this final layer to ensure that the L2 norm of each output was I (e.g. that Cj = 1), described by Deng et al. (2022). We used the modified version of the Neural EF objective described in Appendix E.2
We trained our models using the Adam optimizer (Kingma & Ba 2014) over 50,000 training iterations and batch size of 4096 positive pairs per iteration, implemented using the JAX and FLAX libraries
36

---

Published as a conference paper at ICLR 2023
(Bradbury et al. 2018 Heek et al. 2020). For methods other than Neural EF, used batch normalization for the first 35, 25,000 iterations, then interpolated between the current batch statistics and the average from previous batches for 2,000 more iterations, and finally trained for 13,000 iterations using frozen batch norm statistics alone (e.g. in "inference" mode); we found that this increased the quality of the extracted principal components. For Neural EF, we keep batch normalization at all steps due to the constraint that Cj
F.3.2 EXTRACTION AND ANALYSIS OF PRINCIPAL. COMPONENTS
To estimate the eigenfunctions of the true kernel, we performed PCA using the explicit form Ø+ of the positive-pair kernel feature map, where the population covariance was approximated by averaging over 256 augmentations for each of the images in 2. We then constructed the principal component projection functions using that covariance. Our alignment plots in Figure for "True kernel" compare two PCA decompositions using independent random estimates of the population covariance.
For our approximate kernels Kg. we first constructed an approximation of the feature map for Ro using the Nyström method (Williams Seeger, (000): we sampled a subset of augmentations by randomly selecting 25% of 2 and sampling one augmentation for each image, computed the Gram matrix (5(S, S) for that subset, then set
((a) = Ro((,,))\/2R((55)
where (S(S, a) is the vector of similarities of each reference augmentation in S. The result is feature map such that ((a1) ((az) = Kg (a1, a2). We then again performed PCA using this feature map, using 256 samples per example in Z to compute the covariance.
For the Neural EF model, we again directly used the model's s outputs as the eigenfunctions, and use running averages of Ra to approximate eigenvalues. We note that the Neural EF method did not find a fully orthogonal basis (as indicated by nonzero Rıj terms for * j). and some of its later eigenfunction estimates were correlated with earlier eigenfunctions; we did not attempt to correct for this in our plots in Figure 7 We believe this is the cause of the "jumps" from smaller eigenvalue approximations to larger eigenvalue approximations. (In contrast, the approximate eigenfunctions from the kernel PCA approaches are by construction uncorrelated over the sampled augmentations, due to being derived from eigenvectors of the sample covariance.)
We normalized all principal component projection functions to have unit uncentered variance, e.g. (a)²] = 1 and "a) = 1. As for the overlapping regions task, we then computed alignments by taking the squared covariance (a)] We estimated the positive-pair discrepancy for each principal component function by taking the sample average of (fi(ai) - f((a2))² over 16 randomly sampled augmentation pairs for each image in 2.
F.3.3 THREE-CLASS MNIST RATIONAL QUADRATIC MODEL
For Figure D additionally trained ResNet-13 18 model only the MNIST digits 0, 1, and 2, using a scaled two-dimensional rational quadratic kernel:
Ro(ai, (2) (a (s)( (1 [[o((a)) fo fo(()))1
(10)
2xx
Here fo : A + R² embeds inputs into the plane, 59 : A + R+ a learned scale function, and a is a learned shape parameter. We set the output dimension of the ResNet-18 model to 3, and took the first two elements as fet 88 was defined as exp(5 lanh(x)) where z third element. We also parameterize exp(r) and learn the scalar parameter y. The model has base hidden dimension of 128. The model was trained for 50,000 training iterations. We used the cross entropy InfoNCE loss (as described in Appendix B.I. and the Adam optimizer, with batch size of 4096 positive pairs per iteration.
37

---

Published as a conference paper at ICLR 2023
Classification
Regression
of sampled pixels
10
20
50
10
20
50
True (K+)
PCA
0.564
0.384
0.178
0.722
Learned (Linear)
Kornel PCA
0,589
0.398
0.254
0.724
0.603
0.362
ResNet Emb.
0.553
0.375
0.229
0.730
0.567
0.459
Learned (Hypersphere, Global Scale)
Kernel PCA
0,594
0.401
0.722
0.559
ResNet Emb.
0.561
0.371
0.229
0.737
0.602
0.518
Learned (Hypersphere, Local Scale)
Kernel PCA
0.583
0.392
0.276
0.718
0.552
0.524
ResNet Emb.
0,575
0.380
0.206
0.742
0.599
0.522
Learned (Neural EF)
Learned Eigfns.
0.576
0.398
0.199
0.727
0.561
0.389
Emb.
0.575
0.389
0.204
Table Classification error (fraction misclassified) and regression error (squared error) on MNIST task with multinomial augmentations, across augmentation strengths k = 10, k = 20, A: = 50.
F.4 DOWNSTREAM SUPERVISED LEARNING ON MNIST
To better understand the performance of the true and approximate eigenfunctions for downstream supervised learning, we took our multinomial -aapolinn- MNIST task, and compared the quality of various representations for two downstream prediction tasks: classification with linear layer, and linear least-squares regression on the one-hot indicator vectors for each digit class. We considered three types of representation: the PCA projection functions for K4, the PCA projection functions for
each learned kernel Kg. and the intermediate layer embedding vector between the ResNet layers and the projection head for each model as proposed by Chen et al. (2020a). For each, we fit regularized linear predictor on 160 labeled training examples (16 augmented samples from each class), using 160 additional validation examples to tune the regularization strength. For PCA representations, we additionally tune the representation dimension d, choosing only the first d principal component functions.
The results are shown in Table 2 Performance is fairly similar across representations, suggesting that the positive-pair kernel K+ captures much of the variability between augmentation strengths. Notably, at low augmentation strengths (k- = 50), the true eigenfunctions have the smallest error, but eigenfunction approximations using Kernel PCA do always outperform the intermediate layer representations, suggesting that inductive biases may play role.
In more detail, to generate our supervised training and validation sets, we sampled one augmentation of 16 random images from each digit class, labeled with the original label, a total of 160 labeled augmentations in each set. For the test set, we took 170 distinct images from each digit class and generated one augmentation from each image, without overlap with the training or validation sets, for a total of 1700 labeled augmentations.
For the classification task, we fit a logistic regression classifier on the training set using SciKit Learn. For PCA representations, we swept over logarithmically-spaeed L.2 regularization strengths from 10-1 to 10 and also swept over representation dimension d, taking the first d principal components for d between and 256. For ResNet embedding representations, we swept over 150 logarithmically- spaced L2 regularization strengths from 10 to 10th; found that higher regularization strengths were necessary to attain a good solution. We selected the hyperparameters based on which setting gave the highest t accuracy the validation set.
For the regression task, we used a centered version of the one-hot indicator vector, e.g. the target vector for example from digit 2 was
[-0.1, 0.1, 0.9, - 0.1, 0.1, 001, -011 -011, -0.1, -0.1].
The purpose of this centering was to ensure that the expected value of the label vector was the zero vector. We then fit a predictor using ridge regression (L2-regularized least-squares regression) in swept over 40 logarithmically-
Numpy. As for the classification task, for PCA representations spaced L2 regularization strengths from 10 4 to 10' and over each representation dimension between and 256, and for ResNet embedding representations swept over 150 I.2 regularization
38

---

Published as a conference paper at ICLR 2023
Simple NLF model synticic owatlspping regions
Rested ISimCUR v2 mudd Imrgghhed 2012
1.75
3.75
1.22
4.20
6.72
0.75
0.2
6.25
0. 0.2
0.
3.8
1.6
2.8 0.2
04
Figure 8: Relationship between kernel PCA eigenvalue and positive-pair discrepancy for a norm- constrained linear kernel head and the spectral contrastive loss, across two datasets. Relationship predicted by Equation is shown with a dashed line. Eigenvalues smaller than 10 are omitted.
strengths from 10 10-4 to 10t0, We selected the hyperparameters based on which setting gave the lowest squared error on the validation set.
F.5 PRINCIPAL. COMPONENTS ANALYSIS OF SPECTRAI--LOSS LINEAR KERNEL MODEL ON IMAGENET
In this section, we discuss some preliminary results from applying Kernel PCA analysis to real-world contrastive learning model.
We started by training variant of the SimCLR v2 model Chen al. (200bb) using the spectral contrastive loss and a linear kernel head, normalizing the output layer to have a constrained norm ||oe [a)]l²
described by HaoChen al. (2021). J. We explored automatically learning this norm e using the Adam optimizer and a separately separately-tunedd lunedd learning rate. We found that the norm e reliably increased during training, but training tended to destabilize and produce NaN weights once c 90, and we were unable to successfully train a model with a higher output layer norm.
We trained a model for 100 epochs (+s 30,000 iterations) on the ImageNet 2012 dataset, using the default augmentation parameters and other hyperparameters for SimCLR v2, obtaining similar supervised classification accuracy to previous results by HaoChen
(202T).
Next, we performed kernel PCA by using ordinary PCA with the explicit form of the kernel features (the output layer with normalization applied), since kernel PCA and ordinary PCA are equivalent for a linear kernel parameterization. We computed the covariance over a sample of 16 augmentations of each training dataset example, averaged across all examples. We then constructed the princi- pal component functions f, by normalizing based on the eigenvalues, and computed positive-paie discrepancies for each function over sample of 8 augmentation pairs for each training dataset example.
Figure shows the results of comparing the eigenvalues and positive-pai discrepancies, relative to the predicted relationship from Equation 4 For comparison, we also reproduce the corresponding figure for this kernel head parameterization and loss function our overlapping regions task. We see that, across both tasks, the norm constraint causes estimated eigenvalues to be smaller than Equation 4 would predict, but there still appears to be inverse correlation between the eigenvalue and positive- pair discrepancy. (On the overlapping regions task, it is close to constant shift of the linear Equation rrelationship. On the ImageNet task, the relationship still somewhat linear, but with multiple irregularities, and somewhat different slope than Equation 4 predicts; some of this may be due to increasing in the norm constraint during training.)
We also observe that, in both tasks, the sum of the eigenvalues from Kernel PCA is exactly equal to the norm constraint c. This suggests that the norm constraint is "capping" the sum the eigenvalues, forcing the model to only learn subset of eigenfunctions despite having capacity for more. We conjecture that stabilizing the learning dynamics might enable us to remove the norm constraint c and thus capture additional eigenfunctions, leading to potentially superior representations for future supervuper methods.
39


Reviews:
[{"review_id": "jclkY3aqPQa", "reviewer": "Reviewer_Ry9G", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors proposed a unified framework for interpreting a few existing contrastive learning methods as positive-pair (see Definition 2.1) kernel learning problems, see Table 1 for a summary. \nUnder a mild assumption for the target function g in Assumption 1.1, the authors showed:\n* in Theorem 3.2 that standard kernel PCA under the proposed positive-pair kernel has a few interesting theoretical properties (to identify eigenfunctions of some Markov transition of interest); and \n* in Theorem 4.1 that the obtained representation (1) maximizes the view invariance of the least-invariant unit-norm predictor and (2) minimizes the (quadratic) approximation error for the worst-case target function.\n\nSome (somewhat toy) numerical experiments were provided in Section 6 to support the theoretical results.", "summary_of_the_review": "I think the paper is in general interesting. It would be great if the authors could (1) find some way to better illustrate the contribution of this work and (2) address the following detailed comments:\n\n* more discussion on the positive-pair kernel is needed: the probability ratio and the positive-pair kernel seem to be one key point in the paper, and it is a Mercer kernel. Do we know anything more about it? can we have some more insight into the task, etc.?\n* it remains unclear to me how the proposed theory is of interest from a practical standpoint. Can that be used to design some novel methods/objectives beyond those listed in Table 1?", "strength_and_weaknesses": "**Strength**: the paper focuses on an important problem and the proposed viewpoint is interesting. The paper is in general well written.\n\n**Weaknesses**: a few concepts as well as their connections are discussed in the paper. And (in addition) the notations are somewhat heavy. It would be helpful to have a few figures or tables for the readers to have a better understanding of the contribution of this paper.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Pqyp1CE1-B", "reviewer": "Reviewer_7QsK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "1. This paper proves that multiple contrastive learning methods can find a minimax-optimal representation for linear predictors assuming the target functions satisfy approximate view-invariance property (Assumption 1.1). To prove this, they first show that minimizing the contrastive loss is equivalent to solving Kernel PCA for the positive-pair kernel. Then they show that solving the Kernel PCA is equivalent to finding the eigenfunctions of the Markov chain over positive pairs, which allows them to prove the minimax-optimal property. They also give generalization bounds for the performance of the learned representations for downstream supervised learning. \n2. In the experiments, in two synthetic datasets where the positive kernel has a closed form, the authors verified that multiple contrastive learning methods could indeed approximately recover the eigenfunctions of the kernel. The experiments also showed that the constraints on the kernel approximation and the weaker augmentation can have a negative impact on the recovery of the eigenfunctions. ", "summary_of_the_review": "This is a solid theory paper that proves the minimax-optimality of contrastive learning methods in finding representations for linear predictors assuming the view-invariance property of the target functions. The analysis also builds an interesting connection between contrastive learning, Kernel PCA, and the Markov chain over positive pairs. I believe this is a good step toward explaining the empirical success of various contrastive learning methods. My only concern is that it's unclear to me how this theory can guide us to design between contrastive learning methods. ", "strength_and_weaknesses": "Strengths:\nThis is a very solid and well-written theory paper that proves multiple contrastive learning methods can find a minimax-optimal representation for linear predictors assuming positive pairs have similar labels. This theory offers a unifying explanation for the success of multiple contrastive learning methods in practice. In the proof, they also build a very interesting connection between contrastive learning, Kernel PCA, and the Markov chain over positive pairs. \n\nWeaknesses:\nThis paper builds a connection between contrastive learning and Kernel PCA, which is very interesting from a theoretical perspective. However, what's the implication of this theory? How does this knowledge further guide us to build better contrastive learning methods in practice? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "DbBC92MOZQ", "reviewer": "Reviewer_76h8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work claims that contrastive learning can find a minimax-optimal representation for linear predictors when the prediction function is approximately view-invariant. \n\nMore precisely, the authors demonstrate that learning a representation via contrastive losses such as NT-XEnt, NT-Logistic, and Spectral can be seen under some assumptions as learning a positive definite kernel between pairs of samples. Then, a finite-dimensional representation can be extracted via kernel PCA using the learned kernel. Under some assumptions, it is possible to demonstrate that the resulting representation is minimax optimal for linear prediction for approximately view-invariant functions. This demonstration is done by bridging the vectors obtained via kernel PCA to eigenfunctions of a Markov chain over positive pairs. \n\nThe authors then proceed to experimentally validate their theory on two synthetic tasks (overlapping regions and MNIST with specific augmentations).", "summary_of_the_review": "This work offers a sensible kernel interpretation of contrastive self-supervised learning, whose understanding is an important problem today. The scope of this work may be limited since it differs from practical SSL in different ways: \n- Models are not always linearly evaluated (knn and fine-tuning are also used).\n- Augmentations distributions when learning downstream tasks often differs from training time.\n- Important downstream tasks such as segmentation or object detection may not follow Assumption 1.1\n\nI think these points could be at least discussed in the manuscript.\n\nOverall, the pros outweight the cons and would tend to recommend acceptance.", "strength_and_weaknesses": "Strength:\n- This paper tackles understanding and unifying self-supervised learning methods, which is an important problem as this framework becomes increasingly popular and many apparently different methods are in fact doing the same thing.\n- The theory is both simple and provides insights that follow the practice of SSL such as the importance of stronger augmentations or the relevance of linear evaluation, as well as new (at least to me) ones such as the negative effects of constraints on the output heads, and is validated experimentally. \n- The main Assumption 1.1 is clearly stated and discussed. \n\nWeakness: \n- I think Assumption 1.1 does not apply to important downstream tasks for evaluating visual representations such as object detection and segmentation. Moreover, visual representations are evaluated via linear probing, but also via fine-tuning or knn, which is not covered here. Hence, the extent of this theoretical analysis seems at first sight limited. In my opinion it would be very interesting to discuss these limitations, as another possible valuable conclusion is that object detection / segmentation / fine-tuning / knn are not relevant when it comes to evaluate contrastively learned representations.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster