Similarity search generalisation in contrastive learning with InfoNCE loss

• URL: http://arxiv.org/abs/2607.09405v1
• Date: Fri, 10 Jul 2026 13:37:41 GMT
• Title: Similarity search generalisation in contrastive learning with InfoNCE loss
• Abstract summary: Similarity search is a primary application of embedding models trained by contrastive learning.<n>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.<n>We show that the averaging effect of $k$ negative samples in the InfoNCE loss carries over to stabilisation of the generalisation error as $k$ grows.
• Score: 3.780240063064779
• License: http://creativecommons.org/licenses/by/4.0/
• 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\to\infty$ 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.

Related papers

• Posterior Information Dynamics of Diffusion Models for Linear Inverse Problems [11.548853370822343]
  We study the process through the smoothed likelihood force, the difference between exact posterior and prior scores at each noise level.<n>Averaging over measurements yields an information--minimum mean-square error (I-MMSE) identity linking information gain to denoising-error reduction.
  arXiv  Detail & Related papers  (2026-08-22T00:53:42Z)
• On Pairwise Quantile Regression -- Statistical Guarantees and Applications [0.0]
  Quantile regression provides a powerful tool for summarizing the conditional distribution of a real valued random variable (r.v.) of interest.<n>This article aims to extend this methodology to the pairwise case, when the variable to be explained takes the form of a similarity function between two independent observations.
  arXiv  Detail & Related papers  (2026-07-05T17:51:59Z)
• The Measure of Deception: An Analysis of Data Forging in Machine Unlearning [2.141079906482723]
  Key challenge in verifying unlearning is forging.<n>A key challenge in verifying unlearning is forging, adversarially crafting data that mimics bounds of a target point.<n>We show that adversarial forging is fundamentally limited and that false unlearning claims can, in principle, be detected.
  arXiv  Detail & Related papers  (2025-09-06T23:44:05Z)
• Dimension-free Score Matching and Time Bootstrapping for Diffusion Models [19.62665684173391]
  Diffusion models generate samples by estimating the score function of the target distribution at various noise levels.<n>We introduce a martingale-based error decomposition and sharp variance bounds, enabling efficient learning from dependent data.<n>Building on these insights, we propose Bootstrapped Score Matching (BSM), a variance reduction technique that leverages previously learned scores to improve accuracy at higher noise levels.
  arXiv  Detail & Related papers  (2025-02-14T18:32:22Z)
• Denoising Score Matching with Random Features: Insights on Diffusion Models from Precise Learning Curves [8.038035670274706]
  Empirical studies suggest that generalization and memorization are influenced by model complexity and the size of the training dataset.<n>We capture these behaviors by derivingally precise expressions for test and train errors of Denoising Score Matching (DSM) under a simple theoretical setting.<n>Our theoretical findings are consistent with the empirical observations.
  arXiv  Detail & Related papers  (2025-02-01T06:43:33Z)
• Asymptotic Characterisation of Robust Empirical Risk Minimisation Performance in the Presence of Outliers [18.455890316339595]
  We study robust linear regression in high-dimension, when both the dimension $d$ and the number of data points $n$ diverge with a fixed ratio $alpha=n/d$, and study a data model that includes outliers. We provide exacts for the performances of the empirical risk minimisation (ERM) using $ell$-regularised $ell$, $ell_$, and Huber losses.
  arXiv  Detail & Related papers  (2023-05-30T12:18:39Z)
• Not All Semantics are Created Equal: Contrastive Self-supervised Learning with Automatic Temperature Individualization [51.41175648612714]
  We propose a new robust contrastive loss inspired by distributionally robust optimization (DRO) We show that our algorithm automatically learns a suitable $tau$ for each sample. Our method outperforms prior strong baselines on unimodal and bimodal datasets.
  arXiv  Detail & Related papers  (2023-05-19T19:25:56Z)
• Boosting Differentiable Causal Discovery via Adaptive Sample Reweighting [62.23057729112182]
  Differentiable score-based causal discovery methods learn a directed acyclic graph from observational data. We propose a model-agnostic framework to boost causal discovery performance by dynamically learning the adaptive weights for the Reweighted Score function, ReScore.
  arXiv  Detail & Related papers  (2023-03-06T14:49:59Z)
• Score-based Continuous-time Discrete Diffusion Models [102.65769839899315]
  We extend diffusion models to discrete variables by introducing a Markov jump process where the reverse process denoises via a continuous-time Markov chain. We show that an unbiased estimator can be obtained via simple matching the conditional marginal distributions. We demonstrate the effectiveness of the proposed method on a set of synthetic and real-world music and image benchmarks.
  arXiv  Detail & Related papers  (2022-11-30T05:33:29Z)
• Attentional-Biased Stochastic Gradient Descent [74.49926199036481]
  We present a provable method (named ABSGD) for addressing the data imbalance or label noise problem in deep learning. Our method is a simple modification to momentum SGD where we assign an individual importance weight to each sample in the mini-batch. ABSGD is flexible enough to combine with other robust losses without any additional cost.
  arXiv  Detail & Related papers  (2020-12-13T03:41:52Z)
• Evaluating representations by the complexity of learning low-loss predictors [55.94170724668857]
  We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learning a predictor on top of the representation that achieves low loss on a task of interest.
  arXiv  Detail & Related papers  (2020-09-15T22:06:58Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  We develop a methodology to compute precisely the full distribution of test errors among interpolating classifiers. We find that test errors tend to concentrate around a small typical value $varepsilon*$, which deviates substantially from the test error of worst-case interpolating model. Our results show that the usual style of analysis in statistical learning theory may not be fine-grained enough to capture the good generalization performance observed in practice.
  arXiv  Detail & Related papers  (2020-06-22T21:12:31Z)
• A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent [85.77233010209368]
  This article characterizes the exacts of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples $n$ is all large and comparable. This analysis also provides accurate estimates of training and test regression errors for large $n,p,N$.
  arXiv  Detail & Related papers  (2020-06-09T02:05:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.