An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
Authors: Jingyi Cui
Hongwei Wen
Yisen Wang
Venue: ICML 2025 poster (2025)
Keywords: theoretical understanding
contrastive learning
self-supervised learning
Primary area: deep_learning->selfsupervised_learning
TL;DR: We for the first time propose an augmentation-aware error bound for self-supervised contrastive learning, enabling discussions on the effect of specific data augmentations.

Abstract: Self-supervised contrastive learning has emerged as a powerful tool in machine learning and computer vision to learn meaningful representations from unlabeled data. Meanwhile, its empirical success has encouraged many theoretical studies to reveal the learning mechanisms. However, in the existing theoretical research, the role of data augmentation is still under-exploited, especially the effects of specific augmentation types. To fill in the blank, we for the first time propose an augmentation-aware error bound for self-supervised contrastive learning, showing that the supervised risk is bounded not only by the unsupervised risk, but also explicitly by a trade-off induced by data augmentation. Then, under a novel semantic label assumption, we discuss how certain augmentation methods affect the error bound. Lastly, we conduct both pixel- and representation-level experiments to verify our proposed theoretical results.

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
Jingyi Cui
Hongwei Wen
Yisen Wang
Abstract
to encode useful features that capture semantic similarities between different instances in the data, leading to improved performance on downstream tasks like classification, detec- tion, or segmentation.
Self-supervised contrastive learning has emerged as a powerful tool in machine learning and com- puter vision to learn meaningful representations from unlabeled data. Meanwhile, its empirical success has encouraged many theoretical stud- ies to reveal the learning mechanisms, However, in the existing theoretical research, the role of data augmentation is still under-exploited, espe- cially the effects of specific augmentation types. To fill in the blank, we for the first time pro- pose an augmentation-avee
Aside from the empirical success of self-supervised con- trastive learning, many theoretical works aim to explain its underlying working mechanisms. The main theoretical framework branches into two categories. The first category directly builds relationship between the unsupervised con- trastive risk and supervised risks via statistical modelings (Arora et al.. 2019; Nozawa & Sato, 2021; Ash et al., 2022; Bao et al., 2022; Lei et al., 2023). However, these works assume that the anchor and positive samples are condition- ally independent, which contradicts the practical selection procedure of positive samples therefore being unrealistic.
error bound for self- supervised contrastive learning, showing that the supervised risk bounded not only by the unsu- pervised risk, but also explicitly by trade-off in- duced by data augmentation. Then, under novel semantic label assumption, we discuss how cer- tain augmentation methods affect the error bound. Lastly, we conduct both pixel- and representation- level experiments to verify our proposed theoreti- cal results.
The second category depends on the assumption of augmen- tation graph and borrow mathematical tools from unsuper- vised spectral clustering (HaoChen et al., 2021; Zhang et al., 2023a; Zhuo et al., 2023; Wang et al., 2024a;b). However, the augmentation graph assumption is relatively abstract and typically hard to verify. Wang et al. (2021) proposed a similar assumption called augmentation overlap, but it still fails to explain the impacts of specific kinds of data aug- mentations. Huang et al. (2023) proposed a (a, 87)-mmsuueee to mathematically quantify the data augmentation, whereas there still remains a gap between this measure and real- world data augmentation methods.
1. Introduction
Self-supervised contrastive learning has shown great empir- ical success in learning representations for computer vision (Chen et al., 2020a;b; He al.. 2020; Chen al., 2021: Grill al., 2020; Chen & He, 2021) and multi-modal tasks (Radford et al., 2021; Zhang al., 2023a). Typically, con- trastive learning model learns to distinguish between similar and dissimilar pairs of data points by drawing near the pos- itive samples (data augmentations of the same instance), while pushing away the negative samples (data augmenta- tions of different instances) (Chen et al., 2020a;b; He et al., 2020; Chen et al., 2021). This process encourages the model
Aside from these two major categories, there are also other explanatory works of contrastive learning from aspects of feature geometric (Wang & Isola, 2020; Zhang et al., 2023b), information theory (Tian et al., 2020; Wu et al., 2020; Ouyang et al., 2025), independent component analysis (Zim- mermann et al., 2021), neighborhood component analysis (Ko et al., 2022), stochastic neighbor embedding (Hu et al., 2023), message passing (Wang et al., 2023), distribution- ally robust optimization (Wu al., 2024), etc. Nonetheless, the role of data augmentation is still under-exploited in the existing theoretical frameworks, especially without mathe- matically analyzing specific data augmentation methods.
'State Key Lab General Artificial Intelligence, School of Intelligence Science and Technology, Peking University Facultyy of Electrical Engineering. Mathematics and Computer Science, University of Twente "Institute for Artificial Intelli- gence, Peking University. Correspondence to: Yisen Wang Eyisen.wang @ @aong@@ku..com pku.edu.cn..
Under such background, in this paper, we propose an augmentation-awar theory for self-supervised contrastive learning. Specifically, we derive novel dccomposition of the unsupervised contrastive risk with respect to the number
Proceedings of the 4rnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

An Augmentation-Awarc Theory for Self-Supervised Contrastive Learning
of negative samples sharing the same label with the an- chor. Then through investigating the inner risks, we propose our main theorem of the augmentation-awan error bound, which shows that the supervised risk is not only bounded by the unsupervised contrastive risk, but also by the minimum same-class distance and the maximum same-image distance of the augmented dataset. Then under a novel semantic label assumption, we analyze specific types of data aug- mentation and discuss the existence of trade-off between the two distance terms with respect to the strength of data augmentation.
to Section 2.3, where we first propose a novel decomposi- tion of the risk and then investigate the bound of the inner risk. Detailed proofs are shown in Appendix B.
2.1. Mathematical Formulations
Notation. For original input data, we use the bar nota- tion to denote the original input image, i.e., we let X de- note the set of all possible data points and denote Px as the corresponding distribution. Then we have the input image ā E X ~ Px. We denote C' E N as the num- ber of classes, and с E [C] ~ Te as the class label of x, where [C] := (l..... C} and Tec := P(y = c) denotes the marginal probability distribution of Class c. Denote π { Moreover, we denote Pe := P(-ly c) as the posterior probability distribution of Class c. For the augmented data, we let A denote the set of all possible data augmentations, and denote PA as the corresponding distribution. We denote x == a()) as the augmented image, where a E PA.
Our contributions are summarized as follows.
We for the first time propose an augmentation-awarr error bound for self-supervised contrastive learning, which explicitly includes the quality of data augmenta- tion in the bound without any additional assumptions. The bound shows that data augmentation is equally important to downstream classification as the unsuper- vised contrastive risk.
Unsupervised contrastive learning. In unsupervised con- trastive learning, we select the different data augmenta- tions of the same input image as the positive samples, and select the data augmentations of different input images as negative samples. The data generation process is de- scribed as follows: (i) draw positive/negative classes: e, {cr ) k' (ii) draw an original sample for the anchor and positives T Pei (iii) draw original samples for the negatives क5 Pee k = =1,.... 1....., K; (iv) draw data augmentations a, a', {ax] ~ -AK+1. Then the anchor is x = a()), the positive sample is x' = a'=) and the negative samples are F2=- = ax h =
By proposing novel semantic label assumption, we analyze specific types of data augmentation including random resized crop and color distortion, and show a trade-off with respect to the strength of data augmen- tation, i.c., the minimum same-class different-image distance decreases while the maximum same-image distance inereases as augmentation strength increases.
We conduct both pixel- and representation-level exper- iments to verify our theoretical conclusions. We verify the trend of distances with respect to augmentation strength and that the optimal augmentation parameters lead to optimal downstream classification accuracy.
Compared with the CURL frameworks (Arora et al., 2019). our formulation accords better with the practical applica- tions of unsupervised contrastive learning, where the anchor and positive samples are drawn from the augmentations of the same input image, instead of the same latent class samples. That means, we no longer need the conditional independence assumption. Moreover, we formulate the data augmentations a, a', ] explicitly, making it possible to analyze the impacts of data augmentation to the error bounds.
The paper is organized as follows. In Section 2, we pro- pose our theoretical framework, including the mathematical formulations and our proposed augmentation-awanl error bound for supf-supe contrastive learning. In Section 3, we compare our bound with existing theoretical studies. Based on the error bound, by proposing the semantic label assumption, we analyze the effects of specific types of data augmentation including random resized crop and random color distortion in Section 4. In Section 5, we conduct nu- merical experiments to verify our theoretical conclusions. Finally, we conclude our paper in Section 6. Appendices A, B, and C present the related works, proofs of the theorems, and additional experiments, respectively.
In this paper, we investigate the widely used InfoNCE loss function (Chen et al., 2020a; He et al., 2020; Arora et al., 2019), i.e., for f ::X' - Rd, the loss function is
L (x, {
e (
2. Theoretical Framework
== log (e(()) f(x)) + Σk= el(2) ((w))
In this section, we first introduce the mathematical formu- lations in Section 2.1. Then in Section 2.2, we present the main theorem of this paper, i.e. the augmentation-ane awaree er- ror bound. We delay the error analysis of the main theorem
which is mathematically equivalent the logistic form
L x', (xx (x))
2

---

An Augmentation-AAare Theory for Self-Supervised Contrastive Learning
K exp (- (()x))))() f(w)))). (2) -
Theorem 2.1 (Error Bound). Let (e))()) be the su- pervised risk of the mean classifier, and Run (f) be the unsupervised risk of contrastive loss. Denote TK P(Col(c, {c* * 0) as the class collision probabil- ity, where Col(c, {cx) - - 1|c =.]. Then we have the following upper bound of the supervised risk.
lo 1
Under the above-mentioned data generation process, we have the unsupervised contrastive risk as
RThh ()) == Be,lexhrein) Ea- Ba (axhue()
1
Roup 2
[R
TA Be log(Col + +1)
-L (a(x), (an( (3)
TK
+ E, E2 Ppp E min [If((()) f(a'(=
For the empirical forms, define the datasets
+ 5E, max [[((())) [ad' (7)
S = [1r a Fy1. F5KK }]jj)) Then the empirical unsupervised risk is denoted as
a,a
Theorem 2.1 shows that the downstream supervised risk is upper bounded by both the unsupervised contrastive risk, CURL's class collision term, and two distance terms. The first term represents the minimum distance between two aug- mented same-class (different) images. Intuitively, this term measures how well the same-class images are connected. The better the same-class connection, the smaller this term is. The second distance term represents the maximum dis- tance between the two augmentations of the same images. Intuitively, this term could be understood as the range or variance of data augmentation.
um (f) =
1 Σ jEIn
(" 12 (2
(4)
Downstream supervised classification. To evaluate the rep- resentations learned by unsupervised contrastive learning, we adopt the linear- linear-probing setting, i.c. given the learned representation f X + Rd, we train a linear classifier g f Rd + IC on top of f with W E RCxd Note that in the downstream classification task, usually the goal is to classify original images instead of the augmented ones, because when directly using pre-trained model, it is hard to know the exact augmentation methods in training and replicate them on the downstream datasets.
Typically, as the augmentation strength increases, an image is more likely to be connected with other images under data augmentation, and the first distance term is smaller. On the other hand, stronger augmentation has larger range and variance. As result, there is a trade-off between the two distance terms w.r.t. augmentation strength. This point will be further discussed in greater detail in Section 4 and verified in Section
Following previous theoretical works (Arora et al., 2019; Nozawa & Sato, 2021; Ash et al., 2022; Bao et al., 2022), we use the mean classifier for evaluation. Specifically, the mean classifier defined as = WS, where W := [Mc T Me == [ [C].
In addition, it is worthwhile mentioning that we can further improve the coefficient of the second distance term to I with a mild assumption that the original input image has a centered representation among all of its augmentations. This assumption has been made implicitly by previous works, e.g. Nozawa & Sato (2021); Zimmermann et al. (2021).
We adopt the softmax cross entropy loss for the mean clas- sifier g, defined by
(o (1 -log
D
cala),
which is mathematically equivalent to the logistic form
Assumption 2.2 (Centered Representation). For E X and f : X Rdd, we assume that E f((=))((())) = f()).
Coup (2, e; f) = log (1 + Σ f(3) (Me ))
Theorem 2.3 (Error Bound (Improved)). Under Assumption 2.2, we have
Under the data generation process, we have the supervised risk as
1
Ruu <
R un - TK feu log(Col + +1)
1 - TK
(f) = Eown Ez-p, Lu ( ff.
(6)
+ ExEx up. E. min -
a"
+ Ex max (af((()()))) ((c (8) a.a'
2.2. Augmentation-Aware Error Bound
In Theorem 2. we present the upper bound of the super- vised risk of the downstream mean classifier (the lower bound of the unsupervised contrastive risk), where two terms regarding with data augmentations are shown explic- itly in the bound.
To provide the generalization bound, we introduce the em- pirical Rademacher complexity as follows,
Rads(F) = -E.-
sup Σ ΣΣ fEF JEIN] kE[K] rE|d]
3

---

An Augmentation-AAare Theory for Self-Supervised Contrastive Learning
To derive the relationship between the unsupervised con- trastive risk (J) and the downstream classification
+ (caae))) + (smaall(as))
risk RT))()) we construct intermediate supervised risk RePP (f) ;= (e, (Ba log + (-
Theorem 2.4 (Generalization Bound). Assume that [I((z)ll2 S R for any f F and E X and the unsu- perivsed loss L is bounded by B. Then for any ò (0,1)
[()) T (Mee - (ea))) which has a similar decomposition with Rm)(() shown in Corollary B.
and any I E F, we have
RouP()) 5 - TK
1
Run uun (f) +
12RRads(F)
Next, in Theorem 2.6, we investigate each inner risks Tke and build a relationship between l' and ri We show that for k O...., K, r' is upper bounded by rh minus a series of distance terms, including the distances between same-class different-image augmentations and that between same- same-image data augmentations.
n
log(26)
+ 3Bx
2n Tx c log(Col +)
+ E, p' up
Eg min (II((()))))))))))))))(((())))[)) f(a((='))
+ 51L max
f(d'''"))
Theorem 2.6 (Bound of Inner Risk). Let E belong to Class c. For k 0,...,K, K. given .1,....26 is # c, we have
with probability at least 6.
rk (i(,,....,
We show the generalization bound in Theorem 2.4, where the population downstream supervised risk is bounded by the empirical unsupervised contrastive risk. Note that the proof follows from Lei et al. (2023), where the dependence of K is removed compared with that in Arora et al. (2019).
2 'x
sup (i,, (i1,...,,v
in) (2)(a()((()))) (())
+ BB max (1((d - f()(
a'aa"
+ Bs pim max (a" (a(((=
d'aa"
+ Ex En min (f f(a" log (1 + exp
(12)
2.3. Error Analysis
where r (i1.
In this part, we present the key theorems in proving The- orem 2.1, the main theorem of this paper. Specifically, in Theorem 2.5, we derive a novel decomposition of the un- supervised contrastive risk w.r.t. the number of negative samples sharing the same label with the anchor. Note that this decomposition is non-trivial, as it only works for con- trastive losses that treat negative samples equally.
Σm [(x) (Ho - mim))) and μs E Eneng J (+²),
i E (c.
Then combining Theorem 2.5, Corollary B. and Theorem 2.6, we reach Theorem 2.7 showing the relationship between Ru and Ruup, i.c. R=uP is upper bounded by Ru and two distance terms induced by data augmentation.
Theorem 2.5 (Error Decomposition of R!"), We have
Theorem 2.7 (Error Bound of Reup). We have the following upper bound of the supervised risk.
RTT (f)
Expp Eg Σ ... .....nn Ipp((t...,i $1
Ruu SR Run R. En min ([((()))))())))))))))))))))))))) - [((((()
Ax
+ +5E,Brrpp max [I(((())) - f(a (z)))) (13)
E.EEr E. Ep((t)ri(t)) + Ee
(9) Finally, close the gap between Reup and ReuP, we adopt the CURL bound directly. Theorem 2.7 and Lemma 2.8 together finish the proof of Theorem 2.1.
iy
where k = O,...,K K and in, i Ss. we denote
Lemma 2.8 (CURL bound (Arora et al., 2019; Nozawa & Sato, 2021)). Denote TK = P(Col(e, (cx {c))k=) * 0) as the class collision probability, where Col(c, {c)]<
Th Tk(ii....,.5) == EzInpI, Earxps Expp
Ea ( ((a)))iiia(((().).).)))))))))))) (7)).) (10)
Σ 1[c = Cx)- Then we have Rup (f) (1 TK RRTP)(
and
+ +TK log(Col
(14)
palii....,, (2) PPS)........
such that Cj = ii,..., CG. = is. and Cjuss me))
3. Discussions on the Error Bound
(11)
We first compare our bound with previous studies on build- ing relationships between the unsupervised contrastive risk
where .jkk is rearrangement of [K].

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
and downstream supervised risk. Most of these previous bounds under the CURL framework (Arora al., 2019; Ash et al., 2022; Bao et al., 2022), which assumes that the positive samples are conditionally independently drawn from a certain class, whereas our framework explicitly for- mulates the probability distribution of data augmentation and assumes that the positive samples are drawn as different augmentations of the same input image. That is, we are based a more realistic data generation process that cords with the empirical applications of contrastive learning.
tations to be exactly the same, nor do we need the perfect alignment assumption adopted in Wang et al. (2021). In- stead, the distances between different augmentations are shown explicitly in our bound without any additional as- sumptions. Later on, Huang et al. (2023) defined a kind of (o, me-esure to mathematically quantify the data aug- mentation, and provided an upper bound of the downstream classification error rate. Whereas their bound relies on the maximum (augmentation) distance of same-class images, our bound relies on a trade-off between two distance terms, enabling us to further discuss real-world data augmentation methods.
Perhaps more related to our bound, Nozawa & Sato (2021) derived a lower bound of InfoNCE loss based on the same data generation process as ours. However, they treated the gap term d(() induced by data augmentation as an al- most constant, whereas in this paper, we further dissect the augmentation-reles relevann terms into two distance terms based on our proposed error decomposition, resulting in a trade-off between the minimum same-class distance and the maxi- mum same-image distance. Our result suggests that to reach a better downstream classification risk, data augmentation equally important as the unsupervised contrastive risk.
4. Impacts of Data Augmentations
In this section, we try to explain the trade-off between the two distance terms in Theorems 2.1 and 2.3 from the per- spective of pixel-level discussions of the training images. As suggested by Chen et al. (2020a), the combination of random cropping and random color distortion contributes to successful downstream classification. Therefore, in this part, we discuss the impacts of random cropping and random color distortion respectively.
Also note that because the focus of our bound is on the role of data augmentation rather than that of negative samples, we directly adopt CURL's class collision term for simplicity. Nonetheless, our bound is in fact compatible with previous bounds under the CURL framework, e.g. Arora et al. (2019); Nozawa & Sato (2021); Ash et al. (2022); Bao et al. (2022), with replacing the class collision term with their correspond-
First of all, under the Lipschitz continuous assumption, we transform our main theory into an error bound w.r.t. the pixel-level distances, so that we are able to discuss the impact of specific data augmentation.
Assumption 4.1 (Lipschitz Continuity). For x, E X, there exists a constant CL 2 0, such that
ing forms. As the two distance terms in (7) are independent of the number of negative samples K, we could reach the same conclusions on the role of K as in the corresponding previous works.
- - ( S ca1lx- x'11
(15)
Theorem 4.2 (Error Bound with Pixel-level Distances). Un- der Assumptions 2.2 and 4.1, we have
We also compare our bound with works that explain con- trastive learning from the perspective of data augmentation. Wu et al. (2020) discussed the importance of data augmenta- tion from the perspective of permutation invariance, but the impact of data augmentation was not reflected in the error bound. HaoChen et al. (2021) proposed a concept called augmentation graph where the vertices are all the augmented data points and the edge weights is the probabilities that two augmentations are generated from the same input image. Their derived downstream error bound relies on the eigen- values of the adjacency matrix of the augmentation graph. Similarly, Wang et al. (2021) built their theory on the as- sumption of augmentation overlap, meaning that two images have the same augmented view under some data augmenta- tion. However, it is unlikely in practice that two different real images have exactly the same augmented views, espe- cially as we usually use only two views in training instead of using multiple ones. By contrast, in this paper, we treat the connectivity between augmented views in rather "soft" way. Specifically, our bound does not require the augmen-
R
<
R
TK
B. (o log (Col + 1)
TK
+ C₁ B. E. up Eng min ||( al (z')l
a'
+ er C. max ( (z)')l]] (16)
Inspired by Koenderink (1984), we introduce the pixel-level formulation of an d x d 3-channel original input image. Specifically, for any integers j. l E [d]. define
1=11 1
e 7
(17)
d
representing a square with side length 1/d. Then in each channel, a d x d image ž (E jeM, with d2 pixels can be expressed as a function
( 2 + 10,
(18)
5

---

An Augmentation-Awar Theory for Self-Supervised Contrastive Learning
where the value of the (j, f)-th pixel in the i-th channel is given by
4.2. Impacts of Random Crop
Based on the pixel-leve formulation, given the scale param- eter ó E (0, 1], we formulate the random resized crop of an image as { Acrop
ge d [( J1ze (u, du, i E (l....,d}. d}, (19)
& derop (u, v) = [(errop b)) = E(Ou - T, f0 - -');
representing the average intensity of g(o) on J,..-
where ~ Unif(0, T, ~ Unif[0, 1] are i.i.d. random
4.1. Semantic Label Assumption
variables.
We introduce the generation process of pixels based on semantic label assumption. We underline that our proposed pixel-level generation process aims just to provide a possible explanation for the trade-off in the two distances terms of Theorem 4.2, rather than generating images.
Denote || -|e as the Frobenius norm. For the minimum dis- tance between same-class offfereent-mage augmentations, if al (z) contains only same-semantic label pixels (with seman- tic label s), then we have
I Ea( min [|a(T) - d'(x')lrr
Specifically, we assume that image can be decomposed into several semantic areas with their corresponding seman- tic labels, where the semantic areas/labels are dependent on the class label. That is, for an original image म. aside from a class label for the entire image, each pixel h5.t also has a unique semantic label 8 that relates to y.
Eimin
Σ
(5)7 - -00 2/2
-5
o'
(E() - /1 (100))111 1/2
For example, an im- age of Class automo- bile usually has seman- tic features windshield, headlights, wheels, etc., and an image of Class truck usually has se- mantic features truck cab, cargo box, wheels, etc. As illustrated in Figure 1, we mark the disjoint semantic ar- eas with distinguished color boxes, and we mark the shared se- mantic wheels with the same color.
Σ
Bgat 10 (5 - -1(0)
1/2
jr (3) (3)
2 d
000)
1/2
20
(20)
where f and (+) denote the mean and variance pixel value of semantic class in the i-th channel, and the second incquality holds because there cxists small enough 0 such that its induced resized-cropped a' d((x)) has all pixels with semantic label s.
(a) Automobile.
(b) Truck.
Figure Illustration of semantic label assumption. (a) An automo- bile image with semantic labels windshield (blue), headlights (pur- ple). and wheels (green); (b) an truck image with semantic labels truck cab (yellow excluding green), cargo hox (orange), and wheels (green).
On the other hand, if the pixels in (x)) has more than one semantic labels, then we have
Ba(s) min |a()) a' (3'))l 1F)
(5)) d' (37) 3 1/2
= E min Σ
Σ
Mathematically, assume there are T > 0 possible semantic labels {si,..., 8T} } E {0, 1)ah (Without loss of generality, we assume ST represents the background). We use s, = to describe that the semantic s, exists in an image of Class y and s, = 0 otherwise. For & E [T] and y E [C], we denote by : (s. = 1 1yy) as the probability that semantic label st is related to Class label y. Moreover, for i 1,2, denote 1/5, P(5(*) (s;) as the probability of a pixel with semantic label s have value g() in the i-th channel.
Bat s0 (5)1 - /1 /((5)) 1/2
Σ
(5(()) (8) )2) 1/2
Σ
E
B
Tomax
Σ
(n!0 10( )²]
1/2
Then the pixel-level generation process is shown as follows: (i) Draw a class label E [C] ग.; (ii) draw semantic labels St ~ qy: (iii) generate a disjoint random partition (Jm Ei ft, (iv) For each pixel in Jm with semntic label St, draw a value in the i-th channel following 1/.
= 2o
1[s(Eae) # smax] -na] J.FE(M)
Σ
1/2
(21)
where Smax denotes the majority semantic label that most pixels in a(T) have. Compared with the single-semantic
6

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
case (20), there is an additional bias term in (21) result- ing in a larger overall distance. Moreover, the larger the crop size, the larger the probability that the cropping area intersects with the partition boundary, leading to a higher probability that a()) has more semantic labels and larger Eeteja (SS(e) + {mmx)]] Consequently, a larger crop size (or larger scale parameter d) results in larger value of E. min, [|a(z) d' dIl')
+
(n( p )2) 1/2 1211/2
of [E]3]
: : [E j.PE[d)
(ss(Er,)) # Smax)] =//2) 2//21/2
1/2
(24)
where the last equation holds by taking X v /E Compared with the uniform-semantic label case, when the pixels have multiple semantic labels, the color manipulation has a less significant effect because it can only reduce the distance terms with regard to Smax and still fails to deal with the bias term. This also to some extent explains that with- out cropping, color distortion alone does not lead to good downstream performance. (As shown in Figure 5 of Chen et al. (2020a), the linear probing accuracy of color+crop is 56.3, whereas that of color alone is merely 18.8.)
Likewise, for the maximum distance between same-image different augmentations, with smaller crop size, it is more likely for a(ï) to have different pixel-level seman- tic labels with the least alike augmentation a(()), and therefore having larger bias term and the overall distance E. Ex maxa,a' [|a()') (z')]]-
4.3. Impacts of Color Distortion
On the other hand, for the maximum same-image distance, by (21), color distortion enhances the bias term, because if 1, we have
The random color distortion used for data augmentation usu- ally contains adjustments of brightness, contrast, saturation, and hue. For simplicity, we use brightness manipulation of each channel augmentations w.r.t. colors. Specifically, based on the pixel- level formulation, given the brightness adjustment parameter b > O, we formulate the random brightness distortion of an image as f o Ocolor
example to represent the random
max
|a(x) a' a1(T)ll a.a'
Σ (5
27 1/2
max X0E(0,0)
(5)2 - 27 1/2 j.t)
((i) o Ocolor (u, u) = ( (u, v).
(22)
Σ i/E|4/ie
(25)
where 109 E Unif(O, b). E [3].
5. Verification Experiments
With combining Acolor and Gcrop. if ((z) contains only same- semantic label pixels (with semantic label s), then we have
In this section, we aim to verify our theoretical conclusions through empirical experiments. Specifically, in Section 5.1, we verify the trade-off between the two distance terms induced by data augmentation in Theorem 2.1. Then in Section 5.2, we show that the parameters of data augmenta- tion minimizing the two distance terms coincides with the optimal parameters for downstream accuracy, which in turn verifies the effectiveness of Theorem 2.3.
E (a(z) min [aaTT) d' F
Σ
0 (5 - - 1())))11
+
Σ
E
Egc s (101. [0(
-11 =10)))113 1/2
1.EE(
= d8 2 1/2
Experimental Setup. We conduct numerical comparisons the CIFAR- and Tinylmagenet benchmark datasets. For conciseness of presentation, we delay the figures regard- ing Tinylmagenet to Appendix C. We follow the experimen- tal settings of SimCLR (Chen et al., 2020a). Specifically, we use ResNet- 18 as the backbone and a 2-layer MLP as the projection head. We set the batch size as 1024 and use 1000 epochs for training representations. We use the SGD optimizer with the learning rate 0.5 decayed at the 700-th, 800-th, and 900-th epochs with weight decay 0.1. We run all experiments on an NVIDIA GeForce RTX 3090 24GB GPU.
0
(23)
RE(3)
where the equality holds by taking 1 = مs pared with (20), the combination of color distortion further reduces the minimum same-class different-image distance by half. Similarly, when the pixels in a()) have more than one semantic labels, we have
p /5 Com-
En(x) min [[a(T) a' dz())
Egg 6 (5/,2- (((0)²] 1/2
Σ
E
The data augmentations we use are random resized crop, random horizontal flip, random color jitter, and random grayscale. The default crop size [0.2, 1.0), the default
Σ
E
(2(0)
5.6 5.t p
j2
1/2
7

---

An Augmentation-AAare Theory for Self-Supervised Contrastive Learning
flip probability is 0.5, the default color probability is 0.8, and the default gray probability is 0.2. evaluate the self- supervised learned representation through linear probing, i.e, we train linear classifier on top of the encoder for 100 epochs and report its test accuracy.
Then for each class, we calculate the minimum distances between same-class (different) images and the maximum distances between the two augmentations of the same image in the embedding space with training epoch from I to 1000. We report the average maximum and minimum distances over all classes on CIFAR- 100 in Figures and 4, and those on Tiny Imagenettt in Figures and 9. Note that for better visualization, we plot the moving average of the distance curves with window=100 epochs.
5.1. Verification of the Trade-off' between Two Distances
5.1.1. PEXEL-LEVEL VERIFICATION
We first conduct pixel-level verifications. Specifically, under certain augmentation parameters, for n original input im- ages, we first create 2n random augmented views. Note that to study the effect of a certain type of data augmentation, we vary its parameters (range of crop size and probability of color jitter) and set the default parameters for other types of augmentations. Then for each class, we calculate the minimum pixel-level distances between same-class (differ- ent) images and the maximum pixel-Ievel distances between the two augmentations of the same image. We report the average maximum and minimum distances over all classes on CIFAR-100 and Tinylmagenet in Figures 2 and 7.
MezSamelmageDD
MasSamelnagstis
cropsite 2.020044
size C 20000000
prob-0
crop_sits 2.02
prob-0
crop_size 2102.100
prob-0
20
60
041
spach
(a) Various crop size.
(b) Various color probability.
Figure 3. Representation-levee maximum distance between same- class different-imann -mage augmentations on CIFAR-I00.
MinsameClasiDis
MisSamedassDii
crop (.2...44
pro--
crop.sae (9.0..6)
prbb-i.4
emp_
prsb-0.6 0.6
Brrissm Chsse
cmp sum C (.2.1.0.)
prbb-0
MaxSumdmapeBdd VerrsmsCisaaat
MaxSameinng:0s: MintsameCaanDiee
10.
(02341
1023
6.1
color prob
26
(a) Various crop size.
(b) Various color probability.
(a) Various crop size.
(b) Various color probability.
Figure 4. Representation-levt minimum distance between differ- ent same-image data augmentations CIFAR-100.
Figure 2. Pixel-level maximum distance between same-class different-image augmentations and minimum distance between same-image data augmentations on CIFAR-100.
From Figures 3, 4, 8, and 9, we observe that through training, both distance values become smaller. Besides, at the begin- ning of the training stage, the rank of the representation-lewe distances w.r.t. augmentation parameters coincides with that of the pixel level, i.e., as the augmentation strength increases (smaller range of crop size and higher probability of color jitter), the maximum distance between augmentations of the same image increases, whereas the minimum distance between same-class different images decreases. Moreover, during training, this trend maintains till convergence.
In Figures 2 and 7, we show that as the augmentation strength increases (smaller range of crop size and higher probability of color jitter), the maximum distance between augmentations of the same image increases, whereas the minimum distance between same-class different images de- creases. According to the theoretical discussions in Section 4. smaller crops reduce the minimum same-class distance by avoiding intersections with the semantic boundaries, and color distortion further reduces the distance for crops with pixels sharing the same semantic label. Moreover, smaller crops increase the maximum same-image distance by creat- ing views with oon-overlapping semantic labels, and color distortion further increases it by enhancing the bias term.
5.2. Verification of Optimal Parameter
We run experiments with various augmentation parameters including the range of random crop size and the probability of random color jitter on the CIFAR-100 dataset. We report the sum of the two distance terms against training epochs in Figure 5. The curves smoothed by taking the moving average over 100 epochs. Besides, in Figure 6, we show the linear probing accuracy of the unsupervised contrastive learning representations trained with various augmentation parameters. The results on Tinylmagenet are shown in Figures 10 and 11.
5.1.2. REPRESSNTATION-LEVEE VERIFICATION
We also conduct empirical verification by calculating the distances in the embedding space. Specifically, we train SimCLR models with various parameters of data augmenta- tion (range of crop size and probability of color jitter) and set the default parameters for other types of augmentations.
8

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
sts
sum
specifically highlighted here.
crop. (1t.NaxxG00.... 2.0
prob-02
ors__tee 2.
prob-0.
pr3b-0..6
pr3b-0..
References
Aberdam, A., Litman, R., Tsiper, S., Anschel, O., Slossberg. R., Mazor, S., Manmatha, R., and Perona, P. Sequence- to-sequence contrastive learning for text recognition. In CVPR, 2021.
(a) Various crop size.
(b) Various color probability.
Figure 5. Sum of the two distance terms under various data aug- mentations in the embedding space CIFAR-100.
Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N. A theoretical analysis of contrastive unsupervised representation learning. In ICMI,, 2019.
Ash, J., Goel, S., Krishnamurthy, A., and Misra, D. Investi- gating the role of negatives in contrastive representation learning. In AISTATS, 2022.
K2244
19206
02
Bao, H., Nagano, Y., and Nozawa, K. On the surrogate gap between contrastive and supervised losses. In ICML., 2022.
(a) Various crop size.
(b) Various color probability.
Figure 6. Linear probing accuracy under different data augmenta- tion parameters CIFAR-100.
Chen, T., Kornblith, S., Norouzi, M., and Hinton, simple framework for contrastive learning of visual rep- resentations. In ICML, 2020a.
According to Figures 5, 6, 10, and 11, we observe that the optimal augmentation parameter with the smallest distance sum also leads to the highest downstream accuracy. This verifies Theorem 2.3, which indicates that the downstream supervised risk is guaranteed by the sum of the maximum distance between same-class different-image augmentations and the minimum distance between different same-image data augmentations in the embedding space.
Chen, X. and He, K. Exploring simple siamese representa- tion learning. In CVPR, 2021.
Chen, X., Fan, H., Girshick, R., and He, K. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003.04297 2020b.
Chen, X., Xie, S., and He, K. An empirical study of train- ing self-supervised vision transformers. arXiv preprint arXiv: 20t:::200402057., 2021.
6. Conclusion
In this paper, by proposing an augmentation-awwin -waaee error bound, we establish that the supervised risk is only in- fluenced by the unsupervised risk but also explicitly shaped by a trade-off induced by data augmentation. Under novel semantic label assumption, we further analyze how specific augmentation methods impact this bound. Moreover, we em- pirically verify the theoretical conclusion on the trade-offs of data augmentation. We believe our study lays a founda- tion for further theoretically exploring data augmentation techniques in contrastive learning.
Cui, J., Huang, W., Wang, Y., and Wang, Y. Rethinking weak supervision in helping contrastive learning. In ICML,, 2023.
Grill, J.-B., Strub, F., Altché, F., Tallec, C., Richemond, P., Buchatskaya, E., Doersch, C., Avila Pires, B., Guo, Z., Gheshlaghi Azar, M., et al. Bootstrap your own latent-a new approach self-supervised learning. NeurlPS, 2020.
HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T. Provable guarantees for self-supervised deep learning with spectral contrastive loss. In NeurIPS, 2021.
Acknowledgements
Yisen Wang was supported by National Key R&D Program of China (2022ZD1100300), National Natural Science Foun- dation of China (92370129, 62376010), and Beijing Nova Program (20230484344, 2024044442).
He. K. Fan, H., Wu, Y., Xie, S., and Girshick, R. Mo- mentum contrast for unsupervised visual representation learning, In CVPR, 2020.
Hu, T., Liu, Z., Zhou, F. Wang, W., and Huang, W. Your contrastive learning is secretly doing stochastic neighbor embedding. In ICLR, 2023.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be
Huang, W., Yi, M., Zhao, X., and Jiang, Z. Towards the generalization contrastive sulf-supe learning. In ICLR, 2023.

---

An Augmentation-AAare Theory for Self-Supervised Contrastive Learning
Khaertdinov, B., Ghaleb, E., and Asteriadis, S. Contrastive self-supervised learning for sensor-based human activity recognition. In IJCB, 2021.
Wang, Y., Zhang, Q., Guo, Y., and Wang, Y. Non-negative contrastive learning. In ICLR, 2024h.
Wu, J., Chen, J., Wu, J., Shi, W., Wang. X., and He, X. Understanding contrastive learning via distributionally robust optimization. NeurIPS, 2024.
Ko, C.-Y., Mohapatra, J., Liu, S., Chen, P.-Y., Daniel, L., and Weng, L. Revisiting contrastive learning through the lens of neighborhood component analysis: an integrated framework. In ICML,, 2022.
Wu, M., Zhuang, C., Mosse, M., Yamins, D., and Goodman, N. On mutual information in contrastive learning for visual representations. arXiv preprint arXiv:2005. 13149, 2020.
Koenderink, J. The structure of images. Biological cyber- netics, 5065):363-370, 1984.
Lee, S., Eun, H., Moon, J., Choi, S., Kim, Y., Jung, C.,, and Kim, Learning to discriminate information for online action detection: Analysis and application. IEEE Trans- actions Pattern Analysis and Machine Intelligence, 45 (5):5918-55) 5934, 2022.
Zbontar, J., Jing, L., Misra, I., LeCun, Y., and Deny, S. Barlow twins: Self-supervised learning via redundancy reduction. ICML, 2021.
Zhang, Q., Wang, Y., and Wang, Y. On the generalization of multi-modal contrastive learning. In ICML, 2023a.
Lei, Y., Yang. T., Ying. Y., and Zhou, D.-X. Generalization analysis for contrastive representation learning. In ICML, 2023.
Zhang, Q. Wang, Y., and Wang. Y. Identifiable contrastive learning with automatic feature importance discovery. In NeurIPS, 2023b.
Nozawa, and Sato, I. Understanding negative samples in instance discriminative self-supervised representation learning. In NeurlPS, 2021.
Zhuo, Z., Wang, Y., Ma, J., and Wang, Towards a unified theoretical understanding of non-contrastive learning via rank differential mechanism. In ICLR, 2023.
Ouyang, 7.,, Hu, K., Zhang, Q., Wang, Y., and Wang, Y. Projection head secretly an information bottleneck. In ICLR, 2025.
Zimmermann. R. S., Sharma, Y., Schneider, S., Bethge, M., and Brendel, W. Contrastive learning inverts the data generating process. In ICML, 2021.
Radford, A., Kim, W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. In ICML, 2021.
Shen, K., Jones, R. M., Kumar, A., Xie, M., HaoChen, Z., Ma. T., and Liang, P. Connect, not collapse: Ex- plaining contrastive learning for unsupervised domain adaptation. In ICML, 2022.
Tian, Y., Sun, C., Poole, B., Krishnan, D., Schmid, C., and Isola, P. What makes for good views for contrastive learning? NeurlPS, 2020.
Wang, T. and Isola, Understanding contrastive represen- tation learning through alignment and uniformity on the hypersphere. In ICML., 2020.
Wang. Y., Zhang, Q., Wang, Y., Yang, J., and Lin, Chaos is a ladder: new theoretical understanding of con- trastive learning via augmentation overlap. In ICLR, 2021.
Wang, Y.. Zhang, Q. Du, T., Yang, J., Lin, Z., and Wang, Y. message passing perspective on learning dynamics of contrastive learning. In ICLR, 2023.
Wang, Y., Zhang, J., and Wang. Y. Do generated data always help contrastive learning? ICLR, 2024a.
10

---

An Augmentation-AAare Theory for Self-Supervised Contrastive Learning
A. Related Works
A.1. Self-Suuee Contrastive Learning
Self-supervised contrastive learning (Chen et al., 2020a;b; He et al., 2020; Chen et al., 2021) aims to train an encoder that maps different augmentations of the same input to similar feature representations, while ensuring that augmentations from distinct inputs result in distinct features. Once the encoder pre-trained, it can be fine-tuned on a specific downstream task. Contrastive learning methods can be broadly divided into two categories based on their use of negative samples. The first category (Chen et al., 2020a;b; He et al., 2020) involves learning the encoder by aligning anchor point with its augmented versions (positive samples) while explicitly pushing apart other samples (negative samples). The second category does not rely on negative samples and often incorporates additional components, such as projectors (Grill et al., 2020), stop-gradient techniques (Chen & He, 2021), or high-dimensional embeddings (Zbontar et al., 2021). Despite this, the first category remains the dominant approach in self-supervised contrastive learning and has been applied to a wide range of domains (Khaertdinov et al., 2021: Aberdam al., 2021; Lee et al., 2022). This paper primarily analyzes and discusses the first category of contrastive learning methods, which depend on both positive and negative samples.
A.2. Theory of Contrastive Learning
The early studies of theoretical aspects of contrastive learning manage to link contrastive learning to the supervised downstream classification. Arora et al. (2019) first proposed the CURL framework where the positive samples generated from the same latent class. They proved that the downstream supervised risk of a mean classifier can be bounded by the unsupervised contrastive risk and a class collision term. Under the CURL framework, succeeding studies further extended this bound and incorporated the effect of negative samples (Ash et al., 2022: Bao et al., 2022). Moreover, Lei et al. (2023) improved the results of Arora et al. (2019) by deriving a tighter generalization bound. However, the CURL framework has long been criticized as having unrealistic generation process of positive samples (Wang et al., 2021). Nozawa & Sato (2021) formulated the positive samples from the perspective of data augmentations, whereas they considered the corresponding term relative constant without conducting further analysis.
Later on, HaoChen et al. (2021) motivated from the unsupervised nature of contrastive learning by proposing the concept of the augmentation graph, where the vertices are all augmented images and the edge weights representing the probability of two augmented views originating from the same original image. They borrowed the mathematical tools from spectral clustering to build generalization guarantees for their proposed spectral contrastive learning. The theoretical framework was later extended to contrastive learning for unsupervised domain adaption (Shen et al., 2022), multi-modal learning (Zhang et al., 2023a), and weakly supervised learning (Cui et al., 2023). In a similar vein, Wang et al. (2021) propose the idea of augmentation overlap to explain the alignment of positive samples. However, these modelings of data augmentation measure the case where two original images sharing the same view, whereas this is empirically hard to realize, especially with only two views used in contrastive learning instead of multiple ones.
Besides, contrastive learning is also interpreted through various other theoretical frameworks in unsupervised learning. For example, Wang & Isola (2020) explained the contrastive learning through aligmment of positive samples and uniformity of negative samples. Zimmermann et al. (2021) showed that training with InfoNCE inverts the data generating process through establishing a theoretical connection between InfoNCE and nonlinear independent component analysis (ICA). Ko al. (2022) built the relationship between contrastive learning and neighborhood component analysis (NCA) and developed new contrastive losses. Hu et al. (2023) interpreted contrastive learning type of stochastic neighbor embedding (SNE) methods. Wang et al. (2023) showed the learning dynamics of contrastive learning corresponds to a specific message passing scheme on the corresponding augmentation graph. Wu et al. (2024) explained the tolerance of contrastive learning towards sampling bias via the perspective of distributionally robust optimization (DRO). Nonetheless, the role of data augmentation is still under-exploited in the existing theoretical frameworks, especially without mathematically analyzing specific data augmentation methods.
B. Proofs
B.1. Proof of Error Decomposition
Proof of Theorem 2.5. According to the definition, we have
un (f) Ro, Eamposrrpp Ea,a' for bej C(a(F), a (7), as ff

---

An Augmentation--Aarr Theory for Self-Supervised Contrastive Learning
C
E po
B
P(c = =i)).. ...P(c = ig) Enswpi B Bol (5)
=1
fx=1
Eepep Bg
Σ
P(c i.))..P((cc. ix)
#x
ix
Bax Ba (an wan.aaaaeeeee heln ((a(() a (2), (it)
E. Bo
Σ E... Σ
P(e1 = in) ... ..((cK ik) ke bae (a0
1x
K
+ E,
Hemp E
Σ Σ.E Σ
P(a = P(cj =c- .((cK = iix
life
ix
Bgymp Bea Kef laxhoenn f(a(z), (
+ E2 Smpp
En
P(c1 = -c)... .((c,=i))) = iz) i,(k..,((cK- c)
-Bserpen k kyjne, fer Re f(a(E), (z) (z))
+ Ba En ((1 = c) ... P(ck =c) ke Bed JuEIx ((a(T), ('),,, (z))
-E,Ba-p Es
Σ
Σ
P(e1 = = ... .(.P( = ik) BelK (i) (bt
ix
K Σ ΣΣN
+ E. Caraaeee En Σ
P(e ii) P(cj P(cj= cc) ..P((K- = -ik
11f
85417
ixpo-=1
Eg, Beerpe, A Ea' Ea (antreix
+ Eepep En Σ
P(c c)...P((.. =i)) P(CK - =)
k
k4t Ex' Loxhee (x)):
+ Exp. Bup. E. pc) c) P(ck =) Eeexpe Eet (oe Ba haj (()) (Tx);))
(26)
Note that the loss ((a(T), a' (t), an (Tx); f) is symmetric w.r.t negative samples. Specifically, denoting (ii..... ix} as rearrangement of [K] = {l...., K}, we have
C(a(T), an (ix);:) = log 1 + Σ exp ( (- (((((() ((a
k=1
ix
=log 11
exp (( ((a)((()
(27)
Therefore, for & E [K], given i..... is. by denoting
Th rk(1i....,, 46) = Ezinpi, ... Ezerpy Exp Eat fauheexx L(a(F), d' d'()), a0),(((x):1
Exmp,
(28)
and
Pa ( (x) == = P(3(j),....... jrc J. such that Cj. = i....., Cja = ig. and Cj. cx
(29)
where is a rearrangement of [K] = {1,..., .....,K), K). we have
Rf) EzEp. E.
Σ
pk (f1..... (x)rx (f.....,4 Σ
ix t0
12

---

An Augmentation-Awart Theory for Self-Supervised Contrastive Learning
R.
Σ
Σ
Σ
Σ
pk (k..
16 a. iK) (1,, - o 23 1....... ix)
$1#C
$3-1#c
6y+1
#x
+ E.Er prpp Ea Σ
((((t)ri(1s) + P. Az3
BoPoTo-
(30)
Corollary B.1 (Error decomposition of Ruup), We have
(J)
EeExrpe Σ ...
Σ
(
#1
in #o
E.
Brope
Em((i)) sup (1n) + B Pep. sup
(31)
where Tk sup (ii,...,,.)) it) == log [ + [KK -k) Σt 2m=1 exp (- Ex' Bam Pmmp [(3) f(am)))))
Proof of Corollary B.1. Because log (1+ (1+ E exp (- f(z) (No Hex)) is symmetric w.r.t. the negative samples, we follow the proof Theorem 2.5, replace ru(ii,...,.u ix) with sup (i....., it), , and finish the proof.
B.2. Proof the Error Bound without Additional Assumption
Proof of Theorem 2.6. By Jensen's inequality and the convexity of log-sum-exy sum-exp, we have
(i, (ix)
Esirei Bxarpi Ez, Ex.....xppp. Bay Aas (z))
K
=Eaiop ... -.BNNp Bee Bx Ea hanher log (1+
Σ exp (= f(ax())))))
log (1+ Σ exp (- Bairpi Bxaapi Exs i Ra (a())) (s(((())
(ax(t))))))
llog (1+ Σ exp (- Eim mpm Ed aa (a(l)) ((mmm)))))
m=1
exp ( Es, up, Ea an
fam (Zm (Fm)
(32)
m==+1
We note that the negative samples break into two groups: Imms 's sharing the same class with F. and Z,m 's having different classes with F. For the same-class terms, given a, F. Zm. and f. we take a* as the augmentation such that
a' = arg min ([((()()) (a((x)))
(33)
and then we have
Ex up En am f(a(F) (f(( - -(am f(am (im)))
Eemrup B.y a (a(()) ([(a)))((((((E)) 1(a" ((aa((m)) + S(a" (Fm)) f(am (Tm))
Eea up. E. (((E))
Be. f(a(t)) ( (f(a"(()) - (Tm)))
S Re Ent (1 (7)) f(a'((m)))) ))1l Esmap. Bam (Tm)) (Tm)))
13

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
S Bemeup Eat min (I) - (f(aa(mm) Bx max d',0"
((a l( (Fm())
(34)
where the first inequality holds because ||O||=
On the other hand, for the different-class terms, we have
Bg..ppin Bot am I (a(a)) ( ((mm((
= -e''epe pm. Pm a" (((())
- (x')) + f(d"(')) - f(mm(()))
= Ex'rp. aa f((()) (((d())((((( f + Eg' Bam-pin f(())) - ((mm(mm)) (35)
Following (34), the first term of (35) is bounded by
Egginpe Fat .a l() [(d())) ((a"(')))
S Bp Eg min Il (z)) - ((d"((')) Bz'npe max of a'
-
(36)
Besides, we decompose the second term of (35) as follows.
Eg Pmm Ea am fa(()) [(((3) ( (mm())))
Ex Bi
p Bim~pi f() f(ām))
+ Eg upe BA,,, Phm B a. [[(a(z)) [(t)) ([(a" ((a))(((((((()))))) - [um (Tm))]
+ Ex' Ex''pe up E. (1) [(a Ex mm Bon f()) (((T)][((e))) [f(ām] (fmn)-f(ann) f(am (2m)))
S Eg'np. Bs,,. mm (i) - + 2 f(((z)) - f(3)]l
+ RE E.
(z') + F mm R.,,, 11
(Tm))]
= Eve Pe Ex ~p (()) + 21| (a (7)) - f(3)]
+ Ep de E.d 15 ( - ((T(('))) + Eg Ppm Eam (TTT(Tm)) f(am (3m)))
& By B.... ~p (f('))
[a())) - f())]
+ Ex'r max
If (z') - f(a(('))) Ex Pim
max a'
(ammm)) f(d((am))
(37)
where the last inequality holds if Id(.) E {a: a ~ A}. Combining (36) and (37), we have the different-class terms bounded by
Ex Emm-pi Ex' am (((d) (Zm))
< Egin, Eng min a"
((]( + Egiop max ((((a"
a'
+ Exinp Er,. P (()) + Ee. Eon~pin
(a))()()) - f(i)]
+ Ep' max o' ,''""
max [f(a (Zm)) - f(d (#m))
pim
a'
= -Eripe Ba Pmm. f(=) - (((m) + Exr Ea min [l)(d())) - (x))ll
+ +1]f((((F)) f())| + 2g max a'
- f(a(('))) Ez,, Cmpp d'
max II5 (Tm)) - ((l (38)
Then plugging (34) and (38) into (32), we have
Th re(ii....,25! ix)
2 log (1+] Σ exp ( [Ep'pp Ey Sm. (()) [(ām)] + Ber Eg min ([(()())) - ((a(('))
+ +2)f(a(z)) - f())]
2E 2 max (f(a" f(a((*')) + Ez a'.a"
max || f (Zm)) -f
d',a"
+ (K- - k)) exp (- E p. E. min [()( - (T..( + Eampp, max (a) (c'((..)))l)
14

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
2 log (1+] Σ
exp ( Ex Ee mp (( - exp (- L-EE''rp
Ex min [I](d -
m=1
+ +2])(a(ā)) f())) + 2 ~ max (l - (((())) +Eg +B
max ff f(a'(am)))l))
+ +K- - exp ( Bap Be min - Be'ape
max aa
[I((a()²)) - -
= =log (1 (1+ [KK - k) + Σ exp ( - Bx Re ~ (()) [5(#') (5(=)) - [(m))) exp - (211/(((()) s())l
m=1
+ Np max [Ia((')))) ((d''''))))))))) + E Bm Ppm
a',a" [I( s(a' (dd(#=))lll)
max
.exp ( - Exg Be min [f((a - ((a"('')) Ez'op,
max aa.a"
- f(a'=)))((((('))))))
2 log (1 [[K - k)) +
exp (- -- Ex
Ei Pm Dam f() (f(#') - f fZm))) exp (xp((12lif((a))
m=1
+B max || (d'('' + Es
max [I (am()))) s(a' (TT )[I]]
d' a
- -E upp Eg' min [lf(a'())) - f(a" (f'"((')) Es a"
max [f(a)())) f()((
k
2og (1 [KK- - -k)+
+
exp - (p
Ezn ~ f()) (f(=') - -f f(m)))))
m=1
- -(2]f(a(ET) f(])]| + Ex max [f(aa())) (('((z')) Exmeptn, a'
max (lf((a f(a'(#m)) (Il
d'
=log (1+ [[K- - k) + exp ex (3F) [5(#') - ((m)))))
Ex Exm -p
-(21)(a(F))- f())| + 28 up max
f(a Enn, ppm max (5(a S(al (Tm)))
+ EB E. min ((a fx)'l
rk (i........ ix) (a(()) f(3)] + 2' max ((( o'
+ Eg m Pim max [I((aa(mm)) - f(a((Tm) + Ex Ea min
min
(39)
Proof of Theorem 2.7. Combining Theorems 2.5 and 2.6, we have
R. R. = E.E. E.
Σ ... Σ
(k......,, (i. ix)
$1
ix
E, E pappe
En
Σ ix
Pk (4 ......... -3- ...))r - (bi.....
i5-1, (8-1.......11. (3t..))).)))) ...kk..k)
+ E.Ep E. Σ ((gt))r((()) + EEE ExPoTo
ExExp
Σ
Σ
Pk (ik)., ((......)
iif
ix fc
+ E.E. EgNpe
Σ
Σ.E
Σ
Σ
24g111 ... ......xx))))) ix sup
...ik)
17-170
1117
ix
15

---

An Augmentation-Awart Theory for Self-Supervised Contrastive Learning
Re PopPe
(i(1))r'''(, (1,) + P.R um
Epp En (2)l(((()) f())1l 2 max [l((aa))))) f(d((z))) + Ex Eg min
Ee
Σ
Σ Σ...
Σ P(c, ii).... = i/ ig) = =c) ... Plck c)
K=
ULundR (Ere((K] i1zt
iufe
Es pm
max (f((a f(d
(40)
a
Note that
K
Eg
E
E...
Σ P(cy = i1)... P(cse = ip)e( = =c)...P(ccy = c)
K=
Usondr (Ere([K]) i17t
max Ri mm (l (Tm)) a',a"
K
Eg
Σ
Σ
E
P(ej.. = im)) max pp (fm f(al (Tm()
o'aa"
k=0 (iinn (Ere([(]) km
E... P(ch P(....
= is)P(cian = =c)... .)ec. = c)
life 12#C
Eg max Ez B ((ll((((m))) - (dm() of aa
Σ Σ
P(en xc) ... .(g). + c)P(cee+1 = ..)..P(cx== =c)
UK ((e((
< B, Be max B. mp (a(m)))))) [(d (Tm)l) aa"
Ee oo a'
max [I((a)()))) f(a((t'))
(41)
Then by Corollary B.1, we have
R Rm (f) 2 RT (f) - E,Exvp, Es E. min - f(a" f(a"(')) Ex max =
" E. P(om # c) E.
d'
- -(()) + Ex' max max -
a'
max (f(a f(ad))))-aa3" - f(a()')) E.E.p E.g Fe
d'a""
- =R"P(() ExExp E Ex Ey minmmil//1 [d)( f(a" (((aa())) (2)))| ExEx max ()) f(d(()))
-IIE,P(c' & c) Ba E. (a())) f()) E. E. max [If(aa f(dd(()))((((()))
E.. Ex max (faa - f(a'(F)))l a'
2 R)) - Ee
B. min [[(()))) - ((d(('))) - JE,Ex-n max ([(())) (x)()) (42)
a,a'
Proof of Theorem 2.1. By combining Theorem 2.7 and Lemma 2.8, we finish the proof.
B.3. Proof of the Improved Bound
Theorem B.2. Under Assumption 2.2. we have
(a(ii,.... rk) 2 log (1 Σ
exp (- (-E Evroge Bemrppn, (a(F)) (((()) [(Tm))) + (K - 13)
mm1
16

---

An Augmentation-Awarc Theory for Self-Supervised Contrastive Learning
- -pe''pe Eg min (z) [(a" (*))) + Ex'npe max (z)( ((d
(43)
a'
Proof of Theorem B.2. Under Assumption 2.2, have
Eg'-p. Exmppen En" (((()) I(dd(zz)) - ((am((m)) = Exm f(a(t)) [f(x') f(ām)).
(44)
Then by (32), (34), and (35), we have
(k(1,....,, 2 log 1+
exp (
Be aa, I [a(()) (f((()) ((pp)))((mmmm ((m((mm)))
1=1
K
Σ exp (- f((()))
- (Zm)l)m))))
m=
k 2 log 1+
Σ m=1
exp -EEE Ban -p ((a [ f(mm)
+ Eg Egi Bar min [|
Ex max |n -
+ (K - k) exp
[B En min f((a Ev'rp a'.a"
max f(()
k
= loog 1 +
exp Egin Bz Am f((z)) f(z,))) (K (K-k)) -h]
m=1
exp
[Bx' En min f(aa + E max f a'
k
2 log 1 + Σ exp - Bur Ex Pinm [a(())) (s(T)) ((Tm))) + (K - -k)
m=1
[E ~pe E. min [sdd [(a Eg p. a'
(z(a - s(a' (x))))))
(45)
Proof of Theorem B.2. Combining Theorem 2.5, Corollary B.1, and Theorem B.2, we finish the conclusion.
B.4. Proof the Generalization Bound
Proof of Theorem 2.4. By combining Theorem 2.1 and Theorem 4.6 in Lei et al. (2023) with G2 for the logistic loss in (2), we get the assertion.
17

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
C. Experimental Results of Tinylmagenet
15.5
MinSame Dis
MaxSamelmi ImageDis
121
15.0
Min MinSam Casss
MaxSamelmagee
136
MaxSamelmageDist
10.0
120
MaxSamelmageDist MinSameClassDist
14.5
MinSameClassDist
9.5
119
14.0
132
9.0
Mins
117
1300
128
[0.08.0.4]
[0.08.0.6]
10.08.0.0]
[0.08.1.0]
0.2
0.6
color prob
color prob
(a) Various crop size.
(b) Various color probability,
Figure 7. Pixel-level maximum distance between same-class different-image augmentations and minimum distance between same-image data augmentations on Tinylmagenet.
MaxSamelmageDist
MaxSamelmageDist
crop_size [0.08,,0.4]
0.70
prob=0.2
crop_size [0.08.0.6]
prob=0.4
0.90
crop_size E [0,08,0.8]
0.61
pro
distance
0.25
crop_size [0.08,1.0]
prob=0.8
0.60
0.55
0.7
0.50
200
800
epoch
epoch
(a) Various crop size.
(b) Various color probability.
Figure 8. Representation-llvel maximum distance between samc-class diffcrent-image augmentations on Tiny
MinSameClassDist
MinSameClassDist
0.84
crop_size E (0.08,0.4)
0.90
prob=0.2
crop size (0.08,0.6]
prob=0.4 4
crop size E [0,08,0.8)
prob=0.6
distance
0.80
crop_size [0.08,1.0]
0.86
prob=0.8
0.2
0.7
0.0
203
800
epach
epoch
(a) Various crop size.
(b) Various color probability.
Figure 9, Representation-levee minimum distance between different samc-image data augmentations on Tinylmagenet.
18

---

An Augmentation-Aware Theory for Self-Supervised Contrastive Learning
SumOfDists
SumOfDists
175
166
crop_size E [0.08,0.4]
prob 0.2
crop_size (0.08.0.6]
135
1.45
crop_size size E [0.08,0.8]
distance
prob=0.6
crop_ size [0.08.1.0]
prob-0-
1.40
1.45
1.55
1.40
1.50
130
202
200
100
epach
epoch
(a) Various crop size.
(b) Various color probability.
Figure 10. Sum of the two distance terms under various data augmentations in the embedding space on Tiny finylmagenet.
52.6
492
49.
$1.0
452
(0.08.044
[0.06.0.6]
[0.00.0.0]
[0.06.1.0]
0.4
0.6
crap size
color prob
Various crop size.
(b) Various color probability.
Figure 11. Linear probing accuracy under different data augmentation parameters on Tinylmagenet.
19


Reviews:
[{"review_id": "rRVQL7u7ex", "reviewer": "Reviewer_Xxrg", "summary": "This paper theoretically examines the role of data augmentation in contrastive learning. It demonstrates that supervised risk is bounded not only by unsupervised risk but also by a trade-off introduced by data augmentation. The analysis is further extended using Lipschitz continuity, providing insights into how changes in input data or augmentations affect the model's output and error bounds. Experimental results validate the theoretical findings, reinforcing the impact of augmentation on contrastive learning performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We express our sincere gratitude to Reviewer Xxrg for appreciating our practical theoretical assumptions and novel theoretical results. We address your concerns below.\n\n---\n\n**Q1.** Empirical verification of Assumption 2.2.\n\n**A1.** For each input image in the CIFAR100 dataset, we generate 100 different random augmentations, and plot the tsne visualizations of the random augmentated views, the mean of the augmented views, and the original input sample in the embedding space. We show the tsne plots of 4 randomly selected samples in https://imgur.com/a/NadpBSl. We see that the mean of augmented views lie near the embedding of the original input sample, which verifies Assumption 2.2. Besides, we also measure the $l$-2 distance between the mean of augmentations and the original sample in the embedding space. We show that on CIFAR100, the average distance is 0.083, which is small enough considering that the embeddings are normalized to have unit l-2 norm, indicating that the mean of augmented embeddings $\\mathbb{E}_a f(a(\\bar{x}))$ is close enough to input embedding $f(\\bar{x})$.\n\n---\n\n**Q2.** The experiments are conducted only on small-scale datasets such as CIFAR-10/100. Since image resolution and dataset complexity could influence the theoretical results, an evaluation of larger, high-resolution datasets would provide a more comprehensive validation.\n\n**A2.** Following your advice, we conduct additional verification experiments on Imagenet100, which contains 224*224 high resolution images from 100 classes. Due to time limitation, we run experiments with ResNet-18 with batchsize 64 for 50 epochs on 2 24G RTX 3090 GPUs. (The other settings follow those of TinyImagenet in our submitted paper.) The pixel-level verifications are shown in https://imgur.com/a/UcVPXwS, and the representation-level verification w.r.t. crop size is shown in https://imgur.com/a/jl00TVn, where the results conincides with that in Sections 4.1.1 and 4.1.2, i.e., as the augmentation strength increases, the max same-image different-augmentation distance increases and the min same-class different-image distance decreases. Besides, in the figure https://imgur.com/a/wPs9WOO, we verify that the optimal augmentation parameters with the smallest distance sum also leads to the highest downstream accuracy, which coincides with Section 4.2.\n\n---\n\n**Q3.** The study focuses exclusively on InfoNCE loss, which may limit the generalization of the theoretical findings.\n\n**A3.** On the one hand, as one of the mainstream contrastive losses, InfoNCE-based contrastive learning still achieves state-of-the-art performances e.g. SimCLR, MoCo, etc. The extensive applications of InfoNCE loss partly demonstrate the generalization of our theory. On the other hand, although our theoretical results focus on the InfoNCE loss, we strongly believe that our analysis can potentially be generalized to other contrastive losses, e.g. BYOL, BarlowTwins, etc. Specifically, our analysis theoretically explains the effect of data augmentation to contrastive learning based only on the data generation procedure described in Section 2.1, with mild (Theorem 2.3) or even no further assumptions required (Theorem 2.1) and regardless of the network architectures. As long as a contrastive learning method selects positive/negative samples using random data augmentations, we can adapt the two trade-off distance terms to any error bound revealing the relationship between contrastive and downstream risks. \n\n---\n\n**Q4.** Page 1, top right. The statement “we usually use only two views in training instead of using multiple ones.” may be misleading for readers unfamiliar with SSL. While many traditional contrastive learning methods use two views, several recent approaches, such as MMCR and DINO, leverage multiple views.\n\n**A4.** We will replace this statement with \"we usually use only two views in training instead of using multiple ones in popular methods such as SimCLR and MoCo\".\n\n---\n\nThanks for your insightful and constructive comments. We sincerely hope you can reconsider the recommendation score if our explanations and additional experiments solves your concerns. We also welcome further questions and discussions.", "claims_and_evidence": "Claims made in the submission are supported by clear evidence.", "methods_and_evaluation_criteria": "There are no new methods proposed. Evaluation criteria make sense for the problem of the theoretical analysis.", "theoretical_claims": "I believe the analysis in Sections 2 and 3 is correct. However, Assumption 2.2 could benefit from some empirical verification. The radius $R$ in Theorem 2.4 seems to be not formally introduced and explained.", "experimental_designs_or_analyses": "The experiments are sound for evaluating the theorems introduced.", "relation_to_broader_scientific_literature": "Contrastive learning is a key self-supervised learning approach with numerous real-world applications. Augmentation plays an integral role in contrastive learning, often determining the quality of learned representations. Gaining a theoretical understanding of augmentation's impact could have significant implications for the broader scientific literature, shaping future advancements in self-supervised learning and representation learning.", "essential_references_not_discussed": "Most papers are discussed.", "other_strengths_and_weaknesses": "Strength:\n1. This work extends previous theoretical analyses by making assumptions that may not fully align with real-world scenarios. This work does not assume that anchor and positive samples are conditionally independent or that two different real images share exactly the same augmented views. These assumptions, while useful for theoretical exploration, may not always hold in practical applications.\n2. The experimental results validate the new theoretical results. \n\nWeakness:\n1. The experiments are conducted only on small-scale datasets such as CIFAR-10/100. Since image resolution and dataset complexity could influence the theoretical results, an evaluation of larger, high-resolution datasets would provide a more comprehensive validation.\n2. The study focuses exclusively on InfoNCE loss, which may limit the generalization of the theoretical findings.", "other_comments_or_suggestions": "Page 1, top right: The statement “we usually use only two views in training instead of using multiple ones.” may be misleading for readers unfamiliar with  SSL. While many traditional contrastive learning methods use two views, several recent approaches, such as MMCR and DINO, leverage multiple views.", "questions_for_authors": "Please address the questions regarding the assumptions and evaluations, as these concerns could impact my assessment of the paper.", "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": "", "extra_scores": {}}, {"review_id": "0jT4WEObh3", "reviewer": "Reviewer_cGdD", "summary": "Self-supervised contrastive learning effectively extracts representations from unlabeled data. Despite its success prompting theoretical studies, the impact of specific data augmentation techniques is still under-explored. To address this, the authors proposed an augmentation-aware error bound for self-supervised contrastive learning, showing that the supervised risk is bounded not only by the unsupervised risk, but also explicitly by a trade-off induced by data augmentation. Furthermore, the authors discussed how certain augmentation methods affect the error bound.\n\n## Update after rebuttal\n\nAfter reviewing the author's rebuttal and the reviews from another reviewer, I will keep my current weak accept rating.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We express our sincere gratitude to Reviewer cGdD for appreciating the soundness of our theoretical formulations and results. We address your concerns below.\n\n---\n\n**Q1.** Organization of Section 2.\n\n**A1.** As suggested, we will make the discussions in Section 2.3 an independent section following Section 2 in our next version and also add a roadmap in the introductory section to enhance readability.\n\n---\n\n**Q2.** Lack of discussion regarding the contributions and comparisons with SOTA.\n\n**A2.** The discussions of our contribution locate mainly in Section 2.3, where we compare our bound with previous theoretical works. Besides, we also conduct verification experiments in Section 4 to verify our new theoretical claims proposed in Sections 3.2 and 3.3. As the main contribution of this paper is to theoretically explain the role of data augmentation in self-supervised contrastive learning, the significance of the proposed error bound is not necessarily verified by ablations or experimental comparisons. Nonetheless, we could compare empirically the bound value with previous theoretical works. In detail, as shown in Figures 5 and 10, the sum of the two distance terms is around 1 (1.3 for TinyImagenet and 0.8 for CIFAR100) after 1000 epoch training, whereas we additionally measure the contrastive loss value to be around 42 (41.6 for TinyImagenet and 41.2 for CIFAR100). This indicates that compared with previous bounds, our bound relax the data generation assumption with the bound value increases less than 3% (1/42). See also **A6**.\n\n---\n\n**Q3.** Some experimental settings lack sufficient discussion and analysis in relation to the theoretical framework.\n\n**A3.** The experimental section 4.1 is specifically in relation to theoretical analysis in Section 3 verifying the trade-off between the two distance terms, and the experimental section 4.2 is in relation to the error bound of Theorem 2.3, where the optimal augmentation parameter leads to the minimum distance sum and also the highest downstream accuracy.\n\nTo further enhance the relation of experiments to the theoretical framework, we here present an additional experiment about the formulations of data augmentation strategies. This experiment verifies the theoretical analysis in Section 3.3 about the combination of random crop and color distortion. Specifically, we present the pixel-level distances between data augmentations using only random crops and that using random crops plus color jitter on CIFAR100. As shown in the figure https://imgur.com/a/aj3Xp4i, on top of random crop, color distortion further reduces the minimum same-class different-image distance and enhances the maximum same-image different-augmentation distance. \n\n---\n\n**Q4.** Missing punctuation.\n\n**A4.** We will fix the typo in our next version.\n\n---\n\n**Q5.** Do the authors analyze and discuss the impact of different augmentations and augmentation-aware error bounds in the two experimental settings?\n\n**A5.** Yes, in both settings, we show that stronger augmentations, e.g. smaller range of crop size and higher probability of color jitter, lead to larger maximum same-image different-augmentation distance and smaller same-class different-image distance, which coincides with the theoretical analysis in Sections 3.2 and 3.3. From the perspective of our error bound, there exists a trade-off between the two distance terms w.r.t. the strength of data augmentation, indicating the existance of the optimal augmentation parameters. Related discussions can be found in Section 4.1.1 2nd paragraph, Section 4.1.2 2nd paragraph, and Section 4.2 2nd paragraph.\n\n---\n\n**Q6.** How does the proposed approach compare against state-of-the-art papers, and can the authors highlight its main contributions across these different settings?\n\n**A6.** In fact, instead of proposing a new contrastive learning methods that competes against the state-of-the-art,, the aim of our error bound is to explain their working mechanisms. Our bound applies for any contrastive learnin methods as long as they use the InfoNCE loss function regardless of the backbones or other architectural techniques. It builds upon a more realistic data generation process described in Section 2.1 without relying on any further assumptions (Theorem 2.1). That is, compared with other theoretical papers deriving the error bound, our bound can easily adapt these previous bounds under our more realistic data generation, only with two additional trade-off distance terms added to these bounds. See also the third paragraph of Section 2.3 for more details.\n\n---\n\n**Q7.** The paper needs a detailed analysis of the experiments and discussions.\n\n**A7.** See **A2** and **A3**.\n\n---\n\nThanks for your insightful and constructive comments. Hope our explanations and additional experiments can address your concerns.", "claims_and_evidence": "The authors aim to formulate the problem and motivation using different scenarios:\n1. Directly establishing a relationship between unsupervised contrastive risk and supervised risks through statistical modeling.\n2. Relying on the assumption of an augmentation graph and borrowing mathematical tools from unsupervised spectral clustering.\n3. Exploring other explanatory works of contrastive learning from the perspective of feature geometry.\n\nWith these three scenarios, the authors attempt to formulate the problem, which remains under-explored. Thus, they propose an augmentation-aware theory for self-supervised contrastive learning, decomposing the unsupervised contrastive risk in relation to the number of negative samples sharing the same label as the anchor. Furthermore, they analyze specific types of data augmentation and discuss the existence of a trade-off between the two distance terms concerning the strength of data augmentation.", "methods_and_evaluation_criteria": "In Section Two, the authors introduce a mathematical formulation for unsupervised contrastive learning and downstream classification, accompanied by a detailed analysis of the proposed approach. Following this, an augmentation-aware error bound is presented, supported by intriguing mathematical theory. This section offers a compelling theoretical explanation of how the authors address the issue with clear formulations. However, the organization of Section Two is lacking. For instance, in the middle of the theoretical explanation, the authors introduce a discussion that feels disconnected from the main theoretical idea.\n\nThe authors design two types of experimental settings: pixel-level and representation-level, to validate the proposed approach. However, there is a lack of discussion regarding the contributions of the proposed method(in tense of ablation, comparison). In Section 2, the authors explain the main theoretical concepts with a strong promise of performance improvement. However, I cannot find a thorough discussion in these two experiment settings with different scenarios (impact of augmentation, augmentation-aware error bound). Furthermore, it is necessary to evaluate the proposed approach against state-of-the-art papers and to highlight its main contributions across different settings, as mentioned by the authors.", "theoretical_claims": "The authors provide a solid theoretical formulation of the proposed approach, clearly outlining how they intend to address the issues with precise mathematical formulations. However, the organization of the paper still needs some modifications. In certain sections, the authors introduce theoretical concepts alongside mathematical formulations, while simultaneously discussing experimental performance (Section 2.3). This structure can be confusing and may benefit from clearer separation.", "experimental_designs_or_analyses": "The experimental design needs reorganization and more discussion based on the theoretical formulation (augmentation-aware error bound, impact of different augmentation, some downstream tasks). As noted, some experimental settings lack sufficient discussion and analysis in relation to the theoretical framework. The experimental results should be presented with different augmentation strategies based on their formulations, the Augmentation-Aware Error Bound compared to other approaches (as discussed in Section 2.3). These aspects should be addressed more thoroughly, as they represent a significant weakness of the paper.", "relation_to_broader_scientific_literature": "Their formulation is very interesting, particularly in relation to contrastive and self-supervised learning, as it addresses the risks associated with different augmentation techniques. Furthermore, the approach is intriguing for utilizing unlabeled samples in downstream classification tasks.", "essential_references_not_discussed": "Some of the recent papers are discussed in the theoretical sections, but these discussed papers need to be addressed in the experimental section as well. It would be beneficial to compare their performance with the proposed approach and analyze how they affect performance in downstream tasks.", "other_strengths_and_weaknesses": "I found the theoretical aspects of the paper is good. The problem formulation, arguments, and claims about how the approach is addressed in their work are interesting. Furthermore, their mathematical formulation is somehow fine.\n\nHowever, there are some weaknesses in the paper, particularly in the organization of Section 2 and the lack of detailed discussion in the experimental section. Specifically, the experimental section needs a more thorough discussion, including comparisons with different variations and settings, as well as a comparison of the proposed approach with existing works related to their approach.", "other_comments_or_suggestions": "The authors need to check the entire paper and proofread it thoroughly. Some sentences without proper punctuation. For example: \"That means, we no longer need the conditional independence assumption Moreover, we formulate the data...\"", "questions_for_authors": "Most of the comments and questions have been mentioned in the sections above. However, these issues still need to be addressed:\n\n1. Do the authors analyze and discuss the impact of different augmentations and augmentation-aware error bounds in the two experimental settings?\n2.\tHow does the proposed approach compare against state-of-the-art papers, and can the authors highlight its main contributions across these different settings?\n3.\tSince the paper serves as a foundation for further theoretical exploration of data augmentation (self-supervised and contrastive learning), it needs a detailed analysis of the experiments and discussions.", "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": "", "extra_scores": {}}, {"review_id": "b7HuH3MMlf", "reviewer": "Reviewer_6JLt", "summary": "In this paper, the authors theoretically study how augmentations affect supervised risk, an unexplored area in self-supervised learning. Furthermore, they conduct some experiments to verify the theories.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We express our sincere gratitude to Reviewer 6JLt for appreciating the significance and reliability of our findings. We address your concerns below.\n\n---\n\n**Q1.** The error bound is not directly correlated with the final performance.\n\n**A1.** We respectfully disagree. As shown in Section 4.2, we show that the optimal data augmentation parameter minimizing the distance sum also leads to the best downstream accuracy, indicating that lower downstream error bounds highly correlate with better downstream performance. Specifically, in Theorem 2.3 we show that the supervised error bound depends not only on the unsupervised loss but also on the maximum distance between augmentations and the minimum distance between samples of the same class. Typically, efforts focus on minimizing the unsupervised error to reduce the supervised error bound. However, the two distance terms, which depend on the augmentation parameter, are also crucial and must be minimized to improve classification accuracy. This is empirically verified by Figures 5 and 6, which show that classification accuracy is inversely proportional to the sum of these two distance terms.\n\n---\n\n**Q2.** The paper lacks empirical guidance, making it unhelpful for selecting appropriate augmentation parameters.\n\n**A2.** On the one hand, our theoretical results in Section 2.2 show that the downstream classification risk depends not only on the unsupervised loss but also on the sum of two distance terms related to data augmentation, which provides empirical insight that the selection of data augmentation parameters is also vitally important. On the other hand, Section 3 demonstrates a theoretical trade-off between the two distance terms, indicating the existance of the optimal data augmentation parameters. Empirical varifications show that the optimal range of crop size should be large enough, with the upper bound being 1.0; the optimal probability of color jitter is around 0.6-0.8. (See Figures 5 & 6 and also the additional experiments on Imagenet100 in the response **A2** to Reviewer Xxrg.) Furthermore, for future works, our theoretical results also guides a possible direction for designing new data augmentation methods to deliberately minimize some unsupervised surrogate of the two distances.\n\n---\n\n**Q3.** When selecting augmentation parameters, only suitable values lead to good performance. Could the authors explain why this occurs based on these theorems?\n\n**A3.** In Theorems 2.1 and 2.3, we show that the supervised error bound depends not only on the unsupervised loss but also on the maximum distance between augmentations and the minimum distance between samples of the same class. Through model training, the unsupervised error can be reduced to a very small value. However, the impact of these two distance terms on classification performance is often overlooked. In fact, these distance terms are highly influenced by the augmentation parameter values. The augmentation parameter values that minimize the sum of these two distances may also yield the smallest classification error bound, as verified by Figures 5 and 6.\n\n---\n\nThanks for your insightful and constructive comments. Hope our explanations and additional experiments can address your concerns.", "claims_and_evidence": "Yes, the claims are supported by evidence.", "methods_and_evaluation_criteria": "There is not a new method in this paper.", "theoretical_claims": "No, I am not familiar with it.", "experimental_designs_or_analyses": "After reviewing the experiments, I think the findings are reliable.", "relation_to_broader_scientific_literature": "None", "essential_references_not_discussed": "None", "other_strengths_and_weaknesses": "Strengths \n1. This paper supports the augmentation study and highlights its important role in self-supervised learning.\n\nWeakness\n1. The error bound is not directly correlated with the final performance.\n2. The paper lacks empirical guidance, making it unhelpful for selecting appropriate augmentation parameters.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. When selecting augmentation parameters, only suitable values lead to good performance. Could the authors explain why this occurs based on these theorems?", "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": "", "extra_scores": {}}, {"review_id": "BLTZJRiVvm", "reviewer": "Reviewer_Do5D", "summary": "This paper explores the role of data augmentation from the perspective of theoretical research. It for the first time propose an augmentation-aware error bound for self-supervised contrastive learning, showing that the supervised risk is bounded not only by the unsupervised risk, but also explicitly by a trade-off induced by data augmentation. It also discuss how certain augmentation methods affect the error bound. Some experiments verify its proposed theoretical results.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We express our sincere gratitude to Reviewer Do5D for appreciating the novelty of our theory. We address your concerns below.\n\n---\n\n**Weaknesses.**\n\n**W1,W2,W3,W4,W7,W8.**\n**A.** We will revise the typos as suggested.\n\n**W5.** Mistakes in proof. (1) the decomposition at the beginning of Proof of Theorem 2.7 should have $p_{K-1}(\\ldots)r_{K-1}(\\ldots)$; (2) the last equation of Eq(31) should be $\\sum_{m=1}^k$.\n\n**A.** **(1)** The typo $r_K$ in the second line should be $r_{K-1}$, so that $p_{K-1}r_{K-1}$ appears in the second term of the decomposition. This typo does not affect the overall correctness of the proof.\n\n**(2)** No, the summation should be $\\sum_{m=k+1}^K$. According to the definition of $r_k$, there are $k$ different-class negatives, so the summation $\\sum_{m=1}^K$ here breaks into two groups: the negatives $\\bar{x}\\_m$ having different classes from the anchor $\\bar{x}$ ($\\sum_{m=1}^k$) and the negatives $\\bar{x}\\_m$ sharing the same classes as the anchor $\\bar{x}$ ($\\sum\\_{m=k+1}^K$). By fixing the abuse of notation $k$, Eq(31) becomes\n$$\n\\log(1+\\sum_{m=1}^k\\exp(-\\mathbb{E}\\_{\\bar{x}\\_m\\sim\\rho_{i_m}}\\mathbb{E}\\_{a',a_m}f(a(\\bar{x}))^\\top[f(a'(\\bar{x}))-f(a_m(\\bar{x}\\_m))])+\\sum_{m=k+1}^K\\exp(-\\mathbb{E}\\_{\\bar{x}_m\\sim\\rho_c}\\mathbb{E}\\_{a',a_m}f(a(\\bar{x}))^\\top[f(a'(\\bar{x}))-f(a_m(\\bar{x}\\_m))])),\n$$\nwhich simplifies the expectations and separates the two groups.\n\n**W6.** Eq(26) not rigorous, making Eq(25) and Eq(29) not strictly equivalent. Necessity to modify Theorem 2.6.\n\n**A.** **(1)** Eq(26) is rigorous according to the commutative law of addition. It holds for any $\\\\{i_1,\\ldots,i_K\\\\}$ being a rearrangement of $[K]$. Eq(26) ensures that e.g. $\\mathbb{E}\\_{\\bar{x}_1\\sim\\rho_1}\\mathbb{E}\\_{\\bar{x}_2\\sim\\rho_2}\\mathcal{L}=\\mathbb{E}\\_{\\bar{x}_1\\sim\\rho_2}\\mathbb{E}\\_{\\bar{x}_2\\sim\\rho_1}\\mathcal{L}$, and therfore Eq(27) can all be represented by the same $r_k$, making Eq(25) and Eq(29) strictly equivalent. \n\n**(2)** Theorem 2.6 is correct. Typos will be fixed according to **W5(2)**.\n\n---\n\n**Questions.**\n\n**Q1.** Understanding of augmentation overlapping.\n\n**A1.** We respectively disagree from a mathematical viewpoint. In the original paper (Wang et al., 2021), augmentation overlap is formulated as $\\mathcal{T}$-connectivity (Definition 4.3), where $x_i$ and $x_j$ are $\\mathcal{T}$-connected if $\\mathrm{supp}(p(x_i^+|x_i))\\cap\\mathrm{supp}(p(x_j^+|x_j))\\neq\\emptyset$, or equivalently, $\\exists t_i,t_j \\in \\mathcal{T}$ s.t. $t_i(x_i)=t_j(x_j)$, meaning that $x_i$ and $x_j$ sharing exactly the same augmented views $t_i(x_i)=t_j(x_j)$, which is unrealistic.\n\n---\n\n**Q2.** Relationship between $P_X$ and $P_{\\bar{X}}$.\n\n**A2.** $\\mathrm{P}_X$ is the distribution of $a(\\bar{x})$, where $a\\sim\\mathrm{P}_A$ and $\\bar{x}\\sim\\mathrm{P}\\_{\\bar{X}}$.\n\n---\n\n**Q3.** Which results does Lemma 2.8 represent?\n\n**A3.** Lemma 2.8 is part of Proposition 6 in Nozawa & Sato, 2021 and Lemma 4.3 in Arora et al., 2019. Compared with Proposition 6 in Nozawa & Sato, 2021, Lemma 2.8 does not have the $d(f)$ term and shows an equation because the left hand side is $\\bar{\\mathcal{R}}^{\\mathrm{sup}}$ instead of $\\bar{\\mathcal{R}}^{\\mathrm{un}}$ (without the need of using Jensen's inequality).\n\n---\n\n**Q4.** Advantages of decomposition.\n\n**A4.** The decomposition makes separation between same-class and different-class negative terms possible. Specifically, it decomposes the contrastive risk according to the number of negative samples having different labels from the anchor sample. The decomposition is non-trivial, as it only works for contrastive losses that treat negative samples equally (Eq(26)). With this decomposition, we further decompose the risk into different-class negative terms and same-class negatives terms (Eq(31)). Then respectively investigating the two types of terms (Eq(33) and Eq(37)), we reach our main theorems.\n\n---\n\n**Q5.** Discussions about Theorem 2.4.\n\n**A5.** Theorem 2.4 shows the finite-sample error bound as a complement to the other theorems based on the population distribution. It also shows the compatibility of our bound with generalization bounds in previous works.\n\n---\n\n**Q6.** Explain Lipschitz continuity.\n\n**A6.** The Lipschitz continuity condition concerning $f$ with respect to the image $x$ for convolution neural networks has been widely made in previous works, see e.g. \n[1] On Lipschitz Bounds of General Convolutional Neural Networks. TIP, 2019.\n[2] Intriguing properties of neural networks. ICLR, 2014.\nMoreover, the consistency between our pixel-level (Figure 2) and representation-level (Figures 3 & 4) experiments also verifies the assumption.\n\n---\n\nThanks for your insightful and constructive comments. According to our answers, we have clarified that our proofs have no factual mistakes (only typos to be fixed). We sincerely suggest the reviewer continue reviewing Section 3 and reconsider the overall recommendation score. We welcome any further questions during your follow up reviews.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I have carefully check the correctness of all proofs in this paper. Some issues I found are listed behind.", "experimental_designs_or_analyses": "No. Their experiments are intuitive.", "relation_to_broader_scientific_literature": "Please see the above Summary.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\n1.This paper for the first time proposes an augmentation-aware error bound for self-supervised contrastive learning, which is quite interesting.\n\nWeaknesses:\n\n1.In the lines 103-105, the symbol of the set of all possible data points should be $\\bar{X}$ instead of $P_{\\bar{X}}$.\n\n2.In the second paragraph of Section 2.1, the first sentence should be “In unsupervised contrastive learning, we select the different data augmentations of the same input image as the positive samples, and select the data augmentations of different input images as negative samples”. \n\n3.On the right head of the line 82, there lacks a period between “assumption”and “Moreover”.\n\n4.The equation between the line 138 and 139 lacks a minus sign in the exponential function.\n\n5.There are some mistakes in proof. For example, (1) the decomposition at the beginning of Proof of Theorem 2.7 should have $p_{K-1}(...) r_{K-1}(...)$; (2) the last equation of Equation (31) should be $\\sum_{m=1}^k$.\n\n6.The setting of Equation (26) is not very rigorous. Therefore, Equation (25) and Equation (29) are not strictly equivalent. Besides, it may be necessary to make some modifications to Theorem 2.6 and its proof.\n\n7.On the right head of the line 309, “likewise” should be “Likewise”.\n\n8.Equation (21) exceeds the page margin.", "other_comments_or_suggestions": "Because of Question 6, I have not read the analysis of Section 3 carefully. If the authors provide some reasonable explanations for my concerns, I will improve my score.", "questions_for_authors": "1.In the third paragraph of Introduction, the authors state that the augmentation overlap assumption is still barely realistic, because in practice, it is unlikely for two different real images to share **exactly** the same augmented views. However, in my opinion, if an image has an augmented view having the same semantics as another image, we can say that these two images are augmentation overlapping.\n\n2.What is the relationship between the distributions $P_X$ and $P_{\\bar{X}}$?\n\n3.Which results in Arora et al., 2019 and Nozawa &Sato, 2021 does Lemma 2.8 represent?\n\n4.The authors state that they derive a novel decomposition of unsupervised contrastive risk. However, from my perspective, it is just a detailed expansion of unsupervised contrastive risk. What are the advantages of this decomposition?\n\n5.What is the purpose that the authors provide the generalization bound in Theorem 2.4? It seems to be not essential. Please have more discussions about Theorem 2.4.\n\n6.Assumption 3.1 is very confusing. Generally, Lipschitz continuity condition is $\\|f(w) - f(w^\\prime)\\|\\leq \\|w-w^\\prime\\|$, where $w,w^\\prime$ represent model parameters. Some works denote model parameter as $x$. However, in this paper, $x$ represents sample (image). Therefore, I suggest the authors carefully explain this assumption (it is better to give some examples) and check their subsequent analysis.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper received ratings of 3,3,3,2. It offers a valuable theoretical contribution by introducing an augmentation-aware error bound for self-supervised contrastive learning, providing new insights into how data augmentation affects supervised risk. The analysis is rigorous and avoids overly restrictive assumptions, and while the experiments support the theory, they are limited to small-scale datasets and lack comprehensive comparisons. Some organizational and clarity issues also affect the presentation. Nonetheless, the paper addresses an important and under explored area, making it a worthwhile contribution that justifies acceptance
Decision: Accept (poster)