Joint Embedding Self-Supervised Learning in the Kernel Regime
Authors: Bobak Kiani
Randall Balestriero
Yubei Chen
Seth Lloyd
Yann LeCun
Venue: Submitted to ICLR 2023 (2023)

Abstract: The fundamental goal of self-supervised learning (SSL) is to produce useful representations of data without access to any labels for classifying the data. Modern methods in SSL, which form representations based on known or constructed relationships between samples, have been particularly effective at this task. Here, we aim to extend this framework to incorporate algorithms based on kernel methods where embeddings are constructed by linear maps acting on the feature space of a kernel. In this kernel regime, we derive methods to find the optimal form of the output representations for contrastive and non-contrastive loss functions. This procedure produces a new representation space with an inner product denoted as the induced kernel which generally correlates points which are related by an augmentation in kernel space and de-correlates points otherwise. We analyze our kernel model on small datasets to identify common features of self-supervised learning algorithms and gain theoretical insights into their performance on downstream tasks.

Under review as a conference paper at ICLR 2023
JOINT EMBEDDING SELF-SUPERVISED LEARNING IN THE KERNEL REGIME
Anonymous authors Paper under double-blind review
ABSTRACT
The fundamental goal of self supervieee learning (SSL) is to produce useful rep- resentations of data without access to any labels for classifying the data. Modern methods in SSL, which form representations based on known or constructed rela- tionships between samples, have been particularly effective at this task. Motivated by rich line of work in kernel methods performed on graphs and manifolds, we show that SSL methods likewise admit a kernel regime where embeddings are constructed by linear maps acting the feature space of kernel find the op- timal form of the output representations for contrastive and non-contrastive loss functions. This procedure produces new representation space with inner prod- uet denoted as the induced kernel which generally correlates points which are re- lated by an augmentation in kernel space and de-correlates points otherwise. We analyze our kernel model on small datasets to identify common features of self- supervised learning algorithms and gain theoretical insights into their performance on downstream tasks.
INTRODUCTION
Self-supervised learning (SSL) algorithms are broadly tasked with learning from unlabeled data. In the joint embedding framework of SSL, mainstream contrastive methods build representations by reducing the distance between inputs related by augmentation (positive pairs) and increasing the distance between inputs not known to related (negative pairs) (Chen et al.) 2020 He et al,
2020 Oord et al., 2018 Yt al. 2019). Non-contrastive methods only enforce similarities between positive pairs but are designed carefully to avoid collapse of representations (Grill et al.) 2020 Zbontar al. 202T). Recent algorithms for SSL have performed remarkably well reaching similat lar
performance to baseline supervised learning algorithms on many downstream tasks (Caron et al.,
2020 Bardes al. 202 Chen & He 202T).
In this work, we study SSL from a kemel perspective motivated by the rich history of study of kernel algorithms on graphs and manifolds (Smola & Kondor 2003 Ando & Zhang 2006 Bellet et al. 2013 Belkin & Niyogii 2004p. Our primary aim is to extend this line of work to cover commonly used loss functions in modern SSL settings potentially providing useful insights into their properties and performance. In standard SSL tasks, inputs are fed into neural network and mapped into a feature space which encodes the final representations used in downstream tasks (e.g., classification tasks). In the kernel setting, inputs are embedded in a feature space corresponding to a kernel, and representations are constructed via an optimal mapping from this feature space to the vector space for the representations of the data. Here, the task can be framed optimal "induced" kernel, which a mapping from the original kernel in the input feature space to an updated kernel function acting the vector space of the representations. Our results show that such an induced kernel can be constructed using only manipulations of kernel functions and data that encodes the relationships between inputs in SSL algorithm (e.g., adjacency matrices between the input datapoints).
of finding an
More broadly, make the following contributions:
For contrastive and non-contrastive loss, provide closed form solutions when the al- gorithm is trained over a single batch data. These solutions form a new "induced" kernel which can be used to perform downstream supervised learning tasks.

---

Under review as a conference paper at ICLR 2023
We show that version of the representer theorem in kernel methods can be used to for- mulate kernelized SSL tasks as optimization problems. As an example, we show how to optimially find induced kernels when the loss is enforeed over separate batches of data.
We empirically study the properties of our SSL kernel algorithms to gain insights about the training of SSL algorithms in practice. We study the generalization properties of SSL algorithms and show that the choice of augmentation and adjacency matrices encoding relationships between the datapoints are crucial to performance.
We proceed as follows. First, we provide a brief background of the goals of our work and the theo- retical tools used our study, Second, we show that kernelized SSL algorithms trained on a single batch admit closed form solution for commonly used contrastive and non-contrastive loss func- tions. Third, we generalize our findings to provide a semi-definite programming formulation to solve for the optimal induced kernel in more general settings and provide heuristies to better understand the form and properties of the induced kernels. Finally, we empirically investigate our kernelized SSL algorithms when trained various datasets (code included in supplemental material).
1.1 NOTATION AND SETUP
We denote vectors and matrices with lowercase (a:) and uppercase (X) letters respectively. The vector 2-norm and matrix operator norm is denoted by || 11. The Frobenius norm of matrix M is denoted as |[. We denote the transpose and conjugate transpose of M by MT and M respectively. We denote the identity matrix as and the vector with each entry equal to one as 1. For a diagonalizable matrix M, its projection onto the eigenspace of its positive eigenvalues is M,.
For a dataset of size N. let a; X for i [N] denote the elements of the dataset. Given kernel function k= X' x X - R, let ((x) = -) be the map from inputs to the reproducing kernel Hilbert space (RKHS) denoted by H. with corresponding inner product (- -: and RKHS norm || ||p.. Throughout we denote K E NNN to be the kernel matrix of the SSL dataset where (Ks,))ij = k(x;,, a.)) We consider linear models W H -> R-K which map features to representations 2; W (Z:z;) Let Z be the representation matrix which contains (ax;) as rows of the matrix. This linear function space induces corresponding RKHS norm which can be calculated
lll / Σ (W;, W where W. H denotes the i-th component of the output of the linear mapping W. This linear mapping constructs an "induced" kernel denoted as k (*(,,)) as discussed later.
The driving motive behind modern self-supervised algorithms to maximize the information of given inputs in dataset while enforcing similarity between inputs that are known to be related. The adjacency matrix A E {0. 1 JNNN (also can be generalized to E NRNNNN connects related inputs 2; and 2j (i.e., Au 1 if inputs and j are related by a transformation) and DA is diagonal matrix where entry on the diagonal is equal to the number of nonzero elements of row of A.
2 RELATED WORKS
In this section, we briefly summarize some of the related works for this study. We include a more detailed related works section in Appendix
Modern self-supervised learning approaches: Joint embedding approaches to SSL produce rep- resentations by comparing representations of inputs via known relationships. Methods are denoted as non-contrastive if the loss function is only function of pairs that are related (Grill et al.) 2020) Chen & He. 2021 Zhontar et al., 2021 Bardes et al. 2021). Contrastive methods also penalize similarities of representations that are not related. Popular algorithms include SimCLR (Chen et al.) 2020), SWAV (Caron et al., 2020), NNCLR (Dwibedi et al. 2021), contrastive predictive coding OOrdd et al. 2018), spectral contrastive loss (HaoChen et al. (021). and many others. Separate from the joint embedding framework, many methods in SSL form representations by predicting held-out portions of the data typically in generative model setting. Commonly used algorithms incorporate autoencoder approaches (He et al.] 2022 Radford et al.) 2019 Vincent et al. 2010: Dosovitskiy
al. 2020 which are used in both natural language processing and image processing tasks.
2

---

Under review as a conference paper at ICLR 2023
Standard SSL Approach
Kernel Approach
A BR
(adjacency metrix encoding relations between imputs)
x X (inpul)
X1 NN E (SSL dataset)
Bugment
augment
(()xx x
x
X
xj EX /
(x1)) (x H (RKHS)
k(xxxx) = (0(x)))0)))
NNO
NN(-)
W": R
NN(x) ) R
loss
N
IR*
W (' W (xx) ug
lr (xxx)) (w"((x) (xx))
(representation)
function
(representation)
(representations)
Downstream Task
Downstream Task
Downstream Task (egg. kemoel regression)
(ag. classifier)
(e.g. classifior)
Figure 1: To translate the SSL setting into the kernel regime, we aim to find the optimal linear func- tion which maps inputs from the RKHS into the K K-dimensional feature space of the representations. This new feature space induces a new optimal kernel denoted the "induced" kernel. Relationships between data-points are encoded in an adjacency matrix (the example matrix shown here contains pairwise relationships between datapoints).
Neural tangent kernels and gaussian processes: Prior work has connected the outputs of infinite width neural networks to a corresponding gaussian process (Williams & Rasmussen (006)] Neal 1996 Lee al.] 2017). When trained using continuous time gradient descent, these infinite width models evolve as linear models under the so called neural tangent kernel (NTK) regime (Jacot et al.)
2018 Arora et al., 2019a). The discovery of the NTK opened a flurry of exploration into the con- nections between so so-called lazy training of wide networks and kernel methods (Yang) 2019] Chizat & Bach 2018 Wang et al.) 2022 Bietti & Mairal 2019). Though the training dynamies of the NTK has previously been studied in the supervised settings, one can analyze an NTK in self-supervised setting by using that kernel in the SSL. algorithms that we study here. We perform some preliminary investigation into this direction in experiments.
Kernel and metric learning: Various works have proposed a series of graph-based kernels that have ties to semi-supervised learning and appealing regularization properties over the geometric structure of the data (Smola & Kondor 2003 Belkin et al.) 2006 Vishwanathan et al., 2010). Links between spectral properties of the graphs and representations often formed during the process of learning (Belkin & Niyogi 2004 Zhao & Liu 2012]. Throughout our study, we note connections to
these related works. From an algorithmic perspective, perhaps the closest lines of work are related to kernel and metric learning (Bellet et al. 2013) Yang & Jin (006). Since our focus is on directly kernelizing SSL methods to eventually analyze and better understand SSL algorithms, our end goal is not to improve over these methods but instead, to extend them to the SSL setting. These works are further summarized in Appendix
CONTRASTIVE AND NON-CONTRASTIVE KERNEL METHODS
Stated informally, the goal of SSL in the kernel setting is to start with a given kernel function k: X' x X' + I (e.g., g., RBF kernel or neural tangent kernel) and map this kernel function to new "induced" kernel k** X' X' - E which a function of the SSL loss function and the SSL dataset. For two new inputs and x', the induced kernel k- æ²) generally outputs correlated values if x and x' are correlated the original kernel space to some datapoint in the SSI. dataset or correlated to separate but related datapoints in the SSL dataset as encoded in the graph adjacency matrix. If no relations are found in the SSL dataset between æ and x', then the induced kernel will generally output an uncorrelated value.
To kernelize SSL methods, we consider a setting generalized from the prototypical SSL setting where representations are obtained by maximizing/minimizing distances between augmented/un- augmented samples. Translating this to the kernel regime, as illustrated in Figure [ our goal is to find linear mapping W H K which obtains the optimal representation of the data for
3

---

Under review as a conference paper at ICLR 2023
given SSL loss function and minimizes the RKHS norm. This optimal solution produces "induced kernel" k- (:.-) which is the inner product of the data in the output representation space. Once constructed, the induced kernel can be used in downstream tasks to perform supervised learning.
Due to a gencralization the representer theorem (Schölkopi et al. 2001), we can show that the optimal linear function W must be in the support of the data. This implies that the induced kernel can be written as a function of the kernel between datapoints in the SSL dataset.
Proposition 3.1 (Form of optimal representation). Given a dataset æ1..... EN E X, let k(::) be a kernel function with corresponding map Φb : A' - H into the RKHS H. Let W H - R be a function drawn from the space of linear functions W mapping inputs the RKHS to the vector space of the representation. For risk function ((W((w1):.... W ()(xx)) E R and any strictly increasing function r :0, 03) - R, consider the optimization problem
+ +r ([ 1x). W arg min ((W (
(1)
WeW
The optimal solutions of the above take the form
optimal representation: W (x)) Mkx,a
(2)
induced kernel: k² (æx x') (MKx,a) Mkx = -x' M Mkx x'
where Mr R is matrix that must be solved for and kx E R. is vector with entries [kx = k( z)).
Proposition 3.1 proved in Appendix B.1 provides a prescription for finding the optimal represen- tations or induced kernels: i.e. one must search over the set of matrices M E R R to find an optimal matrix. This search can be performed using standard optimization techniques as we will discuss later, but in certain cases, the optimal solution can be calculated in closed-form as shown next for both contrastive and non-contrastive loss function.
Non-contrastive loss
Consider variant of the VICReg (Bardes et al. 2021 loss function below:
zT I (1- 117) z - 3 (ZL)
CViC
(3)
where B E RR+ is hyperparameter that controls the invariance term in the loss and L D A is the graph Laplacian of the data. We note that the second term in the above loss function takes a role akin to the Laplacian or manifold regularization term studied in kernel methods over graphs (Ando & Zhang 2006 Belkin et al. 2006 When the representation space has dimension K 2 N and the kernel matrix of the data is full rank, the induced kernel of the above loss function is:
ke (ar x²) = kin K ( -
2 ) )
N 11T
3 Kiikk ks.."'
(4)
where (.)4 projects the matrix inside the parentheses onto the eigenspace of its positive eigenvalues, kæ,e E RIXN is the kernel row-vector with entry equal to k(x, xx)) with k,, equal to its transpose, and K,,s E NNNN the kernel matrix of the training data for the self-supervised dataset where entry i,j is equal to k(æ,, 22)). When we restrict the output space of the self-supervised learning task to of dimension K < N, then the induced kernel only incorporates the top K eigenvectors of I 11 $ L:
k- (xx a²) = ki.. C..K .gK Ki
(5)
where CDCT - 1
is the eigendecomposition including only positive eigenvalues sorted in descending order, C.Ssk denotes the matrix consisting of the first K columns of C and
$ 111
D 1/2 SKKcK denotes the K K matrix consisting of entries in the first K rows and columns. Proofs of the above are in Appendix B.2
Contrastive loss For contrastive SSL, we can also obtain a closed form solution to the induced kernel for variant of the spectral contrastive loss (HaoChen al. 202
L.c
22 (I + A)
(6)
4

---

Under review as a conference paper at ICLR 2023
where A is the adjacency matrix encoding relations between datapoints. When the representation space has dimension K 2 N, this loss results in the optimal induced kemnl::
k" (x x') = k K (I + A) K
where ( is equal to the projection of I + A onto its eigenspace of positive eigenvalues. In the standard SSL setting where relationships are pair-wise (i.e., A,, = x; and æj are related by an augmentation), then I + A has only positive or zero eigenvalues so the projection can be ignored. K < N, then we similarly project the matrix + A onto its top K eigenvalues and obtain an induced kernel similar to the non-contrastive one:
ke (x. a²) kiz, k C. C..KDDKKKKKK .SK K K
where as before, CDC = I + is the eigendecomposition including only positive eigenvalues with eigenvalues in descending order, C.ssk consists of the first K columns of C' and D KKK <K is the K' x matrix of the first rows and columns. Proofs of the above are in Appendix B33 Note, that the induced kernels generally correlate data over the top eigenvalues of the graph adjacency matrix in line with findings from previous works in kernel methods and spectral graph theory ZZhao
Liu 2007
Belkin Niyogi 2004).
3.1
GENERAL FORM AS SDP
The closed form solutions for the induced kernel obtained above assumed the loss function was enforced across a single batch. Of course, in practice, data are split into several batches. This batched setting may not admit closed-form solution, but by using Proposition 3.1 we know that any optimal induced kernel takes the general form:
kt (xx x²) kin, Bk.
(9)
where B IR NxN positive semi-definite matrix. With constraints properly chosen so that the
solution for each batch is optimal (Balestriero & LeCun 2022 HaoChen et al. (022). one can find
the optimal matrix B" by solving semi-definite program (SDP). We perform this conversion to SDP for the contrastive loss here and leave proofs and further details including the non-contrastive case to Appendix B.4
Introducing some notation to deal with batches, assume we have N datapoints split into Whatches of size b. We denote the i-th datapoint within batch j as x,!) As before, 2; denotes the i-th datapoint across the whole dataset. Let Ks N be the kernel matrix
the complete dataset where [Ka = k( xz). Ks,,, E IR-V be the kernel matrix between the complete dataset and batch j where ll,b k( _e, and A be the adjacency matrix for inputs in batch j. With this notation, we now aim to minimize the loss function adapted from Equation (6) including a regularizing term for the RKHS norm:
C=
Σ
K K.K.BK.. - A0) + Tr(K,,,)),
(10)
where E + is a weighting term for the regularizer. Taking the limit of a - 0, we can find the optimal induced kernel for a representation of dimension > by enforcing that optimal representations are obtained in each batch:
min Tr(BK,,)) NNN
s.t. K 8 BK, s,3, = (I II+ (1)
Vj (1,2..... Rbaches
(1I)
B z O, rank B = K.
where as before, where (I+AA A0) is equal to the projection I + (0) onto its eigenspace of positive eigenvalues. Relaxing and removing the constraint that rank (B) K results in an SDP which can be efficiently solved using existing optimizers. Further details and a generalization of this conversion other representation dimensions shown in Appendix B.4
5

---

Under review as a conference paper at ICLR 2023
3.2 INTERPRETING THE INDUCED KERNEL
The top eigenvectors of the adjacency matrix form the representations in the SSL tasks studied here and consistent with related approaches in kernel methods and spectral graph theory ZZao & Liu 2007; Belkin & Niyogi] 2004]. More generally, as a loose rule, the induced kernel will correlate points that are close the kernel space or related by augmentations in the SSL dataset and uncorrelate points otherwise. Stated in the framework of (Wang & Isola 2020), the induced kernel increases alignment by enforcing correlation in datapoints in the traning set and achieves uniformity by setting elements of the representation space to be orthogonal eigenvectors over the dataset. As an example, note that in the contrastive setting (Equation 77). if one calculates the induced kernel k*( between two points in the SSL dataset indexed by and that are related by an augmentation (i.e., A.j = 1), then the kernel between these two points is k* (2; xz) = 1. More generally, if the two imputs to the induced kernel are close in kernel space to different points in the SSL dataset that are known to be related by A, then the kernel value will be close to 1. We formalize this intuition below for the standard setting with pairwise augmentations.
Proposition 3.2. Given kernel function k(---) with corresponding map (()) into the RKHS H. let and formed by pairwise
{æ 32. ØN be an SSL dataset normalized such that k(æ,,2.) augmentations (i.e., every element has exactly one neighbor in A) with kernel matrix Kss- Given two points x and x', if there exists two points in the SSL. dataset indexed by and j which are related by an augmentation (Aiz=1) and [] (x S 5I.KINN and [[(((ee) - (xx))ll S
VN then the induced kernel for the contrastive loss is at least k* (ax, x') 2 1
We prove the above statement in Appendix B.5 The bounds in the above statement which depend on
the number of datapoints N and the kernel matrix norm k || are not very tight and solely meant to provide intuition for the properties of the induced kernel. In more realistic settings, stronger cor- relations will be observed for much weaker values of the assumptions. In light of this, we visualize the induced kernel values and their relations the original kernel function in Section [4. on a sim- ple 2-dimensional spiral dataset. Here, it is readily observed that the induced kernel better connects points along the data manifold that are related by the adjacency matrix.
3.3 DOWNSTREAM TASKS
In downstream tasks, one can apply the induced kernels directly on supervised algorithms such as kernel regression or SVM. Alternatively, one can also extract representations directly by obtaining the representation kt (xx M M shown in Proposition 3.1 and employ any learning algorithm from these features. As an example, in kernel regression, we are given a dataset of size
Nr consisting of input-output pairs (z!(") M// } and aim to train linear model to minimize the mean squared error loss of the outputs (Williams & Rasmussen 2006). The optimal solution using an induced kernel (-,-,-) takes the form:
(x) = 1h' (ar, (1)), A an) "...,,, (x, a 2))
K y.
(12)
where Kir is the kernel matrix of the supervised training dataset with entry i,j equal to ke (xx(() x. ( and y is the concatenation of the targets as a vector. Note that since kernel methods generally have complexity that scales quadratically with the number of datapoints, such algorithms may be unfeasible in large-scale learning tasks unless modifications are made.
A natural question is when and why should one prefer the induced kernel of SSL to a kernel used in the standard supervised setting perhaps including data augmentation? Kernel methods generally fit a dataset perfectly so an answer to the question more likely arises from studying generalization. In kernel methods, generalization error typically tracks with the norm of the classifier captured by the complexity quantity 8N (K) defined as (Mohri et al. 2018 Steinwart & Christmann 2008):
Tr(K)
N (K)
N y y'K-'y.
(13)
where y is a vector of targets and K is the kernel matrix of the supervised dataset. For example, the generalization gap of an SVM algorithm can be bounded with high probability by D (K))N (see example proof in Appendix C.1) (Meir & Zhang 2003 Huang et al. (02T). For kernel functions

---

Under review as a conference paper at ICLR 2023
b)
100
RSF Kemee
075
0.50
0.25
SSL Induuced Kernel
0.00
-0
-0.0
0.75
-100
Figure 2: Comparison of the RBF kernel space (first row) and induced kernel space (second row). The induced kernel is computed based on Equation 4 and the graph Laplacian matrix is derived from the inner product neighborhood in the RBF kernel space, i.e., using the neighborhoods as data augmentation. a) We plot three randomly chosen points' kernel entries with respect to the other points on the manifolds. When the neighhorhood augmentation range used to construct the Lapla- cian matrix is small enough, the SSL-induced kernel faithfully learns the topology of the entangled spiral manifolds. b) When the neighborhood augmentation range used to construct the Laplacian matrix is too large, it creates the "short-circuif" effect in the induced kernel space. Each subplot the second row is normalized by its largest absolute value for better contrast.
k(..)) bounded in output between 0 and 1, the quantity sx( (x(K) ) is minimized in binary classification when k(æ,, x²) = for x, x' drawn from the same class and k(x, x²) = O for æ x'' drawn from distinct classes. If the induced kernel works ideally in the sense that better correlates points within class and decorrelates points otherwise then the entries of the kernel matrix approach these optimal values. This intuition is also supported by the hypothesis that self-supervised and semi-supervised algorithms perform well by connecting the representations of points common data manifold (HaoChen et al. [202T]Belkin Belkin & Niyogi (2044). To formalize this somewhat, consider such ideal, yet fabricated, setting where the SSL induced kernel has complexity 8 (xK") that does not grow with the dataset size.
Proposition 3.3 (Ideal SSL outcome). Given supervised dataset of N points for binary classifi- cation drawn from distribution with mi and m441 connected manifolds for classes with labels and +1 respectively, if the induced kernel matrix of the dataset K successfully separates the manifolds such that k* k* x²) 1 if x' are in the same manifold and K- x²) O otherwise, then x (*) = m_ m+1 = O().
The simple proof of the above in Appendix C short, we conjecture that should preferred in such settings where the relationships between datapoints are "strong" enough to connect similar points class on the same manifold. We analyze the quantity (x(K) Appendix D.4 add further empirical evidence behind this hypothesis.
EXPERIMENTS
In this section, we empirically investigate the performance and properties of the SSL kernel meth- ods on toy spiral dataset and portions of the MNIST and eMNIST datasets for hand-drawn digits and characters (Cohen al. 2017). As with other works, we focus on small-data tasks where ker- nel methods can be performed efficiently without modifications needed for handling large datasets (Arora et al. 2019a Srmmández-Delgadee et al., 2014). For simplicity and ease of analysis, we per- form experiments here with respect to the RBF kernel. Additional experiments reinforcing these findings and also including analysis with neural tangent kernels can be found Appendix D
4.1 VISUALIZING THE INDUCED KERNEL ON THE SPIRAL DATASET
For an intuitive understanding, we provide visualization in Figure to show how the SSL-induced kernel disentangles manifolds in the representation space. In Figure we study two entangled 1-D spiral manifolds in 2D space with 200 training points uniformly distributed on the spiral manifolds. We use the non-contrastive SSL-induced kernel, following Equation 4 to demonstrate this result,

---

Under review as a conference paper at ICLR 2023
Contrastive-MMN MNIST
Contrastive-EMNNI
N-16
N-61
N-256
16
50
18
8
Tes: accuraty
15
14
8
10
6
30
sxggmertstons 1og2))
Wuggmensatires legg)
sugmennttooon ons [lgg2]
s.ugmertsttons (log2)
Puugmenttteee Degg))
sugmennttton Degg1
nonn-conrrasive-MNNN -NNIST
non-contrastive-EMMM
N-16
N-64
N-256
N-16
No:44
N-2
Test 300-000
10-
10
AugIttm 0ay22)
(egg2)
0cg2)
daggennaaiions Beg21
Figure 3: Depiction of MNIST and EMNIST full test set performances using the contrastive and non-contrastive kernels (in red) and benchmarked against the supervised case with labels on samples (original augmented) in black and with labels only the original samples in blue, with the number of original samples given by N E {16, 64, 256} (each column) and the number aug- mented samples (in log2) in x-axis. The first corresponds Gaussian blur aatteaaugmntttioon (poorly aligned with the data distributions) and the second row corresponds to random rotations (-10,10), translations (-0.1,0.1) and scaling (0.9.1.1). We set the SVM la regularization and use the RBF kernel (NTK kernels in Appendix D.3). In all cases, the kernel representation dimensions are unconstrained. Two key observations emerge. First, whenever the augmentation is not aligned with the data distribution, the SSL kernels falls below the supervised case, especially as N increases. Second, when the augmentation aligned with the data distribution, both SSL kernels are able to get close and even outperform the supervised benchmark with augmented labels.
0.001
whereas contrastive SSL-induced kernel is qualitatively similar and left to Appendix D.I In the RBF kernel space shown in the first row of Figure 2 the value of the kernel is captured purely by distance. Next, consider the SSL setting, we construct the graph Laplacian matrix L by connecting vertices between any training points with k(z1, 222) >> d, i.e., Lij -1 if k(x,, my) > d and Lij otherwise. The diagonal entries of L are equal the degree of the vertices, respectively. This construction can be viewed using the Euclidean neighborhoods of x the data augmentation. We choose 3 = 0.4, where other choices within a reasonable range lead to similar qualitative results. In the second row of Figure we show the induced kernel between selected points (marked with an x) and other training points in the SSL-induced kernel space. When d is chosen properly, lyy, as observed in the second row of Figure aa), the SSL-induced kernel faithfully captures the topology of manifolds. However, the augmentation has to be carefully chosen as Figure] 2b) shows that when d is too large, the two manifolds become mixed in the representation space.
4.2 CLASSIFICATION EXPERIMENTS
We explore in Figure the supervised classification setting of MNIST and EMNIST which consist of 28 28 grayscale images. (E)MNIST provide strong baseline to evaluate kernel methods due to the absence of background in the images making kernels such as RBF more aligned to measure input similarities. In this setting, explore two different data-augmentattin (DA) policies, one aligned
8

---

Under review as a conference paper at ICLR 2023
sup, beselines: 120 0 93.00 tram)
sup. becel nes: $5.60. 79.02 dest
sup. beselines: 120 93.00 (trano)
sip. becel Des: 85 79.02 0est
18.9
11.
16.0
9.74
9.74
100.0 170 105.0 100
18.0
19.0
130.0 192. 100
9.24
0:75
18:14
72.62 12.00
92.
100.0 100.0
100.2 100.0
70.94
11.36 85.
10-
9:.
100.0 120.0 102.2
03.76
01.03
05.00 85,
05.0
500.0
120.0
102.2 100.0
03.0
09.76
79.09
120-
70.0
120.0
100.0 120.0 102.2
00.5
$1.03
85.
0.001
92.2
100.0
100.0
100.2 100.0
1:29
05.30
$1.38 05.33
1000-
34.0
200.0
200.0 120.0 100.0
10.4
00.5
51.05
55.00
0.0003
46.0
90.0
100.0
120.0 100.0 100
29.29
08.04
02.7
27
10
22
122
220
312
10
22
64
124
235
3L2
10
24
64
120
220
212
10
22
64
230
3L2
rnppesentationn demersion
reprosie fation cimonaion (C:
Inpresertation dimersion 05)
representation dimansionn (SC
Figure 4: MNIST classification task with 100 original training samples and 100 augmentations per sample on the train and test set (full, 10, 000 samples) with baselines in the titles given by supervised SVM using labels for all samples or original (100) samples only. We provide on the left the contrastive kernel performances when ablating over the (inverse) of the SVM's & regularizer y-axis and representation dimension (K) in the x-axis. Similarly, we provide on the right the non- contrastive kernel performances when ablating over 3 on the y-axis and over the representation dimension (K) on the x-axis. We observe, as expected, that reducing K prevents overfitting and should be preferred over the l2 regularizer, and that 3 acts jointly with the representation dimension iee one only needs to tune one of the two.
with the data distribution aaaatioonttaanslatio-ssssannnni and one largely misaligned with the data distribution (aggressive Gaussian blur). Because our goal is to understand how much DA impacts the SSL kernel compared to fully supervised benchmark, we consider two (supervised) benchmarks: one that employs the labels of the sampled training set and all the augmented samples and one that only employs the sampled training set and no augmented samples. We explore small training set size going from N 16 to N = 256 and for each case we produce a number of augmented samples for each datapoint so that the total number of samples does not exceed 50, 000 which is standard threshold for kernel methods. We observed in Figure 3 that the SSL kernel is able to match and even outperform the fully supervised case when employing the correct aata-augmentation, while with the incorrect data- auttaaaggmtttiionn the performance is not even able to match the supervised case that did not see the augmented samples. To better understand the impact of different hyperparameters onto the two kernels, we also study in Figure 4 the MNIST test set performances when varying the representation dimension K, the SVM's Eg regularization parameter, and the non-contrastive kernel's 3 parameter. We observe that although / is an additional tuning plays a similar role to K, the representation dimension. Hence, in practice, the design of the non-contrastive model can be controlled with a single parameter as with the contrastive setting. We also interestingly observe that K is a more preferable parameter to tune to prevent over-fitting as opposed to SVM's &g regularizer.
to tune, its
5 DISCUSSION
Our work explores the properties of SSL algorithms when trained via kernel methods. Connec- tions between kernel methods and neural networks have gained significant interest in the supervised learning setting (Neal 1996; Lee et al. 2017) for their potential insights into the training of deep networks. As we show this study, such insights into the training properties of SSL. algorithms can similarly be garnered from an analysis of SSL. algorithms in the kernel regime. Our theoretical and empirical analysis, for example, highlights the importance of the choice of augmentations and en- coded relationships between data points on downstream performance. Looking forward, we believe that interrelations between this kernel regime and the actual deep networks trained in practice can be strengthened particularly by analyzing the neural tangent kernel. In line with similar analysis in the supervised setting (Yang et al., 2022) Seleznova & Kutyniok| 2022 [Lee et al. 2020). neural tangent kernels and their corresponding induced kernels in the SSL setting may shine light some of the theoretical properties of the finite width networks used in practice.
REFERENCES
Rie Ando and Tong Zhang. Learning on graph with laplacian regularization. Advances in neural information processing systems, 19, 2006.
9

---

Under review as a conference paper at ICLR 2023
MOSEK ApS. The MOSEK optimization toolbox for MATLAB manual. Version 9.0., 2019. URL http://docs mosek. wwm/9.00..mmmo /ttp:///0t.oooo////////o indexxn.xxxx..o//// html
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019a.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.09229 2019b.
Mahdich Solcymani Baghshah and Saced Bagheri Shouraki. Kernel-bace metric learning for semi- supervised clustering. Neurocomputing, 13:7799:1352-1161, 2010.
Randall Balestriero and Yann LeCun. Contrastive and con-contrastive self-supervised learning re- cover global and local spectral embedding methods. arXiv preprint arXiv:2205./1558, 2022.
Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: wwwpeeeaiaaaiinccccoviinnna regaareeeoooaaannnneeeeaaaaiiooi for self supervised learning. arXiv preprint arXiv:2105.06 04906, 2021.
Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Mikhail Belkin and Partha Niyogi. Semi-supervised learning riemannian manifolds. Machine learning, 56(1 56(1):209-239, 2004.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, 7 (11), 2006.
Aurelien Bellet, Amaury Habrard, and Mare Sebban. A survey on metric learning for feature vectors and structured data. arXiv preprint arXiv:1306.6709, 2013.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kemelss. Advances in Neural Information Processing Systems, 32, 2019.
Stephen Boyd, Stephen P Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge uni-
versity press, 2004.
Vivien Cabannes. From weakly supervised learning to active labeling. PhD thesis, Ecole Normale Supérieure (ENS), 2022.
Vivien Cabannes, Loucas Pillaud- Francis Bach, and Alessandro Rudi. Overcoming the curse of dimensionality with laplacian regularization in semi-supervised learning, Advances in Neural Information Processing Systems, 34:30439 24430449--3051,, 2021.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances Neural Information Processing Systems, 33:9912-99244 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15750-15758, 2021.
Yanping Chen, Eamonn Keogh, Bing Hu, Nurjahan Begum, Anthony Bagnall, Abdullah Mueen, and Gustavo Batista. The ucr time series classification archive, July 2015. www. . es uez edu/
eamonn/time_serxe sereees_eeeeeeeeeee d
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint 1812v:1812.0723 8, 2018.
Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
10

---

Under review as a conference paper at ICLR 2023
Gregory Cohen, Saced Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 international joint conference on neural networks (IJNN), pp- 2921-2926. IEEE, 2017.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Two-stage learning kemnl algorithms. In Proceedings of the 27th International Conference on International Conference on Machine Learning, pp. 239-246, 2010.
Nello Cristianini, John Shawe- Shawe-Taylor, Andre Elisseeff, and Jaz Kandola. On kernel-target alignment. Advances in neural information processing systems, 14, 2001.
Mare Deisenroth and Jun Wei Ng. Distributed gaussian processes. In International Conference on Machine Learning, pp. 1481-1490 1490. PMLR, 2015.
Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov. Clustering with multi- layer graphs: A spectral perspective. IEEE Transactions on Signal Processing, 60(1 1):5800- 5831, 2012.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 19929, 2020.
Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman. With little help from my friends: Nearest-neighhor contrastive learning of visual representations. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9588-9597, 2021.
Manuel Fernández-Deegaddo, Eva Cernadas, Senén Barro, and Dinani Amorim. Do we need hun- dreds of classifiers to solve real world classification problems? The journal of machine learning research, 15(13:3133-118, 2014.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach self-supervised learning. Advances in neural information processing systems, 13:21271-21288 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-54 1, 2021.
Jeff HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. arXiv preprint arXiv:2204.08 026883, 2022.
Charles R Harris, K Jarrod Millman, Stéfan Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, al. Array program- ming with numpy. Nature, 585(7885) 2020.
Kaiming He. Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked au- toencoders are scalable vision learners. In Proceedings of the IEEE/VV Conference on Computer Vision and Pattern Recognition, pp. 16000-16009, 2022.
Thomas Hofmann, Bernhard Schölkopf. and Alexander J Smola. Kernel methods in machine learn- ing. The annals of statistics, 36(3): 171-1220, 2008
Steven CH Hoi, Rong Jin, and Michael R Lyu. Learning nonparametric kernel matrices from pair- wise constraints. In Proceedings of the 24th international conference on Machine learning, pp- 361-368, 2007.

---

Under review as a conference paper at ICLR 2023
Hsin- Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean. Power data in quantum machine learning. Nature Communi- cations, 12(1), May 2021. doi: 10.1038/41447-001-25555555 1038/s41 4 46 021-0201---22-2-
/ttttps://do..oom
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, 31, 2018.
Ashesh Jain, Swaminathan VN Vishwanathan, and Manik Varma. Spf- Spf-gmkl: generalized multiple kernel learning with million kernels. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 750-758, 2012.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. arXiv preprini arXiv: 2017.
Jaehoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: empirical study. Advances in Neural Information Processing Systems, 13:15156-15172, 2020.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34:309- 323, 2021.
Ron Meir and Tong Zhang. Generalization error bounds for bayesian mixture algorithms. Journal of Machine Learning Research, 4(Oct):889-866)) 860, 2003.
Aditya Krishna Menon. Large-scale support vector machines: algorithms and theory. Research
Exam, University of California, San Diego, 117, 2009.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning.
MIT press, 2018.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Roman Novak, Lechao Xiao, Jiri Hron, Jaehoon Lee, Alexander A. Alemi, Jascha Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations, 2020. httpt:/
com/
[google/neuze tanggl//ennalllltgnnntt
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv:1807.03745. 2018.
Pedregosa, G. Varoquaux, Gramfort, V. Michel, Thirion, O. Grisel, Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830 2011.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer school on machine learning, pp. 63-71. Springer, 2003.
Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola. A generalized representer theorem. In International conference on computational learning theory, pp. 416-426. Springer, 2001.
Mariia Seleznova and Gitta Kutyniok. Analyzing finite neural networks: Can we trust neural tangent kernel theory? In Mathematical and Scientific Machine Learning, pp. 868-895. PMLR, 2022.
Alexander Smola and Risi Kondor. Kernels and regularization on graphs. In Learning theory and kernel machines, pp. 144-158. Springer, 2003.
12

---

Under review as a conference paper at ICLR 2023
KP Soman, R Loganathan, and V Ajay. Machine learning with SVM and other kernel methods. PHI Learning Pyt. Ltd., 2009.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
Jos F Sturm. Using sedumi 1.02, matlab toolbox for optimization over symmetric cones. Opti- mization methods and software, 11(1-4)625-653, 1999.
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, Pierre-Antoine Manzagol, and Léon Bottou. Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion. Journal of machine learning research, 11(12), 2010.
S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 11: 11:1201-222,, 2010.
Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf. Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34:16451-16461) 2021.
Sifan Wang, Xinling Yu, and Paris Perdikaris. When and why pinns fail to train: A neural tangent kernel perspective. Journal of Computational Physics, 449: 149:1, 2022.
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.
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks unlabeled data. arXiv preprint arXiv:2010.03622 2020.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. In International Conference Machine Learning, pp- 11112-11122. PMLR, 2021.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Hao Xia, Steven CH Hoi, Rong Jin, and Peilin Zhao. Online multiple kernel similarity learning for visual search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(3):536-549 2013.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 17Xiv:190.004760, 2019.
Greg Yang, Edward J Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ry- der, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tensor programs Tuning large neural networks via zero-shot hyperparameter transfer. arXiv preprint arXiv:200.004666 2022.
Liu Yang and Rong Jin. Distance metric learning: A comprehensive survey. Michigan State Uni- versiy, 2(2):4, 2006.
Mang Ye, Xu Zhang, Pong C Yuen, and Shih-Fu Chang. Unsupervised embedding learning via in- variant and spreading instance feature. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 6210-6219 2019.
Dit- Yan Yeung and Hong Chang. A kernel approach for semisupervised metric learning. 1EEE Transactions Neural Networks, 1811)944 2007.
13

---

Under review as a conference paper at ICLR 2023
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In International Conference on Machine Learning, pp. 12310- 12320. PMLR, 2021.
Zheng Zhao and Huan Liu. Spectral feature selection for supervised and unsupervised learning. In Proceedings of the 24th international conference on Machine learning, pp. 1151-1157, 2007.
Zheng Alan Zhao and Huan Liu. Spectral feature selection for data mining. Taylor & Francis, 2012.
Mingkai Zheng, Shan You, Fei Wang, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Xu. Ressl: Relational self-supervised learning with weak augmentation. Advances in Neural Information Processing Systems, 14:2543-2555 2021.
Xiaojin Jerry Zhu. Semi-supervised learning literature survey. 2005.
Jinfeng Zhuang, Jialei Wang, Steven CH Hoi, and Xiangyang Lan. Unsupervised multiple kernel learning. In Asian Conference on Machine Learning, pp. 129-144 144. PMLR, 2011.
14

---

Under review as a conference paper at ICLR 2023
A RELATED WORKS AND TOPICS
A.1 JOINT EMBEDDING SSL ALGORITTMS IN PRACTICE
Joint embedding approaches form representations by comparing representations of jointly chosen inputs that have known relations. These methods also can hold out portions of the data, but this not necessarily a requirement. Any joint-embedding SSL algorithm requires a properly chosen loss function and access to a set of observations and known pairwise positive relation between those observations. Methods are denoted as non- con-contrastive the loss function only function of pairs that are related (Grill et al.) 2020 Chen & He| [021 Zbontar et al. (02T). One common method using the VICReg loss (Bardes et al. 202 1p. for example, takes the form
K
Cvie a
max 0, 1 (or(Z)), 1011 +B Σ
Cov ()
A) D Zz. Zz.
(14)
We adapt the above for the non-contrastive loss we study in our work.
Contrastive methods also penalize similarities of representations that are not related. Popular algo- rithms include SimCLR (Chen et al. (020). SWAV (Caron et al.) 2020)), NNCLR (Dwibedi et al.]
2021 contrastive predictive coding (Oord et al. 2018), and many others. The spectral contrastive
loss, for example takes the form (HaoChen et al. 20211
[f(=) + Eg,.- (((O)T((E))
L.c g
(15)
where x, - are positive pairs and x, xt are negative pairs. We consider variant of the spectral contrastive loss in our work.
A.2 THEORETICAL STUDIES OF SSL
In tandem with the success of SSL in deep learning, a host of theoretical tools have been devel- oped to help understand how SSL algorithms learn (Arora et al. 2019b Balestriero & LeCun 2022
HaoChen al. 2022 Lee al. (022)) Findings are often connected the underlying graph con- necting the data distribution (Wei et al. 2020 HaoChen et al. 2021) or the choice of augmentation (Wen & Lij 2021). WWang& & Isola (020)) study the theoretical properties of good SSL algorithms showing that alignment and uniformity are two important criteria for successfully building repre- sentations. We also note that prior work on SSI. has analyzed the importance of the choice of augmentation in building positive pairs (Zheng et al. [021 Von Kügelgen et al. (02T). Building representations from known relationships between datapoints is also studied in spectral graph the- ory (Chung 1997b. We employ findings from this body of literature to provide intuition behind the properties of the algorithms discussed here.
A.3 KERNEL METHODS
Kernel methods have been connected to properties of graphs and manifolds in long line of work.
Smola & Kondor 22003; Vishwanathan et al. (2010). among others, introduce a family of kernels on graphs which offer nice regularization properties for their corresponding RKHS. Similar methods
have been proposed for semi-supervised learning via graph-based methods Zhu 2005 Hofmann
al., 2008) and manifold regularization (Belkin et al. 2006). These methods generally introduce terms into a loss function which regularize the solution depending on the geometric structure of the data. Properties of the features have also been tied to results in spectral graph theory (Zhao & Liu
2007 2012: Dong et al.) 2012), where the top features generally correspond to the top eigenvalues of the graph Laplacian. More recently, kernel methods have been employed to more efficiently regularize data based on the Laplacian and improve semi-supervised learning algorithms (Cabannes
ct al. 2021 Cabannes 2022).
As stated in the main text, perhaps the closest lines of work are related to kernel and metric learning (Bellet et al. 2013 Yang & Jin (006) In kernel learning, prior works have proposed constructing a kernel via learning procedure; e.g., via convex combinations of kernels (Cortes et al. (010)), kernel
15

---

Under review as a conference paper at ICLR 2023
alignment (Cristianini et al. 2001), and unsupervised kernel learning to match local data geometry (Zuang et al., 2011). Prior work in distance metric learning using kernel methods aim to produce representations of data in unsupervised
semi-supervised settings by taking advantage of links between data points. For example, (Baghshah & Shouraki] (010:) Hoi et al. 2007) learn to construct kernel based on optimizing distances between points embedded in Hilbert space according similarity and dissimilarity matrix. Yeung & Chang (2007) perform kernel distance metric learning semi-supervised setting where pairwise relations between data and labels are provided. Xia al. (013) propose an online procedure to learn kernel which maps similar points closer to each other than dissimilar points. Many of these works also use semi-definite programs to perform optimization to find the optimal kernel.
B DEFERRED PROOFS
B. REPRESENTER THEOREM
Theorem B.1 (Representer theorem for self-supervised tasks; adapted from Schölkopf et (001) >.
Let a, E X for i E [N] be elements of a dataset of size N, k X' x X' R.. be a kernel function with corresponding map & X + H into the RKHS H. and r [0, oc) + I be any strictly increasing function. Let W H + I be a linear function mapping inputs to their corresponding representations. Given a regularized loss function of the form
(W ((1)),...... w (x + ( [|));
(16)
where ((W)(x))... ( is an error function that depends on the representations of the dataset, the minimizer W of this loss function will be the span of the training points {$(2;). i e
(1,..., N},, iee. for any & E H:
W Φ = if (0. (Zx)) ViE [N].
(17)
Proof. Decompose W = Wi + WT, where W (ax,) 0 for all i E [N]. For a loss function L of the form listed above, we have
L(W + Wi) R (WW) W W. (L)))()) (WI + W (())(())) +r (I] Willx)
(18)
(Wi ((1)).)...... Wi (xx))) r W1] W Willx)
Where in the terms in the sum, used the property that W1 is not in the span of the data. For the regularizer term, we note that
W W Wilk)) =r (VIW 1 W
(19)
2r((W))
Therefore, strictly enforcing W minimizes the regularizer while leaving the rest of the cost
function unchanged.
As a consequence of the above, all optimal solutions must have support over the span of the data. This directly results in the statement shown in Proposition 3.1
Remark B.2. The representer theorem renders the problem of optimization tractable over a finite dataset for given SSL loss function (Hofmann et al.] 2008 [Soaan et al.) 2009). In certain cases, as we show in the main text, such optimization have nice closed form solutions. Nevertheless, approximate methods of optimization can be used to find closed form solutions for loss functions where closed form solutions do not exist or are not expected to exist. Many optimizers exist to perform this optimization including potentially approximations that allow for incorporation of larger datasets (Hofmann et al. 2008 Deisenroth & Ng 2015 Jain et al. 2012 Menon 2009) Rasmussen 2003
16

---

Under review as a conference paper at ICLR 2023
B.2 CLOSED FORM NON-CONTRASTIVE LOSS
Throughout this section, for simplicity, we define M :- 1- n 11T. With slight abuse of notation,
we also denote X E RNXD as matrix whose i-th row contains the features of (xx)).
((x1))
)(x2))
X
(20)
((x))
Note that if the RKHS is infinite dimensional, one can apply the general form of the solution as shown in Proposition 3.1 to reframe the problem into the finite dimensional setting below. As reminder, aim to minmize the VICreg cost function:
C
min W
WXXMXXW - II + T WXXLXXT..
(21)
By applying the definition of the Frobenius norm and from some algebra, obtain:
C(W) | || BTr [WXTXXWT]]
= XXTMXXW - [| + [WXT (BL + 2M - 2M) XWT]
=K + | X X [ M
=
(22)
+'Ir X (BL 2M - XWT]
-K+ |XXMXWW1 Tr W (2M 3L) XWT
= K + | - - (2M -3L)].
The optimum of the above formulation has the same optimum as the following optimization problem defined as C" CWWW):
C((W) - - (M - 3L/2) ||.
(23)
Since Mi is a projector and M(2M -BM--B BLL 2M BL (since the all-ones vector the kernel of L). then we can solve the above by employing the Eckart- Young theorem and matching the K- dimensional eigenspace of XWTWXXT with that of the top K eigenspace M 1-LL22
One must be careful in choosing this optimum as X can only take positive eigenval- ues. Therefore, this is achieved by choosing the optimal W to project the data onto this eigenspace
W
(+)) C.Sk (I- -D) SK
(24)
where we set the eigendecomposition of / 11 + as CDOT = 1/2 = 11 + 7 L and C. is the matrix consisting of the first K rows of C. Similarly, (I - D) denotes the top left K x K matrix of (I- D). Also in the above, (+) denotes the pseudo-inverse of X. If the diagonal matrix I- D contains negative entries, which can only happen when is set large value, then 1/2
the values of (I - 1/2 for those entries is undefined. Here, the optimum choice is to set those entries to equal zero. In practice, this can be avoided by setting to be no larger two times than the degree of the graph.
Note, that since W only appears in the cost function in the form WTW. the solution above is only unique up to an orthogonal transformation. Furthermore, the rank of XWTWXT X at most N so better optimum cannot be achieved by increasing the output dimension of the linear transformation beyond N. To see that this produces the optimal induced kernel, we simply plug in the optimal W
k- (xr x²) = (W*x)
=x)x C,Sk (I- (IDD) 1/2
SK DDDD)K (I (D- D) CT CT (x(et)T x
(25)
=kn, C. (I -DD))KKg CT
C. K-kkk-
17

---

Under review as a conference paper at ICLR 2023
Now, it needs to be shown that W is the unique norm optimizer of the optimization problem. To show this, we analyze the following semi-definite program which is equivalent since the cost function is over positive semi-definite matrices of the form WTW:
min Tr(B) BEROXD
s.t. XBX = C.Sk (I (I- SK.SK C.
C. == Pk
(26)
0
To lighten notation, we denote Px = C.SK (I 2/2
<K C. and simply use X for X. The
above can easily be derived by setting = WTW in Equation 23 This has corresponding dual
max Y YERNEN
Tr(YTPk)
(27)
S.t. I X
The The optimal primal can be obtained from by (X : optimal dual can be similarly calculated and is equal to Y (x+) A straightforward calculation shows that the optimum value of the primal and dual formulation are equal for the given solutions. We now check whether the chosen solutions of the primal and dual satisfy the KKT optimality conditions (Boyd et al. 2004):
Primal feasibility: X XTM Pk, B
Dual feasibility: I X MX 2 0
(28)
Complementary slackness: (I - X--X ="= =0
The primal feasibility and dual feasibility criteria are straightforward to check. For complementary slackness, note that
(I --XTY- MX) B X
X X LK (X+)²
- (x+)= - (X+)*
(29)
=X+LK (x+) -X-LK (x+)
=0.
In the above we used the fact that M M = that projection. This completes the proof of the optimality.
Lx since M is projector and Lx is unchanged by
B.3 CONTRASTIVE LOSS
For the contrastive loss, follow similar approach above find the minimum norm lution that obtains the optimal representation. Note, that the loss function contains the term X - -I+ l) Since XWTWXT is positive semi-definite, then this is opti- mized when XWTW X matches the positive eigenspace of (I+ defined (I + A) Enumerating the eigenvalues of A v; with corresponding eigenvalues e,, then (I+ + A) Exe, -1 (e: + 1)v.v/. More generally, if the dimension of the representation is restricted such that K < N, then we abuse notation and define
K Σ
(I + A)
max(e; + 1, 1,00,
(30)
where are sorted in descending order.
To find the minimum RKHS norm solution, we have to solve similar SDP Equation (26):
min
Tr(B) (B)
BeROxD
s.t. X = (I A)
(31)
B 2 0
18

---

Under review as a conference paper at ICLR 2023
This has corresponding dual
Tt (I+()++A)) YER TRRNNN
max
(32)
s.t. I X 0
The optimal primal is B² = = (X+)*. The optimal dual is equal to Y (x+)" x Directly plugging these in shows that the optimum value of the primal and dual formulation are equal for the given solutions. As before, dual satisfy the KKT optimality conditions (Boyd et al. 2004):
check whether the chosen solutions of the primal and
Primal feasibility: XB" X = + B' 2'20
Dual feasibility: I - X
(33)
Complementary slackness: (I- =.
The primal feasibility and dual feasibility criteria are straightforward to check. For complementary slackness, we note that
X
A)+ Xx') A)+ (x+)
=x+ A)+
A)- (x+)*
(34)
O.
In the above, we used the fact that X + X is a projection onto the row space of X. This completes the proof of the optimality.
B.4 OPTIMIZATION VIA SEMI-DEFINITE PROGRAM
In general scenarios, Proposition 3.1 gives prescription for calculating the optimal induced kernel for more complicated optimization tasks since we note that the optimal induced kernel k- (az, x²) must be of the form below:
k" (x,, x²) Kn,s BkT s'
(35)
where ha a row vector whose entry equals the kernel k(xx,;; between æ and the i-th datapoint and E NxN is positive semi-defniit matrix.
For example, such scenario arises when one wants to apply the loss function across Yabacches batches of data. To frame this as an optimization statement, assume we have N datapoints split into batches of size each. We denote the i-th datapoint within batch k as x (k) As before, æ; denotes the i-th datapoint across the whole dataset. We define the following variables:
Ka,s E RNN (kernel matrix over complete dataset including all batches) where Kanalis = at,;
Ka,sn Nxb (kernel matrix between complete dataset and dataset of batch k) where K [Koockis = k( ar (a))::: similarly, K K E R is simply the transpose of Ke...
(k) is the adjacency matrix for inputs in batch & with corresponding graph Laplacian (k)
In what follows, we denote the representation dimension as K.
Non-contrastive loss function In the non-contrastive setting, we consider a regularized version of the batched loss of Equation (3). Applying the reduction of the loss function in Equation (23). consider the following loss function where we want to find the minimizer B:
Thbaahee
K Kr,,BK.,,,
(1- (I- 11--1-1-----00 -9
11
| F
+ a TTTK.....). (36)
where I hyperparameter. The term Tr(BK,,,) regularizes for the RKHS norm of the resulting solution given by B. For simplicity, we denote before M I 11T Taking the limit
19

---

Under review as a conference paper at ICLR 2023
- and enforcing representation of dimension K, the loss function above is minimized when we obtain the optimal representation. i.c. we must have that
K,, BK.,, M M (L
(37)
where (M - 33 denotes the projection of M -BL /2 onto the eigenspace of the top K positive singular values (this is the optimal representation shown earlier).
Therefore, we can find the optimal induced kernel by solving the optimization problem below:
min BERNKN
(r.BK,,s))
s.t. K si. BK s,8, M M -M Vi E (1,2.... ..... bbttchees
(38)
B z 0, rank(B) K,
Relaxing the constraint rank B = K forms an SDP which can be solved efficiently using existing Sturm 1999).
SDP solvers (ApS) 2019;
Contrastive loss
As shown in Section 3.1 the contrastive loss function takes the form
K sy. BK., s,s; - (I+ A l Tr(BKs,,))
L Σ
(39)
where a E R is weighting term for the regularizer. this setting, the optimal representation of dimension K is equal to
K BKs,sy s,y; - -( [I+ +++
(40)
where (0) K denotes the projection of I + A onto the eigenspace of the top K positive singular values (this is the optimal representation shown earlier). Taking the limit of a - 0, have a similar optimization problem:
Tr(BKs,²) BERNXN
min
s.t. K 81.8 BK 8,81
( (I+ A
Ei (1,2,... Pbatchhs
(41)
B O, (Bnk(B) K. As before, relaxing the rank constraint results in an SDP.
B.5 PROOF OF KERNEL CLOSENESS
Our goal is to prove Proposition 3.2 copied below.
Proposition 3.2. Given kernel function k(-.-) with corresponding map 4b.) into the RKHS H. let (æ1, ... xNN) } be an SSL dataset normalized such that k(æ.,, (::) and formed by pairwise augmentations (i.e., every element has exactly one neighbor
A) with kernel matrix K Given two points and x', if there exists two points in the SSL dataset indexed by and which are related and [1(())) ) - ((xx))lm S
by an augmentation (Aij=1) and [| ((x.))l 7 S K
VN' then the induced kernel for the contrastive loss is at least k2 (x, x') 2 1
Note, the adjacency matrix A for pairwise augmentations takes the form below assuming augmented samples are placed next to each other in order.
1
0
A
0
(42)
0
1
0
Before proceeding, we prove a helper lemma that shows that k.... k..,, is small if [[(())) (xx))]| is also relatively small with factor of dependence the dataset size.
20

---

Under review as a conference paper at ICLR 2023
Lemma B.3. Given kernel k(-, with map ((-) into RKHS H and SSL dataset {x,);-) 1
normalized such that k( x.) = 1, let K. be the kernel matrix of the SSL dataset. If [[
((x))]lH S then ||
K 8,8 ko, - K Koo... S | | IlV.e.
Proof. We have that
K Kg
K kg
sea
S | |kap.. k0
1/2
= =
((0(2))) ((ar))) ((2)))))))
1/2
N
(()())) ((x.o) - ((2x6)) H)
(43)
=
1/2
K
(0:)))1 - (1xx))1
K ||
VNc
We are now ready to prove Proposition 3.2
Proof. Note that _ e, where e; the vector with a 1 placed on entry and zeros elsewhere. we have that
From equation Equation
kn (æx x²)
Kin K_ [I + A)+ K
(K e, + e,) (I + A) (K KKrkker te,
=e] (I A) ej (Ki -,,) (I A) ej ge (I+A), A) (K ke e₁)
+ (K 3,8 kz e (I + A)_ (K ks,"' - -e).
(44)
Note that eạ (I+ 4) Bj = since Ai 1. Therefore,
(a x²) = 1 + K 3,0 K2. e (I+ + A) ej + + (I+ A)+ Koikkss' -e)
+ K 3,0 K0, e,) (I+ A) (K (K_1 ka,a' -e,)
(45)
2
K Kas
eill |I A) e, || 5,8 kaw -ell [) eill
+ K 5,a
ke, -
cill
[I
A)
K-tkk k - -eill
Let [xxx)= - (<x;)) || <c=
A
and [x(x') - x(x;))) <
K V| and by applying
5|l
k.
V
Lemma B.3 we have
k" (x, x') > -
K | kaz e:ll
|| + A) e + |K K ke, - ||[|||([ -ell||[
A) eill
+ | ke eill [I ( [A[+]]]] A) K ko e,ll
2 1 2v2 K 1 VN - 2 K 2,8 IINN2²
(46)
2 1 - (2V2+ + 2) K |
2 5/ K VN
A.
In the above, we used the fact that A is block diagonal with pairwise constraints (see Equation 42
so (I + A) eill = 22 and [I + A) = 2.
21

---

Under review as a conference paper at ICLR 2023
C IDEALIZATION OF DOWNSTREAM TASKS
In this section, we prove Proposition 3.3 copied below.
Proposition 3.3 (Ideal SSL outcome). Given supervised dataset of N points for binary classifi- cation drawn from distribution with mn and m41 connected manifolds for classes with labels -1 and +1 respectively, if the induced kernel matrix of the dataset K* successfully separates the manifolds such that k² x²) if x' are in the same manifold and k" (=. (x) = 0 otherwise, then sN (K*) 1 m41 = (1).
Proof. There m mn total manifolds in the dataset. Assume some ordering of these mani- folds from {1, (1, 1 + m-13 and let #(i) be the number of points in the i-th manifold.
The rows and columns of the kernel matrix K be permuted such that it becomes block diagonal with m411 + m-1 blocks with block é equal to #(6) #() 1 #(1) where 1 is the all ones vector of length k. L.e., K" permuted accordingly takes the form below:
1
#(1) #(1 ((1)
#(2) 1 #
(47)
1 # [m+++m-)) (mm41mm-1 # (mm++ +mmm)+mmm))
Each block of the above is clearly a rank one matrix with eigenvalue 1. Let Ymu vector containing all labels for entries in manifold Then we have
R+) be the
m4 +
y yI(K))
#(1) ((1 (m.))
mj
(48)
Σ
#V))=1((((1)
m+1 + m-
C.I PROOF OF GENERALIZATION BOUND
For sake of completeness, we include an example proof of the generalization bound referred to the main text. Common to classic generalization bounds for kernel methods from several prior works (Huang et al. 2021 Meir & Zhang 2003 Mohri et al. 2018 Vapnik 1999] Bartlett & Mendelson 2002), the norm of the linear solution in kernel space correlates with the resulting bound the generalization eгror. We closely follow the methodology of (Huang et al.] (021). though other works follow a similar line of reasoning.
Given a linear solution in the reproducing kernel Hilbert space denoted by w, we aim to bound the generalization error in the loss function E(y, v/) min(1, max(-1, v)) - y'l where y/ denotes binary classification targets in { {-1.1}. }. is the output of the kernel function equal to y = (w, x) for a corresponding input x in the Hilbert space or feature space. For our purposes, the solution w is given by e.g., Equation (12 equal to
N
w
Σ
K U], (z!!).
(49)
where (xx denotes the mapping of x we have that
(1)
to the Hilbert space of the kernel. Given this solution,
|w| V KT,K y.
(50)
The norm above controls, in a sense, the complexity of the resulting solution as it appears in the resulting generalization bound.
22

---

Under review as a conference paper at ICLR 2023
Given imput and output spaces X' and y respectively, let D be distribution of input/output pairs the support X' V. Slightly modifying existing generalization bounds via Rademacher complexity Mohri al. 2018). we prove the
arguments (Huang et al. 2021 Bartlett & Mendelson 2002
following generalization bound.
Theorem C.I (Adapted from Section 4.C of (Huang al. 2021)). Lel 21,...,, NN and y1..... :......yy.. UN, (with y the corresponding vector storing the scalars Yi as entries) be our training set of N indepen-
denote the solution to the kernel regression problem normalized by the trace of the data kernel. For an L-lipschitz loss function y x y + [0, b), with probability 1 8 for any
dent samples drawn ii.dd from D. Let = Tr(K)
N Σ [K-ty] (xx
we have
2V2L +
TT(K) yy K
log (2g(2/(0)) (2/(0((( 1)))
Bgg [e((w,, x),
No Σ ((w,,))),
3b1
V2
N
2N
(51)
To prove the above, we apply a helper theorem and lemma copied below.
Theorem C.2 (Concentration of sum; see Theorem 3.1 in Mohri et al. (2018). Let G be a family of functions mapping from Z to [0, 1]. Given N independent samples 21,..., 2n from Z. then for any the following holds:
> 0, with probability at least
1 Eg]g()] - N
N
log(2/8)
Σ
2 (G) + 33
(52)
2N
where Rs) denotes the empirical Rademacher complexity of G equal
1 N
Rs (G) = E.
sup gEG
asg((z))
(53)
where are independent uniform random variables over +1}.
Lemma C.3 (Talagrand's lemma; see Lemma 4.2 in Mohri et al. (018)). ). Let &b IR + R be L-Lipschitz. Then for any hypothesis set G of real-valued functions,
Rs( o G) S (.R(G))
(54)
Now, we ready prove Theorem C.I
Proof. We consider a function class G, defined as the set of linear functions on the reproduc-
ing kernel Hilbert space such that G, = {(w, ||/|| < 23. Given a dataset of inputs F1,.... EN in the reproducing kernel Hilbert space with corresponding targets y/.....: UN, let cw (x;) = =[(ww, x), y:) E [o. b). The inequality in Theorem C.2 applies for any given G, but would like this to hold for all 7 E 21, ... since || can be unbounded. Since our loss function é is bounded between [0, b). we multiply it by 1/b so that it is ranged in [0, 1] as needed for Theorem C.2 Then, we apply Theorem C.2 to e (x;) over the class G., for each y E {1, 11.2,33 ....
with probability dy = ō(e 1)e- This implies that
[x)
1 N
Σ
N
En (x:) S 2E,
sup ||
Σ ((s))
+3bg
log log(2/(8(e= - 1))) +7
N
2N
(55)
This shows that for any 7, the above inequality holds with probability 1 8(e 1)e-", However, we need to show this holds for all 7 simultaneously. To achieve this, we apply a union bound which holds with probability
Σm= = -ー ō(e 1)e- =
To proceed, we consider the inequality where 7 = [|| ? copied below.
N
N
log 12g(2/(8(e -))) +
Eg ((w((x))
Ew (xx) < 2E,
sup || w ?
N Σ (x))
+36l
N
2NV
(56)
23

---

Under review as a conference paper at ICLR 2023
Applying Talagrand's lemma (Lemma CB3
followed by the Seuuch--ccwaare inequality,
N
N
log(2/(8(e 1))) + w 1
Ex [Ew(()) (x)]
Σ (x:) S 2
sup
(2;)
+ +36V
N 1=1
||||| -
N
2N
t=1
1
log 1og(2/(0(e - 1))) + w
2
sup
(1 x.,)
+ 36V
N
2NV
==1
N
log(2/(8(e 1)))
28
2LE,
sup
|
0
+ +31
| 1|||1
2N
N
log (gg(2/(8(e 1))) +
$ 2LE,
[1
Σ
+ +3b
N 7=
2N
(57)
Expanding out the quantity have
N Σ
0.33%
and noting that the random variables are independent,
1
N
log(2/ 1))) +
Ex (x)]
(x,)
s 2L
[1|2||]
o
+ +3bV
N
2N
i=1
2L
log(2/(0(e 1))) + [|
[|] I
Σ (2;,
+ +3b1
2N
2L
N N
log(2/(8(e: 1))) + ||
<
[|
Er
+ +3/% 0z0 235)
N
2N
i=1 j=1
2L
N
log log(2/(8(e 1))) +
w 11
(< xz;) + /
N
2NV
2T.
log(2/(8(e - 1))) + w
[|ll|l Tr(K) 3b1
N
2N
(58)
Since we normalize such that Tr(K) = N, we have
1
N
2L
log(2/(0(e - 1))) +
Ex [w:)w(x)]]
cw (x
<
[||2]|]
1 + +.3b/
N
VN
2N
<
2L
[||w||]
+ 36p
log(2/(6(e 1)))
36
[|]]]]
(59)
VN
2N
V2N
2/2L
35
1og(2/ 2/(e 1)))
[|| [ +
36V
V2N
2N
Plugging in ||w||2 = yT K K--y and noting that normalized the kernel to have Tr(K) N thus
completes the proof.
D NUMERICAL EXPERIMENTS
All of our implementations are based on the common Python scientific library Numpy/Scipy (Harris et al. 2020) and runs CPU (no GPU used). Kernel algorithms were performed using the Scikit- learn package (Pedregosa et al. 2011. Hyperparameters were chosen via a grid search over the kernel algorithm parameters (e.g., regularization terms) and the loss function hyperparameters where appropriate. For calculation of the neural tangent kernel, we used the neuraltangents package (Novak
al. 2020
24

---

Under review as a conference paper at ICLR 2023
D.1
VISUALIZING THE CONTRASTIVE INDUCED KERNEL ON THE SPIRAL DATASET
b)
RSEE Keme
Kerne
Figure 5: Inner products comparison in the RBF kernel space (first row) and induced kernel space (second row). The induced kernel is computed based on Equation 7 and the graph adjacency matrix A is derived from the inner product neighborhood in the RBF kernel space, i.c., using the neighbor- hoods data augmentation. We plot three randomly chosen points' kernel entries with respect to the other points on the manifolds. a) When the neighborhood augmentation range used to construct the adjacency matrix small enough, the SSL-induced kernel faithfully learns the topology of the entangled spiral manifolds. b) When the neighborhood augmentation range used to construct the adjacency matrix too large, creates the "short-cireuit" effect in the induced kernel space. Each subplot the second is normalized by dividing its largest absolute value for better contrast.
Here, we provide the contrastive SSL-induced kernel visualization in Figure show how the SSL- induced kernel is helping to manipulate the distance and disentangle manifolds in the representation space. In Figure 5 we study two entangled 1-D spiral manifolds in a 2D space with 200 training points uniformly distributed on the spiral manifolds. We use the contrastive SSL-induced kernel, following Equation 7 to demonstrate this result, whereas the non-contrastive SSI.-induced kernel is provided earlier in the main text. We use the radial basis function (RBF) kernel to calculate the inner products between different points and plot a few points' RBF neighborhoods the first row of Figure 2 i.e., ((x1, exp( ||21 2n - As
see, the RBF kernel captures the locality of the 2D space. Next, we use the RBF kernel space neighborhoods to construct the adjacency matrix A and any training points with k(#1, x22) d treated connected vertices, i.e., A.j 1 and Aij = 0 otherwise. The diagonal entries of are O. This construction can be considered as using the Euclidean neighborhoods of as the data augmentation. In the second row of Figure 5 we show the selected points' inner products with the other training points in the SSL-induced kernel space. Given o, when d chosen small enough, we can see the second row of Figure aa) that the SSL-induced kernel faithfully captures the topology of manifolds and leads to a more disentangled representation. Figure b)) shows that when too large, i.e., an improper data augmentation, the SSI--induced kernel leads to the "short-circuit" effect, and the two manifolds are mixed in the representation space.
D.2 TIME SERIES DATA AND CIFARI0
We also add table additional empirical validation on a few time-series datasets extracted from UCR (Chen et al. 2015) well as a few controlled experiments on CIFAR10. 10. For the latter we pro- pose the same set-up as in our MNIST experiments: i.c., translation and rotation data-augmentation. implement translations and add white noise data-augmentation.
For the UCR experiments, Surprisingly, despite such simple augmentations, the SSL induced kernel achieves similar perfor- mance to the supervised baselines.
D.3 MNIST WITH NEURAL TANGENT KERNELS
In further exploring the performance of SSL kernel methods small datasets, perform further numerical experiments on the MNIST dataset using kernel functions derived from the neural tangent kernel (NTK) of commonly used neural networks (Jacot et al. 2018). We the neural-tan Saurelttangents package to explicitly calculate the NTK for a given architecture (Novak et al.) 2020). The basic setup is repeated from Section 4.2 where two different types of augmentations performed im-
25

---

Under review as a conference paper at ICLR 2023
Method
training size/#DA
100/20
100/30
200/20
300/20
Original kernel (w/ DA)
23.07
22.99
29.33
30.65
85.13
70,00
53.07
Original kernel (no DA)
21.49
21.49
26.81
29.16
84.86
64.00
52.49
SSL
22.68
23.62
27.52
29.53
93.78
68.00
52.84
Table 1: Test accuracy various datasets comparing the different methods. For CIFARIO, 10, the same augmentation was used as for MNIST (rotation + translation) while for the time-series dataset, translation and white noise was used. Every implementation uses the same methodology and hyperparameter tuning as that of the fig. experiment.
Test Set Accuracy
Num. Augmentations Algorithm
16
32
64
128
256
512
1024
Augmentation
Samples
Gaussian blur
16
self superviedd
32.3
32.3
32.6
29.1
32.8
32.3
32.5
baseline (no augment)
21.8
21.8
21.8
21.8
21.8
21.8
21.8
baseline (augmented)
34.8
34.9
35.0
35.0
self-supervised
71.8
71.8
71.6
71.4
72.1
baseline (no augment)
65.0
65.0
65.0
65.0
65.0
baseline (augmented)
74.6
74.6
74.7
74.7
74.7
256
self-supervised
87.5
88.0
88.0
baseline (no augment)
86.5
baseline (augmented)
88.6
88.6
88.6
translate, zoom
16
self- self-supervised
34.2
35.2
36.0
36.8
37.3
37.5
38.0
rotate
baseline (no augment)
21.8
21.8
21.8
21.8
21.8
21.8
21.8
bascline (augmented)
37.5
38.5
39.3
40.2
41.5
41.7
self-supervised
73.4
74.8
75.9
baseline (no augment)
65.0
65.0
65.0
65.0
65.0
baseline (augmented)
77.7
78.8
79.4
79.7
80.0
256
self superviedd baseline (no augment)
90.4
91.0
91.5
86.5
86.5
86.5
baseline (augmented)
90.4
90.8
91.1
Test accuracy of SVM using the neural tangent kernel of a 3 layer fully connected network in only supervised (baseline) setting or via the induced kernel in self-supers supervised setting. The induced kernel for the SSL algorithm is calculated using the contrastive induced kernel. Numbers shown above are the test set accuracy for classifying MNIST digits for small dataset sizes with the given number of samples. Due to the quadratic scaling of memory and runtime for kernel methods, we restricted analysis to more feasible settings where there were less than 25,000 total samples (number of augmentations times number of samples).
Table 2: NTK for 3-layer fully connected network:
ages. As before, we consider augmentations by Gaussian blurring of the pixels or small translations, rotations, and zooms.
Test set accuracy results are shown in Table for the NTK associated 3-layer fully connected network with infinite width at each hidden layer. Similarly, in Table we show similar analysis for the NTK a CNN with seven convolutional layers followed by a global pooling layer. We use the contrastive induced kernel for the SSL kernel algorithm. The findings are similar to those reported in the main text. The SSL method performs similarly to the baseline method without any self-sun supervueere learning but including labeled augmented datapoints in the training set. In some cases, the SSL method even outperforms the baseline augmented setting.
D.4 ANALYSIS OF DOWNSTREAM SOLUTION
To empirically analyze generalization, we track the complexity quantity sN (K) here defined in Equation 13 and copied below:
Tr(K) N y
SN (K)
K
(60)
26

---

Under review as a conference paper at ICLR 2023
Test Set Accuracy
Num. Augmentations Algorithm
16
32
128
256
512
1024
Augmentation
Samples
Gaussian blur
self-supervin superviddd
28.4
28.4
28.
28.4
28.3
28.3
28
baseline (no augment)
25.6
25.6
25.6
25.6
25.6
25.6
25.6
baseline (augmented)
26.6
26.6
26.6
26.6
26.6
26.6
26.6
64
self-supervised
60.0
60.0
60.1
60.1
60.1
baseline (no augment)
55.6
55.6
55.6
baseline (augmented)
56.5
56.5
56.5
56.5
56.5
256
self self-supervised
87.6
87.9
87.6
baseline (no augment)
81.5
81.5
81.5
baseline (augmented)
82.9
82.9
82.9
translate, zoom
self-supervised
33.4
33.8
34.4
34.6
35.1
35.4
35.3
rotate
baseline (no augment)
25.6
25.6
25.6
25.6
25.6
25.6
25.6
baseline (augmented)
30.6
30.7
30.8
31.6
31.7
31.9
32.0
64
self-supervised
70.7
72.7
73.2
73.8
74.3
baseline (no augment)
55.6
55.6
baseline (augmented)
66.0
67.8
68.8
69.5
70.2
256
self- superviedd
91.9
92.3
92.6
baseline (no augment)
81.5
81.5
81.5
baseline (augmented)
89.5
90.3
Table 3: NTK for 7-layer convolutional neural network: Test set accuracy of SVM using the neural tangent kernel of CNN with 7 layers of 3 3 convolution followed by global pooling layer. The induced kernel for the SSL algorithm is calculated using the contrastive induced kernel and compared to the standard SVM using the kernel itself with or without augmentation. Numbers shown above are the test set accuracy for classifying MNIST digits for small dataset sizes with the given number of samples. Due to the quadratic scaling of memory and runtime for kernel methods, restricted analysis to more feasible settings where there were less than 25,000 total samples (number augmentations times number of samples).
Figure Depiction of sx(K) (Equation (3) for the case of MNIST classification depicted in the left figure in Figure 4 computed on the training set. This setting considers MNIST clas- sification with the contrastive kernel on a 10000- sample dataset with 100 original MNIST samples and 100 augmentations. s (K) for the super- vised baselines for the full dataset (including la- beled augmented samples) and only the original dataset (no augmented samples) are calculated as approximately 1534 and 203 respectively. Many values (K() are smaller than the baseline numbers especially at points where the test set accuracy for the SSL induced kernel was com- paritively larger. Here, recover the trend of the test set performances obtained from Figure showing that 8 (K) is potentially good indi- cator of test accuracy.
sup. baselines: 1534.24, 203.64
0.1
100
inv. 12 regularization
1
10
243
344
364
99
300
100
1584
2036
2010
99
100
1000
14998
25783
28385
100
16
64
128
256 512
representation dimension (K)
where y is vector of targets and K is the kernel matrix of the supervised dataset. As reminder, the generalization gap can be bounded with high probability by O O(ysN (K)N), and in the main text, we provided heuristic indication that this quantity may be reduced when using the induced kernel. Here, we empirically analyze whether this holds true in the MNIST setting considered in the main text. As shown in Figure 6 the SSL induced kernel produces smaller values s (K) than its corresponding supervised counterpart. We calculate this figure by splitting the classes into binary parts (even and odd integers) in order to construct a vector that mimics binary classification task. Comparing this to the test accuracy results reported in Figure 4 it is clear that xx( (K) also correlates
27

---

Under review as a conference paper at ICLR 2023
inversely with test accuracy as expected. The results here lend further evidence to the hypothesis that the induced kernel better correlates points along a data manifold as outlined in Proposition 3.3
28


Reviews:
[{"review_id": "y5xAywH022", "reviewer": "Reviewer_qCTa", "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": "This paper studies self-supervised learning (SSL) with kernels. The authors prove the representer theorem for SSL and provide explicit expressions of the optimal induced kernel for some SSL methods using contrastive or non-contrastive loss functions. The prediction accuracy on downstream tasks is analyzed based on the complexity quantity related to kernels. In numerical experiments, the authors investigate hyper-parameter tuning and the relation between data augmentation and generalization property. ", "summary_of_the_review": "Though the theoretical results in the paper are rigid, the scope of the paper seems narrow. ", "strength_and_weaknesses": "Strength\n- The paper considers SSL with a linear map on an RKHS. Due to the restriction of the problem setting, the authors provide simple theoretical results that promote an intuitive understanding of SSL. The problem falls into a simple optimization problem. An explicit form of the solution is presented for non-contrastive/contrastive loss. \n\nWeaknesses\n- Nowadays, SSL is widely used for learning tasks with large data sets. Considering such a situation, the scope of this paper is relatively narrow. This paper focuses on SSL with kernel features. Though Proposition 3.1 deals with a general class of loss functions, the theoretical analysis is provided only for VICReg loss and spectral contrastive loss.\n- In analyzing the generalization performance of downstream tasks, the complexity quantity s_N(K) is considered. It is unclear how the complexity quantity relates to the concept of alignment and uniformity [1], which are regarded as important features in SSL.[1] Wang, and Isola, Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere, ICML,2020.\n- In numerical experiments, feature extraction with RBF kernel is reported. However, most readers will be interested in feature extraction using deep neural networks (DNNs). The authors showed the SSL with neural tangent kernel (NTK) regime in the appendix. The authors should conduct intensive numerical studies using DNN and investigate how much their theoretical findings for the NTK regime explain numerical results. Though the authors discussed it in section 5, the numerical results in the present paper are not very informative in understanding the usefulness of SSL 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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "a0KMqN14JR", "reviewer": "Reviewer_Gmj4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors consider \"joint embedding\" self-supervised learning (SSL) formulations applied to a kernel learning setting.  That is, finding / learning a linear mapping in the feature space (induced by some kernel) that minimizes commonly used SSL learning objectives, such as for contrastive learning.\n\nThe authors prove properties about this mapping function and the solution to such problems, and derive closed form optimal solutions to specific formulations (objectives), as well as a semi definite programming formulation to solve a general objective over batches.\n\nThe authors experimentally explore the SSL kernel induced kernels - comparing the induced kernel from the SSL formulation (which leverages an adjacency matrix as part of fitting the kernel space mapping / the SSL objective) with the base kernel (RBF kernels used with NTK in the appendix).  They compare qualitatively by plotting the similar pairs under each kernel on the spiral toy dataset, and compare classification accuracy and for varying hyper parameters / settings. ", "summary_of_the_review": "While the development of the properties and formulations, and closed form solutions for this approach to learning and induced SSL kernel could be useful, overall I feel more like the paper is incomplete and lacks a coherent purpose and objective to achieve, and so falls short.  I think it could benefit from more experiments and comparisons, and elucidating the connection with current SSL approaches and what it reveals about them (as motivated in the introduction).   ", "strength_and_weaknesses": "Strengths:\n1. It is an interesting idea and direction to consider contrastive / SSL representation learning approaches from the perspective of kernel learning.\n\n2. Several useful properties are proven about the SSL kernel formulation, and solutions derived (including closed-form) for SSL formulations / objectives - which could be useful to researchers and practitioners.\n\n3. Analysis and experiments were formed to better understand ad explain the SSL induced kernels.\n\nWeaknesses:\n1.  The paper feels a bit incomplete - the properties developed are not unexpected, and the intro argues for understanding of common modern SSL representation learning methods.  However, the paper really just presents a kernel algorithm for SSL and there does not really seem to be a connection to deep learning based SSL learning methods.\n\nEssentially it's not really clear what is the real goal or objective of the paper.  If it's to propose a new SSL representation learning algorithm using kernel representations, then it needs more experiment evaluation to demonsrate its benefits over existing approaches.  If instead it's to reveal insights about current SSL representation learning approaches and losses used - this was also not accomplished.  As such, it doesn't feel complete.\n\n2. Experiments seem lacking.  Comparison with more methods and more datasets would be better.  As mentioned above, if the point is a new kernel SSL algorithm - more thorough comparison with other kernel algorithms and with existing representation learning algorithms on multiple datasets and tasks should be done - not just a simple classification task on EMNIST and MNIST comparing only to using the standard SVM classifier with RBF kernel.   If the point is to understand modern SSL algorithms, experiments using those algorithms and showing how the proposed method helps understand their results should be included.\n\nAdditionally the classification results do not seem very convincing for the benefit of using the proposed approach - in particular if I understand it correctly, Figure 3 show that the accuracy by simply using augmented training data as opposed to the induced kernel based on the augmentations consistently yields higher test accuracy.\n\n\n3. The results / resulting formulations and properties are not very surprising / seem somewhat expected, including the method itself, and seem similar and closely related to much prior work on learning on graphs or manifolds (using kernels).  It's not completely clear to me how this brings much novelty beyond past kernel approaches to learning across a graph / manifold - as these use the graph laplacian / manifold assumption in a similar way.  I think more discussion and comparison is warranted.  Baselines for comparing prediction results for a relationship-informed kernel learning representation approach should include such laplacian / manifold informed versions of the corresponding estimators, like graph / manifold regularized SVM.\n\nExamples of such work:\n- \"Kernels and Regularization on Graphs\" Smola and Kondor.\n- \"Learning on Graph with Laplacian Regularization\" Ando and Zhang\n- \"Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples\" Belkin et al.\n\n\n4. Minor comments: \n- In the introduction, one type of self supervised learning missing is the other major class of SSL not mentioned - predicting held-out parts of the input data (as in transformer models).\n- Figure 1 does not seem very helpful to me and doesn't seem to explain anything. \n\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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DJBt2APRYc", "reviewer": "Reviewer_FCEZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Modern methods in SSL form representations based on known or constructed relationships between samples and are particularly effective in this task. Here, this paper aim to extend this framework to incorporate algorithms based on kernel methods, where the embeddings are constructed from linear maps acting on the kernel feature space. ", "summary_of_the_review": "1、For a contrastive and non-contrastive loss, this paper provide closed form solutions when the algorithm is trained over a single batch of data.\n2、This paper show that a version of the representer theorem in kernel methods can be used to formulate kernelized SSL tasks as optimization problems.\n", "strength_and_weaknesses": "Strengths:\n1、The theoretical derivation is rigorous;\n2、The contribution description is relatively clear;\n3、The writing process is clear.\n\nWeaknesses:\n1. Please describe the motivation of the proposed method in detail in the abstract;\n2. For the organization of other parts of this article, it should be directly specific to the chapter, rather than described in sequence;\n3. In the experimental part, the equipment type used and some hyper-parameter settings (the specific usage of the data set) should be described in detail;\n4. The experimental part only proves the effectiveness of the proposed method, and does not compare with other advanced algorithms;\n5. The design concept of the paper is complicated and cumbersome, please prove its reproducibility;\n6. The last sentence of the paragraph above equation (14) lacks punctuation;\n7. Tables are also a language. Don't just mention that the results of your proposed method are better than others, but try to explain why.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject