Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings
Authors: Nong Minh Hieu
Antoine Ledent
Venue: ICML 2025 poster (2025)
Keywords: Contrastive Learning
Generalization Analysis
Primary area: theory->learning_theory
TL;DR: We derive generalization bounds for CRL when data is limited to a fixed pool of labeled, reusable data points across tuples

Abstract: Contrastive Representation Learning (CRL) has achieved impressive success in various domains in recent years. Nevertheless, the theoretical understanding of the generalization behavior of CRL has remained limited. Moreover, to the best of our knowledge, the current literature only analyzes generalization bounds under the assumption that the data tuples used for contrastive learning are independently and identically distributed. However, in practice, we are often limited to a fixed pool of reusable labeled data points, making it inevitable to recycle data across tuples to create sufficiently large datasets. Therefore, the tuple-wise independence condition imposed by previous works is invalidated. In this paper, we provide a generalization analysis for the CRL framework under non-$i.i.d.$ settings that adheres to practice more realistically. Drawing inspiration from the literature on U-statistics, we derive generalization bounds which indicate that the required number of samples in each class scales as the logarithm of the covering number of the class of learnable feature representations associated to that class. Next, we apply our main results to derive excess risk bounds for common function classes such as linear maps and neural networks.

Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings
Nong Minh Hieu
Antoine Ledent
Abstract
points of other classes, thereby ensuring inter-class separa- bility under an appropriate distance metric. Motivated by this intuition, CRL has been utilized in numerous ML tasks as pre-processing step to improve data representations. Essentially, the goal CRL to learn a representation function f X RR that maps data from an input space X' to a representation space (potentially of lower dimension). The underlying strategy for representation learning is by pulling together similar pairs of data points (x. while pushing apart dissimilar pairs (xr, x; via minimizing cer- tain contrastive loss function l. For instance, given an input tuple (æz, at, , {., } where is the number of negative samples. the logistic loss (otherwise known as N- N-pair loss (Sohn, 2016)) é: 18 R2 is defined as follows:
Contrastive Representation Learning (CRL) has achieved impressive success in various domains in recent years. Nevertheless, the theoretical un- derstanding of the generalization behavior of CRL has remained limited. Moreover, to the best of our knowledge, the current literature only analyzes generalization bounds under the assumption that the data tuples used for contrastive learning are independently and identically distributed, How- ever, in practice, we are often limited to fixed pool of reusable labeled data points, making inevitable to recycle data across tuples create sufficiently large datasets. Therefore, the tuple- wise independence condition imposed by previous works is invalidated. In this paper, we provide a generalization analysis for the CRL framework under non-i.i.d. settings that adheres to practice more realistically. Drawing inspiration from the literature on U-statistics, we derive generalization bounds which indicate that the required number of samples in each class scales the logarithm of the covering number of the class of learnable feature representations associated to that class. Next, we apply our main results to derive excess risk bounds for common function classes such as linear maps and neural networks.
exp(-v:) v.) v.))
((v) log 1
Σ exp(
(I)
==1 where v; =f(x) f(xt) f(x) f(x))((x;))
The application of CRL spans a wide variety of ML disci- plines, including computer vision (Chen et al., 2020; He et al., 2019; Gidaris et al., 2018), graph representation learn- ing (Hassani & Khasahmadi, 2020; Zhu al., 2020; Velick- ovic al., 2019), natural language processing (Gao et al., 2021; Zhang et al., 2021; Reimers & Gurevych, 2021) and time series forecasting (Lee et al., 2024; Yang et al., 2022; Niel et al., 2023; Eldele et al., 2021). The increasing em- pirical success naturally inspires multiple theoretical works (Arora al., 2019; Lei et al., 2023; Hieu et al., 2024) ded- icated to studying the generalization behavior of the CRL framework. However, the analyses performed by previous works have only explored the i.i.d. settings where input tuples are independently and identically distributed (cf. Sec- tion 3.2). In reality, training datasets are often limited to fixed pools labeled samples (Sohn, 2016; van den Oord et al., 2019; Khosla al., 2020). Therefore, order to create sufficiently large datasets for contrastive learning, is standard practice "recycle" data points across input tuples (cf. Section 3.3). Effectively, it is possible for the same data points to appear multiple times in different input tuples, invalidating the independence criterion. As a result, previous results on generalization bounds for CRL might not comply with most practical use cases where data is limited.
1. Introduction
The performance of many machine learning (ML) algo- rithms is often significantly influenced by the quality of data representations. For example, multi-class classification problems, it is typically desirable for data points within the same class exhibit proximity, reflecting intra-class com- pactness, while maintaining sufficient separation from data
'School of Computing and Information Systems, Singapore Management University. Correspondence to: Nong Minh Hieu <mh.nong. 2024 @10e4@@phhcssse wtwdssssmu..du.s......
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalization Analysis for Non-IID CRL
In this work, we propose revised theoretical model and establish generalization bounds for the CRL framework under non-i.i.d. conditions, adhering more closely to the standard practice compared to existing results. Our key contributions are listed as follows:
more samples in the dataset, formulations of U-Statistics are often used to create unbiased estimators for the popu- lation risk. In such cases, the empirical risk minimizer is obtained via the minimization of U-Statistics. Techniques in U-Statistics have been applied in various analyses for generalization performance of common ML tasks, including bipartite ranking (Clémençon et al., 2008), metric and simi- larity learning (Cao al., 2016; Jin et al., 2009). pairwise learning (Lei et al., 2020; 2018), clustering (Li & Liu, 2021) and semi-supervised learning (HaoChen et al., 2021).
1. A revised theoretical framework for CRL: Previous analyses performed for CRL mostly rely on the theo- retical model proposed by Arora et al. (2019), which requires an i.i.d. assumption across input tuples used for empirical risk minimization (HRM). However, we argue that this approach does not abide by the set-ups of most practical use cases. As an alternative, we pro- pose a modified framework where ERM is performed using a small subset of input tuples assembled from a fixed pool of labeled data points (cf. Section 3.3).
Theoretical analysis of CRL: In the seminal work of Arora et al. (2019), the foundation for the theoretical understand- ing of the CRL framework was initially established. Their main contributions are threefold: (1) A formal definition of the population unsupervised risk and derivation of bounds the excess unsupervised risk, (2) a rigorous analysis of the class-collision phenomenon, which shows how the repetition of anchor-posie pestitr-ossivee classes among the negatives can distort learning and finally, (3) an analysis of the rela- tionship between the unsupervised risk and the downstream classification risk. While their theoretical contribution has set a strong foundation and has been rigorously utilized by further works, the bounds derived by Arora al. (2019) are limited by strong dependency of O(v kk) the number of negative samples. This dependency was later improved to at most logarithmic by Lei et al. (2023) using more advanced complexity measures like worst-case Rademacher complex- ity, fat-shattering dimension and arguments related to e=- Lipschitzness of loss functions inspired by prior works in multi-class classification (Lei et al., 2019; Wu et al., 2021; Mustafa et al., 2021). The theoretical model designed by Arora et al. (2019) was later extended to results in other regimes of CRL such as adversarial contrastive learning (Zou & Liu, 2023; Ghanooni et al., 2024), PAC-Bayes anal- ysis (Nozawa et al., 2020), de-biased CRL (Chuang et al., 2020) and CRL using DNNs (Alves & Ledent, 2024; Hieu et al., 2024). Notably, we emphasize that all of the afore- mentioned works target learning setups with i.i.d. tuples.
2. Generalization bound for the empirical minimizer of U-Statistics: We proposed a U-Statistics formula- tion (cf. Equation 10) for the population unsupervised risk (cf. Definition 3.1). We proved that, with high probability and when the dataset is balanedd,,,,, the generalization gap between the performance of the empirical U-Statistics minimizer and the Bayes risk grows in the order of (1/VVN) NN) where Ñ scales like ((N/(C) for small values of and (N//k) when l is large (cf. Theorem 5.1 and Theorem 5.2).
3. Generalization bound for the empirical minimizer of a sub-sampled risk: We derive generaliza- tion bound for the empirical minimizer of the "sub- sampled" risk, i.e., the average of some contrastive loss evaluated over a small subset of non-i.i.d. tuples (cf. Equation 7). We prove that, with high probability, the gap between the performance of the empirical sub- sampled risk minimizer and the Bayes risk scales in the order of O(1/V Ñ + 1/VM) where M is the number of tuples subsampled for training.
4. Applications of the theoretical results: We apply our results to obtain bounds for common classes of representation functions such as linear maps and deep neural networks.
Other lines of research in CRL: Other directions in the theoretical analysis of CRL have also been explored. For example, in Wang et al. (2022), the effect of data augmen- tation was studied using augmentation overlap theory. The authors suggested that aggressive augmentation can implic- itly enhance intra-class compactness. In Huang et al. (2023), the effect of unsupervised risk downstream classification was investigated by deriving bounds for the error rate of nearest-neightes classifiers built on top of learned represen- tations using misalignment probability. In Bao et al. (2022), the authors showed that the unsupervised risk is a surrogate of the supervised risk by deriving upper and lower bounds for the surrogate gap, which is the difference between the supervised and unsupervised risk. Further efforts for under- standing the effect of representation quality to downstream
2. Related Work
Empirical minimization of U-Statistics: U-Statistics were first introduced by Hoeffding (1948) as a class of statistics to estimate parameters via the use of symmetric kernels. The concentration properties of U-Statistics was later rigorously studied by Gine & Zinn (1984) and Arcones & Gine (1993). These works proposed concentration inequalities and limit theorems for U-Processes, setting an concrete foundation for subsequent works in statistical learning theory. In gen- eralization analyses where loss functions rely on two or
2

---

Generalization Analysis for Non-IID CRL
tasks have also been made (Arora al., 2019; Chuang et al., 2020; Li & Liu, 2021; Bao et al., 2022). Crucially, these works primarily focus on studying the influence of the population unsupervised contrastive risk on the population downstream classification risk. On the other hand, the anal- ysis in this paper targets generalization bounds on excess contrastive risk. Aside from the works mentioned above, another line of research studies the effect of negative sam- pling on the supervised downstream task. For example, in Ash et al. (2022), the authors show that while increasing the number of negatives can be initially advantageous, too many negative samples can potentially hinder the performance of
Definition 3.1 (Unsupervised Risk). Let 8 R R
be unsupervised loss function (E.g., Hinge Logistic losses) where k is the number of negative examples and f : X - R be representation function. The population unsupervised risk for ʃ is defined as follows:
Lun
(3)
E (1x))))))))))))((>)>)>>))))
E xxxxxxxa x D
Lun (f(c)
downstream classifiers. The work of Awasthi et al. (2022) builds upon this by showing that the decline of downstream performance as number of negatives increases can be theo- retically alleviated under certain situations (e.g., when class distribution is balanced). Despite earlier efforts, empirical experiments tend to suggest that amount of negatives usu- ally correlates positively with downstream performance. In Nozawa & Sato (2021), the authors proposed a novel frame- work based on the coupon collector's problem that bridges the gap between theory and practice, showing that as the number of negatives increases, the unsupervised risk is more likely to contain the supervised risk. We also note that all of the results in this direction concern population-level risks.
By the law of total expectation, we can decompose the population unsupervised risk as the weighted sum of the class-specific unsupervised risks Lun(flc) (flc) as follows:
Lfn(f) = Σ p(c)Lum(fll))
(4)
cEC
Remark 3.2. We note that the risk in Definition 3.1 is slightly different from Arora et al. (2019). In the latter, the negatives are drawn from D Exec p(e)Do, which allows the positive class to re-appear among the negatives, effectively allowing class-collision.
A natural choice of algorithm for determining a representa- tion function with low expected unsupervised risk is through empirical risk minimization (ERM). In the analyses done by Arora al. (2019); Lei et al. (2023); Hieu al. (2024), the empirical risk minimizer is identified via ERM ap- proach. Specifically, let S = {(x, .i).......... x7x) j-1
3. Problem Formulation
3.1. Problem Set-up
We denote X' as the space of input vectors and C be the finite set of all classes. Suppose that p is the discrete probability measure over C (for all E C. p(c) denotes that occurrence probability of class c). For any class e C, we denote De as the class-conditional distribution of input vectors over X given that the vectors belong to class c. On the other hand, we define D. as the distribution of input vectors in A' given that the vectors do not belong to class c. Specifically, D. is defined as follows:
be a dataset of n independently and identically (i.i.d.) drawn input tuples from an unknown distribution. The empirical risk minimizer then defined as fn = arg min [J)(() where T. (f) is defined as:
n i (ʃ) - Σ 3=1
(5)
In line with most of the learning theory literature, the gener- alization gap (am((f))) -inffannfiffaaaa jes [fm( can be conveniently (2)
Dz(z)= = Exec,rrc (xx)
X
1 1- p(c)
upper bounded via controlling the Rademacher complexity of the loss class l F:
Basically, for I X, (x(x) quantifies the probability that rr does not belong to class c. Let F denote the class of repre- sentation functions f X + Rd for d >>> 1. For f E F, we denote Tunn (f) as the (population) unsupervised risk of f (cf. Definition 3. In this work, we are interested in bounding the excess risk of the form Lun(f) -inn fEF (fa(f) where f a minimizer of an empirical risk assessed on some dataset.
lo F (xx,xt,xx....,xxx.
(6)
((x)) 1(x)) fEFJ.
However, Rademacher complexity based bounds, which arise from the symmetrization trick, are only immediately applicable under the assumption that the tuples in S are all independent. Under regimes where tuples are sampled in a way that violates this assumption, more nuanced ap- proaches are required before sample complexity bounds can be derived.
3.2. A Theoretical Framework under IID Settings
We start by revisiting the key definitions from the theoretical framework proposed by Arora al. (2019).
3

---

Generalization Analysis for Non-IID CRL
3.3. A Revised Framework under non-IID Settings
4. Proof Strategy
An issue with the framework described in Section 3.2 that S is defined as a dataset sampled i.i.d. from distribution of tuples. However, in practice, we do not observe whole input tuples independently due to the cost of data collection. Instead, training of representation functions is often limited
As mentioned in the previous section, we are interested in how well the empirical sub-sampled risk minimizer faub generalizes to testing data. In particular, we are concerned with bounding the excess risk Lun (faub) - inf JEF Lun( However, as noted in Section 3.3, this is not immediately straightforward because the set of sub-sampled tuples Taub are not i.i.d. Therefore, we first formulate an (asymptoti- cally) unbiased estimator (U-Statistics), denoted MN(J), for the population unsupervised risk Lun (f). Then, can decompose the generalization gap as (cf. Theorem E.1):
to fixed pool S {x
X' C of input vec- tors and their corresponding labels, which are drawn i.i.d. from joint distribution over X and C (for each E C, we denote Ñ the number of samples that belong to class c, i... Exec Ñ N). One possible alternative is to evaluate the empirical risk over all possible tuples that one can create from the dataset S. Unfortunately, this approach is computa- tionally expensive because as the number of labeled samples N increases, the number of all possible tuples grows in the order of o (Nt) (N N
SEF 2 T (nmn() inf Tmun())
sup [(f; Teub) ux(f)| SeF
sup ((N(F) Lm)( feF
Alternatively, more reasonable approach is to use only a small subset of valid tuples. Let Taub denote the subset of tuples that we use for training, the procedure for sub-sampling input tuples to train representation functions can be described as follows:
As result, the task of bounding [fun()) (utfsss--iaa inf fer Lfn(f) translates naturally to the sub-tasks of deriving uniform bounds for the absolute deviations between:
1. The sub-sampled empirical risk (Eqn. 7) and the for- mulation of U-Statistics (Eqn. 10), and
1. For 1 & j < M, collect M tuples of the form (x,, x5+ X,1 X....... xxx) as follows:
2. The U-Statistics (Eqn. 10) and the population unsuper- vised risk (Eqn. 3).
(i) Select a class c C with probability P(c) = R (ii) Select x uniformly (without replacement) among samples belonging to class c. We call these two data points the "anchor-positive pair".
In the following sections, we will provide general strate- gies to tackle both types of deviations. Our proof will rely heavily on the U-Statistics decoupling technique (Arcones & Gine, 1993; de la Peña & Giné, 1998).
(iii) Select ......., Xjx uniformly (without replace- ment) among samples belonging to classes other than c. We call these "negative samples". (iv) Add the tuple (x,, Xfi...., X(k)) to Teub.
4.1. Bounding the U-Statistics to Population Unsupervised Risk Deviation
2. Finally, repeat the above steps M times independently.
Given S= (x X,) drawn i.i.d. from a distribution P over an input space X. Let h : xm IR be a symmetric kernel in its arguments, i.e., (I, is unchanged for any permutations of Z1. Im E X. Then, natural estimate for the parameter 0 = Ex Ex........PP.. [h (x ...)) can be the average of the kernel h over all possible mntuuples (selected without replacement) that can be formed from S (which is the one-
Overview of U-Statistics:
Using the collected set of tuples Taub described above, the empirical risk evaluated for every representation function T F is computed as:
L(;; Taub))
1 M Σ ((( f(x), Bit)
M
sample U-Statistics of order m for the kernel h), denoted (n).). Formally:
which we refer to as "sub-sampled empirical risk" since it is only evaluated on small subset of valid tuples. In this revised framework, we are interested in the performance of the sub-sampled empirical risk minimizer, which we define as feub arg =i [f Taub).
Σ Un(h) (Cm
h(Xi,
Xim)
(8)
where Cn.[n]] denotes the set of m-tuples selected (without replacement) from [r]] without order (m-combinations), We call (h) an one-sample U-Statistics of order m. When the kernel h is asymmetric with respect to the arguments, the average is taken over the set of m-tuples selected from [n] with order instead (m-permutationn).
'For given class e, a valid tuple is chosen by picking two samples from class c and & samples from other classes. Hence, the total number of tuples possibly formed for each class is
2( (N-NE) o (N (N- )
4

---

Generalization Analysis for Non-IID CRL
Remark 4.1. (2) is indeed an unbiased estimator for 0. However, since the formula averages over set of non-
where N₂ min L(N //) and Ux(fle) denotes the U-Statistics that estimates the conditional unsu- pervised risk Lun (f(c), i.e., the average of the contrastive loss l over valid tuples in Te (cf. Appendix D, Eqn. 27). The indicator involving N. specifies whether there are enough samples to form at least one tuple where the anchor-positive pair belongs to class c. When N, = (i.e., To = D), the dataset S lacks either anchor-poss postitie pairs or negative sam- ples. In this case, we set the estimation for Lau (flc)) to O, indicating the absence of information about the unsuper- vised risk conditioned on class c.
i.i.d. tuples, it is impossible to analyze the concentration properties of U, (h) without applying further processing.
Our proof relies on the decoupling technique of U-Statistics discussed in de la Peña & Giné (1998). Specifically, the goal is to decouple the U-Statistics as an average of mean over independent "blocks" of samples so that we can apply concentration inequalities (E.g. McDiarmid (1989)). Let q = |n/m| (which represents the maximum number of i.i.d. tuples possibly created from S). the U-Statisties given in Eqn. (8) can be re-formulated as follows:
4.2. Bounding the Sub-sampled Empirical Risk to U-Statistics Deviation
(h) = 1
Σ (S),,
n!
Suppose that the dataset S is given. The sampling procedure described carlier in Section 3.3 is equivalent to selecting M elements (with replacement) from the pool of all possible tuples such that the probability of selecting a tuple whose auchor-positivy pair belongs class c C is proportional to N
SeS[p]
VS( =
Σ
h [afmiim++1]pp Xzfma)),
1-1
N the unbiased estimator of the class probability Pe. In
and S[n]] = π [m]] - [n]]] π is bijective denotes the set of all possible permutations of the indices [m] = (l,...,7) n).
other words, it is equivalent to drawing M tuples indepen- dently from the discrete distribution V/ over T such that for any tuple T T, the mass assigned to T via v is:
The techniques related to decoupling U-Statistics has been applied for bipartite ranking in Clémençon al. (2008), which involves one-sample U-Statistics with order 2. Even though the authors pointed out that their results can be nat- urally extended to m--order U-Statistics for any m > 2, it is not as direct to formulate a (I: + 2)-ord U-Statistics in the case of CRL. Specifically, in Clémençon et al. (2008), the selection of valid tuples is straightforward by choosing (without replacement) m elements arbitrarily from single random sample S. On the other hand, the problem setup of CRL involves [C] random samples with random sizes. Fur- thermore, given an arbitrary (k + 2)-tuple selected (without replacement) from S, the validity of the tuple is restricted by the classes of its elements (as described Section 3.3).
N [Ta
v(T)
if TE
(11)
fcec: N. > 13. which denotes the subset of classes such that Vc e č, To + Ø. Then, we have:
Let č
N Σ cEC
E Tout>ud
[ (Tub)) [
N UN(slc).
(12)
Ux(()
In other words, given fixed draw of the labeled dataset S, the sub-sedpled empirical risk, which is evaluated subset of tuples drawn i.i.d. from the distribution V, concen- trates to the proposed U-Statistics formulation in Eqn. (10). Hence, we can make use of classic results in learning theory on Rademacher complexity bounds (cf. Proposition F.3) to obtain high probability results on the excess risk of saub. conditionally given the draw of the labeled dataset S?.
Therefore, instead of formulating (k+2)-order U-Statistics to estimate Lun (f) directly, our approach is to formulate multiple class wise U-Statistics (x((flc) to estimate each class-conditional risk T.mm (flc) separately then combine the estimations. Specifically, Let T be the set of all possible valid tuples (not necessarily i.i.d., repetition of data points across tuples allowed) that can be formed from the dataset S. Additionally, denote T Usee Te where for each e C, Te denotes the set of valid tuples whose anchor-positive pairs belong to class c. Thus, |To| = 2() ((=N . The core strategy of our proofs relies on the following U-Statistics formulation for the population unsupervised risk (f):
5. Main Results
Notations and Settings: Let S (x) be the
labeled dataset and 'T be the set of all possible valid tuples that can be formed from S. Additionally, for each C:
(f( = Σ N+
acd N (x(flc). Ux(flc) = I(N. > 1FUN(fIc)
(10)
The conditioning can be easily eliminated using the tower rule (cf. Theorem E)
5

---

Generalization Analysis for Non-IID CRL
where f(x)), (xx)), [(x denoted Jz J3 for all 1 ] _ n, x k for notational brevity and denote Σ, (01,..., as the vector of independent
Sc
Rademacher variables. Additionally, when T 2, we define ( for completeness.
Assumption: We assume that for all classes C, whenever Teli Ø (i.e., N₂ 1), Rademacher complexity Rysa (fo of the loss class as:
bound the empirical
Selected for tuples set 7
Ry.i ((oF) KF.c. VN."
(14)
where KF,- an expression that depends on both the function class F and the class itself. For example, by the Dudley entropy integral (Theorem F.5), we can bound RTu F) with Ky,e as an expression that involves the T2z-covering number (ef. Definition D.11) 11) of to restricted to the subset of independent tuples T
Excesss Sg mnm Samples
In the results that follow, for a given representation function f we denote ER ( Lun( feF Lun for notational brevity (short for "excess risk").
5.1. Generalization Bound for Empirical Minimizer of U-Statistics
Figure An illustration of the tuples selection process for Telidd In this case, there excess samples from S. that are left unused. However, the other way around where there are excess samples from S. also possible (E.g. for very large values of k.).
Theorem 5.1 (cf. Theorem D. Let F be class of rep- resentation functions and { R - [0,M] be bounded contrastive loss. Let fur arg min (f). Then, for any 5 e (0, 1), with probability of at least 1 5:
Let S. S the be set of data points belonging to class c (i.e., S = Usec So). Also, denote S. S
KFc
In C|/8
ERan(fu) (fu) & <0
p(c)
MM
(15)
OEC
Let o = |Sol and No- 15.1 N Also, we //1.
where = N min |mineee p(c)
1-maxesc p(c)
define N.
Let Trid be the set of independent tuples selected in a "greedy" way such that each tuple's anchor anchor-positive pair belongs to class c. Specifically, we select tuples for Tilld by matching 2-element disjoint blocks from S. and k-element disjoint blocks from S. until one of the two sets Therefore, when T:id Ø, T Ne-
To understand the intuition of Theorem 5.1, let assume that the underlying distribution over the labels set C is per- fectly balanced, meaning p(c) = |C|-1, Vc E C. Under this assumption, have Ñ N max ACC)/(CC 1)] which means that the bound scales O O(vicI/N) for k & 2|C| and as O(yk/N) for larger values of k. In other words, for given desired generalization gap, the sample complexity of the model exhibits square-root de- pendency on either the number of classes or on the number of negative samples. For example, if we consider class of neural networks with W parameters in total, the sample complexity to reach desired generalization gap of e scales in the order of δ Wk (cf. Table or Theorem 1717) for large values of & and when the distribution over C is perfectly balanced.
of blocks to select (cf. Figure 1).
Furthermore, for any subset of tuples T = T, we denote ( F) as the empirical Rademacher complexity of the loss class lo F (Eqn. (6)) restricted to T'. Formally, we denote T { (xx, .xI1. xJ......
x7x) j=1
we have:
Ex,
sup fEF
1
Σ oje (1T
(13)
At first glance, the bound may seem worse than that of previous works by Lei al. (2023) and Hieu et al. (2024)
n --1
6

---

Generalization Analysis for Non-IID CRL
Table 1. Summary of generalization bounds for lu and Jeub when the class of representation functions linear maps and neural networks. The O notation hides poly-logarithmic terms of all relevant quantities. For linear maps, N,M, 7), 8, a, b, k and df are hidden. For neural networks, 77, N, L, b, 1iil/ and {sili= are hidden.
f
Function Classes
Generalization Bounds ER (f)
Relevant Results
Ju
Fin (Eqn. (17))
geab
In
Theorem D.15
N
fu
FA (Equ. (18))
Ö MW2
+ MM
16
Theorem D.17
Jaub
Fiin (Eqn. (17))
δ nsab² ( + V VM + +
In 1015
1m188 M
Theorem E.2
N
Paub
FA
um (Eqn. (18))
δ
Mw3
(V*
+ V M
+ M
In CC/5 N
In 1/5 M
Theorem E.3
where one of the primary strengths of their results is the logarithmic dependency on the tuples size k. However, we note that the results in the above references express sample complexity in terms of tuples rather than the number of labeled data points. Specifically, their generalization bounds scale in the order of O(1/ where n is the number of tuples drawn i.i.d. from an unknown distribution of tuples. In other words, there are N nk labeled data points in total. Therefore, under the regime where the label distribution is perfectly balanced and there is a large number of negative samples, our bound behaves similarly as the bounds derived by prior works.
5.2. Generalization Bound for Empirical Sub-sampled Risk Minimizer
Theorem 5.2 (cf. Theorem E.1). Let F be a class of rep- resentation functions and i : R - [O be bounded contrastive loss. Let feub arg minje. [(f: Tsub). Then, for any 8 E (0, 1), with probability af least 1 - 5:
ER ( &0
Ep(e)
Σ p(c)
KF VN
+ RTo
(loF) (16)
CEC
In 1/5
In C1/8
My
MM
M
N
One key drawback of the bound in Theorem 5.1 is its square- root dependency on the number of classes |C| when & is small. This arises from analyzing the concentration of each U-Statistics UN (flc) around their corresponding conditional unsupervised risk Lun (flc) independently. As a result, the sample size required to achieve desired generalization gap has to be large enough such that for all e E C, the deviations [flc)) - Lun (ffc) are small even though the probabili- ties for most classes are low (especially for large number of classes (C), making their contribution to the overall unsuper- vised risk (f) negligible. Consequently, the minimum occurrence probability min.ec p(c) is introduced into the sample complexity as a result of minimizing the deviations between UN (flc) and Lun(f (flc) across all classes equally.
where Ñ N min mineee plc)
1- maxxcc p(c)
2
h
From the above theorem, there is a striking resemblance to the result in theorem 5.1 except there is additional cost of order O (V In 1/8
Although there is additional empiri-
cal Rademacher complexity Ry... (f F) appearing in the bound, by Theorem F.5, we know that it also scales in the order of ((1/VM] The implication of this result is straight- forward: under the sub-sampling regime, when the number of sub-sampled tuples large, the performance discrepancy between the empirical sub-sampled risk minimizer saub and fu is negligible. As a result, under circumstances when the amount of labeled data points available is too large, making it computationally impossible to train on all valid tuples, the training of representation functions can be improved by simply increasing the number of (non- -oo--nddeendden) tuples. We further corroborate this intuition with a numerical exper- iment (Figure 2). which shows that the performance of the aub-sampled empirical risk minimizer tends to the perfor- mance of the full U-Statistics minimizer as the number of sub-sampled tuples M increases.
We conjecture that there a certain U-Statisties formulation that accounts for the concentration of all classes once. However, we note that this is major technical challenge as it is non-trivial to formulate a (I + 2ordrr U-Statistics to estimate (f) directly. This is primarily due to the fact that a randomly selected (k + -tuuee from the pool of la- beled data points S is not automatically a valid input for the loss function& l, making complicated to apply techniques in de la Peña & Giné (1998) and Clémençon al. (2008).

---

Generalization Analysis for Non-IID CRL
All-tppes
NoevERL (95% Elj
R.A.d. 195%
195%
A.d.. 195%
Allituples (95%
2.30
Generalization gap
Classifier Accuracy
Classifier Accuracy
Generalization
Generalizza aaaaaiizziion
1.2h
1,00
0.30
02
0.09
025 858
1.5
2.08
025
0.50 835
3/75
2.9
20000
40083
c0ao0
00033
20088
4200e
Number of tuples (M)
Number tuples (M)
Number of tuples (M)
Number of tuples (M)
Figure 2. Summary of results for experiments with the MNIST dataset. On the left, we have the results for 10000. On the right, have the results for n 100 as well as the additional result for the all all-ruples regime.
Neural Networks: Let I, 3 1 and do d1..... dz be known positive integers representing layer widths. Furthermore, let W Σi_ d. which is the total number of parameters in the neural networks. For 1 < & L, we define the sets of matrices Br A E Rd-ixdi xdi, ||A0)) st as the
Sample complexi eexittyt N2
layer-wise parameter spaces where {s is sequence of known real positive numbers. Let {sp) R - R }/= be sequence of activation functions that are fixed a-priori which are L-Liscchitz with constants {(r) i.e. Vx, x' e Rd: and & & L, we have [|xx - (x('') || < &/|ix - x'12. Then, we are interested in the class of neural networks FA defined follows:
12
26
15
24
Number of Ineattvve samples k
Number of classes [c]
Figure 3. Summary of results for synthetic data experiments the relationship between [C], l the sample complexity.
FA = FL FL-10...0
(18)
where Fi for fx for (A)))) A E Bi J.Ve [L].
5.3. Generalization Bounds for Common Classes of Representation Functions
6. Experiments
In this section, we describe the numerical experiments on both synthetic and open sourced datasets to empirically verify our main results. Specifically, we aim to provide em- pirical evidence to corroborate three hypotheses. Firstly, the sample complexity, i.e., the number of labeled examples re- quired to reach desirable performance, for the U-Statistics minimizer corresponds (linearly) to the number of negative samples and the number of classes. Secondly, as the num- ber of sub-sampled tuples increases, the performance of the sub-sampled empirical risk minimizer approaches that of the full U-Statistics minimizer. Finally, the performance of models trained on tuples with recycled data (non-i.i.d. tuples) can outperform both models trained independent tuples and models trained directly with the non-contrastive cross-entropy loss. This observation is in line with the ex- isting literature (Khosla et al., 2020). In fact, the benefit of recycling data most present when there are too few labeled data points to construct disjoint tuples. For all ex- periments detailed below, we fix class of shallow
Suppose that the contrastive loss function é : R MM 888 -iipchhctttz with constant 17 > 0. Specifically, for all v.v' R [((v) f(v') < 7/|vv v'lle- Also, suppose that supxes x|2 with probability one (with respect to the draw of dataset S) for some R4. In this section, apply our main theorems to derive generalization bounds for common classes of representation functions such as linear maps and neural networks. We provide a summary of our main results Table and a brief description of the considered function classes below.
Linear Functions: For matrix A mxd define the || 12,1 norm as ||4 Σ |A,12 i.e., the sum of column Euclidean norms and || lla as the spectral norm. We define the class of linear functions as follows:
Fim = {I xI- Ar :A d
(17)
AAT 12,1 & &.ll $n).
8

---

Generalization Analysis for Non-IID CRL
neural networks (with a fixed number of layers L 2). We summarize experiment results in Figure 3 and Figure 2.
Training: We create 5 random generations of Gaussian datasets for each configuration of |C] and & values. Then, for each configuration and dataset, we find the sample com- plexity N. corresponding to a desired gap using a binary search approach within a fixed values range of N. For each search, we train the neural network with M = N² sub- sampled tuples so that the performance is approximately close to that of fu- Fixing < = 0.5, we conduct the ablation studies with the following values ranges of [C] and k:
6.1. Performance of faub as M Increases
In this section, we describe two experiments conducted on the MNIST dataset. Firstly, we sample from the original dataset n independent (disjoint) valid tuples. Then, for each of the following regimes, We train the neural networks for random weights initializations:
Ablation study I: Fix k 3 and increase the values of [C] from 5 to 50 with an interval of 5.
Using only the selected n inde- pendent tuples as the training dataset.
Independent tuples:
Sub-sampled tuples: Among all the n2k + 2) labeled data points from the previously selected disjoint tu- ples, we sub-sample M tuples and use them as the training dataset.
Ablation study 2: Fix |C| and increase the values of k from 5 to 50 with an interval of 5.
For each configuration, we average the sample complexities over the random dataset generations and plot the results in Figure 3. For both experiments, the sample complexities display linear relationships with values of l and [C]. These observations are consistent with the result in Theorem 5.1.
For each regime and random weight initialization, we also train and evaluate linear classifier on top of the learned representations extracted from the original MNIST dataset. We conduct the experiments with n = 100 and n = 10000. For the case of n = 100, we also compare the above regimes with the performance of the neural networks when trained on all possible valid tuples. The results of both experiments are summarized in Figure 2. For both cases, the results show that the sub-sampling regime helps with the performance for both supervised and unsupervised tasks. Noticeably, when the number of labeled examples (n = 100) is small, the re- sult of reusing samples across tuples outperforms the i.i.d. regime extremely fast, which cements the practical validity of the learning setting considered. Moreover, for n = 100, we observe that the performance of the sub-sampling regime closely approximates the all-tuples regime. This observa- tion is in line with the implications from Theorem 5.2. Fur- thermore, the model trained on sub-sampled tuples quickly outperforms the fully independent tuples regime as M in- creases, highlighting the benefit of recycling data when the amount of labeled examples limited.
7. Conclusion & Future Work
In this work, we derive generalization bounds for the CRL framework when training is limited to a fixed pool of reusable labeled examples. We provide two main results on the excess risk bounds for the U-Statistics minimizer fur and the empirical sub-sampled risk minimizer feub. We show that under the assumption that the class distribution is per- fectly balanced, our results for the U-Statistics minimizer behave similarly to the previous analyses conducted for the i.i.d. regime. Furthermore, we prove both theoretically and empirically that under the sampling regime, as the number of sub-sampled tuples increases, the performance of faub is approximately close to fu. Thereby, verifying the validity of the common practice of recycling labeled samples across input tuples. Finally, we apply our main results to derive specific generalization bounds for common function classes such as linear maps and neural networks.
6.2. Correlation Between Sample Complexity and Values of [C], k
In experiments, demonstrate the advantages of recy- cling samples in different tuples, and confirm the superiority of supervised contrastive learning over direct training with the cross-entropy loss.
Let us denote N, as the minimum number of samples re- quired to achieve a desired generalization gap e O. We conducted two ablation studies to investigate the correlation between N. and different values of [C] and k.
We also note that our excess risk bounds possess a depen- dency of O (Pmii) where Pmin is the probability associ- ated the rarest class. This can potentially be overly pes- simistic in cases when there are a lot of small categories in the true class distribution. This dependency arises because all the class-wise U-Statistics Uxx (4x(f ff(c need to concentrate uniformly. Therefore, a possible future direction is to im- prove this dependence by designing an estimation strategy which captures joint concentration across small classes.
For each value of N, |C] and k, we gener- ate the sample sizes )N+) Jeec ~ Multinom(N, (IC)-))occ (assuming perfectly balanced classes condition) and random Gaussian centers g. E R128 corresponding to each class ce C. Then, for each class CE C, we generate the samples from that class as S. ~ NN(., 22)Nt with a fixed standard deviation of laaaa 0.1.
Initialization:

---

Generalization Analysis for Non-IID CRL
Impact Statement
de la Peña, V. and Giné, E. Decoupling: From Depen- dence Independence. Probability and Its Applications. Springer, 1999 edition, 1998.
This work is primarily theoretical and we cannot foresee any potential implications that need be addressed.
Eldele, E., Ragab, M., Chen, Z., Wu, M., Kwoh, C. K., Li,
References
X., and Guan, C. Time-series representation learning via temporal and contextual contrasting. International Joint Conference on Artificial Intelligence, 2021.
Alves, R. and Ledent, A. Context aware representation: Jointly learning item features and selection from triplets.
IEEE Transactions Neural Networks and Learning Systems, 2024.
Gao, T., Yao, X., and Chen, D. Simese:
Simple contrastive learning of sentence embeddings. In Conference on Em- pirical Methods Natural Language Processing, 2021.
Arcones, M. A. and Gine, Limit theorems for u- a-processes. The Annals of Probability, 21(3):1494 1542, 1993.
Ghanooni, N., Mustafa, W., Lei, Y., Lin, A. W., and Kloft, M. Generalization bounds with logarithmic negative- sample dependence for adversarial contrastive learning. Transactions on Machine Learning Research, 2024.
Arora, S., Khandeparkar, H., Khodak, M., Plevrakis, O., and Saunshi, N. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Learning Representation, 2019.
Gidaris, S., Singh, P., and Komodakis, N. Unsupervised representation learning by predicting image rotation. In International Conference on Learning Representation, 2018.
Ash, J. T., Goel, S., Krishnamurthy. A., and Misra, D. Inves- tigating the role of negatives in contrastive representation learning. In International Conference Artificial Intelli- gence and Statistics, 2022.
Gine, E. and Zinn, Some limit theorems for empirical processes. The Annals of Probability, 12(4):929 989, 1984.
Awasthi, P., Dikkala, N., and Kamath, P. Do more negative samples necessarily hurt in contrastive learning? In International Conference on Machine Learning, 2022.
Golowich, N., Rakhlin, A., and Shamir, O. Size-independent sample complexity of neural networks. In Conference On Learning Theory, 2017.
Bao, H., Nagano, Y., and Nozawa, K. On the surrogate gap between contrastive and supervised losses. In Interna- tional Conference on Machine Learning, pp. 1585-1606. PMLR, 2022.
HaoChen, J. Z., Wei, C., Gaidon, A., and Ma, T. Provable guarantees for self-supervised deep learning with spec- tral contrastive loss. Advances in Neural Information Processing Systems, 2021.
Bartlett, P. L., Foster, D. J., and Telgarsky, M. Spectrally- normalized margin bounds for neural networks. In Ad- vances in Neural Information Processing Systems, 2017.
Hassani, K. and Khasahmadi, A. H. Contrastive multi-view representation learning graphs. In Advances in Neural Information Processing Systems, 2020.
Boucheron, S., Lugosi, G., and Massart, P. Concentration Inequalities Nonasymptotic Theory of Independence. Oxford University Press, 2013.
He, K., Fan, H., Wu, Y., Xie, S., and Girshick, R. Mo- mentum contrast for unsupervised visual representation learning. In Computer Vision and Pattern Recognition, 2019.
Cao, Q. Guo, Z.-C., and Ying, Y. Generalization bounds for metric and similarity learning. Mach. Learn., 102(1): 115-132, 2016.
Hieu, N. M., Ledent, A., Lei, Y., and Ku, C. Generaliza- tion analysis for deep contrastive representation learning, In Proceedings of the AAAI Conference Artificial In- telligence, 2024.
Chen, T., Kornblith, S., Norouz, M., and Hinton, G. A simple framework for contrastive learning of visual rep- resentations. In International Conference on Machine Learning, 2020.
Hoeffding, W. class of statistics with asymptotically nor- mal distribution. The Annals of Mathematical Statistics, 19(3):293- 325, 1948.
Chuang. C.-Y., Robinson, J., Yen-Chen, L., Torralba, A., and Jegelka, S. Debiased contrastive learning. In Ad- vances in Neural Information P Processing Systems, 2020.
Huang, W., Yi, M., Zhao, X., and Jiang, Z. Towards the generalization of contrastive self-supervised learning. In International Conference on Learning Representation, 2023.
Clémençon, S., Lugosi, G., and Vayatis, N. Ranking and empirical minimization of u-statistics. The Annals of Statistics, 36(2):844 874, 2008
10

---

Generalization Analysis for Non-IID CRL
Jin, R., Wang. S., and Zhou, Y. Regularized distance metric learning: Theory and algorithm. In Advances in Neural Information Processing Systems, 2009.
Nozawa, K. and Sato, Understanding negative samples in instance discriminative self-supervised representation learning, In Advances in Neural Information Processing Systems, 2021.
Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised contrastive learning. In Advances in Neural Information Processing Systems; 2020.
Nozawa, K., Germain, P., and Guedj, B. Pac-bayesian contrastive unsupervised representation learning. In Con- ference on Uncertainty in Artificial Intelligence, 2020.
Ledent, A., Mustafa, W., Lei, Y., and Kloft, M. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8279-8287, 2021.
Reimers, N. and Gurevych, I. Sentence-bert: Sentence embeddings using siamese bert-networkss. In Conference on Empirical Methods in Natural Language Processing, 2021.
Sajjadi, M., Javanmardi, M., and Tasdizen, T. Regulariza- tion with stochastic transformations and perturbations for deep sune-super learning. In Conference on Neural Information Processing Systems (NIPS), 2016.
Lee, S., Park, T., and Lee, K. Soft contrastive learning for time series. In Interaational Conference on Learning Representation, 2024.
Lei, Y., Lin, S.-B., and Tang, K. Generalization bounds for regularized pairwise learning. In International Joint Conference on Artificial Intelligence, 2018.
Sohn, K. Improved deep metric learning with multi-class n-pair loss objective. In Advances in Neural Information Processing Systems, 2016.
Lei, Y., Dogan, Ü., Zhou, D.-X., and Kloft, M. Data- dependent generalization bounds for multi-class classifi- cation. IEEE Transactions on Information Theory, 65(5): 2995-3021, 2019.
van den Oord, A., Li, Y., and Vinyals, O. Representation learning with contrastive predictive coding, 2019. URL https: / arxiv. wwwp:/iwwwwga////oo/o 807 0 03748.
Velickovic, P., Fedus, W., Hamilton, W. L., Lio, P., Bengio, Y., and Hjelm, R. D. Deep graph informax. In Interna- tional Conference on Learning Representation, 2019.
Lei, Y., Ledent, A., and Kloft, M. Sharper generalization bounds for pairwise learning. In Advances in Neural Information Processing Systems, 2020.
Wang, Y., Zhang, Q., Wang, Y., Yang, J., and Lin, Z. Chaos is a ladder: A new theoretical understanding of con- trastive learning via augmentation overlap. In Interna- tional Conference on Learning Representation, 2022.
Lei, Y., Yang, T., Ying, Y., and Zhou, D.-X Generaliza- tion analysis for contrastive representation learning. In International Conference in Machine Learning, 2023.
Li, S. and Liu, Y. Sharper generalization bounds for cluster- ing. In International Conference on Machine Learning, 2021.
Wei, C. and Ma, T. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In Ad- vances in Neural Information Processing Systems, 2020.
Long, P. M. and Sedghi, H. Generalization bounds for deep convolutional neural networks. In International Confererence on Learning Representations, 2020.
Wu, L.,, Ledent, A., Lei, Y., and Kloft, M. Fine- Fine-grained gen- eralization analysis of vector-valued learning. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10338-103444 2021.
McDiarmid, C. On the method of bounded differences, pp. 148-188. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989.
Yang, X., Zhang, Z., and Cui, R. Timeclr: self-supervised contrastive learning framework for univariate time series representation. Knowledge-Bood Based Systems, 2022.
Mustafa, W. Lei, Y., Ledent, A.. and Kloft, M. Fine-grained generalization analysis of structured output prediction. In Proceedings of the Thirtieth International Joint Confer- ence on Artificial Intelligence (IJCAI). International Joint Conferences on Artificial Intelligence, 2021.
Zhang, D., Li, S.-W., Xiao, W., Zhu, H., Nallapati, R., Amool, A. O., and Xiang, B. Pairwise supervised con- trastive learning of sentence representations. In Confer- ence on Empirical Methods in Natural Language Pro- cessing, 2021.
Niel, Y., Nguyen, N. H., Sinthong, P., and Kalagnanam, J. A time series is worth 64 words: Long-term forecasting with transformers. In International Conference on Learning Representation, 2023.
Zhang, T. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research 2, 2002.

---

Generalization Analysis for Non-IID CRL
Zhu, Y., Xu, Y., Yu, F., Liu, Q. Wu, S., and Wang, L. Deep graph contrastive representation learning. In ICML. Workshop on Graph Representation Learning and Beyond, 2020.
Zou, X. and Liu, W. Generalization bounds for adversar- ial contrastive learning. Journal of Machine Learning Research, 2023.
12

---

Supplementary Materials Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings
A. Table of Notations
Table 2: Table of notations for quick reference.
Notation
Description
Basic Setups
Let X' be the input space and C. be the finite set of labels endowed with the probability measure
Let S = (() be labeled dataset sampled i.i.d. from distribution over X' x C.
We fix class of representation F, for every C, we have the following notations:
p(c)
The probability mass assigned to class i.e., the occurrence probability of class c.
D.
The distribution over X' of data points belonging class
De
The distribution over X' of data points not belonging class
Se
The subset of S that contains instances of class
S.
The subset of S that contains instances not belonging to class e C. S. = SYS..
x /
The ith and jth elements of S. and Sc, respectively.
Seaf Sej
The shortcuts for f(xx())
( and f(x)))
(e)) where f F, respectively.
N
Number of samples that belong class We have N Bin(N.
No
Number of samples that does belong to class c. No- - N
Ne
Number of possible i.i.d. tuples with positive pairs class c. N min /2], [N.[[N]])]]
Ne
N. = Ne).
fo F = xxxxtxxxx) (1x))) of F loss function class.
lo F
Combinatorics
[n]
[n] (1,2..... n) where E N.
S[n]
The set of all permutations (shuffles) of the indices set [m]]
[m[n]
The of all permutations of m elements from the indices set [n].
[m(n]
The of all combinations of m elements from the indices set [n:]
Datasets & Auxiliary Datasets
13

---

Generalization Analysis for Non-IID CRL
T
The of all possible valid tuples. T Usec Te-
T
The set all valid tuples whose anchor-positive pairs belong to c (Eqn. (20)).
Tea
The set of i.i.d. tuples whose anchor-positive pairs belong to c E C (Eqn. (21)).
Fid
The set of all vectors including anchor, positive and negative samples from T, (Eqn. (22)).
Tuu
The subset of tuples sampled i.i.d. from distribution v T (Eqn. (52)).
The discrete distribution over T such that r(T)
N /N if Te-
Risk, Empirical Risk & U-Statistics
Let l: 1R [0, MJ be contrastive loss function and JF be a class of representation functions.
e ( -
(f(c)
(fu( xx? x
Lun())
Lfn Beap wD
1(x)
p(c) (flc). (nnn(()))
x
Ux(flc)
UN(flc) = [Tc 1. Σ jINEEP,INE1 e (Vo.. US.s Saal)=)) if if * Ø.
IN
Ux(flc)
ux(flc) = (x(flc) if * Ø and (x(ccc) = O otherwise.
Ux(()
Ux(f) = Eosc N (x(fec)
E(f: Taub))
[(f; Taub) Trun E(x),x) (3, JT.n ((f((x) -fx)))) f(x57)1]
Fu
Bu arg (minferUss())
faub
faub arg minjer L( Tsub).
Notations for Rademacher Complexity
In the following notations, suppose that we have a distribution P over input space Z.
Let S (z1.... k be drawn i.i.d. from P and let G be a function class.
En
Σ, ,
, is the sequence of n i.i.d. Rademacher variables.
Rg Ree
A random variable depending S, Σn and the class G. R S.E. suppee 1 - o39(zz)
Rs(9)
The empirical Rademacher Complexity of 9 restricted to Rs(9) EE, R.
S.E.
when n 2
and Rg (G) 0 when n = 0 (in other words, S = Ø) The expected Rademacher Complexity of G. RG) Es {9)
(G)
Specific Rademacher Complexities Used in The Main Results
T-lld Ene
Tdld Ex.
EN of [022 fans f ) k+t
R
supfer
+. Ei
E IEE..IS..
This INe
when No >
Ry.zae (fo FF)
Ryza (fo
when N
Ry. (lo
RN F) ESIN: [Riyiaa ( FF]
14

---

Generalization Analysis for Non-IID CRL
Constants Estimators
k
The numher of negative samples.
M
The upper bound on the unsupervised loss function é R +. Bound on input's e norm. Vx S: | < with probability one. The 2d -Lisshhtt constant of the loss function L: R - I++.
7
Pmin
Minimum class occurrence probability Pmin min.ec p(c).
Piaax
Maximum class occurrence probability Pmax max.ec p(c).
A
For 8 (0, 1).
3ln 4/C///
Npmn
N
N. max
1 min
Note)(1
NO
N0-deD1--N) }}
2
k
Ñ
Ñ Minn
Pwin
Panas
2
Class of Linear Functions
Fin x Ar A Rdxm
|AT 22,1 a, lAllo & s).
1 1,,1
For A RRdxm | Ei |A, i.e., sum of column Euclidean norms.
For Idxm |Allo the spectral norm, i.e., the largest singular value of A.
Class of Neural Networks
FA F FL-10 where
8o (A4)) A Bi).
L
Number of layers in the neural networks.
do
Dimensionality of the input layer.
d [4]
Dimensionality of the h hidden layer.
s, [Z]
Bounds on the 7th layer's weight matrices' spectral norm.
B E [4]
Space of (th layer's weight matrices. Bi A Rd 1xd; |A & si).
/ [L]
{2 e--Lischitz constant the 1th layer's activation function.
pi,ee [Z]
s : Rd Rd is the 7th layer's activation such that Vx, x' e (Rde - x(xx)|l2 & & x/122
Covering Numbers
Let = g: Z - Rd be class of http//eetoo-valueee functions (with d 1) from an input space Z.
Let S (Zi...., 2n < Z be dataset.
N(G.e, --I
The covering number of class & with granularity e with respect to a norm Specifically, if there exists (minimum internal) cover Cg g
where Vi G,3ʃ Cg || 9l e, then |Cgl N e, II).
Vg.ge g: : lgg وlL = دリー ( g(2;) 13 1/2 Vg.ğe g lgg (1l....a5)) es [g(z,) g(2
|| (Lx(S)
|| It
15

---

Generalization Analysis for Non-IID CRL
B. Useful Notations
Notations on datasets & tuples sets: As a reiteration the main text, we lay out formal definitions for the notations drawn i.i.d. from joint distribution |=1 j=1
used throughout this work. Suppose that we are given a dataset S = over the input and label spaces X' C. We denote
Usec Se where S. the set of data points belonging to class c:
S. (x
ES:))
(19)
With a slight abuse of notation, we also denote Se as the set containing only the data points (without labels). Furthermore, for each c E C, we also define S. = Sr. i.e., the set of instances not belonging to class c. For every C C and f E F (where is the class of representation functions), we denote:
1. o = [S _ = |S. and N₂ min( (N,.
2. x; as the 7th clement of S..
(c)
3. x
(c) the jth element of S..
4. f(x) (0) fer and f(x)=)) fei for notational brevity.
Let T = UcEc To where Te denotes the set of tuples whose anchor-positive pairs belong to class E C. Formally:
Vee C Te = { (
(
j1, < N 1 < 4 4a < No.
(20)
Additionally, for all e C, we also define T:lid as the set of independent tuples selected in a "greedy" way such that every tuple in Trid has an anchor-positive pair belonging to class (See also Figure for visual illustration). Formally:
e C: Tedi
={
{xxxx 1 X2j (c) Xkj
(21)
Furthermore, we progress through the proofs, we also often use the auxiliary datasets Trid, which contains all vectors including anchors, positive and negative samples from the tuples set Tiid Formally:
Vee C: Frid
U
(22)
TETRa XET
2. Notations loss function class: Let é 1 - [0, MJ be contrastive loss function and F be class of representation functions. With slight abuse of notation (of the composition operator "o""), we define the class of loss functions as ( F formally as follows:
Co Fo
e (1)(x) ((x))) :Se))
(23)
3. Notations related to Rademacher complexitites: Now, we are ready to formally define the quantities related to Rademacher complexity used throughout the proofs. For the following definitions, we use the notation Ex[-] to refer to the expectation taken over the distribution of random variable X and [-] to refer to the conditional expectation over the
distribution of X conditioned on another random variable Y. For every e C, let En. = fol....,NN. {
be the vector of
N. independent Rademacher variables and Tiiid be define in (21), we have:
RJ
T!!! EN.
sup fef
1 N- of
Σ
- Saaj-k+i k ) (foee)
(when N₂ > 1)
N
j=1
EEN, S.N!
E
RS.
T EN.
when N.
(24)
A (foF)
(Empirical Rademacher Complexity)
0
when N =
Hy. (lo F)
=ESINg RRyya (f F)].
(Expected Rademacher Complexity)
16

---

Generalization Analysis for Non-IID CRL
The vector N (Nr esc represents the sample sizes and N Multinom(N, (E() Hence, though denote Hy (eo the "expected" Rademacher complexity, it is still random variable due the randomness in N. However, we will see in subsequent proof's of the main results, we will eventually handle the randomness by analysing the concentration of N around the respective expectations [Np(c))eEc.
Throughout the main results, we will often encounter the assumption that for all C, the empirical Rademacher complexities Ryyuaa (l F) are upper bounded by some Ky, depending on both the class of representation functions F and the class c. In this work, we use Dudley entropy integral bound to derive the upper bounds K, Specifically, by
Theorem F.3, for any choice of a > 0, we can generally upper bound N Ryya yua (f F) by setting:
M In 2N o L, )de,
Ky.e = 4a + 12
where ((eo F, ( is the L2 covering number of the loss class l o F restricted to the vector dataset Foid (See definition D.11 for the formal definition of L2 norm).
For more comprehensive summary of all the notations used throughout this paper, we refer the readers to Table for quick references.
C. U-Statistics Revisited
In this section, we revisit the definition of U-Statistics and the decoupling technique which will be used throughout the proofs of the main results.
Definition C.1. (U-Statistics) Given S { x., drawn i.i.d from distribution P over X. Let h Xm IR be symmetric kernel in its arguments. Then, the U-Statistics (n(h) used to estimate 0 Ex pm [x(Xx,,..... , defined as follows:
Xm)]
(h) = (m
Σ
Xim);
(25)
where C.. [n] denotes the set of m-tuples selected (without replacement) from [m] without order (m-combinations)) We call U, (h) an oae-sample U-Statistics order m. Furthermore, let = |n/m], the decoupled form of U,, (h) is:
Un(h)
Σ V=(S),
n!
rES[m]
(26)
1 g g
V=(S) = Σ
h( (mx ... x [mmi))
Remark C.2. For any igiς g, we can write (h) 4 EmeS(n) ((x+(mi- Xx(me]). Specifically,
n! Σ TES(m)
h(xx(miim+11)) ..... Xn(mi))
Σ
(n - (-)m))((xx,,,.... Xjm.)
n!
fu e [ [n]
1
Σ
m!(n m)lh Xim)
n!
im CCn [n]
1(Xi Xim)
n
Am CCm [x]
Eqn. (25)
Hence, by swapping the summations, the decoupled formula of Un(h) can be understood summing the same quantity a
17

---

Generalization Analysis for Non-IID CRL
times then dividing by g:
4
4
h(
x (mi (mi-m+1];- [ms]]
Σ
h(x* [mi-mm))+)) ... [mmms)
n!
9
9 NES(n]
[n]
Eqn. (26)
Un,(k)
Un(h))
D. Generalization Bound for Empirical Risk Minimizer of U-Statistics
D.I. Formulation of U-Statistics
Let Nç = min ( 2]. [ /kl). which represents the maximum number of valid i.i.d. tuples that can be formed for contrastive learning from the pool of training data. We restate the definition of the U-Statistics for L (fle) as follows:
(x(flc) = 1 2N
where (N(flc)
E
(( - Seu))]
(27)
IT
[C....4EC.[NE]
From the above equation, when N. 0, there is no valid tuple where the anchor- sitiior-oosiiveeeee pair belongs to class c (either the number of instances from class e or outside of class e is not sufficient). In such case, we adopt naive estimate Ux (flc) = 0. On the other hand, when N. 2 1, it is natural to estimate Lua(f(c) as the average loss over all valid tuples (not necessarily i.i.d.) where the mnchor-positive pairs belong to class c. Finally, we define the overall U-Statistics for L.un (f) as follows:
Un(5) Σ No OEC
N (x(ccc).
(28)
Remark D.1. is worth mentioning that the above formulation is asymptotically unbiased, i.e., limn Un(J) Lun(S). To demonstrate this briefly, denote N as the event that for all classes, there are enough data points to form at least one tuple, ie.. ie., (Ye > 3 Hence, limn P(N) = 1. Furthermore, we have:
(() = P(A) + P(AN)(
= P(N)E
Σ
N
N UN(FIO/AN PANTENU
=((N) Σ p(c)L (flc) P(N"))IN(())))
OEC
-P(N)Lun + B[4W()))N
IJ) as
N - 00.
Remark D.2. Let UN(flc) be defined in Eqn. (27). With similar decoupling argument to de la Peña & Giné (1998) and given that N. 2 1, we re-write Ux(flc) follows:
Ux((lc
Σ
(flc),
N X No
TEESIN I.F.ESIN.
(29)
where V=..=c (flc)
Σ ((
Sam. Se,n. )
No j=1
where S[n] { [n] [n] ग bijective denotes the set of all possible permutations of the indices set [x]] for any E N. Vo., (flc) is the average over the loss evaluated on the set of independent tuples T.lld [T.. #e] selected follows:
18

---

Generalization Analysis for Non-IID CRL
1. Shuffle the of inputs Se according to the permutation Te E S[ denote the resulting set Sc(me]]
2. Shuffle the of inputs S. according to the permutation n.. S[N denote the resulting set as S.[
3. Pair 2-element blocks from S.] to k-element blocks from S. until either set runs out of independent blocks.
x (c) Te Te. Te] {xx/00 121--- 11125-111 R.1251 Relks
x
N: Rclkss) "-
(c)
(30)
Essentially, the formation of the tuples set Thlil TT F.] is identical to that of T except S. and S. are shuffled according to permutations Te and Re beforehand. To briefly demonstrate how the representation of U-Statistics Eqn. (29) holds, for any two data points in x2 E Se, we define:
(c) (c)
h(x (c) J1 xxx)
E (nndde
[a
(31)
Σ
[Fess Jes.lkm-ktal )rmn)
N.1
*.ES[NE]
for any m & Ne (by remark C.2), Then, using the same decoupling argument de la Peña & Giné (1998), can as follows:
write UN(fle) as an average over l(xx) (0) (e))
Ji x $2
UN(fIC) = P2[No]
Σ
Mxx (c) (c)
31 x32
Σ
(c) h(x 125-1]
x x2
N
[[ES[N]]
Σ
T.E[[N2]
[.E[[N]]]
N. N (Jonn.B-- [emd111 - SeR.111-k+s)) (
N
S [
j=1
Remark D.3. Let be real-valued function. For any distinct pairs of indices re-arrangements ne, To e S[N+] and Rer Re E S[N]], we have ESIN? g(V (( = ss g(Vng,rg (flc)).
D.2. Proof of the Main Results
Lemma D.4. <p RR - R be convex, non-decreusing function. Let N (Nt)eec ~ Multinom((N (E()) be the multinomial random variable representing the class-wise sample sizes. Suppose that N. 2 1 and EN. denote the sequence of N₂ i.idd. Rademacher random variables. Then, for every c E C, we have:
E
SINt
( sup fef
UN(flc) - TTmn([lee))] B. IN
2R
Tiid Dec
(32)
where ESI denotes the expectation taken over the sample S conditioned on the random variable N and the random variable RJ Tud En. defined Eqn. (24).
19

---

Generalization Analysis for Non-IID CRL
Proof. We have:
ESINE (0( sup fEF
- - [nnn(//o)
S 10
sup TTel
1
Σ
[e(tton [Jess - Sas fai))/1 Tuu (f(co
fer
Jisiee [NN]
4 [NN
N! 10
sup feF
Σ
V Vflc)((fcc) Lun (f(o (flc))
No! x No!
S[N I
Es N!! 40
sup /eF
Σ
(Triangle inequality)
No! x No!
ESI ESIN1
Σ
sup FEF
V Ve Lun (f()
sup
sup, jp non-decreasing
!o! x No!
1
Σ
E SIN
90 feF
sup
V M. (flc) (Sm(
(Jensen's Inequality)
No! X No!
T.ESIN ESIN
sup JEP
N.
e (1
Ja2s
Sa
k+i 1 )/rm) (
(Remark D.3).
N
j=1
When conditioning on given sample size o class c S. an i.i.d. sample drawn N N times from the distribution
De. Hence, for any 1 < j & Ne. we have ESN ( (1122--1 [ - fans- )}=,) Lun Lun(flc) (flc). Therefore, by the symmetrization trick (Lemma F.6), we have:
E S ( sup fef
Ux(flc) - Lun((ll))]
N:
((rres-1[1o2) Sans Saus-kttl (aass-ko])] 1/.1) Lun (S10)
ESINT 10
sup fer
N
Tels Exe
< E EN..NN 1
2
Hence, obtained the desired bound.
Proposition D.5. Let N Yeec Multinom(N, (((c) be the multinomial random variable representing the class-wise sample sizes. Let F be class of representation functions. For any ö E (0, 1), the following inequality holds:
In 2/8
sup fer
Ux(flc) Lua (flc) o 8MM
N
> 21-8
(33)
2N.
where N. max(1,NN) and (e F) is the expected Rademacher complexity (Eqn. (24)).
Proof.
We divide the proof into two cases when N and when N >>
1. When N 0: Then, we have UN (flc) = 0 by default and sup (N(C)c) - I Inm( & M. Furthermore, since
8M4
2/6 4M, the bound holds trivially.
2
20

---

Generalization Analysis for Non-IID CRL
2. When N₂ 1: By lemma D.4, let sfx) exp((x) for l O, we have:
E SINT exp (isup Ux([lc) - Lun (fn(() & I. exp (21R Tell 2Ne
JEF
3212
exp 1eo
(Lemma F.))
Nc
Using Markov's Inequality, for any À >> 0, we have:
P sup fEF
Ux(flc) Tun (Slc) A/5²) - IP
exp
tsuu EEF
Ux(flc) - -mmn(floo) > a
cut No
& e B SIN: sINNt
exp
(tsup
UN(fle) - - f5F
Lunn(fll)
321² M22 t1 tA).
< exp
2t9RN
Ne
Setting 8 cxp (2tRN. (e F)+
M2 No
t2) and solve for X, we have:
32tM²
In 1n8/
== 2nx, (eo F)+
No
/N, Ia 1/5
Using the Lagrange multiplier to solve for the optimal value of t, we have t to the formula of X:
Plugging the value of back
4Mv2
In 1/8
UN(JlC) - (ua( & (eo + +8M = (2o, + +8M1
sup fEF
2N
In 1/8
2N,
2n2/8
29r, F) + +
2N,
with probability of at least - 8, as desired.
Lemma D.6. Let N Multinom(N, (oE)) be the multinomial random variable representing the class-wise sample N N p(c) & p(c))
sizes. Then, for any 8 (0, 1), the events
3ln2/C18 hold simultaneously for all with probability
Npmi
of at least 1 8. In particular, the same high probability event:
N
3ln2/c1/8
p(c) <
(34)
N
Npmin
Proof. Recall that N p(c)N, Hence, E[ Ne(c). Then, let 0 < X < 1, by the two-sided multiplicative Chernoff bound:
N+ P
p(c) > Ap(e)
-P( Nole) > ANp(c)) 2eep
x2Np(c)
N
21

---

Generalization Analysis for Non-IID CRL
Then, by the Union bound, have:
N+
N
mloa))
P
p(c)
A
P
p(c)
N
N
eEC
OEC
N
p(() P(ODA)
P
N
OEC
x2Np(c)
Σ oEC
exp
2 Pmin
2/C| exp
3
Setting = 2/c|es) exp (-
we have
3ln Clia
Therefore, with probability of at least 1-6, 6,
3
N Pintn
N
Σ eEC
p(c)
Npmin
and the events Proposition D.7. Let F be a class of representation functions and Ju = arg min be the empirical minimizer of the U-Statistics (Eqn. (28)). Then, for any ō (0, 1), with probability of at least we have:
No N - p(o) & p(cly 31 2 C1/8 Npmn
hold simultaneously for all c E C, as desired.
3 In 4C///5
In 2////
Lun(fi)
inf Lua (f) & v fet
+ e(e)
12x (foF) 16M
(35)
Npmin
2Ñ.
eEC
where No max {1,
min min (1
[Nolela-Aa N(L-0Ch(1-A) })
3 1//// Npmin
(cf. Table 2) and BN F) is the
V
expected Rademacher complexity (Eqn. (24)).
Proof. From the definition of UNy we have:
Lun Pis) - inf [ & 2sup
Ux(J) - Imn[[]
(Uniform Deviation Bound)
JEF
fEF
N
2sup fer
Σ
UN([lc)
Σ P(e))tun(F1
N
cEC
aEC
2 sup
Σ (x(c))) C&C
N ple)
+ Σ
E(oo(uu(((c) - Lann(Fl))
feF
oce
N+
2 Σ
sup UN
p(c)
+ Σ p(c)
sup (N(cf -Lmn(
<EC feF
N
feF
cEC
N+
< 2M
p(c)
+ 2 Σ
p(c)
sup fef
(x([lc) - [1o
N
oEC
Let 8 E 10 and A
3 ln 4
By lemma D.6, we have:
N Pmin
N
3 3ln 4/C1/8
Σ CEC
p(c)
A,
(36)
N
Npmin
22

---

Generalization Analysis for Non-IID CRL
with probability of at least 1 5/2. Furthermore,
p(o) < p(c)A holds simultaneously for all e C with probability N N
1 6/2. Hence, by the triangle inequality:
N N
No Np(c)(1 No > N(1 (())((c)(1-M))
> pl) - Ap(c)
simultaneously for all e C with probability of at least 6/2. Therefore, we can estimate N₂ with probability of least
1 6/2 follows:
No(c) A)
N(1 p(c)) A) D}
No No + max 1, min
(37)
2
By proposition D.5, we have sup fer (f(() - Lun (flc) <
SMV
2/ 2N.
with probability of at least - E
for & (0, 1). Then, by the Union bound, we have:
In 1//////
Σ p(c) sup (x((lc) (un() < e())) 29n (Lo 2 + M
p(c)
(38)
fEF
2N.
OEC
CEC
with probability of at least 1 - -/22. By inequalities (36), (38) and Union bound, we have:
In ||//
Lun(Fu) inf Lua (f) & 2AM + Σ
4NH (eo + 16M
2N.
aEC
In 4/1//8
& 2AM+ Σ p(c)
49. (lo + 16
(Eqn. (37))
2Ñ.
aEC
3ln 4/C1/8
In C
2M
+
49ix, 49ix (l 16M E(e) p(c)
Npuin
2N.
with probability of least 8. Hence, we obtained the desired bound.
Remark D.8. The above proof relies the assumption that A because of the of multiplicative Chernoff bound. In other words, Npmin In 4|C]/6. However, when we have A > 1, the right hand side of the bound becomes greater than or equal 2MM which already larger than the largest possible value for Lun (fu) je feFF Lun(f). Hence, we can safely remove the assumption that A (0.1) from the result of the theorem.
Remark D.9. Let A
3 1/C /8 Suppose that N >
G 4/C//
We can further simplify the high probability (of
Npain
min Eigin lmeaas)
at least 1 8/2) lower bound for N Firstly, we have:
In 4/C//8
min
Piiin 2
I- Oanax
Npmin
2pmin
2
Note that for every C. we have p(c) Pmiin and p(c) Pmax where Pmaax probability of at least 6/2, have:
max.ee p(c). Hence, with
Npmin (1 ---1) A)
N(1 A)(1 Pmma))
N. max
min
2
k
Pmin
1
Pinax
max
1,
N(1 A) min
(39)
2
k
Pmin
- Pmax
N min
4k
23

---

Generalization Analysis for Non-IID CRL
and for all > 1. Then, by the initial assumption on the lower bound of N, have In 4 1. Therefore, with probability of least - 6/2, our final simplification for the lower bound of N. becomes N, > min
since
N Wmin
Cuni 8
Paunx 1k
Puii
Piaa
for all C
4k
Theorem D.10. Let F be class of representation functions and fu arg minger Ux(f) be the empirical minimizer of U-Statistics (Eqn. (28)). Suppose that Rt F) N. K5 where K5,c depends both the function class F and for all e E C. Then, for any E (0,1), with probability of at least 1 - 6, we have:
In 8//8
Lun (Bn) inf T (nm(s)) & 200)),,44MM
(40)
/EF
2Ñ
1-pmax and Ry Tual o the empirical Rademacher complexity of the loss class restricted to the set of independent tuples Tidd (Eqn. (24)).
where Ñ N min
(Cain
Proof. Fixing A (0, Let
V
3 31u AC/A and suppose that N >
6 4/A/AA
Then, A and the events
Npain
min Cogin 1-Pmax
N. > N/4 hold simultaneously for all c e C with probability of at least - 2 (Eqn. (39)). By proposition D.7 and the
assumption on the lower bound of N, for any value of (0, 1), we have:
ICA/A
Luu (fe) inf Lun & 2AM+ Σ p(c) fer
Ed(c)
4N, (loFF + 16M
2N.
CEC
$ 2AM + 16M
Σ Rcc) (lo
Ñ
3 In4/CA/AA
2 2In4/C/
-2M
16Mg
+ 4 > ((c)
Npmin
CEC
(41)
3 /////
C N
42M
16M
Σ ((e)
2Ñ
2 In 4/C//A
< <18M
Σ
((oF)
Ñ
aEC
In / A
36M
Σ
(Eo.F)
2N
aEC
with probability of at least 1 - A. By lemma F.2 and a Union bound, we have:
In IC/A
En(c)oi. (co ((e)
Ry. (6o Rt () My
2N.
oEC
cEC
In ICIAA
$
> p(c)
Ryya F) + +M
(42)
2Ñ
ICI/A
MM
Σ p(c) (lo
2N
CEC
24

---

Generalization Analysis for Non-IID CRL
with probability of least 1 A. From Eqn. (41), Eqn. (42) and Union bound, we have:
In 4CC//A A
In Cl/A
Lun (fe) inf fEF
Lum (f) & 3
8M
((c)
2N
2N
4/C//A
1
+
4
p(c) (F
2Ñ
CEC
In 4/C//A
Kf,c
V
Σ
p(c)
2N
VN.
CEC
4/C/A
E 4
K(c)
2N
N
CEC
with probability of at least 1 2A. Now, suppose that N
6ln
or Ñ 6ln 4C//AA Then, have
min
/n4/C/A M
44MV 12" Therefore, the right-hand-side Eqn. (41) will be at least 22M/ which is the greater
2N
than the largest possible upper-bound for L (fu) yer Lun(f) Hence, the inequality in Eqn. (41) holds regardless of the assumption on N. Finally, setting A 6/2 yields the desired bound.
D.3. Applications to Common Function Classes
In the results that follows, without reiteration, define for arg min (fx by default. We will use covering number and the Dudley entropy integral bound (Theorem F.5) as the primary tools for bounding empirical Rademacher complexities. Firstly, we define the following metrics defined on function spaces:
be a class of real/vector-valued functions (with d 1) Definition D.11 (T22 and T metrics). Let 9 {g - _
from an input space Z. Let S (zi....,,,,, Z,, Z be a dataset. Then, the L2 and Log.2 metrics defined for any two
functions 9, 9 is defined as:
1/2
1g -6911 =
19(2,) - 3(2,)13
(43)
lg - Ø (9)
max 2,ES
[ ((2z 5(2,)1l2
Lemma D.12 (Hieu et al. (2024)). Let F be class of representation functions f X + Rd. Let l R² - R+ be
contrastive loss function which is f -Lipschitz with constant 1) 0 and S { (x,,, x.I.....,
(in....,jT)) x5k) أ-ز x be
given set of i...d. input tuples. Then, let E. o F denote the loss function class and O, we have:
(o < InN F, -.
(44)
where š X is the set of all vectors including anchor, positive and negative samples and I =sup fer lf(())l2
D.3.1. LINEAR FUNCTIONS
Proposition D.13 (Ledent et al. 2021; Hieu et al. 2024), ). Let be R4, be given and let X = R.m. be an input space where
m > 2. Define FF as the class of functions f X + Rd as follows:
F= f + Az A mdx 11 & aa).
where d 2 2. Given dataset S {01 ( InD E X" such that |2i12 & b, siE n. Then, for all e 0, we have;
64a26²
(1lco) +7) 7)ndd
(F,
In
(45)
2
25

---

Generalization Analysis for Non-IID CRL
Remark D.14. For proper credit, the above proposition is a consequence of the L covering number for linear function classes from Zhang (2002).
Theorem D.15. Let a, 8 R be given and Fin be the class of linear representation functionss (also defined in Eqn. (17)),
defined as follows:
Fin = x Ax: A Rdxm |AT & a, |A & $s.
(46)
Let Ñ = min
Pmin 2
Pmax
and |x|2 & 6, Vx E with probability one" Suppose that the contrastive loss function
k
:: I - M) is 10 Lipschitz with constant > O. Then, for any ō E (0, 1), with probability of at least - 6, we have:
Lun Lin
inf feJin
Lun (f) &
32
+
1
In 8/C/
+
Nv N
2Ñ
(47)
3072 2nsab²
In (44NNsabb + 7) (( + 2)d) In(NM).
Proof.
Given certain class e E C. Suppose that Ne > 1. In other words, the set of i.i.d. tuples whose anchor anchor-positive pairs belong to class G, Telld, is not empty. Let Told be the set of all vectors including anchor, positive and negative samples from Tridd Let Te = sup JeupfeFunne xe [x)
For any > 0, we have:
(eo Frin L2((Tel)) In
Fiim 4r
L I (Teii)
(Lemma D.12)
1024nja
[AAnTTaad
In
+
No(k: + +2dd]
(Proposition D.13)
2²
1024n)s&aa*
2b
44msab²
In
+ 7
N(K 2)d
(Te < sb, Ve C).
22
Let N Without loss of generality, assume that No o Theorem F.5, we have:
Frin,e, e,
La((Teid) 2 for all & & M. Then, using
12 M
Ryzall (e Flin) & +
V
(2
Flim, e, Frin
Le(T. de
VN Ja
12
20481 ²²
44nsal2
< 40 +
In
+7
N(k: + 2)d
de
Noo Ja
384 2nsaba
44nsab2 a
M 1 1
4a
In
+
N(k + 2)d
-ee
VNe
e
384 22nsb²
44nsab2
4a
In
+ N(K + 2)d
In(M/a)
VN.
384v 2nsab²
444Nsabb² +7 +7) + 2)d) In(NM).
+
N
VN.
Setting In ((AANnsaa + N)N N(k + 2)d) (N( の for brevity. Then, for all e E C, we have:
4
384y 2nsab²
Ryyal (lo Fin <
VN.
"The bound input's with probability one imposed that for any draw of hound the T. covering number of Fin restricted to any subset of using proposition D.13 with the same value
26

---

Generalization Analysis for Non-IID CRL
Then, by Theorem D.10, setting K5 * + 3848 (obly2nsbb for all have:
32
8|
3072 2
In ((4ANnsab + 7) (2)N((= 2)d) In(N.),
Lun(Fu) inf feFFin
[fn(f)
NV
2N
VN
N
with probability of at least 1 for any ò e (0, 1), as desired.
D.3.2. NEURAL NETWORKS
We are interested in the following class of neural networks: Let be natural number representing number of layers. Let da, di,.... dr. N such that di 1, 44 < L be layer widths. Let 81,-..,88 be sequence of real positive numbers and define the following parameter spaces:
Bi {Aw) Rdi-ixd 1| $1)
(48)
where lo denotes the spectral norm. Denote A= B1 x By as the parameter space for the class of neural networks FA (also defined in Eqn. (18)), defined as follows:
FA = FL-1
(49)
where for all < < L, Fi = P0: o Vi such that:
1. Rd - Rd: is L-pischhitz activation function with constant & fixed priori.
2. Vi 1 10rx: A e Bi represents the pre-activated linear layers.
Lemma D.16 (Long& & Sedghi (2020), Lemma A.8). The internal covering number of a d-dimensional ball with radius denoted as By with respect to any norm || can be bounded by:
d +
N (B,, c11- <
3x
3R &
(50)
c
Theorem D.17. Let F.A. be the class of neural networks defined in Eqn. (18). Let Ñ
Nmin
(Qmin
1-pmax Panax
and
|x||a & b, Vx E S with probability one. Suppose that the contrastive loss E 12t R, is 1 Lipschhitz with constant > 0. Then, for any 8 (0, 1), with probability of at least 1 5, we have:
32 NVN
8/8/5
W. 192M
L II
E2 sm + 11)
Lunl inf Iun(f) ferA
+ 44M
In 12n Ñ
(51)
2N
m==
where W- - di is the total number of neurons the neural networks.
Proof. Let A H4 set of weight matrices from the parameter space A and we denote FA E F-A network parameterized by A. In other words,
nu as the neural
FA pr. pr
Vx X.
Additionally, let 1 & 4 <4 & L. define Fl as the sub-network from layer 4 to lg. Specifically,
Fh- (z) 1p12 (A(l)) (-
Vz -41
27

---

Generalization Analysis for Non-IID CRL
Let A 14 A be another set of weight matrices different from A. Additionally, for 1 1 L, define À = (A(11). .........)), _t..... A as the set of weight matrices obtained by replacing the 1th to the 1 elements of A with those of Á. Then, for all 1 & & L, we have:
F ++ (+ (z)
-F Vze R4
À
ActI
F F2-1-1(x4 (x) = -(111-(x); V X
Given certain class C and suppose that N₂ 3/ 1. In other words, T:id Ø. For any E 7.id and $ l & L, we have:
x2 (x) - (x.n(())
p
[1 1 o
(Al))
pol
A.
Ar+1
Acti
E1
9m9m
A (xx)
(x)
1100 111-111110 (x)
À,
Att1
m=1+1
L
A A(0)
| (x) 1
4)
Em 8m
m=I+1
L
51
5m 8m
AAl) A
|xX||
Sn
m=/+1
AA1) - 500
8m
81 mm1
By the triangle inequality, for all x Tudd we have:
F - (x)
F (x) - FA (x))
L
E 11A - 1|.
<
5. Sm
St
m-1
Let > 0 and EL be sequence of positive real numbers such that e = Σ/=1 Ster where Σi= == 1. For all 1 & & L, we construct an internal ei-cover, denoted as C(B,, with respect to the || lla norm for the parameter space at the 1th layer, Br. Let CA _ C(Br, be the Cartesian product of all constructed covers. Then, for all A {1 1 A, there exists A {A
L CA such that:
FA FÁ l
max FA - FA (x)
x
2
A00 ||a
b
mm
m-1
Et
b
mm Sm
S1
m-1
For each 1 & 1 & L, setting ê1
Bigge
yields FA - F2 I1... S.. Hence, CA becomes the e-cover for A (or
D1l 8m
28

---

Generalization Analysis for Non-IID CRL
equivalently, Fill with respect the 1,, (Teii) metric. Setting B1 L- for all I [L] 4, have:
In (
2
Σ In En
381
di In
+1)
(Lemma D.16)
E1
3b -T 11 Em Sm
Σ 1=1
di In
+
Bic
3Tb II I=== Em8m +1
WI
Let N-1 and P. sup t [F(x)]
Without loss of generality, assume that v(eo FA o Iz(Tehit)
for all a & é & M. By Theorem F.5, we have:
12 M
Ryzal ( F(ht 4a
2lnN (eo FA Le((Tii)
VN.
12 M
4a
21nA
FA hn
(T de
(Lemma D.12)
VN. Ja
4nIe
12 M
12nLT bb I Em8m
& 40
2W'n
+ +1/ee de
VN. Ja
12 M
12mLb² I
62 52
L
< 4a
2W
+ de
(Te <
Smimi Vc C)
VNc
40 + VNc
12 (M (M-a))
1 2W
L2
m==1
L
Sm
22
+
+ 12M
2W
In
12n II
S $2 +1
Ne
Then, all C C, we have:
Rysd (fo F(A &
4
24M
W
122/NTb2 I
I.
2
+ +1)
2Nc
Let Ky,a $ + 22 Win (12/NTAP I Sn 2n + +1) for all c C, applying Theorem D.10 yields:
Lun(fu)
inf fer
Lun Lun(f) &
32
+ 44M
In 8|8/8
192M
W 12
In
II
L
c2 22 + 1
NVN
2N
Ñ
Sm
with probability of at least 1 - for any 8 e (0, 1), as desired.
*Even though Lagrange multiplier to solve for the optimal values of (i, these values only present in logarithmic terms. Therefore, we can afford to be somewhat less "strict" with their selection.
29

---

Generalization Analysis for Non-IID CRL
E. Generalization Bound for Empirical Sub-sampled Risk Minimizer
E.1. Sub-sampling Procedure
Given labeled dataset S = (xx, )
j-1 Let T be the set of all valid tuples that can be formed from the datasct S and let To be the set of valid tuples whose anchor-positive pairs belong to class c. Then, we have T Usec To and [T] = >iec [Tl
where [Tal 2( (N (N- The procedure for sampling subsets of tuples described in Section 3.3 equivalent to drawing M samples i.i.d. from the discrete distribution over T defined
VT VTE7,CEC:v(T) = /
if T
(52)
Taub nM
In other words, for all ce C, the probability of picking from T tuple T whose anchor-positive pair belongs to class c is
u(T E Tol)
N N which an unbiased estimator of the class probabilities themselves, i.e., EN[u((T E Te))] = p(c).
E.2. Proof of the Main Result
a be the sample of tuples drawn i.i.d. from the distribution v over all valid tuples T. Let FF class representation functions and R R+ be an f Lipschitt contrastive loss function. For any f F, we define the sub- sampled empirical risk evaluated on the tuples set Taub as follows:
Let Tsub { x
M
5=1
1
Σ (
M
Tefi)) = M
-
(53)
Theorem E.1. Let F be class of representation functionns and Seub arg mingefF ((J;Teub) be the empirical sub-sampled risk minimizer (Eqn. (53)). Suppose that Ryzaa (f F) & No KF.e where K5 depends on both the function class and for all Then, for any d (0, 1), with probability of least 5, we have:
L (faut)) inf L (f) 4Di (lo
8 VN
xl(c)KF 6M
In8/8
44M
In 16/C1/8
(54)
FeF
2M
2N
esc
and Piga (fo o F) is the empirical Rademacher complexity of the loss class restricted to the set of independent tuples Thid (Eqn. (24)).
where Ñ = N min
Pmin
Pinax
2
Proof. Let A E (0, 1). By the uniform deviation bound, we have:
Lun (Pab)) inf Lun(f) 2 sup feF
Eu (ʃ: Taub) - Lmn(S))
feF
sup
E.m (J; Taub)) - (ms(1) + 2 ssu (2x(I) Ln)
fef
feF
With a slight abuse of notation, for any T (x, x Xi , E T, denote ((s(x)][((x)) - -(x)))
x5)
as ((T)
30

---

Generalization Analysis for Non-IID CRL
for brevity. Denote č = fce C: N > 1).
Then, we have:
T Pua( (o: Trubb)(s (TT NDM
Lun (f: (T)))-1)
1 M M J-1
((T))
simplifies to Ey ([(T][]
Σ (TT)((T)
TET
Σ Σ (TT))((T))
osc T.E..
Σ N N
((Ta)
ac
P.E..
Ux(f(e) (27) (27)
N
( = =U((A)
N
OEC
Hence, by Proposition F.3, for any choice of S we have with probability of at least A (with respect to the draw of Taub):
In 4/A
sup feF
(u: (J;Toub) - Ux(l) & TT. +
(55)
2M
In particular, we have P (Eqn. (55) does not hold) = Es Eqq.. (55) does not hold s)
< Es|A] = A: the overall failure
probability of Eqn. (55) is less than Furthermore, by Theorem D.10, with probability at least - A (with respect to the draw of S), have:
sup UN( - Lun(f))
4 VN
El(c) 22,M
In M///
(56)
SEF
2Ñ
EEC
Combining Eqn. (55) and Eqn. (56) using Union bound, with probability of least and Tsub), have:
24 (with respect to the draw of
Lun (aat)) inf Lun(S) & feF
8 VN .c
I4/A
+ 4&M
In8/C/AA
2M
2N
Setting = 8/2 yields the desired bound.
E.3. Applications to Common Function Classes
Without reiteration, we define frub = arg minjer Z(f; Tsub) by default. Applying the above result, we can easily obtain the generalization bounds for the common classes (linear functions, neural networks) by bounding Ryas (l F) using Dudley entropy integral (Theorem F.5) and applying Theorem D.10.
E. LINEAR FUNCTIONS
Theorem E.2 (Linear Functions). Let a, E R+ be given and Fin be the class of linear representation functions (also defined in Eqn. (17)), defined as follows:
Fin In Ax AE Rdxm
IATI2s $ aa Aal & 8).
(57)
31

---

Generalization Analysis for Non-IID CRL
Let Ñ min
Pmin
Pmaax
and |
< b, Vx E S with probability one. Suppose that the loss R
1R+ is
2
n -ippschit with constant > O. Then, for any ò (0, 1), with probability of at least we have:
Luu [sub)) inf [fa(
4
32
+ 3072v 2nsab> In ((4ANnsab² + +7) 2)d) In(NM)
feFum
M
NVN
VM
In8/
16//////
WW
+4M
2M
2Ñ
(58)
Proof. By Theorem D.15, for all C C, we have Ry.allo Frinn & 4NN1+ + N. $384 2osd/22 where e a logarithmic function of M,,, 7, a, k and d, defined by Φ In (44NNsab² + N) (K: 2)d) In(NM). Then, by Theorem E.1, with probability of at least 1 - for any ò E (0, 1), we have:
Lan((anb)) inf [fu(f) & RTaD (eo Flin) + 32 JeFun
3072 2nsab2 +6MV
8/8/5
In 16|C1/5
+ 44MM
(59)
NV N
2M
2N
Using Dudley entropy integral bound (Theorem F.5) in the same way as Theorem D.15, we have:
4
384y 2nsab²
NT.a (Eo Fiim) &
(60)
M
vM
Combining Eqn. (59) and Eqn. (60), with probability of at least - 8, we have:
32 M NV N
In 8/8
In 16
Lun (frub) inf Lun(f) m
+
+ 207222nsabt'
+
6MM
+ 44M,
feFin
VM
VN
2M
2Ñ
as desired.
E.3.2. NEURAL NETWORKS
Theorem E.3 (Neural Networks). Let L 3 and do, di....,d dp positive integers representing layer widths. For 1 1 L, let Bi = A())) ) Rdi- ||A & ss be parameter spaces where {si)t_1 is sequence of known real positive numbers and {4pt IR4 Rd] be the sequence of activation functions that are fixed priori and E -ipschhitz with constants (Ei)ten Let FA be the class of neural networks (also defined in Eqn. (18) defined as follows:
FA FL FL-10..... .... F1, where Fi = -Z-- m pp () :A E Bi}
(61)
Let Ñ = N min
Pmin
1- Panax
and |x|12 & b, Vx E S with probability one. Suppose that the contrastive loss & R& - IR
80 Lipschitz with constant > 0. Then, for any 8 e (0, 1), with probability of at least ô, we have:
Lum (feut) inf L (n) feFA
4
32
24MW3 Ind (12
11
2 sm + 1
M
NVN
N
M
m=1
(62)
In 8/8
In 16/C//8
6M
+ 44M
2M
2N
where W Ele de is the total number of neurons the neural networks.
32

---

Generalization Analysis for Non-IID CRL
Proof. By Theorem D.17, for e C, we have (PoFF)))F & 4N +N. Applying Theorem E.1 yields:
& 22MM's In (12n IIm
2 s +1)
24MWi
(121NTTIP
sm +
(aub) - inf (fn & RTas (l Fr)) SEFi
32
NV
N
(63)
In88
In
16/C/8
+ V
4
2M
2N
with probability of at least 1 - 8 for any 8 E (0, 1). Applying Dudley entropy integral bound (Theorem F.5) again for Rua (L FAA,, we have:
4
24MW
In
(121/NL
I1
S sm
+
To
(CoFA)
na
(64)
M
VM
Combining Eqn. (63) and Eqn. (64), we have:
Lun (Jsub))) inf fEFA
(nn(
&
4
32
+ 24MW3 Ind (121NT1
11
22 Sm
2
+
1
M
NVN
VM
m=1
In 8/8
In 16/C//1
6M
4
2M
2Ñ
with probability of least for any 8 (0, 1), as desired.
F. Classic Learning Theory Results
F.1. Rademacher Complexity
Definition F.1 (Rademacher Complexity). Let Z be vector space and 'D be distribution over Z. Let G be class of functions 2 [a, b] where a, b E R and < b. Let 5 [zi,..., } be dataset drawn i.i.d. from D. Then, the
empirical Rademacher complexity of Ç is defined as follows:
Rs(9) Ex,, sup 1 n Ti
Σ
(65)
where En = (ai,..., σn) is a vector of n independent Rademacher variables. Additionally, the expected Rademacher complexity of G is defined as follows:
Ri (g) = Es As(())
(66)
Intuitively, the Rademacher complexity is measure of function class' richness. If class G is sufficiently diverse, there is a higher chance that given random sequence of signs (represented by the sequence of Rademacher variables), we will be able to find function E G that matches the signs. Hence, the Rademacher complexity will be large.
Lemma F.2. Let Z be vector space and D be a distribution over 2. Let be a class of functions g Z [a. where a, be T and a < b. Let S (Zi,..., 2n) be dataset drawn i.i.d. from D. Then, for any e (0, 1), with probability of at
least 1 - 8, we have:
In 1/8
(g) Rs(g) (b a)
(67)
Proof. Let o: n - R2 be defined as x o( Inn) = Ex,
sup yeg 1 Σラ [ where 2 for all 1 & &
Then, all 1 < 1 & n, we have:
b-a
,( (4...,,
sup
zuz
7
33

---

Generalization Analysis for Non-IID CRL
Hence, by McDiarmid's inequality (McDiarmid, 1989), for any have:
2ne
R (Z1........ ................................ knd
-11 2n
2 s) & exp
(b a)²
(S)
(c(
Setting the right-hand-side to 8, we have (b V)v 1/6 and we obtained the desired bound.
Proposition F.3 (Rademacher Complexity Bound). Let Z be vector space and 'D be distribution over 2. Let G be class of functions Z - [a, 6] where a, b R and < b. Let S = [Zi...., Zn be dataset drawn i.i.d. from D. Then, for any e (0, 1), with probability of at least 1 8, we have:
1 Σ n
1m4/0
sup gEg
F EZ-D[g(2)]
g(zi)
(Rs(() 3(b axp
(68)
2n
Proof. Let Φ _ R be defined as ((I1,.... ,nn
sup geg
[g-D[g(Z)] g(.)) Using McDiarmid's
inequality, for all A (0, 1), the following inequality holds with probability of least A/2:
In 2/A
( zn) & Eso(zi..... 2nd + (b V)v
2n
In 2/A
$ (9) + (b (b-a)
V)v
(Symmetrization Lemma F.6)
2n
Furthermore, we have (9) & Rs(g) + (b /
2/4
with probability of at least 1 A/2 (Lemma F2). Hence, by the
2n
Union bound, with probability of at least A, we have:
In 2/4
Eg Ex-D[g(2)]
Σ g(x;)
& 29s + 3(b- - a)v
sup gEg
2n
Let ((T1....,,,)) = supgeg yeg other direction with probability of at least A. Hence, by the Union bound, with probability of at least 24, we have the following two-sided inequality:
- ((x;) Ez vl p[g(z)))))))) 2)] and repeat the above argument, we have the inequality in the
E [[])]
Σ g(2,) & 29gs()) + 3(b - a)
In 2nA
sup geg
2n
Setting 5/2 completes the proof.
F.2. Massart Lemma & Dudley's Entropy Integral
Lemma F44 (Massart's Finite Lemma). Given (z,...., 2nd an i.i.d. sample from a given distribution. Let G a finite function class. Then, we have:
2 2|
Ex.
sup geg 73
Σ ozg(
B
(69)
n
where Σ, (ai,..., on) is sequence of i.i.d. Rademacher variables and B sup
( Σ 11(2
34

---

Generalization Analysis for Non-IID CRL
Proof. For each h 9, denote On A ozg(z,). Then, for À >> 0, have:
A
sup hey n
0ig
(4))
x,
max heg
|0hl
(sup max due to finite g)
In exp x,
max [ Keg
In exp x,
max max -0h) hey
In Ex, exp
\ max
(mmaxmaxi max(On; -0.)
(Jensen's Inequality)
heg
In EE, maxexp hEy
(Amax(On:- -0x))
(exp(Az) is increasing function)
$ In
Ex, exp()An) + exp(->0m)
(exp max & exp sum)
heg
In 2 Σ Exn exp((Ak)
(By symmetry of a)
heg
exp Aawoles)
ln
Ex,
(Since all o,'s are independent)
NEg 1=1
- A In 2
exp (2o(2i)
exp
2
hEg
Using the inequality et + e- & 2e F, we have:
< In 2 Σ 22
g²,(2))
sup heg
Σ 1=1
o:g (2:)
exp
2n 2
beg 1=1
X > 1==
(Z,)2
In2 2
exp
2n
< In 2
exp
2n
B²
In 2
2n
From the above, let = B-1 /22 In 2|9] and we obtain the desired bound.
Theorem F.5 (Dudley's Entropy Integral), Let G be real-valued function class and S (Z1,..., be a sample drawn i.i.d. from fixed distribution. Then, have:
In (G, L2))
Rs(()) & inf a20
4a + 12
(70)
Ja
n
1/2 where sup [ 1
and Rg( is the empirical Rademacher complexity of the function class G.
Proof. The above result is derived by standard chaining argument (See, for example, Ledent et al. (2021, Proposition 22) or Bartlett et al. (2017, Lemma A.5)). Then, apply Massart's 's finite lemma. The difference is that instead of using the standard Massart's lemma for the regular notion of Rademacher Complexity (without the absolute value surrounding the sum), we apply lemma F4.
35

---

Generalization Analysis for Non-IID CRL
F.3. Symmetrization Inequality
Lemma F.6 (Symmetrization). Let izi,...,, Zn} be a sample drawn i.i.d. from a distribution P. Let G denote function class. Then, for any real-valued non-decreasing function yp, we have:
Esy
sup
Σ g(z)) - Ee-r(g(z)]
< Es,,, & 2R S.N."
(71)
gEg
where En = (o1,..., Jn) the sequence L.i.d. Rademacher variables.
Proof. Denote Eys as the expectation taken over the sample S. We introduce another sample S' = , 2z,} that is identically distributed as S. We have:
1
n Σ (g())) Es(o(z)))
Esp sup geg
71
Essp
sup
(o(z,) Es(a(z)))
geG Y
a Σ g(z:) Σ [s([(()))] "
Egg
sup geğ n
1=1
i=1
< Es
sup
Σ (0(z,) f(E)))
(Jensen's Inequality for yo supl
geg
i=1
1
sup Es. En.
(g(x))
(9(z;) g(z() is symmetric)
gE9 71
<
1
Es,... 1
sup
2
Σ 0g9 (2)
+ Eg En 1p
sup
2
Σ (-0))((2))
2
9Eg
2
gEg
2
2
2 (zg(zz))
EsS... 10
sup
(z,)
Es E.
sup gEG
(Rademacher variables are symmetric)
2
gEG T1
2
Es,,, 4
sup
a:g(Zz) (2:)
(S and S" are identically distributed)
gE$
Es,,,
22R5 S.R.
F.4. Sabb-auussinttt of Rademacher Complexity
Definition F.7 (Sub-Gaussian Random Variable). Let X be a random variable with mean E[X] j.. is then called sub-Gaussian if there exists & such that:
t2e 2
Mx(1) & exp I1
VI 0,
(72)
where Mx denotes the moment generating function of X. We call X a sub-Gaussian random variable with variance proxy {², denoted X E SG
Lemma E8 (Boucheron et al., 2013), Theorem 2.1). Let a random variable with mean E[X] = p. If there exists
{ > 0 such that the following holds:
82
P( ul > & 2exp
(73)
26
36

---

Generalization Analysis for Non-IID CRL
then the random variable X is nub-Gaussian. Specifically, X SG((6E2).
Proof. Let Z =X- -X- f the centered random variable derived by translating X by its mean. Firstly, we prove that Equ. (73) implies that 1 q!(452)9 for all integers q 1. Using the identity |3|2 x So q(--11([2] t)dt, have:
2q 2
24 [r[PP[ > t)dt
J0
12
< 4q
(24 exp
dt.
2
-0
Letting
/ hence = 2ug² and dt
5ddu the above integral becomes:
E 2 & 4
2 ddu
30
= 195² Jo
(2 -
1
= = (25
w du [(a)
22 & (
Let ğ be the i.i.d. copy of Z. Hence, Z Ž symmetric about 0, which means that E[(Z - 2) = 0 for odd-order p-moments. Therefore, For all > O, we have:
Mz(A)M_2(0) = Mz-z(A) (Due to independence)
Rexp (>(2 - 21)
2 (2 2)
(24)
By the convexity of f(z) 22, for all / E (0. 1), we have:
2z + (1 (1- 1 (1 (1-tto -2)
Setting & 1, have:
29
2
7
724 + 7,4
(Z- 2)-9 1229 +224)
2
2
As result, we have EZ - 2)
Plugging this back to the formula of E|
22
M (2), we have:
22
E
E
EE
1 + A2
(2q)
< 1 +
(2q)
37

---

Generalization Analysis for Non-IID CRL
Since Ble- 1 > 1 for all À 0 and
(2q)
( + f) >
II
(2)) 29g!,
9!
j=1
j=1
have:
80 Σ
(2A )
(8)2
BIe $ 1 +
1
Σ
8ARE?
q!
Therefore, we have:
16A25²
Mx(A) cATE[AA1 exp
Ay+
Hence, by definition, we have X SG(16E²) as desired.
Lemma F9. Let F be class of bounded functions f f 10, MJ and let S (x1, xx) be sampled i.i.d. from given distribution P. Let En .o.,...., on) be sequence of independent Rademacher variables and define the following random variable:
R.E. sup
Σ {x)(x))
(74)
JEF
j-1
which is a function of both and En. Then, we have:
Es,,, exp (IRSZ exp (Rn(F) +
16t
41 0,
2n
where (F) is the expected Rademacher complexity, defined as (F) = Es,E. R
Proof. Let S; be the copy of S with the th element replaced with x/, an i.i.d. copy of x, Similarly, let E(! be the copy of En where the th element replaced with of, an i.i.d. copy of or. Then, we have:
R.S.n En
R..
S.
oi (f(xx) - (f(x)) f(xx))
2M
sup fEF
n
n
R
(x)) - ot) &
2M
sup fEF
n
n
Hence, by McDiarmid's inequality, we have:
P ((R5 S. (F) 2t)
t² Vt
2exp
4n-1
Let =2 2M2 Then, by lemma F.8, the random variable R S.E. is sub-Gaussian with variance proxy of 166² Hence, we have:
32M
16 Vt 0,
Es,,, exp (IRSE.) exp (Rn(F) +
7
as desired.
38

---

Generalization Analysis for Non-IID CRL
G. Further Discussions
G.I. Some Comments on the Differences between Our Proof Strategy and that of Lei et al. (2023)
The core similarity of our work and Lei et al. (2023) is that we both bound the (empirical) Rademacher complexity of the loss class, denoted as Rg) through the Lo covering number of the following class:
H. = [xxxxx -(x) -(x)
f(x)
(75)
Specifically, suppose that the loss is e -lisschhizzz with constant 1) > 0 and bounded by M. By Dudley's entropy integral bound, we have:
M
e, de &
In. e/n,, Loe (Sx) de, a > 0.
R9( $
(76)
Where S is set of n independent tuples and Sy is the set of triplets incurred from S (See Lei et al. (2023), Section 4.2). At this point, the difference lies in the methods by which we estimate (H, e/n1, (Sx)). In our work, the Lo covering number of H is directly estimated by the 2 covering number of the representation function class F (Lemma D.12). In Lei et al. (2023), the estimation is done via fat-shattering dimension and worst-case Rademacher complexity. Below, we show how the additional costs in terms of n, k and their logarithmic terms propagate through complexity measures:
nk/e?
In (nk/ee)) In Noo Loz (Sx)),
Rwc(H)
faa, (H)
(77)
where AW)(() denotes the worst-case Rademacher complexity of H (note that Rw)(H) Ö(1/Vnk)) and fat, denotes the fat-shattering dimension. This yields the final inequality (See Lei et al. (2023), Eqn. (C.6)):
nkn W (H)
12'nk
eM, &
In?
(78)
2
Effectively, this introduces an additional multiplicative factor of In()) in the main results of Lei et al. (2023) (See Theorems 4.8 and 4.9 of Lei et al. (2023)).
We also note that the works in the similar lines of research as Arora al. (2019) and Lei et al. (2023) deal with the i.i.d. tuples regime while our work is concerned with non-i.i.d. regimes. In this paper, we use similar arguments as Hoeffding (1948) and Clémençon al. (2008) to handle the non-i.i.d. d. nature of the tuples with recycled data. This requires estimating
each class-conditional risk independently, resulting in excess risk bounds of order (L/\ min
min Pmin: 1-mmax
)) which
substantially different than those of Lei et al. (2023). In fact, the number N min Pminn 1-Pmmax in our bounds plays similar role as the number "n" in Lei et al. (2023) the sample complexity for the number disjoint tuples.
G.2. Extension of the Sub-sampling Procedure
In the procedure described in Section 3.3, the tuples are sub-sampled independently from the pool of "valid" tuples where samples are unique within tuples. This means that the samples within each tuple are dependent conditionally given the full sample ..,..., XN (but independent without condition), whilst the tuples are independent with or without conditioning. This approach corresponds to calculating U-statistics.
It is also possible allow replacement within tuples, in which the samples within each tuple would instead be independent conditioned on the full sample XI...., Xy but dependent if no conditioning is applied. This approach corresponds to calculating V-statistics. Our techniques readily extend to this case and would only incur an additive term of θ
N min( (12P1la which does not worsen the order of magnitude in our bounds. To see why, let us consider the one-sample case for simplicity. Specifically, let (x1,..., x,) be random sample drawn i.i.d. from a distribution
39

---

Generalization Analysis for Non-IID CRL
P over X' and let h xm IR be symmetric kernel. The V-Statistics of order m of the kernel is defined as:
(h(
h(x1 Xim
(79)
T2
Vm
Unlike (h), (h) generally not an unbiased estimator of EEh (1,,...... Xm) due the terms with repeated samples. By Hoeffding (1948), we can write Vn (h) as follows:
n (h)
12
Un)
Σ
h(xi,..... Xim)
(80)
m
As result:
V. (h) (h) = n (nm [[.].
E
(x.,,....... Un(h)
(81)
where E 0n. Therefore, if (mm) & for æ1...., E X, then Va(h) - (h) ((M/n), which means the effect biasedness dissipates when n increases. Therefore, while biasedness slightly complicates analysis, leverage results the concentration of U-statistics study the concentration of V-statistics around the population risk, with small incurred cost.
G.3. Relevance to Semi-Supervised Contrastive Learning
The methods developed in this work is not directly tailored for semi-supervised self-supervised regimes. However, note that they are reasonably extendable to those settings. In this section, we outline how the analytical techniques used in this paper can be adapted to semi/self-sun supervised representation learning. Suppose that there exists a distribution P over X' x C' where X' denotes the data space and C' denotes the labels space (which is accessible to the learner). In semi-supervised classification, two sets of data S = U ~ pD' and Su = {(u,. ū5)];- ~ pm are given. While both S, Sy are drawn i.i.d. from P, the labels (E are hidden, making Sy unlabeled. In general, the overall risk for a representation functions f E JF is a combination of both supervised and unsupervised risks. As the supervised risk has been well-studied (Bartlett et al., 2017; Golowich al., 2017; Long & Sedghi, 2020; Wei & Ma, 2020; Ledent al., 2021), we focus on the possible formulations of unsupervised risk below instead.
Consistency regularization (Sajjadi et al., 2016; Chen et al., 2020): Under this regime, the unsupervised loss aims to ensure consistency of representations under different augmentations of inputs. Specifically, let A be a distribution over augmentation schemes, the unsupervised risk can be defined as
|| f(luu) f(a [w)]]
Luu (f) = E a.at
u-p
(82)
where 1 is a distance measure in Rd. Under this regime, we are implicitly given a set of augmented pairs S ((a]u))] [u,])]{= drawn i.i.d. from a distribution dependent on both P, (where ay's 's are drawn i.i.d. from A). Here, the loss function only relies on augmented views a(x) and a (x) which comes from the same natural sample, which precludes reusing natural samples different pairs/tuples. Thus, we can analyze this regime using standard results in learning theory without the decoupling technique.
||
Self-supervised CL (HaoChen et al., 2021; Wang et al., 2022; Huang et al., 2023): In this case, the unsupervised risk can be defined as
e [[ [(a+ ( 1(3 K +)
Lun (.f) = E u.u.appe a 2h11
(83)
Intuitively, the augmented views of the same input should be similar to each other while being dissimilar to augmented views of other samples. Since Sy consists of i..dd data points in this setting, it is natural to formulate a (k 2) 2o-ore U-Statistics from Sr, generalizing our results to this setting. While such a learning setting involves reused samples, the lack of supervised information removes much of the subtleties of class-collision in our work. Thus, the analysis would be close to (a wise extension of) Clémençon al. (2008), making the result simpler than our case when class constraints are present.
40


Reviews:
[{"review_id": "aFC7nM4Xta", "reviewer": "Reviewer_sw2u", "summary": "This paper revisits contrastive representation learning by relaxing the traditional i.i.d. assumption on training tuples. Instead of assuming independent tuples, the authors analyze a practical setting where a fixed pool of labeled data is recycled to form multiple tuples. They derive generalization bounds using a U‑Statistics framework for both the full risk and a sub-sampled empirical risk. They applied the obtained resutls to linear models and neural networks, and experiment on MNIST and synthetic data.", "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": "Many thanks for the thoughtful and detailed response. We sincerely appreciate your recognition of the novelty in our decoupling techniques. Below, we provide our responses to address your concerns.\n\n**Re (Remark 4.2)**: To clarify your concern, suppose we have an one-sample, $m$-order U-Statistic as defined in Eqn. (12) and pick an arbitrary integer $i\\in[q]$ where $q=\\lfloor n/m\\rfloor$. Additionally, denote $P_m[n]$ and $C_m[n]$ as the sets of $m$-permutations and $m$-combinations selected from $[n]$, respectively. Then, for any $l_1, \\dots, l_m \\in P_m[n]$, there are $(n-m)!$ re-arrangements $\\pi\\in S[n]$ (line 220) such that $\\pi[mi-m+u]=l_u, \\forall u\\in[m]$. In other words, when we shuffle $[n]$ brute-forcedly, the tuple $l_1, \\dots, l_m$ appears $(n-m)!$ times (in exact order) from position $mi-m+1$ to $mi$. Hence, we can write:\n$$\n    \\frac{1}{n!}\\sum_{\\pi\\in S[n]} h(x_{\\pi[mi-m+1]}, \\dots, x_{\\pi[mi]}) = \\frac{1}{n!}\\sum_{l_{1:m}\\in P_m[n]}(n-m)!h(x_{l_1}, \\dots, x_{l_m}).\n$$\n\nWhen $h$ is symmetric, any permutation of its arguments does not alter its value. Thus, we can further simplify the right-hand-side to a sum over the set of $m$-combinations:\n$$\n    \\sum_{l_{1:m}\\in P_m[n]}h(x_{l_1}, \\dots, x_{l_m}) = \\sum_{p_{1:m}\\in C_m[n]}m! h(x_{p_1}, \\dots, x_{p_m}).\n$$\n\nCombining all of the above:\n$$\n\\frac{1}{n!}\\sum_{\\pi\\in S[n]} h(x_{\\pi[mi-m+1]}, \\dots, x_{\\pi[mi]}) = \\frac{m!(n-m)!}{n!}\\sum_{p_{1:m}\\in C_m[n]} h(x_{p_1}, \\dots, x_{p_m}),\n$$\n\nwhich is exactly Eqn. (11).\n\n**Re (Weakness 1)**: We thank the reviewer for the suggestion to improve our presentation. To summarize, our U-Statistics formulation is motivated by the task of creating an (asymptotically) unbiased estimator for $\\mathrm{L_{un}}(f)$ by estimating each conditional risk $\\mathrm{L_{un}}(f|c)$ then combining the estimators, resulting in Eqn. (8). The reason for this separation lies in the nuance of estimating $\\mathrm{L_{un}}(f)$ directly through a $(k+2)$-order U-Statistics (Lines 240 - 245). We acknowledge that we can make the intuition clearer for the readers and we will make sure to improve our presentation in the revised manuscript.\n\n**Re (Weakness 2)**: Thank you for the keen observation. In the procedure described in Section 3.3, the tuples are subsampled independently from the pool of 'valid' tuples where samples are unique within tuples. This means that the samples within each tuple are dependent conditionally given the full sample $x_1,\\ldots,x_N$ (but independent without condition), whilst the tuples are independent with or without conditioning. **This approach corresponds to calculating U-statistics**.\n\nIt is also possible to allow replacement within tuples, in which case the samples within each tuple would instead be independent conditioned on the full sample $x_1,\\ldots,x_N$ but dependent if no conditioning is applied. **This approach corresponds to calculating V-statistics**. Our techniques readily extend to this case and would only incur an additive term of $\\widetilde{O}\\Big(\\frac{1}{ N\\min(\\rho_{\\min}/2, (1-\\rho_{\\max})/k)}\\Big)$, which does not worsen the order of magnitude in our bounds. To see why, let us consider the one-sample case (described before Eqn. (11)) for simplicity. The V-Statistics of order $m$ for some kernel $h$ is defined as:\n$$\n    V_n(h)=\\frac{1}{n^m}\\sum_{i_1=1}^n\\dots\\sum_{i_m=1}^n h(x_{i_1}, \\dots, x_{i_m}).\n$$\n\nGenerally, $V_n(h)$ is not an unbiased estimator of $\\mathbb{E}h(x_1, \\dots, x_m)$ due to the terms with repeated samples. By [1], we can write $V_n(h)$ as follows:\n$$\n    n^m V_n(h) = \\binom{n}{m}U_n(h) +\\sum_{i_{1:m}\\in[n]^m\\setminus C_m[n]}h(x_{i_1}, \\dots, x_{i_m}).\n$$\n\nAs a result:\n$$\nV_n(h) - U_n(h) = \\frac{1}{n^m} \\sum_{i_{1:m}\\in[n]^m\\setminus C_m[n]}[h(x_{i_1}, \\dots, x_{i_m}) - U_n(h)],\n$$\n\nwhere $|[n]^m\\setminus C_m[n]|\\in O(n^{m-1})$.  Therefore, if $|h(x_1, \\dots, x_m)|\\le M$, then $V_n(h)-U_n(h)\\in O(M/n)$, which means the effect of biasedness dissipates when $n$ increases (as the reviewer remarked). Thus, while biasedness slightly complicates analysis, we can leverage results on the concentration of U-statistics to study the concentration of V-statistics around the population risk, with a small incurred cost. Once again, we really appreciate the reviewer's feedback that help extend the scope of our work to a very interesting regime.\n\n**Other Modifications**: As per reviewer's suggestions, we have made the following changes:\n\n- Reiterate the definition of $k$ in definition 3.1 (Eqn. (3)).\n\n- Move the definition of the i.i.d. dataset $S$ before Eqn. (5) for better flow.\n\n- Define $C_m[n]$ before Eqn. (11).\n\nFurthermore, we promise to add a more detailed experiment set-up description in the appendix as well as a pointer to the appendix in the main text. We thank the reviewer once again for their efforts in making our work clearer for readers.\n\n**References**:\n\n[1] Wassily Hoeffding, A Class of Statistics with Asymptotically Normal Distribution. Ann. Math. Statist., 1948.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, I have some questions on Remark 4.2 (see questions)", "experimental_designs_or_analyses": "I checked the to experiments in section 6.1 on how a method based on sub-sampling strategy can effectively approximate the performance of the all-tuple method, and the experiments in section 6.2 showing that the number of samples needed scales linearly with the number of classes and negative samples.", "relation_to_broader_scientific_literature": "The authors overcome the non-i.i.d. issue by reformulating the risk estimation problem in terms of U‑Statistics and then applying decoupling techniques. \nMore in detail: instead of computing the empirical risk over tuples of iid samples, they express the population unsupervised risk as a U‑Statistic. This formulation averages the contrastive loss over all valid tuples that can be formed from the dataset. Although these tuples are generated by reusing the same data points, the U‑Statistics framework provides an unbiased estimator of the true risk.\nTo handle the dependencies, the authors use a decoupling technique inspired by works of Peña and Ginè. The key idea is to break down the U‑Statistic into sums over independent blocks.\nThey reorganize the sum over all possible tuples into sums over several groups (or blocks) where, by design, each block consists of tuples that are constructed in a disjoint manner from the fixed dataset.", "essential_references_not_discussed": "I don't believe there are essential related works missing from the paper's citations.", "other_strengths_and_weaknesses": "Strengths: \n- The paper extends the theoretical analysis of contrastive representation learning by explicitly handling the non-i.i.d. nature of real-world data developing a framework based on U‑Statistics and decoupling techniques.\n- The experiments (although conducted on MNIST and synthetic datasets) demonstrate that the proposed sub-sampling regime can approximate the performance of using all possible tuples, thereby validating the theoretical claims. \n\nWeaknesses:\n\n- The clarity of the paper’s exposition is not as strong as it could be. The presentation sometimes lacks sufficient intuition or detailed explanation of certain steps, particularly in the derivations involving U‑Statistics and decoupling techniques\n- One limitation is that treating the tuples as they where independent, as discussed in 4.1, can be done only if we use the tuple sampling strategy described in section 3.3. In a real-world scenario the within-tuple selections may not be  independent. \nOf course the dependency is negligible when the number of available samples is very large. \n- While the paper describes the overall approach, details on experimental setup are missing.", "other_comments_or_suggestions": "For eq (3) I think it's better to reply what is k before eq 3. You mentioned that in the introduction, but I think it's better to restate it before equation 3 instead of before equation 5. \n\nLine 141, it is written \"where $\\mathcal{S}$...\" but $\\mathcal{S}$ does not appear in the equation above (eq 5). \n\ntypo: C[m]  in equation 11 not defined", "questions_for_authors": "1) Question regarding remark 4.2: In your decoupling argument, you partition the data into disjoint blocks to form the U‑Statistics. Could you please clarify how the symmetry of the kernel ensures that we can remove the sum over q? and write U_{n} in that way as per remark 4.2?  I guess the writing is true only in expectation.", "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": "kPmHqW4fMq", "reviewer": "Reviewer_81JF", "summary": "For the generalization analysis of contrastive representation learning (CRL) in non-IID settings, several new theory bounds are proposed in this paper. First, this paper proposes a revised theoretical framework for CRL. Then, a U-Statistics formulation for the population unsupervised risk is proposed, and bounds for the empirical minimizer of U-Statistics and a sub-sampled risk are derived. Finally, excess risk bounds for classes of linear functions and neural networks are derived based on the above theoretical results.", "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": "Many thanks for your thorough review. We especially appreciate your efforts in checking the correctness of our theoretical analysis as well as raising an interesting question regarding the proof techniques. Please refer to our response below regarding the difference between the technicality of our work and that of [3].\n\n**Re (Weakness 1)**: Many thanks for your keen observation! Indeed, our Theorem 5.1 is free of any logarithmic factors in either $N$ or $k$. However, the right hand side involves the quantities $K_{\\mathcal{F},c}$, which each bounds the Rademacher complexity of the loss class associated to tuples corresponding to positive class $c$: applying the bounds to concrete function classes, as we do in Appendix B.3, does incur logarithmic factors of both $k$ and $N$ when bounding these complexities via covering numbers and Dudley's entropy formula. \n\nIn contrast, bounds in [3] incur logarithmic factors as early as in Theorem 4.8, even though the Rademacher complexities $\\mathfrak{R}\\_{S_{\\mathcal{H}},nk}(\\mathcal{H})$ have yet to be bounded. This is because [3] relies on inequalities between different complexity measures (Lemma C.3 in [3]) earlier in the proof. Still, since our analysis on concrete function classes subsequently incurs log factors, we have chosen not to dwell on this particular improvement to not obscure our main contributions. \n\n**Details on Proof Technique**: The core similarity of our work and [3] is the fact that we both bound the (empirical) Rademacher complexity of the loss class, denoted as $\\mathfrak{\\widehat R}\\_{S}(\\mathcal{G})$ through the $L_\\infty$ covering number of $\\mathcal{H}=\\\\{(x, x^+, x^-)\\mapsto f(x)^\\top[f(x^+) - f(x^-)]:f\\in\\mathcal{F}\\\\}$. Specifically, suppose that the loss is $\\ell^\\infty$-Lipschitz with constant $\\eta>0$:\n$$\n\\mathfrak{\\widehat R}\\_S(\\mathcal{G}) \\lesssim \\int_\\alpha^\\mathcal{M}\\sqrt{\\frac{\\ln \\mathcal{N}(\\mathcal{H}, \\epsilon/\\eta, L_\\infty(S_\\mathcal{H}))}{n}}d\\epsilon, \\quad \\alpha>0.\n$$\n\nWhere $S$ is a set of $n$ independent tuples and $S_\\mathcal{H}$ is the set of triplets incurred from $S$ (See [3], Section 4.2). At this point, the difference lies in the methods by which we estimate $\\mathcal{N}(\\mathcal{H}, \\epsilon/\\eta, L_\\infty(S_\\mathcal{H}))$. In our work, the $L_\\infty$ covering number of $\\mathcal{H}$ is **directly estimated** by the $L_{\\infty, 2}$ covering number of $\\mathcal{F}$ (Lemma B.12). In [3], the estimation is done via fat-shattering dimension and worst-case Rademacher complexity. Below, we show how the additional costs in terms of $n, k$ and their logarithmic terms propagate through complexity measures:\n$$\n\\mathfrak{R}\\_{WC}(\\mathcal{H})^2 \\xrightarrow{nk/\\epsilon^2} \\mathrm{fat}\\_{\\epsilon}(\\mathcal{H}) \\xrightarrow{\\ln^2(nk/\\epsilon^2)} \\ln\\mathcal{N}\\_\\infty(\\mathcal{H}, \\epsilon, L\\_\\infty(S_\\mathcal{H})),\n$$\n\nwhere $\\mathfrak{R}\\_{WC}(\\mathcal{H})$ denotes the worst-case Rademacher complexity of $\\mathcal{H}$ (note that $\\mathfrak{R}\\_{WC}(\\mathcal{H})\\in\\widetilde O(1/\\sqrt{nk})$) and $\\mathrm{fat}\\_\\epsilon(\\mathcal{H})$ denotes the fat-shattering dimension. This yields the final inequality (See [3], Eqn. (C.6)):\n$$\n\\ln\\mathcal{N}(\\mathcal{H}, \\epsilon/\\eta, L_\\infty(S_\\mathcal{H}))\\lesssim \\frac{nk\\eta^2\\mathfrak{R}^2\\_{WC}(\\mathcal{H})}{\\epsilon^2}\\ln^2\\Bigg(\\frac{\\eta^2 nk}{\\epsilon^2}\\Bigg).\n$$\n\n**Re (Weakness 2)**: We thank the reviewer for their suggestion. In our revised manuscript, we will certainly re-phrase the subtlety of formulating a $(k+2)$-order U-Statistics more succinctly.\n\n**Conclusion**: Aside from the concerns addressed above, we promise to correct any other existing typos in our revised manuscript. We thank the reviewer once again for their effort in making our work clearer for readers.\nWe stand ready to answer any further questions you may have and hope that our answer has helped further improve your opinion of our work. \n\n**References**:\n\n[2] Arora et al., A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML, 2019.\n\n[3] Lei et al., Generalization Analysis for Contrastive Representation Learning. ICML, 2023.\n\n[4] HaoChen et al., Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss. NeurIPS, 2021. \n\n[5] Wang et al., Chaos is a ladder: A new theoretical understanding of Contrastive Learning via augmentation overlap. ICLR, 2022.\n\n[6] Huang et al., Towards the generalization of contrastive Self-supervised Learning. ICLR, 2023.\n\n[7] Khosla et al., Supervised Contrastive Learning. NeurIPS, 2020.\n\n[8] Awasthi et al., Do More Negative Samples Necessarily Hurt In Contrastive Learning? ICML, 2022.\n\n[9] Ash et al., Investigating the Role of Negatives in Contrastive Representation Learning. AISTATS, 2022.\n\n[10] Schroff et al., FaceNet: A Unified Embedding for Face Recognition and Clustering. CVPR, 2015.\n\n[11] Sohn, Improved Deep Metric Learning with Multi-class N-pair Loss Objective. NIPS, 2016.", "claims_and_evidence": "$\\bullet$ This paper mainly proposes the claim: Training datasets are often limited to fixed pools of labeled samples, previous results on generalization bounds for CRL might not comply with most practical use cases where data is limited.\n\n$\\bullet$ The theoretical results in this paper provide strong and clear evidence for the claim.", "methods_and_evaluation_criteria": "Yes. The analytical method on U-Statistics provides effective support for theoretical analysis for CRL under non-IID settings.", "theoretical_claims": "Yes. I have reviewed most of the proofs and the theoretical claims are correct.", "experimental_designs_or_analyses": "Yes. The experimental designs used to verify the theoretical results and the analyses on the theoretical results are all valid.", "relation_to_broader_scientific_literature": "Compared with previous works which require an IID assumption across input tuples, the theoretical results in this paper for non-IID settings are more consistent with practical situations, and these theoretical results broaden the limitations of existing works.", "essential_references_not_discussed": "No. All the essential references have been adequately discussed.", "other_strengths_and_weaknesses": "$\\bullet$ Strengths:\n\nThe theory of U-Processes is often considered to deal with pairwise learning or ranking learning. Using it to deal with pairwise relationships between anchor-positive pairs and tuples of negative samples is a novel perspective, which provides a good example of the potential application and development of U-Statistics.\n\n$\\bullet$ Weaknesses:\n\n1. The discussion on reducing the dependency of the generalization bounds on $k$ is insufficient. Previous work used the Lipschitz continuity of the loss functions with respect to the $\\ell_\\infty$ norm or the self-bounding Lipschitz continuity (essentially smoothness) to reduce the dependency on $k$ from square-root to logarithmic. When the label distribution is perfectly balanced, the discussion in lines 314 to 326 is that due to $N=nk$, the bound here is similar to the $\\tilde{O}(1/\\sqrt{n})$ bounds in previous works. However, in this case, the bound here is tighter than the existing $\\tilde{O}(1/\\sqrt{n})$ bounds by a logarithmic factor of $k$, What is the reason for the tightness of this logarithmic factor?\n\n2. Regarding the reasons why formulating the (k+2)-order U-Statistics in the case of CRL is not straightforward, it seems to me that the two points listed are actually stating the same thing together, and I suggest that the two points can be combined or that some appropriate explanation should be added to the first point.", "other_comments_or_suggestions": "Typos: Line 321, \"$O(1/\\sqrt{n})$\" --> \"$\\tilde{O}(1/\\sqrt{n})$\".", "questions_for_authors": "Please refer to Weaknesses.", "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": "5jOoEyDBvv", "reviewer": "Reviewer_bLbY", "summary": "This paper provides the first statistical generalization theory of Contrastive Representation Learning (CRL) where data does not follow the strong assumption of independently and identically distributed (i.i.d.). Previous theoretical research on CRL assumes that data points used for training are drawn independently. However, this is not true in real-life applications. In reality, datasets are often created by reusing labeled samples across multiple tuples via resampling. Such kind of reuse invalidates the independence assumption, making existing theoretical analyses less applicable to real-world scenarios.\n\nTo address this issue, the paper introduces a revised statistical theory framework that applies to non-i.i.d. data. It establishes generalization bounds for CRL using statistical techniques from U-Statistics, showing that the required number of samples per class depends on the logarithm of the covering number of the learnable feature space. The paper formulates the population risk in CRL as a U-statistics problem and prove that the generalization gap between the empirical minimizer and the Bayes risk decreases at a rate that depends on the dataset size and the structure of the contrastive loss. This provides a more rigorous understanding of how generalization behaves under data reuse. The authors also derive generalization bounds for empirical risk minimization under both U-Statistics and subsampled risk settings, demonstrating how these bounds change with dataset size and subsampling factors. Finally, the paper applies its theoretical findings to common function classes such as linear models and neural networks. By providing a more realistic theoretical foundation, the study offers insights into how CRL generalizes when data is limited and frequently reused.\n\n## update after rebuttal\n\nThe authors have addressed all my questions in my original review. I thus decide to maintain my original rating of 'accept'.", "questions": "", "limitations": "", "rating": 4, "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": "Dear reviewer, we truly appreciate your **recognition of the strength and novelty** of our contributions. We are also particularly grateful for your detailed review and the effort you put into carefully **checking our technical proofs** in Appendices B and C. \n\nTo answer your question - yes - the techniques presented in our paper can be useful in semi-supervised learning depending on the unsupervised risk formulation. Below, we list several examples. \n\n**Overview**: Suppose that there exists a distribution $\\mathcal{P}$ over $\\mathcal{X}\\times\\mathcal{C}$ where $\\mathcal{X}$ denotes the data space and $\\mathcal{C}$ denotes the labels space (which is accessible to the learner). In semi-supervised classification, two sets of data $S=\\\\{(x\\_j, y\\_j)\\\\}\\_{j=1}^{n}\\sim\\mathcal{P}^n$ and $S_U = \\\\{(u\\_j, \\bar y\\_j)\\\\}\\_{j=1}^m\\sim\\mathcal{P}^m$ are given. While both $S, S_U$ are drawn i.i.d. from $\\mathcal{P}$, the labels $(\\bar y_j)_{j\\in[m]}$ are hidden, making $S_U$ unlabelled. In general, the overall risk for a representation functions $f\\in\\mathcal{F}$ is a combination of both supervised and unsupervised risks. As the supervised risk has been well-studied [13, 16, 17], we focus on possible formulations of unsupervised risk below instead.\n\n**Consistency regularization [14, 15]**: Under this regime, the unsupervised loss aims to ensure consistency of representations under different augmentations of inputs. Specifically, let $\\mathcal{A}$ be a distribution over augmentation schemes, the unsupervised risk can be defined as\n$$L_\\mathrm{un}(f)=\\mathbb{E}_{\\substack{u\\sim\\mathcal{P} \\\\\\ \\alpha,\\alpha^+\\sim\\mathcal{A}^2}}\\Big[\\\\|f(\\alpha[u])-f(\\alpha^+[u])\\\\|\\Big]$$\n\nwhere $\\\\|\\cdot\\\\|$ is a distance measure in $\\mathbb{R}^d$. Under this regime, we are implicitly given a set of augmented pairs $S_U^\\mathrm{aug}=\\{(\\alpha_j[u_j], \\alpha_j^+[u_j])\\}_{j=1}^{m}$  drawn i.i.d. from a distribution dependent on both $\\mathcal{P, A}$ (where $a_j$'s are drawn i.i.d. from $\\mathcal{A}$). Here, the loss function only relies on augmented views $\\alpha(x)$ and $\\alpha^+(x)$ which comes from the *same* natural sample, which precludes reusing natural samples in different pairs/tuples. Thus, we can analyze this regime using standard results in learning theory without the decoupling technique. \n\n**Self-supervised CL [4, 5, 6]**: In this case, the unsupervised risk can be defined as\n$$L\\_\\mathrm{un}(f)=\\mathbb{E}\\_{\\substack{u, u^-\\_{1:k}\\sim\\mathcal{P}^{k+1}\\\\\\ \\alpha,\\alpha^+, \\beta\\_{1:k}\\sim\\mathcal{A}^{k+2}}}\\Big[\\ell\\Big(\\Big\\\\{f(\\alpha[u])^\\top[f(\\alpha^+[u])-f(\\beta\\_i[u\\_i^-])]\\Big\\\\}_{i=1}^k\\Big)\\Big].$$\n\nIntuitively, the augmented views of the same input should be similar to each other while being dissimilar to augmented views of other samples. Since $S_U$ consists of i.i.d. data points in this setting, it is natural to formulate a $(k+2)$-order U-Statistics from $S_U$, generalizing our results to this setting. While such a learning setting involves reused samples, the lack of supervised information removes much of the subtleties of class-collision in our work. Thus, the analysis would be close to (a $k$-wise extension of) [12], making the result simpler than our case when class constraints are present. \n\n**Extension**: Extension to semantic segmentation is natural: we then have $\\mathcal{X}\\subseteq\\mathbb{R}^{C\\times H\\times W}$, $\\mathcal{C}\\subseteq \\\\{0, 1\\\\}^{C\\times H\\times W}$ where $C, H, W$ represents image channels, height, width and $\\mathcal{F}$ is a class of CNNs. Under consistency regularization, $\\\\|\\cdot\\\\|$ can be the MSE loss between tensors. Under self-supervised contrastive learning, the contrastive loss can be any common loss functions (hinge/logistic).\n\nLastly, as explained in the response to Reviewer t8eS, we note that our results concern the *excess unsupervised risk*: the connection between the unsupervised (population) risk and the (population)  downstream classification risk is an orthogonal line of research which has been studied in various works [4, 5, 6].\n\n**Conclusion**: Once again, we thank the reviewer for the interesting suggestion that extends our work to potential new directions. In our revised manuscript, we promise to discuss such extension to semi-supervised learning at length and propose future directions accordingly. Please do let us know if you have any further questions or points to discuss. \n\n**References**:\n\n[12] Clemencon et al., Ranking and Empirical Minimization of U-Statistics. Ann. Statist., 2006.\n\n[13] Bartlett et al., Spectrally-normalized Margin Bounds for Neural Networks. NIPS, 2017.\n\n[14] Ting Chen et al., A Simple Framework for Contrastive Learning of Visual Representations. ICML, 2020.\n\n[15] Sajjadi et al., Regularization With Stochastic Transformations and\nPerturbations. NIPS, 2016.\n\n[16] Long \\& Sedghi, Generalization bounds for deep convolutional neural networks. ICLR, 2020.\n\n[17] Golowich et al., Size-Independent Sample Complexity of Neural Networks. COLT, 2018.", "claims_and_evidence": "I think all the four major claims in the introduction are supported by theoretical results.\nSpecifically, there are two main technical results. The first one is the generalization bound for the empirical minimizer of U-statistics. This claim is supported by section 5.1 and the detailed analysis is presented in Appendix B.2. The second one is Thm 5.2 in Section 5.2, with detailed proof included in Appendix C.2. \n\nI read the proof of the main results in Appendix B and C and skimmed through the technical lemmas. It seems to me that the claims are supported.", "methods_and_evaluation_criteria": "N/A. This is a purely theoretical work that proposes new statistical generalization analysis for contrastive representation learning.There is no empirical evaluation.", "theoretical_claims": "Yes. I read section 4 on the proof strategy. I also skimmed Appendix B.2, where I focused on the proof of the main result in Thm B.10. I checked the proof of Thm C.1.\nI did not check the details of the proof for other auxiliary lemmas.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper belongs to the scientific area of statistical generalization theory, where advanced statistical methods are used to analyze the accuracy and robustness of statistical and machine learning models. It specifically focuses on contrastive representation learning. I think this paper is a good complement to this area. Specifically, the previous theoretical work in this area all follows the framework of Arora et al. 2019 which assumes the ideal setting of i.i.d. Data tuples. However, in CRL use case, this often does not hold. This paper relaxes this strong assumption via a U-statistics technique. Therefore, I think this paper makes a valid contribution to its field.", "essential_references_not_discussed": "From my opinion the most relevant works are discussed in the Related Work section.", "other_strengths_and_weaknesses": "**1** Clarity: I think this paper is clear. The claims are clear to understand. As a theoretical work, the section of proof strategy significantly helps readers like me to better understand the major steps in the analysis.\n\n**2** Originality: this paper is the first theoretical work in generalization theory of contrastive learning.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Can the results or analysis framework of the paper be extended to semi-supervised contrastive representation learning? \nTo be specific, in many use case such as AI for Health (e.g. segmentation task of medical images), practitioners often adopt semi-supervised learning where the total loss consists of a contrastive loss and a supervised loss. \nSo I guess to what extent does the major results depend on the unsupervised risk formulation in Definition 3.1? Can it be of other forms? Thanks!", "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": "CEC6nDJHRm", "reviewer": "Reviewer_t8eS", "summary": "This paper proposes a modified framework where ERM is performed using a small subset of input tuples assembled from a fixed pool of label data points. It derives generalization bounds for the empirical minimizer of U-Statistics and a sub-sampled risk. The results are applied to obtain bounds for common classes of representation functions such as linear functions and neural networks.", "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 truly value your thoughtful feedback. Below, we do our best to allay your concerns within the character limit, and stand ready to answer any questions in further detail during the rolling discussion. \n\nFirstly, we clarify that our work assumes $N$ **labeled** examples $x_{1:N}$ are used to form valid tuples $(x,x^+,x^-_{1:k})$ (where $x,x^+$ share a label) for training an unsupervised loss. Thus, we agree that our setting aligns more with **supervised contrastive learning**, differing from [4, 5, 6], which rely on data augmentation for positive pairs. We promise to clarify these distinctions in our revision. \n\nHowever, we note that using CRL loss in a supervised setting is valid. For instance, both [2, 3] assume access to i.i.d. tuples where $x,x^+$ come from the same conditional distribution, which **cannot be simulated without labels**. Empirically, using the unsupervised loss at the feature representation stage enhances downstream classification performance (See Fig. 2), aligning with previous findings [7, 10, 11].\n\n**Our work vs. [4, 5, 6]**:\n\n- The main results in [5] are Thms. 4.2 and 4.8, which bound the **population downstream classification risk** in terms of **population contrastive learning risk**. In [6], bounds are derived for the error rate of nearest-neighbor classifiers built on representation functions in terms of misalignment probability $R_\\epsilon$. Thus, results in [5,6] are all at population level. In contrast, we focus on the *excess contrastive risk*.\n\n- Thm. 4.1 in [4] tackles excess contrastive risk for a loss taking *two* arguments $x,x^-$. Somewhat like ours, they construct the empirical contrastive risk from a fixed dataset $\\bar x_{1:n_{pre}}$ using all pairs. Since there are only two arguments, their proof closely resembles [12], ignoring dependence on $k$. Crucially, the lack of labels allows **all pairs** to be included, removing the nuance of class-collision. In contrast, our work focuses on the interaction between $k$ and class labels, raising many technical challenges. Meanwhile, [4] emphasizes the link between population classification risk and contrastive risk, as well as the impact of data augmentation, which we do not consider.\n\n**Q1a: Re formula of $\\mathcal{\\bar D}\\_c$.**\n\n**Re**: In Eqn. (2) of [2], the negative distribution is defined as $\\mathcal{D}\\_\\mathrm{neg}(x)=\\mathbb{E}\\_{c\\sim\\rho}[\\mathcal{D}_c(x)]$, which allows negative samples to be drawn from any class regardless of the anchor's class, effectively **allowing class-collision**. In our definition, class-collision is excluded, resulting in the definition in Eqn. (2) of our work. Disallowing class collision is associated to better performance [2, 8, 9].\n\n**Q1b: Are results affected by Eqn. (2)?**\n\n**Re**: Yes, our definition of negative distributions results in a class-collision free version of the population risk in Eqn. (3). Thus, our results concern the concentration of empirical risks around this version. However, our techniques readily extend to class-collision case: we believe the quantity $\\widetilde N$ (Thm. 5.1 and 5.2) would then be replaced by $N\\min(\\rho_{\\min}/2,1/2k)$ and we expect the results on the estimation error to be marginally tighter (although the practical performance would suffer from reduced alignment between the unsupervised loss and classification objective [2, 9]). \n\n**Q2: Re Sections 3.2 and 3.3.**\n\n**Re**: Our Sec. 3 compares the tuples sampling methods in [2] and our work. Under [2] (Sec 3.2), the tuples are drawn i.i.d. from a distribution over $\\mathcal{X}^{k+2}$, i.e., each whole tuple is observed independently as the reviewer stated and no data reuse occurs. Under our framework (Sec. 3.3), the procedure in P. 3 is used to select tuples from a labeled dataset $\\mathcal{S}$ drawn i.i.d. from a distribution over $\\mathcal{X}\\times\\mathcal{C}$. Hence, while **independence holds for elements of $\\mathcal{S}$, it does not hold for the selected tuples**. For instance, if $k=1, \\mathcal{S}=(x,y,v,z)$ with labels $1,1,1,2$, then both $(x,y,z)$ and $(u,v,z)$ are valid tuples but they are dependent due to a shared negative sample $z$. This process allows data reuse across tuples, adhering to practice [7] where recycling samples is desired to create large tuples datasets.\n\n**Q3: Why is $S$ labeled?**\n\n**Re**: As clarified above, our work indeed targets **supervised contrastive learning** rather than truly unsupervised settings. We promise to emphasize this in the revision.\n\nWe thank you again for your suggestions, which we believe will help us better frame our contribution in a broader context beyond [2, 3]. We promise to thoroughly discuss all the proposed references.  If the reviewer and AC deem it appropriate, we are open to changing the title to `Generalization Analysis for supervised contrastive learning in non i.i.d. settings'. We hope our rebuttal has helped improve your opinion of our contributions. Please do not hesitate to let us know if you have any further questions.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No. I have only read Section 1,2,3 of this manuscript because I am very confused about the motivation and settings of this paper. If the authors can remove my doubts, I will carefully check the subsequent content.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Please see the above Summary.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n\nNone.\n\nWeaknesses:\n\n1.There are some issues for references. For example, Lei et al., 2022 the authors cited should be “Lei, Y., Yang, T., Ying, Y., and Zhou, D.-X. Generalization analysis for contrastive representation learning. In International Conference in Machine Learning, **2023**.”\n\n2.Firstly, some previous works such as Arora et al., 2019 and Lei et al., 2023 have explored **conditional** i.i.d. setting. Secondly, this paper is not the first work provide a generalization analysis for the CRL framework under non-i.i.d. settings. The authors didn’t mention those non-i.i.d. works such as HaoChen et al., 2021, Wang et al., 2022, Huang et al., 2023. \n\nHaoChen et al., Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss. NeurIPS, 2021.\nWang et al., Chaos is a ladder：A new theoretical understanding of contrastive learning via augmentation overlap. ICLR, 2022.\n\nHuang, et al., Towards the generalization of contrastive self-supervised learning. ICLR, 2023.\n\n3.The sampling process adopted by the authors is unreasonable since all pre-training samples are unlabeled.", "other_comments_or_suggestions": "I have only read Section 1,2,3 of this manuscript because I am very confused about the motivation and settings of this paper. If the authors can remove my doubts, I will carefully check the subsequent content.", "questions_for_authors": "1.Why do the authors define $\\bar{\\mathcal(D)}_c$ as Equation (2)? It does not follow the set-ups of most practical use cases since the latent label of input is unavailable. I suggest that the authors adopt the definition of Arora et al., 2019 (Equation (2) on page 2). If so, is the theoretical analysis in this paper affected by this definition, and where?\n\n2.In the lines 141-143, the authors state that $S$ is a dataset of $n$ i.i.d. input tuples. This sentence is a little confusing. The relationship between any two tuples is certainly independent. The authors also describe their own independent sampling process on the right hand of page 3. Do the authors want to state that the $k+2$ samples in each tuple are i.i.d. ? In my opinion, the authors didn’t clarify the drawback of the i.i.d. condition of previous works. It may be better for readers to understand via an intuitive example.\n\n3.In the part 3.3, why do the authors define $\\mathcal{S}$ with some labeled samples?  Should these samples be unlabeled? If these samples are labeled, the contrastive learning studied in this paper is supervised, not unsupervised. However, the authors state that they derive some generalization bounds of unsupervised contrastive learning. It is very confusing.", "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 revisits contrastive representation learning by relaxing the traditional i.i.d. assumption on training tuples (Arora et al. (2019) and lei et al. (2023)). In contrast, the authors analyze a practical setting where a fixed pool of labeled data is recycled to form multiple tuples. They derive generalization bounds using a U‑Statistics framework. The authors use a decoupling technique (Peña and Ginè) which breaks down the U‑Statistic into sums over independent blocks.  

The reviewers all agree the motivation for this theoretical work is clear and reasonable and it  is more consistent with practical setting, and the results are new.  In the rebuttal, the authors addressed the questions satisfactorily in their rebuttal.  I concur with the reviewers and recommend its acceptance. 

I would strongly suggest to incorporate all the suggestions made by the reviewers in the final version.
Decision: Accept (poster)