Pith. sign in

REVIEW 1 major objections 5 minor 25 references

InfoNCE population risk is O(1/k)-close to expected cross-entropy of softmax similarity search, and averaging over negatives stabilises generalisation.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-13 03:14 UTC pith:SZVC7Z2Y

load-bearing objection Clean finite-k theory that ties InfoNCE to similarity search and removes the spurious √k growth in generalisation bounds. the 1 major comments →

arxiv 2607.09405 v1 pith:SZVC7Z2Y submitted 2026-07-10 cs.LG stat.ML

Similarity search generalisation in contrastive learning with InfoNCE loss

Nick Whiteley This is my paper
classification cs.LG stat.ML
keywords InfoNCEcontrastive learningsimilarity searchgeneralisation boundsRademacher complexityGâteaux derivativetemperature parameternegative samples
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper reinterprets the InfoNCE loss of contrastive learning as a statement about similarity search on unseen data. With k negative samples, the population risk is shown to sit within O(1/k) of an expected cross-entropy that measures how far a softmax search performed with the learned embedding sits from an idealised search that uses the similarity already encoded in the positive-sample generator. Existing large-k stories (mutual information, alignment/uniformity) are therefore complemented by a finite-k, search-centric picture. A new continuity bound obtained by Gâteaux differentiation keeps the averaging structure over the negatives and introduces a tunable inverse-temperature parameter. When the embedding class is Lipschitz in its parameter, that averaging carries over to the empirical Rademacher complexity, so generalisation error stabilises rather than grows as k increases. The combined bound therefore decomposes the gap between empirical training risk and ideal similarity-search performance into three transparent terms: sample variability, complexity, and finite-k bias, all of which improve or remain controlled when more negatives are used.

Core claim

The population InfoNCE risk with k negatives is O(1/k)-close, uniformly over embeddings, to the expected cross-entropy between the empirical softmax Markov kernel built from k unseen points and the idealised importance-weighted kernel induced by the positive-sample generator M; a Gâteaux continuity bound that retains averaging over those negatives then implies that the Rademacher complexity of Lipschitz embeddings stabilises as k grows.

What carries the argument

The Gâteaux continuity bound of Proposition 4: it differentiates the InfoNCE loss functional, preserves the power-mean average over the k negative samples, and introduces a free inverse-temperature parameter β that can be set to match the algorithmic temperature τ, converting the averaging present in the loss into a matching average inside the Rademacher estimate.

Load-bearing premise

The embedding class must be Lipschitz in a Euclidean parameter with a constant that multiplies the input norm; without that strong Lipschitz control the covering-number argument that turns the continuity bound into a stabilising Rademacher estimate fails.

What would settle it

Construct or train a Lipschitz embedding family on data whose negative-sample norms do not concentrate, then check whether measured generalisation gap continues to fall or level off as k is increased while n and τ are held fixed; any systematic growth would contradict the stabilisation claim of Proposition 5 and Theorem 1.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Minimising InfoNCE with large k is equivalent, up to vanishing bias, to making softmax similarity search on unseen data match the similarity already present in the positive-sample generator.
  • Generalisation error for Lipschitz embeddings does not grow with the number of negatives; the usual √k factors that appear in earlier bounds are artefacts of maximisation rather than averaging.
  • Temperature τ appears both as an explicit prefactor and inside a power-mean of negative-sample norms, so lower temperature makes the generalisation bound more sensitive to large-norm negatives.
  • The same continuity bound applies to the decoupled contrastive loss (DCL) and removes the extra log(1+e^{2/τ}/k) term, tightening the finite-k bias.
  • Early stopping of any optimiser that keeps the parameter inside a ball of radius R automatically regularises the Rademacher complexity to zero as R o0.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The search-centric view suggests that evaluation protocols for contrastive models should report retrieval or ranking metrics on held-out data rather than only linear-probe classification accuracy.
  • If the positive-sample Markov kernel M is itself learned or heavily engineered, the idealised kernel cM_k becomes a natural diagnostic: large residual cross-entropy after training would indicate that the embedding cannot represent the intended notion of similarity.
  • The same Gâteaux technique may extend to other softmax-style losses (e.g., multi-class or multi-positive contrastive objectives) whenever an average over a growing set of terms is present inside a logarithm.
  • Because the bound is free of embedding dimension, sphere-valued embeddings enjoy a structural advantage over unconstrained Euclidean embeddings of growing dimension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper reinterprets the InfoNCE population risk for contrastive learning through the lens of similarity search. It proves that R(ϕ; k, τ) is O(1/k)-close (uniformly in ϕ ∈ B(Z, S^{d-1})) to the π_data-integrated cross-entropy between the positive-sample Markov kernel M and the softmax kernel Q_ϕ_τ (Proposition 1), and likewise O(1/k)-close to the expected empirical cross-entropy between the idealised importance-weighted kernel ĉM_k and the empirical softmax kernel bQ_ϕ_τ,k built from k unseen draws (Proposition 2, under domination (B)). A new continuity bound for the InfoNCE loss is obtained via Gâteaux differentiation (Proposition 4); the bound retains a power-mean average over the k negatives and an inverse-temperature parameter β. For embedding classes that are Lipschitz in a Euclidean parameter (Assumption (C)), this yields an empirical Rademacher complexity bound that stabilises as k grows (Lemma 1, Proposition 5), which is assembled into a combined similarity-search generalisation statement (Theorem 1). Parallel sharper statements are given for the DCL loss.

Significance. The work supplies a clean, quantitative bridge between InfoNCE and the primary downstream use of the learned embeddings—softmax similarity search on unseen data—complementing the classical mutual-information, alignment-uniformity and density-inversion interpretations that are phrased only in the k → ∞ limit. The O(1/k) rate improves on the previously reported O(1/√k) and is shown to be essentially sharp for DCL via an explicit construction. The Gâteaux continuity bound is technically novel: it preserves the averaging structure of the loss and thereby explains why large k can stabilise generalisation error for Lipschitz embeddings, addressing a tension with earlier Rademacher analyses that retained explicit √k or max-over-k factors. All claims are proved in the appendix with standard tools (Taylor expansion with remainder, Popoviciu, dominated convergence for Gâteaux derivatives, Dudley entropy integral). The finite-k bias terms and the counter-example for exponential temperature dependence are carefully derived. These are genuine contributions to the theoretical understanding of contrastive learning.

major comments (1)
  1. Assumption (C) (Section 4.2) is used only to convert Proposition 4 into a concrete covering-number bound; the continuity statement itself is distribution-free. Nevertheless, the resulting Rademacher estimate (Proposition 5) inherits an explicit √d_Θ factor and a data-dependent term B_τ that can grow with the norms of the negative samples. For wide/deep networks this can render the bound vacuous unless n is enormous, a limitation the authors themselves note in Section 5. A short remark clarifying that the stabilisation-with-k claim is demonstrated only inside the Lipschitz-parameter regime, and that path-metric or spectral-norm techniques would be needed for modern architectures, would prevent over-reading of Theorem 1.
minor comments (5)
  1. Throughout the manuscript the Gâteaux symbol appears with encoding artefacts (“Gˆ ateaux”). Please normalise to “Gâteaux”.
  2. In the definition of ℓ (Eq. 14) the factor 1/k is written inside the log; the subsequent population risk (Eq. 2) subtracts log k. A one-sentence reminder that the two normalisations differ only by a constant would help readers who jump between sections.
  3. Proposition 2 sets the number of unseen points m equal to the number of negatives k for analytic convenience. The authors note that the general m ≠ k case is similar but omit the bound; a short appendix statement of the m-dependent remainder would make the similarity-search interpretation more immediately usable.
  4. The numerical constant 65 appearing in the DCL sharpness example (Eq. 13) is acknowledged to be non-optimal. Either improve it or replace the concrete number by a generic O(1) factor to avoid the impression of a sharp constant.
  5. References: the arXiv version of Wang & Isola (2020b) is cited for the O(1/√k) rate; the published ICML version should be preferred if the rate statement is identical.

Circularity Check

0 steps flagged

No circularity: pure mathematical derivation of approximation rates and continuity bounds from the InfoNCE definition, with no fitted parameters, self-referential uniqueness claims, or tautological reductions.

full rationale

The paper's central claims are quantitative approximation statements (Propositions 1–2: population InfoNCE risk R(ϕ;k,τ) is O(1/k)-close to integrated/expected cross-entropies of the Markov kernels Q_ϕ_τ and ĉM_k) and a Gâteaux-derived continuity bound (Proposition 4) that retains the negative-sample average, which is then fed into a standard Rademacher + covering-number argument under the Lipschitz assumption (C) to obtain Proposition 5 and Theorem 1. All steps start from the explicit definitions of the loss (1)–(2), the kernels (5)–(6) and (9)–(10), and elementary analytic tools (Taylor expansion with remainder, Popoviciu variance bound, dominated convergence for Gâteaux derivatives, Jensen, Cauchy–Schwarz). The kernels are constructed from the same objects that appear in the loss, yet the O(1/k) statements are non-identity comparisons proved by explicit remainder estimates (Lemmas 2–3); they are not forced by construction. No parameters are fitted to data, no uniqueness theorem is imported from the author's prior work, and the references that supply background interpretations (van den Oord et al., Wang & Isola, Zimmermann et al., Saunshi et al., Lei et al.) are external. The derivation is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 1 invented entities

The paper rests on three standing modelling assumptions (A–C) that are standard or mild in the contrastive-learning literature, plus classical analytic tools (Gâteaux derivatives, covering numbers, Rademacher complexity). No numerical constants are fitted to data; temperature τ is an algorithmic hyper-parameter, not a free parameter of the theory. The Markov kernels are definitional constructs, not new physical entities.

