📊 statistics

Similarity search generalisation in contrastive learning with InfoNCE loss

This paper establishes that the InfoNCE loss with $k$ negative samples approximates an expected cross-entropy quantifying similarity search deviation and introduces a novel continuity bound via Gâteaux differentiation to demonstrate that increasing the number of negative samples stabilizes generalization error for Lipschitz embedding functions.

Original authors: Nick Whiteley

Published 2026-07-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nick Whiteley

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot to understand what "similar" means. You show it a picture of a cat (the anchor) and then a slightly different picture of the same cat (the positive). You also show it a bunch of pictures of dogs, cars, and bananas (the negatives). The robot's job is to learn a special "embedding" (a mathematical map) that pulls the two cat pictures close together and pushes the dogs far away.

The tool the robot uses to learn this is called InfoNCE. It's like a game where the robot gets a score based on how well it separates the cats from the noise. But here's the big question: If the robot learns this game perfectly on the pictures you showed it, will it actually be good at finding similar things in the real world (unseen data) that it has never seen before?

This paper, written by Nick Whiteley, dives deep into that question. It doesn't just say "it works"; it tries to explain why it works and how the number of "noise" pictures (negative samples) changes the game.

The Magic of the "Noise" Crowd

In the InfoNCE game, you usually give the robot a few negative samples (maybe 10 or 100). But in the real world, there are infinite possibilities. What happens if you give the robot a massive crowd of negative samples?

The paper proves something very specific: As you increase the number of negative samples ( $k$ ), the robot's performance gets closer and closer to a perfect "ideal" search.

Think of it like this:

The Ideal Search: Imagine a magical librarian who knows exactly how the universe generates "positive" pairs (like the cat and its twin). This librarian can instantly tell you the perfect similarity between any two things.
The Robot's Search: The robot uses its learned map to guess the similarity.
The Connection: The paper shows that the difference between the robot's guess and the magical librarian's perfect answer shrinks very fast as you add more negative samples. Specifically, the error drops at a rate of $O(1/k)$ .

This means if you double the number of negative samples, you cut the error in half. If you have 1,000 negatives, the error is tiny. This is a proven mathematical fact in the paper, not just a guess. It corrects an older idea that suggested the error might drop slower (like $1/\sqrt{k}$ ). The author shows that with the right math, it's actually much faster: $1/k$ .

The Temperature Knob

There is another character in this story: the temperature parameter ( $\tau$ ). Imagine this as a "focus knob" on the robot's brain.

If the temperature is low, the robot is very picky. It only cares about the most similar things and ignores the rest.
If the temperature is high, the robot is more relaxed and considers a wider range of similarities.

The paper proves that this knob acts as a regularizer. If you turn the temperature up (make it high), the robot's map is forced to stay closer to the average distribution of all data, preventing it from getting too crazy or overfitting to weird outliers. The paper explicitly states that the higher the temperature, the more the robot's search behavior is constrained to be close to the general data distribution, no matter how the robot is configured.

The "Averaging" Superpower

One of the most exciting findings is about generalization—how well the robot performs on new, unseen data.

Previous theories suggested that adding more negative samples might make the math messy and harder to control. But this paper argues the opposite. It introduces a new mathematical tool (using something called Gâteaux differentiation) to show that the "averaging" effect of the negative samples in the loss function actually stabilizes the robot's performance.

Think of it like taking a poll. If you ask one person, their opinion might be wild. If you ask 10, it's better. If you ask 1,000, the average opinion becomes very stable and reliable. The paper proves that the InfoNCE loss function works exactly like this poll. As $k$ grows, the "noise" of individual bad samples gets averaged out, and the robot's ability to generalize to new data stabilizes.

What the Paper Rules Out

It is important to note what this paper says is not the answer:

It argues against the idea that the error rate drops slowly (like $1/\sqrt{k}$ ) when $k$ gets large. The paper proves it drops faster ( $1/k$ ).
It does not rely on the assumption that the "positive" and "negative" samples come from the exact same distribution in a symmetric way. The paper explicitly rejects the idea that we need to assume the positive samples are just random draws from the same pool as the negatives. In the real world, positive pairs are created by specific transformations (like cropping a photo), and the paper handles this "black box" reality without forcing it into a perfect symmetry.
It does not claim that the robot needs to be a specific type of neural network (like a deep CNN). The results hold for any embedding function that is "Lipschitz" (meaning it doesn't change too wildly), which includes many types of networks, but the proof is general.

How Sure Are We?

The authors are very sure about the core mechanics. They have mathematically proven (using rigorous calculus and probability theory) that:

The error between the robot's search and the ideal search is $O(1/k)$ .
The generalization error (how well it works on new data) stabilizes as $k$ grows because of the averaging effect.
The temperature parameter $\tau$ plays a specific, predictable role in constraining the search.

They do not rely on simulations or experiments to make these claims; they are derived from first principles. However, they do note that for very complex, deep neural networks, the bounds might become "vacuous" (too loose to be useful) unless the network is very large or the data is huge. They suggest that future work could combine their new math with other techniques to handle those massive networks better.

The Big Picture

In simple terms, this paper tells us that the InfoNCE loss function is a very robust tool. It's not just a heuristic that "works well in practice." It has a deep theoretical foundation:

It learns to approximate an ideal similarity search.
The more negative samples you throw at it, the faster it converges to that ideal.
The averaging of those samples naturally protects the model from overfitting, making it reliable on unseen data.

So, the next time you see a system using contrastive learning to find similar images or texts, remember: it's essentially running a massive, mathematically proven poll of "what's similar," and the more people (negative samples) it asks, the more accurate the answer becomes.

Technical Summary: Similarity Search Generalisation in Contrastive Learning with InfoNCE Loss

Problem Statement
Contrastive learning, particularly using the InfoNCE loss, is a foundational technique for training embedding models used in similarity search. While the theoretical understanding of InfoNCE has advanced significantly in the limit of infinite negative samples ( $k \to \infty$ )—often framed in terms of mutual information maximization or the balance between alignment and uniformity—there is a gap in understanding how the finite- $k$ regime relates to the generalization performance of similarity search on unseen data. Existing generalization analyses have largely focused on downstream classification tasks, where bounds often depend explicitly on $k$ in ways that seem to contradict empirical observations that large $k$ improves performance. Furthermore, the behavior of the population risk as it converges to an idealized similarity search metric, and how this convergence stabilizes generalization error, requires clarification.

Methodology
The paper adopts a measure-theoretic framework to analyze the InfoNCE loss without assuming specific neural network architectures or gradient descent algorithms. The core methodology involves:

Probabilistic Formulation: The training data is modeled as i.i.d. tuples consisting of an anchor, a positive sample (generated via a Markov kernel $M$ ), and $k$ negative samples (drawn from a data distribution $\pi_{data}$ ). The embedding function $\phi$ maps inputs to the unit sphere $S^{d-1}$ .
Markov Kernel Interpretation: The authors define a Markov kernel $Q^\phi_\tau$ representing a softmax similarity search over the data distribution. They also define an empirical counterpart $\hat{Q}^\phi_{\tau, k}$ based on unseen data.
Continuity Bounds via Gâteaux Differentiation: A novel continuity bound for the InfoNCE loss is derived using Gâteaux differentiation. Unlike previous approaches that rely on the Lipschitz continuity of the logistic loss (which often leads to maximization over negative samples), this bound preserves the averaging structure inherent in the InfoNCE loss. It introduces an "inverse temperature" parameter $\beta$ to tune the bound relative to the algorithmic temperature $\tau$ .
Rademacher Complexity Analysis: The derived continuity bound is applied to bound the empirical Rademacher complexity of the InfoNCE loss for embedding functions that are Lipschitz in their parameters. This allows for a generalization bound that explicitly tracks the role of $k$ .

Key Contributions

Convergence Rate of Population Risk: The paper establishes that the population risk of the InfoNCE loss converges to the cross-entropy between the positive sample generator kernel $M$ and the softmax search kernel $Q^\phi_\tau$ at a rate of $O(1/k)$ . This refines previous results that reported $O(1/\sqrt{k})$ .
Similarity Search Generalization Interpretation: A new interpretation is provided where the population risk is shown to be $O(1/k)$ close to the expected cross-entropy between an empirical softmax kernel (built from unseen data) and an idealized empirical kernel representing the implicit similarity defined by the positive sample generator. This frames InfoNCE minimization as learning a similarity search mechanism that approximates the implicit structure of the data generation process.
Novel Continuity Bound: The authors introduce a continuity bound (Proposition 4) that maintains the averaging structure of the negative samples. This contrasts with standard Lipschitz-based bounds which resort to maximization over negative samples, a distinction that is crucial for the subsequent generalization analysis.
Stabilization of Generalization Error: By applying the new continuity bound to Lipschitz embedding classes, the paper demonstrates that the averaging effect of $k$ negative samples in the loss function translates directly to the stabilization of the generalization error (Rademacher complexity) as $k$ grows. This provides a theoretical justification for the empirical observation that increasing the number of negative samples improves generalization.

Results

Theorem 1 (Combined Bound): The paper synthesizes its findings into a comprehensive generalization bound. It decomposes the difference between the expected cross-entropy of similarity search on unseen data and the empirical risk into three components:
1. Sample Variability: $O(n^{-1/2})$ , independent of $k$ .
2. Complexity Penalty: $O(n^{-1/2})$ , which stabilizes as $k \to \infty$ due to the averaging structure in the bound.
3. Finite $k$ Bias: $O(1/k)$ , representing the deviation between the finite- $k$ population risk and the idealized similarity search metric.
Temperature Sensitivity: The analysis highlights that the generalization bound becomes increasingly sensitive to the norms of negative samples as the temperature $\tau$ approaches zero, suggesting that lower temperatures may lead to larger generalization errors if negative sample norms are large.
Dimension Independence: The derived bounds for embedding functions on the sphere $S^{d-1}$ do not explicitly depend on the embedding dimension $d$ , contrasting with bounds for unconstrained embeddings.

Significance
The paper claims to provide a clearer theoretical understanding of InfoNCE by shifting the focus from downstream classification to the primary application of similarity search. By establishing an $O(1/k)$ convergence rate and demonstrating that the averaging over negative samples stabilizes generalization error, the work offers a theoretical basis for the practical necessity of large numbers of negative samples in contrastive learning. The new continuity bound, derived via Gâteaux differentiation, is presented as a technical tool that preserves the structural properties of the InfoNCE loss, enabling more precise generalization analysis than previous Lipschitz-based methods. The results are framed as algorithm-agnostic, applying to any embedding function obtained via empirical risk minimization within the specified function classes.