# Tight PAC-Bayesian Risk Certificates for Contrastive Learning

Anna van Elst, Debarghya Ghoshdastidar

► To cite this version:

Anna van Elst, Debarghya Ghoshdastidar. Tight PAC-Bayesian Risk Certificates for Contrastive Learning. SIAM Journal on Mathematics of Data Science, 2025, 7 (4), pp.1904-1927. 10.1137/24M1715283. hal-05510232

HAL Id: hal-05510232

https://hal.science/hal-05510232v1

Submitted on 13 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Tight PAC-Bayesian Risk Certificates for Contrastive Learning

Anna van Elst

LTCI, Télécom Paris, Institut Polytechnique de Paris

anna.vanelst@telecom-paris.fr

Debarghya Ghoshdastidar

School of Computation Information and Technology,

Technical University of Munich

ghoshdas@cit.tum.de

## 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*-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 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, \dots, z_n$, where each $z = (x, x^+, x_1^-, \dots, 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^-, \dots, 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, \dots, 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, \dots, 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, \dots, 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].

## 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
<table><caption>Table 1: Comparison of risk certificates for contrastive learning. A checkmark (✓) indicates that the method satisfies the specified condition, and a cross (×) 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.</caption><thead><tr><th></th><th>Non-vacuous</th><th>Sample dependence</th><th>SimCLR</th></tr></thead><tbody><tr><th scope="row">Contrastive Loss</th><td></td><td></td><td></td></tr><tr><th scope="row">Arora et al. [44]</th><td>×</td><td>×</td><td>×</td></tr><tr><th scope="row">Nozawa et al. [36]</th><td>✓</td><td>✓</td><td>×</td></tr><tr><th scope="row">Theorem 4, 3 (ours)</th><td>✓</td><td>✓</td><td>✓</td></tr><tr><th scope="row">Downstream Risk</th><td>Many -ve samples</td><td>Data augmentation</td><td>Temperature scaling</td></tr><tr><th scope="row">Arora et al. [44]</th><td>×</td><td>×</td><td>×</td></tr><tr><th scope="row">Bao et al. [3]</th><td>✓</td><td>×</td><td>×</td></tr><tr><th scope="row">Wang et al. [52]</th><td>✓</td><td>✓</td><td>×</td></tr><tr><th scope="row">Theorem 5 (ours)</th><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

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 | \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 | \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 $\mathcal{S} \sim \mathcal{S}^n$. The dataset $\mathcal{S}$ is randomly partitioned into equal-sized batches of $m$ i.i.d. positive pairs $S_{\text{batch}} \subset \mathcal{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_{\text{batch}}$ of size $m$ containing $x_i$.

**Representation function** SimCLR learns a representation function $f: \mathcal{X} \to \mathcal{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')$ is typically defined in terms of their cosine similarity, $\frac{f(x)^\top f(x')}{\|f(x)\| \|f(x')\|}$, 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')$. Let $\tau \in (0, \infty)$ be a temperature parameter. To improve readability, we use the notation $\text{sim}(x, x') = \exp\left(\frac{f(x)^\top f(x')}{\tau}\right)$ and define $\ell_{\text{cont}}(x, x^+, X) = -\log \frac{\text{sim}(x, x^+)}{\text{sim}(x, x^+) + \sum_{x' \in X} \text{sim}(x, x')}$. The empirical SimCLR loss over the dataset $\mathcal{S} \sim \mathcal{S}^n$, denoted $\hat{L}_S(f)$, is given by [7]:

