A theoretical study of inductive biases in contrastive learning
Authors: Jeff Z. HaoChen
Tengyu Ma
Venue: ICLR 2023 poster (2023)
Keywords: theory of self-supervised learning
theory of contrastive learning

Abstract: Understanding self-supervised learning is important but challenging. Previous theoretical works study the role of pretraining losses, and view neural networks as general black boxes. However, the recent work of [Saunshi et al.] argues that the model architecture --- a component largely ignored by previous works --- also has significant influences on the downstream performance of self-supervised learning. In this work, we provide the first theoretical analysis of self-supervised learning that incorporates the effect of inductive biases originating from the model class. In particular, we focus on contrastive learning --- a popular self-supervised learning method that is widely used in the vision domain. We show that when the model has limited capacity, contrastive representations would recover certain special clustering structures that are compatible with the model architecture, but ignore many other clustering structures in the data distribution. As a result, our theory can capture the more realistic setting where contrastive representations have much lower dimensionality than the number of clusters in the data distribution. We instantiate our theory on several synthetic data distributions, and provide empirical evidence to support the theory.

Published as a conference paper at ICLR 2023
A THEORETICAL STUDY OF INDUCTIVE BIASES IN CONTRASTIVE LEARNING
Jeff Z. HaoChen & Tengyu Ma
Department of Computer Science Stanford University {jhaochen, @ew.mmmmassaaaa.....oommm
ABSTRACT
Understanding self-supervised learning is important but challenging. Previous theoretical works study the role of pretraining losses, and view neural networks as general black boxes. However, the recent work of [Saunshi et al. (2022) argues that the model architecture a component largely ignored by previous works also has significant influences on the downstream performance of self- supervised learning. In this work, we provide the first theoretical analysis of self-supervised learning that incorporates the effect of inductive biases originating from the model class. In particular, we focus on contrastive learning popular self-supervised learning method that widely used in the vision domain. We show that when the model has limited capacity, contrastive representations would recover certain special clustering structures that are compatible with the model architecture, but ignore many other clustering structures in the data distribution. As result, our theory can capture the more realistic setting where contrastive representations have much lower dimensionality than the number of clusters in the data distribution. We instantiate our theory on several synthetic data distributions, and provide empirical evidence support the theory.
INTRODUCTION
Recent years have witnessed the effectiveness of pre-trained representations, which are learned on unlabeled data with self-supervised losses and then adapted a wide range of downstream
tasks (Chen al. 2020aa b He et al.) 2020; Caron et al., 2020 Chen et al. [020c] Gao et al.) [021]] Su et al. 1021] Chen & He 2020 Brown ct al. 2020 Radford et al. 2019)). However, understanding
C
the empirical success of this emergent pre-training paradigm is still challenging. It requires novel mathematical frameworks and analyses beyond the classical statistical learning theory. The prevalent use of deep neural networks self-supervised learning also adds to the mystery.
Many theoretical works focus on isolating the roles of self-supervised losses, showing that they encourage the representations capture certain structures of the unlabeled data that are helpful for downstream tasks (Arora et al. 2019 HaoChen et al. 2021 2022 Wei et al. [202]] Xie et al. [02T]] Saunshi et 2020). However, these works oftentimes operate the sufficient pre-training data (polynomial in the dimensionality) or even infinite pre-training data regime, and view the neural network as black box. The only relevant property of neural networks these works is that they form a parameterized model class with finite complexity measure (e.g., Rademacher complexity).
Recently, Saunshi et al. (2022) argue that the pre-training loss is not the only contributor to the performance of self-supervised learning, and that previous works which view neural networks as a black box cannot tell apart the differences in downstream performance hetween architectures (c.g., ResNet (He et al. (015)) vs vision transformers (Dosovitskiy et al., (2020)). Furthermore, self-supervised learning with an appropriate architecture can possibly work under more general conditions and/or with fewer pre-training data than predicted by these results on general architecture. Therefore, more comprehensive and realistic theory needs to take into consideration the inductive biases of architecture.
This paper provides the first theoretical analyses of the inductive biases nonlinear architectures in self-supervised learning. Our theory follows the setup of the recent work by HaoChen et al. (2021)

---

Published as a conference paper at ICLR 2023
implementable
not implementable x
0.5
spurious
spurious dimension
dimension
invariant dimension
invariant dimension
Figure 1: A simple example where the linear function class learns the correct feature and ignores the spurious feature. A simplified version of the synthetic example proposed in [Saunshi et al. at (002). The orange points are the original data and blue points are augmented data (obtained by adding noise in the spurious dimension). The dimension invariant augmentation desired. Edges represent positive pairs that are constructed from augmentation. We say a real-valued function implements a cluster if it outputs on the cluster and outputs on all other data. We note that here implementing means matching the exact value, rather than simply matching the label after applying some linear threshold. The figure above shows two possible ways partition the data into two clusters, but only the one on the left-hand side (which captures the invariant dimension) is implementable by linear function. Here we use black numbers to indicate the target output on the data, and green numbers to indicate the output of the implementing function which extrapolates outside of the data support. Note that linear model is not composed with a threshold function. The partition the right hand side is not implementable because any linear model that outputs constant on the upper-left small cluster would also output on the bottom-left small cluster due to linear extrapolation. Here use red numbers to indicate the output of the linear function that contradicts with the target.
on contrastive learning and can be seen as a refinement of their results by further characterizing the model architecture's 's impact the learned representations.
We recall that HaoChen et al. 2021) shows that contrastive learning, with sufficient data and a parameterized model class of finite complexity, is equivalent to spectral clustering a so-called population positive-pair graph, where nodes are augmented images and an edge between the nodes and x' is weighted according to the probability of encountering (x,,²)) as a positive pair. They essentially assume that the positive-pair graph contains several major semantically-mennigg clusters, and prove that contrastive representations exhibit corresponding clustering structure in the Euclidean space, that is, images with relatively small graph distance have nearby representations.
Their results highly rely on the clustering property of the graph- the representation dimensionality and pre-training sample complexity both scale in the number of clusters. The important recent work of TSunnshi et al. (2022), however, demonstrates with synthetic setting that contrastive learning can provably work with linear model architectures even if the number of clusters is huge (e.g., exponential in the dimensionality). Beyond the simple synthetic example discussed in their paper, there has been no previous work that formally characterizes this effect in general setting.
In this work, we develop a general theory that leverages the inductive bias to avoid the dependency on the potentially huge number of clusters: although there exists large number of clusters in the positive-pair graph, the number of clusters implementable by the model (which we call minimal implementable clusters) could be much smaller, even exponentially. Figure I shows an example where a linear function can only implement one clustering structure but not the other, despite both being valid clusters in the positive-pait graph. It's possible that a minimal implementable cluster consists of multiple well-separated sub-clusters but none of these sub-clusters can be implemented by the model class.
2

---

Published as a conference paper at ICLR 2023
We show that contrastive representations would only recover the clustering structures that compatible with the model class, hence low-dimensional contrastive learned representations would work well the downstream tasks. Concretely, suppose the number of minimal implementable clusters is m which can be much smaller than the number of natural clusters in the graph m. HaoChen al.] (202T) prove the efficacy of contrastive learning assuming the representation dimensionality (hence also sample complexity) is larger than m. We develop a new theory (Theorem D that makes the representation dimensionality only depend on m instead of m. We also extend this result to more complex setting where we can deal with even more structured clusters, e.g., when there are 2 clusters with certain geometric structures, but the representation dimensionality can scale with only s instead of 2". See Theorem 2 and its instantiation on Example for this result.
We instantiate our theory on several synthetic data distributions and show that contrastive learning with appropriate model architectures can reduce the representation dimensionality, allowing better sample complexity. We consider data distribution on hypercube first proposed by |Saunshi ctt al. 2022) which contains small subspace of features that are invariant to data augmentation and large subspace of spurious features. When the function class is linear, contrastive representations can solve downstream binary classification tasks if the downstream label only depends on dimension of invariant features (Theorem B). When the function class is ReLU networks (hence more expressive), we show that the contrastive representations can solve more diverse downstream classification problems where the label can depend on all invariant features (Theorem 4). We also provide examples for Lipschite-continuous function classes (Theorem 5) and convolutional neural networks (Theorem 6
show that the
We provide experimental results to support our theory. We propose a method to test the number of implementable clusters of ResNet- 18 on the CIFAR-10 dataset and show that there are indeed only a small number of implementable clusters under the model architecture constraint (Section B).
2 RELATED WORKS
The empirical success of contrastive learning has attracted a series of theoretical works that study the
contrastive loss (Arora et al. 2019 HaoChen et al. 2021 2022 Tosh et al., 2020 2021: Lee al.)
2020 Wang et al. 2021 Nozawa & Sato 2021; Ash et al. [022 Tian. 2022). most of which treat
the model class as black box except for Lee ct al. (2020) which studies the learned representation
with linear models, and Tian 2022) and Wen & (20T)) which study the training dynamics of
contrastive learning for linear and 2-yayer ReLU networks.
Several theoretical works also study non-contrastive methods for self-supervised representation learning (Wen & Li. 2022 Tian et al. 2021 Garrido et al. 2022, Balestriero LeCun 2022). There also works theoretically studying self-supervised learning in other domains such language
modeling (Wei et al. 2021 Xie et al. 2021 Saunshi et al. 2020).
3 FROM CLUSTERS TO MINIMAL IMPLEMENTABLE CLUSTERS
In this section, we introduce our main theoretical results regarding the role of inductive biases of architectures in contrastive learning. Recall that contrastive learning encourages two different views of the same input (also called a positive pair) to have similar representations, while two random views of two different inputs (also called a negative pair) have representations that are far from each other. Formally, we use Pdata to denote the distribution of random view of random input, use Ppos to denote the distribution instance, X' is the set of all augmentations of all images for visual representation learning.
random positive pair, and X' to denote the support of Pdata- For
Following the setup of HaoChen al. (0022), for a representation map f : + R where k the representation dimensionality, we learn the contrastive representation by minimizing the following generalized spectral contrastive loss:
(x) = B(2,z)) (rrat [1) - f(x f(x X ARR(),
(1)
3

---

Published as a conference paper at ICLR 2023
positive pair
Positive-pair graph
A demonstration of the positive-pair graph. When the positive pairs are formed by applying data augmentation (such as rotation) to the same natural image, data with the same semantic meaning (e.g.. the two butterfly images) tend to belong the same cluster in the vositive-pair graph. Datapoints with different semantic meanings (e.g., a butterfly image and a clock image) would not be connected in the positíve-pair graph, hence belongs different clusters.
Figure 2:
where À > 0 is hyperparameter indicating the regularization strength, and the regularizer normalizes the representation covariance towards the identity matrix:
R()) Ezrpaar [x)
This loss is very similar to the popular Barlow Twins loss (Zbontar et al. 2021 and has been shown to empirically work well (HaoChen et al.) 2021).
Theoretically, the prior work proposes the notion positive-pair graph with X' being the vertex set and an edge between the nodes z and x' is weighted according to the probability of encountering <r,,x") as a positive pair (i.e., Ppoc(1r, x')). This graph is defined on the population data, and intuitively captures the semantic relationship between different data when the positive pairs are formed by applying data augmentation to the same natural data, is expected that datapoints in the same cluster in the positive-pait pair graph would have similar semantic meanings. Figure gives demonstration of the positive-pair graph.
Their analysis shows that learning contrastive representations with the above loss is equivalent to spectral clustering Ng et al. (2001) on this positive-pair graph, hence can learn meaningful representations when the graph has clustering structures.
Different from the prior work, we study the representation map that minimizes the contrastive loss within certain function class J. Here assume functions in F map data in X' to representations in & for some dimensionality k. The main contribution of our result is the improvement of & due the consideration of this specific function class: by studying the representation learned within constrained model class F, we will show that the necessary representation dimensionality A is much smaller than that required the prior work. As a result, the sample complexity for the downstream labeled task would be improved compared to the prior work.
Let {S1, S2, ... Sm3 be m--wy partition of X, i.c. they are disjoint non-empty subsets of X such that X' = Use(m] S. For any E X, let id, be the index such that æ E Sa.- We consider a partition of the graph such that there not much connection between any two clusters, which formalized by the following assumption.
Assumption (a-separability). The probability of a positive pair belonging to two different sets less than a::
Pr [1r, Jo-ppon
(idz + idg+) Sa.
We consider downstream tasks that r-way classification problems with label function y(-) [r). We assume that the downstream task aligns with the clusters:
Assumption 2. The downstream label y(x) is constant each S..
Our key assumptions about the function class are that it can implement desirable clustering structures (Assumption 4 but cannot break the positive- pair graph into too many clusters (Assumption 3
Let S C X be a subset X. p be the distribution Pdata restricted to set S, and p be the positive pair distribution Ppos conditioned on both datapoints in the pair belonging to set S. For any
4

---

Published as a conference paper at ICLR 2023
function g g - R. define the following expansion quantity:
Qs(g) = B(z,at)ngg [(((z) ))²)
E Ex wp Panta (g(x)) 9x')))
Pata
We let Qs(g) = Do if the denominator is O. Here the numerator represents the discrepancy between a random positive pair, and the denominator represents the global variance of g. Intuitively, smaller value (g(g) means that function y does a better job at separating the set S into disjoint sub-clusters, and hence implements an inner-cluster connection structure that is sparse. For instance, if S contains two disjoint sub-clusters, and 9 has different constant values each of them, then (s(g) 0. On the other hand, S is densely connected, then @s(g) > regardless of the choice of g.
The first assumption about the function class F assumes that function in the class break one cluster into two well-separated sub-clusters:
Assumption (F-implementable inner-cluster connection larger than 3). For any function f E F and any linear head w R* let function g w f()). For any E [m] we have that:
Qs. (g) 2 B.
(5)
We note that when the function class F contains all the functions from X' to R Assumption essentially says that each of {S1, S2. Sm) has large internal expansion, hence recovers Assumption 3.5 in HaoChen et al. (202T). However, when F has limited capacity, each cluster St can still contain well-separated sub-clusters, but just those sub-clusters cannot be implemented by functions in F.
Assumption 3 implies that the function class cannot be too expressive. However, in order for the leamned representation map to be useful for downstream tasks, it needs to be expressive enough to represent the useful information. Thus, we introduce the following assumption on the function class.
Assumption 4 (Implementability). Recall that idg is the index such that x Sa.,. There exists function f E F such that f(z) eid_ for all x E Pdata where E R is the vector where the i-th dimension and other dimensions
When both Assumption and Assumption hold, say 12,, (5m) are minimal implementable clusters with respect to F.
We also introduce the following Assumption 5 which is for any function class implemented by a neural network where the last layer is linear. We note that this assumption is needed only for the technical rigour of the proof, and is not essential to the conceptual message our theory.
Assumption 5 (Closure under scaling). For any function f E F and vector E R define function (x) = u C fzx) where & means element-wise product. Then, we have f' E F.
Let Pmin == minse(m] Pra-paan (x E St) and Pmux = maxie[m] Pracppaata (x E St) be the sizes of the smallest and largest sets respectively. Under the above assumptions, have the following theorem that shows learning a representation map within F and representation dimensionality k m can solve the downstream task:
Theorem 1. Suppose (S,,S2- S.,) are minimal implementable clusters with respect F (i.e., Assumptions
and the function class F satisfies Assumptions AssumptionssAnndd Andd For X >> a/ Pmin. consider a learned representation map f = arg min Lx( that minimizes the contrastive loss. Then, when i m, for any downstream task that satisfies Assumption there exists a linear head W E grak which achieves downstream error
Excesiaa ((x) [ eyccell?
S
P Pmmie
max
We note that Pmax Pmin when the partitions are balanced. Thus, long & Pmin (i.e., the probability of a positive pair crossing different clusters smaller than the probability of it containing data from the smallest cluster), the right-hand side is roughly a/3. Thus, when the inter-cluster connection a is smaller than the cluster connection that implementable by the function class B, the downstream accuracy would be high.
5

---

Published as a conference paper at ICLR 2023
Comparison with HaoChen et al. (2021). We note that result requires k m, whereas HaoChen et al. (2021) provides analysis in a more general setting for arbitrary &s that is large enough. theorem recovers special case of HaoChen et al. (2021). Our result requires a stricter choice of k mainly because when J has limited capacity, higher dimensional feature may contain lot of "wrong features" while omitting the "right features", which is phenomenon that doesn't I occur when F contains all functions.
Thus, when the function class FF is the set of all functions,
4 AN EIGENFUNCTION VIEWPOINT
In this section, we introduce an eigenfunction perspective that generalizes the theory in the previous section more general settings. We first introduce the background on eigenfunctions and discuss its relation with contrastive learning. Then we develop theory that incorporates the model architecture with assumptions stated using the language of eigenfunctions. The advantage over the previous section that we can further reduce the required representation dimensionality when the minimal implementable clusters exhibit certain internal structures.
Our theory relies on the notion of Laplacian operator L. which maps a function X - R to another function L(g)= X + R defined as follows.
((g)()) := g(x) ff Poos Pros( x²) g(x')de'.
Peuna (x)
We say a function g is an eigenfunction with eigenvalue vp E E if for some scalar yb
Ez-pinta [11b= g(x) - [=g)(=))²] = 0.
(8)
This essentially means that L(g) g the support of pdata- Intuitively, small eigenfunctions (i.e., eigenfunctions with small eigenvalues) correspond to clusters in the positive-pair graph. To see this, let g implement the indicator function of cluster S, i.e., g(x) = 1 if E S, and g(x) 0 if x & S. One can verify that (zg)(x) = for all æ, thus g is an eigenfunction with eigenvalue 0.
In this section, provide generalized theory based characterizing the implementability of eigenfunctions. Intuitively, we will assume that there exists k (and only k) orthogonal eigenfunctions in the function class with very small eigenvalue, and the downstream task can be solved by these cigenfunctions. More formally, let ø 2 be a very small real number (can be thought as 0), and fzig(z) X + I2* be a k-dimensional representation map the function class JF such that
E (a.art) )~Ppos [(l - fcig( (x (1) <
(9)
and
Exeeaaca (eeg(
=
(10)
Intuitively, when á is small, each dimension of Seig corresponds to one eigenfunction of the graph
Laplacian with small eigenvalue, as formalized by the following Proposition I in the case of Φ 0.
Proposition 1. For any E [k] and any function feig satisfying equation 9 with o = and equation 10 we have that function g(x) = (x)s is an eigenfunction of LL with eigenvalue O.
Recall that our assumptions in the previous section intuitively say that even though a larger number of clusters exist in the positive-pair graph, many of them are not implementable by the function class. From the eigenfunction viewpoint, this means that only small number of eigenfunctions with small eigenvalue are the function class. Thus, we can make the following corresponding assumption which says that the vector-valued function feig contains all the implementable eigenfunctions with small eigenvalue.
Assumption 6. Suppose is function implementable by F (in the sense that g(z) f(x); some f F and E [k) and
B(gaat)-ppal ((((x) (){] Z. Egroetar [g(x))]
(11)
then there exists it & such that
Ex-panes [(w Seig (x) g(x))2] Sc
(12)
Here both d and are very small and be thought 0.

---

Published as a conference paper at ICLR 2023
We consider downtream tasks that can be solved by feig- Let v()) E R'' be vector that represents the downstream label of data x (c.g., the one-hot embedding of the label when the downstream task is classification). We have the following assumption the downstream task:
Assumption 7. There exists linear head W E R with norm ||W* 11 S B such that
Eer-paata [ feig(() - Mx) S.
(13)
Here is very small and can be thougth as O.
We have the following theorem using the above two assumptions:
Theorem 2. Suppose function Seig E F satisfies Assumptions o with (Ø, c) and Assumption 7 with
(B Suppose & > & or é Φ 0. Then, any X > O such that & S Φ(1 10l-vol /V///// (/)) and learned representation map f arg miz Lx(f), there exists linear head W B such that
E Eg-paann [|] [[)) -0= 5 35+BB B²k(c+
(14)
Since Ç, and @ are all very small values. the RHS of equation 14 is very small. hence the learned representation acheives small downstream error. As we will see the first example in the next section, Theorem 2
indeed allows the representation dimensionality to be smaller than the number of minimal implementable clusters in the graph, hence generalizes the result in the previous section.
Relationship between Theorem 2 and Theorem | We note that in the setting of Theorem the identity function of each minimal implementable cluster would be an achievable eigenfunction. Theorem 2 considers more general situation than Theorem [ where the minimal implementable clusters may not be well-defined, yet still we can show good results when the dimensionality is equal to the number of achievable cigenfunctions. We will mainly use Theorem 2 for the examples because it's more general and easier to be used, whereas we present Theorem because it's more intuitive understand. For instance, in Example Theorem T only applies when 1, whereas Theorem appplie for arbitrary s.
5 INSTANTIATIONS ON SEVERAL SYNTHETIC DATA DISTRIBUTIONS
In this section, we instantiate our previous theory on several examples of data distributions and show that when the model class has limited capacity, one can learn low-dimensional representations using contrastive learning and solve the downstream task with simple linear probing. In all of these examples, if we to be much higher, and hence more downstream samples are needed. These results demonstrate the benefit of leveraging inductive biases of the model architecture in contrastive learning.
much more expressive model class, the representation dimensionality needs
5.1 LINEAR FUNCTIONS
Our first example is the hypercube example proposed in Saunshi et al. (2022).
Example The natural data ē ~ 111, is the uniform distribution over the d-dimensional cube. Given natural data 3, an augmented data x ~ A(ø) is sampled as follows: first uniformly sample scalar 1 [ 11, then scale the 11 to d-th dimensions of it with т, while keeping the first dimensions the same. Intuitively, the last d dimensions correspond to spurious features that can be changed by data augmentation, and the first dimensions are invariance features that contain in formatioon about the downstream task. The downstream task is binary classification problem, where the label y(x) = sgn(x.) (x) is the sign function of one of the first s dimensions [s].
We consider contrastive learning with the linear function class defined below:
Definition (Linear function class). Let U BRe be a matrix and we use fo (x) = Ux to denote the linear function with weight matrix U. We define the k-dimensional linear function class as Funeear {fv : E
R &x
Saunshi et al. 2022) directly compute the learned representations from contrastive learning. Here we show that the example can be viewed as an instantiation our more general Theorem 2 In particular, we have the following result:
7

---

Published as a conference paper at ICLR 2023
Theorem 3. In Example | suppose set the output dimensionality as k and learn a linear representation map that minimizes the contrastive loss arg min fe (x) for any À O. Then, there exists linear head w E IK such that
Eg-pass [1 f(x) yz)))²²=
(15)
In contrast, suppose the function class is the set of universal function approximators Funi- So long as the output dimensionality is no more than 2d-1, there exists solution f E arg minseF.. Cx(f)
such that for any linear head E IR*, we have
Eapopaan [(w' f(0)-
(16)
We note that as an implication of the lower bound, previous works that analyze universal function approximators (Arora et al. 2019] Tosh et al., 2021 HaoChen al. al.] [202]) wouldn' 't be able show good downstream accuracy unless the representation dimensionality is larger than 2d-1, In contrast, our theory that incorporates the inductive biases of the function class manages to show that much
lower representation dimensionality k suffices.
We also note that this example shows a situation where Theorem works but Theorem doesn't i, hence demonstrating how our theory derived from the eigenfunction viewpoint allows for lower representation dimensionality. There are 2 model-restricted minimal clusters the graph, each encoded by configuration of the feature dimensions. However, all the function in Flnncar that implment a cluster span in s-dimensional subspace, thus we can find s-dimensional eigenfunctions that satisfies Assumption 6 As result, learning s-dimensional representations already suffices for solving the downstream task.
5.2 RELU NETWORKS
In the previous example, the downstream task is only binary classification where the label is defined by one invariant feature dimension. Here we show that when we use ReLU network as the model architecture, the linear probing can solve more diverse downstream tasks where the label can depend on the invariant feature dimensions arbitrarily.
The natural data distribution and the data angmentation are defined in the same way as Example The downstream task is a r-way classification problem such that the label function v(-): X + r satisfies y(x) = y(x') if F1:s x'ys. In other words, the label only depends on the first s dimensions of the data.
Example 2.
Definition 2 (ReLU networks). Let U RR and E Rt, use fu.s o(Wx+++ b) to denote the ReLU network with weight U and bias b, where a is the element-wise ReLU activation. We define the k-dimensional ReLU network function class as FReUU UvV U Bgxxd b R*).
We have the following theorem which shows the effectiveness of the ReLU network architecture. Theorem 4. In Example 2 suppose we set the output dimensionality k 2" and learn a ReLU network representation map f == arg min Jemax Lx(f) some X > 0. Then, we can find a linear
head W E Bexk such that
Ex-pasa eg =.
(17)
In contrast, suppose the function class is the set of universal function approximators Funi So long as the output dimensionality is no more than 2d-s, there exists solution f' arg arg Cx(f) such that for any linear head W E grak we have Egrepaca [ [ - c 2
5.3 LIPSCHITZ CONTINUOUS FUNCTIONS
In many real-world settings where neural network is trained with weight decay, the resulting model usually has a limited weight norm which encourages the network to have smaller Lipschitz constant. The implicit bias of the optimizers the learned function. Here we provide an example showing that restricting the model class to Lipschitz continuous functions allows use lower dimensional representations. In particular,
further encourage the smoothness of
8

---

Published as a conference paper at ICLR 2023
consider the following example where large number of clusters are located close to each other despite being disconnected in the positive-pair graph. Our result shows that contrastive learning with Lipschitz continuous functions would group those clusters together, allowing for lower representation dimensionality.
, Example 3. Let S1, S2, ... S. C TRd be m. manifolds in Rm each of which may contain lots of disconnected subsets. Suppose the radius of every manifold is no larger than p. that is for any i E [m] and two data z, x' E St, we have || - z'l12 S We also assume that different manifolds are separated by ", that is for any i.j [m]] such that + J. and x S, x' Sj. we have || - x'112 2 The data distribution Pdata is supported on S1 U USS U...UU Sm and satisfies Prempaas (x (x E 5²)
1/m for every [m] positive pair only contains data the same S.. The downstream task is r-way classification problem such that the label function y(-) X + [r] satisfies y(x) = y(x') if and x' belong to the same set S,.
We introduce the following family of Lipschitz continuous functions with parameter K:: Id + R is r-Lipschitz if (z) - faaa))l I k x x' ll for all x, TR. We define the k-Lipschtiz function class Fusp.x as the set of all k--ipschitz continuous functions
Definition 3 (K-- (<s-Lipschizz continuous functions). A function
functions in R -> IR...
We have the following theorem:
Theorem S. In Example suppose Ki 2 /2m/7. Let the oulput dimensionality k = and learn a Lipschhit continuous function arg min fx(f) for some X Then, we can find linear head W &Rexk such that
(18) On the other hand, suppose the positive-pair graph contains mn disconnected clusters, and the function class is the set of universal function approximators Funi- So long as the output dimensionality k < m, there exists solution f E arg arg men Lx(f) such that for any linear head W E Brxk, we have Ba-ppaa [ ('x)) Ev(x)) 2
Exsepasta ( ( 12-1 S 2rmx²p'
We note that a smaller к (hence smoother function class) decreases the RHS of equation leads to better downstream performance.
18 and
6 CONCLUSION
In this paper, provide theoretical analysis of contrastive learning that incoporates the inductive biases of the model class. We prove that contrastive learning with appropriate model architectures allows for lower representation dimensionality (hence better sample complexity), and instantiate this theory on several interesting examples. One open questions is to allow > m our theory, which believe requires additional assumptions the structure of the family of the models. We note that our work only concerns the inductive biases originating from the model architecture, whereas in practice the learned representations also depend the optimization method. Hence, another interesting future direction would be studying how the implicir bias introduced by the optimizer influences self-supervised learning.
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. International Conference on Machine Learning, 2019.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. In International Conference on Artificial Intelligence and Statistics, pp. 7187-7209. PMLR, 2022.
Randall Balestriero and Yann LeCun. Contrastive and non-contir con-contrastive self-supervised learning recover global and local spectral embedding methods. arXiv preprint arXiv: /508, 2022.

---

Published as a conference paper at ICLR 2023
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. arXiv preprint arXiv:2006.00882 33:9912-9922. 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, volume 119 of Proceedings of Machine Learning Research, pp. 1597-1607. PMLR, PMLR, 13- 18 Jul 2020a.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey Hinton. Big self- supervised models are strong semi sume-super learners. arXiv preprint arXiv:2006. 10029, 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. arXiv preprint arXiv:2011.10566, pp. 15750-15758, June 2020.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297, 2020c.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:2104.0885 2021.
Quentin Garrido, Yubei Chen, Adrien Bardes, Laurent Najman, and Yann Lecun. On the duality between contrastive and non-contrastive self-supervised learning. arXiv preprint NKKv:22006002574. 2022.
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-5011, 2021.
Jeff Z. HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. Advances in Neural Information Processing Systems, 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. arXiv prepring (506:11500.1499 2015.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pp. 9729-9738, June 2020.
Jason Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008.00 010644 2020.
Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and algorithm. Advances in neural information processing systems, 14:849-856, 2001.
Kento Nozawa and Issei Sato. Understanding negative samples in instance discriminative self- supervised representation learning. Advances in Neural Information Processing Systems, 34: 0784-5797, 2021.
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.
Nikunj Saunshi, Sadhika Malladi, and Sanjeev Arora. mathematical exploration of why language models help solve downstream tasks. arXiv preprint arXiv:2010.0366 03.444 2020.
10

---

Published as a conference paper at ICLR 2023
Nikunj Saunshi, Jordan Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham Kakade, and Akshay Krishnamurthy. Understanding contrastive learning requires incorporating inductive biases. arXiv preprint arXiv:2202.14037, 2022.
Yixuan Su, Fangyu Liu, Zaiqiao Meng, Tian Lan, Lei Shu, Ehsan Shareghi, and Nigel Collier. Tacl: Improving bert pre-training with token-aware contrastive learning, 2021.
Yuandong Tian. Deep contrastive learning is provably (almost) principal component analysis. arXiv preprint arXiv:2201. 12680, 2022.
Yuandong Tian, Xinlei Chen, and Surya Ganguli. Understanding self-supervised learning dynamics without contrastive pairs. In International Conference Machine Learning, pp. 10268 10268-10278. 10278. PMLR, 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. arXiv:2003. 02234, 2020.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pp. 1179-1206. PMLR, 2021.
Yifei Wang. Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is ladder: A new theoretical understanding of contrastive learning via augmentation overlap. In International Conference Learning Representations, 2021.
Colin Wei, Sang Michael Xie, and Tengyu Ma. Why do pretrained language models help in downstream tasks? an analysis of head and prompt tuning. Advances in Neural Information Processing Systems, 34:16158-1611 2021.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process self-supervised contrastive learning. In International Conference Machine Learning, pp. 11112-11122. PMLR, 2021.
Zixin Wen and Yuanzhi Li. The mechanism of prediction head in non-contrastive self-supervised learning. arXiv preprint arXiv:2205.062226, 2022.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2021.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: learning via redundancy reduction. In International Conference Machine Learning, pp. 12310- 12320. PMLR, 2021.
Self-supervised

---

Published as a conference paper at ICLR 2023
A
ADDITIONAL EXAMPLES
A.1 CONVOLUTIONAL NEURAL NETWORKS
Our last example shows that convolutional neural networks learn contrastive representation more efficiently than fully connected networks when the downstream task has certain rotational invariance structure. We consider the following data generative model where the data contains feature patch that determines the downstream label.
The natural data I Rdd is defined as follows: for some consecutive s dimensions It.t+--1 (the informative patch), have Itat+--1 E "} where 7 1. The other d dimensions of ã (spurious dimensions) are all in 1-1,1]. Given a natural data I, its augmentations generated by first sampling
Example 4.
Uni 0, 1]. then multiplying the spurious dimensions of I by т, while keeping the informative patch the same. The downstream task a r-way classification problem such that the label function v(-) X + [r] satisfies y(x) = y(z²) if the informative patches for x and x' are the same.
We consider the following convolutional neural network model with & channels.
Definition 4 (Convolutional neural networks). Let U = [u1, ....... uel" E R and b E R X + R to represent the following convolutional neural network: foom (z);
We use gromy
Ei= (uu Irt+s-1 + b:), where is ReLU octivation,function We define the convolutional neural network class Feomv (f0 U E -Rxxx e R.
We have the following theorem which shows that contrastive learning with convolutional neural networks requires lower representation dimensionality than using fully-connected ReLU networks Theorem 6. In Example 4 let output dimensionality network ff E arg min Fear (x( for some À > Then, we can find linear head W T such that Ex-paata [[] (x())
2 and learn a convolutional neural
On the other hand, suppose the function class is the set of ReLU networks FREEU so long as the output dimensionality is less than d x 2", there exists function f" E arg f Lx(f) such that for any linear head W E TRrkk we have Ear-paaa W f(())= Ev(x) 12 2 d=
B NUMERICAL SIMULATIONS
Recall that our assumptions intuitively state that the model architecture cannot break the data into too many well-separated clusters. In this section, propose method to empirically test how many clusters a model architecture can partition positive-pair graph the data distribution into. Given deep neural network and target number of cluster ideally aim find function f from the model class that maps each data point to a one-hot vector in dimension r which includes the cluster identity. That is, [(x) fer,..., } where e; is the i-th natural basis in Rr. With this constraint, we minimize the disagreement between the functions outputs of a positive-pair, that is,
= (z) - f(=+)(((+>>> )12], which compute the amount of inter-cluster edges. However, the one-hot vector requirement makes it challenging for optimization. Note that when the r clustering has the same probability mass 1/r, we have [[](())[(x)] constraint of f and arrive at a relaxation of the original optimization program.
I/r. We use this equation as the
b, = min E(g.+t)~paa
[1] - [[]f()))(++)]pp
s.t. [[(()))())")=T//>
(19)
Thus, we use b, as surrogate for how the architecture can partition the graph into clusters, and a smaller b, means that it's easier to partition. We empirically implement equation 19 by first minimizing the contrastive loss Lx (Jo) with representation dimension & and a heavily- tuned regularization strength X. Then, we whiten the obtained model [a(x) to have exactly the
covariance 1/r, that is, f(x) = Ex-pane (o(x)) f2)) is a valid solution for the
program in equation 19 We compute b, = [E [I] f(x) f(+t)) We also try various choices of and pick the smallest result as the final value of the estimated by.
Here we denote Td4 3t.
12

---

Published as a conference paper at ICLR 2023
We run this test with ResNet-18 model on CIFAR-10 10 and compute the b, for {10, 100, 500) list the results the table below. Here we note that b, increases from 0.127 to 0.315 as r increases from 10 to 500, suggesting that although the network partition the data relatively well into 10 clusters, it cannot partion the data into 500 well-separated clusters, which supports our theoretical assumptions. More details can be found in Appendix B.1
r
10
100
500
b,
0.127
0.204
0.315
B. ADDITION EXPERIMENTAL DETAILS
We train ResNet-18 model CIFAR-10 training set and test the b, the test set. We train with SGD using initial learning rate 0.01 and decays with cosine schedule. All experiments {10, 100,00000000 5003 and grid search using {0.1, 0.3, 1, 3, 10, 30, 100, 300, 1000), the result for each configurate is listed in the table below.
are run for 200 epochs. We test with
À
0.1
0.3
3
10
30
100
300
1000
10
0.445
0.127
0.134
0.144
0.151
0.155
0.215
0.343
0.901
100
0.887
0.660
0.408
0.245
0.204
0.220
0.254
0.424
1.579
r -= 500
1.031
0.981
0.710
0.554
0.427
0.372
0.315
0,481
1.231
C PROOFS FOR SECTION
Proof of Theorem
7 Let P; == Pr Pravpaan (x S.) be the probability of Sg. Let f be the function Viae Cid. From Assumption 5 and Assumption 4 have f F.
(x)
first show that f achieve small contrastive loss. For the regularizer term, we have
Ex-panta [M())
Σ
P: P.
Cid, Cid.
T = I.
(20)
xE(m)
Thus, have R(f*) 0. For the discrepancy term, let Pmin min P. be the probability mass of the smallest set, we have
E [f - fr |1
Pr (w.xt)-ppon
(ide + id,t)
a
(21)
Pmin
P
Combining equation 20 and equation 21 we have
Cx(F") = =E,,-- (1 + A(f -
(22)
Pmin
Since f arg min Lx(f) is the minimizer of contrastive loss within the function class, we have
Ex( < Cx(M*) <
(23)
Pmin
Define matrix
M Exppaata [()))(()
(24)
We have
Lx(l) a
||M - 11 <
(25)
XP
13

---

Published as a conference paper at ICLR 2023
Since À > i we know that M is full rank matrix, thus define function
f(x) = --
(26)
Let
Bxrupaua [+())[())]]
(27)
and
mz(x) = (x)
(28)
We know that
Ex-ppata
[x)()))(xx]]
B Bexopaaca [(()}{())]]] - QF Quzeppaica [+)))
= 0. (29)
Using Assumption
3 we have:
[ PrPp [15(()) - x ||]
(Pr -a) a) - -(e, ( (12
kE|m]
28
Σ
(P. - at) EE wwatan [1mT((t) x (2
kE|m)
-33-
(P, a)
Eaoeaatts [1T,(()]12
iE(m)
22 (1
E Eara
[|T5(2))11]
(30)
Pmin
On the other hand, we have
E (egptt
[|T - T (z
[[(Co) - s(a-t)1
E ((xxtt)pppr
[1((00) f(x )(xt)|10 1112
IM
EE (G, pappon
spec
1
(31)
XP
Pani
Combining equation 30 and equation
we have
Expepaaaa
S
(32)
APmin
233 Piin a)
By Lemma] we know that there exists a matrix U E Rmxm such that
[|1())-UMM |
5(1+ XP
a
Exppasta
$ 1+
(33)
2,3Ppin a)
S 3(Pmin min a)
(34)
Thus, if we define matrix W = diagl VP, VP,.... PPm then we have
|| Ieua
wf(t) ?
||)(()) UM 1/2
Exrpassa
P PmaxEEepia
(35)
2
< Pmax 3(P min -a)
(36)
which finishes the proof.
14

---

Published as a conference paper at ICLR 2023
Lemma 1. Suppose X - Rm and g X mh two functions defined & such that
Exz-paa [x(=)[())] ] Pareaa [
(37)
Define the projection of f onto g orthogonal subspace as:
F f = f(x) - Ex' opanon [f(x)g(x)] g(x). (g(x).
(38)
Then, there exists matrix U R.xx such that
Egcepaas [10(=)) ((x)) = Exwpeata [
(39)
Proof of Lemmal
Let matrix
U = Ex paaasa [
(40)
We have
E papaa
[l0(()) U f1))
(41)
E Eg-paat
[10()))1
2E 2Ezrpaaca [f(()] + E Eu-panu [f(x) U Uf())
(42)
=m - 2 11 + 1
(43)
=m - -
(44)
On the other hand, we have
Eg-paaes
(x)((>))1
(45)
[I((x)) - T ((=))|2]
Ez-paata
(46)
= =Bzupases
[ 2E
[f(x) (T [[xx]] + Exupasta [0(x) UU g(x)]
(47)
-m
||
(48)
Thus, we have
[ = Ernpasta [[TT(T)]12]
Exropatta
(49)
which finishes the proof.
D PROOFS FOR SECTION 4
Proof of Proposition]]
7 Define function
g(x) = V Pdata (x))
(50)
Define the symmetric Laplacian operator
Ppos P2o (I,
(())(z) = õ(x) -
g(x') 'd''.
(51)
Pdaca x (2')
can be verified that
J (()) = 0.
(52)
Notice that the operator is PSD, we have that
f (((0)=))²² =
(53)
which is equivalent to hence finishes the proof.
E Exnppats
[[L())<)))] = 0,
(54)
n
15

---

Published as a conference paper at ICLR 2023
Proof of Theorem
Notice that L (feie) S Ø. know that Lx(f)
S o,
[ - - X
(55)
In Assumption 6 set f f and sum over i = 1.2. ,k, we have that for some matrix W,
[aa((t) f(x) -f(0))(())))))) (10)
E Em-paatt
S kc.
(56)
Let matrix Q = Euwopan [f())((x) ]. we have that
110 - |c00|11] -
2Φ
[|(())) S
2Φ k
Egzepacco
B Bempaao
1 V x
(57)
Thus,
E Exrppaata
|| -1-11
27
46 s 2ke +
22ke
_ k
( 1+
[1 v2)
(58)
X
Define matrix
M Eep-a (12xx))1133(())
1/2
(59)
Using Lemma I and equation 58 we have
Ego-paato [[ - MQ MQ- 1/2 ((0) [13] S 2ke +
400 k
Φ V )
86b
1
s 2kr +
x k
(60)
x
Thus, using Assumption
have
[WMMQ-1/ 1/2 f(x) Ev(ir) !-]
Bgueasts
(61)
[|IW Seig(())) evcooll2] + 2E 22grpann
\-22Q-1/2((x) - M fa)(
<22grraan
(62)
166 B²k.
22 + +B=kkt
(63)
A
E PROOFS FOR SECTION
E. PROOF FOR EXAMPLE
Proof of Theorem 3 Define
= [E1, e2, ee,] E Rexd, We can verify that
E ( Pmppon
[116(()) - f )|2] =0
(64)
and
Egpopara [x(( =I.
(65)
Thus, view fo as the feig in Section 4
Let U e kxd and i [k] such that
E E(r,at) ymppo (x), (x (x)))
(66)
Notice that and + only differs the 1-th to d-th dimensions, know that U, is on the s + 1-th to d-th dimensions. Thus, we have that U, is the span of e₁, 62, .. C., and as a result Assumption 6 holds with = 0.
16

---

Published as a conference paper at ICLR 2023
Since the downstream task's label is equal to x; for i [s], we set W e. and we would have Ex=pases [(W* fo (x) )()))²] O. Hence Assumption holds with a = 0 and B = 1.
(67)
Applying Theorem finishes the proof for the linear function class case.
For the case of universal function approximators, without loss of generality we assume the downstream task's ' label only depends on the first dimension of æ, i... y(x) sgn(x1). When k S 2d-1, 1 we can construct a function f X' + R such that for every diemnsion j E [k], we have f()); = vk when 22.4 viewed as a binary number equals to j. otherwise f(x); = 0. It can be verified that (x( = O hence f a minimizer of the contrastive loss. However, f((x) agnostic to the first dimension of æ, hence the downstream error is at least 1.
E.2 PROOF FOR EXAMPLE
Proof of Theorem 4
For any vector (-1,1)", we define function bin(h) E {0, 1.... , - 1}
be the function that maps h to the corresponding number when viewing }(hh + 1) as binary. Since bin(-) is a one-to-one mapping, we can define U E {k x d} such that the 2-th row of U satisfies: the first s dimensions equal to vk bin (i 1), and the rest d d dimensions are O. Let bias vector b E IR* such that every dimension is -Vk- (r - 1). We have fu.o(z) = Vk @hin(ar1.)+1 E R
Since Eawpgaan (us))))
and pppp.r (x) Su, )12) O, we can view fü,b as the feig in Section 4 Assumption naturally hold wihth B = 1.
For Assumption (xr
consider a function fors E FReLL and index i E [A] such that
E(a,
= Suppose there exist + x' and their augmentations æ, x' such that J (x), : > [vrr((")s, Then, there must be (Ui),- * and
oUT x) > 0. This suggests that there must exist another ā which is also an augmentation of but oU x) + (U, Z). Hence, we have
P(xpa->~ppon
O,
(68)
leading to contradiction. Hence, we know that fur (z): for, so (for can only be function of 11s. Therefore, there exists a vector w E R such that fur, (x); w fv,((1, which means Assumption 6 holds with
Applying Theorem finishes the proof for equation 17
The result about universal function approximators follows the same proof as for Theorem exeept for constructing the function using the last (d-s) dimensions rather than the last (d-1) dimensions.
E.3 PROOF FOR EXAMPLE
Proof of Theorem 5 Let id,, be the index such that E Sit, and define function fei (x) /m-eia, It can be verified that Seig satisfies equation 9 and equation 10 For s E Frip.x and E [mm]. define g(æ) = f(z); Suppose Ex-puns [9 = 1, we can chooose m data T2, I' such that
1 Ia E S; and 1 Etelm) o(x,)² < Define vector u E R" such that بi = vm g(xx). We have
Egepena [(w fag(2) g(x))²]
Σ Eg [(g(x;) 9(x))}
(69)
m
<c|m]
12 = 12 p2
(70)
sc(m]
Thus, feig satisfies Assumption with c c= n2
Since the data in the same S; have the same downstream label, we know that Assumption holds with = v and a = O. Thus, applying Theorem 2 finishes the proof for the upper bound.
For the lower bound, Let set Š be the set among those mn clusters that has the largest size. When < m, we can construct a function that maps all data in S to 0, hence the final error would be at least 1. m
17

---

Published as a conference paper at ICLR 2023
E.4 PROOF FOR EXAMPLE
Proof of T For any vector E {-1,1}" we define function bin(h) E 10,1, 10.1,... .... ,
be the function that maps h the corresponding number when viewing 7 [h 1) binary. Since bin(-) is a one-to-one mapping, we can define E [k x 8) such that the i-th row of U equal /E.
7 bin -i 1). Let bias vector b R be such that every dimension is
y-1 (-s (r - () - 1)). We have fü. (x) Vk Cbin(Fre11 1)+1 E R where is the starting position of the informative patch in It can be verified that E Exoepese [fom (f) (x) (=)
I and (x )mepos foon (x) JUB (x 113 O. Also, Assumption holds with B when viewing
fai JU
Suppose some function feb and dimension i [k]] satisfies
[ poom (z)) (x)
fcony (a+ (a+)))
(a >~Ppoon
(71)
define ž the vector that replaces spurious dimensions of x with O. Notice that T is in the support of w's augmentations, and the model is continuous, we know feeny
Then, we know that for any Pdata: suppose
0.6 (Ir); foomy (+); Further notice that for any data xr xf with the same
informative patch (location might be different) and corresponding i. x', there must be f.. (Ø); reonv (ā'); due to the structure of the convolutional neural networks. Thus, We have foomy (I:); 0.6
reony (x'); This suggests that the funciton f (-); is in the span of Jug hence finishes the proof 0.6
for the upper bound.
For the lower bound, we note that due to the lack of invariance to informative patch location, we can construct network with 2 di-dinnnsional output that satisfies equation and equation TO When then output dimension is less than d 2", there would exist a minimizer of the contrastive loss that merges two of these 2 clusters. these two clusters have different downstream label, there would be at least 7 loss incurred due to the data being mapped to the same feature, hence finishes the proof for the lower bound.
18


Reviews:
[{"review_id": "gRZSjPuKom", "reviewer": "Reviewer_1bvx", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Prior work by Saunshi et al. 2022 had highlighted the insufficiency of previous theoretical analyses that are function-class agnostic to completely explain the success of self-supervised learning. This paper provides theoretical guarantees for self-supervised learning that do incorporate the function class building on the framework of HaoChen et al 2021. \n\nIn particular, the paper presents a notion of *minimal implementable clusters* for a function class $\\mathcal{F}$, that is, the size of the smallest disjoint partition of the input space such that the positive pairs lie with high probability in the same cluster and the clusters within each partition are non-sparse under the geometry enforced by the underlying function class $\\mathcal{F}$. At a high level, this notion intends to captures the ability of the function class $\\mathcal{F}$ to break the underlying positive-pair graph (vertices = augmentations of images, edges = if two augmentations can be generated from the same image) into too many clusters. The main theorem then says that the embedding dimension needed to guarantee good downstream performance is dependent on the minimal implementable clusters which may be exponentially smaller than the total number of clusters independent of the the function class.", "summary_of_the_review": "Overall, I think the paper makes progress towards understanding the role of function class for contrastive learning and formalizing the observations in Saunshi et al. 2022. Given that the prior work did already propose a setting where the role of function class was highlighted, this paper’s primary contribution is a more refined theoretical treatment of this observation, and not the observation itself. This diminishes the contribution of the work slightly, however I still think it would be interesting to the ICLR audience. My major concern is writing and the experimental section, which is reflected in my comments above. Therefore, currently I think the paper is not ready for acceptance. I will be happy to increase my score if these are improved.\n\nPost rebuttal: 5-> 6", "strength_and_weaknesses": "**Strengths**:\n- The main result in the paper improves the current theoretical understanding of self-supervised learning and formalizes the example presented in Saunshi et al. (2020).\n- The eigenfunction perspective is a nice generalization and probably has connections directly to spectral clustering/kernel PCA.\n- The authors do a good job of including several examples to instantiate the theorem.\n\n**Weaknesses**:\n- The main weakness of the paper is writing. The paper is written for a narrow set of the audience who is very familiar with the existing works of HaoChen et al. 2021, 2022 and Saunshi et al. 2022. Very little effort has been put to make the core ideas accessible to a broader audience. Furthermore, figure 1 is very hard to understand given that it has no “orange” points. Considering this is the main figure used to motivate the underlying study, this already makes it very hard to follow the paper.\n- The experimental evaluation is not very convincing. Assumption 2 depends on all $f \\in \\mathcal{F}$ but the evaluation is based on a specific value of the learned $f$ from the contrastive solution (which encodes the inductive biases of the algorithm as well). It is hard to understand what these numbers mean and whether the trend is enough.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "d8SJMViqX7", "reviewer": "Reviewer_HMnY", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 paper studies inductive bias from the model class in contrastive learning. The paper proposes some mild and practical assumptions and studies the optimal solution of the spectral contrastive loss from the eigenfunction perspective. The paper argues that when the model has limited capacity, contrastive representations would recover certain special clustering structures (depending on model architecture) but ignore other clustering structures in the data distribution. Moreover, the paper also studies different model classes including linear functions, ReLU networks, Lipschitz continuous functions, and Convolutional neural networks. ", "summary_of_the_review": "Although there are some questions I mentioned in the Weakness part that blocked me, the paper has its novelty and I tend to accept it. ", "strength_and_weaknesses": "Strength:\n1. As far as I know, this is the first work to study inductive bias originating from the model class in contrastive learning. The paper is based on some reasonable assumptions and gets a non-trivial conclusion. In my opinion, Assumption 2 is the most critical one. The function class cannot be too powerful so that we can guarantee the generalization. The authors also introduce novel tools, eigenfunction methods, in analyzing contrastive learning. \n2. The paper has a clear motivation and a good structure. \n\nWeakness and Questions:\n1.  I am not familiar with Eignfunction methods. I have some questions for Section 4. What is the relationship between $k$ orthogonal eigenfunctions and equations (9) and (10)? Are equations (9) and (10) additional assumptions here or can they be induced from $k$ orthogonal eigenfunctions? What is the connection between Assumption 6 and Assumption 2 and 3? I cannot get full insights into how is Therom 2 generalized from Theorem 1. \n2. One concern I have is that in practice the model has more than millions of parameters, e.g. vision transformer. Then, how to guarantee assumption 2 in a real empirical scenario. Note that Assumption 2 considers the whole function space. If assumption 2 is not guaranteed, how to explain the success in MoCo v3 [3]? \n3. There are some subtle weaknesses in the problem settings. The paper studies generalized spectral contrastive loss rather than the InfoNCE family loss. The authors also did not consider the sample complexity in the pre-training like [1,2]. \n4. The experiments part is weak.  It is acceptable considering it is a theoretical paper. The $b_r$ is not a clear metric for reader to understand the partition effect, e.g. for $r=500$, how bad is $b_r=0.315$. More explanation is needed here.\n\nTypos:\n1. In Figure 2, there are no orange points. \n2. In page 16, “wiht” -> “with”.\n\n[1] Arora, Sanjeev, et al. \"A theoretical analysis of contrastive unsupervised representation learning.\" arXiv preprint arXiv:1902.09229 (2019).\n\n[2] HaoChen, Jeff Z., et al. \"Provable guarantees for self-supervised deep learning with spectral contrastive loss.\" Advances in Neural Information Processing Systems 34 (2021): 5000-5011. \n\n[3] Chen, Xinlei, Saining Xie, and Kaiming He. \"An empirical study of training self-supervised vision transformers.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2021.\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": "Not applicable"}, "extra_text": {}}, {"review_id": "EXYPy9BoUA", "reviewer": "Reviewer_XWTN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a theoretical analysis of contrastive learning in the setting where the hypothesis class has significantly smaller dimension than the data distribution (as measured by the number of clusters). They instantiate their framework on a few example settings and show that their results provide theoretical guarantees where previous approaches do not.", "summary_of_the_review": "This paper presents a theoretical analysis of inductive biases in contrastive learning. Their main result is that when the function class being learned over is restricted, one needs a representation size that is far smaller than the number of clusters in the data distribution. The paper is clearly written, the results seem correct, and also address issues raised by prior work. ", "strength_and_weaknesses": "Strengths:\n\n- The paper is well-written and the authors provide intuition around each provided result, and motivate the problem well.\n- The authors present the example from Saunshi et al (2021) and show how their results shed light on the actual behavior of contrastive learning in that setting.\n\nWeaknesses:\n\n- The experimental section is a bit confusing and I don't quite see the connection between the theory and the experimental results. In particular, the experiment shows that as the number of clusters gets higher, the loss of a contrastive classifier also gets higher. My issue with this experiment is that I do not see what the alternative is to the results shown in the table in page 9---clearly as r -> infinity the loss must increase, and for r = 1 the objective is trivial, so I'm not sure what I should take away from the loss increasing (the numbers themselves are not interpretable to me).\n- A much more compelling experiment would be to show that the bounds proved in the previous sections are actually predictive of model behavior in some non-obvious way (e.g., by implicitly varying P_min and P_max, or by varying alpha and beta) and showing that Theorem 1 is predictive in this setting (at least in terms of trend)", "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": "6Ulle-4il4l", "reviewer": "Reviewer_tjye", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies contrastive learning from a theoretical perspective. Previous works on this topic showed the benefits of contrastive learning, assuming the pretraining loss is minimized over all sets of functions with no specific form. In this work, it is assumed that the pretraining loss is minimized by certain classes of functions, such as linear predictors and neural networks. Under different assumptions on the data and architecture, it is shown that contrastive learning can learn useful representations for downstream tasks. The results show that this can be achieved with representations of lower dimensionality compared to previous results.", "summary_of_the_review": "This paper shows novel theoretical results on self-supervised learning with the contrastive loss. In several parts, the presentation of the mathematical results and writing are not clear.", "strength_and_weaknesses": "Strengths\n1. Solid theoretical results.\n\n2. Novel results for self-supervised learning with contrastive loss.\n\nWeaknesses\n\nThe main weakness is that the presentation of the results and mathematical details are not very clear.\n\nHere are the details:\n\n1. The relevance of Theorem 1 in this paper is not clear. It is presented as the main result but is not used in the paper. Theorem 2 is used instead. It is claimed that Theorem 2 generalizes Theorem 1. However, because of the various assumptions, it is not shown if this generalization is strict, or there are cases where Theorem 1 guarantees better results. Generally, the connection between the assumptions in Section 3 and Section 4 are not clear. \n2. The details of the proof of Theorem 2 are not clear:\n(a) Where is Eq. (57) used in the proof? Also, $\\tilde{W}$ appears in the proof (Eq. 57), but later disappears. Where does it appear in the calculations?\n(b) How is Eq. (59) derived from Lemma 1 and Eq. (55)? The details are not shown.\n3. In Example 3, what does “contains lots of disconnected subsets” mean formally?\n4. In Theorem 1, does the result hold for k>m? In Theorem 3, can we set k > s?\n5. The experiments are not very convincing. The optimization method that first optimizes the contrastive loss and then whitens the result may not minimize Eq. (18).\n6. Are the results in Section 5 specific to the regularization used? For example, if we slightly change the distribution in Example 1 to a general product distribution, do the results still hold?\n7. The orange points in Figure 1 are missing.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}]

Author rebuttal:

Decision: Accept: poster