Towards the Generalization of Contrastive Self-Supervised Learning
Authors: Weiran Huang
Mingyang Yi
Xuyang Zhao
Zihao Jiang
Venue: ICLR 2023 poster (2023)
Keywords: deep learning theory
contrastive learning
generalization error

Abstract: Recently, self-supervised learning has attracted great attention, since it only requires unlabeled data for model training. Contrastive learning is one popular method for self-supervised learning and has achieved promising empirical performance. However, the theoretical understanding of its generalization ability is still limited. To this end, we define a kind of $(\sigma,\delta)$-measure to mathematically quantify the data augmentation, and then provide an upper bound of the downstream classification error rate based on the measure. It reveals that the generalization ability of contrastive self-supervised learning is related to three key factors: alignment of positive samples, divergence of class centers, and concentration of augmented data. The first two factors are properties of learned representations, while the third one is determined by pre-defined data augmentation. We further investigate two canonical contrastive losses, InfoNCE and cross-correlation, to show how they provably achieve the first two factors. Moreover, we conduct experiments to study the third factor, and observe a strong correlation between downstream performance and the concentration of augmented data.


Published as a conference paper at ICLR 2023
TOWARDS THE GENERALIZATION OF CONTRASTIVE SELF-SUPERVISED LEARNING
Weiran Huang 1
Mingyang 2
Xuyang Zhao Zihao Jiang'
1 Qing Yuan Research Institute, Shanghai Jiao Tong University
Huawei Noah's Ark Lab
3 School of Mathematical Sciences, Peking University
ABSTRACT
Recently, self-supprvised learning has attracted great attention, since it only requires unlabeled data for model training. Contrastive learning is one popular method for self-supervised learning and has achieved promising empirical performance. However, the theoretical understanding of its generalization ability is still limited. To this end, define kind of (ar, me-muuur to mathematically quantify the data augmentation, and then provide an upper bound of the downstream classifi- cation error rate based the measure. It reveals that the generalization ability of contrastive self-supervised learning is related to three key factors: alignment of positive samples, divergence of class centers, and concentration of augmented data. The first two factors are properties of learned representations, while the third one is determined by pre-defined data augmentation. We further investigate two canonical contrastive losses, InfoNCE and cross-correlation, to show how they provably achieve the first two factors. Moreover, we conduct experiments to study the third factor, and observe a strong correlation between downstream performance and the concentration of augmented data.
INTRODUCTION
Contrastive Self-Supervised Learning (SSL) has attracted great attention for its fantastic data effi- ciency and generalization ability computer vision (He al., 2020; Chen al., 2020a;b; Grill et al., 2020; Chen & He, 1021; Zbontar et al., 2021) and natural language processing (Fang et al., 2020; Wu et al., 2020; Giorgi al., 2020; Gao et al., 2021: Yan et al., 2021). learns the representation through a large number of unlabeled data and manually designed supervision signals (i.e., regarding the augmented views of a data sample as positive samples). The model is updated by encouraging the features of positive samples close to each other. To overcome the feature collapse issue, various losses (e.g., InfoNCE (Chen et al., 2020a; He et al., 2020) and cross-corellatin (Zbontar et al., 2021)) and training strategies (e.g., stop gradient (Grill et al., 2020; Chen & He, 2021)) are proposed.
In spite of the empirical success of contrastive SSL terms of their generalization ability on downstream tasks, the theoretical understanding is still limited. Arora al. (2019) propose theoretical framework to show the provable downstream performance of contrastive SSL based on the InfoNCE loss. However, their results rely the assumption that positive samples are drawn from the same latent class, instead of the augmented views of a data point as in practice. Wang & Isola (2020) propose alignment and uniformity explain the downstream performance, but they empirical indicators and lack of theoretical generalization guarantees. Both of the above works avoid characterizing the important role of data augmentation, which is the key to the success of contrastive SSL, since the only human knowledge is injected via data augmentation. Recently, HaoChen et al. (2021) propose model the augmented data as a graph and study contrastive SSL from a matrix decomposition perspective, but it is only applicable to their own spectral contrastive loss.
Besides the limitations of existing contrastive SSL theories, there are also some interesting empirical observations that have not been unraveled theoretically yet. For example, why does the richer data
"Equal contribution (a-8 ordering). Correspondence Weiran Huang (weiran.huang Quttunngoooloooccommmmo

---

Published as a conference paper at ICLR 2023
Automablee
Oeer
frg
Astmnoiis
Attoretle
(a) Initial
(b) Only color distortion
(c) Multiple transformations
Figure 1: SimCLR's embedding space with different richnesses of data augmentations on CIFAR-IO.
augmentation lead the more clustered structure in the embedding space (Figure 1) well the better downstream performance (also observed by Chen et al. (2020a))? Why is aligning positive samples (augmented from the "same data point") able to gather the samples from the "same latent class" into cluster (Figure ic)? More interestingly, decorrelating components of representation like Barlow Twins (Zbontar et al., 2021) does not directly optimize the geometry of embedding space, but it still results in the clustered structure. Why is this?
In this paper, we focus on exploring the generalization ability of contrastive SSL provably, which can explain the above in- teresting observations. We start with understanding the role of data augmentation in contrastive SSL. Intuitively, samples from the same latent class are likely to have similar augmented views, which are mapped to the close locations in the embed- ding space. Since the augmented views of each sample are encouraged to be clustered in the embedding space by trastive learning, different samples from the same latent class tend be pulled closer. As an example, let's consider two images of dogs with different backgrounds (Figure 2). If we augment them with transformation "crop", we may get two similar views (dog heads), whose representations (gray points in the embedding space) are close. As the augmented views of each dog image are enforced to be close in the embedding space due to the objective of contrastive learning, the representations of two dog images (green and blue points) will be pulled closer their augmented views (gray points). In this way, aligning positive samples is able to gather samples from the same class, and thus results in the clustered embedding space. Following the above intuition, define the augmented distance between two samples the minimum distance between their augmented views, and further introduce the (a, Jaaaumeentnt to measure the concentration of augmented data, i.e., for each latent class, the proportion of samples located in ball with diameter ò (w.r.t. the augmented distance) is larger than a.
Augmentation
Augmentation
Close to Each Other
Embadding
Figure 2: Mechanism of Clustering
With the mathematical description of data augmentation settled, we then prove an upper bound of downstream classification eтror rate in Section 3. It reveals that the generalization of contrastive SSL related three key factors. The first one alignment of positive samples, which common objective that contrastive learning algorithms aim to optimize. The second one is divergence of class centers, which prevents the collapse of representation. The third factor is concentration of augmented data, i.e., sharper concentration of augmented data indicates better generalization error bound. We remark that the first two factors are properties of representations that can be optimized during the learning process. However, the third factor is determined by pre-defined data augmentation and is independent of the learning process. Thus, data augmentation plays a crucial role in contrastive SSL.
We then study the above three factors in more depth. In Section 4, rigorously prove that not only the InfoNCE loss but also the cross-correlation loss (which does not directly optimize the geometry of embedding space) can satisfy the first two factors. For the third factor, conduct various experiments on the real-world datasets and observe that the downstream performance of contrastive SSL is highly correlated the concentration of augmented data in Section 5.
In summary, our contributions include: 1) proposing novel (ar 8) meesure to quantify data aug- mentation; 2) presenting theoretical framework for contrastive SSL that highlights alignment,
2

---

