arXiv CSopen access

Similarity search generalisation in contrastive learning with InfoNCE loss

Similarity search generalisation in contrastive learning with InfoNCE loss Nick Whiteley School of Mathematics, University of Bristol, U.K. July 13, 2026

arXiv:2607.09405v1 [cs.LG] 10 Jul 2026

Abstract Similarity search is a primary application of embedding models trained by contrastive learning. For one of the most popular contrastive learning loss functions, InfoNCE, we show that the population risk with k negative samples is O(1/k) close to an expected cross-entropy which quantifies deviation between i) a softmax similarity search over unseen data using the learned embedding function, and ii) an idealised softmax search over the same data but using similarity implicitly represented in the positive sample generator. This complements existing interpretations of InfoNCE in the k → ∞ limit which are phrased in terms of mutual information, and alignment versus uniformity in embeddings. To quantify generalisation performance, we introduce a new continuity bound for the InfoNCE loss, obtained via Gâteaux differentiation. The bound preserves the structure of averaging over negative samples present in the loss function and features an “inverse temperature” parameter which can be tuned to account for the algorithmic temperature. For embedding functions which are Lipschitz in a parameter, this yields a simple demonstration that the averaging effect of k negative samples in the InfoNCE loss carries over to stabilisation of the generalisation error as k grows.

1

Introduction

The InfoNCE loss [van den Oord et al., 2018] is one of the most popular loss functions in contrastive learning and is a fundamental ingredient in hugely impactful systems such as SimCLR [Chen et al., 2020], MoCo [He et al., 2020] and CLIP [Radford et al., 2021]. Similarity search is a primary application of these technologies and other embedding models trained using contrastive learning; the learned embedding is used to calculate cosine similarities and hence evaluate closeness among unseen data. The goal of the present work is to add clarity to our theoretical understanding of InfoNCE, similarity search and generalisation. To date, theoretical generalisation analysis of contrastive learning has largely focused on downstream classification. In that context, “generalisation” has the conventional meaning of a model’s ability to make accurate predictions on unseen data: a pioneering step forward was made by Saunshi et al. [2019], who showed that the InfoNCE population risk can contribute to bounding the population risk of a downstream linear classifier, thus quantifying classification accuracy when an unseen input data point, such as an image or text document, is represented by its embedding vector. Subsequent refinements and extensions, discussed in more detail later, have been made by [Lei et al., 2023, Ghanooni et al., 2024, Hieu and Ledent, 2025]. In the present work we also analyse InfoNCE risk but from a different perspective, which we call similarity search generalisation: the performance of similarity search on unseen data using the learned embedding, compared to an idealised search which we show is implicitly defined by the ingredients of contrastive learning. We draw inspiration not only from learning-theoretic analyses of e.g., [Saunshi et al., 2019, Lei et al., 2023, Ghanooni et al., 2024, Hieu and Ledent, 2025], but also from widely referenced interpretations of contrastive learning in terms of mutual information [van den Oord et al., 2018], “alignment” versus “uniformity” in embeddings [Wang and Isola, 2020a], and cross-entropy between conditional probability densities [Zimmermann et al., 2021].

1

1.1

Interpretations of InfoNCE

Each training tuple or mini-batch in contrastive learning comprises “anchor”, “positive” and “negative” samples1 . Pairs of anchor and positive samples are generated in order to convey some notion of semantic similarity which is specific to input data modality, such as text, images, etc. Negative samples are usually additional data points which are independent of the anchor and positive samples. Conventional theoretical interpretations of contrastive learning with InfoNCE loss address the regime where the number of negative samples grows. The InfoNCE loss function was introduced by van den Oord et al. [2018] as the categorical cross-entropy associated with correctly classifying a positive sample versus negative samples. They showed that minimising InfoNCE risk maximises a lower bound on mutual information, and argued that bound becomes tight as the number of negative samples grows. Wang and Isola [2020a] uncovered another interpretation of InfoNCE associated with taking the number of i.i.d. negative samples k → ∞. They showed that, in this limit, the logarithmically normalised InfoNCE population risk converges to a limiting risk function which separates into a sum of two terms, arguing that minimising InfoNCE loss promotes a balance between “alignment” and “uniformity” of embeddings. The same k → ∞ limit was given another interpretation by Zimmermann et al. [2021], as cross-entropy between conditional probability density functions, in a setting where the input samples are assumed to be drawn from a distribution defined by pushing the uniform density on a hypersphere or convex subset of Euclidean space through an invertible transformation. They argued that contrastive learning can invert that data generating model. In all of these interpretations, the convergence of the logarithmically normalised InfoNCE population risk as k → ∞ can be viewed as a consequence of a law of large numbers for the negative samples. The risk converges because averaging over these negative samples occurs within the loss function. In the present work we explore yet another interpretation of the k → ∞ averaging, relating InfoNCE population risk to similarity search on unseen data.

1.2

Generalisation analysis of contrastive learning

In order to quantify downstream classification performance, Saunshi et al. [2019] and in turn Lei et al. [2023] assumed a specific data-generating model involving discrete classes and class labels, with positive samples generated by drawing from the same class-conditional distribution as the anchor sample. However, their complexity analysis of InfoNCE risk (rather than classification risk) depends very little on this model. To apply a standard generalisation bound [Mohri et al., 2018, Thm. 3.3] they only really require that training tuples are i.i.d., and their empirical complexity bounds hold for any realisation of the data hence do not require any distributional assumptions at all. We would like to exploit this fact in order to apply their results outside of the context of classification. Considering the interest in the regime k → ∞ described above, this naturally leads us to the question of how InfoNCE generalisation error behaves as k grows. As discussed by Lei et al. [2023], the complexity √ bounds of Saunshi et al. [2019] feature an explicit factor which grows with k (e.g., see the factor of k in [Saunshi et al., 2019][Supp. material, eq. (30)]), seemingly at odds with studies indicating that a large number of negative samples is necessary for good generalisation performance in practice [Chen et al., 2020, He et al., 2020, Henaff, 2020, Khosla et al., 2020, Tian et al., 2020]. Lei et al. [2023] revisited this generalisation analysis and used alternative mathematical techniques to obtain√refined complexity bounds, improving over [Saunshi et al., 2019] by √ eliminating the explicit factor of k for ℓ2 -Lipschitz loss functions and reducing by a further factor of k for ℓ∞ -Lipschitz losses (up to factors logarithmic in k and the number of training tuples n). Lei et al. [2023] also obtained datadependent bounds in the case of self-bounding loss functions. Nevertheless, the complexity estimates obtained by Lei et al. [2023] for ℓ2 or ℓ∞ -Lipschitz loss functions still depend on k and may grow with k in general; they involve summing and/or maximising over an index set which grows with k (see the quantities denoted A and C in [Lei et al., 2023][eqs. 4.2 and 4.5]). The resulting bounds for linear and nonlinear features [Lei et al., 2023][sec. 5, quantity Bx ] involve the maximum of the norms of the input data vectors, which will grow with k in general when the input domain is unbounded. One of the aims of the present work is to clarify whether such dependence on k is avoidable. In more recent developments, the assumption of i.i.d. data tuples made by Saunshi et al. [2019] and Lei et al. [2023] was loosened by Hieu and Ledent [2025], bringing the analysis closer to practical 1 The terms “anchor”, “positive” and “negative” samples are standard in the contrastive learning literature.

With a warning to the uninitiated reader that “positive” and “negative” should not be interpreted in the conventional mathematical sense, the quotation marks will be dropped from here on.

2

dependency between samples using U -statistics. Ghanooni et al. [2024] developed generalisation analysis for adversarial contrastive learning.

1.3

Outline and contributions

• Section 2 presents the basic ingredients of contrastive learning with the InfoNCE loss. Our setup is purposefully general in some ways: our measure-theoretic notation is chosen to help interpret the InfoNCE population loss in terms of Markov kernels and softmax similarity search. However, our presentation is purposefully narrow in other ways: our priority is to give the reader, in just a few pages, an end-to-end account from interpretation of the InfoNCE loss, to easily interpretable generalisation bounds which exhibit the role of k and other quantities. We thus introduce contrastive learning as obtaining an embedding function ϕ by empirical risk minimisation (although strict minimisation is not required for our generalisation results to apply), and do not enter into details of how specific neural network architectures, gradient algorithms, mini-batches etc., are used in practice. • In section 3.1 we introduce a Markov kernel Qϕτ on the input space Z, depending on the embedding function ϕ and temperature parameter τ , and in proposition 1 in section 3.2 show that as k → ∞, the (logarithmically normalised) InfoNCE population risk converges to cross-entropy between Qϕτ and the Markov kernel M which generates positive samples: Z + ∼ M (Z, ·) where Z ∼ πdata and πdata is a probability measure on Z. This presentation is partly inspired by [Zimmermann et al., 2021, Thm 1.] but does not require the specifics of their data-generating model. It is already known that √ the population risk converges in this limit, Wang and Isola [2020b, Thm 1.] report a rate O(1/ k); we clarify in proposition 1 the rate is O(1/k). We also highlight the regularising role of the temperature parameter: the higher τ is, the more Qϕτ (z, ·) is constrained to be close to πdata , uniformly in z and ϕ. • In section 3.3 we present an interpretation of the InfoNCE population risk which, to the knowledge of b ϕ defined in terms the author, is new. We introduce an empirical softmax similarity Markov kernel Q τ,k of k unseen (i.e., independent of training data) draws from πdata . In proposition 2 we show that when M (z, ·) is dominated by πdata for all z ∈ Z, the (logarithmically normalised) InfoNCE population b ϕ and an idealised empirical Markov risk is O(1/k) close to the expected cross-entropy between Q τ,k ck kernel built from the same k unseen data points importance weighted according to the density of M ck conveys whatever M (z, ·) with respect to πdata , where z is the search query point. In this sense M c notion of similarity is implicitly represented in M , and sampling from Mk has the interpretation of an idealised softmax similarity search. • Motivated by these considerations of InfoNCE when k is large, we turn to generalisation analysis in section 4. The key mathematical contribution in section 4.1 is a new continuity bound for the InfoNCE loss, presented in proposition 4. This bound is obtained by via Gâteaux differentiation, exploiting the specific structure of the InfoNCE loss, whereas Lei et al. [2023]’s analysis applies more generally to ℓ2 /ℓ∞ -Lipschitz or self-bounding loss functions. The continuity bound is applied to bounding InfoNCE Rademacher complexity in section 4.2 when the embedding function is chosen from a class of functions Lipschitz in a parameter. This demonstrates the structure of averaging over k negative samples in the InfoNCE loss carries over to stabilisation of generalisation error as k grows. • Possible extensions are discussed in section 5. All proofs are in the appendix.

1.4

Notation

Throughout this work, Z is a set and FZ is a σ-algebra of subsets of Z. The set of probability measures on the measurable space (Z, FZ ) is denoted P(Z). The delta-Dirac measure located at z ∈ Z is denoted Pd δz . For d ≥ 2, p ≥ 1 and v = (v1 , . . . , vd ) ∈ Rd we write the norm ∥v∥p := ( j=1 |vj |p )1/p , and denote by ⟨·, ·⟩ the Euclidean inner product. We write Sd−1 for the set all of v ∈ Rd such that ∥v∥2 = 1. For functions f : Z → Rd we define the norm ∥f ∥2,∞ := supz∈Z ∥f (z)∥2 and denote by B(Z, Rd ) the Banach space of all measurable f : Z → Rd such that ∥f ∥2,∞ < ∞. We denote by B(Z, Sd−1 ) ⊂ B(Z, Rd ) the set of those functions f such that ∥f (z)∥2 = 1 for all z ∈ Z. For scalars a, b, the maximum and minimum are denoted a ∨ b and a ∧ b, respectively.

3

2

Contrastive learning with the InfoNCE loss

2.1

Preliminaries

The model we assume for contrastive learning training data has three ingredients: • a set Z; • a probability measure πdata ∈ P(Z); • a Markov kernel M : Z × FZ → [0, 1], i.e., for each z ∈ Z, M (z, ·) ∈ P(Z), and for each A ∈ FZ , z 7→ M (z, A) is a measurable function. The training data comprises n ≥ 1 tuples, Z1 , . . . , Zn , where, for k ≥ 1, each tuple Zi ∈ Z 2+k consists of − − an anchor sample, Zia ; a positive sample, Zi+ ; and negative samples, Zi1 , . . . , Zik . The following is taken as a standing assumption throughout the entirety of this work. iid

− − , . . . , Zik (A) Z1 , . . . , Zn are i.i.d. and each tuple Zi is distributed: Zia ∼ πdata , Zi+ ∼ M (Zi , ·), Zi1 ∼ πdata .

In practice, positive samples are generated by applying various transformations to the anchor samples, sometimes called “views”. Examples include, for images: cropping, resizing, rotation, colour adjustment, jitter and blurring; and for text: synonym replacement, back-translation, and swapping, insertion and deletion of characters, tokens, or words. All of these transformations are usually subject to some degree of randomisation, for example randomly choosing the area to be cropped, the rotation angle, etc., and the choice of transformation, or the order in which to compose transformations, may also be randomised. We assume that any and all such randomisation is encapsulated in the Markov kernel M . We do not assume any particular functional form or algorithmic description of M is known; for our purposes it can be thought of as a “black box” sample generator (later subject to assumption (B), which is applied solely within section 3). Similarly, we do assume any particular functional form for πdata , in practice this distribution is unknown. For our purposes, we may think of contrastive learning as choosing an embedding function ϕb from some class Φ ⊂ B(Z, Sd−1 ) by minimising the empirical InfoNCE risk associated with Z1 , . . . , Zn . The procedure is outlined in algorithm 1. Later on, in section 4, we will consider specific choices of Φ. Algorithm 1 InfoNCE Empirical Risk Minimization iid

inputs: anchor samples Z1a , . . . , Zna ∼ πdata ; integer k ≥ 1, set of functions Φ; temperature param. τ > 0. for i = 1, . . . , n, – draw one positive sample Zi+ ∼ M (Zia , ·) iid

− − – draw k negative samples Zi1 , . . . , Zik ∼ πdata end for do minimisation:   n k X X   − ϕb = argmin log 1 + exp ⟨ϕ(Zia ), ϕ(Zij ) − ϕ(Zi+ )⟩/τ  . ϕ∈Φ

i=1

j=1

bn (·; k, τ ) and R(·; k, τ ), are defined as The empirical and population InfoNCE risk functionals, R d−1 follows. For ϕ ∈ B(Z, S ), k ≥ 1 and τ > 0,   n k X X − + a 1 bn (ϕ; k, τ ) := R log 1 + e⟨ϕ(Zi ,ϕ(Zij )−ϕ(Zi )⟩/τ  − log k, (1) n i=1 j=1    k X − a + R(ϕ; k, τ ) := E log 1 + e⟨ϕ(Z ),ϕ(Zj )−ϕ(Z )⟩/τ  − log k, (2) j=1 iid

where in (2), expectation is over Z a ∼ πdata , Z + ∼ M (Z a , ·), Z1− , . . . , Zk− ∼ πdata , so (A) implies bn (ϕ; k, τ )]. The empirical risk R bn (ϕ; k, τ ) differs from the quantity in Algorithm 1 only R(ϕ; k, τ ) = E[R 4

by the multiplicative 1/n and logarithmic − log k normalisation factors, which the argmin operation is invariant to.

2.2

Discussion of the setup

• The assumption within (A) that the tuples Z1 , . . . , Zn are i.i.d. was made in [Saunshi et al., 2019, Lei et al., 2023]. Similarly to those works, we use the assumption of i.i.d. tuples to apply a standard generalisation bound [Mohri et al., 2018, Thm. 3.3] in the proof of proposition 3, section 4. The assumption that, within each tuple, negative samples are i.i.d. from the same distribution as the anchor samples is quite common in the literature, e.g., [Wang and Isola, 2020a, Zimmermann et al., 2021]. This assumption of i.i.d. negative samples is used in the proofs of propositions 1 and 2 in section 3, concerning interpretation of the InfoNCE population risk. However, this part of (A) is not needed for any of the results in section 4 concerning generalisation. In fact, propositions 4 and lemma 1 in section 4, used to bound empirical Rademacher complexity, hold for any realised values z1 , . . . , zn of Z1 , . . . , Zn , and hence do not require assumption (A) at all. • In some presentations of contrastive learning and the InfoNCE loss, it is assumed that the joint distribution of anchor and positive pairs has a symmetric density and/or that the marginal distributions of the positive and negative samples are the same, e.g., [van den Oord et al., 2018, Wang and Isola, 2020a]. We make no such assumptions. Indeed the author considers it unrealistic to assume that if Z ∼ πdata and Z + ∼ M (Z, ·) then the marginal distribution of Z + is exactly πdata . This would amount to saying that M admits πdata as an invariant distribution; in practice the distribution πdata is unknown and nothing is built in to achieve such invariance. • A temperature parameter was not presented in the InfoNCE loss by [van den Oord et al., 2018] but was included in, e.g., Wu et al. [2018], Chen et al. [2020], where the loss is sometimes called the normalized temperature-scaled cross entropy loss (NT-Xent). In their generalisation analyses, Saunshi et al. [2019],Lei et al. [2023] did not explicitly consider a temperature parameter, but considered embedding functions ϕ satisfying ∥ϕ∥2,∞ ≤ R for some finite R > 0. In the present work our embedding functions are always members of B(Z, Sd−1 ), i.e., ∥ϕ(z)∥2 = 1 for all z ∈ Z. This is not essential for many of our results, but we make this assumption to conform with common practice and presentation of contrastive learning; for ϕ ∈ B(Z, Sd−1 ), ⟨ϕ(z), ϕ(z ′ )⟩ is the cosine similarity between ϕ(z) and ϕ(z ′ ). • For the purposes of our analysis it will not be important that ϕb is an exact minimiser as in algorithm 1, we write it as such just for sake of illustration; our various bounds presented in sections 3 and 4 hold uniformly over embedding functions belonging B(Z, Sd−1 ) or some some Φ ⊂ B(Z, Sd−1 ).

3

Similarity search interpretation of the InfoNCE loss

3.1

Basics of similarity search

Suppose that we are given an embedding function ϕ ∈ B(Z, Sd−1 ), for example ϕb from algorithm 1, and we use it for similarity search on unseen data, as follows: for some m ≥ 1, let ξ1 , . . . , ξm be points in Z (we use the notation ξi to distinguish these samples from any of the constituents of the training tuples Z1 , . . . , Zn ) and let z ∈ Z be a query point. Similarity search is the task: find

ξ⋆ ∈ {ξ1 , . . . , ξm }

which maximises

⟨ϕ(z), ϕ(ξ⋆ )⟩.

(3)

A “softmax”, randomised relaxation of this similarity search with the same query point z is to instead sample ξ⋆ from the set {ξ1 , . . . , ξm } as follows: 1/τ

set

ξ⋆ = ξi

with probability

Wi

(z)

1/τ (z) j=1 Wj

Pm

,

where

Wi (z) := e⟨ϕ(z),ϕ(ξi )⟩ .

(4)

When τ → 0, (4) reduces to (3). Our next objective is to explain the connection between (4) and the InfoNCE population risk R(ϕ; k, τ ). We need some further definitions. For any ϕ ∈ B(Z, Sd−1 ) and

5

τ > 0, define the Markov kernel2 : Z Qϕτ (z, A) := ZA

′

e⟨ϕ(z),ϕ(z )⟩/τ πdata (dz ′ ) ,

′

z ∈ Z, A ∈ FZ .

(5)

e⟨ϕ(z),ϕ(z )⟩/τ πdata (dz ′ )

Z

We also introduce the following empirical counterpart of Qϕτ built from the unseen data ξ1 , . . . , ξm , Pm ⟨ϕ(z),ϕ(ξi )⟩/τ e δξi (A) b ϕ (z, A) := i=1 Pm ⟨ϕ(z),ϕ(ξ )⟩/τ , z ∈ Z, A ∈ FZ . (6) Q τ,m i e i=1 b ϕ (z, ·) is equivalent to (4). These Markov kernels have the following interpretations: sampling ξ⋆ ∼ Q τ,m b ϕτ,m just encapsulates the probabilities in the softmax similarity search. If the unseen In that sense, Q iid

data are drawn from πdata , i.e., ξ1 , . . . , ξm ∼ πdata , then by the strong law of large numbers, for any b ϕτ,m (z, A) converges almost surely to Qϕτ (z, A) as m → ∞. Thus Qϕτ captures the z ∈ Z and A ∈ FZ , Q behaviour of the softmax similarity search (4) in the limit of a large amount of unseen data.

3.2

Relating population risk to integrated cross-entropy

We define the cross-entropy between M (z, ·) and Qϕτ (z, ·) (with πdata taken as a dominating measure for the latter) as:   ϕ Z dQτ (z, ·) ′ ϕ CrossEnt[M (z, ·)∥Qτ (z, ·)] := − log (z ) M (z, dz ′ ) (7) dπdata Z Z Z ′ 1 =− ⟨ϕ(z), ϕ(z ′ )⟩M (z, dz ′ ) + log e⟨ϕ(z),ϕ(z )⟩/τ πdata (dz ′ ), τ Z Z d· where d· denotes Radon-Nikodym derivative 3 , and the second equality follows from the definition (5). The following proposition relates this cross-entropy, integrated with respect to πdata , to the population risk R(ϕ; k, τ ).

Proposition 1. For any ϕ ∈ B(Z, Sd−1 ), k ≥ 1 and τ > 0,  Z  1 2/τ e2/τ ≤ CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; k, τ ) ≤ (e − 1)2 . − log 1 + k 8k Z Proposition 1 implies that, as k → ∞, R(ϕ; k, τ ) converges to the πdata -integrated cross-entropy between M (z, ·) and Qϕτ (z, ·). Modulo the technical details of our measure-theoretic setup, it is already well known that R(ϕ; k, τ ) approaches a limit as k → ∞, e.g., [van den Oord et al., 2018, Wang and Isola, 2020a, Zimmermann et al., 2021]. However, noting that for x ≥ 0, log(1 √ + x) ≤ x, proposition 1 implies a rate O(1/k) uniformly over ϕ ∈ B(Z, Sd−1 ), whereas a rate O(1/ k) was reported by [Wang and Isola, 2020b]. What more does proposition 1 tell us? The integrated cross-entropy considered in proposition 1 quantifies discrepancy between the Markov kernels M and Qϕτ . Thus proposition 1 indicates that, if we were to hypothetically choose ϕ by minimising R(ϕ; k, τ ) when k is large, this would amount to minimising discrepancy between M and Qϕτ . We might therefore take the view that choosing ϕ by minimising InfoNCE risk amounts, in effect, to learning the Markov kernel M . Consideration of Qϕτ sheds some light on the role of the temperature parameter τ here. Since ∥ϕ(z)∥2 = 1 for all z, the following two inequalities follow from the definition of Qϕτ in (5) and hold for all z ∈ Z and A ∈ FZ , e−2/τ πdata (A) ≤ Qϕτ (z, A) ≤ e2/τ πdata (A).

(8)

Thus we see that when τ → ∞, Qϕτ (z, ·) is constrained to be closer and closer to πdata , for all z ∈ Z, no matter what the choice of ϕ ∈ B(Z, Sd−1 ). In this sense, a large value of τ limits the ability of Qϕτ to closely approximate an arbitrary M . 2 A closely related but technically different conditional probability density was introduced by Zimmermann et al. [2021][Thm. 1] in the setting of a latent variable model for inputs to contrastive learning. We note their purposes were somewhat different to ours, focusing on the question of whether contrastive learning can invert a data generating process, rather than focusing on similarity search. R ⟨ϕ(z),ϕ(x⟩/τ dQϕ (z,·) ′ 3 Strictly speaking, e⟨ϕ(z),ϕ(z ′ )⟩/τ / πdata (dx) is a version of the R.-N. derivative dπτ (z ), and we are Z e data choosing to make the stated definition of cross-entropy in terms of this specific version.

6

3.3

Relating population risk to expected empirical cross-entropy

Even if we are given ϕ, the Markov kernel Qϕτ is not available in practice because the data-generating bϕ , distribution πdata is unknown. Let us now look more closely at the empirical Markov kernel Q τ,k defined in (6) which we can access in practice for any given ϕ and ξ1 , . . . , ξm . Consider the domination assumption: (B) for all z ∈ Z, M (z, ·) ≪ πdata , From a practical point of view, (B) has a simple interpretation: it says that if the data-generating distribution πdata assigns zero probability to any set A ∈ FZ , then there must be zero probability of generating a positive sample in A, i.e., M (z, A) = 0, for any point z ∈ Z. (z,·) When (B) holds, M (z, ·) admits a density with respect to πdata , denoted dM dπdata (·) and we may define the empirical Markov kernel and probability measure, Pm dM (z,·) m 1 X i=1 dπdata (ξi )δξi (A) c Mm (z, A) := , π bdata,m (A) := δξ (A), z ∈ Z, A ∈ FZ . Pm dM (z,·) m i=1 i i=1 dπdata (ξi ) cm has the Here ξ1 , . . . , ξm are the unseen data as in the similarity search (3)-(4). The Markov kernel M interpretation of importance-weighting each of the points ξ1 , . . . , ξm to account for how likely they are under M (z, ·) versus πdata . We may interpret such weighting as an abstract measure of similarity to the query point z, implicitly conveyed by whatever randomised transformations, or “views”, constitute the Markov kernel M . cm and Q b ϕτ,m , Similarly to (7), we define the cross-entropy between M # " Z h i b ϕτ,m (z, ·) dQ ′ ϕ cm (z, dz ′ ) cm (z, ·)∥Q b (z, ·) := − (z ) M (9) CrossEnt M log τ,m db π data,m Z ! Pm dM (z,·) m 1 X ⟨ϕ(z),ϕ(ξi )⟩/τ 1 i=1 dπdata (ξi )⟨ϕ(z), ϕ(ξi )⟩ . (10) e + log =− Pm dM (z,·) τ m i=1 (ξi ) i=1 dπdata

iid

Proposition 2. If (B) holds and ξ1 , ξ2 , . . . ∼ πdata , then for any ϕ ∈ B(Z, Sd−1 ), k ≥ 1 and τ > 0, Z Z

 h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; k, τ ) E CrossEnt M τ,k 4 ≤ E τk

"

dM (Z, ·) ′ (Z ) dπdata

2

#

  e2/τ + log 1 + , k

iid

where on the r.h.s., Z, Z ′ ∼ πdata . Proposition 2 tells us that when the unseen data points ξ1 , ξ2 , . . . are drawn from πdata , and are equal in number to the number of negative samples per training tuple, k, then R(ϕ; k, τ ) is O(1/k) close to the expected value of (9), integrated with respect to πdata . Here the expectation, E(·) in proposition 2, iid

integrates out ξ1 , . . . , ξk ∼ πdata . In this sense, hypothetically minimising R(ϕ; k, τ ) with respect to ϕ, b ϕ towards M ck . In turn, this can be interpreted as meaning that the softmax when k is large, pushes Q τ,k ck (z, ·). similarity search (4), with m = k, approximates sampling ξ⋆ ∼ M In practice the number of unseen data m will generally not be equal to the number of negative samples k per training tuple. Rather, we present the case m = k because it is relatively simple to analyse mathematically. One could bound the difference between R(ϕ; k, τ ) and the expected crossentropy with some m ̸= k using similar arguments to those in the proofs of propositions 1 and 2, but for brevity we doh not pursue such aibound here. In any case, propositions 1 and 2 together imply  R R ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) converges to that Z E CrossEnt M CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) τ,k Z as k → ∞.

3.4

Simplified bounds for the DCL loss function

Propositions 1 and 2 relate R(ϕ; k, τ ) to two different quantities. Can we say anything about whether, for finite k, R(ϕ; k, τ ) is closer to one or the other? The picture becomes clearer if we consider a slight 7

change to the InfoNCE loss. Suppose the term “1+” is omitted from the loss in algorithm 1. This was called the Decoupled Contrastive Learning (DCL) loss by Yeh et al. [2022], who discussed its properties and gave evidence of superior performance in practice. The population risk becomes:    k X − a + e k, τ ) := E log  R(ϕ; e⟨ϕ(Z ),ϕ(Zj )−ϕ(Z )⟩/τ  − log k, j=1

instead of (2). It can be checked that with fairly minor modifications to the proofs of propositions 1 and 2 (see e k, τ ) appendix A.1), under all the same conditions as in those propositions, the DCL population risk R(ϕ; satisfies: Z e k, τ ) ≤ 1 (e2/τ − 1)2 , (11) 0≤ CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; 8k Z i.e., compared to the proposition 1 the lower bound is zero, and Z

i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; e k, τ ) ≤ 4 E E CrossEnt M τ,k τk Z 

h

"

dM (Z, ·) ′ (Z ) dπdata

2

# ,

(12)

i.e., the additive term log(1 + e2/τ /k) in proposition 2 vanishes. We can see that if τ → 0, k must grow exponentially fast in 1/τ to control the bound in (11), but only as fast as 1/τ to control the bound in (12). In practice, τ is often chosen somewhere in the range 0.07 − 0.5 [Chen et al., 2020, He et al., 2020], so e1/τ could be quite a large number. This prompts the question: is the bound in (11) tight? The answer is that for small values of k it generally is not tight (lemma 4 shows that an alternative bound 2/τ holds for any k ≥ 1 and τ > 0), but as k grows, exponential dependence on e1/τ cannot be avoided: it is shown in appendix A.1 that if e1/τ > 2, then an example can be constructed such that  h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; e k, τ ) E CrossEnt M τ,k Z R e k, τ ) CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; Z

R lim sup k→∞

≤

"

65 τ (e1/τ − 2)

E

dM (Z, ·) ′ (Z ) dπdata

2

# .

(13)

The numerical constant 65 represents some particular choices made in the construction of this example and so may be improved. Therefore, in this example and for large k, the numerator on the left hand side of (13) will be much smaller than the denominator if # " 2 dM (Z, ·) ′ 1/τ τe ≫E (Z ) . dπdata

4

Generalisation analysis

The results of section 3 explain the behaviour of the population risk R(ϕ; k, τ ) when k is large, with the bounds in propositions 1 and 2 holding uniformly over any embedding function ϕ ∈ B(Z, Sd−1 ). As b k, τ ) where the embedding function ϕb is obtained by empirical risk such, those bounds apply to R(ϕ, minimisation as in algorithm 1, or by any other approximate minimisation scheme which outputs some member of B(Z, Sd−1 ). b k, τ ) in terms of In order to quantify generalisation performance we would like to upper bound R(ϕ, b b k, τ ), b bn (ϕ, Rn (ϕ, k, τ ). This would tell us how the quality of training, i.e., achieving a small value of R transfers to similarity search on unseen data, as discussed in section 3. Following the usual workflow b k, τ ) directly, we seek to upper bound R(·, k, τ ) bn (ϕ, of statistical learning theory, instead of analysing R bn (·, k, τ ) uniformly over some class of embedding functions Φ ⊂ B(Z, Sd−1 ) to which ϕb in terms of R is supposed to belong. Section 4.1 sets out tools for doing so applicable to a general function class Φ. These tools are applied in section 4.2 to a specific class of embedding functions which are Lipschitz in a parameter.

8

4.1

Generalisation and continuity bounds

− − For zi = (zia , zi+ , zi1 , . . . , zik ) ∈ Z 2+k define: 

 k X − + a 1 1 e⟨ϕ(zi ),ϕ(zij )−ϕ(zi )⟩/τ  ℓ(ϕ, zi , k, τ ) := log  + k k j=1

(14)

so that substituting the random tuple Zi in place of zi we have: n X bn (ϕ; k, τ ) = 1 R ℓ(ϕ, Zi , k, τ ). n i=1

The following proposition is an application to the InfoNCE risk of a well-known empirical Rademacher complexity generalisation bound for additive loss functions [Mohri et al., 2018, Thm. 3.3]. Proposition 3. Let Φ be a subset of B(Z, Sd−1 ). For any n ≥ 1, k ≥ 1, τ > 0 and δ ∈ (0, 1), it holds with probability at least 1 − δ that for all ϕ ∈ Φ, s # " n X log 2δ 12 1 bn (ϕ; k, τ ) + 2E sup σi ℓ(ϕ, Zi , k, τ ) Z1 , . . . , Zn + , R(ϕ; k, τ ) ≤ R τ 2n ϕ∈Φ n i=1 where σ1 , . . . , σn are i.i.d. Rademacher variables, independent of Z1 , . . . , Zn . The conditional expectation term in proposition 3 is the empirical Rademacher complexity associated with the InfoNCE loss functional (14) evaluated over Φ, with respect to the training sample of tuples Z1 , . . . , Zn . This empirical Rademacher complexity quantifies generalisation error, i.e., the capacity of Φ, via (14), to overfit the training data. To obtain insight into this generalisation error, we need to bound the empirical Rademacher complexity in such a way that the roles of Φ, k, τ , n, etc., become clear. A crucial step towards such a bound is to obtain some kind of quantitative continuity estimate for the loss function with respect to the embedding function ϕ. Such an estimate opens the door to bounds on Rademacher complexity using well-known techniques such as contraction [Maurer, 2016], and/or covering numbers, chaining and Dudley’s integral lemma, e.g., [Wainwright, 2019, Ch. 5]. The following proposition is the main technical contribution of section 4. Here β ≥ 1 is a mathematical parameter, introduced in order to be able to tune the bound in proposition 4 to account for the algorithmic temperature parameter τ (this tuning is demonstrated in section 4.2). As such, we call β the “inverse temperature” parameter. Proposition 4. For any k ≥ 1, z = (z a , z + , z1− , . . . , zk− ) ∈ Z 2+k , τ > 0, β ≥ 1, and ϕ, ϕ′ ∈ B(Z, Sd−1 ), |ℓ(ϕ, z, k, τ ) − ℓ(ϕ′ , z, k, τ )|  ≤

k 1X

1/β

4 1 3 ∥ϕ(z a ) − ϕ′ (z a )∥2 + ∥ϕ(z + ) − ϕ′ (z + )∥2 + e2/βτ  ∥ϕ(zj− ) − ϕ′ (zj− )∥β2  τ τ τ k j=1

.

A key feature of the bound in proposition 4 is that it preserves the structure of averaging over the negative samples present in the InfoNCE loss (14); specifically the negative samples z1− , . . . , zk− enter into the bound only through a “power-mean” parameterised by the inverse temperature β. We shall see in section 4.2 how this averaging over negative samples transfers to bounds on the Rademacher complexity. Let us compare the bound in proposition 4 to an alternative estimate available in the literature, derived from Lipschitz continuity of the logistic loss:   k X ℓlog (v) := log 1 + exp(−vj ) , v = (v1 , . . . , vk ) ∈ Rk , j=1

as discussed in, e.g., [Lei et al., 2023]. Note that when: vj = ⟨ϕ(z a ), ϕ(z + ) − ϕ(zj− )⟩/τ, we have ℓlog (v) − log k = ℓ(ϕ, z, k, τ ). 9

(15)

It is known that ℓlog is 1-Lipschitz with respect to the ∥ · ∥∞ norm on Rk [Lei et al., 2019] (and hence also 1-Lipschitz with respect to the ∥ · ∥p norm for any p ≥ 1), that is: |ℓlog (v) − ℓlog (v ′ )| ≤ ∥v − v ′ ∥∞ ,

(16)

for all v, v ′ ∈ Rk . In the case (15) note that ℓlog (v) and ℓ(ϕ, z, k, τ ) differ only by an additive factor of log k. Therefore, the 1-Lipschitz property of ℓlog (·) transfers to ℓ(·, z, k, τ ) as follows: for any ϕ, ϕ′ ∈ B(Z, Sd−1 ) let (15) hold and let v ′ = (v1′ , . . . , vk′ ) be defined by replacing ϕ in (15) with ϕ′ . Then as a consequence of (16) we have: |ℓ(ϕ, z, k, τ ) − ℓ(ϕ′ , z, k, τ )| 1 max ⟨ϕ(z a ), ϕ(z + ) − ϕ(zj− )⟩ − ⟨ϕ′ (z a ), ϕ′ (z + ) − ϕ′ (zj− )⟩ ≤ τ 1≤j≤k √  1/2 6 ≤ ∥ϕ(z a ) − ϕ′ (z a )∥22 + ∥ϕ(z + ) − ϕ′ (z + )∥22 + max ∥ϕ(zj− ) − ϕ′ (zj− )∥22 , 1≤j≤k τ

(17) (18)

where the second inequality uses the fact established in [Lei et al., 2023][Proof of Lemma 4.3] that for √ any ua , u+ , u− ∈ Sd−1 , the mapping (ua , u+ , u− ) 7→ ⟨ua , u+ − u− ⟩ is 6-Lipschitz with respect to the ∥ · ∥2 norm on R3d . Crucially in (17) the structure of averaging over negative samples in (14) has been lost. Comparing to proposition 4, we may view (17) as resorting to maximisation rather than averaging. Noting that in proposition 4 we are free to choose the inverse temperatureP parameter β ≥ 1, we can take β → k ∞ there, in which case e2/βτ → 1 and the power-mean (k −1 j=1 ∥ϕ(zj− ) − ϕ′ (zj− )∥β2 )1/β tends to max1≤j≤k ∥ϕ(zj− ) − ϕ′ (zj− )∥2 . In that limit it can be seen that the bounding quantity in proposition (4) and the r.h.s. of (18) are equivalent up to a fairly modest numerical scaling due to the elementary P3 P3 P3 inequalities for scalars: 3−1/2 i=1 |ai | ≤ ( i=1 |ai |2 )1/2 ≤ i=1 |ai |. The knock-on effect of (18) for bounding Rademacher complexity is illustrated in section 4.2.

4.2

Application to Lipschitz embedding functions

To demonstrate how the bound in proposition 4 can be applied, let us a consider a situation in which the class of functions Φ is of the form {ϕθ ; θ ∈ Θ} ⊂ B(Z, Sd−1 ) for some parameter set Θ, and ϕθ is Lipschitz with respect to θ in the sense of the following assumption. (C) The input space Z is Rdin for some din ≥ 1, and the parameter space is: Θ = {θ ∈ RdΘ : ∥θ − θ0 ∥2 ≤ R},

(19)

for some dΘ ≥ 1, θ0 ∈ RdΘ and R > 0. There is some finite constant CΦ such that for all θ, θ′ ∈ Θ and z ∈ Z, ∥ϕθ (z) − ϕθ′ (z)∥2 ≤ CΦ ∥z∥2 ∥θ − θ′ ∥2 . The setting of assumption (C) could easily be generalised in a number of ways. We consider a finitedimensional Euclidean parameter θ and dependence on ∥z∥2 to simplify the exposition which follows. There, our priority is to give a swift and easily interpretable demonstration of how k, τ , n, etc. impact the empirical Rademacher complexity appearing in proposition 3. We shall use the following pseudo-metric on Φ, associated with a realisation of tuples z1 , . . . , zn ∈ Z 2+k , to bound Rademacher complexity. !1/2 n 1X 2 ′ info ′ |ℓ(ϕ, zi , k, τ ) − ℓ(ϕ , zi , k, τ )| ρn (ϕ, ϕ ) := n i=1 The following lemma illustrates how this pseudo-metric can be bounded in the setting of assumption (C). The proof of lemma 1 uses proposition 4 with a particular choice of inverse temperature parameter, β = 2/τ . As noted earlier, in practice τ is usually chosen somewhere in the range 0.07 − 0.5 and choosing β = 2/τ conveniently reduces the factor e2/βτ in proposition 4 to e. − − Lemma 1. If (C) holds, then for any n ≥ 1, k ≥ 1, τ > 0, z1 , . . . , zn ∈ Z 2+k where zi = (zia , zi+ , zi1 , . . . , zik ), and θ, θ′ ∈ Θ, 4e Bτ (z1 , . . . , zn )CΦ ∥θ − θ′ ∥2 , ρinfo n (ϕθ , ϕθ ′ ) ≤ τ

10

where CΦ is as in assumption (C) and n

Bτ (z1 , . . . , zn ) :=

1X a 2 ∥z ∥ n i=1 i 2

!1/2

n

+

1X + 2 ∥z ∥ n i=1 i 2

!1/2

(1∧τ )/2 n X k X 1 2/(1∧τ )  + ∥z − ∥ . nk i=1 j=1 ij 2 

Lemma 1 is put to use along with Dudley’s entropy integral in the proof of the following proposition, which bounds the empirical Rademacher complexity. Proposition 5. Assume (C) holds and let CΦ , dΘ and R be as therein. For any n ≥ 1, k ≥ 1, − − z1 , . . . , zn ∈ Z 2+k where zi = (zia , zi+ , zi1 , . . . , zik ) and τ > 0, let Bτ (z1 , . . . , zn ) be as in assumption (C). Then, # " r n n p o p 96 dΘ 1X σi ℓ(ϕ, zi , k, τ ) ≤ min a log(3) + 1, log(1 + 2a) + 1 , E sup τ n ϕ∈Φ n i=1 where a := eRBτ (z1 , . . . , zn )CΦ and σ1 , . . . , σn are i.i.d. Rademacher variables. We make the following observations on the bound in proposition 5 • On the right of the inequality, the only place that k appears is in the averaging term within Bτ (z1 , . . . , zn ). If the random sample Z1 , . . . , Zn was substituted in place of z1 , . . . , zn , then under − the i.i.d. property of Zij in assumption (A) the law of large numbers would be applicable to this averaging term. In that sense we see the Rademacher complexity stabilises as k → ∞. It can be checked that using (18) instead of proposition 4 results in a maximisation, rather than average, over the negative sample norms. • Other than the leading factor of τ −1 , the influence of the temperature parameter has been transferred all the way through to the inverse exponent of a power-mean of the norms of negative samples − ∥zij ∥2 , within Bτ (z1 , . . . , zn ). Thus as the temperature tends to zero τ → 0, the bound becomes − increasingly sensitive to large values of the negative sample norms ∥zij ∥2 , suggesting that, roughly speaking, generalisation error is bigger at lower temperatures. • The embedding dimension, d in Sd−1 , makes no appearance in the bound of proposition 5. This lack of dimension dependence can be understood as an advantage of embedding onto the sphere Sd−1 , rather than, e.g., embedding in Rd in an unconstrained manner. p p • To interpret the minimum term, note that a ≤ 1 ⇔ a log(3) + 1 ≤ log(1 + 2a) + 1. Therefore √ as a → 0, the bound is O(a), whilst as a → ∞ it is O( log a). In turn, if either the parameter radius R, data-dependent term Bτ (z1 , . . . , zn ) or Lipschitz constant CΦ were to tend to zero (with all other quantities held constant), then so does a, and hence the Rademacher complexity shrinks to zero.

5

Discussion

A combined similarity search generalisation bound. To summarise some of the results of this work we can combine, for example, propositions 2, 3 and 5 in the following theorem. iid

Theorem 1. Assume (A), (B) and (C) with Φ = {ϕθ ; θ ∈ Θ} as therein and ξ1 , ξ2 , . . . ∼ πdata . For any

11

n ≥ 1, k ≥ 1, τ > 0 and δ ∈ (0, 1) it holds with probability at least 1 − δ that for all ϕ ∈ Φ, Z  h i bn (ϕ; k, τ ) ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) ≤ R E CrossEnt M τ,k | {z } Z {z } empirical risk | similarity search expected cross−entropy

const. + | τ

r

n p o p dΘ min A log(3) + 1, log(1 + 2A) + 1 n {z } complexity penalty

s

+

const. log 2δ τ 2n | {z }

sample variability

4 + E τk |

"

#   2 dM (Z, ·) ′ e2/τ + log 1 + (Z ) , dπdata k {z } finite k bias

where A := eRBτ (Z1 , . . . , Zn )CΦ ; dΘ , R and CΦ are as in (C); and Bτ (· · · ) is as in lemma 1. This theorem illustrates the three contributions to the difference between similarity search expected bn (ϕ, k, τ ). The sample variability and complexity penalty terms cross entropy and the empirical risk R arise from proposition 3 combined with the Rademacher complexity bound in proposition 5. The finite k bias term comes from proposition 2. The sample variability term does not depend on k and is O(n−1/2 ), the complexity penalty term stabilises as k → ∞ because of the averaging structure within Bτ (Z1 , . . . , Zn ) and hence is O(n−1/2 ), and the bias term tends to zero as k → ∞ and is O(1/k). As discussed in section 3.4, if using the DCL loss instead of InfoNCE, the log(1 + e2/τ /k) term disappears from the finite k bias. We leave it as an exercise to check that counterparts of proposition 3 and proposition 5 hold for the DCL risk, yielding complexity penalty and sample variability terms equal to those in theorem 1 up to numerical constants. Regularisation from early stopping of optimisation algorithms. Our analysis has been algorithmfree, in the sense that we have not considered any particular method for approximately minimising the InfoNCE risk. Never-the-less, if θ0 in (C) is regarded as an initial point for a recursive optimisation algorithm (which optimises θ in order to approximately minimise the empirical risk associated with ϕθ ) then R can be interpreted as a bound on the distance from θ0 such an algorithm can move in some finite number of steps. We can see in proposition 5 that R → 0 forces the Rademacher complexity to zero. In this sense, our results accommodate the idea that early stopping of an optimisation algorithm has a regularising effect. Neural networks. In our analysis we have prioritised obtaining a clear and easily interpretable demonstration of the impact of k, τ , etc. on generalisation. Assumption (C) serves this purpose. In fact, assumption (C) is satisfied if ϕθ is a fully connected multilayer perceptron with: Euclidean input domain; a 1-Lipschitz activation function such as ReLU; zero biases; weights constrained such that the product of spectral norms of the weight matrices is less than a constant; and θ comprises all entries of all the weight matrices of the network. In this situation dΘ ∼ width2 × depth. The resulting factor of dΘ in the bounds of proposition 5 could be ameliorated to some extent by scaling down the weight matrices (and hence CΦ ) with network size, as is common practice, e.g., [Yang et al., 2021]. However, for wide and/or deep networks, the explicit dependence on dΘ could make the bound in proposition 5 vacuous unless n is very large. Various techniques have been devised to obtain complexity bounds for neural networks which do not have explicit dependence on width and/or depth, e.g., [Neyshabur et al., 2015, Bartlett et al., 2017, Golowich et al., 2018, Lei et al., 2023]. A potential topic for future research is to explore whether such techniques can be made to work together with the continuity bound in proposition 4. Another exciting direction is the notion of a path metric of a neural network, e.g., [Gonon et al., 2025], which can help to bound complexity for a broad class of modern neural network architectures beyond the basic format of a multilayer perceptron and achieve scaling invariance. Downstream classification. Whilst we have emphasised similarity search generalisation, the results of section 4 do not rely on any distributional assumptions other than the tuples Z1 , . . . , Zn being i.i.d. As such, they are transferable to the classification setting of Saunshi et al. [2019], Lei et al. [2023]. 12

A

Proofs and supporting results for section 2

Lemma 2. For any k ≥ 1, b, c > 0 and i.i.d. random variables X, X1 , . . . , Xk , each valued in the interval [−c, c],      k c X  
1 2c 1 b e ≤ log bE eX − E log  + eXj  ≤ (e − 1)2 . − log 1 + bk k k j=1 8k Pk b, µ ∈ [e−c , ec ]. With f (y) := log(1/k + y) we Proof. Denote µ b := k −1 j=1 eXj and µ := E[eX ]. Note µ have:    k X  X 
1 b log bE e − E log  + µ)]. (20) eXj  = log(bµ) − f (bµ) + f (bµ) − E[f (bb k k j=1 For the first difference on the r.h.s. of (20),      1 ec 0 ≥ log(bµ) − f (bµ) = log(bµ) − log bµ 1 + ≥ − log 1 + . kbµ bk

(21)

For the second difference on the r.h.s. of (20), by Taylor expansion of y 7→ f (y) about bµ, there exists ξ ∈ [be−c , bec ] such that:     1 b(b µ − µ) b2 1 2 − 1 + bb µ = log + bµ + 1 (b µ − µ) log 2 k k + bµ + ξ) 2( k k   1 b(b µ − µ) 1 2 ≥ log + bµ + 1 − −2c (b µ − µ) . k 2e + bµ k Therefore, using E[b µ] = µ, E [f (bb µ)] ≥ f (bµ) −

h i 1 2 E (b µ − µ) . 2e−2c

Using Popoviciu’s inequality on variances, h i 1  
2 1 c 2 E (b µ − µ) = Var eX ≤ e − e−c . k 4k Concavity of f and Jensen’s inequality implies E[f (bb µ)] ≤ f (bµ), so we have: 0 ≤ f (bµ) − E [f (bb µ)] ≤

2 1 2c e −1 . 8k

(22)

The proof is completed by combining (21) and (22) with (20). iid

Proof of proposition 1. Fix any z a , z + ∈ Z. Let Z1− , . . . , Zk− ∼ πdata . Applying lemma 2 with b = − a a + e−⟨ϕ(z ),ϕ(z )⟩/τ , c = 1/τ , Xj = e⟨ϕ(z ),ϕ(Zj )⟩/τ , and using b ≥ e−1/τ ,   e2/τ − log 1 + k    Z  k X − a + a − + 1 1 ≤ log e⟨ϕ(z ),ϕ(z )−ϕ(z )⟩/τ πdata (dz − ) − E log  + e⟨ϕ(z ),ϕ(Zj )−ϕ(z )⟩/τ  k k Z j=1 ≤

1 2/τ (e − 1)2 . 8k

Now let Z a ∼ πdata and Z + ∼ M (Z a , ·), independent of Z1− , . . . , Zk− . The proof is completed by substituting Z a and Z + in place of z a and z + respectively, and taking expectation. Lemma 3. For any two probability measures ν, π ∈ P(Z) such that ν ≪ π, any measurable function iid

f : Z → [−1, 1], any m ≥ 1 and ξ1 , . . . , ξm ∼ π, " Pm # " # dν 2 4 dν j=1 f (ξj ) dπ (ξj ) E − Eν [f (ξ)] ≤ Eπ (ξ) , Pm dν m dπ j=1 dπ (ξj ) where Eν and Eπ denote expectation with respectively ξ ∼ ν and ξ ∼ π. 13

Proof. Define A := m−1

Pm

Pm

dν −1 j=1 dπ (ξj ) (f (ξj ) − Eν [f (ξ)]) and B := m

dν j=1 dπ (ξj ). Then

Pm

dν A j=1 f (ξj ) dπ (ξj ) − Eν [f (ξ)] = , Pm dν B j=1 dπ (ξj )

and the quantity we seek to bound is |E[A/B]|. We have: 1 (B − 1)2 =2−B+ , B B and using the fact that E[A] = 0,     A A 2 E = −E[AB] + E (B − 1) . B B

(23)

  dν iid Using the facts that ξ1 , . . . ξm ∼ π and E dπ (ξj )f (ξj ) = Eν [f (ξ)], the expectation of every cross term in the product-of-sums AB is zero, so we have:   m 2 X dν 1 (ξj ) (f (ξj ) − Eν [f (ξ)]) , E[AB] = E  2 m j=1 dπ and since |f (z)| ≤ 1 for all z ∈ Z, we obtain: 2 |E[AB]| ≤ Eπ m

"

dν (ξ) dπ

2

# .

(24)

Again using |f (z)| ≤ 1 we have |A| ≤ 2B, hence: 

A E (B − 1)2 B



2 ≤ 2E[(B − 1) ] = Eπ m 2

"

dν (ξ) − 1 dπ

2

#

2 ≤ Eπ m

"

dν (ξ) dπ

2

# .

(25)

The proof is completed by applying the triangle inequality to (23), then applying the bounds (24) and (25). Proof of proposition 2. Define: 



e k, τ ) := E log  R(ϕ;

k X

 e⟨ϕ(Z

a

),ϕ(Zj− )−ϕ(Z + )⟩/τ

 − log k,

(26)

j=1 iid

where Z a ∼ πdata , Z + ∼ M (Z a , ·) and Z1− , . . . , Zk− ∼ πdata , and decompose: Z  h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; k, τ ) E CrossEnt M τ,k

Z

Z = Z



h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; e k, τ ) E CrossEnt M τ,k

e k, τ ) − R(ϕ; k, τ ). + R(ϕ;

(27) (28)

e k, τ ), as follows: In order to bound the difference in (27), let us first write out an expression for R(ϕ; e k, τ ) R(ϕ; 



k 1X



− a 1 = − E[⟨ϕ(Z a ), ϕ(Z + )⟩] + E log  e⟨ϕ(Z ),ϕ(Zj )⟩/τ  τ k j=1    Z Z k X − a 1 1 =− ⟨ϕ(z), ϕ(z + )⟩M (z, dz + )πdata (dz) + E log  e⟨ϕ(Z ),ϕ(Zj )⟩/τ  , τ Z Z k j=1

14

(29)

where the first equality is just rearrangement of (26), the second equality holds since Z a ∼ πdata and Z + ∼ M (Z a , ·). Recalling the definitions: Pk dM (z,·) Pk ′ ⟨ϕ(z),ϕ(ξj )⟩/τ δξj (dz ′ ) j=1 dπdata (ξj )δξj (dz ) j=1 e ϕ ′ ′ c b . , Mk (z, dz ) := Qτ,k (z, dz ) := Pk P k dM (z,·) ⟨ϕ(z),ϕ(ξj )⟩/τ j=1 e j=1 dπdata (ξj ) and π bdata,k := k −1

iid j=1 δξj , where ξ1 , . . . , ξk ∼ πdata , we have:

Pk

b ϕ (z, ·) dQ τ,k db πdata,k

′

e⟨ϕ(z),ϕ(z )⟩/τ (z ′ ) = 1 Pk ⟨ϕ(z),ϕ(ξj )⟩/τ j=1 e k

z ′ ∈ {ξ1 , . . . , ξk },

for

(30)

ck (z, ·). Therefore noting {ξ1 , . . . , ξk } is a subset of, or equal to, the support of M Z  h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) E CrossEnt M τ,k Z " Z # Z b ϕ (z, ·) dQ τ,k ′ c ′ = (z )Mk (z, dz ) πdata (dz) E − log db πdata,k Z Z    Z  Z k X a 1 1 ck (z, dz ′ ) πdata (dz) + E log  e⟨ϕ(Z ),ϕ(ξj )⟩/τ  =− E ⟨ϕ(z), ϕ(z ′ )⟩M τ Z k j=1 Z    " Pk # Z dM (z,·) k X − a 1 1 j=1 ⟨ϕ(z), ϕ(ξj )⟩ dπdata (ξj ) =− E πdata (dz) + E log  e⟨ϕ(Z ),ϕ(Zj )⟩/τ  , Pk dM (z,·) τ Z k j=1 (ξj ) j=1 dπdata

h i ck (z, ·)∥Q b ϕ (z, ·) ; the second equality is obwhere the first equality holds by definition of CrossEnt M τ,k ck and using tained by substituting in (30); the third equality holds by substituting in the definition of M − − the fact that ξ1 , . . . , ξk and Z1 , . . . , Zk are identically distributed. Comparing with (29), we find: Z i  h ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; e k, τ ) E CrossEnt M τ,k Z " Pk # Z Z dM (z,·) 1 j=1 ⟨ϕ(z), ϕ(ξj )⟩ dπdata (ξj ) ≤ E − ⟨ϕ(z), ϕ(z + )⟩M (z, dz + ) πdata (dz). Pk dM (z,·) τ Z (ξ ) Z j j=1 dπdata In order to control the integrand for any fixed z, we apply lemma 3 with ν := M (z, ·), π := πdata and f (ξ) := ⟨ϕ(z), ϕ(ξ)⟩, which satisfies |f (ξ)| ≤ 1 as required since ϕ ∈ B(Z, Sd−1 ), yielding: " Pk # Z Z dM (z,·) 2 4 dM (z, ·) ′ j=1 ⟨ϕ(z), ϕ(ξj )⟩ dπdata (ξj ) + + E − ⟨ϕ(z), ϕ(z )⟩M (z, dz ) ≤ πdata (dz ′ ), (z ) Pk dM (z,·) k dπ data (ξj ) Z Z j=1 dπdata

and in turn: Z  h i ck (z, ·)∥Q b ϕ (z, ·) πdata (dz) − R(ϕ; e k, τ ) E CrossEnt M τ,k Z

≤

4 kτ

Z Z Z

Z

2

dM (z, ·) ′ (z ) πdata (dz ′ )πdata (dz). dπdata

This completes our treatment of the difference in (27). For the difference in (28), recalling the definitions e k, τ ) in (2) and (26), we have: of R(ϕ; k, τ ) and R(ϕ; e k, τ ) 0 ≤ R(ϕ; k, τ ) − R(ϕ;  

 1

= E log 1 + Pk

a

−

+

⟨ϕ(Z ),ϕ(Zj )−ϕ(Z )⟩/τ j=1 e

e2/τ ≤ log 1 + k 

 ,

15



where the first inequality uses monotonicity of log, the equality uses log(1/k + c) − log(c) = log(1 + 1/kc), and the second inequality uses ϕ ∈ B(Z, Sd−1 ). Having thus obtained bounds on the absolute values of the differences in (27)-(28), the proof is completed by applying the triangle inequality there. Lemma 4. For any ϕ ∈ B(Z, Sd−1 ), k ≥ 1 and τ > 0, Z e k, τ ) ≤ 2 . CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; τ Z Proof. Z

e k, τ ) CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; Z    Z  k X − + − + 1 e⟨ϕ(Z),ϕ(Zj )−ϕ(Z )⟩/τ  = E log e⟨ϕ(Z),ϕ(z )−ϕ(Z )⟩/τ πdata (dz − ) − E log k j=1 Z    Z  k X − − 1 e⟨ϕ(Z),ϕ(Zj )⟩/τ  = E log e⟨ϕ(Z),ϕ(z )⟩/τ πdata (dz − ) − E log k j=1 Z   R ⟨ϕ(Z),ϕ(z− )⟩/τ − 1/τ π (dz ) e 2 data  ≤ log e = E log Z Pk = , − −1/τ ⟨ϕ(Z),ϕ(Zj )⟩/τ 1 τ e e j=1

k

where the inequality holds since ∥ϕ(z)∥2 = 1 for all z.

A.1

Calculations for section 3.4

The bound in (12) is obtained as part of the proof of proposition 2, see (27) in particular. To check the bound in (11), write out the difference: Z e k, τ ) CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; Z Z  Z Z 1 + + ⟨ϕ(z),ϕ(z − )⟩/τ − =− ⟨ϕ(z), ϕ(z )⟩πdata (dz)M (z, dz ) + log e πdata (dz ) πdata (dz) τ Z Z   Z Z k X − 1 1 e⟨ϕ(Z),ϕ(Zj )⟩/τ  + ⟨ϕ(z), ϕ(z + )⟩πdata (dz)M (z, dz + ) − E log  τ Z k j=1    Z  Z k X − − 1 = log e⟨ϕ(z),ϕ(z )⟩/τ πdata (dz − ) − E log  e⟨ϕ(z),ϕ(Zj )⟩/τ  πdata (dz) k j=1 Z Z Z = log µ(z) − E[log µ b(z)] πdata (dz), (31) Z

where the final equality holds with the shorthand notation: k

Z µ(z) :=

e

⟨ϕ(z),ϕ(z − )⟩/τ

−

πdata (dz ),

Z

µ b(z) :=

1 X ⟨ϕ(z),ϕ(Zj− )⟩/τ e . k j=1

By Jensen’s inequality, log µ(z) ≥ E[log µ b(z)]. The upper-bound in (11) is derived by making a Taylor expansion of y 7→ log(y) similarly to as in the proof of lemma 2. The details are omitted, but in order to perform calculations for a specific example, consider the Taylor expansion up to third order (with z fixed): log µ b(z) = log µ(z) +

µ b(z) − µ(z) (b µ(z) − µ(z))2 (b µ(z) − µ(z))3 − + , 2 µ(z) 2µ(z) 3ξ 3

for some ξ on the line segment between µ(z) and µ b(z). 16

Using µ(z) ∨ µ b(z) ≤ e1/τ , we thus have: log µ(z) − E[log µ b(z)] ≥

µ(z) − µ(z)|3 ] E[(b µ(z) − µ(z))2 ] E[|b − . 2µ(z)2 3e3/τ

Since Z1− , . . . , Zk− are i.i.d., the Marcinkiewicz–Zygmund inequality gives E[|b µ(z)−µ(z)|3 ] = O(k −3/2 ) uniformly in z, and by direct calculation, E[(b µ(z) − µ(z))2 ] =

− 1 Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ], n

where Z1− ∼ πdata . This shows that −

k log µ(z) − kE[log µ b(z)] ≥

1 Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ] − O(k −1/2 ), 2 E[e⟨ϕ(z),ϕ(Z1− )⟩/τ ]2

(32)

as k → ∞.

A.2

An example −

−

Now let us construct an example for which we shall lower bound Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]/E[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]2 . The idea of the construction is to make |⟨ϕ(z), ϕ(Z1− )⟩| close to zero with probability close to 1, and otherwise ⟨ϕ(z), ϕ(Z1− )⟩ = 1. Assume e1/τ > 2 and define 1 ϵ := 1/τ , (33) ⌈e − 1⌉ so that ϵ ∈ (0, 1). Let δ ∈ (0, 1) and let d(δ) be large enough that there exist 1/ϵ vectors in Sd−1 which are δ-orthogonal, i.e., vectors u1 , . . . , u1/ϵ such that for i ̸= j, |⟨ui , uj ⟩| ≤ δ. Over the course of the following construction we shall consider taking δ → 0 and when we do it will be automatically assumed that d grows suitably fast as δ shrinks that 1/ϵ δ-orthogonal vectors exist (d = 1/ϵ is sufficient, since in that case the existence of 1/ϵ orthogonal vectors in Sd−1 is trivial, but we allow for δ-orthogonality rather than strict orthogonality to emphasise that d = 1/ϵ is not necessary for the construction). Suppose that πdata and ϕ are such that for Z ∼ πdata , the random vector ϕ(Z) is uniformly distributed on the set {u1 , . . . , u1/ϵ }. It follows that for any z ∈ Z and Zj− ∼ πdata , ⟨ϕ(z), ϕ(Zj− )⟩ = 1 with probability ϵ, and with probability 1 − ϵ, ⟨ϕ(z), ϕ(Zj− )⟩ = X0 for some random variable X0 such that |X0 | ≤ δ. We have:
2 − ϵ(1 − ϵ) e1/τ − E[eX0 /τ ] + (1 − ϵ)Var[eX0 /τ ] Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ] = .
2 − E[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]2 ϵe1/τ + (1 − ϵ)E[eX0 /τ ] As δ → 0 (with d increasing as necessary for the required number of δ-orthogonal vectors to exist), the r.h.s. of the above tends to:
2 ϵ(1 − ϵ) e1/τ − 1
2 . 1 + ϵ(e1/τ − 1) Therefore for any a ∈ (0, 1) we can choose δ > 0 small enough that: −

Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ] −

E[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]2

≥ (1 − a)

2 ϵ(1 − ϵ) e1/τ − 1
2 . 1 + ϵ(e1/τ − 1)

Using e1/τ > 2 and (33) we have: e1/τ − 1 1 ≤ ≤ ϵ(e1/τ − 1) ≤ 1, 2 e1/τ

17

and so:
2 (1 − ϵ) e1/τ − 1 ≥ (1 − a) − 4e1/τ E[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]2   (1 − a) 1/τ e1/τ − 1 ≥ e − 1 − 1/τ 8 ⌈e − 1⌉ (1 − a) 1/τ ≥ (e − 2). 8 −

Var[e⟨ϕ(z),ϕ(Z1 )⟩/τ ]

Combining with (31) and (32) we find that for this example: Z  e k, τ ) ≥ (1 − a) (e1/τ − 2), lim inf CrossEnt[M (z, ·)∥Qϕτ (z, ·)]πdata (dz) − R(ϕ; k→∞ 16 Z from which (13) follows by combining with (12).

B

Proofs and supporting results for section 4

Lemma 5. For any k ≥ 1, τ > 0, z ∈ Z 2+k , and ϕ, ϕ′ ∈ B(Z, Sd−1 ), |ℓ(ϕ, z, k, τ ) − ℓ(ϕ′ , z, k, τ )| ≤

4 . τ

Proof. Since ∥ϕ∥2,∞ = 1, we have:     1 1 −2/τ 2/τ log +e ≤ ℓ(ϕ, z, k, τ ) ≤ log +e , k k with the same inequality holding with ϕ replaced by ϕ′ . The claim of the lemma then follows by bounding:   1 + ke2/τ ′ |ℓ(ϕ, z, k, τ ) − ℓ(ϕ , z, k, τ )| ≤ log 1 + ke−2/τ    1 + ke2/τ = log e2/τ e2/τ + k   2/τ  + ke2/τ 4 2/τ e ≤ log e = , 1+k τ where the inequality uses e2/τ ≥ 1. h i bn (ϕ; k, τ ) , proposition 3 is almost a direct appliProof of proposition 3. Noting that R(ϕ; k, τ ) = E R cation of [Mohri et al., 2018, Thm. 3.3]. The latter theorem applies to sample averages of functions with co-domain [0, 1], whereas in the present setting we have lower and upper bounds:     1 1 + e−2/τ ≤ ℓ(ϕ, zi , k, τ ) ≤ log + e2/τ =: b, a := log k k which hold for any ϕ ∈ B(Z, Sd−1 ) and any zi ∈ Z 2+k . To obtain a function with co-domain [0, 1] denote: g(ϕ, zi ) :=

ℓ(ϕ, zi , k, τ ) − a , b−a

where the dependence Pn on τ, k is hidden for ease of presentation. An application of [Mohri et al., 2018, Thm. 3.3] to n−1 i=1 g(ϕ, Zi ) gives that with probability at least 1 − δ, for all ϕ ∈ Φ, s " # n n log 2δ 1X 1X E[g(ϕ, Z1 )] ≤ g(ϕ, Zi ) + 2E sup σi g(ϕ, Zi ) Z1 , . . . , Zn + 3 . (34) n i=1 2n ϕ∈Φ n i=1 18

Since Rademacher complexity of a class of functions is invariant to adding a constant scalar to every member of the class, and factorising out b − a, we have: # " # " n n 1 1X 1X σi g(ϕ, Zi ) Z1 , . . . , Zn = E sup σi ℓ(ϕ, Zi , k, τ ) Z1 , . . . , Zn . E sup b−a ϕ∈Φ n i=1 ϕ∈Φ n i=1 Substituting into (34), multiplying both sides of the inequality by b − a, adding a to both sides and recalling the definitions (2) and (1) gives: s " # n X log 2δ 1 bn (ϕ; k, τ ) + 2E sup R(ϕ; k, τ ) ≤ R σi ℓ(ϕ, Zi , k, τ ) Z1 , . . . , Zn + 3(b − a) . 2n ϕ∈Φ n i=1 The proof is completed by upper-bounding b − a as in the proof of lemma 5.

B.1

Supporting results and proof of proposition 4

A Gâteaux derivative can be thought of as a generalisation of the directional derivative in Euclidean space. We shall consider Gâteaux derivatives of functionals mapping B(Z, Rd ) into R. For such a functional, say H : B(Z, Rd ) → R, the Gâteaux derivative of H at f ∈ B(Z, Rd ) in direction η ∈ B(Z, Rd ) is the limit (if it exists): H(f + ϵη) − H(f ) . δH(f )[η] := lim ϵ→0 ϵ To prepare for the proof of proposition 4, we need the following definitions. For any τ > 0, x, y ∈ Z and µ ∈ P(Z), define the functionals Hτ (·, x, y, µ) : B(Z, Rd ) → R and Gτ (·, ·, x, y, µ) : B(Z, Rd ) × B(Z, Rd ) → Rd , Z Hτ (f, x, y, µ) := log e⟨f (x),f (z)−f (y)⟩/τ µ(dz). (35) Z R η(z)e⟨f (x),f (z)⟩/τ µ(dz) ZR := Gτ (f, η, µ, x) , (36) e⟨f (x),f (z)⟩/τ µ(dz) Z where in the numerator of (36) the vector-valued function η is integrated elementwise. Lemma 6. For any τ > 0, x, y ∈ Z and µ ∈ P(Z), the Gâteaux derivative of the functional Hτ (·, x, y, µ) at a point f ∈ B(Z, Rd ), in direction η ∈ B(Z, Rd ), is: δHτ (f, x, y, µ)[η] :=

1 [⟨η(x), Gτ (f, f, x, µ) − f (y)⟩ + ⟨f (x), Gτ (f, η, µ, x) − η(y)⟩] . τ

Proof. For brevity throughout the proof we write “derivative” instead of “Gâteaux derivative”. From (35) we have: Z 1 Hτ (f, x, y, µ) = − ⟨f (x), f (y)⟩ + log e⟨f (x),f (z)⟩/τ µ(dz). (37) τ Z Considering the first term on the l.h.s. of (37), for any ϵ > 0, 1 1 ϵ ϵ2 ⟨f (x) + ϵη(x), f (y) + ϵη(y)⟩ − ⟨f (x), f (y)⟩ = [⟨f (x), η(y)⟩ + ⟨η(x), f (y)⟩] + ⟨η(x), η(y)⟩ , τ τ τ τ then using Cauchy-Schwartz and ∥η∥2,∞ < ∞, the derivative of f 7→ τ1 ⟨f (x), f (y)⟩ in direction η is: 1

lim τ

ϵ→0

⟨f (x) + ϵη(x), f (y) + ϵη(y)⟩ − τ1 ⟨f (x), f (y)⟩ 1 = [⟨f (x), η(y)⟩ + ⟨η(x), f (y)⟩] . ϵ τ

(38)

To find the derivative of the second term on the r.h.s. of (37) we use the chain rule. So first consider the functional f 7→ Γ(f ) := e⟨f (x),f (z)⟩/τ (where dependence on τ , x and z is suppressed from the notation). Using (38) with y replaced by z, the derivative of Γ at f in direction η is: δΓ(f )[η] :=

1 [⟨f (x), η(z)⟩ + ⟨η(x), f (z)⟩] e⟨f (x),f (z)⟩/τ . τ 19

(39)

R Our next objective is to show that the derivative of f 7→ Z e⟨f (x),f (z)⟩/τ µ(dz) is given by (39) with z integrated out under µ. For this purpose we seek to apply the dominated convergence theorem, as follows. Fix any ϵ ∈ (0, 1], f ∈ B(Z, Rd ) and η ∈ B(Z, Rd ). By the mean value theorem there exists c ∈ [0, 1] such that by evaluating Γ(·)[ϵη] at the point: (1 − c)f + c (f + ϵη) = f + ϵcη, 1 ⟨f (x)+ϵη(x),f (z)+ϵη(z)⟩/τ e − e⟨f (x),f (z)⟩/τ ϵ 1 = |δΓ(f + ϵcη)[ϵη]| ϵ 1 |⟨f (x) + ϵcη(x), ϵη(z)⟩ + ⟨ϵη(x), f (z) + ϵcη(z)⟩| e⟨f (x)+ϵcη(x),f (z)+ϵcη(z)⟩/τ = τϵ 1 = |⟨f (x) + ϵcη(x), η(z)⟩ + ⟨η(x), f (z) + ϵcη(z)⟩| e⟨f (x)+ϵcη(x),f (z)+ϵcη(z)⟩/τ τ 2 1 ≤ [∥f + ϵcη∥2,∞ ∥η∥2,∞ + ∥η∥2,∞ ∥f + ϵcη∥2,∞ ] e(∥f ∥2,∞ +∥η∥2,∞ ) /τ τ 2 2 ≤ (∥f ∥2,∞ + ∥η∥2,∞ ) ∥η∥2,∞ e(∥f ∥2,∞ +∥η∥2,∞ ) /τ < ∞. τ Since ϵ was any value in (0, 1], the dominated convergenceR theorem allows interchange of integration and differentiation such that from (39) the derivative of f 7→ Z e⟨f (x),f (z)⟩/τ µ(dz) at f in direction η is: Z 1 [⟨f (x), η(z)⟩ + ⟨η(x), f (z)⟩] e⟨f (x),f (z)⟩/τ µ(dz). Z τ R By one further application of the chain rule, the derivative of f 7→ log Z e⟨f (x),f (z)⟩/τ µ(dz) in direction η is: R 1 [⟨f (x), η(z)⟩ + ⟨η(x), f (z)⟩] e⟨f (x),f (z)⟩/τ µ(dz) Z τ R e⟨f (x),f (z)⟩/τ µ(dz) Z 1 = [⟨f (x), Gτ (f, η, µ, x)⟩ + ⟨η(x), Gτ (f, f, µ, x)⟩] , (40) τ where the definition (36) has been used. Recalling (37), the proof is completed by subtracting (38) from (40). Lemma 7. For any k ≥ 1, τ > 0, β ≥ 1, x1 , . . . , xk ∈ [−1, 1] and a1 , . . . , ak ≥ 0, 1/β  Pk k xj /τ X aj 1 j=1 e β ≤ e2/(βτ )  aj  . Pk xj /τ k e j=1 j=1 Proof. Denote pj := exj /τ /

Pk

xi /τ . Since β ≥ 1, Jensen’s inequality gives: i=1 e

 β k k X X   pj aj ≤ pj aβj . j=1

j=1

Combining this inequality with the fact that pj ≤ e2/τ /k gives: 1/β  1/β  k k k X X X 1 aβj  . pj aj ≤  pj aβj  ≤ e2/(βτ )  k j=1 j=1 j=1

Lemma 8. For any k ≥ 1, τ > 0, (z a , z1− , . . . , zk− ) ∈ Z 1+k , ϕ, ϕ′ ∈ B(Z, Sd−1 ), f ∈ B(Z, Rd ) such that ∥f ∥2,∞ ≤ 1, and β ≥ 1,  1/β k X 1 ∥Gτ (f, ϕ − ϕ′ , π b, z a )∥2 ≤ e2/βτ  ∥ϕ(zj− ) − ϕ′ (zj− )∥β2  , k j=1 where π b := k −1

Pk

j=1 δzj− .

20

Proof. As in the statement, fix any k ≥ 1, τ > 0, (z a , z1− , . . . , zk− ) ∈ Z 1+k , ϕ, ϕ′ ∈ B(Z, Sd−1 ) and f ∈ B(Z, Rd ) such that ∥f ∥2,∞ ≤ 1. Define the shorthand: −

a

e⟨f (z ),f (zj )⟩/τ

pj := Pk

l=1 e

⟨f (z a ),f (zℓ− )⟩/τ

,

j = 1, . . . , k.

From the definition of Gτ in (36), Gτ (f, ϕ − ϕ′ , π b, z a ) =

k X

  pj ϕ(zj− ) − ϕ′ (zj− ) .

j=1

Now choose any β ≥ 1. By an application of the triangle inequality for the ∥ · ∥2 norm and lemma 7 with there xj = ⟨f (z a ), f (zj− )⟩ (so that xj ∈ [−1, 1] as required since by assumption of the present lemma ∥f ∥2,∞ ≤ 1), ∥Gτ (f, ϕ − ϕ′ , π b, z a )∥2 ≤

k X

 pj

j=1

1 ϕ(zj− ) − ϕ′ (zj− ) 2 ≤ e2/(βτ )  k

k X

1/β β ϕ(zj− ) − ϕ′ (zj− ) 2 

.

(41)

j=1

Proof of proposition 4. Fix any k, τ and z = (z a , z + , z1− , . . . , zk− ) ∈ Z 2+k as in the statement of the theorem. To lighten notation in the proof, for any f ∈ B(Z, Rd ) define the shorthand ℓ(f ) ≡ ℓ(f, z, k, τ ) Pk and H(f ) ≡ Hτ (f, z a , z + , π b− ), with π b− := k −1 j=1 δz+ and where Hτ is defined in (35). Observe then: j

 ℓ(f ) = log

 1 H(f ) +e . k

Denoting by δℓ(f )[η], δeH(f ) [η] and δH(f )[η] the Gâteaux derivatives of respectively f 7→ ℓ(f ), f 7→ eH(f ) and f 7→ H(f ) at a point f ∈ B(Z, Rd ) and in direction η ∈ B(Z, Rd ), the chain rule gives: δℓ(f )[η] =

eH(f ) 0 + δeH(f ) [η] = δH(f )[η]. 1/k + eH(f ) 1/k + eH(f )

(42)

Now fix any ϕ, ϕ′ ∈ B(Z, Sd−1 ). By the mean value theorem and (42), there exists c ∈ [0, 1], such that, with ξ := (1 − c)ϕ + cϕ′ ∈ B(Z, Rd ), ℓ(ϕ) − ℓ(ϕ′ ) = δℓ(ξ)[ϕ − ϕ′ ] =

eH(ξ) δH(ξ)[ϕ − ϕ′ ], 1/k + eH(ξ)

(43)

and by applying lemma 6 with there f = ξ, η = ϕ − ϕ′ , x = z a , y = z + , µ = π b− , τ δH(ξ)[ϕ − ϕ′ ]   = ϕ(z a ) − ϕ′ (z a ), Gτ (ξ, ξ, z a , π b) − ξ(z + ) + ξ(z a ), Gτ (ξ, ϕ − ϕ′ , π b, z a ) − ϕ(z + ) + ϕ′ (z + ) = ϕ(z a ) − ϕ′ (z a ), −ξ(z + ) + ϕ(z + ) − ϕ′ (z + ), −ξ(z a ) + ⟨ϕ(z a ) − ϕ′ (z a ), Gτ (ξ, ξ, π b, z a )⟩ + ⟨ξ(z a ), Gτ (ξ, ϕ − ϕ′ , π b, z a )⟩ = ϕ(z a ) − ϕ′ (z a ), −ξ(z + ) + ϕ(z + ) − ϕ′ (z + ), −ξ(z a ) + ⟨ϕ(z a ) − ϕ′ (z a ), Gτ (ξ, ξ, π b, z a ) − Gτ (ξ, ϕ − ϕ′ , π b, z a )⟩ a

a

′

′

a

a

+ ⟨ξ(z ) + ϕ(z ) − ϕ (z ), Gτ (ξ, ϕ − ϕ , π b, z )⟩ .

(44) (45) (46)

We shall apply the Cauchy-Schwartz inequality to each of the inner-products in (44)-(46). In preparation, observe that since ∥ϕ∥2,∞ = ∥ϕ′ ∥2,∞ = 1, we have: ∥ξ∥2,∞ ≤ 1

and

∥ξ − ϕ + ϕ′ ∥2,∞ ∨ ∥ξ + ϕ − ϕ′ ∥2,∞ ≤ 3.

(47)

Recalling the definition of Gτ in (36), note that Gτ is linear in its second argument. Combined with Jensen’s inequality, this gives: ∥Gτ (ξ, ξ, π b, z a ) − Gτ (ξ, ϕ − ϕ′ , π b, z a )∥2 = ∥Gτ (ξ, ξ − ϕ + ϕ′ , π b, z a )∥2 ≤ ∥ξ − ϕ + ϕ′ ∥2,∞ ≤ 3. 21

(48)

Since ∥ξ∥2,∞ ≤ 1 we may apply lemma 8 with there f = ξ to give, for any β ≥ 1,  ∥Gτ (ξ, ϕ − ϕ′ , π b, z a )∥2 ≤ e2/βτ 

k 1X

k j=1

1/β ∥ϕ(zj− ) − ϕ′ (zj− )∥β2 

.

(49)

Combining (43); the fact eH(ξ) /(1/k + eH(ξ) ) ≤ 1; application of the Cauchy-Schwartz inequality to each of the inner-products in (44)-(46); and the bounds (47), (48) and (49) gives: |ℓ(ϕ) − ℓ(ϕ′ )|  1/β k X 4 1 1 3 ≤ ∥ϕ(z a ) − ϕ′ (z a )∥2 + ∥ϕ(z + ) − ϕ′ (z + )∥2 + e2/βτ  ∥ϕ(zj− ) − ϕ′ (zj− )∥β2  . τ τ τ k j=1

B.2

Other proofs for section 4

Proof of lemma 1. It follows from proposition 4 that: |ℓ(ϕ, zi , k, τ ) − ℓ(ϕ′ , zi , k, τ )|  ≤



k 1X

4 + a ′ a ′ + 2/βτ  ∥ϕ(zi ) − ϕ (zi )∥2 + ∥ϕ(zi ) − ϕ (zi )∥2 + e τ k j=1

1/β   − − β ∥ϕ(zij ) − ϕ′ (zij )∥2 .

By applying the Lipschitz condition in assumption (C), |ℓ(ϕ, zi , k, τ ) − ℓ(ϕ′ , zi , k, τ )|  ≤



k X

4 1  CΦ ∥θ − θ′ ∥2 ∥zia ∥2 + ∥zi+ ∥2 + e2/βτ  τ k j=1

1/β   − β ∥zij ∥2 .

(50)

Applying the triangle inequality for the ∥ · ∥2 norm in Rn ,  1/β 2 1/2  n k X X 1  a   + 2/βτ  1 ∥z − ∥β     ∥zi ∥2 + ∥zi ∥2 + e n i=1 k j=1 ij 2 

≤

n 1X

n i=1

!1/2 ∥zia ∥22

+

n 1X

n i=1

!1/2 ∥zi+ ∥22

 2/β 1/2 n k X X  1 1 + e2/βτ  ∥z − ∥β   . n i=1 k j=1 ij 2 

(51)

Now set β = 1 ∨ 2/τ . When τ < 1 we have τ = 2/β < 1 and βτ = τ ∨ 2 = 2. In this case, by Jensen’s inequality,  2/β 1/2  1/β  τ /2 n k n X k n X k X X X X 1 1 1  2/τ 1 e2/βτ  ∥z − ∥β   ≤ e ∥z − ∥β  = e ∥z − ∥  . n i=1 k j=1 ij 2 nk i=1 j=1 ij 2 nk i=1 j=1 ij 2 

On the other hand, when τ ≥ 1, we have β ∈ [1, 2], 2/β ≥ 1 and βτ = τ ∨ 2 ≥ 2. In this case, by Jensen’s inequality,  2/β 1/2  1/2 n k n X k X X X 1 1  1 e2/βτ  ∥z − ∥β   ≤ e ∥z − ∥2  . n i=1 k j=1 ij 2 nk i=1 j=1 ij 2 

22

Combining the two cases: τ < 1 and τ ≥ 1,   2/β 1/2  (1∧τ )/2 n k n X k X X X 1  1 2/(1∧τ )  1 ≤ e ∥z − ∥β   e2/βτ  ∥z − ∥ . n i=1 k j=1 ij 2 nk i=1 j=1 ij 2

(52)

On both sides of (50), take the square, then the arithmetic average over the index i = 1, . . . , n, then take the square root. Combined with (51) and (52) this gives: ρinfo n (ϕθ , ϕθ ′ ) ≤

4e Bτ (z1 , . . . , zn )CΦ ∥θ − θ′ ∥2 . τ

Proof of proposition 5. Let Φ = {ϕθ ; θ ∈ Θ} as per assumption (C). As shorthand notation, let us absorb various quantities in the statement of lemma 1 into a constant L such that for all θ, θ′ ∈ Θ: ρinfo (ϕθ , ϕθ′ ) ≤ L∥θ − θ′ ∥2 .

(53)

If for some N ≥ 1 and ϵ > 0, {θ1 , . . . , θN } is an ϵ/L-cover of Θ with respect to the ∥ · − · ∥2 distance, then it follows from (53) that {ϕθ1 , . . . , ϕθN } is an ϵ-cover of Φ with respect to ρinfo . In turn, the associated covering numbers of Φ and Θ obey: N (ϵ, Φ, ρinfo ) ≤ N (ϵ/L, Θ, ∥ · − · ∥2 ). Combining this inequality with Dudley’s entropy integral, e.g., [Wainwright, 2019, eq. 5.48], # " n 1X σi ℓ(ϕ, zi , k, τ ) E sup ϕ∈Φ n i=1 Z τ4 ∧LR q 24 ≤√ log N (ϵ, Φ, ρinfo ) dϵ n 0 Z τ4 ∧LR p 24 ≤√ log N (ϵ/L, Θ, ∥ · − · ∥2 ) dϵ, n 0

(54)

where σ1 , . . . , σn are i.i.d. Rademacher variables; the integral upper-limit term 4/τ in the first inequality holds because by lemma 5, ρinfo (ϕ, ϕ′ ) ≤ 4/τ for all ϕ, ϕ′ ∈ Φ ⊂ B(Z, Sd−1 ); the integral upper-limit LR appears since by combining (53) with the definition of Θ to we have ρinfo (ϕθ , ϕθ′ ) ≤ LR. We have the standard Euclidean volumetric estimate: N (ϵ, Θ, ∥ · − · ∥2 ) ≤ (1 + 2R/ϵ)dΘ , see, e.g., [Wainwright, 2019, eq. 5.9]. Writing U := 4/τ ∧ LR, Cauchy-Schwartz gives: !1/2 Z !1/2 Z Up Z U U log N (ϵ/L, Θ, ∥ · − · ∥2 ) dϵ ≤ 12 dϵ log N (ϵ/L, Θ, ∥ · − · ∥2 ) dϵ 0

0

p ≤ U dΘ

0

Z U

!1/2 log(1 + 2RL/ϵ) dϵ

0

    1/2 p 2RL U U dΘ U log 1 + + 2RL log 1 + U 2RL     1/2 p 2RL +1 , ≤ U dΘ log 1 + U =

where the equality uses the fact that the anti-derivative in question is ϵ log(1 + 2RL/ϵ) + 2RL log(1 + ϵ/2RL), and the final inequality uses log(1 + x) ≤ x for x ≥ 0. Returning to (54) in the case 4/τ ≤ RL, we have U = 4/τ and: # " √    1/2 n 2RL 1X 24 dΘ 4 σi ℓ(ϕ, zi , k, τ ) ≤ √ log 1 + +1 E sup 4/τ n τ ϕ∈Φ n i=1 √ 24 dΘ 4 1/2 = √ [log (1 + 2a) + 1] , n τ 23

where L = 4eBτ (z1 , . . . , zn )CΦ /τ (from lemma 1) has been used and a := eRBτ (z1 , . . . , zn )CΦ . On the other hand, if 4/τ > RL, we have U = RL and # " √ n 24 dΘ 1X 1/2 σi ℓ(ϕ, zi , k, τ ) ≤ √ RL [log(3) + 1] E sup n n ϕ∈Φ i=1 √ 24 dΘ 4 ≤ √ a[log(3) + 1]1/2 . n τ Since 4/τ > RL ⇔ 1 > eRBτ (z1 , . . . , zn )CΦ ⇔ 1 > a, we obtain # " r n n p o p 96 dΘ 1X σi ℓ(ϕ, zi , k, τ ) ≤ min a log(3) + 1, log(1 + 2a) + 1 . E sup τ n ϕ∈Φ n i=1

References Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalized margin bounds for neural networks. Advances in Neural Information Processing Systems, 30, 2017. Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1597–1607. PMLR, 2020. Naghmeh Ghanooni, Waleed Mustafa, Yunwen Lei, Anthony Widjaja Lin, and Marius Kloft. Generalization bounds with logarithmic negative-sample dependence for adversarial contrastive learning. Transactions on Machine Learning Research, 2024. Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Proceedings of the 31st Conference On Learning Theory, pages 297–299. PMLR, 2018. Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and Rémi Gribonval. A rescaling-invariant lipschitz bound based on path-metrics for modern relu network parameterizations. In International Conference on Machine Learning, pages 20047–20074. PMLR, 2025. Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9729–9738. IEEE, 2020. doi: 10.1109/cvpr42600.2020.00975. Olivier Henaff. Data-efficient image recognition with contrastive predictive coding. In International Conference on Machine Learning, pages 4182–4192. PMLR, 2020. Nong Minh Hieu and Antoine Ledent. Generalization analysis for supervised contrastive representation learning under non-iid settings. In International Conference on Machine Learning, pages 23179–23218. PMLR, 2025. Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in Neural Information Processing Systems, 33:18661–18673, 2020. Yunwen Lei, Ürün Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5):2995–3021, 2019. Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou. Generalization analysis for contrastive representation learning. In International Conference on Machine Learning, pages 19200–19227. PMLR, 2023. Andreas Maurer. A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pages 3–17. Springer, 2016.

24

Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018. Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376–1401. PMLR, 2015. Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8748–8763. PMLR, 2021. doi: 10.48550/arxiv.2103.00020. Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar. A theoretical analysis of contrastive unsupervised representation learning. In International Conference on Machine Learning, pages 5628–5637. PMLR, 2019. Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In European conference on computer vision, pages 776–794. Springer, 2020. Aäron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018. Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019. Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 2020a. Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere, 2020b. URL https://arxiv.org/abs/2005.10242v10. Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via nonparametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733–3742, 2018. Ge Yang, Edward Hu, Igor Babuschkin, Szymon Sidor, Xiaodong Liu, David Farhi, Nick Ryder, Jakub Pachocki, Weizhu Chen, and Jianfeng Gao. Tuning large neural networks via zero-shot hyperparameter transfer. Advances in Neural Information Processing Systems, 34:17084–17097, 2021. Chun-Hsiao Yeh, Cheng-Yao Hong, Yen-Chi Hsu, Tyng-Luh Liu, Yubei Chen, and Yann LeCun. Decoupled contrastive learning. In European conference on computer vision, pages 668–684. Springer, 2022. Roland S. Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In International Conference on Machine Learning, pages 12979–12990. PMLR, 2021.

25