axioms (4)
  • domain assumption Training tuples are i.i.d.; within each tuple the negatives are i.i.d. from the same distribution as the anchor (Assumption A).
    Used for the population-risk identities and for the standard Rademacher generalisation bound (Prop. 3).
  • domain assumption The positive-sample kernel M(z,·) is absolutely continuous w.r.t. the data measure π_data for every z (Assumption B).
    Needed only for the finite-k similarity-search interpretation (Prop. 2) so that importance weights exist.
  • domain assumption The embedding class is parametrised by a Euclidean ball and is Lipschitz in the parameter with a factor linear in the input norm (Assumption C).
    Converts the abstract continuity bound into a concrete covering-number estimate (Lemma 1, Prop. 5).
  • standard math Standard facts from empirical-process theory: Rademacher complexity bounds, Dudley entropy integral, Popoviciu’s inequality on variances.
    Invoked throughout Section 4 and the appendix.
invented entities (1)
  • Markov kernels Q_ϕ_τ and ĉM_k (softmax similarity and importance-weighted idealised search) independent evidence
    purpose: To give a precise probabilistic meaning to the finite-k InfoNCE risk as expected cross-entropy of two similarity searches.
    They are definitional rewritings of the softmax and of the Radon–Nikodym derivative of M; they do not introduce new unobserved objects.

pith-pipeline@v1.1.0-grok45 · 34352 in / 2730 out tokens · 29404 ms · 2026-07-13T03:14:50.027809+00:00 · methodology

0 comments
read the original 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\^{a}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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 3 linked inside Pith

  1. [1]

    Spectrally-normalized margin bounds for neural networks

    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

    2017

  2. [2]

    A simple framework for contrastive learning of visual representations

    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

    2020

  3. [3]

    Generalization bounds with logarithmic negative-sample dependence for adversarial contrastive learning

    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

    2024

  4. [4]

    Size-independent sample complexity of neural networks

    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

    2018

  5. [5]

    A rescaling-invariant lipschitz bound based on path-metrics for modern relu network parameterizations

    Antoine Gonon, Nicolas Brisebarre, Elisa Riccietti, and R \'e 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

    2025

  6. [6]

    Momentum contrast for unsupervised visual representation learning

    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

    doi:10.1109/cvpr42600.2020.00975 2020

  7. [7]

    Data-efficient image recognition with contrastive predictive coding

    Olivier Henaff. Data-efficient image recognition with contrastive predictive coding. In International Conference on Machine Learning, pages 4182--4192. PMLR, 2020

    2020

  8. [8]

    Generalization analysis for supervised contrastive representation learning under non-iid settings

    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

    2025

  9. [9]

    Supervised contrastive learning

    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: 0 18661--18673, 2020

    2020

  10. [10]

    Data-dependent generalization bounds for multi-class classification

    Yunwen Lei, \"U r \"u n Dogan, Ding-Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65 0 (5): 0 2995--3021, 2019

    2019

  11. [11]

    Generalization analysis for contrastive representation learning

    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

    2023

  12. [12]

    A vector-contraction inequality for rademacher complexities

    Andreas Maurer. A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pages 3--17. Springer, 2016

    2016

  13. [13]

    Foundations of Machine Learning

    Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. MIT press, 2018

    2018

  14. [14]

    Norm-based capacity control in neural networks

    Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376--1401. PMLR, 2015

    2015

  15. [15]

    Learning transferable visual models from natural language supervision

    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 o...

    Pith/arXiv arXiv doi:10.48550/arxiv.2103.00020 2021

  16. [16]

    A theoretical analysis of contrastive unsupervised representation learning

    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

    2019

  17. [17]

    Contrastive multiview coding

    Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In European conference on computer vision, pages 776--794. Springer, 2020

    2020

  18. [18]

    Representation learning with contrastive predictive coding

    A \"a ron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv:1807.03748, 2018

    Pith/arXiv arXiv 2018

  19. [19]

    High-dimensional statistics: A non-asymptotic viewpoint, volume 48

    Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019

    2019

  20. [20]

    Understanding contrastive representation learning through alignment and uniformity on the hypersphere

    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, 2020 a

    2020

  21. [21]

    Understanding contrastive representation learning through alignment and uniformity on the hypersphere, 2020 b

    Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere, 2020 b . URL https://arxiv.org/abs/2005.10242v10

    Pith/arXiv arXiv 2020

  22. [22]

    Unsupervised feature learning via non-parametric instance discrimination

    Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non-parametric instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733--3742, 2018

    2018

  23. [23]

    Tuning large neural networks via zero-shot hyperparameter transfer

    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: 0 17084--17097, 2021

    2021

  24. [24]

    Decoupled contrastive learning

    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

    2022

  25. [25]

    Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel

    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

    2021