A Statistical Theory of Contrastive Learning via Approximate Sufficient Statistics
Authors: Licong Lin
Song Mei
Venue: NeurIPS 2025 poster ()
Keywords: Contrastive learning
data augmentation
SimCLR
approximate sufficient statistics
Primary area: theory

Abstract: Contrastive learning---a modern approach to extract useful representations from unlabeled data by training models to distinguish similar samples from dissimilar ones---has driven significant progress in foundation models. In this work, we develop a new theoretical framework for analyzing data augmentation-based contrastive learning, with a focus on SimCLR as a representative example. Our approach is based on the concept of \emph{approximate sufficient statistics}, which we extend beyond its original definition in~\cite{oko2025statistical} for contrastive language-image pretraining (CLIP) using KL-divergence. We generalize it to equivalent forms and general $f$-divergences, and show that minimizing SimCLR and other contrastive losses yields encoders that are approximately sufficient. Furthermore, we demonstrate that these near-sufficient encoders can be effectively adapted to downstream regression and classification tasks, with performance depending on their sufficiency and the error induced by data augmentation in contrastive learning. Concrete examples in linear regression and topic classification are provided to illustrate the broad applicability of our results.

A Statistical Theory of Contrastive Learning via Approximate Sufficient Statistics
Licong Lin UC Berkeley 11 liconglin@eer eebongli@bbrkkeey....o edu
Song Mei UC Berkeley
edu
Abstract
Contrastive learning-4 modern approach to extract useful representations from unlabeled data by training models to distinguish similar samples from dissim- ilar ones-has driven significant progress in foundation models. In this work, we develop new theoretical framework for analyzing data augmentation-basee contrastive learning, with focus SimCLR approach is based on the concept of approximate sufficient statistics, which we extend beyond its original definition in Oko et al. [28] for contrastive language- image pretraining (CLIP) using KL-divergence. We generalize it to equivalent forms and general I-divergences, and show that minimizing SimCLR and other contrastive losses yields encoders that are approximately sufficient. Furthermore, we demonstrate that these near-sufficient encoders can be effectively adapted downstream regression and classification tasks, with performance depending on their sufficiency and the eтrоr induced by data augmentation in contrastive learning. Concrete examples in linear regression and topic classification are provided to illustrate the broad applicability of our results.
representative example. Our
Introduction
Leveraging massive unlabeled data learn useful representations has played central role in recent advances in foundation models. A prominent approach of this kind is contrastive learning, which has driven significant progress in visual representation learning [5, 14], large-scale speech processing [3], and multimodal AI [31, 21].
In short, contrastive learning finds useful representations of the data by maximizing similarity between paired samples while minimizing it for non-paired samples. Consider SimCLR [5] for visual representation learning an illustrative example. Given dataset of images æ e X. SimCLR generates two augmented views (z(1), 2())) ) X' x X' for each image æ using random transformations (i.e., data augmentations) such as random cropping, random color distortions, and random Gaussian blur, etc. It then trains an encoder f that aligns the paired views and separates the non-paired views through minimizing the loss in Eq. (2). The learned representation f(x) (or f()())) can then be adapted downstream tasks with few labeled samples and minimal tine-tuning.
Despite its remarkable empirical performance, the theoretical aspects of contrastive learning remain active area of study [32, 28). In this work, present theoretical analysis of data augmentation- based contrastive learning, with specific focus on the SimCLR framework [5] as representative example. Notably, recent work Oko al. [28] has introduced new theoretical insights into contrastive language-image pretraining (CLIP). They first introduced the concept of approximate sufficient statisties, showing that the image and text encoders obtained from the empirical risk minimizer of CLIP are approximately sufficient. Additionally, under the joint graphical hierarchical model (JGHM) assumption for image and text data, they demonstrated that such encoders can be efficiently adapted to various downstream multimodal tasks.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Our work complements and extends the work by Oko et al. [28] in two key ways.
(1) We extend the concept of approximate sufficient statistics, which originally defined for CLIP a specific form based on KL-divergence, to three equivalent forms and general f-divergences. Based on the equivalent forms of the definition, establish that minimizing the contrastive loss (e.g., the InfoNCE loss [29]) is essentially finding approximate sufficient statistics that adaptable to downstream tasks.
(2) We focus on data augmentation- based contrastive learning following the SimCLR framework. In contrast to CLIP, the random transformations in SimCLR introduce additional challenges for theoretical analysis. We show that the downstream performance of the learned encoder depends on its sufficiency and the error induced by the random transformations. Furthermore, motivated by the generalized definition of approximate sufficient statistics, we theoretically demonstrate that encoders trained using alternative contrastive losses can achieve similar downstream performance to those trained using standard SimCLR.
The remainder this work organized as follows. In Section 2, we introduce the concept of approximate sufficient statistics. Sections 3.1-3.2 present the setup of data augmentation-baser contrastive learning and analyze the downstream performance of the SimCLR-traine encoder. In Section 3.3, extend our analysis general [-contrastive losses. Examples in linear regression and topic classification are presented in Section 4. We also conduct synthetic experiments to compare contrastive learning losses in Section 5. Discussion of related works is deferred Appendix A.
2 Approximate sufficient statistics
Before diving into the analysis of contrastive learning, we first introduce the concept of approximate sufficient statisties, which provides novel viewpoint for characterizing the quality of encoders used in contrastive learning. Let I: IR, - R be a convex function such that ((1) O. For random variables (X,Yl Y) X' y with joint density P(ar, y) with respect some measure μa 1 define the I-mutual information (I-MI) as
P(x, v) P()))())dH ((x))) (P()))))))) )
Note that the f-MI is essentially the f-divergence between the joint distribution and the product of marginal distributions. is non-negative and symmetric X and Y. Moreover, provided that is strictly convex, IXX, Y) 0 if and only if X and Y independent. Let (X, Y) be random variables that have the joint density X, Y) (Y could thought as the parameter in Bayesian statistics). For any statistic T X' T(X), characterize the information loss of using T(X) instead of for predicting Y, we introduce the following definition of the sufficiency of ((X).
Definition 1 (Approximate sufficiency). Let : X - T(X) be a mapping (i.e., a statistic). We define three forms of the sufficiency Tf which will be shown to be equivalent:
Information Loss Sufficiency (ILS): The information loss sufficiency of is defined
Suffa, L(X,Y) L(T(X),Y).
Variational Form Sufficiency (VFS): The variational form sufficiency T is given by
inf R2(S T)- inf Suffvr, 5.T(&)))=R
R₂(S),
-
where S T(I,y) = S(T(x),))) and the f-contrastive loss
R²(S) = E S(xx, v) + inf (f" Sz(z)) + Sx()),, (1) R
where 8* is the Fenchel-dual off.
For example, je can be the Lebesgue measure on Euclidean spaces, or the counting measure on discrete
spaces.

---

Conditional Bregman Sufficiency (CBS): The conditional Bregman sufficiency of T is defined
P(y
P(sIT(E))
Suff = Br())xp())
Br
P(y)
P(v)
where Be(a.b) = f(a) f(() - (a ()) b) is the Bregman divergence of Indeed, these definitions will be shown to be equivalent (Lemma 1), i.e.,
Suffn,(T) (TT) Suffeb, (T) =: (Tf,
We say T(X) is an E-approximate sufficient statistic if (T) < E.
The Information Loss Sufficiency (ILS) is closely linked to the InfoMax principle [22, 15], which finds statistic 7 that maximizes mutual information (T), under certain constraints. The equivalence between ILS and CBS suggests that the loss in mutual information can be represented as a divergence between the conditional probabilities XX) and P(Y)T(X)). This provides a concrete measure for interpreting the information loss.
In VFS, by definition, the excess risk R2(S T) infz RR(S) serves upper bound on the sufficiency (T), and they are nearly equal when S is obtained by minimizing R5(S T') over sufficiently rich space Consequently, VFS provides loss minimization framework for finding T with low sufficiency by minimizing the f-contrastive loss R:(S) over S in some space S and extracting from Moreover, an extension of approximate sufficiency similarity scores is introduced in Appendix B.3.
The concept of approximate sufficient statistics was first proposed in Oko al. [28], but only in the CBS form for KL divergence (i.e., f(z) = z log x). In this work, we extend the definition to general f-divergences and establish the equivalence among three forms of sufficiency. Notably, for f that is strictly convex, we have Suff, (T) O if and only if Y IL X (XX from the CBS form, aligning with the classic definition of sufficient statistics (see e.g. [19]). We will mainly consider two special cases of f: ((x) x log x (KI-divergence) and f(x) (ar 1) /222 2 (x2 -d=viverg,,cc), with the corresponding sufficiency denoted by Suffai and Suff x2 For more examples and properties regarding
approximate sufficient statistics, we refer the readers to Appendix B.
In the context of data augmentation-basee augmented views of the sample, and 7 as the encoder f. The sufficiency Suffr(f) then quantifies the loss of recovering augmented views from the encoder representation. We will show that the downstream performance of f can be controlled by its sufficiency (in the CBS form) and the error induced by data augmentation. Specifically, for any downstream task, small risk can be achieved using f if it is near- sufficieff and the random transformations in contrastive learning do not significantly change the downstream outcomes. As preview of the results, we have
contrastive learning, we may choose X and as two
Theorem (Informal). The risk on a downstream task using encoder f (denoted by R(f)) satisfies
R(J) & (VSufff(T)
R + +(0)
for some constant O, where Suff{(f) the f-sufficiency of f and eg denotes the error on the downstream task induced by data augmentation.
Contrastive learning with general f-divergence considered in these works differ from the variational form in (1). In particular, while Lu et al. [23] considered a variational form similar to (1), they set S. 0 instead of taking the infimum over S
also studied in [23, 48), but the loss functions
Statistical properties of contrastive learning
In this section, we demonstrate that data augmentation-base contrastive learning can find near- sufficient encoders that are effectively adaptable to downstream tasks. We focus on the SimCLR framework in Section 3.1-3.2, and extend the results to general f-contrastive losses in Section 3.3.

---

3.1 Setup and the ERM estimator
Let E X be a random sample drawn from a distribution Px on X. Consider set of transformations G in which each transformation X - X' maps X' to itself. Let Pg denote a distribution over the transformations in G. Given a sample æ and two transformations g ggg9( rnd Pgg. we generate two
augmented views of æ, denoted as z (1)) = (x)) and x²)) = g (æ)). The marginal distribution of x1)) (or equivalently x(3) is denoted by 2.. Often, we will omit the superseripts and let x = g(x)
denote single augmented view generated by transformation, y P.g.
Throughout the remainder of this work, unless otherwise specified, we set (X, _ (x(1), 22) in Definition 1, i.e., we define the sufficiency (Tf = 1+(x(1) 20)) (T) 2())) For
simplicity, we assume the joint distribution of (z. (2)) is either discrete or has a continuous density w.r.. some base measure on X We abuse the notation P(.)) to refer to either discrete distributions or the density of continuous distributions, with the intended meaning clear from the context. Also, we occasionally omit the subscript kl when referring to KL--sffficiency.
SimCLR [5] learns a representation of the sample æ (i.e., f((x:) or [(g(=))) through performing contrastive learning on the augmented views (z(2), (2))). Specifically, given a batch of i.i.d. samples (a. from 1x, we generate K pairs of augmented views {(=,") 2 =(²))) using 2K
i..d. transformations {(g) ") 9. ) from Pg. Let f : -
- R' be an encoder function, potentially parametrized by neural networks. The SimCLR risk function is defined as the expected InfoNCE loss [29]:
1 E log exp(S(21) (1) ,z(2))) ΣjE[K] exp(S(z))) (1) (3))
exp( S(2) (1) 10,111)22)) (z(3)))
1 - log
Rsimctr, x (S) ==
and
2
{ Eje[K] exp(S( (1) xz(2)))
(2)
Rsimer,,& (f) == Raimer, (S)), where Sy == T([((2 J( ((=(2)))), T: T - R is some simple link function.
Given set of encoders denoted by F and n K i..dd pairs of augmented views {(x (1) (2) > SimCLR learns an encoder function f e F through empirical risk minimization (ERM), namely,
(1) exp(S, (xp(S)(2(011))x)) 1) (i-1)) ()=))
(2)
f = argmin / [Raimd, x (Sy) = 2n i-1
n1
log
(1-1)
feF
Σle[K] exp(sp (S/ (1- 1)K+) ((-))++]
(1)
(2)
cxp(S (ap(S,( (z (1- I) (1-1) 1)
(1)
(2)
|- log
(3)
ΣiejK] exp(S, (2 (i-1)K+1 (i- 1)
(1)
(2)
With the encoder f(-) at hand, ((x) (or [g((=)) serves as a representation for each æ E X, which can be used for downstream tasks.
We now show that the sufficiency of the ERM estimator f can be properly controlled. We will
demonstrate in Section 3.2 that the downstream performance of f fis closely tied to its sufficiency. First, we note that a global minimizer of the SimCLR risk is S. (2)) log (see Lemma 2 for the proof). To analyze the properties of the ERM estimator, we introduce the following boundedness assumption on the score function and regularity assumption on т.
(())) P(E
Assumption (Bounded score). There exists a constant Bş > such that for all pairs (z(1), x (2),, we have
F(2 (21) (2())) E [1/Bs, for all f F and F(2 ((2))) +1/BB. Bs].
Assumption 2 (Simple link function). The link function some constant B, 0 such that [+(0) < B, and T, - are Lipsshht
R - R is invertible and there exists
Note that the first part of Assumption 1 is satisfied with Bs- exp( B3) when [lf()) < By for all f E F, x E X and T is the identity function. Based on these assumptions, we have
Moore generally, we only need each transformation g X - Z maps X' to a space Z, which entails a natural injective map back to X.

---

Theorem (Sufficiency bound for the ERM estimator). Suppose Assumption I and 2 hold for some Bs 1, By > O. Let be the empirical risk minimizer defined in Eq. (3) and let S. be defined in Section 3.1. Let supp(z()) be the support of z()) and Nu. 12,a;; F) be the u-covering number of
F under the (2, (0)-mmm |,,0, = supzesupp(z(:)) [=) Then, with probubility at least we have
Suffaa()
[generalization error approximation error),
(4)
K
where
2(og B++
generalization error := V 1og(1/5) + B²
V log Vog,Vu,l 112,,0, F)du
(5a)
0
approximation error inf Rsimdr, K (Sp) Reimcr. K (S.) jef
(5b)
for some constant > 0 depending polynomially on Bs.
See the proof in Appendix C.2. In the decomposition the R.H.S. of (4), the approximation error term represents the error incurred when approximating the optimal score S, within the function class F. It property of the function class F, and a richer class tends to have smaller approximation error. The generalization error bound is derived using concentration properties of functions with bounded differences. Notably, it depends only the total sample size n, K rather than the batch size K or the number of batches 71. This allows our results to account for large or full-batch training, used in SimCLR [5] and CLIP [31]. When n 00, the generalization error vanishes while the approximation error remains constant.
Why does the Sim CLR loss work? Intuitively, Raimer, (S) can be viewed as an approximation of the KL-contrastive loss (S) in Eq. (1) using finite batch size K. Namely,
(1) (S((S) - (1) 22) + E E log _ag0) [exp( (5((() #2
lim Rgimdr, (S) - log K. K-000
(6)
See the proof in Appendix C.I. As result, by the definition of VFS in Definition 1 Suffal() & Rs(()) - inf (S) s Rgimdr, (Sy) inf Raimelr, K (S),
5
Excess risk
and thus minimizing the SimCLR loss Rsimetr k (S)) effectively controls the sufficiency Suffu(f).
3.2 Using the encoder for downstream tasks
Given an encoder function f X' - R2, we are interested in applying it to downstream tasks. Specifically, the goal to leverage the learned representation f(z) (or ((())) to facilitate learning in downstream tasks, such regression or classification. By mapping the raw sample æ to the feature space IRP, the representation f(x) (or (g(()))) is expected to capture the most salient information of æ. simplifying the downstream task while maintaining high performance. In this section, we demonstrate that the downstream performance of the encoder depends on its sufficiency Suffa())) and the robustness of the downstream task to the random transformation g P.g.
Adaptation to downstream regression tasks. We first study regression tasks. Consider the task of learning an unknown target function h. X' - R. Given an encoder f. our objective is to find function h : IRP IR such that (x))) = (a)) (or h( h(((g())) s (x))). The estimation error of h is measured by the risk
Rg(h f) == EB-
- [0 [(h(f(((())) (z)),,,, or R(ho f) == EE--P,(((((())) - h, (.
For example, regression tasks where the goal is to predict the outcome y based on the covariates a, one can choose h.. hxx)) E[ylæz]. The two risks RG(-), R(-) correspond to the cases where random transformation g is (or not) applied before passing the input to the encoder f. respectively.
Theorem 2 illustrates how the downstream performance of the encoder ff depends on its sufficiency.
5

---

Theorem 2 (Performance on downstream regression). Suppose h. satisfies [[,,, (1))(()) & BR. almost surely. Given an encoder f X - R", there exists a measurable function h IR" such that
Rg(h o f) & of (B, (fff + cg);
(7a)
where e >> O is some absolute constant and Eg == BE-- .g-Po ((h (g h. (2))) Moreover, if the augmented view has the same marginal distribution as the original sample, i.e., (1) 1 æ, then
R(h <
Eg)
(7b)
for some absolute constant > 0.
The proof of Theorem is contained in Appendix C.3. The term eg characterizes the impact of random transformation on the value of the target function h. In SimCLR, since the encoder is trained only on the augmented views (x(2), 22)), the random transformation need to preserve sufficient information h, (e.g.. Eg is small) for to be effective. This is often the case in practice: for example, random cropping (g) typically does not alter the class label (h,) of an image; similarly, rotations and scaling (g) should not affect the true age (h,) of a person in facial images. In addition. Eq. (7a) still holds when Eg is replaced by the minimum error Eg = inf, Ex Px gP [(((g()) (x))) & eg. We refer to the proof for more details.
ddaptation to downstream classification tasks. We next in the downstream we are given samples (æt y) from some joint distribution P on X' x [K]. where Px is the input and y E [K] is the corresponding label. Note that for any æ, the label y follows the conditional probability ((y/zz) Given an encoder f, for any function h : R2 - A(KK), we
classification tasks. Suppose
measure its classification error by
(h f) (Z.)) (PPlo//lllDL((llpl))))))/CCCCC
Theorem (Performance on downstream classification). Suppose ynf P(ylg(æ)) > exp(-B) for some B on the support of g(z). Given an encoder X + R", there exists measurable function h R2 -> A([K) such that
Re f) & c By Suffwu(f + +
(8)
and 0 is some absolute where c/e := Ex-Pxx--FF (D2 [z) | D2 (P constant. Here, D2 denotes the 2-Rényi divergence.
The proof of Theorem contained in Appendix C.4. Similar the regression case in Theorem the downstream classification error is bounded by the sum of sufficiency term and an eтror term that characterizes the change in label probabilities induced by the transformation, g.
3.3 General f-contrastive learning
We generalize our theoretical framework to using general f-sufficiency as defined in Definition 1, which could be controlled by minimizing the f-contrastive learning risk. We discuss (1) how find encoders f with low f-sufficiency Suffr(/) via data augmentation-based contrastive learning and (2) the implications of low f-sufficiency downstream performance. Note that ((x) log & yields the standard SimCLR setup.
3.3.1 Finding encoders with low f-sufficiency
Recall the variational form sufficiency (VFS) in Definition 1. We see that for any f and encoder f Ri(S f) inf S-X-X-R
Suffr(f) &
inf
Ri(S) Rr(S,)
inf X
Ir(S).
5:f(2)xx=-
Excess risk
Thus, for any > O, if there exists an encoder f E F such that the excess risk of S is less than then the sufficiency (fff((f) < s. Consequently, given i..dd pairs of augmented views. we can

---

obtain an encoder f with low f-sufficiency by choosing f as the empirical risk minimizer (ERM) of a finite-sample estimate Ry(Sy) of ()) provided that Re(S,) Rr(S,), the function class F is sufficiently rich, and its || 112..0 number is well-controleed.
We focus on x x²-sufficiency (i.e., ((x) (ar 1)2/2) in the following. For general the S.) that attains the infimum in Eq- (1) may not have a closed-form solution, and estimating (yy))) requires solvin solving estimating equations, adding complexity to the analysis. Thus, we leave detailed investigation of the general f case for future work.
When ((x) (x - 1)2/ basic algebra shows that the x²-contrastive loss (1) takes the form Rx=(S) Ep(x.v) (ar, v)] ((C v) (S(,, + S(x, Given K i..dd pairs of augmented views {(2 (1) (()) ) unbiased sinite-sample estimate of (5) gives
Rehisq, (Sp)
1
11
K
Σ
(5 22th (2)) - [
4(K - 1)(K-2
==
[.le[K]
jtk, KFL, It
1
Σ (
(1)
=z(k - -5y(2))
(1) (2)) S = T<((( f(x(2)))) (10)
K
where we adopt the shorthand ERM estimator. Similar Theorem 1, we have
2ah
(2) 1) for i E [2]. Let ʃ argmin JEF Rehhisg, x (Sy) be the
Theorem 4 (x2-sufficiency bound for the ERM estimator). Suppose (y 2 x2)) E [- Bs. Bs]
all f F and pairs (z( (2))), and that Assumption 2 holds for some B, > 0. Let (2(1)) ((2) =
((2())._(9))
For any K E 3, with probability at least - 6, we have ((
S (f) & generalization error approximation emtor,
(11)
where
generalization error :- cB Vlo((1/5) + B²
BBs++B+)
VlogN(u 12,00, F)du]
Vn
J0
approximation error: == inf Ryp - (S.)
feF
for some absolute constant
The proof of Theorem provided in Appendix C.5. Note that we not assume the boundedness of S, in Theorem 1.
3.3.2 Implications of low f-Sufficiency
Similar to the KL case in Section 3.2, the downstream performance of can be controlled by its f-sufficiency for a broad class of f considered in Definition 1. Recall the CBS form in Definition 1. Proposition 5 (I-sufficiency bound on downstream performance). The results in Theorem and hold with Suff (f) replaced by cg (fff((f) for some value C2 > 0 if
Eg(0 (99) [ (P-|= (n (-)f(
C2 Suffr(f).
(13)
Proposition follows immediately by noting that, in the proof of Theorem 2 and 3, Suff is only used as an upper bound of the expected total variation distance (e.g., by Pinsker's 'sr inequality). It can be verified that KL-divergence and x²-divergence satisfy Eq. (13) with 02 = 1/v2. Let r = (1) (2) (())))))))))) denote the density ratio. Moreover, for general f, we can choose C2 (nf
1" (r/)), which is bounded when is strongly convex on the range of the density ratio r. For example, we can choose C2 /2B3/4 when f(x:
va corresponds to the density ratio r & for all pairs (z(1), z (2)). We refer the readers to Lemma 3 in Appendix B.2 for further details. Combining the results from Sections 3.3.1 and 3.3.2, we provide end-to-end theoretical guarantees for the downstream performance of encoders obtained by minimizing the X2x -cottrastive losses.
squared Hellinger-suffiiinnee
7

---

4 Examples
In this section, we present concrete examples on linear regression and topic classification to illustrate the applicability our general results Section 3.
4.1 Linear regression
Let follow some distribution Px on X' S Rd. We assume the downstream task is linear regression, where we observe samples of the form (I. y) R" x R, with y (x, 0.) + for some unknown parameter 0, Rd and 7ero-mean noise independent of æt. The goal is predict y given æ. While fitting a linear model using only the downstream samples yields a risk of order (ddmm) a smaller risk may be achieved by fitting linear model on low-dimensional representation f(z) IRP, where & d, that captures sufficient information about æ relevant to the downstream task. Theorem 6 gives theoretical guarantee for learning the downstream task using a given linear encoder.
Theorem 6 (Linear regression with encoder representation). Let & d. Suppose we are given a linear encoder f(2 = W for some W Rexd and i.i.d. samples { y:) from the downstream
linear model y = (x, +,)+5, where ~ NN0, IL æ. Suppose supzeX |2l12 & Ba |x| 2 & Beg for some Ba: Bg > 0 and let B = B Bg. Also assume that E[(Ia W W >) W =1 = 0 almost surely. Consider fitring (random) linear model h₂(z)) (f(z), n) by ordinary least squares, i.e.
n == argminmerR RD [Rin (ha) = - [(((2)) n) v:)²
where = = =(x)), 2, = ge (x;)) and g, {g] are i..dd transformations from Pg. Then the expected risk of the truncated linear model hz)())= == [o)]__nmn(hh(e satisfies
+c( c2 Suffes. + (g) (0² + B2y plog m
E[Rii (ha)] = 1 B[. E.....lol
h [1]]
m
irveuccill risk
where eg- = [x value that satisfies Eq. (13).
0 and the outer expectation is over {(T,, Vo. (1)) and > 0 is any
See the proof of Theorem 6 and more discussion in Appendix D.I. Compared to fitting a linear model using E RRd which yields an excess risk of Od)/m). Theorem 6 achieves smaller excess risk of order Ó(p/m) when p & d and f(g(z)) is a "good" representation of æ, in the sense that (ff and Eg are sufficiently small. In Appendix D.2, we present scenario where a linear encoder with low KL-sufficiency (ff can be efficiently learned by minimizing the SimCLR loss in Eq. (3). Specifically, we consider a case where two augmented views (z("), 22)) follow joint von Mises-Fisher (vMF) distribution [8] on low-dimensional unit sphere, allowing S, to be realized by S for some linear encoder f. Combined with Theorem 6, this yields an end and-to-end result on the downstream performance of the MinCLR-trrined encoder.
4.2 Topic classification
We also demonstrate our results in classification setting. Let y (1,2,..., M) represent set of classes. A sample æ is generated by first selecting a class E y from some distribution Py, and then
drawing ( xx) [S] [S] conditioned on y, with the joint distribution
P(z|y) = (a Iy) x (x)
where Pa(-ly) some conditional distribution over [S]. For example, in a topic classification task, each sample consists of a two-part sentence (or a two-word phrase), with the class y representing the topic (c.g., sports, technology, or health). The first and second parts (or words), σ1 and x,, are independently sampled from vocabulary of size S, conditioned on the topic y.
Contrastive learning. We use the random dropout transformation g [S] [S] [S], which selects one component x from the pair (æ"i, x²2) with equal probability as the augmented view z and drops the other. Denote the augmented view z using one-hot encoding. We consider encoders that are linear functions of z augmented with the one-hot encoding, i.e., consider the encoder space
F (faug S (es) > M+S |/aug = ((Wz) wz T)T W e M w E R.
W
|
2,00 V
w
< Bw)
VS
8

---

with Bw = M. To learn an encoder Jaug: we minimize the x²-contrastive loss computed using n Li.d. pairs of augmented views via Eq. (10). Importantly, class labels (y: ) remain unobservable during contrastive learning.
Downstream classification. Let Saug(2) and define the encoder as f(z) Wz IR.. We train a linear classifier on to predict the conditional topic distribution P2y y vE[ar] BM, Define E, E RRXSS such that E.,;
, ) be the learned representation,
Eo(y=11="==1) (Py(w=1)
for E [S]. Assume that (a) the marginal distributions of y
(M=MM
and at are uniform over [M] and [S]. respectively; (b) the minimum singular value minn E, E, T) > E. for some OE, > 0; (c) S > 4M and inf [=(]sssssssss (oyyss) >> exp(-B) for some B > 0.
Theorem 7 (Classification using the x²-trained encoder). Under the setup and assumptions in Section 4.2 and let Saug be the ERM Eq. (10). Then, with probability least 6,
c5aM²
Suff x & Rr(S Rr(S.) =: (5 for some absolute constant c O.
[Vlog[1/8 1/8) + VSM2S] (14)
Vn
In downstream classification, given m i..d. samples ((x);, y:) y:) consider filting a multi-class
classifier hz(x) hz))(z)) == softmax(log (T f(z) + [b)) with
TOERM, Ir_ lop vi MRMRM (Rea((h)) =
2 log hr (f(i))))) v. (15)
= =argmin r MRRMMM
where z g(x)), 2; = (x;) and g. {g) are i..dd dropout transformations, Br 3 4V5M Jo. and (zun(z) = (oxp(- pro Then there exists some absolute constants c, > such that,
given the encoder î and suppose x Pmm)
oi. 5
with probability at least 81
Rets (hp)
= Ex, v DDL (1 (f(((())))))
cbs cg
S Be Suff (S bmme
[ + M(Vlog Br + v BB))
[oog(11/8)) Vm
B
approxination error
generalization error
See the proof in Appendix D.5. Note that the bound on downstream classification depends on the sufficiency of the score function Suff xS f...), introduced in Appendix B.3, rather than Suff (f)). This distinction arises because we restrict ourselves to linear classifiers, whereas Theorem 3 considers arbitrary measurable functions, leading to an additional approximation error term.
Experiments
We conduct synthetic experiments to learn data representations via contrastive learning using two- layer neural networks, and evaluate them on downstream linear regression.
In the contrastive learning stage, we generate i.i.d. samples an; -O Ta). The augmentation g adds i.i.d. (0, of) noise to the first s < d coordinates of ø,, and replaces the remaining coordinates with i...d. (O, 1) noise. We apply KL and x >ccontrastive learning (Eq. and 10) with link function T(x) Ir and encoder f(-) being two-layer ReLU neural network mapping Rd to R We set = 10, = 100, n = 500, hidden dimension 64, and batch size = 64. The encoder is trained using Adam (learning rate 0.001) for 1000 epochs until convergence.
For downstream regression, we generate m i.i.d. samples (ar; y:), where æ; ~ (0, Ia) and y, (x, 0.) + Eú. with E, Ai o²) independent of x,, We choose 0, = (1//v350/])) and = 1. Using the learned representation f(x.) E R from KL (or connttrras learning,

---

InfoNCE
10a
Chi-squared
Excess risk
10:
150
500
1000
2000
5000 10000
Figure 1: Excess risk for various downstream sample sizes m. The errorbars represent the standard deviation over 10 runs.
fit a downstream linear model to predict y:- We define the excess risk of any predictor as B[ - h ( o², and evaluate the excess risk of the linear model trained on f(x,). For comparison, we also report the excess risk of linear model trained directly on the original features æ; (denoted as Direct LR). Results for various downstream sample size m and the standard deviation over 10 runs are shown in Figure 1.
From the figure, we observe that linear regression based on KL (i.e., InfoNCE) or X x--pretrained representations achieve comparable excess risks, both much lower than that of direct linear regression when the sample size m is relatively small (e.g., m = 150, 500). This suggests that both KI and -ccnttrast learning can learn "good" low-dimensional representation for the downstream task. As the sample size increases, the excess risk of direct linear regression converges to zero, while those of KL and x² ---petrrained representations converge non-zero constants. This is consistent with our theoretical results, which attribute the excess risk to non-zero sufficiency of ʃ and the augmentation error Eg. More results comparing KL (i.e., InfoNCE) and -cnotttate learning in the CLIP setting are provided Appendix E.
6 Conclusion
In this work, we present a new theoretical framework for data augmentation- -aaaed contrastive learning, with SimCLR representative example. Based the extended concept of approximate sufficient statistics, we establish a connection between minimizing the f-contrastive losses and minimizing the conditional Bregman sufficiency (CBS) of the encoder. Moreover, we show that the learned encoders can be effectively applied to downstream tasks with performance depending on their sufficiency and the error on the downstream task induced by data augmentation.
Our work opens up many directions for future research. First, as seen in Definition 1, the concept of approximate sufficient statistics is not limited to contrastive learning; exploring its applicability to other self-supervised and supervised learning paradigms a promising direction. Second, while approximate sufficiency quantifies the information preserved by the encoder, it does not reflect the redundancy in its representation. Thus, would be interesting to generalize the concept of minimal sufficient statistics and develop practical algorithms for finding representations that both approximately sufficient and minimal. Lastly, our work mainly focuses on the empirical risk minimizers in contrastive learning. Understanding what representations are learned and how training algorithms influence the learned representation remains another exciting avenue for future research.
Acknowledgement
We would like to thank the anonymous reviewers for their valuable comments and suggestions. This project was supported by NSF grants MMS-2210827, CCF-2315725, CAREER RMS-2339904, ONR grant N00014-24-S-B000 DARPA AIQ grant HR001 124S0029-A1QQ A1Q-029--I-FF-0000 an Amazon Research Award, a Google Research Scholar Award, an Okawa Foundation Research Grant, and a Sloan Research Fellowship.
10

---

Bibliography
[1] Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives in contrastive representation learning. arXiv preprint arXiv:2106.09943, 2021.
[2] Jean-Yves Audibert and Olivier Catoni. Linear regression through pac-bayesian truncation. arXiv preprint arXi:: 2010.
[3] Alexei Baevski, Yuhao Zhou, Abdelrahman Mohamed, and Michael Auli. wav2vec 2.0:
A framework for self-supervised learning of speech representations. Advances in neural information processing systems, 33:12499-12460, 2020.
[4] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. Theory of cryptography conference, pages 635-658. Springer, 2016.
[5] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pages 15997-607.. PMLR, 2020.
[6] Imant Daunhawer, Alice Bizeul, Emanuele Palumbo, Alexander Marx, and Julia Vogt. Identifiability results for multimodal contrastive learning. arXiv preprint arXiv:2303.09 2023.
[7] Virginia De Sa. Learning classification with unlabeled data. Advances in neural information processing systems, 6, 1993.
[8] Ronald Aylmer Fisher. Dispersion on sphere. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 217((130):295-355, 1953.
[9] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. arXiv preprint 1803. 2018.
[10] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent-a new approach to self-supervised learning, Advances in neural information processing systems, 33:21271-21284 2020.
[11] Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. Proceedings of the thirteenth international con- ference artificial intelligence and slatistics, pages 297-304. JMLR Workshop and Conference Proceedings, 2010.
[12] László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. A distribution-free theory of nonparametric regression. Springer Science Business Media, 2006.
[13] Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011, 2021.
[14] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 7729,9738, 2020.
[15] R Devon Hjelm, Alex Fedorov, Samuel Mavoie-Marchildon, Karan Grewal, Phil Bachman, Adam Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. arXiv preprint 17X6601808.00670, 2018.
[16] Daniel Hsu, Sham M Kakade, and Tong Zhang. An analysis of random design linear regression. arXiv preprint 1rXiv:1106.2363. 6, 2.11.
[17] Weiran Huang, Mingyang Yi, Xuyang Zhao, and Zihao Jiang. Towards the generalization of contrastive self-supervised learning. arXiv preprint ar arXiv:2111.0074. 2021.
11

---

[18] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoe Le, Yum-Hsuar Sung. Zhen Li, and Tom Duerig. Scaling up visual and lsionnlanguage representation learning with noisy text supervision. In International conference on machine learning, pages 4904-49) PMIR, 2021.
[19] Robert W Keener. Theoretical statistics: Topies for core course. Springer Science & Business Media, 2010.
[20] Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. Advances in Neural Information Processing Systems, 34:309-322 2021.
[21] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi. 2 Bootstrapping language-image pre-training with frozen image encoders and large language models. In International conference on machine learning, pages 19730-19742. PMLR, 2023.
[22] Ralph Linsker. Self-organization in a perceptual network. Computer, 21(3):105-117, 1988.
[23] Yiwei Lu, Guojun Zhang. Sun Sun, Hongyu Guo, and Yaoliang Yu. f-micl: Understanding and generalizing infonce-based contrastive learning. arXiv preprint arXiv:2402. 10150, 2024.
[24] Kanti V Mardia and Peter E Jupp. Directional statistics. John Wiley & Sons, 2009.
[25] Ryumei Nakada, Halil Ibrahim Gulluk, Zhun Deng, Wenlong Ji, James Zou, and Linjun Zhang. Understanding multimodal contrastive learning and incorporating unpaired data. In International Conference Artificial Intelligence and Statistics, pages 4348-4380. PMLR, 2023.
[26] Mehdi Noroozi and Paolo Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. European conference on computer vision, pages 84. Springer, 2016.
[27] Kento Nozawa and Issei Sato. Understanding negative samples instance discriminative self-supervised representation learning. Advances in Neural Information Processing Systems, 34:5784-5797, 2021.
[28] Kazusato Oko, Licong Lin, Yuhang Cai, and Song Mei. A statistical theory of contrastive pre-training and multimodal generative ai. arXiv preprint arXiv:2501.0464) 2025.
[29] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding, arXiv preprint arXiv: 00000007788. 2018
[30] Ben Poole. Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference on Machine Learning, pages 5171-5180. PMLR, 2019.
[31] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning. pages $748-8763. PMLR, 2021.
[32] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. A theoretical analysis of contrastive unsupervised representation learning. In Interna- tional Conference on Machine Learning, pages 5628-5633 PMLR, 2019.
[33] Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. Conceptual captions: A cleaned, hypemymed,, image alt-text dataset for automatic image captioning. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2556-2566 2018
[34] Liangliang Shi, Gu Zhang, Haoyu Zhen, Jintao Fan, and Junchi Yan. Understanding and generalizing contrastive learning from the inverse optimal transport perspective. In International conference machine learning, pages 14408-31421, PMLR, 2023.
[35] Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha. The trade-off between universality and label efficiency of representations from contrastive learning, arXiv preprint arXiv:2303.00106, 2023.
12

---

[36] Ravid Shwartz Ziv and Yann LeCun. To compress or not to compress seaprressssssssssuurriiiii self-supervised learning and information theory: A review. Entropy, 26(3):252, 2024.
[37] Kihyuk Sohn. Improved deep metric learning with multi-class n-pair loss objective. Advances in neural information processing systems, 29, 2016.
[38] Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Com- puter Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16, pages 776-794. Springer, 2020.
[39] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. Journal of Machine Learning Research, (2(281))1-31) 2021.
[40] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMLR,
2021.
[41] Anna Van Elst and Debarghya Ghoshdastidar, Tight pac-bayesian risk certificates for contrastive learning, arXiv preprint arXlv:2412.03486 2024.
[42] Julius Von Kügelgen, Yash Sharma, Luigi Gresele, Wieland Brendel, Bernhard Schölkopf, Michel Besserve, and Francesco Locatello. Self-supervised learning with data augmentations provably isolates content from style. Advances in neural information processing systems, 34: 16451-16467, 2021.
[43] Dietrich Von Rosen. Moments for the inverted wishart distribution. Scandinavian Journal of Statistics, pages 97-109, 1988.
[44] Martin J. Wainwright. High--Dimessionll Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/978 108627771.
[45] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In International conference machine learning, pages 9929 99399 PMLR, 2020.
[46] Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap. arXiv preprint arXiv:2203. 13457, 2022.
[47] Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self self-supervised contrastive learning. International Conference on Machine Learning, pages 11112-11122 PMLR, 2021.
[48] Xiangxiang Xu and Lizhong Zheng. Dependence induced representations. In 2024 60th Annual Allerton Conference on Communication, Control, and Computing, pages 1-8. IEEE, 2024.
[49] Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre-training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11975-1 1986, 2023.
[50] Richard Zhang, Phillip Isola, and Alexei A Efros. Colorful image colorization. In Computer Fision-ECCY 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part III 14, pages 649-666. Springer, 2016.
[51] Roland S Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979-12990. PMLR, 2021.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. [No] [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
This is a theoretical paper. We provide a summary of our results in the abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
14

---

Justification:
we have discussed the limitations of our work in the paper.
Guidelines:
The answer NA means that paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: it can be seen from the theorem statements and the proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: we did not run any experiment in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
15

---

If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
we did not run any experiment in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
/guidees/CoeeSummissss
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss... //nips.cc/publllee wttp:ccccppppccccccccee/occppcpa /CodeSodmmmiiicc
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
16

---

Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: we did not run any experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: we did not run any experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: we did not run any experiments in this paper.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
17

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //teurips.....e wtt.riissccccceeeeeecooooooo cc/public//eiccccccccccccc wttpe/ttiiiiiieeeiiieeeeeeeeeeee
Answer: [Yes]
Justification: the authors have reviewed the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: not applicable
Guidelines:
The answer NA means that the paper poses such risks.
18

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: this paper does not involve crowdsourcing research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: this paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: the core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : //tperrpss...e/eee Cwttrripscc///oooeeo for what should or should be described.
/LLM)
20

---

Appendix
Table of Contents
A Related work
21
B Properties of approximate sufficient statistics
22
B.1 Equivalence in Definition
22
B.2 Properties and examples
23
Sufficiency of similarity scores
Proofs Section
26
C.I Proof Eq. (6)
26
C.2 Proof of Theorem
26
C.3 Proof of Theorem 2
30
C.4 Proof of Theorem
31
C,5 Proof of Theorem 4
32
D Proof' in Section 4
33
D.1 Proof of Theorem
33
D.2 Further results in Section 4.1
34
D.3 Proof of Corollary 1
35
D.4 An end-to-end result on downstream linear regression
36
D.5 Proof Theorem
38
D.6 An auxiliary lemma
42
E Additional experiments
A Related work
Self-supervised learning and contrastive learning. Self-supervised learning (SSL) dates back to the early work of De Sa [7], which leverages cross-modality information as a self-supervised substitute for labels to improve classification performance. In the past decade, SSL has been explored image classification through various data augmentations, including rotation [9], colorization [50], and Jigsaw puzzles [26]. More recently, contrastive learning based on paired and non-paired samples has emerged as prominent approach SSL [14, 5, 10, 18, 31J. Notably, SimCLR [5] learns image representations by minimizing the InfoNCE loss [29] on randomly augmented views of images, while CLIP [31] does so on paired and non- non-paired image-text samples.
Choices of the loss function. Various loss functions have been used in contrastive learning, including NCE [11], InfoNCE [29], Multi-class N-pair loss [37], SigLIP [49], f-MICL [23]. These losses utilize cross-entropy and its variants distinguish paired from non-paired samples. Most relevant to our work is the InfoNCE loss [29], derived based on the InfoMax principle [22, 15).
Theoretical understanding of contrastive learning. Thus far, there is a rich body of literature on the theoretical understanding of self- supervised learning [32, 30, 38, 45, 42, 27, 51, 1, 39, 40, 13, 17, 47, 20, 46, 6, 34, 35, 25, 36, 41, 23, 28]. Notably, early works [32, 45, derived generalization error bounds for downstream classification tasks, using linear classifiers trained on representations learned by minimizing the InfoNCE loss. Wang and Isola [45] explained contrastive learning through align- ment (pulling paired samples together) and uniformity (separating non-paired samples). Zimmermann al. [51] showed that InfoNCE minimization can implicitly learn the inverse of the data- eata-generating function. Tosh et al. [39] demonstrated that contrastive learning recovers document representations
21

---

that reveal topic posterior information in document classification problem. More recently, Van Elst and Ghoshdastidar [41] derived new PAC-Bayes bounds on the generalization error SimCLR using bounded difference concentration and applied them to downstream linear classification. Compared with their results, our generalization error bound in Theorem is independent of the batch size K and thus allows for large or full-batch learning. The most related work to ours is Oko et al. [28], which introduced the concept of approximate sufficiency to assess the quality of representations. They also demonstrated that the learned representation from CLIP [31] can be effectively adapted to several multimodal downstream tasks in a joint hierarchical graphical model.
Our work differs from existing theories of contrastive learning in several aspects: (1) Similar to Oko al. [28], we derive more refined "excess risk bounds" instead of the "absolute risk bounds" established under structural conditions for downstream tasks in many prior works. (2) We derive novel unified risk bounds for downstream tasks that depend solely on the sufficiency of the encoder and the error induced by data augmentation. (3) We extend the concept of approximate sufficient statistics and theoretically analyze a broader class of contrastive losses.
B Properties of approximate sufficient statisties
In this section, discuss properties of approximate sufficient statistics introduced in Defini- tion I and provide some concrete examples.
B.1 Equivalence in Definition
Lemma (Equivalence of three forms of sufficiency). The ILS, VFS, CBS definitions in Desinition / are equivalent, i.e., for any statistic T
Suffn,(()) Suffver Suffet, =: (Tf,
Proof of Lemma 1. (ILS) + (VFS). Note that by the variational form of f-divergence, we have
Y)
inf RE((,)) (-((, y)] (e()) [1* (S(x, y))]
S:NxY'R
inf R. Ep(a.)) S(x, v) (f - Sz)l
inf E Ex(xy)) I- S. S.X
inf
(f S,(x) + Sx(x)] 5xxxy-R
inf
Rs(S).
Similarly,
Y))
inf B orgp (f
5.T(X)xy-R inf 5.T(x)xy-x R E (- T(x)
inf | S,(T(=))) +,((()))
inf x-
Er Er [-S(T(x),s)))
inf E of (z(T(=))) S.((())) -
inf R T).
x
Combining the two results yields the equivalence between (ILS) and (VFS). (ILS) (CBS). By definition of the (ILS)
Suff I(X,Y) - - (TT((X))) P(x,, v)
P(T()),
(P(()))())
) ((x))(()dd
P(T(()))(W) P(T(x))P(())
P(ylzz)
P(x))P(y)d f (())T(()) P()))
P(v)
PPy)
[{(
Plylz)
P(y]T(x))
){ (Tf),
F(y)
P(y)
22

---

where the last equality follows since
P(y]T(x))
P(ul=) x
P(vlT(a))
B
P(w)
P(())
P(v)
P(ylT(z))
P(y)x))
P(u]T(x))
[(x))
E
P(u)
P(v)
P(v)
P(ulT(x)))
((
P(UT(()) 0.
(16)
P(v)
P(y)
An equivalent expression of (CBS). We now show that P(ylz)
P(y]T(x)))
Br P(ylx) (
]
(P(2)xB())
B₁
inf (2))))(())
Ep(O)xP())
P(y)
P(y)
P(y)"
P(y)
This follows immediately as for any Q (()) ~ A(D)
P(yy=)) Q(ulT(x)) ) Ep(2)xP(o)
B P(y(2) P(vIT(=))
BP())x7())
B P(y)
P(y)
P(v) ' P(y)
[r( ((
(
QQy)T(z)))
P(ylæ) Q()T(()))
TP(y)
P(y)
IP(y)
P(y)
P(y)
F Q(vlT(z))) (P((TT(>)) P(yla))
)} -0,
P(y)
P(y)
P(y)
where the first equality uses Eq. (16).
B.2 Properties and examples
Lemma (Global minimizers of R₂(S)). Recall
R₁(S) = Er(a,))-S(2z, y)]
inf EPGoy (S
(S(x, v) Sz())) + Sx))
Sx:X->R
For f that strictly convex and differentiable, the following results hold for Rt(-).
(I). The infimum the definition of Re(-) is obtained by Sx(x) such that ((t
(x()) for all a.
(2). Let (x,,)) = P(aa)) P(Z)F
The global minimizers of for- the
Mr x R, 5(x, S.(x,y) Sx(x:) for some S. X TR3.
Proof of Lemma 2. For any fixed x, we have
V.Eroy [f* (S(x. y) c) + cl If - c)
Claim (1) follows immediately from setting the derivative equal to zero and noting that Vf* = (f')-1.
To prove claim (2), first that adding any function S (x) S(x, y) does change the value of R&(S) due to the infimum inside the definition of RR)S). Therefore, it suffices to show that the unique minimizer of
(S( == EF(x. I-S(x, y)1 + [E v))
S. f' ((z))(()) Write 5 = S. + ch. can be verified that R₁ + ch) is strictly convex c.
Thus S. is the unique minimizer of Re if V [r + ch))c-o for all h. This is true since
V.Ri(S. + ch)le=o Ep h(,, y) + Ep( V (S( b)) y)1
Pr xr y) P(x)
Ep h(r, y) (p(
h(x, v) = 0.
where the second inequality uses the property of convex conjugates that (f* =
23

---

Lemma 3 (A general bound on (IV(P[)) based on sufficiency.). For in Definition I that is twice continuously differentiable, and for any statistic T, we have
c2 (SlTaaasee)))
(17)
where C2 : (2inl (x.)))esnsuuppp(...) ("
P(y) and supp y) denotes the support of P(z)) P(y). Notably, when f(z) (x 1) (x2 diveegeecce,, have co 1/v2.
P(yla)
1122
x
Proof of Lemma 3. Using CBS form of sufficiency, we find that
P(ylar))
P(VIT()))
(T) = (p()))P(s))
Br
P(v)
P(v)
(P(()a)) ((((Pr())))
((ul=)
P(ulT(a))
Be(a)xP(w)
2
P(y)
P(w)
P(w)
inf 1" ((ylar)
P((yl=)) P(v)
P()I(())) $
Ep(E)xp())
2 (m.a))ssuppxx.))
IP(y))
P(v)
where the first inequality follows from the definition of Bregman divergence and the fact that the range of P())T(x)) belongs to the range of P(ylæ). Moreover, by Jensen's 's inequality, we have
[ ((ylz)
(ENTT(2)) 1/2
P(yl=)
P(y)
(Ep()))P())
B((z)xP(w))
P(y)
P(y)
P(y
Ply)
2k Drv (P(u)))
Putting pieces together yields Lemma 3.
Example 1 (KL-sufficiency). Take f(x) = x log (KL-divergence). then we have
Suffeb,r ) = (B((z) DKL (P())))|IP((/T((=))) BB
and Rx( (p(x.)) S(x 8)] Ep(x) [log [exp)exxpS((: y))ll.
It can be verified that the InfoNCE loss in Eq. (2) is asymptotically unbiased estimate of Re(S) as the batch size K + oc (see Eq. 6). Moreover, by Pinsker's inequality
(Pr.) < V2 SSfffeb.u(TT)..
Example 2 (Chi-sufficiency). Take f(x) (x 1)2/2 (x2 -dieergence) then we have
P(yl=) P(y[T(x) )
Su = (P(2))
P(y) (P())
R[(S) = (- y)1 + I(S(2,))(((z, v) - v))) S(z,v).
Lemma gives
v2 VSuffabb
Also, we can bound the divergene by the sufficiency:
P(T()))P(U)
(FG)) < Suffat.(T)).
sup
(a. (w.w)ssupp(e..) ((T(x),))
Example 3 (Squared Hellinger-suffciieney) Take ((x) for x < 0, and
vx, then we have I (x:) -1
Suffeb.r(T) EF(w) (1(P) HTTp:///AAEEEIIHPGPPUUUUUUUUUUTE
where (p(p)) S(vp(=) v(==) dx/2 22/2/ the squared Hellinger distance. Similarly, the
squared Hellinger distance between Ply (r), (P())T(x)) can be bounded by the sufficiency Tf
Eg(1)  [[((()()) Ep(w)
24

---

(()(())))
( 2 2 PV(((((z))
Evp(v) (F(())
sup (#.)))s)pp(x.gg)
P(T(z))P(())
y
P(T(22),)
sup (s.p))s)pp(x.g)
P(T()))P(y)) Suffeb.r
where the last equality follows from
E P(yl((()) - <P()))) U. T())
v (x)) P(yla
P(u[T())) - P(yl))
E (VP(T)((E)) - P((l)=)
y, T())
+ E
y, V,
2 F()[(()))
2 (()))(
((y] ))
y. v.T(x)
2 (())
B.3 Sufficiency of similarity scores
The definition of approximate sufficiency can be extended score functions X' y that measure the similarity between (X,Y)
Definition 2 (Approximate sufficient score functions). Let S x - R be a similarity score function. It induces a conditional density Ps X x y w.E.t the base measure μa via
Ps(ula:) a:) (()) (S(x
for all We define the where S(x, v) S(x, u) (a) such that ( sufficiency S in two equivalent forms:
Variational Form Sufficiency (VFS): The variational form sufficiency of is given by
Suffvr.((S)- RR(SS)
inf
R²(S),
3.XxY=R
and the f-contrastive loss
RS( = -BR...n inf R [F v) Sx())) Sz(x),, (18)
where f* the Fenchel-dual of
Conditional Bregman Sufficiency (CBS): The conditional Bregman sufficiency of T is
defined as
Suffeb.r(S) (E(() Bi P(y]x) Ps(gl=))
P(y)
P(y)
where Br(a,b) f(a) f(bb ((a bb) is the Bregman divergence off.
Note that the excess risk of the contrastive loss equals the sufficiency of S under our definition. Similar to Definition 1, we have
Lemma (Equivalence of two forms of score sufficiency). For any similarity score S X - R. the three forms of sufficiency in Definition 2 are equivalent, i.e.,
(S) Suff(b,1(S) =: (S)
Proof of Lemma 4. (VFS) (CBS). Let S.(x. v) ('( P(z.y)
(((()))))) We have by Lemma that
S, Rrgming,,(S5) (5). By the definition of the (VFS), we have Suffvr,r(S) RS(S)) Rr(S.)
EE(z,y) (S. 5(x, y)] + ErGOr (F (S(x,8)) 1* (S. ().
(1) [S. - 5(x, v)] + (2(0)) (P())P())
P(x, y)
P(x, v) P())
S. (2
25

---

Ep(z, [5(x, w)] + Be(o) [1 (xx Becerte) [ (())))(())) v) )
E B 1S y)] + (ww)) [ P + Ps(u(z)
v)
S(1, -f (s(ular) P(y)
((x))(())
PP())
[ P(ylz)) Ps(ul=)) E ((())
P(ylz)
Ps(U(T)
= =Br
S( v)
P(y)
PP())
where step (i) and (ii) use f((f))+(z)) + (*) = xz)))=(z) with 2 = S. y) and S y). respectively. Since S(r,y) ["( -1())=)) ). it follows immediately that Sullvr,r(S) = Suflebbr(S).
Example 4. Take f(x) log (KL-divergence). Then S,(x,y) log (F(a,)) Be(a,b) a aloo(a/b) (a b), and PS(() IP(y) exppsstaalll//eeeleelssi v)) Also, have
) Ps(v|=>)
P(ylz)
Suf = R((S) - Rs(S.) P(ylz)) log
(P(ul=)-Ps(vuia)) (=(()=)) P(x)ddy de
P(x))))) (PPy)az) [P(yy/=))]
Example 5. Take f(x: = (r 1) (x2 diverrgeec Then S. S. v) = P(z, v)/(P())P(v) 1,
b) = (a- ba/-))//2 and Ps(((()) = P(v) ((v - -E,](( v)]
+ 1). Moreover,
(P(u)æ)) - ())()==)))
Suff buff> (s) Re(S.) Ep(n)>P(O)
P(y)2
(P(y) - Ps (v(x))) 2 P(yl)
= Ep(w) Σ
P(yl=)
P(w)
P(x, v) P(z)P(y)
inf (a. (spp))))
Exc (XP([))))))))))))((11))
C Proofs in Section 3
C.1 Proof of Eq. (6)
As given in Example 1 (which can be established using Lemma 2), the KL-contrastive loss has the form
(S) (0)) S(( x =22) + Bgo [log Ee [,
Recall the SimCLR loss Reimclr, x (S) in Eq. (2). We then have
lim Raimetr,<(S)) logg K
K-00
exp(S(z(1) (1) 11(2))
exp(S(z))) (1) -2(2)) 2 EjE[K] exp exp(S(z))) ; (22))
1 lim E log
- log
K--00
Σ exp(S(z)) (1) 2 ()) K
E log Σ (xp(S(z()) (1) 22) ))² /K] E [[eexp(S(2)) (1) 21 (2) = Rs)())
= Jim
K-00
JE[K]
where the second equality follows from the symmetry of in its arguments and the last equality uses the law of large numbers (note that 2 is independent of x for j * 1) and the bounded convergence theorem.
C.2 Proof of Theorem
We begin the proof by stating the following proposition that connects the excess risk with sufficiency.
26

---

Proposition 8 et al. [28]). Suppose Assumption I holds and S. is global minimizer of Rsimcrr (S) as defined in Section 3.1. Then, there exists a constant C > which depends polynomially on Bs, such that for any function f E F, its sufficiency can be bounded by its SimCLR excess risk. Namely, for any K 2, we have
of SimCLR as near- sear-suuficient statistics: Proposition 1 in Oko
Suff(f) lim K'-20
Raimelr, K kry))) Raimclr, (S.))r,K(S.)) (S.)) &
Rsimelr, x xSy)) Raimer,, & (S.)
(1+ C K
SimCLR excess risk
similar version of this result has been established for contrastive eonguage-image pretraining (CLIP) in Proposition in Oko et al. [28]. The proof of Proposition 8 follows immediately from the proof Oko et [28] as the SimCLR setup can be viewed as a special case of CLIP in which the text and image follows symmetric distribution conditioned on their shared information.
of Proposition
Adopt the shorthand notation Rx for Rsimer, With Proposition 8 at hand, we obtain the following decomposition for some C > 0 polynomially dependent on Bş
Suff( f) <
(k - Rx(S.)] (1+
K
[ (5p) inf Rx + [inf Rx((,) Rx(S))] (1+ C KK) JEF
JEF
(s)())) inf Rx (S feF
(1
x +
C'
inf Rx(()) - - Rx()) (1+
C K
JEF
generalization emorr
approximation error
Therefore, remains prove the following bound.
(1). With probability at least 5, the excess risk
Rx(Sy) inf (s,) &
C Vn
V Tog(115) B²
21log Bs+
Vog 12.000 F)
fEF
(19)
for some constant C' that is polynomially dependent on Bs.
Proof of Eq. (19). Recall the definition of Raimetr, K in Eq. (3) and adopt the shorthand Rx for Raimdr,
Let By == / B, (log Bs + B7), == c + 1)B, B, for some absolute constant e >>> 0. It can be verified by Assumption 2 that F must satisfy |f 02 & By for all f E F to ensure Assumption 1 We will show
holds. Define the zero-mean random process y = Rk(S,) - (S)),, f f that
P P([sup sup X,1 JEF
B[sup fe X, 1) & 2exp
(-
2nl
for all t and
(20a)
9B3
E[sup X < E|| fa
El
sup
Xx
Xy1l
fer
f.f
B nn
B
2B,
32
v
Nog,((u, || 12,0, F)du
(20b)
Vn
for any So E F and some absolute constant e > Combining the two bounds and noting
(5p) inf RR (S,) & 2 sup feF
Rx RR (S,)
ssu R (S,) - EJRK (S = 2 sup X
fEF
feF
fEF
(21)
yields claim (1).
27

---

Proof of Eq. (20a). Let 2, (z.²) )2 Then (a are iid. pairs of augmented views. For any i E [n E [K], suppose +j is replaced by some alternative sample (((-))++ = 222) [y((z).... (111))+))) 2,) - X 21. ........ (()-)) 2,,1 (Z).,) (11)))++ 1)K
(2 1) ((-))K+)) in the calculation of Rx(S)). Then we have
k,) (x () xn)l & U1 + U2.
(22)
where (assuming 2 = ng for j [n|]| [((2 1)K + j})
U1 = 1
( (1)
(1- (
Sy Sy
200 (()))+ &
2 2oo Bs
nh
n
and
1 K
U2 =
Σ
log
Σ
exp(S)
(2) ((1))++1))) + log
Σ
(xp(S (
2m k=1
K
K [E[K]
[E[K]
[log
exp(S) (1)
[22)
((u)++ح))) log
Σ
exp(S) (1)
(1-1)K++ ( (()))++
(22)
(i-1)*+**
K
[E[K]
(E[K]
(6)
B5
exp(Sy (1)
1) ( (--))-11)))
(2)
Σ
exp(S (1)
x(2)
2n
K
(1-1)
[E[K]
[E[K]
+
1 K
exp (x (i-1))=++ (1-1)K++ - Σ
exp(S) (1)
(1-)) (
(2)
|E[K]
[E[K]
Bs
K
K
exp(S, (1-
(1-)) ( (1
(1)
(2)
nK
(8)
2B 1)
Here, step (i) follows from the triangle inequality, Taylor expansion of log(x), and Assump- tion I; step (ii) follows from Assumption I and noting that exp((S(>>()>>>> (f-1)))+tt (2(-)))(11)1++111
(-))+))
(2)
exp(S, (1) (--))+
((2) ((-1)++1) # 0 for at most 2K terms with indices k, I E [K].
Putting pieces together, find
((--1) +5
kn) -
2 2oo Bs + +2B -2 2 $ 3B²
for any -(= and any i [ma].j [K] and all f F. Therefore, Eq. (20a) follows from Corollary 2.21 in [44] for functions with bounded differences.
Proof of Eq. (20b). First, we have B[[X < cB5/v by properties of sub-Gaussian variables and the fact that, for any fo E F, Xr, is zero-mean with bounded differences cB3 /n, as implied by the proof of Eq. (20a). By Dudley's entropy integral bound (see Theorem 5.22 in [44]). it suffices to show {X,, E F} is a zero-mean sub-Gaussian process with respect to the metric Px( f) = Blʃ - /l2.///v.
Let |0 inf(t 0 B[v(x/t)] < 13 denote the Orlicz norm for random variables and let (b((u)= exp(u?) - 1. We have
- - Xyl0= = Rk,) - Rx(S)) (S) - RK(Sy)]lle, & &C(UU, - ETU + ||Ua E(Uallo))
(23)
28

---

for some absolute constant > 0 (we allow the value of e to vary from place to place), where
K U'3 =
( -5)())))S())))))) x
(2)
U²:= := _ ΣΣ ΣΣΣ
1 A1
[ log
L
Σ
exp(S,
exp(S) (2)
2 2(2) {()))+)))) + log
1 Σ
(2)
(
2n
K
K
[E[K]
[E[K]
- [1o88
Σ
exp( ((=))) (()))))))) + log
(2)
1
Σ
exp(S)(2
2 {
K
K
[E[K]
[=[K]
remains to show both Uz- E[Us]] and U4 - U[ are px (f. uub-Gaussian.
Notice that for any 21)) x2)) E X J E F, by Assumption 2, we have
1 - - Sy(2 ((11 < B, (f(2(1)) f(x(²)) (F(2(1), F(2(1)1))
$ B+(lf(z(2) (2)) |11 - A12.00 + 1f(2("))22 1f - fl fl12,0)
(1)
B,I I1l2,00
(24)
(2) 2, ) it follows immediately that U3- [ is 2B, B,Ilf - ff22,0// /n--ub- Gaussaan, i.e.,
where step (i) uses Sy z) = 1 < B7 for X. Since ā, =x,,)
i [m] are i.i.d.
<B,B'1I 11f - f12,,0
|U/s - Blall و2 <
(25)
vn
Recall the definition of {E., 8,)%_1 in the proof of Eq. (20a). To bound [|alllys we start with introducing the shorthands for any fixed indices i [m.].jj [K]
ux(z)= = K
Σ [E[R]
(1) (xp(S (+-))+++** (-)))))) Vx(z)= = K
Σ
exp(SS((2 (1)
(1-1)) ((-))++)))
(2)
[E[K]
Úx(z)) = 1 Σ
(xp(S,(2
(1- ()),)) Vx(x))
(2)
1
Σ
exp(S ( (1)
(i-1)K+1* (-))++))
(2)
K
K
[E[K]
[E[K]
for all k E [K]. Similar to the proof of Eq. (20a), for any given index (i - 1) + j. we have
(1( kn) - U2 UZ(21........
((111)) 1m, 24 (2)
1
(x((z)
1x(2))
Vv (2)
log
+ log
- -log
- log
2n
(4)
(2)
(3)
(2)
B2
K
(z)
(x)3)
(x(2))
(x)
+
2n
(x))))
(2)
(x)))
Di (2)
where the last line follows from Assumption I and a Taylor expansion of log(z). Moreover,
Ux(Z))
u&(3)
K
(x) - (l((z) (x( (1((3)
= Σ
(x)
(x)
(1)
(x(
k=1
(18
BS
( (2) - -(((()))( - ((1(22) - (E)
<
B3
Σ [[((UR - -i)) -(Ux (3)) (2)1 + 104 - (Z)((())) it [2))
(144
B3
[[(24x -ix))=) (24x (Z)) + 2B, B.I f Fla.,x((n. - (i],
29

---

where step (ii) uses Assumption 1, step (iii) uses Assumption 1. Eq. (24) and a Taylor expansion of exp(2). Similar to the proof of Eq. (20a), by counting the number of terms in the summations that are different and using Assumption 1, we find
K
[u((3) - [x)( & 2Bs, and
K (44 - (z) - -4- - (x)) ABs 112,00
Similar results hold for V by symmetry. Putting pieces together, we obtain
4B
B
( ; (()-)) z,) - -2, ()
n2
Therefore, follows from Corollary 2.21 [44] for functions with bounded differences that
BB
||U4 E[U4]] 12
(26)
vn
Substituting Eq. (25) and (26) into Eq. (23), we obtain that {X f E F) is a zero-mean aub-Gaussian process with respect to the metric px = Blf /l /n. n. This concludes the proof of Eq. (20b).
C.3 Proof of Theorem 2
Write z g(x) with g Fg 1 Px. Define hmin = [x))) and h(u) = (1
Px.g Po
= uj. Note that I/min (z(1) = [=]1(()))2(1] is bounded by BR, almost surely by the assumption in Theorem 2. We first show that Ro(h f) satisfies bound (7a) with eg replaced by &g inf, Ex- ( - (.))).... The original bound (7a) follows immediately since Eg E cg.
Since (a + b)2 2a² 2b2, we have
Rg(h e f) E Ez,2'0 2 , a [(((f=()) - h. (xx))²
2 [(h(f(=(1)) Aiii (z (2 + 28g.
(27a)
Introduce a random variable which follows the distribution 211) conditioned on f(z(1) and independent of (=(1),=(2) when conditioned on f(=(1), i.e., [ ((=(()) 1 (2(), (2) (1)) Consider the joint distribution of the tuple (#)
By Bayes' ( (f))))) f(z(1)) and therefore
formula, we have ( d (1) Ps and z 2(2)
P( (2)
El(((((2()) hmin ( (2))))
B (hmiul (2(1)) Amin (z (2
Egas (2) P(E
minin (2(1)) Ammin (2 (2)))
(27b)
where step (i) follows from [[(h(f(z())) - Amin (2)) E (2()) Amin (2 (2) (2)
which uses Jensen's 's inequality, the independence of z(1) and 222) conditioned on (zx(1),, and the fact that (20) = h(((z())). Moreover,
E Ega - "1 ((hmmn Amii (z (2)))
(1))
Ege 10- [(hmmi (2(2)) - Mmin (2 (2(2)))
+ / V2B Ega=p / DKL (P (Pataaaa) (1 PPrR) [220))000(((((000)
(111
& (() (0) [(Amin - 1mii (=)n(( + v2 Suufeab,u())
30

---

(1)))) (Aminn((() Amii (2())) + V2B, VSuffaa.u(())
(27c)
where step (ii) follows from the variational form of total variation distance and Pinsker's inequality, while step (iii) uses the (CBS) definition of (fffai(f) in Definition and Jensen's 's inequality. Lastly, have from triangle inequality that
Ex 2x))) [[hmiu (z()) )) hmin (z (2
< 2 x, (n) [(Amin (z(1) h. (x)) + Ex, (Iemin(= (2)) = 4ēg.
(27d)
Combining Eq. (27a) (27d) yields Eq. (7a) in Theorem Eq. (7b) Theorem 2 follows immedi- ately by noting
- ()() ( -,.(=))))))
R(h f) = - (2o
< 2E (1) (2)) [((f(((1)) h.())) 2B 20h (2))
28 [(([((2()) - h.. (a))) + 2gg
and using Eq. (7a).
Following the same proof strategy, it can be verified that Eq. (7a) and (7b) also hold when choosing h(u)= == [1 = u]. The main difference in the proof replace Mmin by h. in Eq. (27a) (27d).
Comments on Theorem 2.
Moreover, although we consider the expected squared loss (i.e., {x. y) = (x - v) for simplicity, be seen from the proof that similar version of Eq. (7a) and (7b) hold for any semimetric {(xr y) that is convex in x for all y. This includes the absolute loss, Huber loss, losses induced by norms, etc.
C.4 Proof of Theorem
For any densities P, Q, define a-Rényi divergence
P(x)) ((x))
(PIIQ) = log Em-P
for any a O. Note that the I-Rényi divergence corresponds to the KL divergence. For any densities F, Q, T, we have the following triangle-like inequality which we will repeatedly use in the proof.
Lemma (Triangle-like inequality for Rényi divergence (Lemma 26 in Bun and Steinke [4))). Let P. Q and T be probability densities w.r.t. the same measure. Then
ka
(P(
< ka -
D ka--1 (PI[T) + (ka( x-1
for all k, E (1)
Write x g(x)) with g Pg 11 x Px and define h(f(z)) P(y]f()) A[K]] as the conditional distribution of y given f(z). where z = g(z) for some random transformation g ~ P'g. can be verified that argming
(Ply(()) [()x) Therefore, using Lemma
with = 4/3, a = (by taking the limit a 1), we obtain
R f) = En = D (PL
4E ( (
(Pr. (P()) En "a DD (P(y)= (
< 4
cls + (.,, (P: (2) [PP
(28a)
where the last inequality uses the monotonicity of Rénén divergence w.r.t a. Similar the proof of Theorem introduce random variable which follows the distribution of 2(1) conditioned on (()
and is independent of (z(1), (22) when conditioned f(=("), i.e., [g()) (=(=())(((())) I
I (2(), (2) ()) Consider the joint distribution of the tuple (2(1) (1)) 2 (2). By Bayes'
formula, we have z(1) d (1) Px and z (2)))(()) (())))(((()))))))))))))))))))()( =0)))=(((3)) f()())) and thus
Eg 2 x (Da (2) |P 1)n
& E E 2 D4 (P (2) || (()]("))
31

---

= +btpap/....uaaear/.///////aaaaaa
(28b)
where step (i) uses Jensen's 's inequality, the convexity of Rényi divergence w.r.t. its second argument and the fact that E[P {) )
f(
Moreover,
Ego 30 prw. [()
E Ega P( ",,,,
22B Bg
z0 DKT (Pa 210 P2 (-
(186)
E Bg (0x)))))))))))0)))))))))
D (P 11 + VBB / /Suffcb,w(f)
= E2 2 (D4,a (P 1()y) })} + vBB v Suffab..(())
(28c)
where step (ii) follows from the variational form of total variation distance, Pinsker's inequality and the fact that
P z (2) P(y ((1) & B,
Day (PP2) (IP())
[ = log By-
and step (iii) uses the CBS definition of (J) and Jensen's inequality. Finally, applying Lemma another time using a 4/3 and 1.5 yields
a (2) D ( P(yl [1]
E D2 (P (1) IP |3) + (. P & d
(28d)
Combining Eq. (28a) (28d) yields Theorem 3.
C,5 Proof of Theorem
Let f(z) (r 1)2 The proof largely follows the same arguments as the proof of Theorem 1. Thus we only provide sketch of the proof here. First, it can be readily verified that the set of minimizers of (S) is
P(z(1), 22))) P(z(1)) P(z(21) }
Ms {s: s S S. const for some const R, (2)2 (2)
Moreover, basic algebra shows that Rehisa, x (Sy) is unbiased estimate of Ry Thus, by the VFS in Definition we have the decomposition
Suff ( & Re(S Rs, & [R(S)))
inf (s())) fEF
+ inf Rc(S,) R(((s)) JeF
generalization eror
approximation ervor
Therefore, it remains to show
(I). With probability at least the excess risk
cB Vlog(1/0)
Rr(Sy) inf Rr &
B²
Vlg.N(u, F)
JEF
vn
(29)
for some absolute constant e > 0.
Proof of Eq. (29). Recall the definition of Rebisq, in Eq. (10) and adopt the shorthand R for Rehisa, Let By / (Bs B,), B : csBs + 1)B, B, for some absolute constant 0. It
32

---

can be verified using Assumption 2 that F must satisfy 2l & By for all f F for Assumption 1
hold. Define the zero-mean random process X Rk(sy) (S)]; f F. We will prove that for some absolute constant c >> 0
Xyl]| > 1 & exxp (- cnt²
feF F([sup sup 1
E (sup fef
for all / > 0.
(30a)
B
B2
2B,
E[sup Xyll & X 11 + El sup /eF
, - Xyll &
+ 32
V log 1l F2,
fIfeF
v1
vn Jo
(30b)
Combining the two bounds and noting
Rx( inf Rx,(S)) = 2 suu Rx((y)) - Rx ssup Rxx(S,) - [[ = 2 sup X,, feF
Jer
feF
feF
yields claim (1).
Proof of Eq. (30a). Similar the proof of Eq. (20a), we establish the bound using concentration properties for functions with bounded differences. Following the notations in the proof of Theorem 1,
we let 2; = (z (1) (2)). For any i E [m,], j E [K], suppose 1(i-1) replaced by ())
(2 1)K+5* 212) ()-1) in the calculation of R (S,). It can be verified using Assumption that |x
........ Z +)* ; .,,) X ($1..... () 2n)
Z (1-1)K 2n)l & cB²
= (R
((-1))++ ((-.))tt)....,,,. zn.) -
(31)
for some absolute constant > 0. As result, Eq. (20a) follows immediately from Corollary 2.21 in [44] for functions with bounded differences.
Proof of Eq. (30b). Similar to the proof Eq. (20b). 5 < cBg/v by the properties of zero- mean sub-Gaussian variable Xfo- and therefore, to establish Eq. (30b), it remains to show (X f, ʃ e F} is a zero-mean sub- aab-Gaussian process with respect to the metric px f) Blf /12.///n.
Let |æl == inffl > 0 B[v(a/(] < 1} denote the Orlicz norm for random variables and let (b2(u) exp(u?) Note that for any 2(1), 222), 2(2) f. F, we have from Eq. (24) that
(1)()
(2) 22)) S)(2 | Byll/ f12,00
(32a)
and
((S)(z()) 2(()) - ()) 22)))) (5)(x x2)) - 55(x (()))))))))))))) (2))))²1
& (Bs([S)(z(1) (1) x2)) - S) x 21) + 1)) 2(2)) S5(x(1), ,)(x(1),x(2))) 2(2)))
< B, - f1,,x1
(32b)
where step (i) uses Assumption 1. Then, following the proof of Eq. (20b), it can be verified that
XX, - Xyl02 = [k,) - Rx(()) (S)) - (x(S))]l < af c(Bs + 1)B, B, |l - f1..00
Vn
D Proofs in Section 4
D.1 Proof of Theorem 6
Recall that B = Be. For linear regression with misspecified model, by Theorem 11.3 in Györfi et al. [12] (see also e.g., Thcorem 1.1 in Audibert and Catoni [2]), we have
E6 Riin (h,)] - o² < 8( inf Rin (h₂) 02) + c(B² + 02 p log m
MERP
33

---

for some absolute constant > 0. Thus suffices to show
inf Rin(hr) 0² < S cg) yeR
(33)
for some absolute constant c > 0. Equivalently, we only need to find some E IP such that Riin (h,) satisfies the bound in Eq. (33). On the other hand, from the proof of Theorem 2, we see that if we choose h.(z) (z) = (x, 0.) and h(u) == (=)f()) = u| = (0., [() = u]) then the excess risk
Riin Rin(n) x² cCB 02 (uff((f) + cg)
for some absolute constant c >> 0 by Theorem and Proposition 5. Therefore, it remains to show is linear in f=)). Note that f(z) Wz. Let Wt W (W W - RdXp be the generalized inverse of W and ीं W 0. R". In fact, choosing î W 0. E RP, we have
h(()) = (0., [[=[ = uI) = (0., El + (la W W [)=lf(z)) u)> (0.. W'n) = (n, u),
where the third equality uses the assumption that E[ w Wz] almost surely.
Comments on Theorem 6. A similar bound can be established for the risk Ran (ha)) with high probability under additional sub-Gaussian assumptions the representation f(z) Wg( g(x) [16]. The assumption [[ W >) W view z discarded by the encoder f does not contain any signal with a non-zero mean. Without this assumption, there may not exist linear function of f(z) that achieves small risk, even though Theorem guarantees the existence of general function of f2) with a small risk.
essentially states that the information of the augmented
D.2 Further results in Section 4.1
Following the setup in Section 4.1, present scenario where linear encoder f with low KL- sufficiency Suff (ff) can be found through SimCLR loss minimization in Eq. (3).
Let U (U1, U2) e Rddd where U₁ Rdxp, be some fixed unitary matrix, and define A U,UI.
(Ia U,UŞ)) 0} denote the unit sphere in the Rdd ~ (0, and consider the random transformation g such that x 21)) 2 _ Ax + conditioned on (1) S(U,) + S(U2) 3, where the noise r) ~ NN oal//p). concrete example of this transformation involves zeroing out the second half of the coordinates of the sample æ, adding some Gaussian noise to all coordinates, and then normalizing both halves of the modified sample to have unit norm. Under this setup, it readily verified that"
For [2]. we let S(U,) (o Rd ||ll||
column space of U, Assume
((=()), 211)) (
(-5 (-b((s)))
[U + U,UT
U U + T
(211) x2))
)))
1 (0ees,)))))
P(z (A0GE
((=("), oc exp U,,,, 2 (()) 1 (08(U)))) P(z(U)P(((21)
p
p
K
( +
2)
of
Note that (z(1) (2)) restricting on S(U,) follows the joint von Mises- Fisher distribution (vMF) [8]. In this case, the optimal score S. (z)))), x(2)) = (((f. f-(2(²))) + const for T(x) = KE and fz(z) = 21z. We present sample complexity bound learning in Corollary 1.
Corollary 1 (An upper bound on Suffcs..(()). Under the setup in Section D.2, let F == (s f(z) = Wz, W e Rexd and [ 1lop & Bw) for some Bw > 1, T(x) KI, and define f as the SimCLR
Us(U,) @ := (o e Rdd x 81 + n2 for some v1 = S(U1), v2 S(U2)). All densities with respect to the Lebesgue measure.
34

---

empirical risk minimizer obtained in Eq. (3) with batch size K and n samples. Then with probability least -, we have
Suff Suff & (1+ ) ddp log Bw + /log(1/6)
for some constant C >>> 0 depending polynomialty exp(x).
See the proof in Appendix D.3. Note that the constant exp(k) depends on the noise level ø. When 2 p 1//4, finding near-sufficient encoder is relatively easy. By combining Theorem and Corollary 1, we conclude that the encoder learned from SimCIR can achieve small risk in the downstream linear regression task, provided there are sufficient pretraining and downstream samples, and data augmentation does not significantly alter the outcome of the true linear model. See Appendix D.4 for an end-to-end statement and its proof.
D.3 Proof of Corollary
suffices to apply Theorem to the setup in Corollary 1.
By the boundedness of =11), (2)) and the property that (2(0) xp. ((
P(z _(=0),_00))
1, we have
F(x ((())
sup 20) P(z(U)P(((22)
P(x (2)
sup (),
((2())
P(=(1), (2))
$ exp(2x).
inf ())
Similarly we have inf (1) (2)
(( exp( -x)).
By properties of the von Mlises-Fished distribution (see e.g., [24]), it can be verified that
((=("), (2))
P(Z())P(Z(2)) = (n(n) exp ,U,
p (1 (1+02) -
K
where
Ep(k) ((pp2) 1p/2-1(())) T(p/2). Σ
k 2m
2)!!
K 2m
(5) (1)22211
mTT (m p/22)
2
(2m) 2m p 2)!!!
m=0
m=0
Σ
8
hb 2m ex, and {p(k>> > (p/(p/2) (2) =1
r(p/2)
150
(34)
(2m)!
Thus, when T(x) = kr, Assumption 1 and are satisfied with Bs = exp(2k), B, 2x (note that the condition x-1 & B, is unnecessary, as from the proof of Theorem we only need |T(((((()), x(1)) log Bs, which follows from the boundedness of F).
Approximation error. The approximation error fer Rgimelr, x xS,)) Reimelr, (S.) 0 since S. + G1 is realized by f. and the link function Txx) kæ some normalizing constant e₁ and (simdr,(S.)) Rgimdr, (S, c.).
Generalization error. Let W ( Rexd |W
op & Bw). ). First, for f((z) = W.z (i 1,2), since If - felle.00 & [| - Wello || & W W2llop it follows that
log.N (u, F) < log N 4 T 1-1..pp || W) < cdp log
4Bw
where the last inequality follows from the upper bound of the covering number of unit ball (see e.g.. exercise 5.8 in Wainwright [44]) and the assumption that p & d. Therefore,
2(lg Bs+ B.)
B,
NogN((u, Fydu os Jo
v (u, Fidu & co/dpi /log Bw
00
Combining the result on the approximation enror and the generalization error and applying Theorem yields the desired result.
35

---

D.4 An end-to-end result on downstream linear regression
Combining Theorem 6 and Corollary 1, we reach the following result on the downstream perfor- mance of encoder learned by SimCLR.
Theorem 9 (Linear regression using the SimCLR-trained encoder). Under the setup described in Section 4.1. let be the empirical risk minimizer obtained from Eq. (3) in Corollary on a restricted function space Fo {f(z) Wz E F; span (pan(W]) (span( W span(U1)) + (span(M) W (pan(U2)) - F. In the downstream task, given i.i.d. samples { y1 y:)) from proj B. (x, 0.)) +E, where x ~ NO, la/P) follows the same distribution as contrastive learning, and E ~ (0, ) L..
(a). Consider fitting a (random) linear model hx)(:)) = (f(2),)) .n) by ordinary least squares
argmingeeR (Rin(hn) = 1 (((())), n -y)
where g(x)), go (2:), and g: {g) are ii.dd transformations from Pg as specified in Section 4.1. Then with probability at least 1 - 5 over the SimCLR training, the expected risk of the truncated linear model hız(z)= Brpji-BBj[hhg satisfies
E Riin (a)nhaa) = El B..v.ll ol -n)(x))²11
+ c (BB (1+ (1²(1+ () d'/4p'/ log 1/4 Bw + log 1/4 (1/8) Eg)
+ tooo + B2) Sayplog plogm
n 1/4
m
invducibble risk
Error from SimCLR training
Error from downstream task
where the outer expectation is over (ax,, Ys 9.) bi C > 0 is some constant depending polynomially on (x)( and eg & E x 2, 0.
0 is some absolute constant,
(b). In contrast, suppose in addition 0² 1, 1..12 Bg and 3 cd, B 3 c( + B8) m/p for some absolute constant e > 0, then the truncated ordinary least squares estimator hate(x)) = proj[ n. (,, Oota)) obtained {( y:)) satisfies
E[R [] x2 := = EE = m
where = denotes matching upper and lower bounds up to absolute constant factors, and the outer expectation over {ax, y:)]
We remark that the truncation the data generation (i.e., = proj (xx, 0.)) + E) due to technical difficulties, however, we can choose the threshold B sufficiently large, for example, B O(log m), that the truncation rarely happens in the generated data. The restriction of the empirical risk minimization to J ensures that the condition E[[(2 W W'))=(W=>] Theorem 6 holds for any f(z) Wz Fo, Without this restriction, when Suff ) is sufficiently small, the ERM f(x) = W x only satisfics [[ W W > W*] x] R and the downstream error bound would contain an additional term depending on the (uf
0 in
For the two-step estimator in (a), the first term in the SimCLR training error converges zero the pretraining sample size n increases, and the second term eg is negligible when either the ground truth Efyla az] does not vary significantly (i.e., ||O.||2 is small) negligible eιror (i.e.. || z|22 is small). Thus, compared with the OLS estimator which has risk of order O (d/m). the two-step estimator achieves small risk of order O(p/m) when the error from SimCLR training is of higher order.
the data augmentation introduces
Proof of Theorem 9. First, we have from Corollary 1 that, with probability at least - 6, the learned encoder satisfies
Suff(J) & (1+
C K)
Vdplog Bw + v log(1/))
n
36

---

for some constant C > 0 depending polynomially on exp(R). Note that the bound can be directly applied even though we consider the ERM on _ E since f. E Fo and the proof of Corollary follows from upper bound on the supremum of an empirical process, which remains valid when restricting a smaller function space J F.
Consider the problem of fitting a linear regression using data {(f(z)), y:))=r We have
[[y] < |||[[|>]]|/(()] B. (a. 0.) ( [=]][[(]]] < B.
Thus the conditions required by Theorem 1.1 in [2] are satisfied and we have
E Rinn (ha)] - x² < 8( inf Ran(h - σ²) o{B² + σ²) p log m
neR
Following the proof of Theorem 6, it remains to verify the condition B[(La w w W2] =|=00 where W is the linear map in f( i.e. f(z) 22). This follows immediately as follows the uniform distribution on S(U1) + S(U2).
Ordinary least squares estimator. Adopt the shorthand p for projj-B.B] When applying p to a vector, we apply it coordinate-wise. Let Σ = E[æx ] = Ia/p be the covariance matrix. For the ordinary least squares (OLS) estimator, let X (x)
xm)
Rm denote the sample matrix,
Y (y) ymm E R.m denote the response vector, and E (E1
Em) T E I denote
the noise vector. By the definition of OLS, we have 0 (X X Y and
E[Rin (hois) - - E[(p(<<r, (X X) x Y>) - (a, 0.)))
We claim two results used later. The proof of them can be found at the end of this section. [[Irace((xTxX1 m -
d
(m 1)d
E B[trace(( (X x) 1 [>) (m d)(m
1) - d 3)
(35)
m BB [[l - -x.))_ <
B² cB//P p
exp(
(36)
p
for some absolute constant >
Choose B 3 c(o² + B3 log m/p for some sufficiently large absolute constant c > 0. We then have [[[[p(X0, - x0.] ]] $ m 11 On one hand, to establish the upper bound, we have
(hoiss)))) 0² & (x (xTx) ' Y (x. 0.)) =: Ti + T2,
where
T = (x, (X x) ( p(X0.)) (x, 0.) 0²
(I, (X X) xxx (p(X0)) -
x
X(X -Xxx x) 1x 1|pp ||lp( - X0.11
(8) 1
x²
Eltrace(( (X xx) -1))] B1llp((0.)) - x0.1
m²
m
and
T- = E[( x
(X x) x) -1 {
= प" o'E[trace X x -ンj (iit) d
m
Here, step (i) uses Sauchy-Schwarr inequality, step (ii) and (iii) follow from claim (35) and (36) and the choice of B. Combining the bounds on Tı, T2 yields the upper bound B[Rin (hoss) 52 s
2
37

---

To establish the lower bound, since B[a²] > + - b)3] follows that
+
B - b) v /B[b2], it
E Riin (RRiinhoss hois)] =²² = E[((p(<E, (X (X"x)
p( 0.)1)
(1) 0, + (X (X+ x) x)-1 p((z, 0.)))
> Ta - (T4 + Th);
where
T3 E[((a, O. + xT (x,,) 0.)1) [[Irace((XTX)) xx)1x))))) = 5²
m. d
T4 2/T3V Ts
T3 = E[[(p( x, 0, + x) (x. 0. (X x) x 8)) - (p((xr 0.)) (x. 0.)]
< [ 0. + (x x) x 8)) - (z. 0. + (x x) x 8)1²} 0² m
where the inequality uses claim (36). To find further upper bound of T4. Ts. we first note that (0. + (X x is independent of æ, and
E12 & co d + v,
10. + X X)
X
812 < 2B@ 21[ X
X
where is some zero-mean B, following the proof of claim (36) and integrating over the uub-Exponential variable v, it can be verified that (when choosing the absolute constant in B sufficiently large) T3 & 20 /o/mm.. Putting the bounds T3, Ts (and hence Ta) together, conclude that E (har)] - x² co d for some absolute constant 0.
variable by Theorem 1 in [16]. Under our choice of
Proof of claim (35) and (36). Claim (35) follows directly from properties of the inverse Wishart distribution [43]. For Claim (36), since each coordinate of Xe, are i.i.d. NN(0, (0.1)) w.l.o.g.. suffice to show
BlIp(2) - 21*1 < cexp(-B²/0 B²/c).
for z ~ NN,, 1). Note that this follows immediately since
Ef]p(2) - 21d1 < c 6 s cxp((s2/2)ds & cs exp(-s2/2) < cexp(-32/c).
D.5 Proof of Theorem
We prove Eq. (14) and (15) in Appendix D.5.1 and D.5.2, respectively.
D.5.1 Proof of Eq. (14)
suffices to apply Theorem to the setup in Theorem With a slight abuse notation, we use both one-hot vectors in - (e:} and integers in [S] to represent the augmented views and do not distinguish them the proof. We also occasionally omit the subscripts in Iy, IP. when the meaning is clear from the context.
We claim that
(()()),(1)) (P)) (()()))(((2)) 2
1
M Po(y)=())) (c())((2)) Py(v)
S
1 (2(0))
(37)
We will prove this claim momentarily. With this claim at hand, we have
38

---

Approximation error.
Let
Pa 1 2 = z)
Poly- = M x = x)
vS2T)²
fx(2)= = V2
Py = M)
can be verified that the parameter (W,, w.) corresponding to f. lies in r. Therefore, the approximation error inf fer Ry²(S;) (S.) 0 since S. is realized by S. and the link function
((r) R.
Generalization error. Let W = ( RAxs w E R, W 2, v / & Bw} and define the metric w1) - (W2, w2)ll := W - W2 v [w) - w2)/ on W.
First, for fz) (WWz)), T, wi -2 T
1, 2), simple calculation shows Il - f2l12.00 &
2((wI wil | W2 Ip), and therefore
log Nog,Nu,l1 F) & log N (5 u 1.1-1:: & log N u (2.1 12, Wi) + log.N
UVS .1 (1
2
< SM log (1+ ABW) + log (1 4Bw w
"
where Wi == { e MMs, | & B. W2 fw E. |u|| < VSBWw } and the last
inequality follows from the upper bound of the covering number of the unit ball (see e.g., Example 5.8 in [44]) and the assumption that M < S. In addition, it is readily verified that (z(()), (²) [-Bs, Bs] with Bs= = w S for all x(1), 222) Consequently,
B
Nog, ll 12,x, Fydu
Bw
|SM- log (1+ 4Bw
Bw
Vlog (1+
4Bw u )du
< c
du
Jo
du
u
< cv SMBw = SM3.
Combining the result on the approximation error and the generalization error and applying Theorem yields the desired result.
Proof of claim (37). For z + x2)), by Bayes' formula, we have
((z(1)2(() P(2
Σ ((2 x+) (()=
Σ (()r)((2)) (1)))2(1)
(2(2(2))
P(x:)
P(x (z(1), z (22) [2))) (2)) Pl = (z(1), 2(00) P(. = (2(1), x())))
2
(38)
where step (i) follows from symmetry between (2)) Moreover,
P( = (z ,,))))))))) (2)))
1
P(x = 2211/0 = =x())== 2
Σ y-1
M
Pe ==(x"==2()11 =x(0)p)) Polylæ = 2))
2
1 M
Po = 2(2)) Po = x())
.Po = 2())
2
Py(y)
M
(2(2)2(2)) P. (yl 12)(
Σ
(39a)
2
Py(v))
Po(2z) (10
PPz), and
(39b)
(1) 22))) (si1)
2P(( (1) 2 2(2)) x = (z(1)2(1)))
(1)
1 P(x =22(),
200,200 (2))), (39c)
2
39

---

where step (ii) follows from the generation process of the augmented views (2(1,, x (2)), and step (iii)
follows from symmetry between z 2(1,, 222). Substituting Eq. (39a) into Eq. (38), we find
,(2()2200) P(z(1)P(2(2)
M Σ y
Pa(0|((2)) Polula(1)) 2 (=(221))
Py(y)
P(æ = (z(1)=(21))
1
P. Polul (3)) Polyl
P( )P(z()) P(z(1), 2(2)
4
(40)
Py(v)
where the second equality uses Eq. (39b) and (39c). Reorganizing Eq. (40), we obtain
P(z()) (2)) P(z(0)((2(2) = Σ Pa(vl=(2) (2)) P
M
Pa(z(1), 2(2))
(41)
Py(y)
2 2P(((())P((222)
where we recall P.( is the marginal distribution of x1d (or x) and the second equality follows from Bayes' formula and the fact that x 11 x=* ly.
For z =2(²) using Eq. (39b) and properties of conditional distribution, we have
Po x, (2) = 2¹) Po(2(1) ==)== 2) 2¹)
P(z = 2 (2) = 2²)
Σ
Pa(z(2)= 2)
P(z = 2)
P(((1) 22) (2) 2²)
e'E[S]
eESS
Combining this with Eq. (41) for all 2()) * 21)) and noting that the marginal Po(.) is the uniform
distribution on [S], we obtain
P(2(1) 2, (2) 2)
Pr(x:1 2, x2 2)
Po(a =2, z²)
Σ
P(z(1) =)P(212)) 2)
=
2 (ar 2 =2
+
Po(x 22) = 21)
2'e[s]
Po(x 2, x =)
s
P. (w 2)Po = 2)
2
M
Polulz) P2(12) s
Σ
Py(y)
D.5.2 Proof of Eq. (15)
Write =(x). By a standard risk decomposition, we have
(hx) E[Reta(ha)) E(Reia (IP (PP (+)]=)]]]
= E[RRis(ha)] inf ([Rcis(h))
inf
Es.g (PL (hrr)
r: T.p (T Br
upproximation
+ E E[Rota(h;)] I
inf generalization
E(Rot.
We will prove that for some absolute constant 0,
1.
Sexp(B) oz.
approximation error < a c +
(Rr(S, - (S.)))
(42a)
and
2. with probability least 1 8,
cB
generalization error x
log(1/5) + M(v log Br + vB)
(42b)
v
40

---

Approximation error. Let E. E R Mx5 be the representation where
1 FV 1|2 =
Foly= = M| =
B..j V2 PP
VPy(y= M)
for j E [S] and let [2) denote the z-th column of E.. Let E = (f(1) f(()) E RMxS.
Given representation f(z), consider the classifier
hr(f(z)) softmax(log trun ff) Tb)), where
T = V2P, 1/2 (E,E,T) E. Pis Pis) ET, T.
1 V2
Ps
1 E. -
(43)
and Py diag 1), ..., Pyly M)). It can be verified that [T & &2/MM/O..
Br and [ & ///OE. Br. Moreover, we have by Lemma that
(D (D.. لار (y|lz)) hr (f()))) 21E [Drr (IP (+12)
(1 + E (D2(P (1)))
$ 2 ds + E D2 (1)(
Therefore, it remains to prove
cSexp(B) (B) (Rm(5 Rs)).)).
(P2
&
(44)
oe
Since
P (ulz( - hr (F()))))
Fe [2 u/ (1=(())](rr(((()))
Be.g By (1#))
hr hr(
(I (u)=) - hr hr(((=))
Ba.g
Σ
hr(f(2))
Mc[M]
< exp(B) 1xx.
(P (Py)=(11z) - -(r(f()))))
ME[Mr]
= eB Ex..
Σ (Po(y) =x = (45)
ye[Ms]
where the third line uses the definition of trun and claim (46) in the proof of Lemma 6. and the last line uses the fact that Pz = 3/2² = j) = P. Fyl=( = y = j) for all y e [M] E [S]. Eq. (44)
follows immediately from Lemma 6 which gives upper bound the term in Eq. (45).
Generalization error. The proof follows from standard analysis of empirical process similar to the proof of Eq. (29) in the proof of Theorem 4. Thus, we only provide sketch of the proof here.
Let [ == (T Ih v Talla & Br} and define the norm |[ - = I - First, by a triangle inequality, the fact that || log hr/ & 2B (which follows from the definition of trun), and Corollary 2.21 in Wainwright [44] for functions with bounded differences, we have
T, - f
sup Rea((h)) - (( + 2B V log(1/0) rer
generalization error < 2E
Vm
with probability at least - 5. Let Xr = (hrr - ElR (hr)). Then we have
2B
sup (hr - (hr)) < Er.1r + E[ sup Per
|X Xpll <
+ sup sup [Xr Xx r.fer
r.rer
Moreover, the process (Xrlrer is a zero-mean sub- Gaussaasiinn process with respect the metric since Xr is the average ii.d. random variables bounded
Px Px(TT, (T, = 2| log hr - log hy by
2 sup Ken. loghr (f - (cy. log (fgh(((())))) dc(m]
41

---

< 2| log br br(f(z)) - log bf & Px I)) vm, and moreover
Px (T(T,T)
cl log trru (T f()) lb) - trugtrn(1 T Tw f(z) + To)lz//m.
Ce |T /l/m f//
where step (i) uses log sofssoaaax(4 (u) log softmax(v)]la 2 ala and step (ii) follows from Taylor expansion of s(x) = log æ, the assumption that [][=)]]2 & Bw = M. Therefore, we have by Dudley's ' integral bound (see e.g.. Theorem 5.22 in Wainwright [44]) that
pcB/vm
B vm 1-11, r
B sup - &
v (Xr, &
V VlggN N
r,rer
J0
30
BB/ym
log.NV vm.
-II-11.)) du B
cB/ym
vm.
VlggN( ym. 111112,,111 du
VlogN(
11 Io (.)
J0
BcB/ym
M2 log (1
Br du &
1/2 (BrB) BM log"
Blo 1/2 Br + vB)
J0
mi
m
m
where In := (T E RRM. :
[Toll2 & Br), and the last line uses the covering number bound of unit balls. Putting pieces together yields the desired bound.
[T & Br} and F, := (T, e RRMM
D.6 An auxiliary lemma
Lemma 6 (Upper bound on the term in Eq. (45)). Let the assumptions in Theorem 3 and the notations in its proof in Appendix D.5.2 hold. Assume Ri(S fmmm R₁(S.) < co / M) for some absolute constant e 0, then
ds (S Pmg (-)((S.))
Ex.g
(-r(((=2)))) (Po(yl - DE[M]
Σ
oF.
for some absolute constant d' 0.
Proof of Lemma 6. The proof consists of two steps. First, plug the definition of hr into Eq. (6) and simplify the expression. Then, we demonstrate that the simplified expression can be further bounded using the excess risk R= Re(S.) of the learned encoder faug.
Step I: simplify the notation. Since
1
V usoftmax((ogg u.... =
IM
1 A
ll
|
for any R.M we have
Em.9
Σ M
(Paly = = -x)=((((())))) < <.E.gg
Σ (P = =x) - -trun[T,, f())
((z)+ + Ib)
yE[M]
cE
(Po(y/æ =2) (Tw + 1o)y)
Mc[M]
where in the first inequality use the claim that
|| - [trun[T + P6)lual < 1/2.
(46)
The proof of this claim deferred to the end of the proof of the lemma. The second inequality follows from Taylor expansion of s(x) log z, the boundedness assumption that ( z)
42

---

(xpp(BB), 1]. and noting the truncation trun(-) reduces the & error. Moreover, for any = E [S], by the definition of (T.m. [b) Eq. (43)
Tw.f(2) + Tb
-22Py 1/2 P.,E, (..E,T)-E..CC
Pis) f(z) + 1s/2]
.22y 1/2 (E,E, 1 E.E. (z)
+ +V2P 1/2 E. E. ) E. [[I -Pg ET f(z) + 1s/2- E. T E.(z)]
v2Py 1/2 E, (z) 2P 1/2 (..E. T) E. PPs) E f(z) 1s/2 E, S.TEA E:)].
Since v2P, 1/2 (z) = (Polyll = yM) and 2 _ xt follows the uniform distribution on [S] by assumption, it follows that
Ex..
Σ
(PP(y)l = - 1b),)
ME[M]
2F
(1( E. E, 1)- (E)))-EE1 E.[(Ts P E f(z) + 1s/2 E, T.T...C.. (=)]]1
2
Ex[l[[[s -P1s) f(z) 1s/2 - E. Ex)]111
2
I[Is - Pig) E E + 1s/s/2 E. E.
S
2
I(Is Pis) E E (Is Pis) E.
E.
(47)
So
where the last equality follows since E. (z E. (z(2)) 2e( (2)),, ()) E [S] and [ ( = 1 for all (1) E [S].
(a(=()) (()
for any
Step 2: bound the expression by excess risk. We claim that for some absolute constant c 0,
[[[ss Pig) ET E (Is - Pis) E. E.
< <c[[1s P1s) E + @ls) - (1s - P1s) E. T E. + 155 and
(48a)
[[(Is Pis) )1s)(B E É @Is) (1s) E. S 1s/2) lio
S² (Re(S) 7 R(())))
(48b)
Combining claim (48a) and (48b) and bound (47) yields the desired bound. Now, remains prove these two claims.
Proof of claim (48a). Adopt the shorthand notation A = (É' E Wis) - (E. T E. + S. 1s/2). First, by the triangle inequality, it suffices to show
I(Is ( 1/ & cl((ss P1s)
for some absolute constant > Note that rank ĐT E E, E.. & 2M, therefore, there are at least S/2 singular values of A which equal -0 - 51/2. As result, we have
[(ss Pi.) Allo = traco traco(A(Ts - Pi.) = I S 11AA'
} ( S/2) l >
1
1 1 (P S/2)),
|
|
>
Proof of claim (48b). Adpot the shorthands 5m = (5()((((1), 201)) [(0)s
(z(1),
E R Sxs and
S, = (5, z(2)))
E
BxS where (z 2(21) ()) (()
Since we
201 [())
43

---

assume _ xt1 follows the uniform distribution on [S]. by the definition of faug and claim (37) in the proof of Eq. (14)
[[Ts - P1s) (I - (E, [[ss -Pss) -. m
J.E.TEE E, + S 1s/2)
TT,
where
Ti 1220 Finally, by second-order Taylor expansion of R₃(S) at S., we have
xP, 2000 xp, L((S (z) 1g ~P_ [(S ,z)
Ri - = Ti.
Combining the two equalities yields the claim.
Proof of claim (46). Note that for any [S],
1 ttrun ( (z) To)lil &
(vla =) -t>-tru(Tww.(3 + Tb)yl
vE[M]]
Σ
P = = ((). [o)yl
WE[M
MS
Exz.
Σ VE[M]
(Polylæ 2) (T Tbl,)²
where the last line follows from the assumption that at (and hence z) follows the uniform distribution on [S]. Thus, combining Eq. (47), claim (48a) and (48b) yields
SVM
| trunnn .T. (2) + r & c
R frme
(s. < 2
OE.
E Additional experiments
We also conducted small-scale experiments in the CLIP setting (language-image pretraining, [31]) to compare the contrastive learning losses. Namely, we use the CLIP model (RN50-quickgelu, which consists of ResNet-50 image encoder and 12-layer Transformer text encoder) 100K subsample of the cc3m-wds dataset [33] using both KL (i.e., InfoNCE) and cc-onttrattive losses (Eq. 3 and 10). The original dataset contains about 3.3M image-text pairs, but due to limited compute, we trained on the subsample for 32 epochs.
We evaluated the models based on their zero-shot classification performance on the ImageNet- 1k validation set (1000 classes, 500 images per class). For KL and x -contraastive losses, we set the link functions r(x) x/t and =/t respectively, with trainable temperature initialized 1. We used batch size of 128 and the AdamW optimizer with weight decay 0.02, and selected the best learning rate via grid search from (3e-5, 1e-4, 3,-4, le-3). The optimal learning rate for both losses is 3 x 10
Table 1: Top-5 zero-shot classification accuracy ImageNet- lk.
Method
Accuracy (%)
InfoNCE
7.5 + 0.3
Chi-squared
9.4 14 0.1
44

---

We repeated the experiments three times and report the top-5 accuracy on the ImageNet- 1k validation set. From Table 1, we observe that in this small-scale experiment, the model trained with x² contrastive loss achieves zero-shot performance comparable to that of InfoNCE. We do not claim that the x²-cottrast loss is superior, as both methods could benefit from further hyperparameter tuning (e.g., initial temperature) or larger datasets. However, we note that x -coottaatee loss is able to learn representations that are useful for downstream tasks, which is consistent with our theoretical findings. We leave more extensive experiments in the CLIP setting to future work.
45


Reviews:
[{"review_id": "CHA0zOhiOt", "reviewer": "Reviewer_8N6b", "summary": "This paper provides a statistical theory of contrastive learning via the approximate sufficient statistics, following~\\cite{oko2025statistical} for contrastive language-image pretraining (CLIP) using KL-divergence. Specifically, the authors generalize the concept of the approximate sufficient statistics to equivalent forms and general $f$-divergence, and illustrate that minimizing SimCLR and other contrastive losses yields encoders that are approximately sufficient. The key factors influencing these near-sufficient encoders are their sufficiency and the error induced by data augmentation in contrastive learning. Examples, including linear regression and topic classification, are given to illustrate the applicability of results.", "questions": "1. Do the provided bounds in Eq.(4) in Theorem 1, Eq.(7a) and Eq.(7b) in Theorem 2, and Eq.(8) in Theorem 3 tight? Please give more discussions.\n2. Please give experimental results to support the validity of the theoretical results in Theorem 6.", "limitations": "Please see the weaknesses section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "# Strengths \n1. Overall, this paper is well-written. The related work and comparison with this work are discussed, especially the work~\\cite{oko2025statistical}.\n2. The claims about the contributions are supported. Specifically, (1) it generalizes the concept of the approximate sufficient statistics in~\\cite{oko2025statistical} for contrastive language-image pretraining (CLIP) using KL-divergence; (2) it provides the theoretical analysis of data augmentation-based contrastive learning following the SimCLR framework, demonstrating the downstream performance of the learned encoder depends on its sufficiency and the error induced by the random transformation.\n3. The proofs seem right, although I have not checked the proof details line by line.\n\n# Weaknesses\n1. Technically, the novelty seems a little limited due to its similarity to the work~\\cite{oko2025statistical}. More details about the additional challenges are suggested to be provided.\n2. The tightness of the bounds in Eq.(4) in Theorem 1, Eq.(7a) and Eq.(7b) in Theorem 2, and Eq.(8) in Theorem 3,  are not discussed. \nBesides, for the classification problem of Theorem 3, why use KL divergence instead of common metrics (e.g., 0-1 loss) to evaluate the classification performance?\n2. There are no experimental results to support the theoretical results. Are the provided bounds non-vacuous or meaningful? Synthetic experiments on examples of linear regression or classification can be conducted to illustrate the validity of theoretical results.", "was_revised": true, "final_justification": "The authors have addressed most of my concerns, including the tightness of the bounds, additional challenges compared with~\\cite{oko2025statistical}, and experimental results to support the validity of the theoretical results in Theorem 6. The remaining concern is the reason why using KL divergence instead of common metrics (e.g., 0-1 loss) to evaluate the classification performance. \nThus, I keep the score.", "rebuttal": "We appreciate the helpful comments and constructive feedback from Reviewer 8N6b. Below, we respond to the questions and comments in a point-by-point manner.\n\n---\n> Q1. Do the provided bounds in Eq.(4) in Theorem 1, Eq.(7a) and Eq.(7b) in Theorem 2, and Eq.(8) in Theorem 3 tight? Please give more discussions.\n\n\nA1. For Eq. (4), we expect that the polynomial dependence of the constant $C$ on $B_{\\mathsf{S}}$ is necessary to obtain a non-vacuous bound for arbitrary batch size $K > 2$. However, we suspect that the constant $C$ in Eq. (5a) may be improved to depend polynomially on $\\log(B_{\\mathsf{S}})$. We hope to derive a more precise characterization of the (log-)polynomial dependence in Eq (4) and (5a) in future work.\n\nFor Eq. (7a), as discussed after Theorem 2 (line 195-197), the error $\\epsilon_{\\mathcal{G}}$ on the right-hand side can be replaced by the minimum error $\\widetilde\\epsilon_{\\mathcal{G}}$, and is therefore tight (up to constant factors) when the sufficiency is sufficiently small.\n\nFor Eq. (7b) and (8b), the current results are not tight due to the gap between between $\\epsilon_{\\mathcal{G}}$ and the minimum error $\\widetilde\\epsilon_{\\mathcal{G}}$. We leave the derivation of matching lower bounds to future work.\n\n---\n\n> W1: Technically, the novelty seems a little limited due to its similarity to the work~\\cite{oko2025statistical}. More details about the additional challenges are suggested to be provided.\n\nA2. A main technical challenge of extending Oko et al. (2025) [1] to the SimCLR setting (or single-modal contrastive learning) is handling the error induced by random augmentation. Note that random augmentation is not performed in CLIP considered in [1], and therefore the downstream error can be controlled directly via the sufficiency of the encoder (see, e.g., Propositions 2, 3, and 4 in [1]). In our work, we introduce a novel augmentation error term $\\epsilon_{\\mathcal{G}}$ (or $\\epsilon^{\\mathsf{cls}}_{\\mathcal{G}}$), and use it to establish downstream error bounds for any encoder $f$, by applying triangle inequalities for $\\ell_2$ error in regression (Theorem 2) and for KL divergence in classification (Theorem 3). \n\n\n---\n\n\n> W2. Besides, for the classification problem of Theorem 3, why use KL divergence instead of common metrics (e.g., 0-1 loss) to evaluate the classification performance?\n\nA3. We use KL divergence instead of 0-1 loss in the multi-class classification setting (Theorem 3) because it is a standard and more informative metric for quantifying the difference between the predicted and true label distributions.\n\n---\n\n\n> Q2 and W3. Please give experimental results to support the validity of the theoretical results in Theorem 6.\n\nA4. We conduct synthetic experiments to learn data representations via contrastive learning with a two-layer neural network, and evaluate them on downstream linear regression.\n\n\nIn the contrastive learning phase, we generate $n$ i.i.d. samples $x_i \\sim \\mathcal{N}(0, I_d)$. The augmentation $g$ adds i.i.d. $\\mathcal{N}(0, \\sigma_1^2)$ noise to the first $s < d$ coordinates of $x_i$, and replaces the remaining coordinates with i.i.d. $\\mathcal{N}(0, 1)$ noise. We apply KL and $\\chi^2$-contrastive learning (Eq 3 and 10) with link function $\\tau(x) = x$, and encoder $f(x)$ being a two-layer ReLU neural network mapping $\\mathbb{R}^d$ to $\\mathbb{R}^s$. We set $s = 10,d = 100,n=500$, hidden dimension 64, and batch size $K = 64$. The encoder is trained using Adam (learning rate 0.001) for 300 epochs, after which the training loss is observed to converge.\n\n\nFor downstream regression, we generate $m$ i.i.d. samples $(x_i, y_i)\\_{i=1}^m$, where $x_i \\sim \\mathcal{N}(0, I_d)$ and $y_i = \\langle x_i, \\theta_\\star \\rangle + \\epsilon_i$, with $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$ independent of $x_i$. We choose $\\theta_\\star = (\\mathbf{1}^\\top_s/\\sqrt{s},\\mathbf{0}^\\top_{d-s})^\\top$ and $\\sigma=1$. Using the learned representation $\\widehat{f}(x_i) \\in \\mathbb{R}^s$ from KL (or $\\chi^2$)-contrastive learning, we fit a downstream linear model to predict $y_i$. We define the excess risk of any predictor $h$ as $\\mathbb{E}[(y_i - h(x_i))^2] - \\sigma^2$, and evaluate the excess risk of the linear model trained on $(\\widehat{f}(x_i),y_i)\\_{i=1}^m$ using 50000 test samples. For comparison, we also report the excess risk of a linear model trained directly on the original samples $(x_i,y_i)\\_{i=1}^m$. Results for various downstream sample sizes $m$ and the standard deviation over 10 runs are shown below.\n\n> **Table: Excess risk  for various downstream sample sizes m**\n>\n> | m    | InfoNCE         | Chi-squared     | Direct LR       |\n> |------|-----------------|-----------------|-----------------|\n> | 150 | 0.106 ± 0.040 | 0.120 ± 0.028 | 2.066 ± 0.594 |\n> | 500 | 0.060 ± 0.015 | 0.070 ± 0.013 | 0.243 ± 0.032 |\n> | 1000 | 0.052 ± 0.012 | 0.063 ± 0.012 | 0.114 ± 0.021 |\n> | 2000 | 0.046 ± 0.011 | 0.058 ± 0.013 | 0.055 ± 0.012 |\n> | 5000 | 0.042 ± 0.011 | 0.055 ± 0.013 | 0.021 ± 0.005 |\n> | 10000 | 0.040 ± 0.012 | 0.054 ± 0.012 | 0.011 ± 0.004 |\n\n\nFrom the table, we observe that InfoNCE and Chi-squared achieve comparable excess risks (within one standard deviation except for $m=10000$), and both are substantially lower than that of direct linear regression when the sample size $m$ is relatively small (e.g., $m = 150, 500$). This suggests that both KL and $\\chi^2$-contrastive learning can learn a “good” low-dimensional representation for the downstream task. As the sample size increases, the excess risk of direct linear regression converges to zero, while those of InfoNCE and Chi-squared converge to non-zero constants. This is consistent with our theoretical results, which attribute the excess risk to the non-zero sufficiency of $\\widehat{f}$ and the augmentation error $\\epsilon_{\\mathcal{G}}$.\n\nDue to limited computational resources, we did not evaluate the performance of $\\chi^2$-contrastive learning on large-scale real-world datasets and leave this for future investigation. \n\n---\n\n[1]. Oko, K., Lin, L., Cai, Y., & Mei, S. (2025). A statistical theory of contrastive pre-training and multimodal generative ai. arXiv preprint arXiv:2501.04641."}, {"review_id": "ax2nsoznHn", "reviewer": "Reviewer_sYsE", "summary": "This paper proposes a theoretical framework for analyzing data augmentation-based contrastive learning, particularly SimCLR, by means of approximate sufficient statistics, which extends a prior work using KL-divergence to general f-divergences. Specifically, this work shows that minimizing a contrastive loss produces encoders approximately sufficient, and they can be adapted to downstream regression and classification tasks, where downstream performance depends on their sufficiency and the error induced by data augmentation in contrastive learning.", "questions": "Please address concerns in Weaknesses above.", "limitations": "Different from the checklist, limitations are not provided.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n+ The idea of analyzing contrastive learning via approximate sufficient statistics sounds interesting.\n\n+ The claim is supported by comprehensive theoretical derivation.\n\n+ Concrete examples on regression and classification are provided, though they are limited to linear models.\n\n\n**Weaknesses**\n\n- There is no experimental results, raising a concern on the practicality of the proposed idea. At least the prior work by Oko et al. [27] conducted some experiments with CLIP. If the theoretical results deviate from practical nonlinear models, then their contribution is limited accordingly. To address this concern, the authors could first conduct toy experiments with linear models as in the examples in Section 4, and then extend it to nonlinear models and see if their theoretical results empirically hold, or how much they are deviated from practical models.\n\n- L252: It is not clear how \"end-to-end theoretical guarantees for the downstream performance of encoders obtained by minimizing general f-contrastive losses\" is drawn by combining the results from Sections 3.3.1 and 3.3.2. \n\n- There are many \"some constants\" throughout the paper. How are they determined, at least in examples? How much are bounds tight?\n\n- The error on the downstream task induced by data augmentation epsilon_G is an important variable in their analysis but it is not specified well. For example, it would be useful to know how we can measure epsilon_G in practice, how much its value deviates by taking different augmentation strategies, and so on.\n\n- Formatting issue: generally speaking, any citation should not be appeared in Abstract.\n\n- Typo: f-sufficieny in the title of Section 3.3.1", "was_revised": true, "final_justification": "The authors successfully addressed my concerns. They also reported an additional experiment in a toy setting in their rebuttal, and further added another one in the CLIP setting around the end of the rebuttal period, though the experimental result in the CLIP setting seems somewhat weak.", "rebuttal": "We thank Reviewer sYsE for their careful review and valuable feedback. We hope to address all questions below.\n\n---\n> Q1. There is no experimental results, raising a concern on the practicality of the proposed idea. At least the prior work by Oko et al. [27] conducted some experiments with CLIP. If the theoretical results deviate from practical nonlinear models, then their contribution is limited accordingly. To address this concern, the authors could first conduct toy experiments with linear models as in the examples in Section 4, and then extend it to nonlinear models and see if their theoretical results empirically hold, or how much they are deviated from practical models.\n\n A1. We conduct synthetic experiments to learn data representations via contrastive learning with a two-layer neural network, and evaluate them on downstream linear regression.\n\n\nIn the contrastive learning phase, we generate $n$ i.i.d. samples $x_i \\sim \\mathcal{N}(0, I_d)$. The augmentation $g$ adds i.i.d. $\\mathcal{N}(0, \\sigma_1^2)$ noise to the first $s < d$ coordinates of $x_i$, and replaces the remaining coordinates with i.i.d. $\\mathcal{N}(0, 1)$ noise. We apply KL and $\\chi^2$-contrastive learning (Eq 3 and 10) with link function $\\tau(x) = x$, and encoder $f(x)$ being a two-layer ReLU neural network mapping $\\mathbb{R}^d$ to $\\mathbb{R}^s$. We set $s = 10,d = 100,n=500$, hidden dimension 64, and batch size $K = 64$. The encoder is trained using Adam (learning rate 0.001) for 300 epochs, after which the training loss is observed to converge.\n\n\nFor downstream regression, we generate $m$ i.i.d. samples $(x_i, y_i)\\_{i=1}^m$, where $x_i \\sim \\mathcal{N}(0, I_d)$ and $y_i = \\langle x_i, \\theta_\\star \\rangle + \\epsilon_i$, with $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$ independent of $x_i$. We choose $\\theta_\\star = (\\mathbf{1}^\\top_s/\\sqrt{s},\\mathbf{0}^\\top_{d-s})^\\top$ and $\\sigma=1$. Using the learned representation $\\widehat{f}(x_i) \\in \\mathbb{R}^s$ from KL (or $\\chi^2$)-contrastive learning, we fit a downstream linear model to predict $y_i$. We define the excess risk of any predictor $h$ as $\\mathbb{E}[(y_i - h(x_i))^2] - \\sigma^2$, and evaluate the excess risk of the linear model trained on $(\\widehat{f}(x_i),y_i)\\_{i=1}^m$ using 50000 test samples. For comparison, we also report the excess risk of a linear model trained directly on the original samples $(x_i,y_i)\\_{i=1}^m$. Results for various downstream sample sizes $m$ and the standard deviation over 10 runs are shown below.\n\n> **Table: Excess risk  for various downstream sample sizes m**\n>\n> | m    | InfoNCE         | Chi-squared     | Direct LR       |\n> |------|-----------------|-----------------|-----------------|\n> | 150 | 0.106 ± 0.040 | 0.120 ± 0.028 | 2.066 ± 0.594 |\n> | 500 | 0.060 ± 0.015 | 0.070 ± 0.013 | 0.243 ± 0.032 |\n> | 1000 | 0.052 ± 0.012 | 0.063 ± 0.012 | 0.114 ± 0.021 |\n> | 2000 | 0.046 ± 0.011 | 0.058 ± 0.013 | 0.055 ± 0.012 |\n> | 5000 | 0.042 ± 0.011 | 0.055 ± 0.013 | 0.021 ± 0.005 |\n> | 10000 | 0.040 ± 0.012 | 0.054 ± 0.012 | 0.011 ± 0.004 |\n\n\nFrom the table, we observe that InfoNCE and Chi-squared achieve comparable excess risks (differences about one standard deviation), and both are substantially lower than that of direct linear regression when the sample size $m$ is relatively small (e.g., $m = 150, 500$). This suggests that both KL and $\\chi^2$-contrastive learning can learn a “good” low-dimensional representation for the downstream task. As the sample size increases, the excess risk of direct linear regression converges to zero, while those of InfoNCE and Chi-squared converge to non-zero constants. This is consistent with our theoretical results, which attribute the excess risk to the non-zero sufficiency of $\\widehat{f}$ and the augmentation error $\\epsilon_{\\mathcal{G}}$.\n\nDue to limited computational resources, we did not evaluate the performance of $\\chi^2$-contrastive learning on large-scale real-world datasets and leave this for future investigation. \n\n---\n\n> Q2. L252: It is not clear how \"end-to-end theoretical guarantees for the downstream performance of encoders obtained by minimizing general f-contrastive losses\" is drawn by combining the results from Sections 3.3.1 and 3.3.2. \n\nA2. In Section 3.3.1, we show that the sufficiency of encoders can be bounded by the excess risk of general f-contrastive losses  (line 218), with concrete calculations for $\\chi^2$-sufficiency in Theorem 4. In Section 3.3.2, Proposition 5 shows that the downstream guarantees in Theorem 2 and 3 remain valid when  Eq. (13) is satisfied. Together, these results imply (at least for $\\chi^2$-contrastive learning) that an encoder $\\widehat{f}$ minimizing the empirical $\\mathsf{f}$-contrastive loss can achieve small downstream errors, provided the pretraining sample size $n$ is sufficiently large and the augmentation error $\\epsilon_{\\mathcal{G}}$ is small.\nNevertheless, we agree the statement may be somewhat overstated, as we focus our analysis on $\\chi^2$-contrastive learning, leaving other contrastive losses for future investigation (lines 224–227). We will revise the statement in the paper.\n\n---\n> Q3. There are many \"some constants\" throughout the paper. How are they determined, at least in examples? How much are bounds tight?\n\nA3. Throughout the paper, we use $c > 0$ to denote absolute constants independent of any parameters (e.g., $c = 1, 2, 10$). We use $C > 0$ to denote constants that depend polynomially on certain parameters (e.g., $B_{\\mathsf{S}}$ in Assumption 1), and we explicitly state the dependencies when introducing the constants. However, tracking the exact polynomial dependence (e.g., $C = \\mathcal{O}(B_{\\mathsf{S}}^2)$) can be cumbersome in analysis, so we use $C$ to simplify the presentation and improve clarity without losing too much in the bounds. Please let us know if this addresses your question.\n\n---\n\n> Q4. The error on the downstream task induced by data augmentation epsilon_G is an important variable in their analysis but it is not specified well. For example, it would be useful to know how we can measure epsilon_G in practice, how much its value deviates by taking different augmentation strategies, and so on.\n\nA4. We thank the reviewer for this practical question. In general, it is challenging to measure $\\epsilon\\_{\\mathcal{G}}$ (or $\\epsilon^{\\mathsf{cls}}\\_{\\mathcal{G}}$) for real-world augmentations, as their values depend on concrete assumptions about the augmentations and oracle knowledge of the data. For example, in image classification tasks, the augmentation error $\\epsilon^{\\mathsf{cls}}\\_{\\mathcal{G}}$ of random cropping depends on the proportion of pixels dropped and the true label probabilities of the cropped images—which are typically unknown. Nevertheless, in practice, one may use the predicted label probabilities of the original and cropped images from a highly accurate image classifier as a surrogate for the true label probabilities, and use them to empirically estimate the augmentation error $\\epsilon^{\\mathsf{cls}}_{\\mathcal{G}}$.\n\n\n\n---\n\n> Q5 and 6: formatting issue and typo.\n\nA5. Thanks for the suggestions. We will fix them in the paper."}, {"review_id": "jFVdw4akcd", "reviewer": "Reviewer_RiyN", "summary": "This paper develops a new theoretical framework for data augmentation-based contrastive learning, focusing on SimCLR. It generalizes the concept of approximate sufficient statistics from prior work on CLIP to general f-divergences and establishes that minimizing contrastive losses yields encoders that are approximately sufficient. The authors show that minimizing contrastive losses (like InfoNCE) yields encoders that are approximately sufficient, and that the sufficiency of these encoders, together with the error induced by data augmentation, governs their adaptability and performance on downstream tasks. The paper provides concrete examples in linear regression and topic classification to illustrate the applicability of the theory.", "questions": "- Is it straightforward to extend your theoretical results to multimodal contrastive learning settings (e.g. image-text), in line with identifiability analyse such as in Daunhawer et al. ICLR 2024 https://arxiv.org/pdf/2303.09166, IDENTIFIABILITY RESULTS FOR MULTIMODAL CONTRASTIVE LEARNING\n- How does your approximate sufficiency framework encompass or relate to alternative contrastive/self-supervised objectives such as VICReg, Barlow Twins, SwAV, and BYOL, DINO, where some of them do not explicitly use negative samples, and yet surpasses SimCLR in most natural imaging experiments ?\n- Could you clarify the practical validity of your assumptions (e.g. bounded score functions, invertibility and Lipschitz continuity of the link function), particularly in the context of deep neural network encoders?\n- Could you clarify the impact of the encoder architecture on your generalization bounds ? Does it impact the approximation error ?\n- Do you have experimental results comparing the empirical performance of encoders trained with different f-divergences (e.g. KL vs. chi-squared contrastive losses) on standard datasets?\n- Could you discuss how your present work connects/relates to identifiability ?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- The paper significantly extends the notion of approximate sufficiency from its prior, more limited form (KL-divergence for CLIP) to a general framework encompassing various f-divergences and equivalent mathematical formulations. This generalization is both non-trivial and valuable for the broader contrastive learning community.\n- The definitions of sufficiency (information loss, variational form, conditional Bregman) are carefully presented and shown to be equivalent, providing a solid mathematical foundation.\n- In Sec. 3.1, the paper establishes a sufficiency bound for the ERM estimator in and shows that when f minimizes the ERM, the bound is a function of a generalization error (which goes to 0 as the number of samples tend to infinity) and a constant approximation error.\n- Then, in Sec. 3.2, the paper establishes that the downstream performance of learned encoders on linear regression and topic classification depends on both their sufficiency and the augmentation-induced error, providing a theoretical explanation on previous work focusing on how the data augmentions affect the performances of SimCLR's encoder.\n- In Sec 3.3, the authors generalizes to other loss terms than SimCLR, by generalizing their result of other type of f using general f-sufficiency. In Eq. 9, they notably extend to the chi-squared sufficiency. This generalization is appreciated and is a strength of the paper.\n\nWeaknesses:\n- The paper is primarily theoretical; while it provides illustrative examples, it lacks empirical experiments that would demonstrate the practical impact of the theoretical bounds and insights in real-world settings. Notbaly, it would have been interesting to study the use on real dataset of various f, such as teh chi-squared contrastive loss for ex. Besides, we would have expected an experimental comparison between empirical risk and theoretical risk, using either real-world dataset (if applicable), or a synthetic one.\n- Overall, the paper is hard to read, and the use of the term \"encoder\" to both talk about the neural network and the f of the f-MI makes it confusing.\n- While the paper discuss how the sufficiency of the encoder impact the downstream performances, it eludes past work about identifiability (Self-Supervised Learning with Data Augmentations Provably Isolates Content from Style, von Kugelgen et al. NeurIPS 2021, https://openreview.net/pdf?id=4pf_pOo0Dt), even though the connection between identifiability and encoder-sufficiency appears intuitively close.\n- While the theoretical bounds are elegant, they rely on assumptions such as boundedness of the score function and invertibility/Lipschitz continuity of the link function. In practical neural networks, these conditions may not strictly hold. Discussing these assumptions would be beneficial for the paper. Moreover, the theory abstracts away from architectural details (e.g., depth, parameter count), which are known to affect the performance of learned representations. A discussion on how architecture choices influence sufficiency and generalization would strengthen the practical relevance of the results.", "was_revised": true, "final_justification": "Authors have globally responded to my points but I wish to keep my score as it is.", "rebuttal": "We sincerely appreciate Reviewer RiyN for their thorough review and constructive feedback on our work. Below, we hope to address all your comments.\n\n> Q1 and Q6. generalization to multimodal contrastive learning and connection with identifiability [1,2]\n\nA1. We thank the reviewer for this insightful question and pointing out the connection with the identifiability results.\n\n**Generalization to multimodal contrastive learning.**  Yes, it is straightforward to generalize our theoretical results to multimodal contrastive learning. The main modification is to choose $X,Y$ as a pair of samples $(x,y)$ from two modalities (e.g, an image and its associated text) instead of two augmented views in the definition of sufficiency (see line 99). As a consequence, similar downstream bounds as in [4] can be derived based on the generalized $\\mathsf{f}$-sufficiency.\n\n**Connection with identifiability.** The identifiability results in contrastive learning [1,2] consider a setting where paired views (either from augmentations or across modalities)  share some common latent factors, and show that a representation that minimizes the expected alignment loss can identify these latent factors. Under their assumptions, it can be shown that the learned representation is equivalent to an encoder with zero sufficiency in our work. In contrast, we derive general downstream error bounds for encoders with arbitrary sufficiency, even though the encoders cannot exactly identify the hidden factors when the sufficiency measure is strictly positive.\n\n\n---\n\n> Q2. How does your approximate sufficiency framework encompass or relate to alternative contrastive/self-supervised objectives such as VICReg, Barlow Twins, SwAV, and BYOL, DINO?\n\nA2.  In our work, the approximate sufficiency framework applies to any encoder $f$, including those obtained from alternative contrastive/self-supervised objectives mentioned by the reviewer, with the downstream error bounds depending on the sufficiency of $f$. However, while the excess risk provides a direct upper bound on the sufficiency for the InfoNCE loss (line 166), for the alternative contrastive/self-supervised objectives mentioned above, it is not yet clear how their respective excess losses relate to our sufficiency measure. We leave establishing the connections between these excess losses and the sufficiency measure for future exploration.\n\n---\n\n> Q3. Could you clarify the practical validity of your assumptions (e.g. bounded score functions, invertibility and Lipschitz continuity of the link function), particularly in the context of deep neural network encoders?\n\nA3. In practice, the link function $\\tau(x)$ is often chosen as a linear function, i.e., $\\tau(x) = x/t$, where $t > 0$ is the temperature parameter. Thus, the invertibility and Lipschitz continuity of the link function are naturally satisfied. In SimCLR [3], the encoder $f$ is normalized before computing the score; therefore, the score is bounded by $1/t$, where the temperature $t \\in \\\\{0.1, 0.5, 1\\\\}$ in their experiments.\n\n---\n\n> Q4. Could you clarify the impact of the encoder architecture on your generalization bounds ? Does it impact the approximation error ?\n\nA4. The encoder architecture affects the generalization bounds by influencing the covering number in the second term of the generalization error (see line 236). By a standard parameter-counting argument (e.g., Theorem 6 in [4]), the covering number can be upper bounded by $\\mathcal{O}(d)$ for transformer-based models. The approximation error, on the other hand, depends on the encoder class $\\mathcal{F}$. A richer and more complex encoder class (or architecture) has a smaller approximation error but potentially larger generalization error. \n\n---\n\n> Q5. Do you have experimental results comparing the empirical performance of encoders trained with different f-divergences (e.g. KL vs. chi-squared contrastive losses) on standard datasets?\n\nA5. We conduct synthetic experiments to learn data representations via contrastive learning with a two-layer neural network, and evaluate them on downstream linear regression.\n\n\nIn the contrastive learning phase, we generate $n$ i.i.d. samples $x_i \\sim \\mathcal{N}(0, I_d)$. The augmentation $g$ adds i.i.d. $\\mathcal{N}(0, \\sigma_1^2)$ noise to the first $s < d$ coordinates of $x_i$, and replaces the remaining coordinates with i.i.d. $\\mathcal{N}(0, 1)$ noise. We apply KL and $\\chi^2$-contrastive learning (Eq 3 and 10) with link function $\\tau(x) = x$, and encoder $f(x)$ being a two-layer ReLU neural network mapping $\\mathbb{R}^d$ to $\\mathbb{R}^s$. We set $s = 10,d = 100,n=500$, hidden dimension 64, and batch size $K = 64$. The encoder is trained using Adam (learning rate 0.001) for 300 epochs, after which the training loss is observed to converge.\n\n\nFor downstream regression, we generate $m$ i.i.d. samples $(x_i, y_i)\\_{i=1}^m$, where $x_i \\sim \\mathcal{N}(0, I_d)$ and $y_i = \\langle x_i, \\theta_\\star \\rangle + \\epsilon_i$, with $\\epsilon_i \\sim \\mathcal{N}(0, \\sigma^2)$ independent of $x_i$. We choose $\\theta_\\star = (\\mathbf{1}^\\top_s/\\sqrt{s},\\mathbf{0}^\\top_{d-s})^\\top$ and $\\sigma=1$. Using the learned representation $\\widehat{f}(x_i) \\in \\mathbb{R}^s$ from KL (or $\\chi^2$)-contrastive learning, we fit a downstream linear model to predict $y_i$. We define the excess risk of any predictor $h$ as $\\mathbb{E}[(y_i - h(x_i))^2] - \\sigma^2$, and evaluate the excess risk of the linear model trained on $(\\widehat{f}(x_i),y_i)\\_{i=1}^m$ using 50000 test samples. For comparison, we also report the excess risk of a linear model trained directly on the original samples $(x_i,y_i)\\_{i=1}^m$. Results for various downstream sample sizes $m$ and the standard deviation over 10 runs are shown below.\n\n> **Table: Excess risk  for various downstream sample sizes m**\n>\n> | m    | InfoNCE         | Chi-squared     | Direct LR       |\n> |------|-----------------|-----------------|-----------------|\n> | 150 | 0.106 ± 0.040 | 0.120 ± 0.028 | 2.066 ± 0.594 |\n> | 500 | 0.060 ± 0.015 | 0.070 ± 0.013 | 0.243 ± 0.032 |\n> | 1000 | 0.052 ± 0.012 | 0.063 ± 0.012 | 0.114 ± 0.021 |\n> | 2000 | 0.046 ± 0.011 | 0.058 ± 0.013 | 0.055 ± 0.012 |\n> | 5000 | 0.042 ± 0.011 | 0.055 ± 0.013 | 0.021 ± 0.005 |\n> | 10000 | 0.040 ± 0.012 | 0.054 ± 0.012 | 0.011 ± 0.004 |\n\n\nFrom the table, we observe that InfoNCE and Chi-squared achieve comparable excess risks (differences about one standard deviation), and both are substantially lower than that of direct linear regression when the sample size $m$ is relatively small (e.g., $m = 150, 500$). This suggests that both KL and $\\chi^2$-contrastive learning can learn a “good” low-dimensional representation for the downstream task. As the sample size increases, the excess risk of direct linear regression converges to zero, while those of InfoNCE and Chi-squared converge to non-zero constants. This is consistent with our theoretical results, which attribute the excess risk to the non-zero sufficiency of $\\widehat{f}$ and the augmentation error $\\epsilon_{\\mathcal{G}}$.\n\nDue to limited computational resources, we did not evaluate the performance of $\\chi^2$-contrastive learning on large-scale real-world datasets and leave this for future investigation. \n\n---\n\n> Other comments: use $f$ for both encoder and $f$-divergence.\n\nWe currently use different fonts for $f$ when referring to the encoder $f$ and the $\\mathsf{f}$-divergence. We will clarify this distinction more explicitly in the paper to avoid confusion.\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n---\n\n[1]. Von Kügelgen, Julius, et al. \"Self-supervised learning with data augmentations provably isolates content from style.\" Advances in neural information processing systems 34 (2021): 16451-16467.\n\n[2]. Daunhawer, Imant, et al. \"Identifiability results for multimodal contrastive learning.\" arXiv preprint arXiv:2303.09166 (2023).\n\n[3]. Chen, Ting, et al. \"A simple framework for contrastive learning of visual representations.\" International conference on machine learning. PmLR, 2020.\n\n[4]. Oko, K., Lin, L., Cai, Y., & Mei, S. (2025). A statistical theory of contrastive pre-training and multimodal generative ai. arXiv preprint arXiv:2501.04641."}, {"review_id": "Psq9eJP98G", "reviewer": "Reviewer_DTT6", "summary": "The paper develops a statistical framework for augmentation based contrastive learning such as SimCLR through the concept of approximate sufficient statistics. Three equivalent definitions of approximate sufficient statistics for general f-divergences are proposed. The authors show that minimizing a finite-batch InfoNCE loss yields encoders whose sufficiency gap is controlled by the excess empirical risk. \nThey then derive excess risk bounds for downstream regression and classification that depend on the encoder's sufficiency and the augmentation error.", "questions": "I would consider increasing the score after the following questions are at least partly addressed.\n1. Could you explain the technical gap or challenges to Oko et al. 2025 when dealing with a self-supervised contrastive learning for a single modality data?\n1. The paper introduces the augmentation error term $\\epsilon_G$. Do you have any upper bounds for any real augmentation such as random cropping, color jitter, or blur? \n1. As a curiosity, how does the temperature parameter in the InfoNCE loss affect convergence rate?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. Solid theoretical analysis for self supervised contrastive learning using data augmentation.\n1. Establishes a clear link between downstream risk and approximate sufficient statistics, and provides learning-theoretic bounds for those statistics.\n\n**Weaknesses**\n\n1. Their second claimed contribution (line 44) sounds vague. They assert that random transformations in SimCLR \"introduce additional challenges for theoretical analysis,\" but they do not identify the challenges of applying Oko et al. 2025 to the contrastive learning for a single modality data.\nAt the same time, their first claimed contribution (line 39) of extending approximate sufficient statistics from the KL divergence to any f divergence and proving three equivalent forms remains a modest generalization of Oko et al. 2025.\n\n1. SimCLR defines specific data augmentation schemes that are central to its success, yet the paper did not derive the resulting augmentation bias $\\epsilon_{\\mathcal{G}}$ for any of these transforms.", "was_revised": true, "final_justification": "I am changing my score to Borderline Accept (4), as the rebuttal meets the criteria I laid out in my Questions. In particular, it resolves my novelty concern of the difference from Oko et al. (2025).\n\nOn $\\epsilon_{\\mathcal{G}}$ for real augmentations, I understand that general bounds are difficult, but there is still no concrete bound even for a simplified version of a canonical augmentation (e.g., random cropping). This remaining gap is why my recommendation is borderline rather than a clear accept.", "rebuttal": "We are grateful to Reviewer DTT6 for their thoughtful review of our submission. Below, we respond to each question  raised in their review.\n\n---\n> Q1. Could you explain the technical gap or challenges to Oko et al. 2025 when dealing with a self-supervised contrastive learning for a single modality data?\n\nA1. A main technical challenge of extending Oko et al. (2025) [1] to single-modality data (especially to SimCLR) is handling the error induced by random augmentation. Note that random augmentation is not performed in CLIP considered in [1], and therefore the downstream error can be controlled directly via the sufficiency of the encoder (see, e.g., Propositions 2, 3, and 4 in [1]). In our work, we introduce a novel augmentation error term $\\epsilon\\_{\\mathcal{G}}$ (or $\\epsilon^{\\mathsf{cls}}\\_{\\mathcal{G}}$), and use it to establish downstream error bounds for any encoder $f$, by applying triangle inequalities for $\\ell_2$ error in regression (Theorem 2) and for KL divergence in classification (Theorem 3). Moreover, in the regression case (Theorem 2 and the subsequent discussion), we show that the same bound holds for the minimum error $\\widetilde\\epsilon\\_{\\mathcal{G}}$, suggesting the tightness of our bounds for encoders $f$ with low sufficiency.\n\n---\n\n> Q2. The paper introduces the augmentation error term $\\epsilon_{\\mathcal{G}}$. Do you have any upper bounds for any real augmentation such as random cropping, color jitter, or blur? \n\nA2. We thank the reviewer for this practical question. In general, it is challenging to derive upper bounds for real-world augmentations such as cropping, color jitter, or blur, as such bounds depend on concrete assumptions about the augmentations and oracle knowledge of the data. For example, in image classification tasks, the augmentation error of random cropping depends on the proportion of pixels dropped and the true label probabilities of the cropped images—which are typically unknown. Nevertheless, in practice, one may use the predicted label probabilities of the original and cropped images from a highly accurate image classifier as a surrogate for the true label probabilities, and use them to empirically estimate the augmentation error $\\epsilon^{\\mathsf{cls}}_{\\mathcal{G}}$.\n\n Theoretically, we emphasize that our main results hold for arbitrary data augmentation $g$, with the downstream error bounds depending on $g$ only through the augmentation error $\\epsilon\\_{\\mathcal{G}}$ (or $\\epsilon^{\\mathsf{cls}}\\_{\\mathcal{G}}$). Explicit bounds on  $\\epsilon\\_{\\mathcal{G}}$ (or $\\epsilon^{\\mathsf{cls}}\\_{\\mathcal{G}}$) require additional assumptions on the augmentation. For example, in the context of Theorem 6, we have $\\epsilon\\_{\\mathcal{G}}=0$ if $g$ is the projection onto some random subspace that contains $\\theta_\\star$.\n\n---\n> Q3. As a curiosity, how does the temperature parameter in the InfoNCE loss affect convergence rate?\n\nA3. In our work, the temperature parameter (denoted by $t$) enters the InfoNCE loss through the link function $\\tau(x)$ in Eq. (2) when defining  $\\tau(x):=x/t$. Theoretically, the temperature affects our bound on sufficiency (Theorem 1) through affecting the upper bound on the score $B_{\\mathsf{S}}$. Qualitatively, a smaller $t$ results in a larger constant $C$ in the bound in Eq. (4), which implies a slower convergence speed (up to constant factors).\n\n\n\n\n\n\n\n\n---\n\n\n[1]. Oko, K., Lin, L., Cai, Y., & Mei, S. (2025). A statistical theory of contrastive pre-training and multimodal generative ai. arXiv preprint arXiv:2501.04641."}]

Author rebuttal:

Meta-review: The paper develops a statistical framework for contrastive learning with data augmentation (e.g., SimCLR), extending prior work on CLIP with KL-divergence to general f-divergences. It formalizes the concept of approximate sufficient statistics, and shows that minimizing contrastive losses yields encoders that are approximately sufficient. 

Reviewers commented strengths such as theoretical contribution, mathematical rigor and timely topic. While three reviewers were originally worried of lack of experiments, they came out with positive comments after successful rebuttal. At the end, all have unanimously provided review score of 4. Given the theoretical nature of the contribution, an acceptance is recommended.
Decision: Accept (poster)