Tight PAC-Bayesian Risk Certificates for Contrastive Learning Anna van Elst, Debarghya Ghoshdastidar Abstract Contrastive representation learning is a modern paradigm for learning representations of unlabeled data via augmentations—precisely, contrastive models learn to embed semantically similar pairs of samples (positive pairs) closer than independently drawn samples (negative samples). In spite of its empirical success and widespread use in foundation models, statistical theory for contrastive learning remains less explored. Recent works have developed generalization error bounds for contrastive losses, but the resulting risk certificates are either vacuous (certificates based on Rademacher complexity or f f -divergence) or require strong assumptions about samples that are unreasonable in practice. The present paper develops non-vacuous PAC-Bayesian risk certificates for contrastive representation learning, considering the practical considerations of the popular SimCLR framework. Notably, we take into account that SimCLR reuses positive pairs of augmented data as negative samples for other data, thereby inducing strong dependence and making classical PAC or PAC-Bayesian bounds inapplicable. We further refine existing bounds on the downstream classification loss by incorporating SimCLR-specific factors, including data augmentation and temperature scaling, and derive risk certificates for the contrastive zero-one risk. The resulting bounds for contrastive loss and downstream prediction are much tighter than those of previous risk certificates, as demonstrated by experiments on CIFAR-10. 1 Introduction A key driving force behind the rapid advances in foundation models is the availability and exploitation of massive amounts of unlabeled data. Broadly, one learns meaningful representations from unlabeled data, reducing the demand for labeled samples when training (downstream) predictive models. In recent years, there has been a strong focus on self-supervised approaches to representation learning, which learn neural network-based embedding maps from carefully constructed augmentations of unlabeled data, such as image cropping, rotations, color distortion, Gaussian blur, etc. [ 2 , 7 , 9 , 17 ] . Contrastive representation learning is a popular form of self-supervised learning where one aims to extract meaningful features from unlabeled data by distinguishing between similar samples, obtained via augmentations, and dissimilar samples [ 54 , 22 , 28 ] . It has shown strong empirical performance across a wide range of of applications [ 24 ] , such as image recognition [ 7 , 57 ] , natural language processing [ 14 ] , audio processing [ 12 ] , and graph processing [ 55 , 42 ] . The core idea is to learn an embedding space where similar (positive) samples are pulled closer together, while dissimilar (negative) samples are pushed apart. This is typically accomplished using a contrastive loss function applied to features extracted by an encoder. A standard contrastive learning pipeline begins with data augmentation, where two augmented views of the same sample are generated to form a positive pair, while other samples in the batch serve as negatives. These augmented views are passed through an encoder network, optionally followed by a projection head. The network is then trained using a contrastive loss computed on these feature representations. Central to many contrastive frameworks is the InfoNCE loss [ 48 , 18 , 37 ] , which uses a softmax function over pairwise feature similarities, often incorporating feature normalization and temperature scaling. This loss is employed in popular frameworks such as SimCLR [ 7 ] , MoCo [ 22 ] , and CLIP [ 43 ] , where negative samples play a critical role. In contrast, other methods like Barlow Twins [ 56 ] and VICReg [ 4 ] eliminate the need for negative sampling by focusing on constraining the cross-correlation or cross-covariance matrix, while still ensuring alignment between positive pairs. In this work, we focus on the SimCLR framework ( i.e., simple framework for contrastive learning of representations ), which has gained widespread attention and demonstrated strong performance in a variety of downstream tasks [ 7 ] . Although SimCLR remains one of the most practically used contrastive models, theoretical analysis of SimCLR’s performance and generalization abilities is still limited [ 3 , 36 ] . The study of generalization error in self-supervised models is mostly based on two distinct frameworks [ 44 , 20 ] , both introduced in the context of contrastive learning. The contrastive unsupervised representation learning (CURL) framework, introduced by Arora et al. [ 44 ] , assumes access to tuples z_{1},\ldots,z_{n} , where each z=(x,x^{+},x^{-}_{1},\ldots,x^{-}_{k}) . The underlying statistical model considers data from a mixture of k (class) distributions, and within each z , it is assumed that x and x^{+} are independent samples from the same class, while x^{-}_{1},\ldots,x^{-}_{k} are k i.i.d. samples from the mixture model, independent of x,x^{+} . Arora et al. [ 44 ] derive Rademacher complexity-based generalization error (risk) bounds for representation learning using bound contrastive losses. Furthermore, the above statistical model for augmented data z allows one to extend the bounds to derive a risk certificate for downstream classification using the mean classifier [ 44 ] . Subsequently, improved risk certificates for both contrastive learning and downstream classification were derived in [ 30 ] using empirical covering numbers, and also in [ 36 ] using a PAC-Bayesian analysis or in [ 3 ] — the latter bounds being specifically obtained for the N-pair (or InfoNCE) loss used in SimCLR [ 48 , 7 ] . The CURL framework has been used to derive risk bounds for non-contrastive models [ 5 ] and adversarial contrastive models [ 59 ] , although both rely on Rademacher bounds. PAC-Bayes bounds have been instead stated in the context of meta-learning [ 13 ] . The independence of samples assumed in the CURL framework is quite impractical. For instance, in the SimCLR framework, the positive samples x,x^{+} are augmented views of the same data instances, for example, random rotation or cropping of the same image. In addition, practical implementations of SimCLR do not generate independent negative samples. The loss is computed over batches of positive pairs (x_{i},x_{i}^{+})_{i=1,\ldots,m} and for each x_{i} in a batch, all x_{j},x_{j}^{+},j\neq i are used as negative samples, thereby inducing strong dependence across tuples z_{1},\ldots,z_{n} and making classical PAC-Bayes analysis inapplicable. Nozawa et al. [ 36 ] derive f -divergence-based PAC-Bayes bounds to account for potential dependence across tuples z_{1},\ldots,z_{n} ; however, their resulting bounds are vacuous in practice. The impractical assumptions of CURL were noted by HaoChen et al. [ 20 ] , who in turn proposed risk certificates in terms of the augmentation graph: a graph over all samples, where each edge is weighted by the probability of obtaining both samples through independent random augmentations of the same data. This framework has proved to be quite useful for understanding inductive biases [ 19 ] , connections between contrastive learning and spectral methods [ 20 , 49 ] , the influence of data augmentation [ 52 , 53 ] , bounds for unsupervised domain adaptation [ 21 ] , etc. However, the setting requires technical assumptions on the augmentation graph, whose practical applicability is not clear, and the works do not provide risk certificates that can be empirically verified (the variance-based bounds could be vacuous in practice). Other approaches to study generalization in self-supervised learning have been suggested, although their suitability for deriving practical risk certificates has not been sufficiently explored. For instance, information theoretic bounds have been derived in [ 50 , 51 , 46 , 47 ] , generalization bounds under cluster assumptions on data have been suggested in [ 25 , 38 ] , and lower bounds on contrastive loss and cross-entropy risk have also been derived in [ 16 , 35 ] . Contrastive Loss Non-vacuous Sample dependence SimCLR Arora et al. [ 44 ] \times \times \times Nozawa et al. [ 36 ] ✓ ✓ \times Theorem 4 , 3 (ours) ✓ ✓ ✓ Downstream Risk Many - ve samples Data augmentation Temperature scaling Arora et al. [ 44 ] \times \times \times Bao et al. [ 3 ] ✓ \times \times Wang et al. [ 52 ] ✓ ✓ \times Theorem 5 (ours) ✓ ✓ ✓ Table 1 : Comparison of risk certificates for contrastive learning. A checkmark (✓) indicates that the method satisfies the specified condition, and a cross ( \times ) denotes that it does not. The table is divided into two parts: the first part compares generalization bounds for contrastive learning, assessing whether they are non-vacuous, account for sample dependence, and are directly applicable to the SimCLR loss. Although Nozawa et al. do not provide a SimCLR-specific bound, their f -divergence bound can be extended to SimCLR, as detailed in the supplementary material. The second part compares bounds on downstream classification loss, focusing on their incorporation of a large number of negative samples, data augmentation, and temperature scaling in contrastive loss. Motivation and contributions in this work The focus of the present work is to develop practical risk certificates for contrastive learning applicable to the widely used SimCLR framework. To this end, we consider an underlying data-generating model from which i.i.d. positive pairs can be sampled, which are used as negative samples for other samples—this framework is aligned with SimCLR. Using a PAC-Bayesian approach, we derive two new risk certificates for the SimCLR loss. The key issue in using a PAC-Bayesian analysis is to account for the dependence across tuples (via negative samples). Our main technical contribution is to show that current PAC-Bayes bounds can be improved when Hoeffding’s and McDiarmid’s inequalities are applied carefully [ 23 , 34 ] . We further build on recent advances in risk certificates for neural networks [ 41 , 40 ] , and, hence, arrive at certificates that are non-vacuous and significantly tighter than previous ones [ 36 ] . Additionally, most existing works do not consider practical settings that are known to enhance performance in the SimCLR framework, such as temperature scaling and large batch sizes [ 3 , 52 ] . We refine existing bounds on contrastive loss and downstream classification loss [ 52 , 3 ] by incorporating SimCLR-specific factors, including data augmentation and temperature scaling. We also extend our analysis to the contrastive zero-one risk [ 36 ] and derive corresponding risk certificates. A comparison of our risk certificates with existing bounds is summarized in Table 1 . The paper is organized as follows. We provide background on the SimCLR framework and PAC-Bayes theory in section 2 . We then present our main contribution in section 3 . In section 4 , we evaluate our results by conducting experiments on MNIST and CIFAR-10, and a discussion follows in section 5 . 2 Preliminaries In this section, we first explain the main components of the SimCLR framework, detailing notation and underlying assumptions. Next, we introduce essential concepts from the PAC-Bayes theory. 2.1 SimCLR framework The SimCLR framework [ 7 ] for contrastive learning involves several components: unlabeled data and augmentations, the model for representations, the contrastive loss, and for all practical purposes, some downstream prediction tasks. We describe these aspects with some theoretical considerations. Specifically, the study of generalization requires an underlying probabilistic model for data. We consider a model inspired by CURL [ 44 ] that makes fewer assumptions about augmented pairs (x,x^{+}) or negative samples. Data distribution Let \mathcal{X} denote the input space and \mathcal{D}_{\mathcal{X}} be a distribution on \mathcal{X} from which unlabeled data is sampled. For any unlabeled instance \bar{x}\sim\mathcal{D}_{\mathcal{X}} , one generates random augmented views of \bar{x} . We use \mathcal{A}(\cdot\mid\bar{x}) to denote the distribution of augmented samples generated from \bar{x} . We define the distribution \mathcal{S} as the process that generates a positive pair (x,x^{+}) according to the following scheme: (i) draw a sample \bar{x}\sim\mathcal{D}_{{\mathcal{X}}} ; (ii) draw two augmented samples x,x^{+}\sim\mathcal{A}(\cdot\mid\bar{x}). Note that we do not assume conditional independence of x,x^{+}|\bar{x} . The augmented views may also lie in a different space, outside \mathcal{X} , but this does not affect subsequent discussion. The distribution \mathcal{S} does not provide negative samples. This is actually computed in SimCLR from the positive pairs. In the subsequent presentation, we assume that one has access to i.i.d. sample of n positive pairs S\sim\mathcal{S}^{n} . The dataset S is randomly partitioned into equal-sized batches of m i.i.d. positive pairs S_{batch}\subset S . For each x_{i} , we use the tuple (x_{i},x_{i}^{+},X_{i}^{-}) to compute the loss, where the set of negative samples X_{i}^{-}=\bigcup_{j\neq i}\{x_{j},x_{j}^{+}\} is taken from the batch S_{batch} of size m containing x_{i} . Representation function SimCLR learns a representation function f:\mathcal{X}\rightarrow\mathbb{S}^{d-1} that maps inputs to unit vectors in d -dimensional space. For convenience, we consider the set of representation functions to be parameterized by the weight space \mathcal{W}\subset\mathbb{R}^{p} ; for instance, it could define the output of a neural network architecture with p learnable parameters. Thus, each representation function is determined by its weight vector w\in\mathcal{W} . Contrastive loss In SimCLR, the similarity between the learned representations of two instances f(x) and f(x^{\prime}) is typically defined in terms of their cosine similarity, \frac{f(x)^{\top}f(x^{\prime})}{\|f(x)\|\;\|f(x^{\prime})\|} , where \|\cdot\| is the Euclidean norm. Since the feature representations are normalized, we express the similarity between two representations as f(x)^{\top}f(x^{\prime}) . Let \tau\in(0,\infty) be a temperature parameter. To improve readability, we use the notation \operatorname{sim}(x,x^{\prime})=\exp\left(\frac{f(x)^{\top}f(x^{\prime})}{\tau}\right) and define \displaystyle\ell_{\operatorname{cont}}(x,x^{+},X)=-\log\frac{\operatorname{sim}(x,x^{+})}{\operatorname{sim}(x,x^{+})+\sum_{x^{\prime}\in X}\operatorname{sim}(x,x^{\prime})} . The empirical SimCLR loss over the dataset S\sim\mathcal{S}^{n} , denoted {\widehat{L}}_{S}(f) , is given by [ 7 ] : \frac{1}{n}\sum_{i=1}^{n}\frac{\ell_{\operatorname{cont}}(x_{i},x_{i}^{+},\bigcup_{j\neq i}\{x_{j}\})+\ell_{\operatorname{cont}}(x_{i}^{+},x_{i},\bigcup_{j\neq i}\{x_{j}^{+}\})}{2}=\frac{1}{n}\sum_{i=1}^{n}\ell(x_{i},x_{i}^{+},X_{i}^{-}), (1) where \ell(x_{i},x_{i}^{+},X_{i}^{-}) denotes the above symmetrization of \ell_{\operatorname{cont}} . Remark 1 . The SimCLR loss presented in eq. 1 differs slightly from the original loss from [ 7 ] , as it considers a subset of negative samples X_{i}^{-} instead of the full set X^{-} in each \ell_{\operatorname{cont}} . This approach still uses all available negative samples while simplifying the theoretical derivations. Importantly, any results derived for this simplified SimCLR loss can be straightforwardly extended to the original SimCLR loss [ 7 ] . A detailed expression of the original loss is provided in the supplementary materials. We define the population SimCLR loss, assuming a batch size of m , as {L}(f)=\underset{(x_{i},x_{i}^{+})_{i=1}^{m}\sim\mathcal{S}^{m}}{\mathbb{E}}\left[\frac{1}{m}\sum_{i=1}^{m}\ell(x_{i},x_{i}^{+},X_{i}^{-})\right]. (2) Note that the population loss remains unchanged if it is computed over all n pairs instead of a m -sized batch as the dependence of samples only occur within a batch. Evaluation of representations through downstream risk Classification is a typical downstream task for contrastive representation learning. Following prior theoretical works [ 44 , 3 ] , we assume that a linear classifier is trained on the representations. The multi-class classifier g:\mathcal{X}\rightarrow\mathbb{R}^{C} incorporates the learned representation f:\mathcal{X}\rightarrow\mathbb{R}^{d} (which remains frozen) and linear parameters W\in\mathbb{R}^{C\times d} , defined by g(\cdot):=Wf(\cdot) . The linear classifier is learned by minimizing the supervised cross-entropy loss of the multi-class classifier g expressed as: L_{\mathrm{CE}}(f,W)={\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[-\log\frac{\exp\left(f(x)^{\top}w_{y}\right)}{\sum_{i=1}^{C}\exp\left(f(x)^{\top}w_{i}\right)}\right] (3) where W:=[w_{1}\cdots w_{C}]^{\top} and \mathcal{D} is the joint distribution on samples x\in\mathcal{X} and labels y\in\{1,\ldots,C\} . We assume that \mathcal{D} has the same marginal \mathcal{D}_{\mathcal{X}} as the unlabeled data distribution. Additionally, we assume that any pair of positive samples (x,x^{+}) belongs to the same class, in line with the label consistency assumption presented in [ 52 ] . This assumption is reasonable in practice, as data augmentations are not expected to change the class of the original sample. We also define the top1 accuracy of the linear classifier, which can be evaluated as \texttt{top1}=1-R_{\text{top1}}(f,W),\quad\text{where }R_{\text{top1}}(f,W)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\mathbb{I}_{\{f(x)^{\top}w_{y}<\max\limits_{c\neq y}f(x)^{\top}w_{c}\}}\right]. (4) An alternative approach to evaluate learned representation f(\cdot) , without invoking a downstream problem, is in terms of the contrastive zero-one risk [ 36 ] defined as \displaystyle R(f) \displaystyle=\mathbb{E}_{(x_{i},x_{i}^{+})_{i=1}^{m}\sim\mathcal{S}^{m}}\left[\frac{1}{m}\sum_{i=1}^{m}\frac{1}{|X_{i}^{-}|}\sum_{x^{\prime}\in X_{i}^{-}}\mathbb{I}_{\left\{f(x_{i})^{\top}f(x_{i}^{+})b , the function x\mapsto\frac{x+a}{x+b} is strictly decreasing. This can be seen by computing its derivative: f^{\prime}(x)=\frac{b-a}{(x+b)^{2}}<0 . Therefore, since \kappa\geq(m-1)e^{-1/\tau} and the \log function is increasing, we obtain \log\frac{\kappa+a}{\kappa+b}\leq\log\frac{(m-1)e^{-1/\tau}+e^{1/\tau}}{(m-1)e^{-1/\tau}+e^{-1/\tau}}=\log\frac{(m-1)+e^{2/\tau}}{m}. Combining these results, we obtain |\delta^{i}_{\bar{S}_{m}}(\bar{x}_{i})|\leq\frac{4}{\tau} and |\delta^{j}_{\bar{S}_{m}}(\bar{x}_{i})|\leq\log\frac{(m-1)+e^{\frac{2}{\tau}}}{m} . This gives: |\Delta\phi_{\bar{S}}(\bar{x}_{i})|\leq\frac{1}{n}\left(\frac{4}{\tau}+(m-1)\log\frac{(m-1)+e^{\frac{2}{\tau}}}{m}\right)=\frac{C}{n}. Taking the supremum concludes the proof. ∎ The rest of the proof of theorem 3 follows the different steps of the proof presented in McAllester [ 32 ] , while incorporating the bounded difference assumption. The first step involves showing that we can bound the quantity \underset{S\sim\mathcal{S}^{n}}{\mathbb{E}}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right] for a certain non-negative and convex function h (this corresponds to lemmas 5 and 6 in [ 32 ] ). lemma 3 below modifies lemma 6 in [ 32 ] since we cannot use Hoeffding’s inequality, whereas lemma 2 is a minor modification of lemma 5 in [ 32 ] that allows us to directly apply McDiarmid’s inequality to prove lemma 3 . Lemma 2 (adaptation of [ 32 ] , Lemma 5) . Let X be a real valued random variable. If for n\in\mathbb{N}^{*} and for x>0 , \mathbb{P}(|X|\geq x)\leq 2e^{-nx^{2}} , then \mathbb{E}\left[e^{(n-1)X^{2}}\right]\leq 2n . Proof. The proof follows from McAllester’s work [ 33 ] . Assume for x>0 , \mathbb{P}(|X|\geq x)\leq 2e^{-nx^{2}} . Then the continuous density that maximizes \mathbb{E}\left[e^{(n-1)|X|^{2}}\right] and satisfies the previous inequality is such that \int_{x}^{\infty}f_{|X|}(u)\mathrm{d}u=2e^{-nx^{2}} which gives f_{|X|}(u)=4nue^{-nu^{2}} . We derive \mathbb{E}\left[e^{(n-1)|X|^{2}}\right]\leq\int_{0}^{\infty}e^{(n-1)u^{2}}f_{|X|}(u)\mathrm{d}u=2n . ∎ Lemma 3 (adaptation of [ 32 ] , Lemma 6) . Let h:x\mapsto\frac{2x^{2}}{C^{2}} and f\sim P . We have \underset{S\sim\mathcal{S}^{n}}{\mathbb{E}}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right]\leq 2n. Proof. The bounded difference assumption allows us to derive the following McDiarmid’s inequality: for \varepsilon>0 , \mathbb{P}_{S}\left(|L(f)-L_{S}(f)|\geq\varepsilon\right)\leq 2\exp\left(-\frac{2\varepsilon^{2}}{\sum_{i=1}^{n}c_{i}^{2}}\right) . Using the change of variable X=\frac{\sqrt{2}}{C}(L_{S}(f)-L(f)) , we observe that the McDiarmid’s inequality gives: for x>0 , \mathbb{P}\left(\frac{\sqrt{2}}{C}|X|\geq x\right)\leq 2\exp\left(-nx^{2}\right) . Invoking lemma 2 , we obtain \mathbb{E}_{S}\left[e^{(n-1)h(X)}\right]\leq 2n where h:x\mapsto\frac{2x^{2}}{C^{2}} . ∎ Given the bound in lemma 3 , one can derive the PAC-Bayes bound as shown by McAllester [ 32 ] (lemma 7–8). We adapt those results in the following statement. Lemma 4 (adaptation of [ 32 ] , Lemma 7–8) . Let h be a non-negative and convex function. If for a fixed f\sim P , the following inequality holds \underset{S\sim\mathcal{S}^{n}}{\mathbb{E}}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right]\leq 2n , then with probability at least 1-\delta over i.i.d. dataset S : \forall Q,\quad h(L_{S}(Q)-L(Q))\leq\frac{\mathrm{KL}(Q\|P)+\log\frac{2n}{\delta}}{n-1}. Proof. Assume for a fixed f\sim P , \underset{S\sim\mathcal{S}^{n}}{\mathbb{E}}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right]\leq 2n . This implies the bound \mathbb{E}_{S}\left[\mathbb{E}_{f\sim P}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right]\right]\leq 2n . Applying Markov’s inequality, we obtain that with probability at least 1-\delta over S , \mathbb{E}_{f\sim P}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right]\leq\frac{2n}{\delta} . Next, we use a shift of measure: \mathbb{E}_{f\sim Q}\left[(n-1)h\left(L_{S}(f)-L(f)\right)\right]\leq\mathrm{KL}(Q\|P)+\log\mathbb{E}_{f\sim P}\left[e^{(n-1)h\left(L_{S}(f)-L(f)\right)}\right] . Combining the previous results, with probability at least 1-\delta over dataset S : \mathbb{E}_{f\sim Q}\left[(n-1)h\left(L_{S}(f)-L(f)\right)\right]\leq\mathrm{KL}(Q\|P)+\log\frac{2n}{\delta}. Since h is convex, applying Jensen’s inequality finishes the proof: (n-1)h\left(L_{S}(Q)-L(Q)\right)\leq\mathrm{KL}(Q\|P)+\log\frac{2n}{\delta}. ∎ Rewriting the statement of lemma 4 shows that, with probability at least 1-\delta over i.i.d. dataset S , L(Q)\leq L_{S}(Q)+C\sqrt{\frac{\mathrm{KL}(Q\|P)+\log\frac{2n}{\delta}}{2(n-1)}} for all Q , completing the proof of theorem 3 . 3.1.2 Second PAC-Bayes certificate While theorem 3 uses the bounded difference assumption, an alternative approach would be to replace \sum_{x^{\prime}\in X}\operatorname{sim}(x_{i},x^{\prime}) in ( 1 ) by its expected value, conditioned on x_{i} , thereby making the terms in ( 1 ) independent. To implement this in the PAC-Bayes framework, we define an \varepsilon -modified SimCLR empirical loss L_{S}^{\prime}(Q)=\int_{\mathcal{W}}L_{S}^{\prime}(f_{w})\,Q(dw) by replacing \ell_{\text{cont}} in ( 1 ) with an upper bound \ell^{\prime}_{\text{cont}} as \ell_{\text{cont}}(x,x^{+},X)\leq\ell^{\prime}_{\text{cont}}(x,x^{+},X)=-\log\frac{\operatorname{sim}(x,x^{+})}{\operatorname{sim}(x,x^{+})+\sum_{x^{\prime}\in X}\operatorname{sim}(x,x^{\prime})+2\varepsilon}. Modifying the loss by the above \varepsilon -factor allows us to bound it by an intermediate loss \widetilde{L}_{S}(f) , defined later, using a concentration bound on the negative samples. \widetilde{L}_{S}(f) turns out to be a mean of i.i.d. terms, allowing us to directly apply the PAC-Bayes bound. The overall bound is summarized through the following theorem that provides a novel PAC-Bayes bound for the SimCLR population loss, extending the PAC-Bayes-kl bound using Hoeffding’s inequality [ 23 ] . Theorem 4 (Extended PAC-Bayes-kl Bound) . Let m denote the batch size and \delta\in(0,1) . With probability at least 1-\delta over dataset S , for all Q : L(Q)\leq\inf_{\alpha\in(0,1)}\left\{B\cdot\mathrm{kl}^{-1}\left(\frac{1}{B}L_{S}^{\prime}(Q)+\left(\frac{\delta}{2}\right)^{\frac{1-\alpha}{\alpha}},\frac{\mathrm{KL}(Q\|P)+\log\left(\frac{\sqrt{n}}{\delta}\right)}{n}\right)+\left(\frac{\delta}{2}\right)^{\frac{1}{\alpha}}\right\}, where B:=\frac{1}{\tau}+\log\left(me^{\frac{1}{\tau}}\right)+\varepsilon for \varepsilon=\left(e^{\frac{1}{\tau}}-e^{-\frac{1}{\tau}}\right)\sqrt{\frac{m-1}{2\alpha}\log\frac{2}{\delta}} . Remark 3 . Observe that Theorem 4 still holds for the original SimCLR loss by replacing \varepsilon with 2\varepsilon . This result follows from grouping terms involving augmented views of the same sample into one variable, \operatorname{sim}(x,x^{\prime})+\operatorname{sim}(x,{x^{\prime}}^{+}) , before applying the concentration bound. This ensures that the variables are independent while multiplying the bound by 2 . The remainder of this subsection is dedicated to the proof of theorem 4 . First, we apply a Hoeffding’s inequality to the term involving the negative samples, as stated below. Lemma 5 (concentration bound on the negative samples) . Let f\sim Q and recall the notation S(x,X):=\sum\limits_{x^{\prime}\in X}\operatorname{sim}(x,x^{\prime}) . For all \delta\in(0,1) , with \varepsilon=\left(e^{\frac{1}{\tau}}-e^{-\frac{1}{\tau}}\right)\sqrt{\frac{m-1}{2}\log\frac{1}{\delta}} , the following concentration bound holds: \mathbb{P}\left(S(x,X)-\mathbb{E}[S(x,X)]\geq\varepsilon\mid x\right)\leq\delta. Proof. Let \delta\in(0,1) . Conditioned on x , we have a sum of independent and bounded variables, as each variable is lower-bounded by e^{-\frac{1}{\tau}} and upper-bounded by e^{\frac{1}{\tau}} . Hence, Hoeffding’s inequality gives: for all \varepsilon>0 , \mathbb{P}\left(S(x,X)-\mathbb{E}[S(x,X)]\geq\varepsilon\mid x\right)\leq\delta , where we set \delta:=\exp\left(-\frac{2\varepsilon^{2}}{(m-1)c^{2}}\right) for c=e^{\frac{1}{\tau}}-e^{-\frac{1}{\tau}} . Deriving the expression of \varepsilon finishes the proof. ∎ Recall the SimCLR population loss L(f) defined in eq. 2 . Define the intermediate loss \widetilde{L}(f) which is a mean of i.i.d. terms obtained by replacing \ell_{\text{cont}} with the loss \tilde{\ell}_{\text{cont}} given by \tilde{\ell}_{\text{cont}}(x,x^{+}):=-\log\frac{\operatorname{sim}(x,x^{+})}{\operatorname{sim}(x,x^{+})+\mathbb{E}\left[S(x,X)\mid x\right]+\varepsilon} for a suitable \varepsilon>0 . We obtain the following \widetilde{L}(f):=\mathbb{E}_{(x,x^{+})\sim\mathcal{S}}\left[\frac{\tilde{\ell}_{\text{cont}}(x,x^{+})+\tilde{\ell}_{\text{cont}}(x^{+},x)}{2}\right]=\mathbb{E}_{(x,x^{+})\sim\mathcal{S}}\left[\tilde{\ell}(x,x^{+})\right]. (6) Using lemma 5 , the following lemma shows that L(f) can be upper-bounded by \widetilde{L}(f) . Lemma 6 (upper-bound by an intermediate loss) . Let f\sim Q and \widetilde{L}(f) defined in eq. 6 . Let \delta\in(0,1) and B_{\ell}=\frac{2}{\tau}+\log m . Then, we have L(f)\leq\widetilde{L}(f)+B_{\ell}\delta. (7) Proof. Recall that \ell_{\operatorname{cont}}(x,x^{+},X^{-}) can be written as an average of two terms that play a symmetric role. Hence, we will first upper-bound \ell_{\operatorname{cont}}(x,x^{+},X) where X=\bigcup_{x^{\prime}\neq x}\{x^{\prime}\} . Observe that \ell_{\operatorname{cont}}(x,x^{+},X) can be split into two terms using \varepsilon defined in lemma 5 : \ell_{\operatorname{cont}}(x,x^{+},X)\leq\tilde{\ell}_{\text{cont}}(x,x^{+})\mathbb{I}_{\{S(x,X)<\mu(x)+\varepsilon\}}+\ell_{\operatorname{cont}}(x,x^{+},X)\mathbb{I}_{\{S(x,X)\geq\mu(x)+\varepsilon\}}, where \mu(x)=\mathbb{E}\left[S(x,X)\mid x\right] . Noting that \ell_{\operatorname{cont}}(x,x^{+},X)\leq B_{\ell} and \mathbb{I}_{\{\cdot\}}\leq 1 , we obtain \ell_{\operatorname{cont}}(x,x^{+},X)\leq\tilde{\ell}_{\text{cont}}(x,x^{+})+B_{\ell}\mathbb{I}_{\{S(x,X)\geq\mu(x)+\varepsilon\}} . We derive: \ell(x,x^{+},X^{-})\leq\tilde{\ell}(x,x^{+})+B_{\ell}\frac{\mathbb{I}_{\{S(x,X)\geq\mu(x)+\varepsilon\}}+\mathbb{I}_{\{S(x^{+},X^{\prime})\geq\mu(x^{+})+\varepsilon\}}}{2}, (8) where X^{\prime}=\bigcup_{x^{\prime}\neq x}\{{x^{\prime}}^{+}\} . Using lemma 5 and the expression of L(f) combined with eq. 8 , L(f)\leq\underset{(x_{i},x_{i}^{+})_{i=1}^{m}\sim\mathcal{S}^{m}}{\mathbb{E}}\left[\frac{1}{m}\sum_{i=1}^{m}\tilde{\ell}(x_{i},x_{i}^{+})\right]+B_{\ell}\delta\,, (9) which finishes the proof. ∎ Define the empirical intermediate loss as \widetilde{L}_{S}(f)=\frac{1}{m}\sum_{i=1}^{m}\tilde{\ell}(x_{i},x_{i}^{+}). (10) Since \widetilde{L}_{S}(f) is an average of i.i.d. terms, the following result is a direct application of the PAC-Bayes-kl bound ( theorem 1 ) after rescaling of the loss function to the interval [0,1] . Corollary 1 (PAC-Bayes-kl bound for the intermediate loss) . For S\sim\mathcal{S}^{n} , let \widetilde{L}(f) and \widetilde{L}_{S}(f) be defined as in eq. 6 and eq. 10 respectively, and define the extended losses: \widetilde{L}(Q)=\mathbb{E}_{f\sim\mathcal{Q}}\left[\widetilde{L}(f)\right] and \widetilde{L}_{S}(Q)=\mathbb{E}_{f\sim\mathcal{Q}}\left[\widetilde{L}_{S}(f)\right] . Let B:=\frac{1}{\tau}+\log(me^{\frac{1}{\tau}}+\varepsilon) . Given a prior P over \mathcal{F} and \delta\in(0,1) , with probability at least 1-\delta over i.i.d. samples S\sim\mathcal{S}^{n} , for all Q over \mathcal{F} , \frac{1}{B}\widetilde{L}(Q)\leq\mathrm{kl}^{-1}\left(\frac{1}{B}\widetilde{L}_{S}(Q),\frac{\mathrm{KL}\left(Q\|P\right)+\log\left(\frac{2\sqrt{n}}{\delta}\right)}{n}\right). The next lemma allows to upper-bound the empirical intermediate loss by a term similar to the SimCLR empirical loss, introduced earlier as the \varepsilon -modified SimCLR loss L_{S}^{\prime}(Q) . Lemma 7 (upper-bound on the intermediate empirical loss) . Let \alpha\in(0,1) and \delta\in(0,1) . With probability at least 1-\delta^{\alpha} over dataset S : \widetilde{L}_{S}(Q)\leq B\delta^{1-\alpha}+L_{S}^{\prime}(Q). Proof of lemma 7 . To prove lemma 7 , we first need the following useful lemma. Lemma 8 . Let \alpha\in(0,1) and \delta\in(0,1) . If for any event A(f,x,X) with f\sim Q , we have {\mathbb{P}}_{X}\left[A(f,x,X)\mid f,x\right]\leq\delta , then, with probability at least 1-\delta^{\alpha} over dataset S\sim\mathcal{S}^{n} , \frac{1}{n}\sum_{i=1}^{n}\underset{f\sim Q}{\mathbb{E}}\left[\mathbb{I}_{\{A(f,x_{i},X_{i})\}}\mid x_{i},X_{i}^{-}\right]\leq\delta^{1-\alpha}. Proof of lemma 8 . For ease of notation, define U=\mathbb{I}_{\{A(f,x,X)\}} with f\sim Q . Assume for any augmented sample x , {\mathbb{P}}_{X}\left[A(f,x,X)\mid f,x\right]\leq\delta . Then, using Markov’s inequality, we derive: \displaystyle{\mathbb{P}}_{S}\left[\frac{1}{n}\sum_{i=1}^{n}\underset{f\sim Q}{\mathbb{E}}\left[U\mid x_{i},X_{i}\right]>\delta^{1-\alpha}\right] \displaystyle\leq\frac{1}{\delta^{1-\alpha}}{\mathbb{E}}_{S}\left[\frac{1}{n}\sum_{i=1}^{n}\underset{f\sim Q}{\mathbb{E}}\left[U\mid x_{i},X_{i}\right]\right] \displaystyle=\frac{1}{\delta^{1-\alpha}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{x_{i},X_{i}}\left[{\mathbb{E}_{f}}\left[U\mid x_{i},X_{i}\right]\right] \displaystyle=\frac{1}{\delta^{1-\alpha}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{f,x_{i},X_{i}}\left[U\right] \displaystyle=\frac{1}{\delta^{1-\alpha}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{f,x_{i}}\left[\mathbb{E}_{X_{i}}\left[U\mid f,x_{i}\right]\right] \displaystyle\leq\frac{1}{\delta^{1-\alpha}}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{f,x_{i}}\left[\delta\right]=\delta^{\alpha}. ∎ Define A(f,x,X):=\{S(x,X)-\mu(x)\leq-\varepsilon\} . Similarly to the inequality from lemma 5 , we can derive, for an augmented sample x , \mathbb{P}\left(S(x,X)-\mu(x)\leq-\varepsilon\mid x\right)\leq\delta . Next, using similar arguments to the proof of lemma lemma 6 , we derive an upper bound on \tilde{\ell}(x,x^{+}) : \tilde{\ell}(x,x^{+})\leq B\frac{\mathbb{I}_{\{S(x,X)+\varepsilon\leq\mu(x)\}}+\mathbb{I}_{\{S(x^{+},X^{\prime})+\varepsilon\leq\mu(x^{+})\}}}{2}+\ell^{\prime}(x,x^{+},X^{-}). Plugging this into the intermediate empirical loss, we obtain: \widetilde{L}_{S}(Q)\leq\frac{B}{n}\sum_{i=1}^{n}\frac{1}{2}\left(\underset{f\sim Q}{\mathbb{E}}\left[\mathbb{I}_{\{A(f,x_{i},X_{i})\}}\mid x_{i},X_{i}\right]+\underset{f\sim Q}{\mathbb{E}}\left[\mathbb{I}_{\{A(f,x_{i}^{+},X_{i}^{\prime})\}}\mid x_{i}^{+},X_{i}^{\prime}\right]\right)+L_{S}^{\prime}(Q). Invoking lemma 8 , we obtain: with probability at least 1-\delta^{\alpha} over dataset S : \widetilde{L}_{S}(Q)\leq B\delta^{1-\alpha}+L_{S}^{\prime}(Q), which finishes the proof. ∎ Let \alpha\in(0,1) . We will now combine all previously established lemmas to finish the proof of theorem 4 . Given that B_{\ell}\leq B and for \delta_{1}\in(0,1) , lemma 6 can be rewritten as L(Q)\leq\widetilde{L}(Q)+B\delta_{1} . Next, combining this inequality with corollary 1 , we obtain for \delta_{2}\in(0,1) : with probability at least 1-\delta_{2} over training i.i.d. samples S\sim\mathcal{S}^{n} , for all Q over \mathcal{F} , \frac{1}{B}\widetilde{L}(Q)\leq\mathrm{kl}^{-1}\left(\frac{1}{B}\widetilde{L}_{S}(Q),\frac{\mathrm{KL}\left(Q\|P\right)+\log\left(\frac{2\sqrt{n}}{\delta_{2}}\right)}{n}\right)+\delta_{1}. Using a union bound argument, and given the property of \mathrm{kl}^{-1} as a monotonically increasing function of its first argument when fixing the second argument [ 41 ] , we can now combine the previous bounds with lemma 7 : with probability at least 1-\delta_{2}-\delta_{1}^{\alpha} over dataset S , for all Q over \mathcal{F} , \frac{1}{B}L(Q)\leq\mathrm{kl}^{-1}\left(\frac{1}{B}L_{S}^{\prime}(Q)+\delta_{1}^{1-\alpha},\frac{\mathrm{KL}\left(Q\|P\right)+\log\left(\frac{2\sqrt{n}}{\delta_{2}}\right)}{n}\right)+\delta_{1}. Let \delta\in(0,1) and set \ \delta_{1}^{\alpha}=\frac{\delta}{2} , \delta_{2}=\frac{\delta}{2} . Taking the infimum over \alpha finishes the proof. 3.2 Bound on the Downstream Classification Loss Bao et al. [ 3 ] derive a bound on the downstream supervised loss, addressing a key limitation of the earlier bound by Arora et al. [ 44 ] , whose bound grows exponentially with the number of negative samples. However, Bao et al. [ 3 ] employ a simplified framework where positive pairs are not generated through data augmentation, and the contrastive loss is computed without batching and temperature scaling. Empirical results, notably from the SimCLR framework, have demonstrated superior performance over this basic approach [ 7 ] . In the following theorem, we extend Bao et al.’s bound [ 3 ] to accommodate the SimCLR framework. Specifically, we show that the loss can be computed over a batch and that, by leveraging an argument from Wang et al. [ 52 ] , the bound holds when positive pairs correspond to augmented views. Additionally, we introduce a novel extension of the bound that incorporates temperature scaling. Theorem 5 (Extended Surrogate Gap) . Consider the cross-entropy loss L_{\mathrm{CE}}(f,W) in ( 3 ) and denote the class distribution by \boldsymbol{\pi}:=[\mathbb{P}(Y=c)]_{c\in\mathcal{C}} . For all f:\mathcal{X}\rightarrow\mathbb{S}^{d-1} , the following inequality holds: \min_{W\in\mathbb{R}^{C\times d}}L_{\mathrm{CE}}(f,W)\leq\min\big\{\beta(f,\sigma),~\tau\beta(f,\sigma)+\alpha\big\} with \beta(f,\sigma)=\frac{\sigma}{\tau}+L(f)+\Delta for \Delta=\log\left(\frac{C^{2}\pi^{*}}{m-1}\operatorname{cosh}^{2}\left(\frac{1}{\tau}\right)\right) where \pi^{*}:=\max_{c\in\mathcal{C}}\pi(c) . Furthermore, \alpha is given by \alpha=\log(C)+\min\{0,\log(C\pi^{*}\operatorname{cosh}^{2}(1))-\tau\Delta\} and \sigma={\mathbb{E}}_{(x,y)}\left[\|f(x)-\mu_{y}\|_{2}\right]\leq 2 represents the intra-class feature deviation. Remark 4 . Practical implementations often consider a deterministic or learnable projection of the representation f(x) . After contrastive training, the projection head is removed, and only the backbone features are used for downstream tasks. Notably, theorem 5 can be extended to include a simple projection head of the form (I_{k},0) . Let f(x)\in\mathbb{R}^{d} denote the backbone features and f_{1}(x)\in\mathbb{R}^{k} the projection head output, where typically d\geq k . We can generalize theorem 5 by considering the contrastive loss on the projected features L(f_{1}) instead of L(f) and by modifying the supervised loss L_{\mathrm{CE}}(f,W) as follows: \underset{x,y\sim\mathcal{D}}{\mathbb{E}}\left[-\log\frac{\exp\left(f_{1}(x)^{\top}w^{(1)}_{y}+f_{2}(x)^{\top}w^{(2)}_{y}\right)}{\sum_{i=1}^{C}\exp\left(f_{1}(x)^{\top}w^{(1)}_{i}+f_{2}(x)^{\top}w^{(2)}_{i}\right)}\right] where f_{2}(x)\in\mathbb{R}^{d-k} is defined such that f(x)=\begin{bmatrix}f_{1}(x)\\ f_{2}(x)\end{bmatrix} and W=\begin{bmatrix}W^{(1)}\\ W^{(2)}\end{bmatrix} . Remark 5 . Note that theorem 5 can be applied to the original SimCLR loss by replacing m-1 with 2(m-1) . When the class distribution is uniform, \pi^{*} simplifies to 1/C . The rest of the subsection proves theorem 5 . First, observe that the SimCLR population loss defined in eq. 2 can be rewritten as L(f)={\mathbb{E}}_{(x_{i},x_{i}^{+})_{i=1}^{m}\sim\mathcal{S}^{m}}\left[\frac{1}{m}\sum_{i=1}^{m}\ell_{\operatorname{cont}}(x_{i},x_{i}^{+},X_{i})\right] where X_{i}=\bigcup_{j\neq i}\{x_{j}\} denotes the set of negative samples. The first part of the theorem builds on the proof from Bao et al. [ 3 ] , but instead of their simple framework, we enhance the applicability of the proof for the SimCLR framework, where the contrastive loss is computed over a batch and includes temperature scaling. Additionally, to address the fact that the positive pair is generated through data augmentation, we incorporate an argument from Wang et al.’s proof [ 52 ] . The following lemma presents the first part of the theorem. Lemma 9 . For all f:\mathcal{X}\rightarrow\mathbb{S}^{d-1} , the following inequality holds: \min_{W\in\mathbb{R}^{C\times d}}L_{\mathrm{CE}}(f,W)\leq\frac{\sigma}{\tau}+L(f)+\Delta. Proof. Let \operatorname{LSE}(\mathbf{z}):=\log\left(\sum_{j}\exp\left(z_{j}\right)\right) where \mathbf{z}:=\left\{{f(x)^{\top}f(x^{\prime})/\tau}\right\}_{x^{\prime}\in X} . For convenience, we define X as the set of negative samples corresponding to the anchor sample x , with the total number of negative samples denoted by K=m-1 . The elements of X are indexed by i=1,\ldots,K . Denoting the class-conditional distribution by \mathcal{D}_{c}:=\mathbb{P}(X\mid Y=c) for each c\in\mathcal{C} , we define \mu_{c}=\mathbb{E}_{\mathbf{x}\sim\mathcal{D}_{c}}[f(x)] and note that \|\mu_{c}\|\leq 1 . We have \displaystyle L(f) \displaystyle\overset{(a)}{\geq}-\underset{{S\sim\mathcal{S}^{m}}}{\mathbb{E}}\left[\frac{1}{m}\sum_{i=1}^{m}\frac{f({x_{i}})^{\top}f({x_{i}}^{+})}{\tau}\right]+\underset{{S\sim\mathcal{S}^{m}}}{\mathbb{E}}\left[\frac{1}{m}\sum_{i=1}^{m}\log\sum_{x^{\prime}\in X_{i}}\exp\left(\frac{f({x_{i}})^{\top}f({x^{\prime}})}{\tau}\right)\right] (11) \displaystyle\overset{(b)}{=}-\mathbb{E}_{(x,x^{+})\sim\mathcal{S}}\left[\frac{f({x})^{\top}f({x}^{+})}{\tau}\right]+\frac{1}{m}\sum_{i=1}^{m}\underset{S\sim\mathcal{S}^{m}}{\mathbb{E}}\left[\operatorname{LSE}(\mathbf{z})\right] (12) \displaystyle\overset{(c)}{\geq}-\frac{\mathbb{E}_{(x,y)}\left[\|f(x)-\mu_{y}\|_{2}\right]}{\tau}-\mathbb{E}_{(x,y)}\left[\frac{f(x)^{\top}\mu_{y}}{\tau}\right]+\mathbb{E}_{x}\mathbb{E}_{X}\left[\operatorname{LSE}(\mathbf{z})\right] (13) \displaystyle\overset{(d)}{=}-\frac{\sigma}{\tau}-\mathbb{E}_{(x,y)}\left[\frac{f(x)^{\top}\mu_{y}}{\tau}\right]+\mathbb{E}_{x}\mathbb{E}_{\begin{subarray}{c}\{(x_{i}^{\prime},y_{i}^{\prime})\}_{i=1}^{K}\end{subarray}}\left[\operatorname{LSE}(\mathbf{z})\right] (14) \displaystyle\overset{(e)}{\geq}-\frac{\sigma}{\tau}-\mathbb{E}_{(x,y)}\left[\frac{f(x)^{\top}\mu_{y}}{\tau}\right]+\mathbb{E}_{x}\mathbb{E}_{\begin{subarray}{c}\{y_{i}^{\prime}\}_{i=1}^{K}\end{subarray}}\left[\operatorname{LSE}(\mathbf{z}^{\mu})\right] (15) where (a) relies on \exp\left(f({x})^{\top}f({x}^{+})\right)\geq 0 , (b) follows from rewriting the expectations and using the definition of the \operatorname{LSE} function (c) uses the argument from Wang et al. : using the Cauchy-Schwarz inequality, assuming y is the label of the positive pair (x,x^{+}) , we can show for any \mu_{y} , \left|f(x)^{\top}\frac{f(x^{+})-\mu_{y}}{\left\|f(x^{+})-\mu_{y}\right\|}\right|\leq 1 [ 52 ] , (d) uses the definition of the intra-class feature deviation \sigma:=\mathbb{E}_{(x,y)}\left[\|f(x)-\mu_{y}\|_{2}\right] , (e) uses the Jensen’s inequality and the convexity of the \operatorname{LSE} function where we define \mathbf{z}^{\mu}:=\left\{{f(x)^{\top}\mu_{y^{\prime}}/\tau}\right\}_{y^{\prime}\in Y} where we denote Y=\begin{subarray}{c}\{y_{i}^{\prime}\}_{i=1}^{K}\end{subarray} . Next, we need to lower-bound the quantity \mathbb{E}_{Y}\left[\operatorname{LSE}(\mathbf{z}^{\mu})\right] . We will use the following lemma. Lemma 10 (Bao et al. [ 3 ] , lemma 3) . Let N\in\mathbb{N}^{*} and L\in\mathbb{R}^{+} . For \mathbf{z}\in[-L^{2},L^{2}]^{N} , 2\log N\leq\mathrm{LSE}(\mathbf{z})+\mathrm{LSE}(-\mathbf{z})\leq 2\log\left(N\cosh(L^{2})\right). We apply this lemma for N=K and L={1/\sqrt{\tau}} . We obtain \displaystyle\mathbb{E}_{Y}\left[\operatorname{LSE}(\mathbf{z}^{\mu})\right] \displaystyle\overset{(a)}{\geq}-\mathbb{E}_{Y}\left[\operatorname{LSE}(-\mathbf{z}^{\mu})\right]+2\log(K) (16) \displaystyle\overset{(b)}{\geq}-\log\sum_{y^{\prime}\in Y}\mathbb{E}_{\begin{subarray}{c}y^{\prime}\end{subarray}}\left[\exp(-f(x)^{\top}\mu_{y^{\prime}}/\tau)\right]+2\log(K) (17) \displaystyle\overset{(c)}{=}-\log K\sum_{c\in\mathcal{C}}\exp(-f(x)^{\top}\mu_{c}/\tau)\pi(c)+2\log(K) (18) \displaystyle\overset{(d)}{\geq}-\log{K\pi^{*}}\sum_{c\in\mathcal{C}}\exp(-f(x)^{\top}\mu_{c}/\tau)+2\log(K) (19) \displaystyle\overset{(e)}{=}-\operatorname{LSE}\left(\left\{-f(x)^{\top}\mu_{c}/\tau\right\}_{c\in\mathcal{C}}\right)+\log(K)-\log(\pi^{*}) (20) \displaystyle\overset{(f)}{\geq}\operatorname{LSE}\left(\left\{f(x)^{\top}\mu_{c}/\tau\right\}_{c\in\mathcal{C}}\right)-2\log\left(C\cosh\frac{1}{\tau}\right)+\log(K)-\log(\pi^{*}) (21) \displaystyle\overset{(g)}{=}\operatorname{LSE}\left(\left\{f(x)^{\top}\mu_{c}/\tau\right\}_{c\in\mathcal{C}}\right)-\Delta\,, (22) where (a) directly comes from lemma 10 , (b) applies Jensen’s inequality to the convex function x\mapsto-\log x and then the linearity of expectation, (c) uses the distribution \pi(c) over the classes and \mathcal{C} represents the set of classes, (d) uses the bound \pi(c)\leq\pi^{*} for all c\in\mathcal{C} and the monotonicity of -\log , (e) uses the definition of the \operatorname{LSE} function, (f) is another application of lemma 10 , and (g) uses the definition \Delta:=\log\left(\frac{C^{2}\pi^{*}}{K}\operatorname{cosh}^{2}(\frac{1}{\tau})\right) . We can now combine the previous inequality and recognizing the cross-entropy loss of a linear classifier for W^{\mu/\tau}:=[\frac{\mu_{1}}{\tau}\cdots\frac{\mu_{C}}{\tau}]^{\top} , we have \displaystyle L(f) \displaystyle{\geq}-\frac{\sigma}{\tau}-\mathbb{E}_{(x,y)}\left[\frac{f(x)^{\top}\mu_{y}}{\tau}\right]+\mathbb{E}_{x}\operatorname{LSE}\left(\left\{\frac{f(x)^{\top}\mu_{c}}{\tau}\right\}_{c\in\mathcal{C}}\right)-\Delta \displaystyle=-\frac{\sigma}{\tau}+L_{\mathrm{CE}}(f,W^{\mu/\tau})-\Delta Taking the minimum over all linear classifiers finishes the proof. ∎ The second part of the theorem is an extension of lemma 9 obtained by removing the temperature scaling from the \operatorname{LSE} term. The result is stated in the following lemma. Lemma 11 . For all f:\mathcal{X}\rightarrow\mathbb{S}^{d-1} , the following inequality holds: \min_{W\in\mathbb{R}^{C\times d}}L_{\mathrm{CE}}(f,W)\leq\sigma+\tau L(f)+\tau\Delta+\alpha, where \alpha=\log(C)+\min\left\{0,\log(C\pi^{*}\operatorname{cosh}^{2}(1))-\tau\Delta\right\} . Sketch of Proof. For a detailed proof of the lemma, we refer the reader to the supplementary materials. We first derive a useful inequality that show that the \operatorname{LSE} function acts as a smooth maximum. For N\in\mathbb{N}^{*} , \mathbf{x}\in\mathbb{R}^{N} with \mathbf{x}=(x_{1},\ldots,x_{N}) , and for any t>0 , t\max_{i}x_{i}<\operatorname{LSE}(t\mathbf{x})\leq t\max_{i}x_{i}+\log(N). (23) The inequality is verified by observing that if m=\max_{i}x_{i} , then we have the following inequality \exp(tm)\leq\sum_{i=1}^{N}\exp\left(tx_{i}\right)\leq N\exp(tm) . Applying the logarithm gives the result. Define W^{\mu}:=[\mu_{1}\cdots\mu_{C}]^{\top} . The bound presented in lemma 11 follows from two applications of ( 23 ) at different steps of the proof of lemma 9 . On one hand, applying ( 23 ) to the term \operatorname{LSE}(\mathbf{z}) introduces a factor of \log(K) . With \mathbf{u}:=\left\{f(x)^{\top}f(x^{\prime})\right\}_{x^{\prime}\in X} , this yields \operatorname{LSE}(\mathbf{z})\geq\frac{1}{\tau}\left(\operatorname{LSE}(\mathbf{u})-\log(K)\right) . Following a proof similar to lemma 9 with L=1 , we obtain a lower bound on \operatorname{LSE}(\mathbf{u}) : \operatorname{LSE}(\mathbf{u})\geq\operatorname{LSE}\left(\left\{f(x)^{\top}\mu_{c}\right\}_{c\in[C]}\right)-\log\left(\frac{C^{2}\pi^{*}}{K}\operatorname{cosh}^{2}(1)\right) . Combining this with the previous bound, we derive L_{\mathrm{CE}}(f,W^{\mu})\leq\sigma+\tau L(f)+\tau\Delta+\log(C)+\log(C\pi^{*}\operatorname{cosh}^{2}(1))-\tau\Delta. (24) On the other hand, applying ( 23 ) to the term \operatorname{LSE}(\mathbf{z}^{c}) with \mathbf{z}^{c}:=\left\{{f(x)^{\top}\mu_{c}/\tau}\right\}_{c\in\mathcal{C}} introduces a factor of \log(C) , leading to \tau\operatorname{LSE}\left(\mathbf{z}^{c}\right)\geq\operatorname{LSE}\left(\mathbf{u}^{c}\right)-\log(C), where \mathbf{u}^{c}:=\left\{f(x)^{\top}\mu_{c}\right\}_{c\in\mathcal{C}} . Plugging this into the proof of lemma 9 , we obtain L_{\mathrm{CE}}(f,W^{\mu})\leq\sigma+\tau L(f)+\tau\Delta+\log(C). (25) Finally, taking the minimum over both refined bounds eq. 24 and eq. 25 and then over all linear classifiers completes the proof. ∎ Combining lemma 9 and lemma 11 , as well as rewriting with the following notation \beta(f,\sigma):={\sigma/\tau}+L(f)+\Delta completes the proof of theorem 5 . 3.3 Risk Certificate for Contrastive Zero-One Risk In the previous sections, we demonstrated that non-vacuous risk certificates can be obtained for the SimCLR loss and that the SimCLR loss acts as a surrogate loss for downstream classification. Similarly to Nozawa et al. [ 36 ] , we extend our analysis to the contrastive zero-one risk. Recall the population contrastive zero-one risk R(f) in ( 5 ). Let \widehat{R}_{S}(f) denote the empirical counterpart of R(f) . We extend both risk certificates from section 3.1 to the contrastive zero-one risk. First, we present theorem 6 corresponding to the extension of theorem 3 . Theorem 6 (Extension of theorem 3 ) . If \bar{x}_{1},\ldots,\bar{x}_{n}\sim_{iid}\mathcal{D}_{\mathcal{X}} correspond to the unlabeled samples that generate the positive pairs in S\sim\mathcal{S}^{n} , then one can express the empirical contrastive zero-one risk as R_{S}(f)=\phi\left(\bar{x}_{1},\ldots,\bar{x}_{i},\ldots,\bar{x}_{n}\right) , where the map \phi:\mathcal{X}^{n}\to\mathbb{R} satisfies the bounded difference assumption with c_{i}=\frac{2}{n} . As a consequence, for any confidence parameter \delta\in(0,1) , with probability at least 1-\delta over dataset S , for all Q : R(Q)\leq\widehat{R}_{S}(Q)+2\sqrt{\frac{\text{KL}(Q\parallel P)+\log\frac{2n}{\delta}}{2(n-1)}}. Proof. For the first part, we follow the proof from lemma 1 , with the only difference that \delta_{i}(x_{i})\leq 1 and \delta_{j}(x_{i})\leq\frac{1}{m-1} , and thus we obtain \sup_{x_{1},\ldots,x_{n},x_{i}^{\prime}\in X}\left|\Delta\phi(x_{i})\right|\leq\frac{2}{n} . For the PAC-Bayes bound, we can follow the proof of theorem 3 and use C=2 . ∎ One can also extend theorem 4 , as stated below. Theorem 7 (Extension of theorem 4 ) . Let \delta\in(0,1) be a confidence parameter. With probability at least 1-\delta over dataset S , for all Q : R(Q)\leq\inf_{\alpha\in(0,1)}\left\{\mathrm{kl}^{\text{-}1}\left(\widehat{R}_{S}(Q)+\gamma+\left(\frac{\delta}{2}\right)^{\frac{1-\alpha}{\alpha}},\frac{1}{n}\left(\mathrm{KL}\left(Q\|P\right)+\log\frac{\sqrt{n}}{\delta}\right)\right)+\gamma+\left(\frac{\delta}{2}\right)^{\frac{1}{\alpha}}\right\}, where \gamma=\sqrt{{(\log\left({2/\delta}\right))/2(m-1)\alpha}} . Proof. We follow the proof from theorem 4 : (1) the sum containing the negative samples becomes S(x,X^{-}):=\sum_{x^{\prime}\in X^{-}}\mathbb{I}_{\left\{f(x)^{\top}f(x^{+})