$$ \frac{1}{n} \sum_{i=1}^{n} \frac{\ell_{\text{cont}}(x_i, x_i^+, \bigcup_{j \neq i} \{x_j\}) + \ell_{\text{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^-), \quad (1) $$

where $\ell(x_i, x_i^+, X_i^-)$ denotes the above symmetrization of $\ell_{\text{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_{\text{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) = \mathop{\mathbb{E}}_{(x_i, x_i^+) \stackrel{m}{\sim} \mathcal{S}^m} \left[ \frac{1}{m} \sum_{i=1}^{m} \ell(x_i, x_i^+, X_i^-) \right]. \quad (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} \to \mathbb{R}^C$ incorporates the learned representation $f: \mathcal{X} \to \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_{\text{CE}}(f, W) = \mathbb{E}_{(x,y) \sim \mathcal{D}} \left[ - \log \frac{\exp(f(x)^\top w_y)}{\sum_{i=1}^{C} \exp(f(x)^\top w_i)} \right] \quad (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, \dots, 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

$$ \text{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_{c \neq y} f(x)^\top w_c\}} \right]. \quad (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

$$ \begin{aligned} R(f) &= \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' \in X_i^-} \mathbb{I}_{\{f(x_i)^\top f(x_i^+) < f(x_i)^\top f(x')\}} \right] \quad (5) \\ &= \mathbb{P}_{(x, x^+), (x', x'^+) \sim \mathcal{S}^2} (f(x)^\top f(x^+) < f(x)^\top f(x')). \end{aligned} $$

$R(f)$ evaluates the representation $f$ in terms of how often it embeds positive pairs further than negative samples. Since the SimCLR loss can be seen as a surrogate loss for the contrastive zero-one risk, risk certificates for the contrastive zero-one risk prove to be valuable [36].

## 2.2 PAC-Bayes Theory

PAC-Bayes theory, initially developed for simple classifiers [45, 6, 15], has been extended to neural network classifiers in recent years [11, 41], to contrastive learning [36], and variational autoencoders [10]. Here, we present the essential notions of PAC-Bayes theory and outline the most common PAC-Bayes generalization bounds.

**Notation** Let $P$ denote a prior distribution and $Q$ a posterior distribution over the parameter space $W$. In PAC-Bayes theory, the distance between the prior and posterior distributions is often quantified using the Kullback-Leibler (KL) divergence, defined as $KL(Q||Q') = \int_W \log\left(\frac{dQ}{dQ'}\right) dQ$. The binary KL divergence is $kl(q||q') = q \log\left(\frac{q}{q'}\right) + (1-q) \log\left(\frac{1-q}{1-q'}\right)$, where $q, q' \in [0, 1]$—this measure quantifies the divergence between two Bernoulli distributions with parameters $q, q'$. Let $\mathcal{Z}$ denote an example space, $\mathcal{D}_\mathcal{Z}$ the distribution over $\mathcal{Z}$, and $\ell_w: \mathcal{Z} \to [0, 1]$ a loss function parameterized by $w \in W$. The risk $L: W \to [0, 1]$ is defined as $L(w) = \mathbb{E}_{z \sim \mathcal{D}_\mathcal{Z}}[\ell_w(z)]$. Here, $L(w)$ represents the expected value of $\ell_w(z)$ under the distribution $\mathcal{D}_\mathcal{Z}$. Let $n$ be an integer, and the empirical risk for a dataset $S = (z_1, \dots, z_n) \in \mathbb{Z}^n$ is defined as $\hat{L}_S(w) = \frac{1}{n} \sum_{i=1}^n \ell_w(z_i)$. Here, $\hat{L}_S(w)$ computes the average loss $\ell_w(z_i)$ over the dataset $S$.

**PAC-Bayes bounds** We extend the previously defined losses for a given weight $w$ to losses for a given distribution $Q$ over weights. Accordingly, the population loss of $Q$ is defined as $L(Q) = \int_W L(w) Q(dw)$. Similarly, the empirical loss of $Q$ over a dataset $S$ is given by $\hat{L}_S(Q) = \int_W \hat{L}_S(w) Q(dw)$. The PAC-Bayes bounds relate the population loss $L(Q)$ to the empirical loss $\hat{L}_S(Q)$ and other quantities through inequalities that hold with high probability. One of the fundamental results in PAC-Bayes theory is the PAC-Bayes-kl bound, from which various other PAC-Bayes bounds can be derived [41].

**Theorem 1 (PAC-Bayes-kl bound [41]).** For any data-free distribution $P$ over $W$ (i.e., prior), and for any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-n i.i.d. samples $S$, simultaneously for all distributions $Q$ over $W$ (i.e., posterior), the following inequality holds:

$$ \mathrm{kl}(\hat{L}_S(Q) \| L(Q)) \le \frac{\mathrm{KL}(Q \| P) + \log\left(\frac{2\sqrt{n}}{\delta}\right)}{n}. $$
The PAC-Bayes-kl bound can be employed to derive the classic PAC-Bayes bound using Pinsker's inequality $kl(\hat{p}\|p) \ge 2(p - \hat{p})^2$, as done in the following.

**Theorem 2** (classic PAC-Bayes bound [41]). For any prior $P$ over $W$, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-$n$ i.i.d. random samples $S$, simultaneously for all posterior distributions $Q$ over $W$, the following inequality holds:

$$L(Q) \le \hat{L}_S(Q) + \sqrt{\frac{\mathrm{KL}(Q\|P) + \log\left(\frac{2\sqrt{n}}{\delta}\right)}{2n}}.$$

In the context of this work, we define $L(Q) := \int_W L(f_w) Q(dw)$ as the SimCLR population loss (2) over a posterior distribution $Q$, where $f_w: \mathcal{X} \to \mathbb{S}^{d-1}$ represents the representation function parametrized by weights $w \in W$. For a sample $S \sim S^n$, the SimCLR empirical loss (1) over $Q$ is defined as $\hat{L}_S(Q) := \int_W \hat{L}_S(f_w) Q(dw)$. If $\hat{L}_S(f_w)$ was an empirical mean of i.i.d. terms, then one could directly apply the above PAC-Bayes bounds. Unfortunately, the $\ell_{\mathrm{cont}}$ terms are dependent, and more effort is needed to derive useful bounds.

# 3 Risk Certificates for Contrastive Learning

In this section, we present our main contributions: (1) using a PAC-Bayesian approach, we establish non-vacuous risk certificates for the SimCLR loss, accounting for the dependence across tuples $(x, x^+, X^-)$, (2) we derive a bound on the supervised loss tailored to SimCLR training, which incorporates data augmentation and temperature scaling, and (3) we extend our analysis to the contrastive zero-one risk and derive risk certificates.

## 3.1 Risk Certificates for Contrastive Loss

Since the SimCLR loss is computed over a batch, it induces dependence across the summand $\ell$ in (1) through $X^-$, violating the assumption required in the PAC-Bayes-kl bound (theorem 1). Since the dataset $S$ is partitioned into $p = \frac{n}{m}$ i.i.d. batches, one simple workaround is to compute the PAC-Bayes bound over these i.i.d. batches instead of the usual $n$ i.i.d. samples. For a detailed overview of the bounds, please refer to the supplementary materials. However, this weakens the risk certificate when there are few large batches. Alternatively, Nozawa et al. [36] suggest using $f$-divergence to address the non-i.i.d. characteristics, but their proposed bounds are vacuous. In this section, we present our first contribution: two PAC-Bayesian risk certificates specifically tailored to the SimCLR framework.

### 3.1.1 First PAC-Bayes certificate

Our first approach involves acknowledging that, while the SimCLR loss does not strictly meet the required independence assumption, we can view the summand in (1) as almost i.i.d. This idea can be formalized through a bounded difference assumption.

**Definition 1** (bounded difference assumption). Let $A$ be some set and $\phi: A^n \to R$. We say $\phi$ satisfies the bounded difference assumption if $\exists c_1, \dots, c_n \ge 0$ s.t. $\forall i, 1 \le i \le n$

$$\sup_{x_1, \dots, x_n, x'_i \in A} |\phi(x_1, \dots, x_i, \dots, x_n) - \phi(x_1, \dots, x'_i, \dots, x_n)| \le c_i$$

That is, if we substitute $x_i$ to $x'_i$, while keeping other $x_j$ fixed, $\phi$ changes by at most $c_i$.

We can indeed prove that the SimCLR loss (1) satisfies the bounded difference assumption when one views the loss as a function of $\bar{x}_1, \dots, \bar{x}_n \sim \mathrm{iid} \mathcal{D}_\chi$ that generates the positive pairs (see lemma 1). This assumption allows us to use McDiarmid's inequality [34]. Although one cannot directly incorporate this assumption into the proof of the PAC-Bayes-kl bound, it is possible to include McDiarmid's inequality in the proof of the PAC-Bayes bound presented in McAllester's work [32]. We present our result in the following theorem.
**Theorem 3** (Extended McAllester's PAC-Bayes Bound). Let $\delta \in (0, 1)$ be a confidence parameter and $C = 4 + (m-1) \log \frac{(m-1)+e^{2/\tau}}{m}$. With probability at least $1 - \delta$ over dataset $S \sim S^n$, for all $Q$:

$$L(Q) \le \hat{L}_S(Q) + C \sqrt{\frac{KL(Q \| P) + \log \frac{2n}{\delta}}{2(n-1)}}.$$

**Remark 2.** One can observe that theorem 3 holds for the original SimCLR loss as it satisfies the bounded difference assumption for $C = \frac{4}{\tau} + (m-1) \log \frac{2m-3+2e^{2/\tau}}{2m-1}$. The detailed proof is provided in the supplementary materials.

The rest of the subsection proves theorem 3. We first show that the SimCLR loss satisfies the bounded difference assumption.

**Lemma 1** (bounded difference assumption for the SimCLR loss). The SimCLR loss (1) can be expressed as $L_S(f) = \phi(\bar{x}_1, \dots, \bar{x}_i, \dots, \bar{x}_n)$, where $\bar{x}_1, \dots, \bar{x}_n \sim iid D_X$ are the unlabeled samples that generate the positive pairs, $x_i, x_i^+ \sim A(\cdot|\bar{x}_i)$, and $\phi: X^n \to \mathbb{R}$ is suitably defined to express $L_S(f)$. Furthermore, the map $\phi$ satisfies the bounded difference assumption with $c_i = \frac{C}{n}$ where $C = \frac{4}{\tau} + (m-1) \log \frac{(m-1)+e^{2/\tau}}{m}$.

*Proof of lemma 1.* Let $i \in [1, n]$ and $\bar{S} = \{\bar{x}_i\}_{i=1}^m$. We aim to bound the following quantity:

$$\Delta\phi_{\bar{S}}(\bar{x}_i) = \phi(\bar{x}_1, \dots, \bar{x}_i, \dots, \bar{x}_n) - \phi(\bar{x}_1, \dots, \bar{x}'_i, \dots, \bar{x}_n),$$

where the notation emphasizes that the difference $\Delta\phi_{\bar{S}}(\bar{x}_i)$ arises from perturbing the $i$-th argument of the function $\phi$, while all other arguments $\bar{x}_j$ for $j \ne i$ are held fixed.

Without loss of generality, we assume that $i \in \{1, \dots, m\}$, meaning $\bar{x}_i$ belongs to the first batch $\bar{S}_m = \{\bar{x}_i\}_{i=1}^m$. The quantity $\Delta\phi_{\bar{S}}(\bar{x}_i)$ can be split into two non-null terms:

$$\Delta\phi_{\bar{S}}(\bar{x}_i) = \frac{1}{n} \left[ \delta_{\bar{S}_m}^i(\bar{x}_i) + \sum_{\substack{j=1 \\ j \ne i}}^m \delta_{\bar{S}_m}^j(\bar{x}_i) \right],$$

where

$$\delta_{\bar{S}_m}^i(\bar{x}_i) := \ell(x_i, x_i^+, X_i^-) - \ell(x'_i, x'_i^+, X_i^-), \\ \delta_{\bar{S}_m}^j(\bar{x}_i) := \ell(x_j, x_j^+, X_j^-) - \ell(x'_j, x'_j^+, \tilde{X}_j^-),$$

and $\tilde{X}_j^-$ is the set of negative samples perturbed with $x'_i$. Since the loss $\ell$ can be written as an average of two terms that play a symmetric role, upper-bounding $\delta_{\bar{S}_m}^i(\bar{x}_i)$ reduces to upper-bounding $\ell_{cont}(x_i, x_i^+, X_i) - \ell_{cont}(x'_i, x'_i^+, X_i)$, where, for convenience, we denote $X_i = \bigcup_{j \ne i} \{x_j\}$. Using the notation $S(x, X) := \sum_{x' \in X} \mathrm{sim}(x, x')$, we have:

$$|\ell_{cont}(x_i, x_i^+, X_i) - \ell_{cont}(x'_i, x'_i^+, X_i)| = \left| \log \frac{\mathrm{sim}(x'_i, x_i^+)}{\mathrm{sim}(x_i, x_i^+)} + \log \frac{\mathrm{sim}(x_i, x_i^+) + S(x_i, X_i)}{\mathrm{sim}(x'_i, x'_i^+) + S(x'_i, X_i)} \right| \le \frac{4}{\tau},$$

as $\forall x, y, e^{-1/\tau} \le \mathrm{sim}(x, y) \le e^{1/\tau}$. Similarly, the term $\delta_j(\bar{x}_i)$ can also be written as an average of two terms. It suffices to upper-bound $\ell_{cont}(x_j, x_j^+, X_j) - \ell_{cont}(x_j, x_j^+, \tilde{X}_j)$, where $\tilde{X}_j$ is the set of $X_j$ perturbed with $x'_i$. This can be upper-bounded as:

$$|\ell_{cont}(x_j, x_j^+, X_j) - \ell_{cont}(x_j, x_j^+, \tilde{X}_j)| = \left| \log \frac{\kappa + \mathrm{sim}(x_j, x_i)}{\kappa + \mathrm{sim}(x_j, x'_i)} \right| \le \log \frac{\kappa + a}{\kappa + b},$$

where we define $\kappa = \mathrm{sim}(x_j, x_j^+) + \sum_{x' \in N_i} \mathrm{sim}(x_j, x')$ with $N_i = X_i \setminus \{x_i\}$, $a = e^{1/\tau}$, and $b = e^{-1/\tau}$. Since $a > b$, the function $x \mapsto \frac{x+a}{x+b}$ is strictly decreasing. This can be seen by computing its derivative: $f'(x) = \frac{b-a}{(x+b)^2} < 0$. Therefore, since $\kappa \ge (m-1)e^{-1/\tau}$ and the log function is increasing, we obtain

$$\log \frac{\kappa + a}{\kappa + b} \le \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_{\bar{S}_m}^i(\bar{x}_i)| \le \frac{4}{\tau}$ and $|\delta_{\bar{S}_m}^j(\bar{x}_i)| \le \log \frac{(m-1)+e^2}{m}$. This gives:

$$|\Delta\phi_{\bar{S}}(\bar{x}_i)| \le \frac{1}{n} \left( \frac{4}{\tau} + (m-1) \log \frac{(m-1)+e^2}{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 $\mathbb{E}_{S \sim S^n} [e^{(n-1)h(L_S(f)-L(f))}]$ 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| \ge x) \le 2e^{-nx^2}$, then $\mathbb{E}[e^{(n-1)X^2}] \le 2n$.

*Proof.* The proof follows from McAllester's work [33].

Assume for $x > 0$, $\mathbb{P}(|X| \ge x) \le 2e^{-nx^2}$. Then the continuous density that maximizes $\mathbb{E}[e^{(n-1)|X|^2}]$ and satisfies the previous inequality is such that $\int_x^\infty f_{|X|}(u)du = 2e^{-nx^2}$ which gives $f_{|X|}(u) = 4nue^{-nu^2}$. We derive $\mathbb{E}[e^{(n-1)|X|^2}] \le \int_0^\infty e^{(n-1)u^2} f_{|X|}(u)du = 2n$. □

**Lemma 3** (adaptation of [32], Lemma 6). Let $h: x \mapsto \frac{2x^2}{C^2}$ and $f \sim P$. We have

$$\mathbb{E}_{S \sim S^n} [e^{(n-1)h(L_S(f)-L(f))}] \le 2n.$$

*Proof.* The bounded difference assumption allows us to derive the following McDiarmid's inequality: for $\varepsilon > 0$, $\mathbb{P}_S(|L(f) - L_S(f)| \ge \varepsilon) \le 2 \exp(-\frac{2\varepsilon^2}{\sum_{i=1}^n c_i^2})$. 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}(\frac{\sqrt{2}}{C}|X| \ge x) \le 2 \exp(-nx^2)$. Invoking lemma 2, we obtain $\mathbb{E}_S[e^{(n-1)h(X)}] \le 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 $\mathbb{E}_{S \sim S^n} [e^{(n-1)h(L_S(f)-L(f))}] \le 2n$, then with probability at least $1 - \delta$ over i.i.d. dataset $S$:

$$\forall Q, \quad h(L_S(Q) - L(Q)) \le \frac{\mathrm{KL}(Q \| P) + \log \frac{2n}{\delta}}{n-1}.$$

*Proof.* Assume for a fixed $f \sim P$, $\mathbb{E}_{S \sim S^n} [e^{(n-1)h(L_S(f)-L(f))}] \le 2n$. This implies the bound $\mathbb{E}_S [\mathbb{E}_{f \sim P} [e^{(n-1)h(L_S(f)-L(f))}]] \le 2n$. Applying Markov's inequality, we obtain that with probability at least $1-\delta$ over $S$, $\mathbb{E}_{f \sim P} [e^{(n-1)h(L_S(f)-L(f))}] \le \frac{2n}{\delta}$. Next, we use a shift of measure: $\mathbb{E}_{f \sim Q} [(n-1)h(L_S(f) - L(f))] \le \mathrm{KL}(Q \| P) + \log \mathbb{E}_{f \sim P} [e^{(n-1)h(L_S(f)-L(f))}]$. Combining the previous results, with probability at least $1-\delta$ over dataset $S$:

$$\mathbb{E}_{f \sim Q} [(n-1)h(L_S(f) - L(f))] \le \mathrm{KL}(Q \| P) + \log \frac{2n}{\delta}.$$

Since $h$ is convex, applying Jensen's inequality finishes the proof:

$$(n-1)h(L_S(Q) - L(Q)) \le \mathrm{KL}(Q \| P) + \log \frac{2n}{\delta}.$$

□
Rewriting the statement of lemma 4 shows that, with probability at least 1 − δ over i.i.d. dataset S, $L(Q) \le L_S(Q) + C\sqrt{\frac{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' \in X} \mathrm{sim}(x_i, x')$ 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(Q) = \int_W L'_S(f_w) Q(dw)$ by replacing $\ell_{\mathrm{cont}}$ in (1) with an upper bound $\ell'_{\mathrm{cont}}$ as

$$ \ell_{\mathrm{cont}}(x, x^{+}, X) \le \ell'_{\mathrm{cont}}(x, x^{+}, X) = -\log \frac{\mathrm{sim}(x, x^{+})}{\mathrm{sim}(x, x^{+}) + \sum_{x' \in X} \mathrm{sim}(x, x') + 2\varepsilon}. $$

Modifying the loss by the above $\varepsilon$-factor allows us to bound it by an intermediate loss $\tilde{L}_S(f)$, defined later, using a concentration bound on the negative samples. $\tilde{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) \le \inf_{\alpha \in (0,1)} \left\{ B \cdot \mathrm{kl}^{-1} \left( \frac{1}{B} L'_S(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\}, $$

$$ \text{where } B := \frac{1}{\tau} + \log\left(me^{\frac{1}{\tau}}\right) + \varepsilon \text{ 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, $\mathrm{sim}(x, x') + \mathrm{sim}(x, x'^{+})$, 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_{x' \in X} \mathrm{sim}(x, x')$. 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}(S(x, X) - \mathbb{E}[S(x, X)] \ge \varepsilon | x) \le \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}(S(x, X) - \mathbb{E}[S(x, X)] \ge \varepsilon | x) \le \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. $\square$

Recall the SimCLR population loss $L(f)$ defined in eq. (2). Define the intermediate loss $\tilde{L}(f)$ which is a mean of i.i.d. terms obtained by replacing $\ell_{\mathrm{cont}}$ with the loss $\tilde{\ell}_{\mathrm{cont}}$ given by $\tilde{\ell}_{\mathrm{cont}}(x, x^{+}) := -\log \frac{\mathrm{sim}(x, x^{+})}{\mathrm{sim}(x, x^{+})+\mathbb{E}[S(x, X)|x]+\varepsilon}$ for a suitable $\varepsilon > 0$. We obtain the following

$$ \tilde{L}(f) := \mathbb{E}_{(x,x^{+}) \sim \mathcal{S}} \left[ \frac{\tilde{\ell}_{\mathrm{cont}}(x, x^{+}) + \tilde{\ell}_{\mathrm{cont}}(x^{+}, x)}{2} \right] = \mathbb{E}_{(x,x^{+}) \sim \mathcal{S}} \left[ \tilde{\ell}(x, x^{+}) \right]. \quad (6) $$

Using lemma 5, the following lemma shows that $L(f)$ can be upper-bounded by $\tilde{L}(f)$.
**Lemma 6** (upper-bound by an intermediate loss). Let $f \sim Q$ and $\tilde{L}(f)$ defined in eq. (6). Let $\delta \in (0, 1)$ and $B_\ell = \frac{2}{\tau} + \log m$. Then, we have

$$L(f) \le \tilde{L}(f) + B_\ell \delta. \qquad (7)$$

*Proof.* Recall that $\ell_{\text{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_{\text{cont}}(x, x^+, X)$ where $X = \bigcup_{x' \neq x} \{x'\}$. Observe that $\ell_{\text{cont}}(x, x^+, X)$ can be split into two terms using $\varepsilon$ defined in lemma 5:

$$\ell_{\text{cont}}(x, x^+, X) \le \tilde{\ell}_{\text{cont}}(x, x^+) \mathbb{I}_{\{S(x,X)<\mu(x)+\varepsilon\}} + \ell_{\text{cont}}(x, x^+, X) \mathbb{I}_{\{S(x,X)\ge\mu(x)+\varepsilon\}},$$

where $\mu(x) = \mathbb{E}[S(x, X) | x]$. Noting that $\ell_{\text{cont}}(x, x^+, X) \le B_\ell$ and $\mathbb{I}_{\{\cdot\}} \le 1$, we obtain $\ell_{\text{cont}}(x, x^+, X) \le \tilde{\ell}_{\text{cont}}(x, x^+) + B_\ell \mathbb{I}_{\{S(x,X)\ge\mu(x)+\varepsilon\}}$. We derive:

$$\ell(x, x^+, X^-) \le \tilde{\ell}(x, x^+) + B_\ell \frac{\mathbb{I}_{\{S(x,X)\ge\mu(x)+\varepsilon\}} + \mathbb{I}_{\{S(x^+,X')\ge\mu(x^+)+\varepsilon\}}}{2}, \qquad (8)$$

where $X' = \bigcup_{x' \neq x} \{x'^+\}$. Using lemma 5 and the expression of $L(f)$ combined with eq. (8),

$$L(f) \le \mathbb{E}_{(x_i, x_i^+)_{i=1}^m \sim \mathcal{S}^m} \left[ \frac{1}{m} \sum_{i=1}^m \tilde{\ell}(x_i, x_i^+) \right] + B_\ell \delta, \qquad (9)$$

which finishes the proof. $\square$

Define the empirical intermediate loss as

$$\tilde{L}_S(f) = \frac{1}{m} \sum_{i=1}^{m} \tilde{\ell}(x_i, x_i^+). \qquad (10)$$

Since $\tilde{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 $\tilde{L}(f)$ and $\tilde{L}_S(f)$ be defined as in eq. (6) and eq. (10) respectively, and define the extended losses: $\tilde{L}(Q) = \mathbb{E}_{f \sim \mathcal{Q}} [\tilde{L}(f)]$ and $\tilde{L}_S(Q) = \mathbb{E}_{f \sim \mathcal{Q}} [\tilde{L}_S(f)]$. 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} \tilde{L}(Q) \le \text{kl}^{-1} \left( \frac{1}{B} \tilde{L}_S(Q), \frac{\text{KL}(Q \| P) + \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(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:

$$\tilde{L}_S(Q) \le B\delta^{1-\alpha} + L'_S(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[A(f, x, X) | f, x] \le \delta$, then, with probability at least $1 - \delta^\alpha$ over dataset S $\sim \mathcal{S}^n$,

$$\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f \sim \mathcal{Q}} [\mathbb{I}_{\{A(f, x_i, X_i)\} | x_i, X_i^-}] \le \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[A(f, x, X) | f, x] \le \delta$. Then, using Markov's inequality, we derive:

$$
\begin{aligned}
\mathbb{P}_S \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f \sim Q} [U | x_i, X_i] > \delta^{1-\alpha} \right] &\le \frac{1}{\delta^{1-\alpha}} \mathbb{E}_S \left[ \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f \sim Q} [U | x_i, X_i] \right] \\
&= \frac{1}{\delta^{1-\alpha}} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{x_i, X_i} [\mathbb{E}_f [U | x_i, X_i]] \\
&= \frac{1}{\delta^{1-\alpha}} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f, x_i, X_i} [U] \\
&= \frac{1}{\delta^{1-\alpha}} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f, x_i} [\mathbb{E}_{X_i} [U | f, x_i]] \\
&\le \frac{1}{\delta^{1-\alpha}} \frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{f, x_i} [\delta] = \delta^{\alpha}.
\end{aligned}
$$

□

Define $A(f, x, X) := \{S(x, X) - \mu(x) \le -\varepsilon\}$. Similarly to the inequality from lemma 5, we can derive, for an augmented sample $x$, $\mathbb{P}(S(x, X) - \mu(x) \le -\varepsilon | x) \le \delta$. Next, using similar arguments to the proof of lemma lemma 6, we derive an upper bound on $\tilde{l}(x, x^+)$:

$$ \tilde{l}(x, x^+) \le B \frac{\mathbb{I}\{S(x,X)+\varepsilon \le \mu(x)\} + \mathbb{I}\{S(x^+,X')+\varepsilon \le \mu(x^+)\}}{2} + l'(x, x^+, X^-). $$

Plugging this into the intermediate empirical loss, we obtain:

$$ \tilde{L}_S(Q) \le \frac{B}{n} \sum_{i=1}^{n} \frac{1}{2} \left( \mathbb{E}_{f \sim Q} \left[ \mathbb{I}_{\{A(f, x_i, X_i)\}} | x_i, X_i \right] + \mathbb{E}_{f \sim Q} \left[ \mathbb{I}_{\{A(f, x_i^+, X_i')\}} | x_i^+, X_i' \right] \right) + L'_S(Q). $$

Invoking lemma 8, we obtain: with probability at least $1 - \delta^\alpha$ over dataset $S$:

$$ \tilde{L}_S(Q) \le B\delta^{1-\alpha} + L'_S(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 \le B$ and for $\delta_1 \in (0, 1)$, lemma 6 can be rewritten as $L(Q) \le \tilde{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 S^n$, for all $Q$ over $\mathcal{F}$,

$$ \frac{1}{B} \tilde{L}(Q) \le \text{kl}^{-1} \left( \frac{1}{B} \tilde{L}_S(Q), \frac{\text{KL}(Q \| P) + \log\left(\frac{2\sqrt{n}}{\delta_2}\right)}{n} \right) + \delta_1. $$

Using a union bound argument, and given the property of $\text{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) \le \text{kl}^{-1} \left( \frac{1}{B} L'_S(Q) + \delta_1^{1-\alpha}, \frac{\text{KL}(Q \| P) + \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_{CE}(f, W)$ in (3) and denote the class distribution by $\pi := [\mathbb{P}(Y = c)]_{c \in C}$. For all $f: \mathcal{X} \to \mathbb{S}^{d-1}$, the following inequality holds:

$$ \min_{W \in \mathbb{R}^{C \times d}} L_{CE}(f, W) \le \min \{\beta(f, \sigma), \tau\beta(f, \sigma) + \alpha\} $$

with $\beta(f, \sigma) = \frac{\sigma}{\tau} + L(f) + \Delta$ for $\Delta = \log\left(\frac{C^2\pi^*}{m-1}\cosh^2\left(\frac{1}{\tau}\right)\right)$ where $\pi^* := \max_{c \in C} \pi(c)$.

Furthermore, $\alpha$ is given by $\alpha = \log(C) + \min\{0, \log(C\pi^* \cosh^2(1)) - \tau\Delta\}$ and $\sigma = \mathbb{E}_{(x,y)}[\|f(x) - \mu_y\|_2] \le 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 \ge 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_{CE}(f, W)$ as follows:

$$ \mathbb{E}_{x,y \sim D} \left[ -\log \frac{\exp \left( f_1(x)^\top w_y^{(1)} + f_2(x)^\top w_y^{(2)} \right)}{\sum_{i=1}^C \exp \left( f_1(x)^\top w_i^{(1)} + f_2(x)^\top w_i^{(2)} \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 S^m} \left[ \frac{1}{m} \sum_{i=1}^m \ell_{\text{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} \to \mathbb{S}^{d-1}$, the following inequality holds:

$$ \min_{W \in \mathbb{R}^{C \times d}} L_{CE}(f, W) \le \frac{\sigma}{\tau} + L(f) + \Delta. $$

*Proof.* Let $\text{LSE}(\mathbf{z}) := \log\left(\sum_j \exp(z_j)\right)$ where $\mathbf{z} := \{f(x)^\top f(x')/\tau\}_{x' \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, \dots, K$. Denoting the class-conditional distribution by $\mathcal{D}_c := \mathbb{P}(X | 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\| \le 1$. We have

$$L(f) \stackrel{(a)}{\ge} - \mathbb{E}_{S \sim \mathcal{S}^m} \left[ \frac{1}{m} \sum_{i=1}^{m} \frac{f(x_i)^\top f(x_i^+)}{\tau} \right] + \mathbb{E}_{S \sim \mathcal{S}^m} \left[ \frac{1}{m} \sum_{i=1}^{m} \log \sum_{x' \in X_i} \exp \left( \frac{f(x_i)^\top f(x')}{\tau} \right) \right] \quad (11)$$

$$\stackrel{(b)}{=} -\mathbb{E}_{(x,x^+) \sim \mathcal{S}} \left[ \frac{f(x)^\top f(x^+)}{\tau} \right] + \frac{1}{m} \sum_{i=1}^{m} \mathbb{E}_{S \sim \mathcal{S}^m} [\text{LSE}(\mathbf{z})] \quad (12)$$

$$\stackrel{(c)}{\ge} - \frac{\mathbb{E}_{(x,y)} [\|f(x) - \mu_y\|_2]}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^\top \mu_y}{\tau} \right] + \mathbb{E}_x \mathbb{E}_X [\text{LSE}(\mathbf{z})] \quad (13)$$

$$\stackrel{(d)}{=} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^\top \mu_y}{\tau} \right] + \mathbb{E}_x \mathbb{E}_{\{(x'_i, y'_i)\}}_{i=1}^{K} [\text{LSE}(\mathbf{z})] \quad (14)$$

$$\stackrel{(e)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^\top \mu_y}{\tau} \right] + \mathbb{E}_x \mathbb{E}_{\{y'_i\}_{i=1}^K} [\text{LSE}(\mathbf{z}^\mu)] \quad (15)$$

where (a) relies on $\exp(f(x)^\top f(x^+)) \ge 0$, (b) follows from rewriting the expectations and using the definition of the 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$, $|f(x)^\top \frac{f(x^+)-\mu_y}{\|f(x^+)-\mu_y\|} | \le 1$ [52], (d) uses the definition of the intra-class feature deviation $\sigma := \mathbb{E}_{(x,y)} [\|f(x) - \mu_y\|_2]$, (e) uses the Jensen's inequality and the convexity of the LSE function where we define $\mathbf{z}^\mu := \{f(x)^\top \mu_{y'} / \tau\}_{y' \in Y}$ where we denote $Y = \{y'_i\}_{i=1}^K$.

Next, we need to lower-bound the quantity $\mathbb{E}_Y [\text{LSE}(\mathbf{z}^\mu)]$. 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 \le \text{LSE}(\mathbf{z}) + \text{LSE}(-\mathbf{z}) \le 2 \log (N \cosh(L^2)).$$

We apply this lemma for $N = K$ and $L = 1/\sqrt{\tau}$. We obtain

$$\mathbb{E}_Y [\text{LSE}(\mathbf{z}^\mu)] \stackrel{(a)}{\ge} -\mathbb{E}_Y [\text{LSE}(-\mathbf{z}^\mu)] + 2 \log(K) \quad (16)$$

$$\stackrel{(b)}{\ge} - \log \sum_{y' \in Y} \mathbb{E}_{y'} [\exp(-f(x)^\top \mu_{y'} / \tau)] + 2 \log(K) \quad (17)$$

$$\stackrel{(c)}{=} - \log K \sum_{c \in \mathcal{C}} \exp(-f(x)^\top \mu_c / \tau) \pi(c) + 2 \log(K) \quad (18)$$

$$\stackrel{(d)}{\ge} - \log K \pi^* \sum_{c \in \mathcal{C}} \exp(-f(x)^\top \mu_c / \tau) + 2 \log(K) \quad (19)$$

$$\stackrel{(e)}{=} - \text{LSE} \left( \left\{ -f(x)^\top \mu_c / \tau \right\}_{c \in \mathcal{C}} \right) + \log(K) - \log(\pi^*) \quad (20)$$

$$\stackrel{(f)}{\ge} \text{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^*) \quad (21)$$

$$\stackrel{(g)}{=} \text{LSE} \left( \left\{ f(x)^\top \mu_c / \tau \right\}_{c \in \mathcal{C}} \right) - \Delta, \quad (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) \le \pi^*$ for all $c \in \mathcal{C}$ and the monotonicity of $-\log$, (e) uses the definition of the LSE function, (f) is another application of lemma 10, and (g) uses the definition $\Delta := \log \left( \frac{C^2 \pi^*}{K} \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

$$L(f) \geq -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^\top \mu_y}{\tau} \right] + \mathbb{E}_x \mathrm{LSE} \left( \left\{ \frac{f(x)^\top \mu_c}{\tau} \right\}_{c \in \mathcal{C}} \right) - \Delta \\ = -\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 LSE term. The result is stated in the following lemma.

**Lemma 11.** For all $f: \mathcal{X} \to \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,$$

$$\text{where } \alpha = \log(C) + \min \{0, \log(C\pi^* \cosh^2(1)) - \tau\Delta\}.$$

*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 LSE function acts as a smooth maximum. For $N \in \mathbb{N}^*$, $\mathbf{x} \in \mathbb{R}^N$ with $\mathbf{x} = (x_1, \dots, x_N)$, and for any $t > 0$,

$$t \max_i x_i < \mathrm{LSE}(t\mathbf{x}) \leq t \max_i x_i + \log(N). \qquad (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(tx_i) \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 LSE($\mathbf{z}$) introduces a factor of $\log(K)$. With $\mathbf{u} := \{f(x)^\top f(x')\}_{x' \in \mathcal{X}}$, this yields LSE($\mathbf{z}$) $\geq \frac{1}{\tau} (\mathrm{LSE}(\mathbf{u}) - \log(K))$. Following a proof similar to lemma 9 with $L = 1$, we obtain a lower bound on LSE($\mathbf{u}$): LSE($\mathbf{u}$) $\geq$ LSE($\{f(x)^\top \mu_c\}_{c \in [C]}$) - $\log(\frac{C^2 \pi^*}{K} \cosh^2(1))$. 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^* \cosh^2(1)) - \tau \Delta. \qquad (24)$$

On the other hand, applying (23) to the term LSE($\mathbf{z}^c$) with $\mathbf{z}^c := \{f(x)^\top \mu_c / \tau\}_{c \in \mathcal{C}}$ introduces a factor of $\log(C)$, leading to $\tau \mathrm{LSE}(\mathbf{z}^c) \geq \mathrm{LSE}(\mathbf{u}^c) - \log(C)$, where $\mathbf{u}^c := \{f(x)^\top \mu_c\}_{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). \qquad (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 $\hat{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, \dots, \bar{x}_n \sim \text{iid D}_X$ correspond to the unlabeled samples that generate the positive pairs in $S \sim S^n$, then one can express the empirical contrastive zero-one risk as $R_S(f) = \phi(\bar{x}_1, \dots, \bar{x}_i, \dots, \bar{x}_n)$, 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 \hat{R}_S(Q) + 2\sqrt{\frac{KL(Q \| 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) \le 1$ and $\delta_j(x_i) \le \frac{1}{m-1}$, and thus we obtain $\sup_{x_1, \dots, x_n, x'_i \in X} |\Delta\phi(x_i)| \le \frac{2}{n}$. For the PAC-Bayes bound, we can follow the proof of theorem 3 and use $C = 2$. $\square$

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\{ \text{kl}^{-1} \left( \hat{R}_S(Q) + \gamma + \left(\frac{\delta}{2}\right)^{\frac{1-\alpha}{\alpha}}, \frac{1}{n} \left( \text{KL}(Q \| P) + \log \frac{\sqrt{n}}{\delta} \right) \right) + \gamma + \left(\frac{\delta}{2}\right)^{\frac{1}{\alpha}} \right\},$$

where $\gamma = \sqrt{(\log(2/\delta))/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' \in X^-} \mathbb{I}_{\{f(x)^\top f(x^+) < f(x)^\top f(x')\}}$; (2) since $\mathbb{I}_{\{\cdot\}} \le 1$, we obtain $\varepsilon = \sqrt{((m-1)\log(2/\delta))/2}$ and we have $B_\ell = 1$; (3) the upper bound on the contrastive zero-one population risk by an intermediate loss becomes $R(Q) \le \tilde{R}(Q) + \frac{\varepsilon}{m-1} + \frac{\delta}{2}$ and the PAC-Bayes bound is computed using $B = 1$; (4) we set $\gamma = \frac{\varepsilon}{m-1}$ and take the infimum over $\alpha$. $\square$

# 4 Experiments

In this section, we describe the experimental setup and empirically demonstrate that our risk certificates improved upon previous risk certificates through experiments on the CIFAR-10 dataset. For a comprehensive overview of all applicable previous bounds, please refer to the supplementary materials. The code for our experiments is available in PyTorch [39]. Experimental results on the MNIST dataset and additional experimental details are available in the supplementary materials.

**Datasets and models** We use two popular benchmarks: (1) CIFAR-10, which consists of 50,000 training images and 10,000 test images [27], and (2) MNIST, which consists of 60,000 training images and 10,000 test images [29], as provided in torchvision [31]. The images are preprocessed by normalizing all pixels per channel based on the training data. Data augmentation includes random cropping, resizing (with random flipping), and color distortions, as detailed in Appendix H [7]. We employ a 7-layer convolutional neural network (CNN) with max-pooling every two layers for CIFAR-10 experiments and a 3-layer CNN for MNIST experiments. We use a 2-layer MLP projection head to project to a 128-dimensional latent space, with a feature dimensionality of 2048 for CIFAR-10 and 512 for MNIST. ReLU activations are used in each hidden layer. The mean parameters $\mu_0$ of the prior are initialized randomly from a truncated centered Gaussian distribution with a standard deviation of $1/\sqrt{n_{in}}$, where $n_{in}$ is the dimension of the inputs to a particular layer, truncating at $\pm 2$ standard deviations [40]. The prior distribution scale (standard deviation $\sigma_0$) is selected from $\{0.01, 0.05, 0.1\}$.

**PAC-Bayes Learning** The learning and certification strategy involves three steps: (1) choose or learn a prior from a subset of the dataset; (2) learn a posterior on the entire training dataset; (3) evaluate the risk certificate for the posterior on a subset of the dataset independent of the prior. We experiment with two types of priors: informed and random. The informed prior is learned using a
subset of the training dataset via empirical risk minimization or PAC-Bayes objective minimization. The posterior is initialized to the prior and learned using the entire training dataset by PAC-Bayes objective minimization. We use the PAC-Bayes with Backprop (PBB) procedure [41] and the following $f_{\text{classic}}$ objective : $f_{\text{classic}}(Q) = (1/B)\hat{L}_S(Q) + \sqrt{(\eta\text{KL}(Q\|P) + \log(\sqrt{n}/\delta))/2n}$, where $\eta$ in $[0, 1]$ is a coefficient introduced to control the influence of the KL term in the training objective, called the KL penalty. We use a KL penalty term of $10^{-6}$ for learning the prior and no penalty term for learning the posterior. We use SGD with momentum as optimizer and we perform a grid search for momentum values in $\{0.8, 0.85, 0.90, 0.95\}$ and learning rates in $\{0.1, 0.5, 1.0, 1.5\}$. Training was conducted for 100 epochs, and we selected the hyperparameters that give the best risk certificates. We experiment with different temperatures selected $\{0.2, 0.5, 0.7, 1\}$. Unless otherwise specified, experiments are run using a probabilistic prior with the simplified SimCLR loss, a batch size of $m = 250$, and 80% of the data for training the prior.

**Numerical Risk Certificates** Since $\hat{L}_S(Q)$ is intractable, the final risk certificates are computed using Monte Carlo weight sampling. Specifically, we approximate $\hat{L}_S(Q)$ using the empirical measure $\hat{Q}_p = \sum_{j=1}^p \delta_{W_j}$, where $W_1, \dots, W_p \sim Q$ are i.i.d. samples. We compute all risk certificates with $\delta = 0.04$, and $p = 100$ Monte Carlo model samples. We report the risk certificates for both the contrastive loss and the contrastive zero-one risk using theorem 3 and theorem 4 for the contrastive loss, and theorem 6 and theorem 7 for the zero-one risk. To find the best value of $\alpha$ for theorem 4 and theorem 7, we perform a grid search over $\{0.1, 0.2, 0.3, 0.4, 0.5\}$. We observe that $\alpha = 0.4$ provides the tightest risk certificates. Our risk certificates are compared with existing ones, as detailed in table 2 and the supplementary materials.

**Linear Evaluation** We assess the quality of the learned representations through linear evaluation [7]: we report the cross-entropy loss and top-1 accuracy of linear classifiers trained on features either before or after the projection head. The classifiers are trained for 20 epochs on the image classification task ($C = 10$) using the Adam optimizer with a learning rate of 0.01. Finally, we report the bounds on the downstream classification loss derived from theorem 5 and compare it with the state of the art [3].

<table><caption>Table 2: Comparison of risk certificates for the SimCLR loss and contrastive zero-one risk using different PAC-Bayes bounds for varying temperature values on CIFAR-10. *kl bound (iid)* refers to the standard PAC-Bayes-kl bound computed over i.i.d. batches (see section 3.1), *Catoni's bound (iid)* refers to Catoni's PAC-Bayes bound computed over i.i.d. batches [36], *Classic bound (iid)* refers to the classic PAC-Bayes bound computed over i.i.d. batches, and *Nozawa et al.* refers to the PAC-Bayes bound based on *f-divergence*. Although Nozawa et al.'s bound uses $\chi^2$ divergence, we use KL divergence, which already results in vacuous bounds and would not improve with $\chi^2$, since $\text{KL}(P\|Q) \le \chi^2(P\|Q)$. We report test losses and observe that our bounds are remarkably tight. We also report the complexity term, KL/n, where KL represents the Kullback-Leibler divergence between the prior and posterior distributions, and n is the dataset size used to compute the risk certificate.</caption><thead><tr><th rowspan="2"></th><th rowspan="2"></th><th colspan="4">SimCLR Loss</th><th colspan="4">Contrastive 0-1 Risk</th></tr><tr><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th></tr></thead><tbody><tr><td></td><td>Test Loss</td><td>4.945</td><td>4.640</td><td>4.257</td><td>2.7076</td><td>0.0601</td><td>0.0433</td><td>0.0324</td><td>0.0199</td></tr><tr><td rowspan="5">Risk Certificate</td><td>kl bound (iid)</td><td>7.164</td><td>7.674</td><td>8.246</td><td>9.954</td><td>0.497</td><td>0.488</td><td>0.47</td><td>0.432</td></tr><tr><td>Catoni's bound (iid)</td><td>7.095</td><td>7.556</td><td>7.959</td><td>9.446</td><td>0.469</td><td>0.466</td><td>0.435</td><td>0.417</td></tr><tr><td>Classic bound (iid)</td><td>8.475</td><td>8.698</td><td>8.910</td><td>10.166</td><td>0.542</td><td>0.540</td><td>0.530</td><td>0.505</td></tr><tr><td>f-divergence [36]</td><td>27.03</td><td>30.138</td><td>33.27</td><td>48.472</td><td>3.009</td><td>3.099</td><td>3.139</td><td>2.973</td></tr><tr><td>Th. 4 (ours)</td><td>5.537</td><td>5.491</td><td><strong>5.492</strong></td><td><strong>6.223</strong></td><td>0.367</td><td>0.353</td><td>0.342</td><td>0.329</td></tr><tr><td></td><td>Th. 3 (ours)</td><td><strong>5.203</strong></td><td><strong>5.328</strong></td><td>6.269</td><td>43.779</td><td><strong>0.129</strong></td><td><strong>0.117</strong></td><td><strong>0.107</strong></td><td><strong>0.093</strong></td></tr><tr><td colspan="2">KL/n</td><td>0.0013</td><td>0.0014</td><td>0.0014</td><td>0.0013</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>
<table><thead><tr><th></th><th></th><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th></tr></thead><tbody><tr><td></td><td>Bao et al. [3]</td><td><strong>3.2720</strong></td><td><strong>4.0274</strong></td><td>5.3015</td><td>12.588</td></tr><tr><td></td><td>Th. 5 (ours)</td><td><strong>3.2720</strong></td><td><strong>4.0274</strong></td><td><strong>4.9533</strong></td><td><strong>4.6079</strong></td></tr><tr><td rowspan="2">Proj.</td><td>Sup. Loss</td><td>1.903</td><td>1.837</td><td>1.7971</td><td>1.7547</td></tr><tr><td>top-1</td><td>0.4868</td><td>0.5710</td><td>0.6205</td><td>0.6677</td></tr><tr><td></td><td>Sup. Loss</td><td>1.765</td><td>1.718</td><td>1.705</td><td>1.699</td></tr><tr><td></td><td>top-1</td><td>0.6350</td><td>0.6939</td><td>0.7102</td><td>0.7278</td></tr></tbody></table>

Table 3: Comparison of upper bounds on downstream classification loss on CIFAR-10. We compare the original bound from Bao et al. with our refined bound (theorem 5). The supervised loss of the linear classifier trained on the projected features is reported, as it is directly related to the theoretical upper bound. Additionally, we report the supervised loss of the linear classifier trained on the features after removing the projection head. We empirically observe that the supervised loss of a linear classifier trained on the full features (without projection) is consistently lower than the loss of a linear classifier trained on the projected features, aligning with previous findings [7]. For reference, we also include top-1 accuracy.

**Results** Table 2 demonstrates that our proposed risk certificates for the SimCLR loss are non-vacuous and significantly outperform existing risk certificates on CIFAR-10, closely aligning with the corresponding test losses. Interestingly, theorem 4 yields tighter certificates for $\tau \le 0.5$, while theorem 3 is more effective for $\tau > 0.5$. We also observe that Catoni's bound is significantly tighter than the PAC-Bayes-kl bound, which is consistent with its known advantage when KL/n is large [58]. Unsurprisingly, the classic PAC-Bayes bound is looser than both of these bounds. Additionally, Table 3 shows that theorem 5 improves upon the bound from Bao et al., which results in exponential growth when $\tau \le 0.5$ [3]. Moreover, models trained using PAC-Bayes by Backprop achieve competitive top1 accuracy. Table 2 further illustrates that our risk certificates for contrastive zero-one risk are notably tight, surpassing existing certificates. Additionally, we observe that theorem 7 consistently outperforms theorem 6. Overall, our risk certificates are competitive, even for low temperatures. PAC-Bayes learning in models with a large number of parameters remains challenging and warrants further investigation (most studies focus on 2 or 3 hidden layers).

# 5 Discussion and Future Work

We have presented novel PAC-Bayesian risk certificates tailored for the SimCLR framework. Our experiments on CIFAR-10 and MNIST show that our bounds yield non-vacuous risk certificates and significantly outperform previous ones.

**Bounding techniques** theorem 4 and theorem 7 rely on concentration bounds to apply the PAC-Bayes bound-kl in an i.i.d. setting. Although the PAC-Bayes-kl bound was selected for its tightness, any bound that respects our proof's assumptions could be applicable. Moreover, theorem 3 and theorem 6 were obtained using McDiarmid's inequality, integrated into McAllester's PAC-Bayes bound. Since this variant is known to be less tight than the kl bound or Catoni's bound, it would be interesting to explore whether McDiarmid's inequality can be incorporated into these tighter bounds.

**Extension to other (non-i.i.d.) losses** While this paper primarily focuses on contrastive learning using the SimCLR framework, the approaches we propose to address the non-i.i.d. characteristics of the SimCLR loss can be readily applied to other loss presenting similar dependence, such as ranking losses [8], Barlow Twins [56] or VICReg [5]. While our non-i.i.d. McAllester PAC-Bayes bound (theorem 3) requires only a bounded difference assumption, the non-i.i.d. PAC-Bayes-kl bound (theorem 4), while more opaque, requires only a Hoeffding's assumption on the dependent terms.
**Impact of temperature scaling and projection head**
Temperature scaling in the SimCLR loss remains challenging as the scaling constant loosens the PAC-Bayes bounds, suggesting the need for more adapted PAC-Bayes bounds for this type of loss. Regarding the bound on the downstream classification loss, our approach better handles smaller temperatures than previous bounds, though it still struggles to perfectly align with downstream classification losses at low temperatures.

Regarding projection head, we empirically observe that classification loss is lower when features are used without a projection head compared to with one, yet the theoretical role of the projection head cannot fully be understood with our downstream classification bound. In this work, we proposed an approach to integrate a simple projection head into our bound, and it would be interesting to link this with [26] that suggests a fixed low-rank diagonal projector might suffice instead of a trainable projection head.

**PAC-Bayes learning**
Our models trained with PAC-Bayes by Backprop achieve accuracy competitive with [7] despite using a much smaller model (7-layer CNN vs. 50-layer CNN) and training for fewer epochs (100 vs. 500). Although this paper focuses on deriving better risk certificates rather than improving the PAC-Bayes learning algorithm, there is a need to extend the PAC-Bayes paradigm to large-scale neural networks, such as ResNet50.
Acknowledgments

We would like to express our gratitude to Maximilian Fleissner for providing Lemma 3.14 and for his careful reading of the original manuscript. We also sincerely thank the SIMODS reviewers for their valuable comments and constructive feedback, which greatly improved the quality of this work.

References

[1] P. Alquier and B. Guedj. Simpler pac-bayesian bounds for hostile data. *Machine Learning*, 107(5): 887-902, 2018.

[2] M. Assran, Q. Duval, I. Misra, P. Bojanowski, P. Vincent, M. G. Rabbat, Y. LeCun, and N. Ballas. Self-supervised learning from images with a joint-embedding predictive architecture. In *IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023*, pages 15619-15629. IEEE, 2023.

[3] H. Bao, Y. Nagano, and K. Nozawa. On the surrogate gap between contrastive and supervised losses. In *International Conference on Machine Learning*, pages 1585-1606. PMLR, 2022.

[4] A. Bardes, J. Ponce, and Y. LeCun. Vicreg: Variance-invariance-covariance regularization for self-supervised learning. *arXiv preprint arXiv:2105.04906*, 2021.

[5] V. Cabannes, B. T. Kiani, R. Balestriero, Y. LeCun, and A. Bietti. The SSL interplay: Augmentations, inductive bias, and generalization. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, *International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA*, volume 202 of *Proceedings of Machine Learning Research*, pages 3252-3298. PMLR, 2023.

[6] O. Catoni. Pac-bayesian supervised classification: the thermodynamics of statistical learning. *arXiv preprint arXiv:0712.0248*, 2007.

[7] T. Chen, S. Kornblith, M. Norouzi, and G. Hinton. A simple framework for contrastive learning of visual representations. In *International conference on machine learning*, pages 1597-1607. PMLR, 2020.

[8] W. Chen, T.-Y. Liu, Y. Lan, Z.-M. Ma, and H. Li. Ranking measures and loss functions in learning to rank. *Advances in Neural Information Processing Systems*, 22, 2009.

[9] X. Chen and K. He. Exploring simple siamese representation learning. In *IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2021, virtual, June 19-25, 2021*, pages 15750-15758. Computer Vision Foundation / IEEE, 2021.

[10] B.-E. Chérief-Abdellatif, Y. Shi, A. Doucet, and B. Guedj. On pac-bayesian reconstruction guarantees for vaes. In *International conference on artificial intelligence and statistics*, pages 3066-3079. PMLR, 2022.

[11] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In *Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence (UAI)*, 2017.

[12] B. Elizalde, S. Deshmukh, M. Al Ismail, and H. Wang. Clap learning audio concepts from natural language supervision. In *ICASSP 2023-2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, pages 1-5. IEEE, 2023.

[13] A. Farid and A. Majumdar. Generalization bounds for meta-learning via pac-bayes and uniform stability. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual*, pages 2173-2186, 2021.
[14] T. Gao, X. Yao, and D. Chen. Simcse: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:2104.08821, 2021.

[15] P. Germain, A. Lacasse, F. Laviolette, and M. Marchand. Pac-bayesian learning of linear classifiers. In *Proceedings of the 26th Annual International Conference on Machine Learning*, pages 353–360, 2009.

[16] F. Graf, C. D. Hofer, M. Niethammer, and R. Kwitt. Dissecting supervised contrastive learning. In M. Meila and T. Zhang, editors, *Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event*, volume 139 of *Proceedings of Machine Learning Research*, pages 3821–3830. PMLR, 2021.

[17] J. Grill, F. Strub, F. Altché, C. Tallec, P. H. Richemond, E. Buchatskaya, C. Doersch, B. Á. Pires, Z. Guo, M. G. Azar, B. Piot, K. Kavukcuoglu, R. Munos, and M. Valko. Bootstrap your own latent - A new approach to self-supervised learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020.

[18] M. Gutmann and A. Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In *Proceedings of the thirteenth international conference on artificial intelligence and statistics*, pages 297–304. JMLR Workshop and Conference Proceedings, 2010.

[19] J. Z. HaoChen and T. Ma. A theoretical study of inductive biases in contrastive learning. In *The Eleventh International Conference on Learning Representations (ICLR)*, 2023.

[20] J. Z. HaoChen, C. Wei, A. Gaidon, and T. Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. *Advances in Neural Information Processing Systems*, 34:5000–5011, 2021.

[21] J. Z. HaoChen, C. Wei, A. Kumar, and T. Ma. Beyond separability: Analyzing the linear transferability of contrastive representations to related subpopulations. In *NeurIPS*, 2022.

[22] K. He, H. Fan, Y. Wu, S. Xie, and R. Girshick. Momentum contrast for unsupervised visual representation learning. In *Proceedings of the IEEE/CVF conference on computer vision and pattern recognition*, pages 9729–9738, 2020.

[23] W. Hoeffding. Probability inequalities for sums of bounded random variables. *The collected works of Wassily Hoeffding*, pages 409–426, 1994.

[24] H. Hu, X. Wang, Y. Zhang, Q. Chen, and Q. Guan. A comprehensive survey on contrastive learning. *Neurocomputing*, page 128645, 2024.

[25] W. Huang, M. Yi, X. Zhao, and Z. Jiang. Towards the generalization of contrastive self-supervised learning. In *The Eleventh International Conference on Learning Representations (ICLR)*, 2023.

[26] L. Jing, P. Vincent, Y. LeCun, and Y. Tian. Understanding Dimensional Collapse in Contrastive Self-supervised Learning. In *Proceedings of the 10th International Conference on Learning Representations (ICLR)*, 2022.

[27] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009. URL https://www.cs.toronto.edu/~kriz/cifar.html.

[28] P. H. Le-Khac, G. Healy, and A. F. Smeaton. Contrastive representation learning: A framework and review. *Ieee Access*, 8:193907–193934, 2020.

[29] Y. LeCun, C. Cortes, and C. J. C. Burges. MNIST handwritten digit database, 2010. URL http://yann.lecun.com/exdb/mnist/.
[30] Y. Lei, T. Yang, Y. Ying, and D. Zhou. Generalization analysis for contrastive representation learning. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, *International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA*, volume 202 of *Proceedings of Machine Learning Research*, pages 19200–19227. PMLR, 2023.

[31] S. Marcel and Y. Rodriguez. Torchvision the machine-vision package of torch. In *Proceedings of the 18th ACM international conference on Multimedia*, pages 1485–1488, 2010.

[32] D. McAllester. Simplified pac-bayesian margin bounds. In *Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings*, pages 203–215. Springer, 2003.

[33] D. A. McAllester. Pac-bayesian stochastic model selection. *Machine Learning*, 51(1):5–21, 2003.

[34] C. McDiarmid et al. On the method of bounded differences. *Surveys in combinatorics*, 141(1):148–188, 1989.

[35] K. Nozawa and I. Sato. Understanding negative samples in instance discriminative self-supervised representation learning. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, *Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual*, pages 5784–5797, 2021.

[36] K. Nozawa, P. Germain, and B. Guedj. Pac-bayesian contrastive unsupervised representation learning. In *Conference on Uncertainty in Artificial Intelligence*, pages 21–30. PMLR, 2020.

[37] A. v. d. Oord, Y. Li, and O. Vinyals. Representation learning with contrastive predictive coding. *arXiv preprint arXiv:1807.03748*, 2018.

[38] A. Parulekar, L. Collins, K. Shanmugam, A. Mokhtari, and S. Shakkottai. Infonce loss provably learns cluster-preserving representations. In G. Neu and L. Rosasco, editors, *The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India*, volume 195 of *Proceedings of Machine Learning Research*, pages 1914–1961. PMLR, 2023.

[39] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch, 2017.

[40] M. Perez-Ortiz, O. Rivasplata, B. Guedj, M. Gleeson, J. Zhang, J. Shawe-Taylor, M. Bober, and J. Kittler. Learning pac-bayes priors for probabilistic neural networks. *arXiv preprint arXiv:2109.10304*, 2021.

[41] M. Perez-Ortiz, O. Rivasplata, J. Shawe-Taylor, and C. Szepesvári. Tighter risk certificates for neural networks. *Journal of Machine Learning Research*, 22(227):1–40, 2021.

[42] J. Qiu, Q. Chen, Y. Dong, J. Zhang, H. Yang, M. Ding, K. Wang, and J. Tang. Gcc: Graph contrastive coding for graph neural network pre-training. In *Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining*, pages 1150–1160, 2020.

[43] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark, et al. Learning transferable visual models from natural language supervision. In *International conference on machine learning*, pages 8748–8763. PmLR, 2021.

[44] N. Saunshi, O. Plevrakis, S. Arora, M. Khodak, and H. Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In *International Conference on Machine Learning*, pages 5628–5637. PMLR, 2019.

[45] M. Seeger. Pac-bayesian generalisation error bounds for gaussian process classification. *Journal of machine learning research*, 3(Oct):233–269, 2002.
[46] R. Shwartz-Ziv and Y. LeCun. To compress or not to compress - self-supervised learning and information theory: A review. *Entropy*, 26(3):252, 2024.

[47] R. Shwartz-Ziv, R. Balestiero, K. Kawaguchi, T. G. J. Rudner, and Y. LeCun. An information-theoretic perspective on variance-invariance-covariance regularization. *CoRR*, abs/2303.00633, 2023.

[48] K. Sohn. Improved deep metric learning with multi-class n-pair loss objective. *Advances in neural information processing systems*, 29, 2016.

[49] Z. Tan, Y. Zhang, J. Yang, and Y. Yuan. Contrastive learning is spectral clustering on similarity graph. In *The Twelfth International Conference on Learning Representations (ICLR)*, 2024.

[50] C. Tosh, A. Krishnamurthy, and D. Hsu. Contrastive learning, multi-view redundancy, and linear models. In V. Feldman, K. Ligett, and S. Sabato, editors, *Algorithmic Learning Theory*, volume 132 of *Proceedings of Machine Learning Research*, pages 1179–1206. PMLR, 2021.

[51] Y. H. Tsai, Y. Wu, R. Salakhutdinov, and L. Morency. Self-supervised learning from a multi-view perspective. In *9th International Conference on Learning Representations (ICLR)*, 2021.

[52] Y. Wang, Q. Zhang, Y. Wang, J. Yang, and Z. Lin. Chaos is a ladder: A new theoretical understanding of contrastive learning via augmentation overlap. In *Proceedings of the 10th International Conference on Learning Representations (ICLR)*, 2022.

[53] C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self-training with deep networks on unlabeled data. In *9th International Conference on Learning Representations (ICLR)*, 2021.

[54] Z. Wu, Y. Xiong, S. X. Yu, and D. Lin. Unsupervised feature learning via non-parametric instance discrimination. In *Proceedings of the IEEE conference on computer vision and pattern recognition*, pages 3733–3742, 2018.

[55] J. Yu, X. Xia, T. Chen, L. Cui, N. Q. V. Hung, and H. Yin. Ximgcl: Towards extremely simple graph contrastive learning for recommendation. *IEEE Transactions on Knowledge and Data Engineering*, 36(2):913–926, 2023.

[56] J. Zbontar, L. Jing, I. Misra, Y. LeCun, and S. Deny. Barlow twins: Self-supervised learning via redundancy reduction. In *International conference on machine learning*, pages 12310–12320. PMLR, 2021.

[57] Y. Zhang, H. Jiang, Y. Miura, C. D. Manning, and C. P. Langlotz. Contrastive learning of medical visual representations from paired images and text. In *Machine learning for healthcare conference*, pages 2–25. PMLR, 2022.

[58] W. Zhou, V. Veitch, M. Austern, R. P. Adams, and P. Orbanz. Non-vacuous generalization bounds at the imagenet scale: a pac-bayesian compression approach. In *ICLR*, 2019.

[59] X. Zou and W. Liu. Generalization bounds for adversarial contrastive learning. *J. Mach. Learn. Res.*, 24:114:1–114:54, 2023.

# A Summary of previous PAC-Bayes Bounds

## A.1 Applicable to the SimCLR loss

Below is the list of previous PAC-Bayes bounds applicable to the SimCLR loss. Recall that *n* denotes the size of the dataset *S* and *m* the batch size. We call *U* the dataset of *p* = *n*/*m* i.i.d. batches partitioned from *S*.
**Proposition 1** (Classic PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$ \frac{1}{B_{\ell}} L(Q) \leq \frac{1}{B_{\ell}} \hat{L}_{S}(Q) + \sqrt{m \frac{KL(Q \parallel \mathcal{P}) + \log \frac{2\sqrt{n}}{\delta\sqrt{m}}}{2n}} $$

*Proof.* We apply the classic PAC-Bayes bound over U [41], since the bound would not hold over the dataset S. This implies that, instead of using the quantity n in the bound, we use the quantity $p = \frac{n}{m}$ corresponding to the number of batches. □

**Proposition 2** (kl-PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$ \frac{1}{B_{\ell}} L(Q) \leq \text{kl}^{-1} \left( \frac{1}{B_{\ell}} \hat{L}_{S}(Q), m \frac{KL(Q \parallel \mathcal{P}) + \log \frac{2\sqrt{n}}{\delta\sqrt{m}}}{n} \right) $$

*Proof.* Similarly, we apply the kl-PAC-Bayes bound over U [41]. □

**Proposition 3** (Catoni's PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$ \frac{1}{B_{\ell}} L(Q) \leq \inf_{\lambda > 0} \left\{ \frac{1 - \exp\left(-\frac{\lambda}{B_{\ell}}\hat{L}_{S}(Q) - m\frac{KL(Q \parallel \mathcal{P}) + \log \frac{1}{\delta}}{n}\right)}{1 - \exp(-\lambda)} \right\} $$

*Proof.* Similarly, we apply Catoni's bound over U [6]. □

**Proposition 4** (f-divergence PAC-Bayes Bound). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$ \frac{1}{B_{\ell}} L(Q) \leq \frac{1}{B_{\ell}} \hat{L}_{S}(Q) + \sqrt{\frac{m-1}{n\delta}} (\chi^2(Q \parallel P) + 1) $$

*Proof.* We adapt the PAC-Bayes f-divergence to the SimCLR loss [36]. We have:

$$ L(Q) \leq L_{S}(Q) + \sqrt{\frac{M_{2}}{\delta}} (\chi^{2}(Q \parallel P) + 1), $$

where $M_2 = \mathbb{E}_{\mathbf{f} \sim \mathcal{P}} \mathbb{E}_{S \sim \mathcal{S}^m} (|L(\mathbf{f}) - \hat{L}_S(\mathbf{f})|^2)$.

$M_2$ can be upper-bounded using the following covariance:

$$ \text{Cov}(\ell(\mathbf{z}_i), \ell(\mathbf{z}_j)) \begin{cases} \leq B_{\ell}^2 & \text{if } i, j \text{ are in the same batch} \\ = 0 & \text{otherwise} \end{cases} $$

where $\ell(\mathbf{z}_i) = \ell_{cont}((x_i, x_i^+), X_i^-)$. Indeed, we have [1]:

$$ \mathbb{E} \left[ \left( \frac{1}{n} \sum_{i=1}^{n} \ell(\mathbf{z}_i) - \mathbb{E}_{X_i^-} [\ell(\mathbf{z}_i)] \right)^2 \right] = \frac{1}{n^2} \sum_{i=1}^{n} \sum_{j=1}^{n} \text{Cov} [\ell(\mathbf{z}_i), \ell(\mathbf{z}_j)] $$

which implies for the simplified SimCLR loss:

$$ M_2 \leq \frac{1}{n^2} \sum_{i=1}^{n} (m-1) B_{\ell}^2 = \frac{m-1}{n} B_{\ell}^2. $$

□
## A.2 Applicable to the contrastive zero-one risk

**Proposition 5** (Classic PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$R(Q) \leq \hat{R}_S(Q) + \sqrt{m \frac{KL(Q \parallel \mathcal{P}) + \log \frac{2\sqrt{n}}{\delta\sqrt{m}}}{2n}}$$

**Proposition 6** (kl-PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$R(Q) \leq \text{kl}^{-1} \left( \hat{R}_S(Q), m \frac{KL(Q \parallel \mathcal{P}) + \log \frac{2\sqrt{n}}{\delta\sqrt{m}}}{n} \right)$$

**Proposition 7** (Catoni's PAC-Bayes Bound over i.i.d. batches). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$R(Q) \leq \inf_{\lambda > 0} \left\{ \frac{1 - \exp\left(-\lambda \hat{R}_S(Q) - m \frac{KL(Q \parallel \mathcal{P}) + \log \frac{1}{\delta}}{n}\right)}{1 - \exp(-\lambda)} \right\}$$

**Proposition 8** (f-divergence PAC-Bayes Bound). For any prior P over W, and any $\delta \in (0, 1)$, with a probability of at least $1 - \delta$ over size-p i.i.d. random batches U, simultaneously for all posterior distributions Q over W, the following inequality holds:

$$R(Q) \leq \hat{R}_S(Q) + \sqrt{\frac{m-1}{n\delta}(\chi^2(Q \parallel P) + 1)}$$

# B Additional Experimental Details

## B.1 Data Pre-processing Details

For data augmentation, we apply random cropping, random horizontal flip with probability 0.5, color jittering with strength 0.5 and probability 0.8, and color dropping, leaving out gaussian blur [7, 31]. We then normalize the augmented images per channel using the mean and standard deviation of the training data.

## B.2 Computing Infrastructure

The experiments are run using three different resource types:

* CPU + Nvidia Tesla P100 (16GB, No Tensor Cores)

* CPU + Nvidia Tesla V100 (16GB, Tensor Cores)

* CPU + Nvidia Ampere A100 (20G MIG, Ampere Tensor Cores)

We use a small memory (40GB) and the Nvidia NGC container image Pytorch 2.4.0.

## B.3 Experiments on MNIST

In this section, we present the results of the experiments on MNIST, as detailed in section B.3, section B.3, and section B.3.
<table><caption>Table 4: Comparison of risk certificates for the SimCLR loss on the MNIST dataset.</caption><thead><tr><th></th><th colspan="4">SimCLR Loss</th></tr><tr><th></th><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th></tr></thead><tbody><tr><th>Test Loss</th><td>4.9318</td><td>4.6575</td><td>4.3130</td><td>2.8574</td></tr><tr><th>Risk Certificate</th><td></td><td></td><td></td><td></td></tr><tr><th>kl bound (iid)</th><td>6.97</td><td>7.008</td><td>7.258</td><td>8.108</td></tr><tr><th>Catoni's bound (iid)</th><td>6.875</td><td>6.848</td><td>7.007</td><td>7.618</td></tr><tr><th>Classic bound (iid)</th><td>7.904</td><td>7.426</td><td>7.475</td><td>8.324</td></tr><tr><th>Nozawa et al.</th><td>23.469</td><td>20.448</td><td>22.275</td><td>35.05</td></tr><tr><th>Th. 1 (ours)</th><td>5.465</td><td>5.383</td><td>5.368</td><td>6.011</td></tr><tr><th>Th. 2 (ours)</th><td>5.099</td><td>5.093</td><td>5.729</td><td>36.033</td></tr><tr><th>KL / n</th><td>0.0009</td><td>0.0005</td><td>0.0005</td><td>0.0006</td></tr></tbody></table>

<table><caption>Table 5: Comparison of risk certificates for the contrastive zero-one risk on the MNIST dataset.</caption><thead><tr><th></th><th colspan="4">Contrastive 0-1 Risk</th></tr><tr><th></th><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th></tr></thead><tbody><tr><th>Test Loss</th><td>0.0571</td><td>0.0529</td><td>0.0478</td><td>0.0357</td></tr><tr><th>Risk Certificate</th><td></td><td></td><td></td><td></td></tr><tr><th>kl bound (iid)</th><td>0.408</td><td>0.327</td><td>0.324</td><td>0.319</td></tr><tr><th>Catoni's bound (iid)</th><td>0.419</td><td>0.333</td><td>0.331</td><td>0.309</td></tr><tr><th>Classic bound (iid)</th><td>0.466</td><td>0.396</td><td>0.394</td><td>0.399</td></tr><tr><th>Nozawa et al.</th><td>2.535</td><td>1.95</td><td>2.097</td><td>2.097</td></tr><tr><th>Th. 4 (ours)</th><td>0.356</td><td>0.347</td><td>0.343</td><td>0.333</td></tr><tr><th>Th. 5 (ours)</th><td>0.113</td><td>0.101</td><td>0.098</td><td>0.088</td></tr></tbody></table>

## C KL Divergence

The KL divergence between one-dimensional Gaussian distributions is given by: KL(Gauss($\mu_1, b_1$) || Gauss($\mu_0, b_0$)) = $\frac{1}{2}(\log(\frac{b_0}{b_1}) + \frac{(\mu_1 - \mu_0)^2}{b_0} + \frac{b_1}{b_0} - 1)$ For multi-dimensional Gaussian distributions with diagonal covariance matrices, the KL divergence is the sum of the KL divergences of the independent components [41].

## D Detailed Proof of Lemma 3.20

Below, we provide a detailed proof of lemma 11. Specifically, we aim to show that

$$ \min_{W \in \mathbb{R}^{C \times d}} L_{\text{CE}}(f, W) \leq \sigma + \tau L(f) + \tau \Delta + \alpha, $$

$$ \text{where } \alpha = \log(C) + \min \{0, \log(C\pi^* \cosh^2(1)) - \tau\Delta\}. $$

*Proof.* On one hand, using two applications of (23), we obtain an upper bound on the term LSE($\mathbf{u}$) with $\mathbf{u} := \{f(x)^\top f(x')\}_{x' \in X}$:

$$ \text{LSE}(\mathbf{u}) = \text{LSE}\left(\tau \cdot \frac{\mathbf{u}}{\tau}\right) \le \tau \max_i z_i + \log(K) \le \tau \text{LSE}(\mathbf{z}) + \log(K), \quad (26) $$

where the first inequality uses $t = \tau$ and the second one uses $t = 1$. This yields:

$$ \text{LSE}(\mathbf{z}) \ge \frac{1}{\tau} (\text{LSE}(\mathbf{u}) - \log(K)). \quad (27) $$
<table><caption>Table 6: Comparison of upper bounds on downstream classification loss with MNIST.</caption><thead><tr><th></th><th>τ = 1</th><th>τ = 0.7</th><th>τ = 0.5</th><th>τ = 0.2</th></tr></thead><tbody><tr><td></td><td>Bao et al.</td><td>3.0212</td><td>3.7607</td><td>5.0141</td><td>12.5462</td></tr><tr><td></td><td>Th. 3 (ours)</td><td>3.0212</td><td>3.7607</td><td>4.8096</td><td>4.5996</td></tr><tr><td rowspan="2">Proj.</td><td>Sup. Loss</td><td>1.5453</td><td>1.5317</td><td>1.5063</td><td>1.5163</td></tr><tr><td>top-1</td><td>0.8874</td><td>0.9057</td><td>0.9425</td><td>0.9418</td></tr><tr><td></td><td>Sup. Loss</td><td>1.4783</td><td>1.4769</td><td>1.4732</td><td>1.4793</td></tr><tr><td></td><td>top-1</td><td>0.9779</td><td>0.9809</td><td>0.9829</td><td>0.9778</td></tr></tbody></table>

We obtain:

$$
\begin{align*}
L(f) &\overset{(a)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \mathbb{E}_x \mathbb{E}_{\{(x'_i, y'_i)\}_{i=1}^K} [\text{LSE}(\mathbf{z})] \\
&\overset{(b)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \frac{1}{\tau} \mathbb{E}_x \mathbb{E}_{\{(x'_i, y'_i)\}_{i=1}^K} [\text{LSE}(\mathbf{u})] - \frac{\log(K)}{\tau} \\
&\overset{(c)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \frac{1}{\tau} \mathbb{E}_x \mathbb{E}_{\{y'_i\}_{i=1}^K} [\text{LSE}(\mathbf{u}^{\mu})] - \frac{\log(K)}{\tau},
\end{align*}
$$

where: (a) follows from the sequence of inequalities in eq. (11) to eq. (14); (b) follows by applying eq. (27); (c) follows from an application of Jensen's inequality with $\mathbf{u}^{\mu} := \{f(x)^{\top} \mu_{y'}\}_{y' \in Y}$.

Then, we derive a lower bound on $\mathbb{E}_Y [\text{LSE}(\mathbf{u}^{\mu})]$:

$$
\begin{align*}
\mathbb{E}_Y [\text{LSE}(\mathbf{u}^{\mu})] &\overset{(a)}{\ge} -\mathbb{E}_Y [\text{LSE}(-\mathbf{u}^{\mu})] + 2 \log(K) \\
&\overset{(b)}{\ge} -\text{LSE} \left( \{-f(x)^{\top} \mu_c\}_{c \in \mathcal{C}} \right) + \log(K) - \log(\pi^*) \\
&\overset{(c)}{\ge} \text{LSE} \left( \{f(x)^{\top} \mu_c\}_{c \in \mathcal{C}} \right) - 2 \log(C \cosh(1)) + \log(K) - \log(\pi^*) \\
&\overset{(d)}{=} \text{LSE} \left( \{f(x)^{\top} \mu_c\}_{c \in \mathcal{C}} \right) - \log \left( \frac{C^2 \pi^*}{K} \cosh^2(1) \right),
\end{align*}
$$

where (a) uses the left-hand side of lemma 10 for $N = K$ and $L = 1$, (b) is a direct application of eq. (17) to eq. (15), using $\mathbf{u}^{\mu}$ instead of $\mathbf{z}^{\mu}$ (they differ only by a scaling factor $\tau$), (c) applies the right-hand side of lemma 10 for $N = C$ and $L = 1$, (d) follows by simplifying the previous line.

Combining this with the earlier bound, we obtain:

$$
\begin{align*}
L(f) &\geq -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \frac{1}{\tau} \text{LSE} \left( \{f(x)^{\top} \mu_c\}_{c \in \mathcal{C}} \right) - \frac{1}{\tau} \log \left( \frac{C^2 \pi^*}{K} \cosh^2(1) \right) - \frac{\log(K)}{\tau} \\
&= -\frac{\sigma}{\tau} + \frac{1}{\tau} L_{\text{CE}}(f, W^{\mu}) - \frac{1}{\tau} \log (C^2 \pi^* \cosh^2(1)).
\end{align*}
$$

Thus, we obtain the following bound on the mean classifier:

$$L_{\text{CE}}(f, W^{\mu}) \leq \sigma + \tau L(f) + \tau \Delta + \log(C) + \log(C \pi^* \cosh^2(1)) - \tau \Delta. \quad (28)$$

On the other hand, applying (23) twice, we obtain an upper bound on the term $\text{LSE}(\mathbf{u}^c)$, where $\mathbf{u}^c := \{f(x)^{\top} \mu_c\}_{c \in \mathcal{C}}$:

$$\text{LSE}(\mathbf{u}^c) = \text{LSE} \left( \tau \cdot \frac{\mathbf{u}^c}{\tau} \right) \leq \tau \max_i z_i^c + \log C \leq \tau \text{LSE}(\mathbf{z}^c) + \log C, \quad (29)$$
where we define LSE(z^c) with z^c := {f(x)⊤μ_c}c∈C. This yields

τ LSE(z^c) ≥ LSE(u^c) − log C. (30)

We obtain:

$$
\begin{align*}
L(f) &\overset{(a)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \mathbb{E}_x \mathbb{E}_{\{(x'_i, y'_i)\}_{i=1}^{K}} [\text{LSE}(z^{\mu})] \\
&\overset{(b)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \text{LSE}(z^c) - \Delta \\
&\overset{(c)}{\ge} -\frac{\sigma}{\tau} - \mathbb{E}_{(x,y)} \left[ \frac{f(x)^{\top} \mu_y}{\tau} \right] + \frac{1}{\tau} \text{LSE}(u^c) - \frac{\log C}{\tau} - \Delta
\end{align*}
$$

where: (a) follows from the sequence of inequalities from eq. (11) to eq. (15); (b) follows from applying eq. (16) to eq. (22); (c) follows by applying eq. (30). We obtain

$$
L_{CE}(f, W^{\mu}) \leq \sigma + \tau L(f) + \tau \Delta + \log C. \quad (31)
$$

Finally, taking the minimum over the two refined bounds eq. (28) and eq. (31), and then over all linear
classifiers completes the proof. □

E Extensions

Throughout the paper, we have noted several directions for generalizing our results to better align with
the original SimCLR framework. In this section, we elaborate on these remarks and provide explicit
derivations to support each extension.

**Remark 2.1**

We now elaborate on the statement made in remark 1. Specifically, we detail the formulation of the
original SimCLR loss introduced in [7], applied over a dataset $S \sim S^n$:

$$
\hat{L}_S(f) = \frac{1}{n} \sum_{i=1}^{n} \frac{\ell_{\text{cont}}(x_i, x_i^+, X_i^-) + \ell_{\text{cont}}(x_i^+, x_i, X_i^-)}{2} = \frac{1}{n} \sum_{i=1}^{n} \ell(x_i, x_i^+, X_i^-), \quad (32)
$$

where we recall that the set of negatives is given by $X_i^- = \bigcup_{j \neq i} \{x_j, x_j^+\}$.

**Remark 3.3**

We now provide details on how the proof of lemma 1 adapts to the loss defined in eq. (32), see remark 2.
The extension requires only minor modifications:

i) The set $X_i$ is replaced with the full set of $2(m-1)$ negative samples, denoted $X_i^-$.

ii) The set $N_i$ is replaced with $N_i^- = X_i^- \setminus \{x_i, x_i^+\}$.

iii) The quantities $\kappa$, $a$, and $b$ are redefined appropriately.

As a consequence, we obtain the following upper bound:

$$
|\ell_{\text{cont}}(x_i, x_i^+, X_i^-) - \ell_{\text{cont}}(x_i', x_i^+, X_i^-)| \le \frac{4}{\tau}.
$$

Let $\tilde{X}_j^-$ denote a perturbed version of the negative set $X_j^-$. Then:

$$
\left| \ell_{\text{cont}}(x_j, x_j^+, X_j^-) - \ell_{\text{cont}}(x_j, x_j^+, \tilde{X}_j^-) \right| = \left| \log \frac{\kappa + \text{sim}(x_j, x_i) + \text{sim}(x_j, x_i^+)}{\kappa + \text{sim}(x_j, x_i') + \text{sim}(x_j, x_i'^+)} \right| \le \log \frac{\kappa + a}{\kappa + b},
$$
where $\kappa = \text{sim}(x_j, x_j^+) + \sum_{x' \in N_i^-} \text{sim}(x_j, x')$, $a = 2e^{1/\tau}$ and $b = 2e^{-1/\tau}$. Since $\kappa$ includes $2m-3$ terms, it is lower-bounded as $\kappa \ge (2m-3)e^{-1/\tau}$. Thus, we can further bound:

$$ \log \frac{\kappa + a}{\kappa + b} \le \log \frac{(2m-3)e^{-1/\tau} + 2e^{1/\tau}}{(2m-3)e^{-1/\tau} + 2e^{-1/\tau}} = \log \frac{(2m-3) + 2e^{2/\tau}}{2m-1}. $$

Arguing similarly to the proof of lemma 1 we conclude that

$$ |\delta_i(\bar{x}_i)| \le \frac{4}{\tau} \quad \text{and} \quad |\delta_j(\bar{x}_i)| \le \log \frac{(2m-3) + 2e^{2/\tau}}{2m-1}. $$

Combining these yields $\frac{4}{\tau} + (m-1) \log \frac{(2m-3)+2e^{2/\tau}}{2m-1}$.

### Remark 3.9

We now detail how the proof of theorem 4 extends to the loss defined in eq. (32); see also remark 3. In this extension, the set $X$ is replaced by $X^-$, and we therefore require a concentration bound on the quantity

$$ S(x, X^{-}) := \sum_{x' \in X^{-}} \text{sim}(x, x') = \sum_{x' \in X} \left( \text{sim}(x, x') + \text{sim}(x, x'^{+}) \right). $$

This expression shows that $S(x, X^{-})$ is a sum of $m-1$ independent and bounded random variables, each lying within the interval $[2e^{-1/\tau}, 2e^{1/\tau}]$. We apply Hoeffding's inequality with range parameter $c = 2(e^{1/\tau} - e^{-1/\tau})$, and obtain the same concentration bound as in lemma 5, with the only difference being that the term $\varepsilon$ is now given by $\varepsilon = 2(e^{1/\tau} - e^{-1/\tau}) \sqrt{\frac{m-1}{2} \log \frac{1}{\delta}}$, which is multiplied by a factor of 2 compared to the previous result.

### Remark 3.16

As discussed in remark 4, theorem 5 can be extended to include a simple projection head. Specifically, we first apply the theorem to the projected features $f_1$, which yields

$$ \min_{W^{(1)} \in \mathbb{R}^{C \times k}} L_{\text{CE}}(f_1, W^{(1)}) \le \min \{\beta(f_1, \sigma), \tau\beta(f_1, \sigma) + \alpha\}, $$

where $\alpha$, $\sigma$, and $\beta$ are defined in theorem 5. Now, since $L_{\text{CE}}(f_1, W^{(1)}) = L_{\text{CE}}(f, \tilde{W})$ for

$$ \tilde{W} = \begin{bmatrix} W^{(1)} \\ 0_{(d-k) \times C} \end{bmatrix}, $$

the bound also holds for any $W \in \mathbb{R}^{C \times d}$ such that $L_{\text{CE}}(f, W) \le L_{\text{CE}}(f, \tilde{W})$. In particular, this includes the minimizer over all such $W$. Therefore, we conclude:

$$ \min_{W \in \mathbb{R}^{C \times d}} L_{\text{CE}}(f, W) \le \min \{\beta(f_1, \sigma), \tau\beta(f_1, \sigma) + \alpha\}. $$

### Remark 3.17

As mentioned in remark 5, the proof of theorem 5 can be directly extended to the loss defined in eq. (32) by replacing $X$ with $X^-$ and setting $K = 2(m-1)$ throughout the derivation. Note that the proof remains unchanged, as it does not rely on any independence assumptions regarding the negative samples.