Published as a conference paper at ICLR 2023
divergence, and concentration key factors for generalization ability; 3) provably verifying that not only the InfoNCE loss but also the cross-correlation loss satisfy alignment and divergence; 4) showing strong correlation between downstream performance and concentration of augmented data.
RELATED WORK
Algorithms of Contrastive SSL. Early works such MoCo (He al., 2020) and SimCLR (Chen et al., 2020a), use the InfoNCE loss to pull the positive samples close while enforcing them away from the negative samples in the embedding space. These methods require large batch sizes (Chen et al., 2020a), memory banks (He et al., 2020), or carefully designed negative sampling strategies (Hu et al., 2021). To obviate these, some recent works get rid of negative samples and prevent representation collapse by cros-correlation loss (Zbontar et al., 2021; Bardes et al., 2021) or training strategies (Grill et al., 2020; Chen He, 2021). In this paper, we mainly study the effectiveness of the InfoNCE loss and the cross-correlation loss, and do not enter the discussion of training strategies.
Theoretical Understandings of Contrastive SSL. Most theoretical analysis based on the InfoNCE loss, and lack of understanding of recently proposed cross-correlation loss (Zbontar et al., 2021). Early works understand the InfoNCE loss based on maximizing the mutual information (MI) between positive samples (Oord et al., 2018; Bachman et al., 2019; Hjelm et al., 2018; Tian et al., 2019; 2020; Tschannen et al., 2019). However, a rigorous relationship between mutual information and downstream performance has not been established. Besides, Arora et al. (2019) directly analyze the generalization of InfoNCE loss based on the assumption that positive samples are drawn from the same latent classes, which is different from practical algorithms. Ash al. (2021) study the role of negative samples and show an interesting collision-coverage trade-off theoretically. HaoChen al. (2021) study contrastive SSL from a matrix decomposition perspective, but is only applicable to their spectral contrastive loss. The behavior of InfoNCE is also studied from the perspective of alignment and uniformity (Wang & Isola, 2020), sparse coding model (Wen & Li, 2021), the expansion assumption (Wei et al., 2020), stochastic neighbor embedding (Hu et al., 2022), and augmentation robustness (Zhao et al., 2023).
PROBLEM FORMULATION
Given a number unlabeled training data i.i.d. drawn from an unknown distribution, each sample augmentation set A, the set of potential positive samples generated from data point æ is denoted as A(x). We assume that A(x) for any æ, and samples from different latent classes never transform into the same augmented sample, i.e., A(Ca) n A(C²) = 2 for any k + &. Notation l2 form Frobenius norm for vectors and matrices, respectively.
belongs to of K latent classes C1, C2 ......, Ck. Based
in this paper stands for
Contrastive SSL aims to learn an encoder f. such that positive samples are closely aligned. order make the samples from different latent classes far away from each other, some methods such as (Chen et al., 2020a; He et al., 2020) use the InfoNCE loss' to push away negative pairs, formulated as
(m,)) TT T(m2))
LInONNE
E. w.w0 (1.)) "'((m')
log (.((=))f(ax) ef())) ((
where æ, æ'' are random data points. Some other methods such Barlow Twins (Zbontar et al., 2021) use the cross-correlatio loss to decorrelate the components of representation, formulated as
LCruss. Cor Σ F.) 2
where F.j = Ex Em, (f normalized as E.r Ex'EA(w) (x') for each dimension i.
d is the dimension of encoder f, and encoder f is
The standard evaluation contrastive SSI. is to train linear classifier over the learned representation using labeled data and regard its performance as the indicator. To simplify the analysis, instead
For simplicity in analysis, we consider the InfoNCE loss with only negative sample.
3

---

Published as a conference paper at ICLR 2023
consider non-parametric classifier nearest neighbor (NN) classifier:
Gy arg min [l [4sll,
kE[K]
where M3g := ExEC, E()) [())) [[x')
]] the center of class Ck. In fact, the NN classifier is a special
case of linear classifier, since can be reformulated as (x)) arg [a]] (W ((x)) + b)k.
where the k-th row of W is μe and by = - _ | (See Appendix E). Therefore, the directly learned linear classifier used in practice should perform better than the NN classifier. In this paper, we use
the classification error rate to quantify the performance of Gy, formulated as
Err(G,) Σ p(G + k, Va Ck]-
Our goal is to study why contrastive SSL is able achieve a small Err(Gy).
3 GENERALIZATION GUARANTEE OF CONTRASTIVE SSL
Based on the NN classifier, if the samples are well clustered by latent classes in the embedding space, the error rate (rr(Gy) should be small. Thus, one expects to have a small intra-class distance Emy [ I (a=2))' || for an encoder / learned by contrastive learning. However, contrastive algorithms can only control the alignment of positive samples Ez, E f f To
bridge the gap between them, we need to investigate the role of data augmentation.
Motivated by Figure 2 introduced in Section 1, for given augmentation set A, we define the augmented distance between two samples as the minimum distance between their augmented views:
min d dz x2) = ar (.
||ar|
2²/1-
(1)
For the dog images in Figure 2 as an example, even though their pixel-level differences are significant, their semantic meanings are similar. Meanwhile, they also have small augmented distance. Thus, the proposed augmented distance can partially capture the semantic distance. Based on the augmented distance, we now introduce the (a, 6)agmmeentaii to measure the concentration of augmented data.
Definition ((a,8)- 5)-Augmmentatinn) The augmentation set A called (a, a)aaummentation, for each class CR. there exists a subset C% C Cs (called main part of Ck), such that both P|æ E CH) 2 a Pla E Ck] where a E (0, 1] and sup2) d (x1, xx2) S 8 hold.
In other words, the main-part samples locate in a ball with diameter å (w.r.t. the augmented distance) and its proportion is larger than a. Larger and smaller 5 indicate the sharper concentration of augmented data. For any A' 2 with richer augmentations, one can verify that d x22) < d 222) for any œτ, 22. Therefore, richer data augmentations lead to sharper concentration as gets smaller. With Definition 1, our analysis will focus on the samples in the main parts with good alignment, i.e., (CP U...
C& n.S. where S. == fxr E _K_ Ck: Vzz, Z2 E A(x),, (xx (x22)] S {] is the set of samples with E-close representations among augmented data. Furthermore, we let R₂ ;= P [..]. which is provably small with good alignment (see Theorem 2).
Lemma 3.1. For a (a, Daa-mmentattoon with main part C2 of each class Ck. if all samples belonging to (CT U... ....1. LJ C+ n can be correctly classified by classifier G. then its classification error rate GG) is upper bounded by (1 σ) + Rg-
The proof is deferred to the appendix. The above lemma presents simple sufficient condition to guarantee the generalization ability on downstream tasks. Based on it, we need to further explore when samples in (CT U ...UU CR) SS can be all correctly classified by the NN classifier.
We assume that encoder f is normalized by |[ = r, and it is L-Lipschitz continuity, i.e., for any 21, 22, [lf())) f(x2) < L ||x æzll. We let pk == Pfæ E Ck] for any k [K]. Lemma 3.2. Given a (a, auggeenttiioo used in contrastive SSL, for any E E [K], if ue pk < 22 (1 (1-pe(a, 6) /2pe(a, 5, 2x) holds for all + e, then every sample x E C n Se can
he correctly classified by the NN classifier G3, where pe(a, 6,6) = 2(1 - o) + p
Bg + a
L8 + 2)
and 4 = minke[K] ||m11//r22
4

---

Published as a conference paper at ICLR 2023
With Lemma 3.1 and 3.2, we directly obtain the generalization guarantee of contrastive SSL:
Theorem 1. Given a ( -augmentationn used contrastive SSL, if
A
x² Prnaz (0, (0,,,)) 2p (o, (0, 6,5) Pe j4k
(2)
2
holds for any pair of (e,k) with 8 + k, then the downstream error rate of NN classifier G3 where Pinaz (a, 5, = 2(1 o) +
Frr(G,) S -0) +)+ Re:
n2 miny
+ Fb 25 and A - mink I1 122/r2
The proof is deferred to the appendix. To better understand the above theorem, let first consider a simple case that any two samples from the latent same class at least own a same augmented view (a 1, 8 0), and the positive samples are perfectly aligned after contrastive learning (E = 0, Rg = 0). In this case, the samples from the same latent class are embedded to single point (pr)
[eel Helll < 1 is enough to distinguish them by the NN classifier. fact, one can quickly verify that Pmaa (7, 6,6) = A = holds in the above case. According to Theorem 1, if pe Mk/r22 < 1 Pinar (a,ar(a,, (a,8, 6) 22pmaz (a, d, An 1, then yrr(Gy) 0, i... NN classifier can correctly recognize every sample when pe 24x / < 1. Thus, the condition suggested by Theorem is exactly the same as the intuition.
on the hypersphere, and thus arbitrarily small positive angle
Theorem implies three key factors to the success of contrastive SSL. The first one is alignment of positive samples, which a common objective that contrastive algorithms aim to optimize. Better alignment enables smaller Rg, which directly decreases the generalization error bound (3). The second factor is divergence of class centers, i.e., the distance between class centers should be large enough (small 24 pg). The divergence condition (2) is related the alignment (R₂) and data augmentation (a, 5). Better alignment and sharper concentration indicate smaller Pmaz (or, 5, E), and hence looser divergence condition. The third factor is concentration of augmented data. When 5 is given, sharper concentration implies larger which directly affects the generalization error bound (3). For example, richer data augmentations lead to sharper concentration (see the paragraph below Definition 1), and hence better generalization error bound. Only the first two factors can be optimized during the learning process, and we will provably show how it can be achieved via two concrete examples in Section 4. In contrast, the third factor is priorly decided by the pre-defined data augmentation and is independent of the learning process. We will empirically study how the concentration of augmented data affects the downstream performance in Section 5. In summary, Theorem provides a framework for different algorithms to analyze their generalization abilities.
Compared with the alignment and uniformity proposed by Wang & Isola (2020), both of the works have the same meaning of "alignment" since it is the objective that contrastive algorithms aim to optimize, but our "divergence" fundamentally different from their "uniformity". Uniformity requires "all data" uniformly distributed on the embedding hypersphere, while our divergence characterizes the cosine distance between "class centers". We do not require the divergence to be as large as better, instead, the divergence condition can be loosened by better alignment and concentration properties. As an example. consider the case below Theorem 1. Since all the samples from the same latent class are embedded into single point on the hypersphere, in that case, an arbitrarily small positive angle (arbitrarily small divergence) enough to distinguish them. More importantly, alignment and uniformity and divergence have explicit theoretical guarantees (Theorem 1) for the generalization contrastive SSL. Moreover, Wang & Isola (2020) does not consider the crucial effect of data augmentation. In fact, with bad concentration (e.g., only using identity transformation as data augmentation), "perfect" alignment along with "perfect" uniformity still can not imply good downstream performance.
empirical predictors for downstream performance, while our alignment
3.1
UPPER BOUND R. VIA ALIGNMENT
We now upper bound Rs via the alignment
Latign
E [If())) fxx2))1 x A(w)
-
(4)
which is common objective of contrastive losses. Recall that Rg can be rewritten
Rg = TP æ E UK
Ok:
sup [[((w)) - f(x2)) m)E())
5

---

Published as a conference paper at ICLR 2023
Note that there is gap between "sup operator" in Rg and "E operator" in Caliga()) which cannot be simply derived by concentration inequalities.
We separate the augmentation set A discrete transformations (-): [m]] and continuous transformations (Ao(:): E [0, }. For example, random cropping or flipping can be categorized into the discrete transformation, while the others like random color distortion or Gaussian blur be regarded as the continuous transformation parameterized by the augmentation strength Without loss of generality,
assume that for any given æ, its augmented data are uniformly random sampled, ie., Pixx = (x)) = 2m and Pla' (a)
vol(@) for any θ S [0, 1]", where vo)(O) denotes the volume of G. For the continuous transformation, we further assume that the transformation is M M-Lipschitz continuous w.r.t. 0, i... ||Ag, (x) ( S M [|0 - 02ll for any æ, 01, 82. With the above setting, have the following theorem (proof is deferred the appendix).
θH] = 2
(x)]
Theorem 2. If encoder f is L-Lipschitz continuous, then
R² S n())
E
E ELA(()
lff(11) - f(x2))l m{E)² ? Calign(
Amax[1m²222
where n(c) inf ke
ha (2m (3n(L-2/
The above theorem confirms that, with good alignment, Rg is guaranteed to be small.
4 CONTRASTIVE LOSSES MEET ALIGNMENT AND DIVERGENCE
now study two canonical contrastive losses, the InfoNCE loss the cross-correlation loss, to how they can achieve good alignment (small Calign(f) and good divergence (small μ mz).
4.1
INFONCE LOSS
The population loss of InfoNCE (Chen et al., 2020a; He et al., 2020) is well known as:
( ( (wg)
LIBONNCE
log cf((:) f(az) ((())))(e""
sa.ee mn ar A(e)) eA(a')
where encoder f is normalized by [[f]| = It can be divided into two parts:
CIsfONCE E
f(x2)) + log (ef(ar)" f(#2) + ((21) T f(x [)] EA(x'))
E
[-f(21) f(w2)
(5)
(2A(())
E
[11((m)) ((<2))
log (c((ar) slea) ((a))) ( ((=))))(()))))))
s(=)))]
A(a)
A(x(')
=:
Regardless of the constant factors, C ClalsNCB (f) is exactly the alignment term in (4). Next, we take close look at ClafoNCE:()) to see how it links to the divergence condition required by Theorem
Theorem Assume that encoder with norm 1 L-Lipschitz continuous. If the augmented data (a, -aaumeeene then for any 2 0 and k * f, we have
C ClufoNCE (f) + T(a, 8, Re)
3 exp(1 ) exp(1-s))
T [ig ue 5 log
exp
P&Pe
where ,,,, Re) is non-negative term, decreasing with smaller e, Rs or sharper concentration of augmented data, and T(a, 8, R.) 0 when = 1, 0, 0, R. 0.
The specific formulation of T(a, o, Re) and the proof are deferred to the appendix. We remark that data augmentation (a, 8), parameter e, and Pk. Pt are pre-determined before training procedure, and thus the upper bound of in Theorem varies only with ChalNNCE (f) and Re, positively.
Therefore. minimizing LIntaNCE = ClafoNCE + C ClaaNCCE (ff leads to both small CInioNCE (f) and =
C small ClaioNCE(s). Small ((nfoNCE(f) indicates good alignment Latign (f), well small R.

---

Published as a conference paper at ICLR 2023
(Theorem 2). Small Ch along with small Rş indicates good divergence (small H4 pe) by Theorem 3. Hence, optimizing the InfoNCE loss can achieve both good alignment and good divergence. According to Theorem and Theorem 2, the generalization ability of encoder on the downstream task is implied, i.e. Err(Gy) S (1 σ) + ( 2 2. when the upper bound of Fg Pe in Theorem is smaller than the threshold in Theorem 1.
is worth mentioning that the form of InfoNCE is critical to meeting the requirement of divergence, which found when we prove Theorem 3. For example, let us consider the contrastive loss (5) formulated in linear form" instead of LogExp such that
C' Cf(
-((m)) f(m2) Xf(m))
)( f(x))
CInfoNCE (ʃ) + *X2(1), L1
2, #1 E2A(()
EA(=')
where C2()) is the negative-par pair term weighted by some À > O. Due to the independence between a and x', we have (/(() = E. (A(=) )[l". Therefore, minimizing ()) only leads to the representation with zero mean. Unfortunately. the objective of zero mean with Il = can not obviate the dimensional collapse (Hua et al., 2021) of the model. For example, the encoder f can map the input data from multi classes into two points in the opposite directions on the hypersphere. This justifies the observation in (Wang Liu, 2021): the uniformity of the encoder on the embedded hypersphere becomes worse when the temperature of the loss increases, where the loss degenerates to ((( with infinite temperature.
4.2 CROSS-COR CORRELATION LOss
Cross-correlation loss first introduced by Barlow Twins (Zbontar et al., 2021). In contrast to InfoNCE loss, it trains the model via decorrelating the components of representation instead of directly optimizing the geometry of embedding space, but it is still observed to have clustered embedding space. To explore this, study the cross-correlation loss in detail and show how implicitly optimizes the alignment and divergence required by Theorem I.
The population loss of cross-correlation can be formulated as
Ceross-Con
1
1-B
E E
[f(()))(((22)
E
(f((a)) (x2))
22 ((a) snly
with normalization condition of Ex Ezi EA(a) (2:) = 0 and Ex Exi i [d]. where d is the output dimension of encoder f. Positive coefficient À balances the importance between diagonal and non-diagonal elements of cross-correlation matrix. When À = 1, the above loss exactly the difference between the cross-correlation matrix and identity matrix. Similar to Section 4.1, we first divide the loss into two parts, by defining
(2, ) [f for each
C C ( = Σ I-B E
[f(())) [((2)) and L CCross (f) == (A(())
[(x1))((=22]
In this way, the cross-correlation loss becomes Leross-Cor = (1-A) C (f) + A CCmes (f). Then, connect C[mes() (f) and CCmes() (f) with the alignment and divergence, respectively.
Lemma 4.1. For given encoder f. the aligument (fliga(f) ( in (4) is upper bounded via c(max()))
Catign (ʃ) EAA(()
E
(1((z)) (x22)) 2 LFmus(()
where d is the output dimension of encoder f.
The above lemma connects Cfros()) with (f indicating that the diagonal elements of the cross-correlation matrix determine the alignment of positive samples. Next, we will link CCmes( to the divergence 11 pr. It is challenging because (f) is designed for reducing the redundancy between the encoder's output units, not for optimizing the geometry of embedding space.
It is also called simple contrastive loss in some literature.

---

Published as a conference paper at ICLR 2023
Theorem 4. Assume that encoder f with norm vd is L-Lipschitz continuous. If the augmented data (a, 6) auagmennte,, then for any E 2 and l + E, we have
2 P&PE
L (f) + (, d-K
1k
S
V
2
where 8,,, RR) is an upper bound of Ev En m Aen
Ex= P
The specific formulation of r' E, R₂) and proof are deferred to the appendix. Here we remark that (a, 5, e, R&) is non-negative term, decreasing with smaller E, R. or sharper concentration of augmented data, and r'(a, 6,E, Re) = O when o = 1, 5 = 0, g = 0, Rg = 0. Since data augmentation (a, (), parameter E, and pk: Pe are pre-determined before training procedure, the upper bound of p. le in Theorem 4 varies only with ( (f) and Re, positively.
Therefore, minimizing LCroas-Cort leads to small L as well as small C (f). Small Erross (f) indicates good alignment Calign by Lemma 4.1 and small R. by Theorem 2. Small C (f) along with small R. indicates good divergence (small 24 pt) by Theorem 4. Hence, decorrelating the components of representation can achieve both good alignment and good divergence. According to Theorem and Theorem 2. the generalization ability of encoder f on the downstream task implied,
i.e. Err(G S (1 σ) + (2) d C C (f) when the upper bound of m1 Me in Theorem is smaller than the threshold in Theorem 1.
Beyond the above two widely used contrastive learning losses, we further analyze a very recently proposed InffNCC loss (Hu et al., 2022), which is a t-SNE style loss inspired by stochastic neighbor embedding. We show that it can also achieve good alignment and divergence in the appendix.
EMPIRICAL STUDY OF CONCENTRATION OF AUGMENTED DATA
Theorem reveals that sharper concentration of augmented data w.r.t. the proposed augmented dis- lance implies better generalization error bound regardless of algorithm. In this section, we empirically study the relationship between the concentration level and the real downstream performance.
Basic Setup. Our experiments are conducted on CIFAR- 10 and CIFAR- 100 (Krizhevsky, 2009). We consider 5 different kinds of transformations for performing data augmentations: (a) random cropping; (b) random Gaussian blur; (c) color dropping (i.e., randomly converting images to grayscale); (d) color distortion; (e) random horizontal flipping. We test different combinations of transformations via various SSL algorithms such as SimCLR (Chen et al., 2020a), Barlow Twins (Zbontar et al., 2021), MoCo (He et al., 2020), and SimSiam (Chen & He, 2021). We use ResNet-18 (He et al., 2016) as the encoder, and the other settings such projection head remain the same the original settings of algorithms. Each model is trained with a batch size of 512 and 800 epochs. To evaluate the quality of the encoder, we follow the KNN evaluation protocol (Wu et al., 2018).
Different Richness of Augmentations. We compose all kinds of transformations together, and then successively drop one of the composed transformations from (e) to (b) to conduct 5 experiments for each dataset (Table 1). We observe that the downstream performance monotonously gets worse with the decrease of transformation number, under all four SSL algorithms, on both CIFAR-10 and CIFAR-100. Notice that richer augmentation implies sharper concentration (see the paragraph below Definition 1), and thus the concentration becomes less sharp from top to bottom for each dataset. Therefore, we observe that downstream performance becomes better with sharper concentration.
We also observe that (c) color dropping and (d) color distortion have great impact on the performance of all algorithms. According to our theoretical framework, these two transformations enable the augmented data to vary in very wide range, which makes the augmented distance (1) largely decrease. As an intuitive example, if the right dog image in Figure 2 is replaced by Husky image, only with random cropping, one will get two dog heads with similar shapes but different colors, which still have large augmented distance. Instead, if color distortion is further applied, one can get two similar dog heads both in shape and color. Therefore, these two dog images have similar augmented views. and thus their augmented distance (1) becomes very small. Notice that small augmented distance (1) indicates sharp concentration (small in Definition 1). Therefore, we observe that dramatic change in concentration leads to wildly fluctuating downstream performance.
8

---

Published as a conference paper at ICLR 2023
Table Downstream performance under different richness of augmentations.
Transformations
Accuracy
Datasct
(b)
(c)
(d)
SimCLR
Barlow Twins
MoCo
SimSiam
89.76 0.12
86,91 + 0.09
90.12 + 0.12
90.59 0.11
88.48 0.22
86.38 = 0.37
89.69 = 0.11
89.34 0.09
CIFAR-I0
83.50 + 0.14
82.00 = 0.59
86.78 + 0.07
85.38
0.09
63.23 0.05
67.83 = 0.94
75.12
0.28
63.27
0.30
62.74 0.18
67.77 = 0.69
74.94 + 0.22
61.47 - 0.74
57.74 0.12
57.99 0.29
64.19
0.14
63.48
0.16
55.43 0.10
55.22 0.25
62.50
0.28
60.31
0141
CIFAR-100
45.10 0.25
50.40 0.64
57.04 0.21
51.42 0.14
28.01 0.18
34.11
40.18 - 0.04
26.26 0.30
27.95 0.09
34.05 1.13
39.63 + 0.31
25.90 + 0.83
Table 2: Downstream performance under different strength of augmentations.
Color Distortion Strength
Accuracy
Datasel
SimCLR
Barlow Twins
MoCo
SimSiam
82.75 1 0.24
82.58 i 0.25
86.68 : 0.05
82.50
1.05
1/2
78.76 + 0.18
81.88 + 0.25
84.30 + 0.14
81.80 0.15
CIFAR-10 10
1/4
76.37 +: 0.11
79.64
+ 0.34
82.76
:: 0.09
78.80
0.17
1/8
74.23 1. 0.16
77.96 0.16
81.20 1 0.12
76.09
0.50
46.67 +: 0.42
50.39 = 1.09
58,50 + 0.51
49.94
2.01
1/2
40.21 + 0.05
48.76 = 0.25
55.08 + 0.09
46.27
0.46
CIFAR-100
1/4
36.67 1: 0.08
16.22:1 1: 0.71
52.09
1 0.18
42.02 0.34
1/8
34.75 1 0.20
44.72 1 0.26
49.43 1 0.16
36.26 0.34
Different Strength of Augmentations. We fix (a) random cropping and (d) color distortion as data augmentation, and vary the strength of (d) in {1, 21 1. } to construct 4 groups of augmentations with different strength levels (Table 2). We observe that the downstream performance monotonously decreases with weaker color distortions, under all four SSL algorithms, on both CIFAR-10 and CIFAR-100 100. Recall that stronger color distortion makes the augmented data vary in wider range, leading to a smaller augmented distance (1) and thus sharper concentration. Therefore, we observe again that downstream performance becomes better with sharper concentration.
Different Composed Pairs of Transformations. To study the relationship between the concentration level and the corresponding downstream performance in more fine-grained way, compose transformations (a)-(e) in pairs construct total of (2) 10 augmentations. Contrasted to the previous two groups experiments, current composed augmentations do not have an apparent order of concentration levels. According to Definition for given smaller (1 .r) corresponds to a sharper concentration. Thus, we mathematically compute (1 - r) (see appendix for details), and observe the correlation between classification error rate Err(Gy) and (1 o)) under different on CIFAR-10, 10, based on the SimCLR model trained with 200 epochs.
Interestingly, downstream performance is surprisingly highly correlated to the concentration level (Figure 3). Specifically, if we fix one of composed transformations as (a), we find that both Err( Err(G,) and (1 σ)) have the same order that (a, d) < (a, e) < (a, e) R (a, b), under two values of 8. Furthermore, among all 10 composed augmentations, augmentation (a, d) has the smallest value of (1 - o), while the corresponding performance also the best one. addition, we observe that the choice of 5 is not sensitive to the eurve shape of (1 o1- These observations suggest that sharper concentration most likely to have better downstream performance. This also provides an explanation for Figure in Sim- CLR paper (Chen al., 2020a) of why the composition of "crop& & color" performs the best.
100
0.6
of am/e
KNVW Error
60
0.4
11
20
KNN Enor
6m80
(0.01
(a.)
(e
(6,0)
(c4)
(c.0)
(d
Combination Transformations
Figure 3: The correlation between observed
Err (Gy) and computed value of (1 a).

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENT
We would like to express our sincere gratitude to the reviewers of ICLR 2023 for their insightful and constructive feedback. Their valuable comments have greatly contributed improving the quality of our work.
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint 192iv:190..09229, 2019.
Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. arXiv preprint arXiv:2106.09943 2021.
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing
mutual information across views. In Advances in Neural Information Processing Systems, pp. 15535-15545, 2019.
Adrien Bardes, Jean Ponce, and Yann LeCun. Vicreg: Variane--inarrance--vvrii reg.aaaaiiiiiieeellliiiiiiiioooi for self-supervised learning. arXiv preprint arXiv:2105.049000 04906, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi. and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. arXiv preprint 2rXiv:2002.05709 2020a.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Patern Recognition, pp. 15750-15758, 2021.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.0422 044997 2020b.
Hongchao Fang, Sicheng Wang, Meng Zhou, Jiayuan Ding, and Pengtao Xie. Cert: Contrastive
self-supervised learning for language understanding. arXiv preprint arXiv:2005.12260 12766, 2020.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:22144 08821, 2021.
John M Giorgi, Osvald Nitski, Gary D Bader, and Bo Wang. Declutr: Deep contrastive learning for unsupervised textual representations. arXiv preprint arXiv:2006. 03659, 2020.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.0777 07733, 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, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
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 autoencoders are scalable vision learners. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16000-16009, 2022.
R Devon Hjelm, Alex Fedorov, Samuel Lavoie-Marchile Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint arXiv: I 1808 06670, 2018.
Karan Grewal, Phil Bachman, Adam
10

---

Published as a conference paper at ICLR 2023
Qianjiang Hu, Xiao Wang. Wei Hu, and Guo-Jun Qi. Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 1074-1083, 2021.
Tianyang Hu, Zhili Liu, Fengwei Zhou, Wenjia Wang, and Weiran Huang. Your contrastive learning is secretly doing stochastic neighbor embedding. arXiv preprint arXiv:2205. 14814, 2022.
Tianyu Hua, Wenxiao Wang, Zihui Xue, Sucheng Ren, Yue Wang, and Hang Zhao. On feature decor- relation in self-supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9598 0888960 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2009.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint 1vx.v:1807.03748, 2018.
Christos H Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: algorithmss and
complexity. Courier Corporation, 1998.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, Pp. PMLR, 2021.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. arXiv preprint arXiv:1906.05849, 2019.
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? arXiv preprint 20X1::2005.10243 2020.
Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. arXiv preprint arXiv:1907, 13625, 2019.
Feng Wang and Huaping Liu. Understanding the behaviour of contrastive loss. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2495-2504, 2021.
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 on unlabeled data. arXiv preprint arXiv:2010.0366 2020.
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self-supervised contrastive learning. arXiv preprint arXiv:2 15134, 2021.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3733-3742, 2018.
Zhuofeng Wu, Sinong Wang. Jiatao Gu, Madian Khabsa, Fei Sun, and Hao Ma. Clear: Contrastive learning for sentence representation. arXiv preprint 2rXiv:20/2.154000 2020.
Yuanmeng Yan, Rumei Li, Sirui Wang, Fuzheng Zhang, Wei Wu, and Weiran Xu. Consert: A contrastive framework for sele-supe sentence representation transfer. arXiv preprint arXiv:2105.11741, 2021.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. arXiv preprini arXiv:2 10o.:32200333330 2021.
Qi Zhang, Yifei Wang, and Yisen Wang. How mask matters: Towards theoretical understandings of masked autoencoders. arXiv preprint arXiv:2210.08344, 2022.
Xuyang Zhao, Tianqi Du, Yisen Wang, Jun Yao, and Weiran Huang. Arel: Enhancing contrastive learning with augmentation-robut representations. In International Conference on Learning Representations (ICIR), 2023.
11

---

Published as a conference paper at ICLR 2023
Appendix
A COMPUTE a FOR FIGURE
When ò is given, for each class Ck. construct auxiliary graph Gj. whose nodes correspond to the samples of Ck and edge (21, 222 exists if (211, S 6. According to Definition 1, we can compute the main part of C2 by finding the maximum clique of graph Gg.- Then a be estimated by [ MAXCLIQUE((G))) Ck We solve MAXCLIQUE via its dual problem vertex cover, and adopt the Approx-Verree Vertex-Cover (Papadimitriou & Steiglitz, 1998) to compute the solution.
B PROOFS FOR SECTION
Lemma 3.1. For a (a, auagmennnnnio with main part C% of each class Cs. if all samples belonging to (CT U... U C ( Se can be correctly classified by classifier G, then its classification error rate Err(G) is upper bounded by (1 σ) + Rg.
..... Proof. Since every sample æ E (CP U... -.CC n St can be correctly classified by G, then the classification error rate
K P(G(x) * k, Va E Ck]
GGr(G)=
k=1
IP
(CP
= P C9 U C US.
(1 - 0) + S
(1 0) + R..
This finishes the proof.
Lemma 3.2. Given (a, auagmemnntnoo used in contrastive SSL, for any é E [K]. if Me pa <
2 (1- (1-pe(a, (2ee 5,5) - _/) holds for all + f, then every sample x E C n S can Ri
be correctly classified by the NN classifier G5, where pela, d, 2(1 σ) + and 4, = minge(K] ||//|1///22
+ Li 2)
pt
Proof. Without loss of generality, we consider & = 1. To show that every sample E Cf n S can be correctly classified by Gy, we need to prove that for all k * 1, l[f(z)) - H1ll < []f - p
It is equivalent prove that
1 |1all)) > 0. f(xo) u1 fxxo) mn (1 ||p1112
(6)
Let f(x) EE (( Then [[(())] = (/(')) S E (I(
On the one hand
f(xo) T #1 = L f(0) [ff(x)(( e Ci)
P1
1 f(xo)
T TE]f())((a E n nS))) + f(wo) Te T Te
1
P1
P1
P(C
ns)
f(xo)
E
[f(x)]
+
E f(xx) T f(x) Mo M
P1
ms
P1
PCC nS):]
2
f(x))
T
E
[f(x))
P[C \ 09 n Sc),
nE
12

---

Published as a conference paper at ICLR 2023
where I(() is the indicator function. Note that
PIC1 \ C9 n. = ) ()) - (1 - o)pı + +Re
(8)
and
NSc = P[Ci) PPC
2m ((1 - opp + R.) = op - Re.
(9)
Plugging to (7), we have
P(C n [e)
x²
f(xo))
M1
f(Z0)
E
[f(z)]
P[C1 \ \.9 S
P1
mECPnSS
P1
Rg
Rs
2
0
f(x0)
E #EConS,
[f(x)] -r2 1 1
(10)
P1
P1
Notice that To E C n Se. For any x E C n S., we have da da(o0, x) S 8. Let (æ x²) = arg A(an)
||2/| x'1.. We have | x'1l S Since fis L-Lipschitz continuous, we have (lf(=))) |I S L- --11=0-- s =01l S L8. Since a E S., for any x' E A(x), (1lf(='))=ff s Similarly, since T. E S. and Fo. vi E A(xo), we have [=))) f( S E.
The first term of (10) can be bounded by
f
E =EC
[f(z)]
E
E
(f(x)) [(x')
=ECinS, x' E'E())
E
E
(f(x)) ( (f(x') - f(0o)) + f(xo))]
=ECinS, d'EA(w)
, +
E
E
[f(z0) T (J(zz) - [(xo))]
Es, EA(e))
2 E
E
[f(z))] T (f(x²) - f(x' + f(x'x(x)))))))) - (1xt) + f(xt) - ((x)))
ns æ' e(x(
|1
11
Ilse
2 r² - |re rL5 + rE]
= = rLL + 2s).
Therefore, (10) turns to
f(x0) 11
N
R
f(x0)
E
[f(x)] p22 (1
+
Re
P1
nE
P1
Re
Rs
N
(n²
r(T5 + 22))
,2
1
+
p1
Rs
Rs
L8
2E
2
(2a - 1)
+
P1
pl
2 (1- 2(1 - 0)
R
R
L8
2s
0
+
P1
P1
r
= 21 - (o,
(II)
On the other hand,
f(xo) (Tz
14 = (f(Zo) m1) PA + pT 1
< <11f(r0) - M1ll |1 + MTT pe
S r 11((2)))1 - 2f(20) 14 + ll 112 + 1T P
S 5r/2222 - -2f(zo) m1 + uT Pr
S (2) + uT pk-
(12)
13

---

Published as a conference paper at ICLR 2023
Note that A 11 ming |/u=1///2 /r², the LHS of (6) is
f(v)) inn
M f(zo) M4 (~ ||
1
l1mEll?)
1
2 s(x0)) (0
in1 - ((00)) Mr
2
2 (1 (() (2, - 14 14 312 n
= (1 (1- pi 6,e) ( (21r(,, An Pi M > 0,
where the second iequality due (11) and (12). This finishes the proof. Theorem 1. Given (o, -augmentatiio used in contrastive SSL, if
A
pl py
[1- Pmaz 8, 2p (r, 8,E) 2
(2)
holds for any pair of k), with l + k, then the downstream error rute of NN classifier G5
Err(G,) - (1 o) -)+ + Re,
(3)
where Pmaaz (,) = 2(1 - o) + min; Pe
R. + Lı 20) and A = minke[K] 1//x1///22
Proof. Since the augmentation A is (o, -uugmenedd there exists a main part C for each class Cx such that P 2 Opk and Sulaa..eEE d (21, 22) I 6. Since for any l * k, we have j1 Pi < 22 (1 Pmaz (o,8,e) /2pmaz 8,
72 (1 pela, 8, 22p 8, 7 According Lemma 3.2, every sample C2 n Sg be correctly classified by Gy. Therefore, every sample E (C9 n (k) can be correctly classified by Gy. According to Lemma 3.1. the error rate Err(G,) $ 1 - o + Re-
11-p
A +
Theorem 2. If encoder L-Lipschitz continuous, then
R² $ n())
E
E EAA(()
[[(xx) - f(x2))1 n(E)² Latiga())
4 m 1max(1mm2120 (e 2VnLMK
where n(E) = inf
he a
Proof. The parameter space [0. 11 of 0 can be separated to cubes .I,..., Om where m' 1 1/h and each cube's is edge length E (0, 2 Then for any given æ, have
1
[f(x)) [(x2)]
[I((A())) ((A(()))
4m
B=1
2mm ΣΣ/
11 ,, hn (I)(A((z)) [(Ao(z)))
|I (x)) f f(Ap)
d0, d0,..
2m
9 30
1,2n
Aa
By Cauchy-Schwarz inequality,
v0, (l) 1f (A) (x)))(())) [(A(()))) +11((A0())) [(Ao(x)))
14

---

Published as a conference paper at ICLR 2023
Then for any given A. sup (x)( [(Ar s (z)( -am6(())) [(Aor (x)))) or
$ (z)( - f(Ao(=))) sup [ f(Ao
0..02
Therefore, for any E [m].j E [m'], we have
sup [AA f(Agr (x))11 2
sup (x)( f(Ao (x))) do
9 h" W'E,
< 9 hn
(x)) f(Ao()))] d0 82,
sup
[If (x)) f((A,(())
II((A( f(Ao())) do +L sup 0,,
||A,, (x)(
9, hm
1 (I (x)) - [(A(2))) d0 LLM 01,050
$ e, hm
sup
110 - -211
[I((A(()) (=)( d0 +LM Vnh
e, ha
je has II)AA f(Ao())) d0 +V
Similarly, we can obtain
sup ,EE,
- (xAo(()))
1
Je, 9 1 EE0,
sup
[I[(A((z)) [(Ao (x))) d02 d0,
< Je. 9 2m (Ao, (x)) - [Ao,, (x)) d0, d0,
Je. 0., 2 DEN:
sup [((())))) - f(As, (0)(()))))))))) d0g d01
sup (Ao f (Aa (x))1 d8, d8;
Je, e, 2
e. , 12m [Ao, (a:) - 1( [Ann, (x)) d0, do,
sup
[[)() - ((Ar(())) + sup 0
[A)())))) f(Ag (x))I
0
1
0: 0; hm [f (x)) (A d0, d0, +2
Therefore,
sup [1((z)) f(x22) =1,m))((m)
supm, (x) ((A))
suppelm]JEime]] ce, [f(A,(x)) - f(Ar (x))
= max
SuPp:jemmssupoee.ccc [[f(A(())) - (x))l
sup [E(m [A)()(())) f((A(()))
sim fe, (m)))) -[(A((=)) do d0
< max
sup So, Jo, n (A,, (æ)) [(Aa, d02 d0, +2/7LMh
15

---

Published as a conference paper at ICLR 2023
y= 2B
f(As(2)))
y=1 ===1 Se, h-' (z)) f(Ao(=))) do +VLLMh
< max
i= Ej=1 j=1 Se, Sos han (1f (
- f(As, (2:) dB2 d8, nLLMh
4m A
max
2mm' A2 VULMh
4m + 2//LMh
4m2 A1 2mm' A2
< max
+ 2/TLM
4m
max ( 4m3 2mm', Am2 (A1
A2 As) + 2/TLMh
max 2mm'', Am?]
(ff()) f(x2)) + 2/
Thus, the following set S is subset of Sy:
S S= 5={0:: w:
2/nLMh max 4m?, 2mm' 4m
E
[1(())) f(x2)]
C Se.
E((())
Then by Markov's 's incquality, we have
Rg = PP
1. < P S
Ei Exg, ag A(xe) (lf - f(x2))
8 2//LAhh
max 44m 22mm ,Am"
max 4, 2m/h" 41m 4mm?12n
E
E
[f(x1) f(x22))
(s 2/TLMh
4max(1, 2/
[l((z) f(x2))l
h2 - 22/LLMh) x E(A
The above inequality holds for all h E (0, 2.ntar) thus
4 m2)22 0ch< Synte 12m - 2//LMh) EL
Re S inf
E E
11(x1) f(x2)) = ((e) E E
[1((a)) - f(x2))1
E(or)
Therefore, have
R² S n()2
EE E(A()
[1(()) f(x2))1) s n()) E
E ())(()
11((x)) s(x2)11
This finishes the proof.
C PROOFS FOR SECTION
Before providing our proofs, we give the following useful lemma, which upper bounds the first and second order moment of intra-difference within each class C₁ via and R.
Lemma C.1. Suppose that ||f(x)]| for every For each k [K].
[lf(x)) - mell S 4r (1
(1 (1-0 σ
E
L5
R
E EcC, EA(())
E
+
2r
4r
pk
and
[[(x1) 1xll s 4/2 [ o+
L 8 +
Rs
R
4p
11-0
1
#EC. E(())
2r
Pk
Pk
16

---

Published as a conference paper at ICLR 2023
Proof. For each & [K].
E #ECx
E
(x)) - u=ll
((z))
E Pk " E
E
[T( E (())a)))))) pxlll
1
1 E
E Pk mm))(())
[I(x E C2 St) (() - pxll]
[I Cs \ Cf ( -xll]]
Pk æ EA())
2r
\ C% n
E Pk (I)((
E
[I(x C n Se) [()) - mall]
Pk
1
Rg
E
[T( C2 Se) (xx) mxll] 2r
1
(using (8)
Pk x ((())
Pk
PIC n
R
E
E
[[( ) - -uull |l + 2r
1 - r +
Pk
nSC #1E((
pk.
Rs
E
E
[[(x)) - Mxll + 2r +
(13)
=Ecing, EAA(())
where
E
E
[[((z)) |kll
=ECins, 2)E)(m)
E
E
[[f(x:)
E
E f(x11)l
mECon8, A(a)(
E'EC, m26 A(=!)
P(C& \ C2 n.
E
E
f(x1)=
E
E
f(xz)
E
B
f(2z)
mEcin8, ((m)(
Pk
='Eonns aGE)(())
Pk
PIcgns
E
E
[(x1))
B
E
f(xza)
mecins, ((E)(
Pk
#'cons, A(on)
PlCk C
+
[(x1)
E
E
I (122)
*' d'EnkiCNns )w))(
PIC2 n S.]
PlCk C2 n S.]]
E =eCons, E(w))
[(x1)
E
E
f(x2)
-2
Pk
2'Ectnss #3EA(=²)
Pk
Rr
sup
sup
[1((x1) - [(x2)1 + 2r 11-0+
(14)
a.e s miE(( #26)((²)
Pk
For any a, x' E Cf Se, we have (1 x²) S ô. Let (xi. arg min A(a) ||||| æ2ll. We have || x; S 8. Since f is L-Lipschitz continuous, we have [= f(x;)| s
L. | æiلl I Lò. Since x E Sc, for any E A(x), [lf(zz) f(æi)) S s. Similarly, since a' E S., for any 22 E A(x'), we have [] - f(x5))] S e. Therefore, for any a, x' E CP ns;
and A(z). 22 A(x'),
[[(())) f(x2)) S [x(1) - f(=i)) + (1f((t)) f(x3)) + 1[f(2)) f(x2)) s 2$ + L8.
Plugging into (13) and (14), we obtain
Re
E
E
[l((x) - pall S (2= + Lб) + 4r
1- 1 +
mcC, EEA)(a)
Pk
4r 1 - o +
L
2r
+ 2
E +
Re
4r
Similar to (13) and (14), we have
R
E
E.
(1((z)) - 1= 5 E
[1[(x)) - - + 2
1 1 o +
#ECx (TA(()
*ECinS, m())())
Pk
17

---

Published as a conference paper at ICLR 2023
and
E
([)()))) - mell
= 8, 21 E(Ee)
PIC2 n
E
E
[((z)) - E
E
f(222)
#EC S, m1EA(a)
r'EOsnS, ag e(a)(
PlCk C n
[(x11
E
((x2)
Ph
PECAACTNS #xEA(w²)
Rr
E
E
f(x1)
E
E
f(x2)
+ 2r
1 1 +
=EC EIE((()
s'ECtns, #2EA((0)
pk
Rs
2
(2e Lo) 2r
o +
Pk
Therefore,
Rs }
Rs
E
E [[f(z))
1xl12
(2E L8) 2r
1 1 +
+ 4r²
1 - r
+
s E(A))
Pk.
Ph.
[11
E [ Rs )
]²
Rs
112
8
+
41
1 - +
2r
Pk.
pk.
This finishes the proof.
Now are ready to give proofs of theorems.
C.I INFONCE Loss
Theorem 3. Assume that encoder ff with norm 1 is L-Lipschitz continuous. If the augmented data is (a, -Jaugmented then for any & 2 0 and + we have
C CInfONCE (f) + (aa, e, Re)
} -s) -xxp(())))
T pe S log
exp
P&PE
where T(a,,, 8, Re) is non-negative term, decreasing with smaller Rs sharper concentration of augmented data, and r(a, 8, Re) = when a = 1, = 0, E = 0, Rg = 0.
Proof. Given x E Se, for any æτ, 22 E A(x), we have
log (eller) f(x2) + ( f(x log (e((m)) ((m)) ((())))((s)))ff ((
(())) (f(=2)-((wx)) + (fl))) f(x)
(ellf(m)))l [1:((= + ed e((m))))(())))
> log
(e (e'-e +e(m) ((a))))())))))))))))
log
Therefore, have
ClofoNCE (f)
log (cl( ( ((wx)
+ (a.)) {(x))) s(a))]
2
E
E
2.20 m as A(a))
x EA(wx'
(T(x E St) T(x: Sc)) log (alter) flaz) ( T( s(1=))
a. A(w)
e(((m))
K
K
T(x S. S.nC)))((a E C2)
E
log (e- eflmi) ((05))
+ E [( E S.) (e 4 +e 11]
z((A(z) EA(aa)
18

---

Published as a conference paper at ICLR 2023
R K
T(x: E Ca)T(a' E CC) log ( etitee + A1 - -(1 -log 2) R
E
pkpi log (et-e + e - ((1 (1-
2) + A
paPt log e''= + me (1 1 -log 2) + -1,
(15)
where A is defined as
log (e'-c ef(os) (
A
I(x Se E Cc)
E
21 (A(e) a EA(x''
k=
K
K
T(x E Ca) E Ce) (6'=5 + eth ke) [
E
k=1
K
K
E
(I(x E C+) - I(x S. ScnCk)) E Cc)
E
log (e (el-e + (m())) f(x )0
a EA((()
1=
# EA(w')
K
I[ E Cx)l(aa E Ct)
E
[oog (e' + ed(m1) ed(m1)) s(05 -log (e' elt Mé
2. (((x) x EA(x')
R=
Then.
|A
K
I log(2e)
E [I(x E Ck) - I(x E S. (cx)) Cc)
K
K
E
I(x E Cx)I(a' E Ct)
E
log (ct + el(e)) f(x 1) log (et- + cti se
A(a)( EA(xx))
km
K
K
log (c' + ((m)) (( f(x 1) log (e'-s + err
< (1 + logoo))2)) Rg +
E
I(x Ca)I(a' E Ce)
E
ma))(a) x EAA((=)
Jm
1 Fmml
ef el- + +ef (f(z1) ((x=)){(x)) u mel
(1 log R) +
I(x Cx)I(a' E Ct)
E
f(x
2 E(EA( EA(w')
1m
Em
(mean value theorem, 11,,
(1 log Rg +
E
I( Ck)T(a' E Ce)
E
f((=)) 14 mel
k=
8=1
20,00
EA(xo)
(16)
< (1 + log R, +
E
I(x E Cx)ll(a' E CC)
E
[[(((z)) - v²)T(((a)) - -pa)
e(EA(2)
EA(x')
+ +1)(())) [4xl
|| + || -1f(xx) -Hell]
19

---

Published as a conference paper at ICLR 2023
S (1 + log R) +
ΣΣ
E
I( Cx)I(a' E Ct)
E
((f(z)) -m) (x) - -eel
20,0!
a1EA(z)
K
+ E
I( E Ck)
E
[1(xx)) - mall
m1EA(z)
k=
K
7
K
< (1 log 2) +
Σ
Pk
E
E
[1(())) mell
+
E
E
[1((x)) mell
DEC E))(()
#E C& m1 E(a)
k=1
k=1
K
4Rc
4Rg
$ (1 + log 2) +
Σ
Pk
28
+ Ld 4(1 - -0) + +
+ 2
Σ
Pk:
2s LR LŌ+ 4(1 -
Pk
pk
k=1
(Lemma C.1)
=1 + log R. + (28 + L5 + 4(1 0) R2) 2 + 15 461+111-16 4(1 00) + 4KR.).
Then (15) turns to
P&PE log
(c--5 + ed se
$ CliiONCE (f) + (1 - log RR + A
< Ch (f) + (2s Lb + 4(1 a) + 4KR)) + (4s + 2LD 881- + 8KR)) 2R,.
Let
T(a, 8, RR) = (2s + L5 + 4(1 4KR)) (4e 2LD 8(1 σ) 8KR)) +2R,
and we obtain
T 14g Me I log
CluLONCE T 0, Rτ)
exp(1 - -s)
exp
P&PE
This finishes the proof.
C.2 CROSS-CORRELATION LOSS
Lemma 4.1. For a given encoder f, the alignment Latign in (4) is upper bounded via C (f))
[If(x)) f (x22) s 2// Limes
Caliga (f) EAAm((
E
where d is the output dimension of encoder f.
Proof. Since E. EZIE fi(xz)² = 1, for each coordinate component i, we have
1- E
(1(21)
EE Al
[fi(x1]² + f( a E(
E [f((2))f(<z2)
x
E
[((())) -(()))){(2>)''=
x (2E
Then
E
[lf(z:) - f(x2)11
E E((())
[f((z1) fx222
E
d
2
E
E
[f((22)
E(E
< 2
d
E
[f((1))((222))
21 E. A(w))
= 2 L
(
where the inequality holds due to the Cauchy inequality.
20

---

Published as a conference paper at ICLR 2023
Lemma C.2. Assume that encoder with norm v is L-Lipschitz continuous. If the augmented data (a, auuumenet then for any 2 0.
E E((((
S &,
where 1', RR) is defined as
4d (1-0+
Lb +.2+
+ (1-0)+
(3 33-21 20
L5 +
+ R
K 1
vdl (s² + +4dR,)²
2/d
Vd
Pk
Proof.
We first decompose the I.HS as
E
[(<1))(=2)
PKPAKE
2 E(((()
Ph
E
E
Papaaa
wECx m=)(()
K
K
E
E
Σ P&PPPE
Σ km/
Pk
E mECh #1 #2((()
E
[f(2)((( - f((1)
#cCr
EA(()
kml
kmm
Pk
E
E
[(f(x1) (f)(((())) mx) +E
E
(f(x)((((2)) f(x1)
weC
(())(()
a (((m)
k=1
Then its norm is
K
Σ papaak
E
E
((x))
K
E
E
[l((f(z1) - (fo(((())) - mbk) TII]
+1 E
(f - f(m)))) D]]]
#EC m(E)(()
28 E A(n)
A=
Pk
E
E
[1f(z)) MA 12
+ 20 ((E
[If(())]] [lf(x)) f (x
#EC, #TEA(()
k=1
K
Pk
E
E
[1f(z)) - mel1
-140)-1elll [=]
E (
[lf(
E [1f(z)) - f(x1)11
xECr E((x)
E A(())
k=1
(Cauchy- Schwarrz inequality)
K
Pk
E
E
[11( - 1=11 -Mxl
+ ve + +ddR))
1
(Lemma 4.1)
ΦECr ((E)())
k=1
K
(1-0+
8
R
Re
+ vd + +4dR)*
< 4d
Pk
+
+ 1 - +
2dd
Vd
Pk
Pk:
kml
(Lemma C.I)
4d
18 +2 (1-0+
2
+ +1-o))+KK
(3 - 20 +
Lo +
R2
Σ
1
+ Vd (e² + 4dR))
2vd
Vd.
Pk
=r'oa, Re).
This finishes the proof.
Theorem 4. Assume that encoder f with norm vd is L-Lipschitz continuous. If the augmented data (a, 8) auggmenne then for any and + we have
2
d d-K)
S
CC (f) + (,,
P&PE
2
where 7'(0, 5,,, Re) is upper bound of En Ex, ae (()))
-k
Ek I
21

---

Published as a conference paper at ICLR 2023
Proof. Let = (VPI/I......
VPKKK) E RR
K
Σ
P7
LIUT Lall -Lll
TrUU UUT - 2UU + Ia)
(due to ||| = -Tr(AT A))
+ Ix) + -d-F K
- UI +d- K
(VPIPeMA Mz Me- - 6ke)² 2 + d K
k=16=
2 Pupelun ue)2 + d K.
where der the Dirichlet function. Therefore.
(NE m))
E Ek=1 PAPAPA Iall (d K)
P&PE
Eu (an Ia+ Ek= PAPAAL Ew (m -(d -d- K)
PePe
2 En Eei (et || +2 E PRPSIM E. Re (o) (d K)
P&PE
20 (f) 22 (d K)
(Lemma C.2)
P&Pe
2 (CCOs (f) d -
P&PE
2
This finishes the proof.
D ANALYSIS OF t-INFONCE
The population loss of I-InfONCE (Hu et al., 2022) can be written as:
(1+ [)(();)))))))))) - f(x2))11)-
LIAIMONCC
E
E
log
(1 ([( f(x2) (1a=2)112)11111))))))) (1 ([( ((x-)112)-
a,.e' 01 x)E(( a A(a2))
It can be divided into two parts:
LI-EBRNNCE = E
log(1 + 11f((z)) f(x2)113)
=iLi(f)
E
E
log [[1 ([f(()) - +0 - f(x ((1))=13
(1+11((#1)
20 2n E A(x)
x EA(x')
=:Ca(1)
Similar to the InfoNCE loss and the cross-correlation loss, we can connect L,( and L2(J) with the alignment and divergence by the following Lemma D. and Theorem 5, respectively. Lemma D.I. For a given encoder J, the alignment Latign (f) in (4) is upper bounded via Ci (f), ie..
Catign (f) E(Ax))
[l((x) f(22)11 ln Lif)).
22

---

Published as a conference paper at ICLR 2023
Proof. is easy verify that log(1 t2)
4 5² for any E [0.
Since [[f(z1) - f(x2))l [0, 2]. we have
[m))) [(x2)]1 -
log(1 + (1)()))) ) (xx2))1
ln5
Thus,
Caliga (f) = E
E
[[(()) - f(æ2)]1
E
E
log(1 1 + ([( - f(x2)113)
5 #))((
4
5 (i)))
This finishes the proof.
Theorem 5. Assume that encoder I with norm is I.-Lipschitz continuous.| If the augmented data is (o, -augmenntd then for any E > 0 and k #
Pk Me S
(o,
exp
PEPE
1+26
where ,,, Re) a non-negative term, decreasing with smaller E, Rg or sharper concentration of augmented data, and T 8, e, R.) = 0 when o = 1, = 0, 0, R. =
Proof. Given x E Sg, for any 1 32 E A(x), we have
log[(1 + []((z)) f(x>)) + (1 + [[f(z)) f(x )113) "]
1
log
2f())) (1x2)
3- 2 2=)) (T [(x=)
1
log
3 2f(x)) IT f(()) 2f(x,) (f(x2)) - f(x1))
3 2f f(xx)
1
1
2
log
(x) 2 2 ( [1))
3 2/(xx) [(x)))
1
log
+
1 28
3 ()(1)) f(x
Therefore, have
C2(f)
E
E
logi(1 1l)())) f(x2) (1 (1f(()) f(x )1B) ")]
a.
02 A(x))
EA(w')
E
E
log
3 - 2f(x)))) (((x2)
- 5=22(xx)) (T((())(((z) [(x))
E((())
EA(x)')
1
E
E
[(x E S.) + I1x 52) log
2. mn a. E ((x)
3 - 2f(x1) f(x22
3 - 2f(xx) T f(x
x EA(w')
K
K
1
1
E
I(x Se Cc)l(a' Ct)
E m1EA(())
log
+
1 2s
3 )-2f(x1) f(
k=
a e"EA(=")
I( E Sc) log (1
3+2 3 3+2)
Σ
K
K
E
I(2E Cx)[(x' e Co)
1
+ 3 - 2n 111
)
+ +4, -logg.55.
1
23

---

Published as a conference paper at ICLR 2023
K K
1
PkPe log
+
-log + A
2E
3
2 we
k=1
1
2 PhPeelog log
+
24 uu
(log 2. + A1.
(17)
1
+ 25
where A is defined
K
K
A =
E
I(a E Se C E Ce)
E log
1+ +
#1 a(a)())
3 - 2f(x))
) f(x
k=1
1=1
EA(2())
1
I( E Cx)ll(ae C.) log
1+ 28
2/1 He
1
1
[L(xx Ck) 1(x E S n Cx)]u((' Ct)
log
a.EA(e)) =A(x''
1
25 1) T s(
K K
E 1(x E Ca)ll(w' E C+)
E
log
1
-oo
+
#1E((w) # EA(#')
1 2:
2f(w1) f(x))
1
3
2
k=1
Then,
A1
[[[x E Ck) - S n E Ct)] 1og
0,.t
K
2.00
E
I(x E CC)
A(ae) EA(xx')
E
log
1
2f(())) s(a-))
log
1 +
2 Me
K K
Rs log 2 +
ΣΣ E
I( E CR)I(a' E Oe)
(3 22) + (f(1))
1 2s
f(x [
15 156
#1E)(m) a EA(2')
k=
t=1
(mean value theorem, & E 1-1,1]
K
K
< Rg log 2 +
E
11< E Cx)l(( E Ct)
E
1f(x1) T. f(x ube mel
a.E((a)
k=1
1=1
x EA(2'))
< Rs log 2 + + Lb 4(1 o) σ) + 4KR))² 42 + 4(1 - 0) + +4KRs)
(using (16))
Therefore, according to (17),
1
1
PkPe log(
+ 25 3-214 μt
$ C2(f) + R. 1o5 |rا|
< (2()) R2 log + 2 (2e LB + 4(1 - + 4KR,) + +4 + 15 + 4(1 o) 4KR.)
Let
r", o,e, Re) = Rs 5og5 + (2c + La + 4(1 0) + 4KR)) + 442 + 18 + 4(1 - σ) + 4KR))
and we obtain
1 ue S
(o.
exp
P&PI
1+26
This finishes the proof.
24

---

Published as a conference paper at ICLR 2023
E ADDITIONAL PROOFS
We give detailed proof of the linear reformulation the nearest neighbor classifier in this section. Proposition E.1 (Linear reformulation of the NN classifier). Lei G arg me[k][]] (xr 14x be the NN classifier. Then
1 Gy(z) arg max (1/ (xx - =2luea12) kE[K]
which is also linear classifier.
Proof. Gy(z)= = k means for each
E [K],
[lf(x) 1M:l1 - [1f(x) mell?
This is equivalent to
N4 f(x) - |llual
1 me f(x) - =1luel1
-
holds for each f E [K]. Therefore, Gy(az) arg max (1L [(xr) =/1l/x which is a linear kE[K]
classifier.
F AN EXTENSION TO A(C&) n A(CI)
In this section, we extend our theory to the case where A(Ck) n A(C2) * Ø for some k * f, i.e., augmentation could introduces wrong signals. To quantify this negative effect, we introduce the following definition.
Definition (Correctly augmented parts). We define the corrected augmented parts of augmentation A by
Č5 = Ex Ck A(x) S C
for each & [K].
We also denote the probability of their complement as t : 1 By the definition, clearly A(C,) n A(C²) Ø, hence our theory in the main body applies to , To see this, first generalize the definition of (ar d)-aummentation to the correctly augmented parts in the following. Definition ((o, Auggmentation on corrected augmented parts). The augmentation set A is called a (a, auggeentann on correctly augmented parts, for each Ck. there exists subset C2 S Ck (called a main part of C+), such that both P/ Col 2 o P(æ E Ck] where a E (0. 1] and sup,,, su d (Z1, 222 hold.
Besides, we modify the definition of pa by Pa EgcO, Ew' Af=)) Then we have a general- ized version of Theorem I.
Theorem 6 (A generalized version of Theorem 1). Given augmentation A that is (a, 0)-
angmentation on corrected augmented parts, if
pg Ub < 12 (1- (1 (o, (0,5,))
A
2p (a, 8,6) 2
(18)
holds for any pair of (L,k) with E + k, then the downstream error rate of NN classifier G3
ErT(G,) S (1 o) 1R t,
(19)
where Pmaaz (a, 8, = 2(1 σ)
R
+ Ld 25 and A, minkelk] || 11//12.
min; Pe
We remark that the definition of R2 is unchanged. The above result gives a more general bound Err (G2) < (1 (1-a) + R +
by taking into account the correctly augmented part. An interesting trade-off between and (a, 5) emerges. Increasing the strength of data augmentation leads to better concentration, but also larger For extremely strong augmentations, t could be large and dominate the above bound, hence the performance could decrease. We leave the detailed study of this trade-off future work.
25

---

Published as a conference paper at ICLR 2023
Proof of Theorem 6. Let Rg == P Se (URE(K)(W) Then using Theorem I on U Ck directly
gives
Err(G,) - (1- R..
Moreover,
Rg P
Se (K)E
P
S. U (URE(K)
< P [ P URE
Rg +
which completes the proof.
G EXTENSIONS TO MAE, CLIP AND BYOL
In this section, discuss how apply framework to MAE (He al., 2022), CLIP (Radford et al., 2021) and BYOL (Grill et al., 2020).
G.1 MAE
MAE learns representations by recovering the original image from its randomly masked version. By viewing random mask as data augmentation, Zhang et al. (2022) has shown that MAE implicitly aligns positive pairs contrastive learning. Specifically, let and be the decoder and encoder of MAE respectively. The loss function of MAE is
LAMA f) = E
[(([(())) -m11? Ex(E
where A(x) denotes random masks of æ. Then using Theorem 3.4 in (Zhang et al., 2022) under their conditions gives
LMAR(g f) 2 Ci -aaligg (f) C2,
where C₁ and C2 are constants. Based on this result, our framework applies to MAE naturally. We can use the (o, -n-ntio to characterize the concentration property of random mask, and use Theorem 1 to study how MAE ensures alignment.
As for the divergence term, we have the following result.
Theorem 7. Assume that the decoder 9 is T.-bi-Lipschits iee., V (21, 22) in the domain of 1/L 1| =2l1 z l1g (21) - g (22) < L 1| 2zl Then for any l. k E [K]
LMAR(G m)
[lf(m) (1x2)) > C.
E
E
2 x2l2
mn EC m2CCk
x
EC
where C some constant. we further assume []]())] for every x, we have
Pk ue 51-C.
||| 1=12- (M
ay Ec EcEC.
The L-bi-Lipschitz assumption follows (Zhang al., 2022). This result shows that, the divergence bound MAE contains both the MAE loss and an addition term Ex, eC, Ea,eC, || - I2ll? which measures the class distances between original images. If the original images already have large class distances, the divergence can be ensured.
More refined results of MAE may need more additional effort.
26

---

Published as a conference paper at ICLR 2023
Proof of Theorem 7. For any E, k E [K], by the L-bi-Lipschitz property of g have
E
E
[ f(2)))
E Ec
1/L
E
E
(lo(f(x1))
æ æIEC, #xEC2
-1/L.
E
[lg(f(=1))
+ 21
22 D2
o(f(x=)))1
#1 m1 CcCh
1/(())
[||a -22l -1/L
E
[11g(s(x1)) x11
|| =(f(<>)))11
21
E1EC,
22
1
1
11((3)
- x22 1/L.
LMAEK f).
E, Ec
Pk
pe
If [f]())] = 1 for any we have
E
E
[1 ) - f(x2)11 = 2 pk.
#1EC2 2gE
Then obtain
(1 Ph pi )
pl 1
E
| 221
Laaeel f)
6L
æi 01E #2ECk
G.2 CLIP
CLIP firstly constructs positive samples by image-text pairs, and then minimizes InfoNCE loss. If we view texts as data augmentation of images, our theory applies directly. To be specific, let 7 ((xx) denote the set of all possible texts corresponding image z. this case, the augmented distance between images (parallel to equation (1) in our paper) can be defined by
dr (11, x2)
min 4 (ET())))
||t1 t2ll.
where || is some norm of the text space. Then the (a, 8) notion can also be extended follows Definition 4 ((o, Conncenntn of image-text pair). We say the image-text pair is (a,6)- concentrated, there exists C2 C C2 such that
P(x C P(x Ck) and sup dr(2)122) < á. z122E02
Note that we treat texts and images asymmetrically, i.c. we view texts as augmentation of images. The reason is that the information density in texts is larger than that in images, namely, images contain more redundant information. Therefore, for two images in the same class, their corresponding texts expected be close each other, but not vice versa. Based this model, all of our theoretical results about InfoNCE loss apply to CLIP.
G.3 BYOL
BYOL (and SimSiam) adopts training strategies to avoid feature collapse instead of involving an explicit L2 term in its loss function. Besides, its network architecture contains predictor, so its loss can not be formulated to the common alignment loss. For these reasons, whether BYOL can optimize alignment and divergence cannot be answered directly by our theory. Nevertheless, our (a, 8 8)-notion and Thm still apply to BYOL, since they are algorithm independent. Besides, our experiments for SimSiam (which is similar to BYOL) indeed verify this:
Tables and 2 show that the performance of SimSiam also gets better as the concentration augmentation gets better, which meets our Theorem I and related conclusions.
The new experimental results in Figure 4b show that SimSiam does implicitly optimize divergence during its optimization procedure.
Further theoretical study of BYOL and SimSiam requires additional effort.
27

---

Published as a conference paper at ICLR 2023
0.425
0.45
Barlow Twins (86.94)
SimSiam (89.28)
0.400
Alignment
Divergence
0.40
MoCo (90.33)
0.375
0.35
0.350
Barlow (86.94)
SimSiam (89.28)
0.30
MoCo (90.33)
0.300
200
400
600
800
200
400
600
800
Epochs
Epochs
(a) Alignment after different training epochs
(b) Divergence after different training epochs
Figure Alignment and divergence vary with training epochs.
0.6
Value of
100
KNN Error
80
0.4
40
0.2
6-70
KNN Error
6-80
0.0
0-
(a.b)
(a.c)
(a.d)
(a.e]
(b.c)
(b.d)
e)
(c.d)
(ce)
(d.e)
Combination of Transformations
Figure 5: The correlation between observed Err(G,) and computed value of (1 σ)) CIFAR-100.
H ADDITIONAL EXPERIMENTS
Alignment and Divergence. We choose the models with three different loss functions (i.e., Barlow Twins, SiamSiam and MoCo) and observe how alignment and divergence change during the training procedure. Each model is trained CIFAR-10 with batch size of 512 and 800 epochs. The setting of data augmentation fixed as the one that Chen et al. (2020a) used. the experiments, the alignment is quantified by
[XT Eoex (I)()( f(A2 and the divergence is quantified by
the average [|टा] (12 Exeo, f(x))
[C2]| Exec, f(x)) among all + E, where f is the encoder, (z) and (z) are two augmented data of x, is the training set, C. contains all the training data with label k. At the end of the training procedure, Barlow Twins, SimSiam, and MoCo achieve KNN accuracy of 86.94, 89.28, and 90.33, respectively.
We have the following observations:
At the end of the training, both the alignment and divergence are ordered MoCo SimSiam < Barlow Twins, from small to large (i.e., good to bad). We also observe that MoCo. Simsiam, and Barlow Twins achieve KNN accuracy of 90.33, 89 89.28, and 86.94, respectively. This suggests that better alignment and divergence result better performance when the setting of data augmentation is fixed. This empirical result is expected: as long as good alignment and divergence are achieved, no matter whether is due to the loss functions (e.g., SimCLR and Barlow Twins, proved in Section 4) or other unknown reasons (e.g., SimSiam), the generalization error should be small according to our Thm 1.
During the training procedure, the divergence factor always gets better (i.e., smaller) for all three kinds of algorithms. It decreases more quickly at the early stage of training. Meanwhile, the alignment factor starts to get better monotonously after several training epochs for MoCo and Barlow Twins. But for SimSiam. it becomes increasingly large. This is because SimSiam does not directly minimize the alignment, instead, a predictor involved transform the feature of one view and matches it to the other view.
28

---

Published as a conference paper at ICLR 2023
Different Composed Pairs of Transformations CIFAR-100. Similar to the experiments CIFAR- 10, we compose transformations (a)-(e) in pairs to construct a total of 10 augmentations, and observe the correlation between classification enror rate Err(Gy) and (1 or) under different on CIFAR-100, based on the SimCLR model trained with 200 epochs. We find that downstream performance is also highly correlated the concentration level CIFAR-100 which has the similar result to Figure 3.
29


Reviews:
[{"review_id": "UsuYYmE-b1", "reviewer": "Reviewer_Lkqf", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 works on contrastive self-supervised learning (SSL) and gives several bounds between the assumed latent class structure of the dataset in terms of different parts of the loss functions. For example, bounds of angles between two cluster centers $\\mu_j^\\top\\mu_k$ (Theorem 1, Theorem 3, Theorem 4), size of the regions where the representation of the input x is different from its view (Theorem 2)), in terms of different loss terms, such as (1) feature alignment within augmentation, and (2) divergence metric across views of different samples. Note that (1) and (2) are largely defined in (Wang and Isola, 2020), and the paper claims that they further study a third term $R_\\epsilon$ that represents by the role played by data augmentation, through the lens of a newly proposed concentration metric for augmentation data, i.e., $(\\sigma, \\delta)$-augmentation. Experiments verify the relationship of the downstream KNN classification performance and the concentration of learned feature for each latent class (Eqn. 3).", "summary_of_the_review": "Overall the paper has pros and cons and I am on the boundary. If authors address my concerns, I will raise the score. ", "strength_and_weaknesses": "Strength\n1. The paper works on an important problem in contrastive learning: how the data augmentation plays the role in learning good representation. \n2. The paper builds theoretical connections between different parts of loss functions to be optimized and the corresponding latent class structure. \n3. The paper is well-written with clear motivations and explanation. \n\nWeakness\n1. Claim in the intro doesn't quite match the content. \n\nWhile the author claims that they also consider a third factor concerning the concentration of data augmentation, in addition to the existing two factors, i.e., alignment and diversity / uniformity in the sphere, as in (Wang and Isola, 2020). In the analysis, it seems that the contrastive loss is still decomposed into two terms, and concentration of data augmentation serves as the additional terms in the upper bounds in theorems. It would be great if the paper can be revised to make the contribution more clear and precise. \n\n2. No comparison between InfoNCE, Barlow Twins and t-InfoNCE.\n\nFrom the analysis, it looks like all losses have two components that can bound the property of latent class models. Then a natural question is what's the pros and cons of InfoNCE, versus Barlow Twins and t-InfoNCE? In which scenarios one is better than others? It would be great if the authors could give empirical guidance. \n\n3. More experiments can be done to verify the points. \n\nThe experiments in Tab. 1-2 are largely common sense: researchers in SSL know that large augmentation helps downstream tasks, without referring to the proposed theory. While Fig. 3 is good, more ablation studies are needed to verify components of the theory. It would be great if the authors could provide experiments on synthetic datasets with the analyzed loss functions (InfoNCE, Barlow Twins and t-InfoNCE), in which the data exactly follow the latent classes assumption with ground truth (and known) concentration, and verify the theory in more details. \n\n4. Issues in mathematical rigidity. \n\nThe are some issues in the definition. $\\cap_{k=1}^K A(C_k) = \\emptyset$ doesn't mean $A(C_k)$ and $A(C_j)$ are pairwise disjoint. \n\nThe nearest neighbor classifier (last equation in Page 3) CANNOT be reformulated to be linear classifier, because what if several class centers $\\{\\mu_k\\}$ are co-linear (i.e., there exists a common vector $v$ so that $\\mu_k = \\lambda_k v$) , then linear classifier can only predict the two \"end-points\" (i.e., $\\arg\\max_k \\lambda_k$ and $\\arg\\min_k \\lambda_k$) since the score of other classes will already be dominated by the two end-points. However, NN can predict these classes with ease. \n\nSome notations are really confusing. E.g., the definition of $\\mathcal{L}_1$ and $\\mathcal{L}_2$ should be different for InfoNCE (Eqn. 5) and for Barlow Twins, yet they use the same notation, making it hard to understand. ", "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": "Qhox2IYCjyc", "reviewer": "Reviewer_LX5M", "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": "The paper studies and quantifies the generalization capability of contrastive learning approaches. Specifically, the paper derives the upper bound of downstream error by introducing the $(\\sigma, \\delta)$-augmentation. The theorems quantify the generalization capability regarding the alignment, divergence, and augmentation concentration.", "summary_of_the_review": "I overall enjoyed reading this paper. The theoretical part is informative and solid. But there are some limitations in the empirical contribution and the practical guidance of the theorems.", "strength_and_weaknesses": "### Strengths\n\n(+) The studied problem of contrastive learning generalization is very interesting and significant.\n\n(+) The theorems look solid and insightful. Examples and intuitive explanations are provided for a better understanding.\n\n(+) The paper is well-organized and easy to follow.\n\n### Weakness\n\n(-) The empirical contribution may be limited since many results are very intuitive and have been (empirically) discovered by existing works. It would be better if some new augmentation approaches or practical guidance based on the theorems can be provided. E.g, are there any optimization approaches to generate augmentations that guarantee the highest concentration subject to that divergence and alignment are achieved?\n\n### Suggestions and questions\n\n- The authors briefly discuss existing theoretical works in contrastive learning. Although they are based on different groundings, I can see there may be some common conclusions or insights. The authors discuss the difference between their theory and the “alignment and uniformity”-based studies. It would be a great additional contribution if the author can include some discussions or analyses to align more works from different grounding, e.g., MI-based and expansion-based.\n\n- Would it be possible to give a formal definition or description of the latent classes? Are they simply based on the semantics of data?\n\n- Can the (\\sigma, \\delta)-augmentation cover all kinds of augmentations in practice, i.e., for some augmentations, there is no such a set and \\sigma for some \\delta? What would happen to the conclusion in this case, if exist?", "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": "M97_OMkskUz", "reviewer": "Reviewer_qUte", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "This paper develops a new theoretical understanding of generalization for self-supervised contrastive methods. In particular, a $(\\sigma, \\delta)$ formulation is proposed to quantify the strength of data augmentation. A generalization bound on KNN error is derived based on the $(\\sigma, \\delta)$ formulation. Three key factors: alignment, divergence, and concentration were proposed, which are closely related to the generalization performance. Then the authors relate the first two factors with various contrastive objectives and prove that such different objectives all implicitly optimize the two factors. Finally, empirical experiments on CIFAR10 and CIFAR100 are conducted to study the effect of the third factor. The authors observe that the generalization performance is highly correlated to the third factor.\n", "summary_of_the_review": "Overall, the paper provides a different perspective on the theoretical analysis of the generalization guarantees of contrastive learning by modeling the concentration of augmented data. It also reveals the important role of augmentation in contrastive learning. The hypothesis is sound and the mathematical proof looks good to me. The insights from theorems are very interesting, including the three key factors of generalization, why decorrelating the components of representation results in alignment and divergence, why logsumexp is crucial to InfoNCE, why \"crop&color\" is the best composition of data augmentation, etc. I really enjoy reading this paper. I believe that this work can enhance people's understanding of contrastive learning, and provide guidance on selecting augmentations and improving existing contrastive learning methods. Self-supervised learning field is usually algorithm-driven and hence seeks more theoretical understanding. Therefore, I strongly recommend to accept this paper. ", "strength_and_weaknesses": "Strength:\n- This paper is well motivated. I can easily get the idea and insights from the theorems. This paper well explains the main phenomenon of contrastive learning that only aligning positive samples is able to gather the samples from the same latent class into a cluster.\n- The $(\\sigma, \\delta)$ formulation of data augmentation is novel. It provides a new yet simple modeling of augmented data compared to the previous graph modeling in Haochen et al [1]. More interestingly, the analysis of this paper can be directly applied to the realistic losses (eg. SimCLR, Barlow Twins, t-InfoNCE) used in practice, while [1] only suits their spectral contrastive loss.\n- Based on the proposed $(\\sigma, \\delta)$ formulation, the generalization analysis of contrastive learning becomes much more natural. Three vital factors are derived from the main result (Thm 1): alignment, divergence, and concentration. The first two factors extend the well-known alignment and uniformity in [2], and match people's intuition better. The third concentration factor is a key concept of this paper. It reveals the prerequisite for contrastive learning to work, since it does not depend on learning algorithms.\n- Section 4 is quite interesting in the sense that the analysis dissects various contrastive learning objectives from the view of the proposed theoretical framework. Various interesting insights emerge, such as why logsumexp is crucial to InfoNCE, and how to properly understand multiple contrastive losses commonly used in practice. Especially for Barlow Twins, it is very interesting to see that optimizing the statistical objective actually optimizes the geometric structure of embedding space. \n- Although the concentration factor is drived from the upper bound of KNN error, it still can provide some predictions for real downstream performance. For example, it is surprising to see that $1-\\sigma$ correlates with KNN error so well (Fig 3) in real-world experiments. It also provides an explaination for the observation in SimCLR paper that \"crop&color\" is the best (due to the sharp concentration). Moreover, the concentration concept can help to understand why (c) color dropping has a great impact on performance (Table 1).\n\nWeaknesses:\n- Compared with [2], the authors claim that the divergence condition can be loosened by better alignment and concentration properties. It seems this is a key difference from [2] but lacks of explainations. Can you provide more explanations on this to help me understand correctly? \n- In Table 1&2, if I further increase the strength of augmentation, will the performance decrease? If so, can your theory explain it?\n- Additional experiments on large-scale datasets such as ImageNet (especially Fig 3 setting) would be better. But the existing experiments are okay for a theory paper.\n- I wonder if the theory can be extended to other self-supervised algorithms such as BYOL [3], MAE [4]. Is the theory applicable to multi-modal contrastive algorithms such as CLIP [5] or only applicable to vision data?\n\n[1] 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, 2021.\n[2] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align\u0002ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp. 9929–9939. PMLR, 2020.\n[3] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent: A new approach to self-supervised learning. arXiv preprint arXiv:2006.07733, 2020. \n[4] Kaiming He, et al. Masked autoencoders are scalable vision learners. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.\n[5] Alec Radford, et al. \"Learning transferable visual models from natural language supervision.\" International Conference on Machine Learning. PMLR, 2021.\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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lgb5C8lH7M", "reviewer": "Reviewer_kpZM", "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 study the generalisation capabilities of contrastive self-supervised learning models, showing that the data augmentation strategy is key to generalisation. They decompose the problem of learning visual representations with siamese networks into 3 crucial parts, alignment of positive samples, divergence of class centers, and concentration of augmented data. By defining the problem formally, they derive upper bounds on the performance of a downstream classifier, that depends on the expressivity of the chosen data augmentation.\n", "summary_of_the_review": "The theoretical contribution of the paper is significant and valuable as the proposed framework could be used as a basis to analyse other self-supervised learning methods. However it is unclear how it could lead to practical insights that could improve these algorithms. For these reasons I recommend the score of 6.", "strength_and_weaknesses": "Strength:\n\n1) The problem is clearly stated and properly mathematically defined, which allows a formal analysis on the role of alignment, divergence, and data augmentation in the downstream performance of some popular self-supervised learning algorithms. The paper provide theoretical understanding on why these components are essential and suffisant to learn meaningful representations.\n\n2) The proposed framework could be used to analyse other self-supervised methods based on an explicit collapse prevention term in the loss, by simply showing how the quantity $\\mu_k^T \\mu_l$ is bounded by the term. Garanties on the performance of the downstream classifier can be derived automatically.\n\n3) Showing experimentally the correlation between $\\mathrm{Err}(G_f)$ and $1 - \\sigma$ is nice. Having more experimental results on the relation with $\\delta$ as well would be even better.\n \n\n\nWeaknesses:\n\n1) Some self-supervised learning methods are hard to modelize in the proposed framework. For exemple BYOL and SimSiam which have no explicit collapse prevention mechanism in their loss function. How would you derive similar bounds for these methods ?\n\n2) It is hard to tell how tight the bounds are in practice. Could you derive practical insights from your theoretical analysis ? For exemple design better data augmentations ?\n\n3) The experimental analysis and the experimental results of Table 1 and Table 2 are very basic and already known results.\n\n\nRemarks and Questions:\n\n1) How would you tackle the case where the $A(C_k)$ intersect ?\n\n2) What is the intuition behind the \"Main part\" in Definition 1 ? Is it a critical detail ?\n\n3) \"Thus, the semantic distance can be partially characterised by the proposed augmented distance\". I believe semantic is much more complex than visual ressemblance. Making this assumption would not work for less fine-grained classification tasks where two samples from the same class are not necessarily visually similar. This might be an inherent shortcoming of these methods based on learning invariances to data augmentations. \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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FwrHLgSJjZK", "reviewer": "Reviewer_R8Eq", "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": "In this paper, the authors analyzed the Self-supervised learning frameworks such as SimCLR, MoCo, and Barlow Twins in perspective of augmentations. (sigma-delta) augmentation was defined to indicate how close the augmented data with the same class are. The authors suggested three important properties to analyze the performance of SSL: alignment, divergence, and concentration. Common SSL losses, InfoNCE, and Cross-Correlation loss can be split into smaller components which are represented as the optimization terms of the alignment and divergence properties. In experiments, various augmentation settings with different strengths were used for comparing the downstream performance with them. In CIFAR-10 and CIFAR-100, the model trained with stronger augmentations can be more robust than with weaker ones. The stronger augmentation can imply a more concentrated cluster of each class.\n", "summary_of_the_review": "The authors defined (sigma-delta) augmentation and three important properties to measure the SSL model's performance. InfoNCE and Cross-Correlation loss functions can be separated into two components that optimize the alignment and divergence properties respectively. To show the correlations between concentration property and augmentation, the authors conducted several experiments with various augmentation sets with different intensities. Updating more recent works and adding more exact analyses or experiments on each property can dramatically enhance this work's novelty.", "strength_and_weaknesses": "## Strengths\n+ Theoretical analyses on the effect of augmentations are less often than ones on the negative samples recently. This paper may give some insights into further research on both positive and negative samples in SSL.\n+ There were few attempts to analyze the mechanism of SSL frameworks without negative samples such as BYOL and Barlow Twins (BT). To prove the robustness of SSL models, the integrated perspective which includes both InfoNCE and non-InfoNCE-based frameworks will be needed and this paper can be the pioneer of it.\n+ The authors defined the three important properties which can represent the status of distribution of the features. Their concept can be widely used to further researchers who analyze similar problems.\n\n## Weaknesses\n- I think that lack of information on recent works may decline their work's novelty. Recently, some papers analyzed the relationship between SSL loss function and supervised learning loss with the collision phenomena such as [1]. In [1], the authors showed that the upper bound of supervised learning loss contains the intra-class variance term which is similar to the concentration property in this paper. I carefully suggest including more recent works which tried to solve a similar problem.\n- The authors used popular, but somewhat old-fashioned augmentations to validate their claims. One of the main results of this paper is stronger augmentations will bring higher performance. However, another recent work [2] said the dramatic distortion of the data can harm the essential information for the downstream tasks (in this case, classification), and it will degrade the performance in the end. This implies that their claim can be right in their experiment settings, but it may not be applied always. Conducting more experiments with other datasets or stronger augmentations such as adversarial attack-based augmentations can be a good way to justify the authors' claims.\n- The authors analyzed alignment and divergence properties in theoretical ways. However, there are no experiments that support their theory. Instead, there are only experiments for the empirical study of concentration property. In general, we cannot be sure that a property is always preserved when the model is trained with a loss with it. This means that there may still exist some performance drops caused by the former two properties (alignment and divergence) in the experiments on the concentration property. I suggest adding more analyses to show the trained model satisfies the former two properties in every augmentation set.\n\n[1] Ash, Jordan, et al. \"Investigating the Role of Negatives in Contrastive Representation Learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n\n[2] Yang, Kaiwen, et al. \"Identity-Disentangled Adversarial Augmentation for Self-supervised Learning.\" International Conference on Machine Learning. PMLR, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster