On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning
Authors: Bokun Wang
Yunwen Lei
Yiming Ying
Tianbao Yang
Venue: ICLR 2025 Poster (2025)
Keywords: Discriminative Probabilistic Modeling; Self-Supervised Representation Learning; Multiple Importance Sampling
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: We study the discriminative probabilistic modeling on a continuous domain for the data prediction task of (multimodal) self-supervised representation learning. To address the challenge of computing the integral in the partition function for each anchor data, we leverage the multiple importance sampling (MIS) technique for robust Monte Carlo integration, which can recover InfoNCE-based contrastive loss as a special case. Within this probabilistic modeling framework, we conduct generalization error analysis to reveal the limitation of current InfoNCE-based contrastive loss for self-supervised representation learning and derive insights for developing better approaches by reducing the error of Monte Carlo integration. To this end, we propose a novel non-parametric method for approximating the sum of conditional probability densities required by MIS through convex optimization, yielding a new contrastive objective for self-supervised representation learning. Moreover, we design an efficient algorithm for solving the proposed objective. We empirically compare our algorithm to representative baselines on the contrastive image-language pretraining task. Experimental results on the CC3M and CC12M datasets demonstrate the superior overall performance of our algorithm. Our code is available at https://github.com/bokun-wang/NUCLR.

Published as a conference paper at ICLR 2025
ON DISCRIMINATIVE PROBABILISTIC MODELING FOR SELF-SUPERVISED REPRESENTATION LEARNING
Bokun Wang
Yunwen Lei²
Yiming Ying
Tianbao Yang"!
Texas A&M University
University of Hong Kong
University of Sydney
ABSTRACT
We study the discriminative probabilistic modeling on continuous domain for the data prediction task of (multimodal) self-supervised representation learning. To address the challenge of computing the integral in the partition function for each anchor data, we leverage the multiple importance sampling (MIS) technique for robust Monte Carlo integration, which can recover InfoNCE-based contrastive loss as a special case. Within this probabilistic modeling framework, we conduct generalization error analysis to reveal the limitation of current mn-see contrastive loss for self-supervised representation learning and derive insights for developing better approaches by reducing the error of Monte Carlo integration. To this end, we propose a novel non-paramettric method for approximating the sum of conditional probability densities required by MIS through convex optimization, yielding new contrastive objective for self-supervised representation learning. Moreover, we design an efficient algorithm for solving the proposed objective. We empirically compare our algorithm to representative baselines on the contrastive image-language pretraining task. Experimental results on the CC3M and CC12M datasets demonstrate the superior overall performance of our algorithm. Our code is available at htltttt://githaii com/ cwm/bokiiiiio bokun waauuun-wwa/NULLL
INTRODUCTION
Recently, self-supervised learning (SSL) of large models has emerged as a prominent paradigm for building artificial intelligence (AI) systems (Bommasani et al., 102 Ozbulak et al. [0233 Zhou ct al.] 2023a Zong et al.) 2023). Unlike traditional supervised learning that relics on human- labeled datasets, SSL can fully exploit the vast multimodal data readily available the internet via self-supervision (pretext tasks such as instance discrimination, masked modeling, and inpaint- ing) to learn large foundation models that useful for many downstream tasks. Although self- supervision differs from human supervision, self-supervised and supervised learning share similar- ities. For instance, many successful self-supervised learning models, e.g., CLIP (Radford et al.] 2021]. still use the softmax function and the cross-entropy loss to define their objective func- tions, similar to traditional multi-class classification in supervised learning. The key difference is that self-supervised learning focuses on predicting relevant data instead of relevant labels.
Discriminative probabilistic modeling (DPM) uses parameterized model to capture the con- ditional probability Pr(y)x) of target y e y
Multi Classiliation
y -Cat, Sks...)
p Discriminative Probabilistic Model (DPM) over Continuous Domain
y
given an input data point x. It is fundamen- tal approach for supervised learning (see, e.g.,
Discriminative Probabilistic Model (DPM) Finita Set for Supervised Learning
Chapter 4.3 in [Bishop 2006). For example, lo- gistic regression for multi-class classification (MCC) uses Pr(y(x) to define the probability of a label y given data point x, whose max- imum likelihood estimation (MLE) yields the cross-entropy (CE) loss. Similarly, probabilis- tic modeling approaches such as ListNet (Cao et al. 2007) have been used for learning to rank
Self-Supervised Representation Learning
Learning to Rank
Y Gake; Dure UP....
p( y aon
p(
Y
Apu
DPM for supervised learning and self- supervised representation learning.
Figure
"Correspondence Hranhao-yang@tamu..c

---

Published as a conference paper at ICLR 2025
(L2R) to model the probability of candidate y in list given query In these supervised learning tasks, the target y is from a discrete and finite set y (e.g. class labels or a list of candidates).
What if the target y in DPM is from continuous domain ) This is particularly useful for modeling the data prediction task of self-supervised representation learning. Considering that each underly- ing object in the real world generates various forms of observational data, such images, texts, and audio, DPM is a natural choice to model the probability of observing a data point from a continuous domain (e.g., the space of natural images, audio, or the continuous input embedding space of texts) given an "anchor" data point. The anchor data may come from a different modality. However, solv- ing DPM over a continuous domain is deemed as a challenging task (c.f. Section 1.3 in LeCun al.) 2006). Compared to the probabilistic modeling over discrete and finite sets, such as in traditional supervised learning tasks like MCC and 1.2R, the DPM problem over a continuous domain (real vector space) necessitates computing the partition function (i.e., the normalizing constant) for each anchor. This involves an integration over an underlying continuous space, rather than a finite sum- mation. Previous works tackle or circumvent this issue using Markov Chain Monte Carlo (MCMC) sampling (Song and Kingma 202T; Du and Mordatch 2019. Ta et al. 2022). noise-contrastive es- timation (NCE) (Gutmann and Hyvärinen 2010), and energy based models (EBMs) (LeCun et al., 2006 Assran et al.j (2023)). However, these approaches have drawbacks that hinder their wide adoption in self-supervised representation learning. Specifically, MCMC approaches
computa-
tionally expensive and prone to divergence during training (Yang and Ji 2021] Kim and Yel (022). NCE suffers from slow convergence for high-dimensional data when the noise distribution is not well-configured (Liu et al.) 2022). and EBMs neglects the partition functions that may throw away some discriminative power of DPM. The state-of-the-art discriminative self-supervised representa- tion learning algorithms rely on InfoNCE-basee contrastive losses (Oord et al. 2018 Chen et al.) 2020 Radford et al., 202T). However, the connection between these losses and DPMs is not fully revealed, limiting our understanding of their strengths and weaknesses.
In this work, we study the DPM problem over a continuous infinite domain for self-supervised rep- resentation learning, called infinite discriminative learning (co-I)..). We investigate computational framework of robust Monte Carlo integration of the partition functions based on the multiple impor- tance sampling (MIS) approach (Veach and Guibas
1995 Veach 1998). Our contributions are:
We construct an empirical risk for maximum likelihood estimation (MLE) based on MIS. Unlike the setting in MIS for traditional stochastic simulation, the sums of conditional densities on training data are not directly accessible, requiring approximations of these sums. We show that an InfoNCE- based contrastive loss, referred to the global contrastive loss (GCL) (Yuan al. 2022). , can be derived as a special case of this empirical risk when a simple uniform approximation is used.
Our finite-sample generalization analysis reveals that GCL incurs non-diminishing error due to the rather crude uniform approximation. To reduce this error, we introduce a novel -oraamrmettiic method approximate the sum of conditional densities required by the MIS approach through optimization. In a toy experiment, we demonstrate that the proposed non-parametric method results in better approximations and significantly smaller generalization errors than GCL.
The MLE framework based on MIS and our parametaetiic method inspires a new contrastive objective for self-supervised representation learning. We design an efficient algorithm, NUCLR, to optimize the proposed objective, which does not require the costly MCMC steps or the elusive noise distribution selection. Furthermore, NUCLR can be interpreted as a contrastive representation learning algorithm with nomuniform margins that are dynamically learned for negative pairs.
Experimental results on language-image pretraining using CC3M and CC12M datasets show the superior overall performance of NUCLR compared to baselines on downstream retrieval tasks.
1.1 RELATED WORK
Probabilistic Models for Self-Supervised Representation Learning: Discriminative probabilistic models learn the conditional probability mass/density function p(y x) of y given data x. Recently, some works have focused on modeling the conditional probability density function p(y x) for the unsupervised representation learning task, where both and y may belong uncountable spaces. Khemakhem et al. (2020) studied the identifiability (i.e., the learned representations are unique up to linear transformation) of DPM and showed its connection nonlinear ICA models. Ta et al. (2022)
2

---

Published as a conference paper at ICLR 2025
improved the Langevin MCMC method to handle the partition function in DPM for learning implicit representations of behavior-cloned policies in robotics. Discarding the partition function, [Assran et al. (023a); [ardes al. (2024) proposed the energy-based models I-JEPA and V-JEPA to learn visual representations by predicting the relevance between data representations. Although the high- level concept of JEPA is similar to our work in that both aim predict the relevance hetween data representations, our approach is grounded in discriminative probabilistic modeling, whereas JEPA is an energy-based model that omits the partition function. Consequently, JEPA lacks some statistical guarantees of probabilistic models, such as the convergence of the maximum likelihood estimator, which have implications for performance on downstream tasks (See Remark Furthermore, JEPA is designed specifically for the visual modality whereas our algorithm applies to multimodal data.
By modeling the joint distribution p( p(x. p(,,y), hybrid models (Grathwohl et al. 2019 Wang et al, 2022 Kim and Ye 2022, BBizeul et al. 2024) simultaneously perform discriminative and generative probabilistic modeling. Although the generative component in hybrid models might offer some ben- efits for representation learning, such achieving reasonably good performance with small batch size, Kim and Ye (2022) pointed out that current hybrid models significantly increase the computa- tional burden and cannot be applied to large-scald scale datasets such ImageNetlk due to the expensive inner loops of stochastic gradient Langevin dynamics or adversarial training. Furthermore, [Bizeul al. (0224) mentioned that generative representation learning approaches face difficulties scaling to large-scale, complex datasets, as "learning representations for complex data distributions under a generative regime remains& a challenge compared discriminative approaches."
InfoNCE-based Losses and Theoretical Guarantees: The InfoNCE loss is arguably the most
widely used loss function in contrastive learning (Chopra et al.. 2005 Oord et al.] 2018 Chen it al. 2020; Radford et al. 2021). Given a dataset (x,;; } from two views or moda lities, the minibatch-based InfoNCE loss contrasts each positive pair with & negative pairs in the sampled
batch. Both empirical observations (Chen et al., 2220: Radford et al. 202T]] Yuan et al., 2022) and theoretical analysis (Yuan et al., 2022) demonstrate that algorithms based on InfoNCE perform well when the batch size is sufficiently large (e.g. 32,768 for CLIP training), which demands lot of computational resources. Besides, several works analyze the generalization error of the minibatch- based InfoNCE loss (Arora et al., 2019: Lei et al. 2023). However, these analyses have critical limitation: the generalization error increases with k which contradicts practical observations.
To address the dependency large batch sizes, Yuan et al. (2022) studied the global contrastive loss (GCL), which can be viewed as a variant of the InfoNCE loss that contrasts each positive pair with all other negative pairs in the whole dataset. Based on the exponential moving average (EMA) technique, they developed the SogCLR algorithm that converges to a neighborhood of a station- ary point of GCL even with small batch sizes (e.g., 256). Recently, Yauu al.) (2024) introduced the MCMC-based EMC² algorithm that converges to the stationary point with a small batch size. However, EMC appears empirically perform worse than SogCLR on large datasets such as Ima- geNetlk. Besides, Waida et al. (2023) established the generalization bound of the kernel contrastive loss (KCL), which is a lower bound of GCL when the kernel is bilinear.
2 PRELIMINARIES
Notations: We use [n] to denote the set (1,...,n). For a vector v E RR,, (.()) represents its i-th coordinate and we define exp(v) = (exp(u()).....eepp)) exp(v("))) Let X and y be Lebesgue- measurable data spaces of different views or modalities. When X ) is finite, the Lebesgue measure j is replaced by the counting measure. For a sequence of random variables (x,) we write x, F. x to denote that ) converges in probability xo
Multiple Importance Sampling (MIS): Next, we briefly review the multiple importance sam- pling (MIS) approach (Veach and Guibas 1995 Veach 1998) for robust Monte Carlo integra- tion. MIS was originally introduced to address the glossy highlights problem for image render- ing in computer graphics, which involves computing several integrals of the form g(a,r,)) r,)) fx (x 3) s)) which represents the light exiting point a on a glossy surface under varia- tions in light size s and surface glossiness r. For Monte Carlo integration of g(, impor- tance sampling based on a sample from single distribution may lead to large variance under

---

Published as a conference paper at ICLR 2025
some light size/surface glossiness. To address this issue, the MIS approach constructs an unbi- ased estimator g(a, s) = Σÿ-1 1 -in (x,,1) (x..m)) by combining samples X ...,X,. from distributions PI....., Pn. where Xj = (xj,1....,,,..) is sampled from the j-th distribu- tion, and w = (w(1) (()) is a weighting function satisfies that Σラ= ( (x) = when a,; a. s) + and w (x) when Py py(x)
p)(3)a))
Moreover, Veach and Guibas (9955) pro-
posed the "balance heuristic" w (x) Py(]] and proved that this choice of w is near-optimal
(x)))
in terms of variance among all possible weighting functions and the resulting MIS estimator is ((a,r, = Σe= Em (y,,,,))))))""" Empirically, they showed that MIS with the balance heuris- tie leads to better rendering performance than importance sampling with a single distribution.
((
3 DPM OVER A CONTINUOUS DOMAIN
When choosing X' as the anchor space, we model the probability density p(y x) of an object y y given an anchor object x X by the following DPM parameterized by w:
exp( Fow ()/)) Jo expp E x,
Pw P x)
y' (x,,)) //)ddd(yy")
where 0 is temperature parameter for flexibility, Ew X x + R is a parameterized prediction function, e.g., (x, = (w E2(w2,y), where Ei and E2 are encoder networks. We assume that exp( Fr (x.))// Lebesgue-integrable for w E W, W c Rdd. Here Pw Pw x) is valid probability density function because fy Pw (y x)dd(yy) 1. Given ((x1,y1),.- (Xn; yn)) sampled from the joint distribution Px.y: the maximum likelihood estimation (MI.E) aims to solve
exp( exp(F (x:; (:)/T Jn ( (x,, y'x,y")) x')/T)d(((")
min
log
71
Corresponding to the empirical objective above, the true (expected) risk can be defined as
exp( (x, L(w)= == Exxy -T log Jy exp(Ew (/)/////dddp()))))))))))m)))))))
The above discriminative learning framework recovers the traditional supervised learning of label prediction when }' is a finite set of class labels. Nevertheless, we focus addressing the challenge of solving 3 for self-supervised learning of data prediction when ) is a continuous space of data.
Remark 1. Learning the DPM Pw. via MLE for self-supervised pretraining naturally provides some performance guarantees for downstream discriminative tasks. Suppose that the true ditional density function is parameterized by some w, e W, i.e., p(y x) = Pw. (y x) for any X,y V. Then, the maximum likelihood estimator w. Ty (ww (x,y' (/)))/))((r)))
exp(Ewr (x.y)/r)
arg max n E logg((y; x;) with the sample ((x,, (x),,;))) y= of size n converges in prob- ability to w, under some mild assumptions (see Theorem 2.1 in Newey and McFadden 1994..
Due to the continuous mapping theorem, the learned model satisfies Ew. (x,y) Ew. (x, and
Pw. (y/x) 3 Pw.(ylxc if the parameterized models Ew and Pw have measure-zen discontinu- ity points on W, which naturally provides a statistical guarantee for cross-modality retrieval. In we also discuss the performance of DPM downstream classification tasks.
App. C
When choosing y as the anchor space, X' given an anchor y e y by the parameterized model Pw (x Iy) Lx (x)x)
also model the probability density of an object (x.))r
similar to ( Based on sample = X x Ý = ((xI,)),..... (x)) of size n from the joint distribution Px.y. we can simultaneously model Pw x) and Pw (x y) via the objective below, which resembles the symmetric InfoNCE loss in Radford et al. (00IT):
min 1 ΣΣ n
exp(E (xc. exp((EE (')))))))) + +loog Jx
(xt.
Flog
4

---

Published as a conference paper at ICLR 2025
3.1 AN
EMPIRICAL RISK FOR MAXIMUM LIKELIHOOD ESTIMATION
For simplicity, we focus on the case where X' is the anchor space and aim to model ply x). The main challenge of MLE in (2) lies in computing the integral g( ((W:x;;))) = Jy e (xx,)))/7) dlp(y') ) for each i e [n]. which is infeasible unless y is finite. For Monte Carlo integration based on the importance sampling, it is difficult, if not impossible, to select a sin- gle distribution that works well for all integrals g( (,:,,,))) i é [ra]. Assume that each data yy is sampled from P3- p(- xj) given data x, sampled from the marginal, j ..2....,P n. Thus, we employ the MIS method with balance heuristic ( (Veach and Guibas 1995) to construct the following estimator of g( (w; xx by combining sampled data yI..... .n from n distributions Pl.....Pr'
0(w; x, Y)
Σ j-1
p(y; Xy.) exp (Ew (x.(x)))) Y= (y1....... ......... Yn).
1
(4)
ER
In App. B. we show that the estimator ğ( (W; Y) in 44) is an unbiased estimator of g (w; x;) and explain why we choose the balance heuristic over other possible weighting functions for MIS.
Remark 2.
The variance of MIS- based estimator ((::,; Y) can be further reduced if sample multiple data (y from each Pj. j E [n]. The MIS-based estimator is then constructed as
m
1
i w; x;: Y) = Σ
Ly xy) exp (x..)t
Uy j=1
E EI
be approximated by random augmentations of y,, assuming that the neighborhood of a high-density point also has relatively high density. Using a sample of (y..)...., Jj.m. of size m 1, as opposed to a single y, has been empirically shown improve performance in bimodal contrastive learning (Fan et al. 2024 Li et al. 2024).
In practice Nj.1.-..... -.....--j... Nim
However, remaining issue prevents us from using the MIS-based estimator in Unlike the rendering problem considered in Veach and Guibas (1995), we do not have access to the conditional probability density p(y; xy.), j.J E [n]. Thus, there is a need for a cheap approximation q(1) of the sum of conditional probability densities g())= = =y=1(y Xy), Vj E [m]. where g(0) can be viewed as a measure of popularity of y, if we consider that all data in $ {(x;, y;)] form a graph and the weight on edge from node x to node is p(y(x). With general approximation
(7()) (()) of q (1 (((),...((")) (()) T. the MLE objective in ( with MIS can be written as exp( (x:
C(::q. S) 1 a Σ T log g(w:x, Y) 1-1
g(w;x, Y) = exp (Ew(x..)))/T) (5)
((i))
Remark 3. If we simply choose the uniform approximation q ncl, with some <> minimizing
L(w; q. S) in (5) is equivalent to minimizing the global contrastive loss (GCL. Yuan et al. 2022).
Besides, the objective in (5) is special case of empirical X-risks discussed in (Yang) 2022 Yuan ct al. 2023). Since it stems from a discriminative learning framework, we refer to it as a discrimi- native X-risk. Given q, minimizing L(w; q. S) can be achieved using existing finite-sum coupled compositional optimization (FCCO) algorithms (Wang and Yang. 2022). The key challenge, how- ever, lies in estimating q to enhance generalization beyond simply minimizing the GCL.
3.2 FINITE-SAMPLE GENERALIZATION ANALYSIS
Next, we analyze the error between the empirical risk L(w, S) in (5) with general approxima- tion q and the true risk L( w) in 33) for DPM. This analysis provides (i) insights into the statistical error of GCL (Yuan et al. 2022), and (ii) guidance on finding an approximation q better than the uniform one used by GCL as discussed in Remark 3 First, we state the necessary assumptions.
Assumption 1. There exist 02 > 0 such that |x|| S c1. lyl2 S 02 for any x xx,
We focus on representation learning such that Ew (x, = Ei (wi:)) Eg y) where w1 and W2 are the encoders+projection heads of the first and second views/modalities, respectively. In our theory, we consider the case that both E, and Eg are L-layer neural networks with positive- homogeneous and I-Lipschitz continuous activation function a() (e.g. ReLU).
"Our results could potentially be extended to other neural networks, such as ConvNets, using the corre- sponding Rademacher complexity bounds (See c.g., Truong 2022.
5

---

Published as a conference paper at ICLR 2025
Assumption 2. Suppose that Ei (w E IRd,, E2 (w2: y) Rd for some dp 1. Moreover, have (ww1x))] $ (w2:t))) such that Ew (x,y) E [[-1,1].
Based on the assumptions above, provide finite-sample generalization error bound between the empirical risk Ê(w; S) in (3) and the true risk ((w) in (
Theorem 1. Suppose that Assumptions ① and (2) hold. Consider the prediction function Ew
parameterized by L-layer deep neural networks W1. W2 and approximation of q, where gl))
Ey=1ply; xy) 2 Q())) almost surely, vje [n]] With probability at least 1 1- 6, 8 (0,
dp
log(1/6)
E (w. (a..))))
00
(6)
where E Q: = Σ Eド=1
gl3 9l5) exp( ( E (x,, 1)/T) is an error term.
Remark 4. (i) The uniform approximation g()) non-diminishing error term ((q.q:$) for solving DPM over continuous domain; (ii) Moreover, the error term Eq. q: S) vanishes when y a finite set. Then, the result reproduces the classical result in the literature for supervised learning (Boucheron al. 2005).
for all j [n] used by the GCL leads to
3.3 NON-PARAMETREE METHOD FOR APPROXIMATING THE MEASURE OF POPULARITY
we show that simply choosing a uniform q as in GCL to approximate the measure of popularities q (i.e., the sum of conditional probability densities) leads to non-diminishing term in generalization eπror. Next, we present a new way to approximate the measure of popularities q. For brevity, we denote by E(.,)) Ew, (+--) that corresponds to the real conditional density expl exp(Ew,ff )/T) exp(Ew. (x.y (x)'')/)ddp(>") Thus, for any E [n]] we have
In Section 3.2
ply x) =ww. (y |
exp xxp(E(xy.y,// (6) Σ ply; xy))= 3'-1 J 7-1
exp(E(xy.)))1 E qie exp E(x(E(xy,)e))/))
Σ
Σ
(7)
where the last step + is due to the MIS-based Monte Carlo integration and its error decreases when increases (See Prop. in App. Note that 7 can expressed as a root-finding problem q= F(q) for some mapping parametric method to approximate q by solving the following convex optimization problem:
R RR. Since directly solving (7) is expensive, we propose non-
min CER
Σ log
Ej_1 cxp((E(x,,))) -()))/>)
vx)(F(xx,)))/>)
-
1 n
(0) 3-1
(8)
n
The following theorem characterizes the set of optimal solutions to K and its relationship q-
Theorem 2. The optimal solution to is unique up to an additive scalar. In other words, if S. belongs the optimal solutions set Z. of (8), then C. + cln is also in Z. for any e R. Moreover, if we define the set Q. == (exp((./ (STP((./TTTTT C. E Z.}, then any q E Q. satisfies the following equation
Σ exp(E(Xy,)))11)
E কाग exp exp(E(xy, Vje [n].
and the set Q, is closed under sealar multiplication, i.e., any E Q. and C'> > 0 implies Cq Q.. Remark 5. Due to Theorem 2 and the resemblance between 7 and ( there exists specific q Q. that approximates the real q in (7). Thus, we can approximate the real q (up to scaling factor) by solving the optimization problem in (B. Specifically, for q' exx(((.TT) computed from (8) with finite to norm, we can conclude that q' and q differ only by Z < co. There no need to worry about the scaling factor since minimizing the empirical risk L(w; S) and the corresponding true risk ((w) is equivalent to minimizing [(w; q' S = L(w; q. S) + + log (1/Z) and L(w) + + log(1/Z).
any solution C. é Z. to
scaling factor, i.e., q' Zq for some constant
We design a synthetic experiment to verify the effectiveness of our non- parametric method, Consider anchor data space and X' (2) of + v 1, [-1, 12,22 22 e [0, 1]} and contrast data space

---

Published as a conference paper at ICLR 2025
GCL
VLE
Quo
y
0.00
X
200
0.04
100
y
y!
520
2003
1500
2000 2500
Sample
Figure Leftt: Illustration spaces and V: Middle: RBF interpolated heatmaps true q approx- imation q when 100; Right: Comparing the generalization error (ć(q. L] of our method and GCL across various n. "MLE" refers to MLE objective in 2 with the exact partition function.
Y' ((11,22) vn: 1/2 [0, 1]}. Let x be uniformly distributed on X' and the conditional density of exp( (Fx.))/r)
an y given x p(y x) = Ty (x=)B(xx"")/))dd(y)) where T 0.2 and E(x,y) = x'y and
fy ( can be exactly computed. More details can be found Appendix G.1
As shown in the middle of Figure our method effectively approximates the true up constant Z. Moreover, we plot the generalization error of different methods in the right column Figure which confirms the result in Theorem and Remark that the uniform approximation of q in GCL results in a non-dimin con-dimnnishing term in generalization error as n increases. In contrast, our method achieves significantly smaller generalization error, almost matching the MLE objective in (2) with the exact partition function when n increases.
3.4 THE NUCLR ALGORITHM FOR SELF-SUPERVISED REPRESENTATION LEARNING
By substituting the q from the non-parametric method described in Section 3.3 the problem of minimizing the empirical risk of DPM in becomes
1 Tı Σ log
exp( (x,,
min S): L(w: = weW
Σ (x )/)))))
where C. solved from g Unfortunately, the true similarity function E y [-1,1] in (8) is unknown. To address this, we can adopt a Jacobi-type alternating minimization approach. In the t-th iteration, we replace the E(.-) in (
by fixed model Ew, (:--) and solve 6,- from
min (C),) Coi
(c(C) =
1
T log
EE, v:)/T) Ej-1 exp( (Fw, (x).,)) (())/T)
" Σ j=1
50)
(10)
Then, we fix the auxiliary variable Ç to C, and solve W,41 from the following problem:
(x).
min V (w). weW
V.(w): =
log
Σe (F (x,, --0
(11)
However, solving the subproblems TO and exactly is computationally infeasible. Instead, obtain the new iterate (We+1, (t.1) by one step of gradient- gradient-based update from the previous iterate (we,S)) Defining di(w,C) () == Ejs; exwee(p(((wwx)) (Ew(x;, - Ew (x) (/)) and s(ç(") =
exp(-ç(0//)) /T) the objectives (C) and (,(w) in (T)) and 11 can be rewritten follows:
(C)
1 Σ n
1 llg((s((9)) dw (), n
Σ ( v v.(w) Σ log(s(c!")) + ())..
Given size-B minibatch B, [n]. the stochastic gradients of (c())), V (w:) can be computed as
1
B.)
Σ
(w.,, .,, C; B.) (C (e (. C,i B.))= n
je Br, (12)
a(G)
(i)
ieB
1
w. V V, (w:;
Σ
V Vwol Wt. S, B.), o Wt, B.)
(13)
B
(1) ct
teB.
'F.g., the gradient descent or momentum-hasee -hased update. could he extended to multiple steps.

---

Published as a conference paper at ICLR 2025
Algorithm NUCLR Algorithm for Self-Supervised Representation Learning
1: Initialize wo. Uo. Ç Coln, and set up Eo So. 7/, 7
2: for (= 1...,...... T do
3: Sample B, {1. [.
4: Compute G(C (() according to (4 for e B,
G)(( (or momentum/adaative method), j B, (1)
(
5: Update <
é B,
6: Compute G(w,) in (15) and update We+1 w.-1)G((we) (or momentun/adaptive method)
7: Update E++1 max 1
8:
end for
where e(c(") is shortened to e,"), &1 (. n-1 B-1 EyeBi( exp( (x, (x. v,) ) Er (x. (x.
is a stochastic estimator of di (w,, S,). However, 9 कदाा (.) and V (ww;; B,) are still biased estimators of açG3 (St). V W. (w.) because the gray parts are in the denominators, where the bias is small only when the batch size B is large. To resolve this issue, adopt the moving average technique from the SogCLR algorithm (Yuan et al., (002)) to keep track of (s(w,, () for each i E [m]- To be specific, for those i e B, while fixing (1) = ut for i B,- Then, we obtain the following stochastic gradient
a
maintain scalar (1)) for each i and update u
(1) =(1- (1-7)u, (i) rr, Sri
estimators G(C!)) and G(w,) by replacing the gray parts in and (13) with (
G((())=
1
Σ
OCl)) (El
di(we; (. 1 je Be
(14)
teB.
( u4
n
1
G(wi) = B &
Σ
V V (rs B,;
(15)
We also adopt an additional trick to improve the quality of the model w, especially during the early training epochs. The denominator Σ5-1 exp( (Fw (xi, ((() )/T)))/)))))))))))))))))())))) in the objective V.(w) of (IT)
can be viewed as the weighted version Σy= E(" exp((Ew (x..))))) of the corresponding term in GCL,, where o(" = exp((<(0)/7 /T) can be viewed as the "strength" of pushing y, away from x;- For less parameter tuning, prefer initializing ( from the same value Ço e R. Consequently, nearly equal weights are assigned to both the positive pair (x,, y:) and negative pairs {(x,, yy) during early training epochs, which may slow down the learning process of model To address this issue, we introduce a scalar &. = max (E |Sl lo) and reduce c( in (5) of positive pair (x) from exp(-s!")/7 /T) exp((Ee/T) to avoid aggresively pushing the positive data y, away from x;-
Then, we can update Ç and w based on G(C,))) and G(w,). The full update procedure in Algorithm|| 1 referred to as NUCLR. The novelty of NUCLR lies in lines and of Algorithm T we fix Ç, O, and & = 0, NUCLR becomes the SogCLR algorithm Yuan et al. (022). As discussed in App- F.T NUCLR incurs only minor computational and memory overheads compared to SogCIR. Moreover, we offer an intuitive margin-based interpretation of NUCLR in App.
4 EXPERIMENTS ON BIMODAL REPRESENTATION LEARNING
Settings: In our experiments, we apply our algorithm to bimodal ceff-superiiee representa- tion learning on the Conceptual Captions (CC3M) (Sharma et al., 2018) and Conceptual 12M (CC12M) (Changpinyo et al. (202T) datasets. Because some data links have expired, our downloaded training set of CC3M contains
2, 723, 200 image-text pairs, while that of CC12M contains n 9, 184, 256 image-text pairs. We evaluate the performance of trained models on downstream zero-shot image-text retrieval and image classification tasks. Retrieval performance is evaluated on the test splits of the Flickr30k (Plummer et al.) 2013) and MSCOCO (Lin et al.) 2014) datasets, in terms of the average Recall @ score of image-to-text and text-to- text-to-image retrievals. The top-1 classification accuracy is evaluated on the CIFAR 100 (Krizhevsky et al.) 2009). ImageNetlk (Rus-) sakovsky et al. 2015), and ImageNet-R (Hendrycks al. 2021) datasets. We compare our proposed
8

---

Published as a conference paper at ICLR 2025
NUCLR algorithm with representative baselines CLIP (Radford al., 2021 SigLIP (Zhai al. 2023). DCL (Chuang et al., 2020), CyCLIP (Goel et al. 2022). and SogCLR Yuan et al. 2022 All experiments utilize distributed data-parallel (DDP) trainin on two NVIDIA A100 GPUs with 40GB memory and the total batch size B in each iteration is 512. Besides, we use ResNet-50 as the vision encoder and DistilBert projected by a linear layer into a 256-dimensional feature representation for computing the losses. We run each algorithm 3 times with different random seeds and each run contains 30 epochs. Hy- perparameters of all algorithms are tuned based on the validation performance. The optimizer for the model parameter w is AdamW (Loshchilov and Hutter (017) with weight decay of 0.02 and cosine learning rate schedule (Loshchilov and Hutter] 2016). For all algorithms, we choose fixed temperature parameter 7 tuned within {0.01, 0.03, 0.05, 0.07). For SogCLR and NUCLR, we set 0.8 as in the SogCIR paper Yuann et al. 2022). For our NUCLR, we select Co -0.05 on the CC3M dataset and So = 0 on the CC12M dataset. Besides, we freeze Ç in the first 5 epochs and update Ç by the SGDm optimizer with cosine learning rate schedule.
the text encoder. The output embedding of each encoder is
Table I: A comparison of test performance. The best result in each column is highlighted in black.
Retrieval
Classification
Dataset
Algorithm
MSCOCO
Flickr30k
CIFAR 100
ImageNetIk
ImageNet-R
Mean
CLIP
24.23 a 0.14
46.33 a 0.76
33.94 a 0.87
35.91 #: 0.33
36.47 = 0.40
35.38
DCL
24.44
46.03 + 0.75
0.75
32.78 a 0.46
35,90 + 0.20
36.11 = 0.29
35.05
SigLIP
35.70 0.84 44.95 + 0.45
37.53 + 0.09
39.64 0.19
36.21
CC3M
CyCLIP
4 0.83
37.27 a 0.61
36.63 a 0.04
37.83 = 0.34
36.66
SogCLR
28.54
52,20 + 0.64
35,50 1.71
40.40 + 0.12
42.65 + 0.50
39.86
NUCLR (Ours)
29.55 + 0.26
53.55 + 0.22
37.45 0,45
40.49 + 0.30
43.82 + 0.25
40.97
CLIP
30.30
55.21 0.45
25.35
0.64
44.28 + 0.22
46.8 66.84 0.41
40.40
DCL.
30.23
54.63 + 0.50
25.55 + 0.61
44.32 0.07
46.92 0.41
40.33
SigLIP
30.13
55.40 0.32 0.24
26.60 1.89
46.12 0.12
48.87 0.46
41.42
CC12M
CyCLIP
54.63 0.20
26.71 2.09 2.09
44.94 0.02
48.66 0.09
41.06
SogCLR
33.91 + 0.26
59.28 0.07
26.10 + 0.88
49.82
0.14
54.54 0.24
44.73
NUCLR (Ours)
34.36 0.13
60.45 0.03
28. # 1.35
49.82
0.23
55.24 0.51
45.61
MSCOCO (CCIM)
Flickr30k (CCIM)
MSCOCO (CC12M)
Flickra0k (CC12M)
16
20001
1000
Eprohr
Epechs
Figure 3: Validation Recall@ performance of our algorithm and baseline SogCIR during training on the CC3M (left two columns) and CC12M datasets (right two columns).
Comparison with Baselines: We compare the performance of our algorithm on downstream retrieval and classification tasks with various baselines in Table D Moreover, we compare the Re- call@1 I of our NUCLR with that of SogCLR across the training epochs in Figure the validation sets of MSCOCO and Flickr30k. Compared to baselines, our NUCLR achieves superior overall performance on downstream tasks. Notably, the performance gain of our NUCLR over SogCLR substantially larger on the more challenging ImageNet-R dataset than on ImageNet1k.
Ablation Study: For further understanding the key components of Algorithm I we compare the performance of NUCLR against three variants: (i) NUCLR- which fixes Ç to 1o i.e., removing
step in Algorithm I (ii) NUCLR-0, which does not reduce the strength E, of pushing away the i-th positive pair to exp(-Ext (E+//) as described in the penultimate paragraph of Section and (iii) NUCLR-+ which does not freeze Ç in the first 5 epochs; to answer the following questions.
(i) What is the advantage of updating Ç using gradient- based updates compared to fixing it at Ço?
*For CLIP and SigLIP, we adapt implementations from the OpenCLIP repository. For DCL and CyCLIP, we use the authors' official implementations. For SogCIRR, we use the implementation in the updated codebase Qf al. 2023), which yields better results of SogCI. RR than that reported Qiu al. (223.

---

Published as a conference paper at ICLR 2025
(ii) Is it beneficial reduce the strength of pushing away each positive pair by introducing ??
(iii) What is the benefit freezing ( during the initial training epochs?
The results are shown in Figure 4 First, can observe that NUCLR with the learned Ç in Algorithm outperforms NUCLR-1 with a fixed Ç Coln. Moreover, we present some examples of images from CC3M with large small q' exp(C/7) in Figure [ showing that the learned T' effectively captures data popularity: Images depicting human life, such as portraits, pets, and landscapes, tend to be more popular than abstract symbols and shapes (see App. G.3.3 for more amples). Second, introducing & to avoid pushing away positive pairs improves performance in both tasks compared NUCLR-O. Lastly, freezing during the first epochs yields better performance, which can be considered as a warm-up stage for learning w before updating Ç. This improvement may arise because model W; is far from w, in the early stage of training, making the Ç solved from (T0) less accurate. We did not tune the number of warm-up epochs as the chosen value consistently performs well across our experiments. We provide more experimental results in App. G3
Downstream Retrieval [Pretrained CC3M]
Downstream Classification (Pretrained CC3M)
Downstream Retrieval (Pretrained on CC12M)
Downstream Classification (Pretrained on CC12M)
BAC.
Teat
Gog SUCUR. HOCK iuca wuzch
SogeL
HOCLE. HUCUR RoCA&&
SugcLO NUCLE BUCIR
SUCUR
SUCLA
SoyCLh
WOCLR.
BUCLK
BUCCK
Figure 4: Compare NUCLR algorithm with variants NUCLR-1, NUCLR-0, and NUCLR- "Downstream Retrieval" refers to the average test recall@ on MSCOCO and Flickr30k datasets; "Downstream Classifica- tion" refers to the average test top-1 accuracy on CIFAR100 and ImageNetIk datasets.
2
SALE
0.079
0.081
0.083
0.006
0.006
0.007
Figure Examples of CC3M images with large (in red) and small learned popularities o' (in blue).
CONCLUSION
In this paper, we tackle the discriminative probabilistic modeling problem on a continuous space by leveraging the multiple importance sampling (MIS) method and proposing novel nonparamet- ric method for approximating the sum of conditional probability densities required by MIS, which yields new contrastive loss for self-supervised representation learning. Then, design effi- cient algorithm called NUCLR to optimize our new loss. Experimental results on bimodal pretrain- ing demonstrate the improved overall performance of method compared baseline approaches on downstream tasks. An open question remains whether we can learn a generative model this discriminative framework that conditionally generate high-quality new data. Additionally, NUCLR algorithm requires storing additional 2n floating-por point numbers for language-imag pre- training. Another open question how to learn a neural network to predict the popularities.
ACKNOWLEDGMENTS
B. Wang and T. Yang were partially supported by the NSF SCH grant 2306572.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.09229, 2019.
Mahmoud Assran, Quentin Duval, Ishan Misra, Piotr Bojanowski, Pascal Vincent, Michael Rabbat, Yann LeCun, and Nicolas Ballas. Self-supervised learning from images with joint-embedding predictive architecture. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15619-15629, 2023a.
Mido Assran, Randall Balestriero, Quentin Duval, Florian Bordes, Ishan Misra, Piotr Bojanowski, Pascal Vincent, Michael Rabbat, and Nicolas Ballas. The hidden uniform cluster prior in self- supervised learning. In The Eleventh International Conference on Learning Representations, 2023b.
Adrien Bardes, Quentin Garrido, Jean Ponce, Xinlei Chen, Michael Rabbat, Yann LeCun, Mahmoud Assran, and Nicolas Ballas. Revisiting feature prediction for learning visual representations from video. arXiv preprint arXiv:2404.000 08471, 2024.
Christopher M Bishop. Puttern Recognition and Machine Learning. Springer, 2006.
Alice Bizeul, Bernhard Schölkopf. and Carl Allen. A probabilistic model to explain supf-suue representation learning. arXiv preprint arXiv:2402.01 2024.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportu- nities and risks of foundation models. arXiv preprint arXiv:2 2021.
Lukas Bossard, Matthieu Guillaumin, and Luc Van Gool. Food-101 mining discriminative com- ponents with random forests. In European Conference on Computer Vision, 2014.
Stéphane Boucheron, Olivier Bousquet, and Gábor Lugosi. Theory of classification: A survey of some recent advances. ESAIM: probability and statistics, 9:323-375, 2005.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymp- totic Theory of Independence. Oxford university press, 2013.
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. Learning imbalanced datasets with label-distribttion-waaa margin loss. Advances in neural information processing systems, 32, 2019.
Zhe Cao, Tao Qin, Tie-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129-136, 2007.
Soravit Changpinyo, Piyush Sharma, Nan Ding, and Radu Soricut. Conceptual 12m: Pushing web-scale image-text pre-training to recognize long-tail visual concepts. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 3558-3568, 2021.
Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607. PMLR, 2020.
Zixiang Chen, Yihe Deng, Yuanzhi Li, and Quanquan Gu. Understanding transferable representation learning and zero-shot transfer in CLIP. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, 2024.
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning similarity metric discriminatively, with application to face verification. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (55,, volume 1, pages 539-546. IEBE, 2005.
Ching Yao Chuang, Joshua Robinson, Yen- Chen Lin, Antonio Torralba, and Stefanie Jegelka. De- biased contrastive learning. Advances in neural information processing systems, 118765-8775, 2020.
11

---

Published as a conference paper at ICLR 2025
M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, and A. Vedaldi. Describing textures in the wild. In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
Stéphan Clémencon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statistics, pages 844-874, 2008.
Victor De la Pena and Evarist Giné. Decoupling: from dependence to independence. Springer
Science & Business Media, 2012.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference Computer Vision and Pattern Recognition, pages 248-25822 255, 2009.
Yilun Du and Igor Mordatch. Implicit generation and modeling with energy based models. Advances in Neural Information Processing Systems, 32, 2019.
Yilun Du, Shuang Li, Joshua Tenenbaum, and Igor Mordatch. Improved contrastive divergence training of energy based models. arXiv preprint arXiv:2012.01316, 2020.
Lijie Fan, Dilip Krishnan, Phillip Isola, Dina Katabi, and Yonglong Tian. Improving clip training with language rewrites. Advances in Neural Information Processing Systems, 36, 2024.
Ruiqi Gao, Yang Lu, Junpei Zhou, Song-Chin Cong-Chun Zhu, and Ying Nian Wu. Learning generative con- vnets via multi-grid modeling and sampling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9155-9164, 2018.
Shashank Goel, Hritik Bansal, Sumit Bhatia, Ryan Rossi, Vishwa Vinay, and Aditya Grover. Cy- clip: Cyclic contrastive lunuuae-image pretraining. Advances in Neural Information Processing Systems, 35:6704-677 6719, 2022.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018.
Will Grathwohl, Kuan-Chieh Wang, Joern-Henrik Jacobsen, David Duvenaud, Mohammad Norouzi, and Kevin Swersky. Your classifier is secretly an energy based model and you should treat it like one. In International Conference Learning Representations, 2019.
Ulf Grenander. A unified approach to pattern analysis. In Advances in computers, volume 10, pages 175-216. Flsevier, 1970.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 297-304. JMLR Workshop and Conference Proceed- ings, 2010.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011, 2021.
Dan Hendryeks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, al. The many faces of robustness: A criti- cal analysis of out-of-distributiin generalization. Proceedings of the IEEE/CVF international conference on computer vision, pages 2340-8345 2021.
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural computation, 14(8) 2002.
Aapo Hyvärinen and Peter Dayan. Estimation of non-normalized statistical models by score match- ing. Journal of Machine Learning Research, 6(4), 2005.
Ira Semmelmacher-Shlieemmaa Steven M Seitz, Daniel Miller, and Evan Brossard. The megaface benchmark: million faces for recognition at scale. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 4873 2016.
12

---

Published as a conference paper at ICLR 2025
Ilyes Khemakhem, Ricardo Monti, Diederik Kingma, and Aapo Hyvarinen. Ice-beem: Identifiable conditional snergy-based deep models based on nonlinear ica. Advances in Neural Information Processing Systems, 33:12768- 2020.
Beomsu Kim and Jong Chul Ye. Energy-based contrastive learning of visual representations. Ad-
vances in Neural Information Processing Systems, 35:4358-4533 -4558, 2022.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. CIFAR-I0 and CIFAR-100 datasets. URI:
https://www. cs. toronto. edu/kriz/cffar html, 6:1, 2009.
Yann LeCun, Sumit Chopra, Raia Hadsell, M Ranzato, Fujie Huang, al. A tutorial on energy- based learning. Predicting structured data, 1(0), 2006.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553):436 444, 2015.
Yunwen Lei, Tianbao Yang. Yiming Ying, and Ding-Xuan Zhou. Generalization analysis for con- trastive representation learning, In International Conference on Machine Learning, pages 19200- 19227, 2023.
Yaoyong Li, Hugo Zaragoza, Ralf Herbrich, John Shawe-Taylon and Jaz Kandola. The perceptron algorithm with uneven margins. In ICML, volume 2, pages 379-386, 2002.
Zeju Li, Konstantinos Kamnitsas, and Ben Glocker. Overfitting of neural nets under class imbal- ance: Analysis and improvements for segmentation. In Medical Image Computing and Computer Assisted Interrention-MICCA 2019; 22nd International Conference, Shenzhen, China, October 13-17, 2019, Proceedings, Part III 22, pages 402-410. Springer, 2019.
Zichao Li, Cihang Xie, and Ekin Dogus Cubuk. Scaling (down) clip: A comprehensive analysis of data, architecture, and training strategies. arXiv preprint arXiv:2404.00 097, 2024.
Tsung-Yt Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft coco: Common objects in context. In Computer Vision-ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part 13, pages 740-755. Springer, 2014.
Bingbin Liu, Elan Rosenfeld, Pradeep Kumar Ravikumar, and Andrej Risteski. Analyzing and im- proving the optimization landscape of noise-contrastive estimation. In International Conference on Learning Representations, 2022.
Weiyang Liu, Yandong Wen, Zhiding Yu, and Meng Yang. Large-margin softmax loss for con- volutional neural networks. In International Conference on Machine Learning, pages 507-516. PMLR, 2016.
llya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:/608.0333 2016.
lyy Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
arXiv:1711.01111, 2017.
Andreas Maurer. A vector-contraction incquality for rademacher complexities. In International
Conference on Algorithmic Learning Theory, pages 3-17, 2016.
Mehryar Mohri and Andres Munoz Medina. Learning theory and algorithms for revenue optimiza- tion second price auctions with reserve. In International conference on machine learning, pages 262-270. PMLR, 2014.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press. 2018
Ryumei Nakada, Halil Ibrahim Gulluk, Zhun Deng, Wenlong Ji. James Zou, and Linjun Zhang. Understanding multimodal contrastive learning and incorporating unpaired data. In International Conference Artificial Intelligence and Statistics, pages 4348 4380. PMLR, 2023.
13

---

Published as a conference paper at ICLR 2025
Whitney K Newey and Daniel McFadden. Large sample estimation and hypothesis testing. Hand- book of econometrics,
1994.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint arXiv: 2018
Utku Ozbulak, Hyun Jung Lee, Beril Boga, Esla Timothy Anzaku, Homin Park, Arnout Van Messem, Wesley De Neve, and Joris Vankerschaver. Know your self-supervised learning: A survey image-based generative and discriminative training. Transactions Machine Learning Research, 2023.
Bryan A Plummer. Liwei Wang, Chris M Cervantes, Juan C Caicedo, Julia Hockenmaier, and Svet- lana Lazebnik. Flickr30k entities: Collecting region-to to-phrase correspondences for richer image- to-sentence models. In Proceedings of the IEEE international conference on computer vision, pages 2641-2649, 2015.
Zi-Hao Qiu, Quanqi Hu, Zhuoning Yuan, Denny Zhou, Lijun Zhang, and Tianbao Yang. Not all semantics are created equal: Contrastive self-super learning with automatic temperature in- dividualization. arXiv preprint arXiv:2305. /965, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, al. Learning transferable visual models from natural language supervision. In International conference on machine learning, pages 8748-8763. PMLR, 2021.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 11::22211-2 2015. doi: 10. 1263-015-01--11116
Piyush Sharma, Nan Ding, Sebastian Goodman, and Radu Soricut. Conceptual captions: A cleaned, hypernymed, image alt-text dataset for automatic image captioning. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2556-2565, 2018
Ravid Shwartz Ziv and Yann LeCun. To compress or not to compress--sell-superviiiee learning and information theory: A review. Entropy, 26(3):252, 2024.
Yang Song and Stefano Ermon. Improved techniques for training score-based generative models. Advances in neural information processing systems, 33:12438-12445 2020.
Yang Song and Diederik P Kingma. How to train your eneggy-based models. arXiv preprint arXiv:2101.03288. 2021.
Yang Song, Sahaj Garg. Jiaxin Shi, and Stefano Ermon. Sliced score matching: A scalable approach to density and score estimation. In Uncertainty in Artificial Intelligence, pages 574 584. PMLR, 2020a.
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint 1rXiv:2011.134560 2020b.
Duy-Nguyen Ta, Eric Cousineau, Huihua Zhao, and Siyuan Feng. Conditional eneryy-based models for implicit policies: The gap between theory and practice. arXiv preprint arXiv:2207.05224 2022.
Yonglong Tian, Dilip Krishnan, and Phillip Isola. Contrastive multiview coding. In Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16, pages 776-794. Springer, 2020.
Lan Truong. On rademacher bosplex generalization bounds for deep learning. arXiv preprint arXiv:2208.04230 2022.
14

---

Published as a conference paper at ICLR 2025
Michael Tschannen, Josip Djolonga, Paul K Rubenstein, Sylvain Gelly, and Mario Lucic. On mutual information maximization for representation learning. arXiv preprint arXiv:1907.13625. 2019.
Eric Veach. Robust Monte Carlo methods for light transport simulation. Stanford University, 1998.
Eric Veach and Leonidas Guibas. Optimally combining sampling techniques for monte carlo rendering. In Proceedings of the 22nd annual conference Computer graphics and interactive techniques, pages 419 420994288110 1995.
Hiroki Waida, Yuichiro Wada, Léo Andéol, Takumi Nakagawa, Yuhui Zhang, and Takafumi Kanamori. Towards understanding the mechanism of contrastive learning via similarity struc- ture: A theoretical analysis. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pages 709-727. Springer, 2023.
Bokun Wang and Tianbao Yang. Finite-sum coupled compositional stochastic optimization: theories and applications. In Proceedings of International Conference of Machine Learning, 2022.
Feng Wang, Jian Cheng, Weiyang Liu, and Haijun Liu. Additive margin softmax for face verifica- tion. JEEE Signal Processing Letters, 25(7):926-930, 2018.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International conference on machine learning, pages 9929-9939. PMLR, 2020.
Yifei Wang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. A unified contrastive energy- based model for understanding the generative ability of adversarial training. arXiv preprint arXiv:2203.13455. 2022.
Ying Nian Wu, Ruiqi Gao, Tian Han, and Song- Chun Zhu. A tale of three probabilistic families: Discriminative, descriptive, and generative models. Quarterly of Applied Mathematics, 77(2): 423 465, 2019.
Jiahao Xie, Xiaohang Zhan, Ziwei Liu, Yew-Soon Ong, and Chen Change Loy. Delving into inter- image invariance for unsupervised visual representations. International Journal of Computer Vision, 130(12):2994-30) 3013, 2022.
Tianbao Yang. Algorithmic foundations of empirical x-risk minimization. arXiv preprint arXiv:2206. 00439, 2022.
Xiulong Yang and Shihao Ji. Jem++: Improved techniques for training jem. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 6494 6503, 2021.
Chung-Yie Yiu Yau, Hoi-To Wai, Parameswaran Raman, Soumajyoti Sarkar, and Mingyi Hong. Emc?: Efficient meme negative sampling for contrastive learning with global convergence. arXiv preprint arXiv:2404. 10575, 2024.
Laurent Younes. On the convergence of markovian stochastic algorithms with rapidly decreasing ergodicity rates. Stochastics: An International Journal of Probability and Stochastic Processes, 65(3-4):177-228, 1999.
Zhuoning Yuan, Yuexin Wu, Zi-Hao Qiu, Xianzhi Du, Lijun Zhang, Denny Zhou, and Tianbao Yang. Provable stochastic optimization for global contrastive learning: Small batch does not harm performance. In International Conference on Machine Learning, pages 25760-25782. PMLR, 2022.
Zhuoning Yuan, Dixian Zhu, Hao Qiu, Gang Li, Xuanhui Wang, and Tianbao Yang. Libauc: A deep learning library for x-risk optimization. In Proceedings of the 29th ACM SIGKDD confer- ence on knowledge discovery and data mining, pages 5487-5499, 2023.
Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre-training In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 11975-11986, 2023.
15

---

Published as a conference paper at ICLR 2025
Rui Ray Zhang, Xingwu Liu, Yuyi Wang, and Liwei Wang. Mcdiarmid inequalities for graph- dependent variables and stability bounds. Advances in Neural Information Processing Systems, 32, 2019.
Ce Zhou, Qian Li, Chen Li, Jun Yu, Yixin Liu, Guangjing Wang. Kai Zhang, Cheng Ji, Qiben Yan, Lifang He, et al. A comprehensive survey on pretrained foundation models: A history from bert to chatgpt. arXiv preprini arXiv:2302.0944 2023a.
Zhihan Zhou, Jiangchao Yao, Feng Hong, Ya Zhang, Bo Han, and Yanfeng Wang. Combating representation learning disparity with geometric harmonization. Advances in Neural Information Processing Systems, 36:20394-20408, 2023b.
Benjin Zhu, Junqiang Huang, Zeming Li, Xiangyu Zhang, and Jian Sun. Eqco: Equivalent rules for self-supervised contrastive learning. arXiv preprint arXiv:2010.01929, 2020.
Yongshuo Zong, Oisin Mac Aodha, and Timothy Hospedales. Self-supervised multimodal learning: A survey. arXiv preprint Stti::3044000008. 2023.
A OTHER RELATED WORK
In this section, we discuss previous research on discriminative and generative probabilistic modeling and theoretical amalyses of self-supervised learning that are relevant to our work.
A.1 DISCRIMINATIVE AND GENERATIVE PROBABILISTIC MODELS
Over the past decades, numerous probabilistic models have been developed for machine learning and pattern recognition problems (Grenander 1970, Wu et al.) 2019). Our work closely related to previous works on discriminative probabilistic models for supervised and unsupervised learning, generative probabilistic models, and the recently proposed hybrid probabilistic models.
A.1.1 DISCRIMINATIVE PROBABILISTIC MODELS FOR SUPERVISED LEARNING
For supervised learning, discriminative probabilistic models learn the conditional probability mass function p(y x) of y given data x. Since the 2010s, discriminative probabilistic models based on deep neural networks, such as ConvNets, have achieved tremendous success in supervised learning tasks (LeCun et al. 2013), where y is a class label from a finite set of categories. Despite the avail- ability of scalionn-scale datasets with label annotations (Deng et al.] [009 Kemelmacher-Shhizzae Shlizerman it al., (016)) scaling of these models is hindered by the enormous cost of collecting even larger curated datasets with label annotations.
A.1.2 GENERATIVE PROBABILISTIC MODELS
Generative probabilistic models typically focus modeling the marginal distribution p(x) of real data. In particular, an energy-based generative probabilistic model can be defined as pe po (x) exp( exp(-Ex(x)) where (x) is called the energy parameterized by 0 and Z is the partition func-
tion (LeCun et al.] 2006). The intractable partition function is the key challenge in training an energy-based generative probabilistic model. Markov Chain Monte Carlo (MCMC) sampling is a
popular approach for calculating the gradient of the model parameter of the log-liieldoood (Younes)
1999 Hinton] 2002, Gao et al., 2018 Du and Mordatch 2019 Du et al. 2020). However, MCMC
sampling is computationally expensive. MCMC-free approaches such as score- mottcing (Hyvärinen and Dayan 2005 Song et al. 2020a] Song and Ermon 2020 [Song and Kingma 20211 [ong et al.
2020b) have been proposed to learn model that can be used to generate the data through MCMC sampling in the inference phase. On one hand, generative modeling tasks are generally more chal- lenging than discriminative ones. For discriminative tasks, such as classification and retrieval, suffices to have the predicted conditional density p(- x) of relevant y be higher than that of an irrelevant y. In contrast, generative tasks require a much more accurate high-dimensional density estimation to produce high-quality new data. On the other hand, training and inference gener- ative models typically demand more time and computational resources compared to discriminative models with similar number of parameters.
16

---

Published as a conference paper at ICLR 2025
A.1.3 HYBRID PROBABILISTIC MODELS
Grathwohl al. 2019) propose the Joint Energy-based Model (JEM) to simultaneously perform discriminative and generative learning by maximizing the likelihood of the joint distribution p( ((,y) for each image-label pair (x.y), which can be factorized into an MCC problem solved by mini- mizing the CE loss and generative modeling problem solved by the stochastic gradient Langevin dynamic (SGLD). When label annotations are absent, Wann et al. (2022) and Kim and Ye (2022) model the joint distribution p(x, x') of data point x and its augmented copy x'. Specifically, Wang et al. (2022) directly maximize the oogllikelhoood of the joint distribution p(x, x') via adver- sarial learning, while Kim and Ye (2022) follow the idea of JEM to decompose the log- lig-liieldhood logp(xx x') into the sum of a generative term lxg and a discriminative term log p(x' x). In Kim and Ye (2022), the gradient of the generative term is computed by multi-stage SGLD, and the discriminative term is approximated by the InfoNCE loss with a finite number of negative data. More recently, [Bizeul al. (2024) proposed the Sim method model the joint distribution of semantically related data (e.g., different augmented copies of an image). The Sim VAE maximizes the evidence lower bound (ELBO) of the log- oog-iieeihood by introducing the implicit latent structure of SimCLR into the variational autoencoder.
A.2 THEORY OF SELF-SCPERVISED REPRESENTATION LEARNING
In this section, we review additional papers on the theoretical properties of self- self-supprvvsed represen- tation learning from broader perspectives. The pioneering work by Arooa et al. (2019) established generalization bound for the minibatch-based InfoNCE loss that contrasts each positive pair with negative pairs in the sampled batch. They formally proved that the unsupervised error can bound the classification error of a constructed mean classifier. Following the settings in Arora et al.) (2199) Lei et al. (202)) refined the analysis and improved the generalization bound by a factor of k. However, both results above depend on the assumption that the negative data points are independent from the anchor data points, which does not hold for contrastive learning algorithms used in practice Moreover, their results suffer from a limitation that the generalization error increases as the number of negatives & increases, which contradicts the practice. HaoChen et al.] (2021) proposed a spec- tral contrastive loss and established generalization bounds for both representation learning and the downstream classification. Based on a sepphddeenddentt McDiarmid inequality and a U-statistics re- formulation, |Waida et al. (2023) proved the generalization bound of a kernel contrastive loss (KCL) without assuming the independence between anchors and negative data. They also provided theo- retical guarantees on downstream zero-shot classification. Recently, Chen al. (2024) established a generalization bound of the symmetric minibatch- sumption that image and text are conditionally independent given their common shared feature. However, the convergence rate of the generalization error is also worse when the minibatch size in- creases. They also proved that an approximate minimizer of the population loss leads to infinitesimal zero-shot classification error under the assumption that "good" encoding functions exist.
InfoNCE loss used in CLIP, under the as-
Besides, Wang and Isola (2020) proved that the asymptotics of the InfoNCE loss can be decomposed into two terms that optimize alignment and uniformity, respectively. Tian et al. (2200) showed that minimizing the InfoNCE loss can maximize the mutual information between two views/modalities
since the loss is a lower bound of the mutual information. |Tschanenn et al. (0019) demonstrated that the success of InfoNCE loss cannot be fully attributed to information maximization because maxi- mizing a tighter bound of mutual information leads to worse empirical performance. Nakada et al. (023) show that the gradient descent steps of minimizing the symmetrie InfoNCE loss of CL.IP can be viewed as performing singular value decomposition (SVD) on a contrastive cross-covariance matrix when the representation is linear. Shwartz Ziv and LeCun (022)) proposed a unified frame- work for self-supervised learning based on information theory. They surveyed numerous existing approaches and demonstrated how their framework can encompass these approaches.
A.3 CONTRASTIVE LEARNING FOR LONG-TAILED DATA
Recently, several papers have proposed contrastive learning algorithms to address the challenge of long-tailed semantic distributions in real-world datasets. For instance, [Assan et al. (2023b) intro- duced a method that applies a user-specified power-law prior to the distribution of representations
In practice, the negative data points for each anchor are from positive pairs of other anchors.
17

---

Published as a conference paper at ICLR 2025
learned by Masked Siamese Networks (MSN). Based on the geometric harmonization method, Zhou jet al. (223b)) proposed a bilevel objective to promote category- level uniformity instead of sample- level uniformity in the representation space. Qiu et al. (2023) proposed a robust contrastive loss inspired by distributionally robust optimization (DRO), which dynamically learns individual- ized temperature parameters for data points with frequent or rare semantics. The high-level ideas estimates the nonuniform g(d) = Σ p(y, xxy) to
of these papers are related our work, reduce the error of Monte Carlo integration, while the papers above also model the uniformity in data. However, our work is grounded in the statistical framework of DPM. It remains unclear how the losses above can be interpreted within the DPM framework or whether these approaches can address the non-diminishing error issue in GCL. Moreover, it unclear about the effectivess of the approaches (Assran et al.) [023b Zhou et al.
20233b in bimodal self-supervised learning, as they
focused on the unimodal setting. In Appendix G.3.1 we compare the experimental performance of our NUCLR with that of Qf et al. (2023) in bimodal self-supervised learning.
B MIS WITH A GENERAL. WEIGHT FUNCTION FOR DPM
We consider the following MIS-based estimator with size-m sample from each distribution p(- xj) and a general weight function w for the integral g(w; (W, = fy exp(Ew (x.,))/))))(
(y exp ( (Ew (x..)))))), Ei ply,, x;)
(w;
Σ
Uly......... Vim), (16)
j=1
where w is a weighting function such that (y) is on a probability simplex, Vy E y. We denote X (y,,)
{xI,..., Xn (w,,, == p(ss,)x;)) exp (Ew (x.)T/.)) We consider the "balance heuristic" ,
( (y) Σ7., ,(vlx,))* Vy y and vj [n] proposed in Veach and Guibas (1995). Proposition wol
shows the unbiasedness of the estimator in (T6) and justifies why we choose the balance heuristic.
Proposition 1.
For each w. we have that g x,, Y.w) is an unbiased estimator of the integral g(;;,, (ū) The balance heuristic Wil minimizes TE[ E[E 1 E (u.(w,, X] among all
possible weighting functions for any i. where E[E m EE (w.(w.y..) 2 X] is an upper bound of the variance Varlğ( w; Y.w) X]: (ii) If Pyyaa xy) 2 (()), Vj E
[n], E [m]
almost surely and Assumptions hollds the variance goes to zero when n + oo or m co.
Proof. Since for any j E [v)] Yi.h.... y.im Vim are i...d. distributed, we have
w (y..)) exp (Ew (x4, X
[[W: W.) X = Σ
E
p(y;,1 X)
j=1
" S w00
ply xx)) ply X2) exp (Ew (x) = J Σ (y) exp (Ew(( du(y) j=l
=
F
= S, exp (Ew (x: y) du(y),
(17)
where due to Tonelli's theorem. Since (ysx)se[m].eel [e[]) are mutually independent and for a specific j. Nj......:ji. are i.i.d,, the variance of the estimator in (T6) can be upper bounded as
Varlğ w; X Y. w)
Σ EEE
X
1 E , y3.1) X)2
(18)
m
m
j=1
w (y) exp (Ew ()x, dyly).
<
Σ E[E (w.
X
Σ
j=1 y
ply xi)
Due to Tonelli's theorem, we have
f wi) (y)² exp ( (x,, (x;, v)/7)
(v) exp ( (Ew (xi, dully)
du(y)= = y 1-1
ply x,)
ply x,)
18

---

Published as a conference paper at ICLR 2025
We instead minimize the variance upper bound at each y pointwise. Then, minimizing Σz-1 w (y)) expl Ex(x)))/T) subject to the simplex constraint leads to whl (y) 2.-1)(0),))) p(yxx))
p(y)x)
Varlo(w;X,, Y, whi)
[X]
1 m
Σ E[ (wh) V j=1
1 m
Σ 5=1
E
exp Ew (xi, VT.1/T)2
(E/= p(y;11 xx,))²
< num S
(x: dp(y) o )
Interestingly, the minimizer Wht of - E (.) X] does not depend x, We
can obtain the estimator in (4) by plugging the balance heuristic whl into (16) and letting m
C PERFORMANCE OF DPM ON DOWNSTREAM ZERO-SHOT CLASSIFICATION
Suppose that the true conditional density function p(y x) is generated by some w. W, i..., exp(Ew., (x.y)/r)
ply x) Pw. (y x) In exp(Ew, (())d)))))( Then, the maximum likelihood estimator w, arg max !, Ei log Pw (y:s x,) with the random sample ((,, y:) 1- converges in probability to w, under some mild assumptions (see Theorem 2.1 in Newey and McFadden (1994)).
Consider the downstream multi-class classification with K 1 distinct classes. The task is to predict the ground- truth label c(x) E {I...., K} data x X. Suppose that there are K subsets ,Yk "/,...,y/s of y and any é VA belongs to the k-th class. Moreover, the ground-truth label c(x) of data x c(x) = arg maX Pr(k: x). Given the model w. trained via MLE, the predicted label cw, (x) of a data x E X can be obtained by the following 1-nearest neighbor (1-NN) classifier:
Cār, (x) = arg max Ew, (x,) ke[K]
where Y& é y is an example of the k-th class. For instance, the example yı of the k-th class of the downstream image classification could be "a photo of (class k]" when X' is the image domain and Y is the text domain [Radford et al. 2021). Due to the monotonicity of the function exp(//T) and the expression of Pw in (1) have Cw. (x) arg maX Ew. (x. ) arg max Pw. (yx x)-
As long the probability mass Pr(k x) on class k is proportional to the probability density p(yx x) on the example of class k the zero-one loss Ea/1 (x, c(x); w.) I[[.. (x) # c(x) on the data-label pair (x, c(x)) of the downstream classification approaches zero when w, & w.-
D PROOF OF THEOREM
The structure of our proof is as follows:
Section D.I
presents necessary lemmas for our generalization analysis.
Section D32
decomposes the generalization error into two parts, which are handled by Section D.3
and Section D 4
respectively.
Section D.5 provides bounds for Rademacher complexities of function classes parameterized by
deep neural networks. The main theorem can be proved by combining (20). 21
23
31
D.1
LEMMAS
The following two lemmas provide contraction lemmas on Rademacher complexities. Lemma considers the class of real-valued functions, and Lemma considees the class of vector-valued func-
tions (Maurer 2016; Lei et al. 2023). Let e, and e, be independent Rademacher variables, i.c., with the same probability.
they take values in
19

---

Published as a conference paper at ICLR 2025
Lemma (Contraction Lemma, Thm 11.6 in Boucheenn et al. 2013)). :: R. be convex and nondecreasing. Suppose th: + contractive (1b(t) - vt)) s Gltt - fl) and x0 = Then for any F we have
E sup Σ (((i)))))) BeT Gsup Σ ea((())) fcF 2-1
leF
We say that function R R is G-Lipschitz continuous w.r.t ||-122 if (V(x) x(xx) G||x xl112 for G> 0 and any x, x ERR.
Z + R& which contains the zero function. Let T: RR, be continuous, non-decreasing, and convex function. Assume I1...., In IR. IR
Lemma 2. Let F be class of bounded functioons Z
are G-Lipschitz continuous w.E.f || 112 and satisfy d. (0) = O. Then
Be-(+ sup fEF
Σ (x):( (eexx))) (GV2su)
(x)s((x)))
(19)
f i-1j-1
The following lemma estimates the moment generating function of a Rademacher chaos variable of order 2 (De la Pena and Giné 2012).
Lemma (De Pena and Giné 2012). Let G, e [n] be independent Rademacher variables. Let ai R. i E [n]. Then for Z = Lisijjsn Eejai have
exp (IZI(4es)) $2, where 5² :=
Σ
Isicisn
The following lemma is version of Talagrand's contraction lemma.
Lemma 4 (Lemma in Mohri and Medina (2014)). Let H be hypothesis set of functions map- ping to and vo is G-Lipschitz functions for some G > O. Then, for any sample S of n. points Fiy In X, the following inequality holds:
G
E
Σ (<b((((z)))
s Ees..
sup Σ cg((a:)) hee i=1
hEPL 1=1
D.2 ERROR DECOMPOSITION
Considering log, x S x 1 for any x > O, we have
2(w;q.5) L(w)
n
1
= Exxyy [ (x]
Σ
Ew (x,,
+
Σ
r
log(ū(w;X;; w: Y)) Ex [x[T [ologo(w:x.])
1-1
n1 i-1
Σ कoा exp( (Fw (xx -1)-))
1
1 Σ Ex
-Exyy Eww ()]
Σ Ea Xis y:)
log
Jy exp (xw)
72
72
< Exxy Fow [Ew (x.
Σ
Few Vi)
n Tm1
C R n
exp(Fw (x:,,)))) CFx IS, (x
(20)
[06
=1
where we define Ew (x. == Ex(xxy)-1 & 2- 0] such that exp( Ew (x, v)) é [exp(-2/T))
Besides, and = supxex oxp (x.)))))
Due to Assumption
C s w())
rexp(2/T)
< oo. In
20

---

Published as a conference paper at ICLR 2025
practice, C could be much smaller than the worst-case value rexp(2/r), (())
Similarly, have
n Σ
((w) (w:; q. S) s
Ew (x;; - Ex, Fo (x,))
(21)
1=1
C'Ex Fx [s (x
C
exp(
exp(Pw Pew (xi:;))))
g(3)
i=
where ='==làl- exp(2/7).
D.3 BOUNDING TERM
Define the function class & y) H yx. w W). Since (iI..))........ (x,. V.) are i...d. and Assumption Ex.y [ (x. y) 3.3 in Mohri al. 2018). With probability at least 1 4
[Ew( () E [-1,1] for any w E W), we can apply the McDiarmid's inequality to E yx) and utilize the symmeterization argument following Theorem
s 1 Σ Ex,y Fw y)]
log (8/)) 2n
Fw (x), (0) 6V
where (8) Ex y D (8)]. (E) = B.y. [sup En E: (x;, y:) is the empirical
Rademacher complexity of on the sample Xx Y. and E En are Rademacher random variables. Similarly, we can also apply MeDiarmid's inequality to Σi-1 E (x;,y;) Ex then use the symmetrization argument. With probability at least 1 1 7
w [
(x,y) y)] and
1 n
log (8/0)
Ew (x), (x, (2) + 6V
2n
Thus, with probability at least - 2. we have
n
log(8) (88)
Σ Em (x), - Ex, E - (E) 6V
(22)
2n
D.4 BOUNDING TERM II
We decompose the term II in 20 as follows.
ΣΣ
exp( Few (,)) Fxx [S exp(Fx(xx,))) (xp((
=11== (0))
Σ Σ
exp(Ew((x)x)))
(c))
q()}
=1
n a ΣΣ
S (xp((((xx.)))))))))
exp En (x,,1,)) Fx
(23)
n 1-1 g(o)
11.b
Thus, have [T| [T..]] [T.b].
Since exp( (x. (x) 1)/r) for any
x E X. y e v,, we have
1
1
IT.a|
Σ Σ
s
(24)
g01)
p(3)
g(5)
1=1
==1
We define T(X, = supw ( Σ के. (x - Fx [/y exp( Em (x, y) r))dd((]]]]
We denote that X; (X1(xx)) (xx), Y, (mMr))) (y²), where (x). ..... (x,r
21

---

Published as a conference paper at ICLR 2025
L.d. to (x1.y))..... ..... Nn). We denote that q(;; X) == Σ Exex p(y x) such that (latt))) q(y;; X))
gq E/ ply, xy) (n) almost surely, we have
|TX,, Y) - r(x,; Y)
12
1 1 (x. O(1/n),
Σ
exp (w sup Σ n j-1 g(yziXe)
sup 12 j-1 g(5)
[T X, 8) I(x, Yo)l
sup Σ w 1-1 {
sup 1 Ew (xi,
exp( Ew (x, v')) s0(/n)).
w n. g X)
Since x; and y, mutually dependent only when i j. then apply the MeDiarmid-Tyy Type inequalities for graph-dependent variables (Theorem 3.6 in Zhang et al. (0199) to the term II.b and -II.b. With probability at least 1- 1. 8 (0,1). 1). we have
10 n
I1.b s E sup ILb O
(25)
Similarly, with probability at least 1 4. 8 E (0,1), we have
-II.b s sup (-I.b) +0 oV
10 (4/8)
(26)
Let (x). (%) be a virtual sample i.i.d. to (x1, Yn). Denote that X'
{xi,..., Xn), Y == ..). Due to (17). we have
Ex SS exp(( Fow (x, y))dd(()))))
Ex
a
exp( Pe exp(Pn (x(xx
1=1 (();:81)
We can rewrite and decompose the E [sup II.b] term as
f-1 (0)) exp(Ew Ex U, (x.
E sup
IL.b
E
sup w
TI
sup
1-1 j-1
Σ Σ
q()
exp( Ew (x., - E 8
1-1 j=1 q (y(; X1)
exp
1
1
1
sup $ &
exp (xi,
exp (w
w
n2
E1 (y;;))
n
i-1
ay' X')
1
sup + +
exp( P.re (x:,),))
ΣΣ
Σ
exp
Frr exp(Fmm
(x..
w
1-1 jai q())
|-1
q(y;
1
+E S 0((1/))
sup
ΣΣ je2 ((3)
exp( Ew (x,,)))
2- gei qly X!) exp( En (x4,3))
Σ
71
the last step is due to the assumption (y:; proof technique in Theorem 6 of Waida et al. 2023). W.l.o.g. assume that n is even (If is odd, we can apply the following analysis to the first n 1 terms in the summation, where n - is even. The last term in the summation is ((1/n) term, which does not change the result), Suppose that S, is the set of all permutations (the symmetric group of degree 12). Then, for each s é S, pairs (x+(26-1)) 1)), Ye(2)) (i = 1....,n/2 are mutually independent. Consider the alternative expression of a U-statistics of order 2 (See Appendix I in Clémencon et al. (2008)) exp Ew (x.)))()))))))
Σ y-1 ply: x 2 R(n). Next, we adapt the
n/2 Σ nn(n/22 sES,, 1-1 (()x(2))
ΣΣ
(-1 joi g(n) exp(
1
Σ
n(n (n - 1)
22

---

Published as a conference paper at ICLR 2025
It then follows that
n21
Σ (x
exp(Ew (x (X' (2-
sup ILb & O(1/n)+
sup
n//
71.
S
((vs(21)i
{(''(22)) X')
1-1
n/2
exp( Ew (x.(25-1))
exp(Liw (2)1 )((22))
s <0(1n)
E
sup
n12
SESp
((V((2)):
a(y (2)))22)) X')
O(1/n)+
n-1
E
supp
n/2
Σ
exp( E. (x26-1
exp( Ew (221-19-/11))
n/2
w 1-1
(V22:
q(y X!)
n-1 O(1/n)
n/2
exp( Ew (x2--1
exp( Ew (X
E
sup
Σ
6/
n/2
((2:; X)
(y X')
s 5(11n)+ 2(n 1)
n/2
E, exepp( Ew (x21
sup
n//
((y2;: X)
where we have used the symmetry between the permutations in S, and (x,, (x,.1) By Lemma and the assumption (y2;; X)= Ey=1p(y xy.) 2 f(n). further get
n/2
E sup s (0(1/))+ O(1/n) sup Σ i=1
E ( 129))
Define the function class 9 = (x,,) exp(Ew w E W). Then, we define the following empirical Rademacher complexity
2 n
n/2
A (G:))=
E B2sn/
sup
Σ w
G (x
We further define the Rademacher complexity 9 2 (9) == max Ex y (9 (G) We can
also apply the symmetrization argument above to bound E[sup Due to Assumption 1 can bound the II.b term as: With probability 1 2. 8 (0, 1), have
10 lo 4/6)
|l.b] s ((1)))
(27)
D.5 BOUNDING RADEMACHER COMPLEXITIES
We consider the specific similarity function:
(x,,)) F. (W1;x) E2(w2:y)
We consider I--layer neural networks
E, (wi;)) Fi, (W (W x))) |
Bi),
Eg (W2:y)) F2.L = fy + oW WW ((2,1v))) 1[2.l Bi).
Suppose that Wi, E 1dd,,, We Rdzaxdaa-1 and d1,0 = d1, d2 = d2. d1.1 = d2.r = dz- Define WT (W>(1) are adaptions of the results in Golowich et al. (001).
((d))) where w(()) is the 1-th row of matrix W,. The following results
D.5.1 BOUNDING (E)
Define h: 1R2dd R as h(v) = v2 where 1h E (wi;x), Ew (W2;y)). Due to Assumption
Vi
and v1. V2 Rd. It is clear that Fw (x.y)
V2
we have E (w)x))l s 1 and [
VI (v2) .'=
()) and v1, V2, vi.v E [0, 1]d, we have
v/
For any v=
(N(v) 1(v))² 22(v] +
-v))) 2( v
23

---

Published as a conference paper at ICLR 2025
where we have used (a + b) 2a² 25 and the decomposition vive -v()' vv (v2-v (v1 - v "vy. Thus, we can conclude that I-Lipschitz continuous to v and apply Lemma 2 to the function E (x,y) h(Ei (w1;x),
w2: (W))
1 n Σ ((
(E) Er
sup cEE n E=
< E
ExE(+1)add
sup Σ ΣΣ7
(3.1) E
(WI; + c.i
(1.0) Es (w2.
n
1=1
dv
$ E
sup Σ Ee
6
(1.1 E
(w xi)
- R -
sup
ΣΣ
Σ
(1.1)
E (w2.
71
Fl1ml
2=1ml
di
E ele(+11nde
sup
ΣΣ
(1:00
(fiitm ((()))
72
m1
di (1.))
E (z
sup Wa
(ffa--(())
For simplicity, we can only consider one of the terms above and neglect the index of embedding networks (I or 2). Let x; be one of x, and ys. Cauchy-Schward Schwarz and (sup.r)² s sup x² imply
d2 ΣΣ e of((x)
Bes(=1)"dz
sup We.SeFL lElel
ΣΣ (1.) o (f(:))
(1.)
sup We.JeFL-11-1 1i
d2 ΣΣ o (f()))
sup Wi.
(28)
For A 0, Jensen's inequality implies that
a de (1)) (((x)((())
E Bee(+l)md
sup LL.
Velel
1 log exp
dr ΣΣ 1ll
{(())
AE
sup WL.FoFL-1
1
di Σ Σ vil [=]
< log
Ee exp
sup WL.feFL-1
(1,
of(xx
(29)
X
We utilize the following facts: (i) sup, x² < max (sup, x)² random variable e, we have - are iid.;; (ii) Lemma (iii) 2s & supa?:
and for Rademacher with 7(t) cxp( (tt?) and or is I-Lipschitz;
( o((x))
Ee exp
A sup
Wi./efln-1
a d2 ΣΣ (b,) (()0)((())
$ 2 exp
sup
Wr.fef
ml
(i)
dg ΣΣ (1.0) [(xi) s(x))
S 2E, exp
sup
WWiffFrr-
(in) 5 2E, exp
di ΣΣ (1.0 s(x))
sup
We.feFL-1
24

---

Published as a conference paper at ICLR 2025
Due to (iv) | s Bi for each E [L], we further have
di
Ehe exp
A
sup WinfeFuu-1
ΣΣ
(1,0
of(x:)
1=1ml
$ $2 exp
sup WenfeFI-1
Σ
Σ i=1
(1,)
[(xi)
S 2 exp
sup
||
Σ
Σ (Sw))
f(x))
Wi.,feIL-1
(iv)
$ 2 exp
sup AB
di Σ
Σ
1.0) f(x:)
(')
JeFL-1 c=1
1=1
di Σ
2E, exp
ABJ
sup WL I.feFF 2
Σ
(1))
(W)-
Due to the positive-homogeneous property of the activation function o.), we have
Σ (1.)) of((x)
di
(W
=
=
E (1.0) (x(:)) (
L-1
di
Σ (itt 0 ((x;) w/,21)
Σ
|
Σ
(1,))
wh6 a f(x,)
|
1
F11
de Σ
((r))
W 2 max
Σ (1:))
[(x))
re|d re(ds-11
|
BB
Σ (it) o (f(x))
sup
w:|w 1
Thus, we can obtain
12 di
E, exp
A
sup WLL
ΣΣ (1.))
1=1
dp n Σ (1a) 0 (f(x)) m))
< 2 exp
ABB,BB B?
sup
|w1,s1,feF....
< 2E 2E.. exp
d1 BLAB
sup
Σ [ T ww)
mml
Applying Lemma I with r2(t) = exp (2 gives
n di
n Σ (fxs) (w)x)>/w))) wn))
E, exp
X sup WL.foF2-1
ΣΣ 11=1-=
(1.) o (s((x)
S 2E
sup
1el L-2
Σ [cx(((x)) ) s=1
< 22
TA
sup
Σ (a(((x))' w)
2E
TA
sup
|wl,5t,feF1.225 1=1
4B
TA
sup
Σ (e((f(x))Tm) Tw))
< $4Ee
Tx
sup
Σ [xi((x))Tv) ww
|w],sl.feFe
|w],sl,feFF
2 i-
)1
Σ (xx, w 1
5 4B
TA
sup
Σ Eeo(WL
5 4E
Tx
BL-2
sup Iw IwIps1,fefr.n
25

---

Published as a conference paper at ICLR 2025
where in the last step we have used the positive-homogeneour property of (-) (e.g., analysis similar to handling the supremum over WL,F f FL-1). Applying the inequality above recursively over the layers leads to
E. exp (x sup WI.JeFL-1
|.]
ΣΣ
( of(xx) 22
TA
I B
Σ 1=1
C
=1
1=1
Plug the inequality above into
29
a ΣΣ
o 27 } ((((x)
x log 2 exp de (odddd
H
L
|
E
(!))
Bee(#1)nde Wi..feFi-.
sup
Let x drd (TT Bi) and choose X Beads (TT BF) 8 ( (x) (x)))) Then, Ā
1/(8es) and we can apply Lemma 3 to show Een. eexp (2) Eisisisn c x;)] 2 such that
Erg.. exp
Σ
Erg
exp
i
Σ 5m1
Xi
2 2Á
Σ lsssisn
6xc X:
n A Σ
exp
i
| 2/z
Bera
exp
Σ
Gepx Xg
S exp
|x113
Isisish
i=1
Since X (1sd) 1p)) and s² S E Eisisisn |xx1112 |x;| 12 S (Ei ||x l1xx13)
we can obtain
n ΣΣ
(1:1) o (f(x)) (w(x)) )²1
)3
S log 2 exp ( {ΣΣ |x: 1x113)
Bees=1Jadr
sup We.feFL-1
1-=1i=1
1=1
(L+ 1og
dp
I B
Σ
|
s dr
[ B$ (8(I. (((T+1)eelgg
L
n log 1)
Σ
1x.
A
1=1
1-1
i=1
1-1
Due to 28 we can obtain
1
L II
(E) Eei
sup
Σ ((
di
B² 111
(8(L+ + 1)elog + 1)((1 02).
eef ni 1-1
nn
(30)
D.5.2 BOUNDING (g)
We define the dataset D. ((x(()))<(2))) (X.(n..,....))--.X.... (s(m))) Consider {(x,y) Ew (x, y) w W) and the following two function classes
E = ((x,y) Ex. w weW W), G {(x,y) + exp(E (x, x)) W WEW.
The empirical Rademacher complexities of E on D. can be defined as
2
a/2
n REis(Eis) -.
sup n w
Σ
e, Ew
(x.
b (9: Beenm
2
sup
n/2
Σ
4exp
Fow (Xo
n
Note that + exp(1) is 1- L-pisschitz when L O. Due to Lemma 4 and Ew (x, = (Ew (Ew(x)))-1//z
Rip (G: s) (E (E:ss)
(31)
Then, bound R (E;8) in the way similar to bounding (t)(E)
(E) in Section D.5.1
26

---

Published as a conference paper at ICLR 2025
E
PROOF OF THEOREM 2
Proof. The problem in S is equivalent to
min CEE
n Σ 1=1
log Σ
((0))
+ - n
Σ
(32)
n2 y=1
We define that +(() = Σi= log [Σj- exp( (E),, E y:) (7)
Due to the first-order optimality condition, any optimal solution S. to ( satisfies
exp(F(xy.,,)/7))
exp Ly= exp( (()/T)²
Vje [je[n].
p by changing the variable g()) = exp(<. (5) /T) for any j E [m].
Then, we can obtain
Due to the property of the log-sum-exp function and yx) [1-1, 11. we have
1 1 Σ max (E(x,,,,) - E(x,, + Σ ( 2-2 min ((5) (C)) 2
[q(m] -- m
Σ5
(())) 2 -2.
1I [
11 5=1
Thus, (C) proper convex. Besides, each line parallel the diagonal line d, = {{ Ç 11 2
R} can be expressed as (b) [[c|s- = =1,
b ,2 R with some unique b E Rn For exam-
00
ple, in the case n = 2, line (b) with some be E R can be rewritten as db( = { (0)) (1)) + b), which is parallel to the diagonal line d2 = {5 ((() = (()). For any point on a line d (b),
12 (C)
Σ 1-1
log
Σ (xxp((E(x,,)) - - 2(+0)))) +
Σ 80)
n=1
12 Σ s=1
log
a exp( (xp(-2//) Σ (Ex(((E(x,))) E(x;,))))) -6())/7)
+ +
-
1 m
Σ (6)
F=1
j=1
n Σ 1=1
E(x,,)) -60)) 1 ạ b00
Σーこ j=1
log
where the expression on the R.H.S is fixed when z varies. Then, the value of +CC) does not change along the line d,, (b). Note that every point Ç R" is uniquely located on one line (b) parallel to
the diagonal line n Thus, if C. zu 1, b. with specific 2. E R and b. e = is a minimum of (C)) then any point on the line (b.) is minimum of (CC).
There may exist uncountably infinite many b. e RR=1 and every point on (b.) minimizes (C)). However, can rule out such case since the set of minima of proper convex function is convex and (C) is strictly convex along any direction other than the diagonal and parallel lines [6 Thus,
there is only a unique b. -g and any point on (b.) = -ccss = =1, b. 2 E minimizes Φb (C)), i.e., the minimum of (C) is unique up to an arbitrary scalar additive term E IR.
F MORE DISCUSSIONS ON NUCLR IN ALGORITHM
F.1 COMPUTATIONAL AND MEMORY OVERHEADS OF NUCLR
The computational cost of updating w in NUCLR is O( Bd), where B is the batch size and d is the total number of parameters in the model w. This cost is identical to that of SogCLR. The additional computational cost of NUCLR lies in the update of & (line 4 and line 5 of our algorithm).
Fach log-sum-exp function is strictly convex along any direction other than diagonal and parallel lines.
27

---

Published as a conference paper at ICLR 2025
(1) The computation of "(C:") w.r.t. ( in (14) requires {"t-1) )ess ja and āदt Ss Wr. Cz; B.). Here (1 JeB, is also needed in SogCLR so it does not result in additional cost. Besides, note that 2 açtn (we,,, B.) (B-1)r
a
n-1
Ew, (x..,,, ,) - (x.. where the shaded part is already exp
computed in the forward propagation and does not incur additional cost. The computation of the gradient w.r.t. 5!9) only involves summation of B scalars such that the computational cost of line 4 and line 5 of NUCLR is only O O(B²). Since d exceeds 70 million in our experiments, the O O(B²) additional computational cost of NUCLR is negligible compared to the dominant O(Bd) term.
Compared to SogCLR, NUCLR needs to store one extra n-dimensional vector Ç. Maintaining Ç in GPU only requires less than 100MB for 12 million data points, which is negligible compared to the GPU memory required for backpropagation. Moreover, we may instead maintain the vector in CPU and only transfer those needed { juss, to GPU in each iteration. The overhead can be further reduced by overlapping the communication and computation.
F.2 MARGIN INTERPRETATION OF NUCLR
Cross-entropy and contrastive losses with a positive additive margin have been widely studied in the
literature (Li et al. 2002 Liu et al., 2016 Wang et al. 2018: Cao et al.] 2019 Li et al.) 2019 Zhu et al. 2020). which can be viewed as smooth version of the hinge loss to separate the matching (positive) pair y;) from negative pairs { (x; yy + y,
Y, E ))) In supervised learning tasks such face verification and multi-class classification, using a relatively large positive margin has been shown to be beneficial (Wang et al., 2018 Cao et al. 2019). However, the "false negative" issue more pronounced in self-supervised learning. Determining the appropriate (positive negative) margin becomes more difficult, as aggressively and uniformly pushing negative pairs away from positive pairs may hurt the performance (Xie al.) (022). As shown the objective in (IT). our NUCLR algorithm adopts an individualized negative margin (6) for each negative data y; when updating the model parameter w. Rather than relying on an expensive grid search for individualized margins, our method learns them in a principled way. Recall ((i) can serve as a measure of the popularity since q()) oc exp(c(0//7) when (b) is optimized. As a result, NUCLR may help tolerate potential false negatives because the negative margin (()) between pairs (x) and (x), is larger when y, is popular, as it is more likely be false negative.
G MORE EXPERIMENTAL RESULTS
G.1 DETAILED SETUP OF THE TOY EXPERIMENT IN SECTION 3.3
We construct a dataset $ = =(x;, y:) by uniformly sampling Xi,..., Xn from X and then sam-
pling each y, from p3 = p(: x;) by rejection sampling. The ground-truth q can be computed by the
analytic expression of p(y x). To solve the optimization problem in (8), we initialize Çg O,, and
obtain Ç. and q' = cxp(( C. /T) by running gradient descent until the gradient norm S 10- Besides,
we estimate the true risk L = - -Ex,y [ [Tlogp(y
x)] by N ΣN T logp(y; x;) on N = 50, 000
sampled pairs and estimate 7 > 0 by
q' 14'1> to obtain q = 2. Then we plug q into (5) to calculate
our empirical risk Ć. It is worth noting that estimating the true risk L and the constant 2 is only for the plots in Figure 2 which is not necessary for real-world empirical risk minimization problems.
G.2 ADDITIONAL PLOT OF THE ToY EXPERIMENT IN SECTION 3.3
To further verify whether the non-diminishing error might be worse under long-tailed data distribu- tions, we added a new experiment Figure Appendix G.I of our revised manuscript. We still use the data spaces X, y, and the density function p(y x) as defined in the last paragraph in Pg. of our paper. Here we consider two values T 0.2 and 7 1.0, where T 0.2 results in a more long-tailed distribution of q compared to = 1.0. As demonstrated in Figure 6 the generalization error and the error term E(q. S) of GCL are worse (larger) when q is long-tailed. Moreover, our method effectively reduces the error term E(q. q: S) and the generalization error in both cases.
28

---

Published as a conference paper at ICLR 2025
Distribution (r- 1.0)
0.10
1.0
Error Term 8) (r= 1.0)
0.070
Truc
Pstimared
0.08
Ours
MLE
0.17
+ GCL
Densities
0.015
0.10
Gen.
0.010
0.06
0.04
6.005
0.02
6.000
200
200 Values
0.00
0
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Sample Size (n)
Sample Size (n)
Distribution (x= 2)
Gen. Err. (r= 0.2)
Error Term () (r- 0.2)
0.005
True Estimmtted
Ours MLE
0.12
GCL
Ours
Densitie
0.10
0,003
Geh
0.002
0.04
0.001
0.02
0.02
0.000
0.00
0.00
300
200
300
400
0
500
1000
1500
2000
2500
500
1000
1500
2000
2500
Values
Sample
(n)
Sample (6)
Figure 6: Left column: Distributions of the true q and our estimated q with 1.0 and = = 0.2, which are
estimated by KDE when n 100; Middle column: Comparing the generalization error (Ć S) - L] our method and GCL across various n. "MLE" refers to the MLE objective in (2) with the exact partition function; Right column: Comparing the error term E(q. q. S) of our method and GCL across various n.
G.3 MORE BIMODAL EXPERIMENTAL RESULTS
G.3.1 COMPARISON WITH ISOGCLR
In Section of the main paper, both our algorithm NUCLR and baselines (CLIP, CyCLIP, DCL, SogCLR) use shared temperature parameter for all data pairs. In contrast, the iSogCLR algo- rithm (Qu et al. 2023) learns an individual temperature parameter for each pair data. Here we compare the testing performance of our NUCLR algorithm that of iSogCLR. The results show that our NUCLR outperforms iSogCLR on most metrics except for the zero-shot classification on ImageNet when pre-trained on the CC12M dataset. Lastly, note that the individual temperature learned by the approach in iSogCLR could also be incorporated into our algorithm.
Table 2: Test performance of NUCLR and iSogCLR.
Dataset
Algorithm
MSCOCO
Flickr30k
CIFAR100
ImageNetlk
Mean
iSogCLR
28.50 0.21
51.56 0.38
35.57 = 0.99
40.18 + 0.28
38.95 0.30
CC3M
NUCLR
29.55 0.26
53.55
0.22
37.45 0.45
40.49 0.30
40.26 0.19
iSogCLR
34.09 =: 0.25
59.42 + 0.41
27.78 = 1.75
50.23 a 0.18
42,88 0.38 43.20 0.39
CC12M
NUCLR
34.36 0.13
60.45
0.03
28.16 = 1.35
49.82 # 0.23
G.3.2 EFFECT OF THE INITIAL VALUE Co
We also investigate the performance of NUCLR with two different initial values Ço of the auxiliary variable Ç: The natural choice So = and 2) The value So -0.05 according EqCo (Zhu al. 2020). As seen in Table 3 Co = -0.05 performs better on the CC3M dataset while Ço = 0 yields better results on the CC12M dataset.
worth noting that our NUCLR algorithm, with either initialization Co. leads to overall better performance than SogCLR.
G.3.3 IMAGES FROM CC3M DATASET WITH LARGE AND SMALL LEARNED POPULARITY
Figure and provide more images from CC3M with small and large learned popularity //
29

---

Published as a conference paper at ICLR 2025
Table 3: Test performance of NUCLR with different initial values of Co.
Dataset
Algoritiu
MSCOCO
Flickr30k
CIFAR100
ImageNetlk
SogCLR
28.54 = 0.25
$2.20 0.64
35.50 1.71
40.40 # 0.12
19.16 + 0.33
CC3M
NUCLR (Co
29.51 0.12
$ 0.35
1
40.00 0.26
NUCLR (Co -0.05)
29.55 0.26
53.55
0.22
37.45
0.45
40.49 0.30
40.26 0.19
SogCLR
33.91 0.26
59.28
0.07
26.10
0.88
49.82 # 0.14
42.28 + 0.27
CC12M
NUCLR (Co 0.0)
34.36
0.13
60.45
0.03
1
43.20 0.39
NUCLR (Co -0.05)
34.35 0.14
59.69
0.16
26.30 2.35
49.90 0.28
42.56 0.59
SALE
"Cutv pag
Cirrstmss siyn symbo!"
medat""
"Older coucorion mon woovingg brown loother slandlng pest to his mutorcycle out in the desent"
"Booguet of yelltwr rooes with a writable white card on old wordiv board!"
"Woman in front of refrgerator"
"Puupy sitting in buckict (oowrrs around bws, on while bas backgrourdd"
"Bustnersman office shoucing on megashocw:"
Figure Images (and their captions) from the CC3M dataset with large (high learned popularity).
Bratscc
TTweel on a hanger seamiess pattern."
"Vector illusrrtion of icons the web."
"Ladybug in decorative pottern, nature, seamless background."
"The abstract background created from simple wavy
"The white cross red strake."
shutterstrok
BIG
CK
2018
elophant, higgest wild onimal"
for the new year"
metal white background!
book in surnal nature landocope."
inons on the theme of ccology.
Figure 8: Images (and their captions) from the CC3M datasct with small q' (low learned popularity).
G.3.4 EVALUATIONS ON MORE DATASETS
We empirically compare our NUCLR and baselines on two more datasets for downstream zero-
shot classification other than the three used in Section 4 DTD (Cimpoi et al.) 2014) is texture recognition dataset that contains textural images in the wild from classes; Food-101 101 (Bossard al. 2014 is food recognition dataset containing 25, 250 food images from 101 categories.
30

---

Published as a conference paper at ICLR 2025
Table 4: A comparison of test performance two more datasets. The best results are highlighted in black.
CC3M
CC12M
Algorithm
DTD
Food-
Algorithm
DTD
Food- 101
CLIP
23.05 * 1.55
19.07 = 0.14
CLIP
27.73 1.86
43.54 = 1.07
DCL
24.11 + 1.68
18.46 + 0.50
DCL.
28.07 + 1.69
43.12 0.85
SigLIP
22.34
20.09
0.23
SigLIP
28.92 2.37
44.37
::
CyCLIP
24.59 1.49
19.25 0.85
CyCLIP
27.95 1.54
43,93
SogCLR
25.83 0.73
22.33 0.51
SogCLR
31.79 0.55
49.89
0.61
NUCLR (Ours)
27.73 0.94
22.22 0.31
NUCLR (Ours)
31991 0.54
51.04 0.15
Our algorithm demonstrates superior overall test performance these two datasets.
31


Reviews:
[{"review_id": "fDS2pMKkGD", "reviewer": "Reviewer_SkDm", "summary": "This paper explores discriminative probabilistic modeling in unimodal and multimodal self-supervised learning. By applying multiple importance sampling to Monte Carlo integration, it recovers the contrastive loss as a special case. The paper also identifies a generalization error limitation inherent in contrastive learning frameworks. To address this, it proposes a non-parametric method aimed at mitigating this error. The effectiveness of the approach is validated through experiments on multimodal datasets.", "questions": "please refer to the weakness part.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tIt seems a novel and interesting perspective to improve self-supervised contrastive learning with discriminative probabilistic modeling.\n2.\tIt provides theoretical insights into the generalization error limitation in self-supervised contrastive learning and presents a reasonable solution to address this problem.\n3.\tExperiments on CC3M and CC12M are conducted to verify the effectiveness of the proposed method.\n4.\tThe paper is generally well-structured and easy to follow.", "weaknesses": "-\tThis paper claims that the vanilla contrastive learning objective (e.g., GCL) results in non-diminishing error terms due to a misalignment between the uniform distribution and the true data distribution on y. However, it is unclear if these error terms are substantial and whether they might worsen under long-tailed data distributions. Would incorporating long-tailed contrastive learning methods [1,2], which use automatic or prior population distribution estimation, help address this issue?\n-\tThe paper lacks quantitative or qualitative results demonstrating that the proposed method effectively reduces the non-diminishing error terms (as seen in Eq. 6) on real-world datasets like CC3M and CC12M.\n-\tThe proposed method may introduce additional computational overhead. It would be beneficial to discuss and compare the computational cost relative to baseline methods. \n-\tAccording to Figure 4 in the ablation study, the proposed method appears to require specific design tricks for optimal performance, raising questions about its generalizability and applicability across varied scenarios. Clarifying whether substantial hyperparameter tuning is needed for different applications would be helpful.\n-\tThe theoretical framework suggests applicability to unimodal contrastive learning. The paper would be further strengthened by demonstrating its effectiveness on common SSL benchmarks for unimodal data. \n-\tThe empirical evaluations focus on classification and retrieval tasks across four datasets (MSCOCO, Flickr, CIFAR100, and ImageNet). Including more challenging datasets and a wider variety of tasks would enhance the robustness of the results.\n\n[1] The Hidden Uniform Cluster Prior in Self-Supervised Learning.\n[2] Combating Representation Learning Disparity with Geometric Harmonization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h3TJfX4QAw", "reviewer": "Reviewer_Ttd9", "summary": "The manuscript studies the discriminative probabilistic modeling problem on a continuous domain for (multimodal) self-supervised representation learning. To address the challenge of computing the integral in the partition function for each anchor data, the multiple importance sampling (MIS) technique is considered for robust Monte Carlo integration, which can recover InfoNCE-based contrastive loss as a special case. Typically, the generalization error analysis is conducted to reveal the limitation of current InfoNCE-based contrastive loss for self-supervised representation learning and derive insights for developing better approaches by reducing the error of Monte Carlo integration.\n\nIn order to resolve the problem, a novel non-parametric method is proposed for approximating the sum of conditional densities required by MIS through convex optimization, yielding a new contrastive objective for self-supervised representation learning. Moreover,  an efficient algorithm is designed for solving the proposed objective. The algorithm is compared with representative baselines on the contrastive image-language pretraining task. Experimental results on the CC3M and CC12M datasets demonstrate the superior overall performance of the proposed algorithm.", "questions": "Given the method is to handle discriminative probabilistic modeling problem on a continuous domain for (multimodal) self-supervised representation learning, the scope of the method that can be applied seems to be narrow. I am wondering if the method can be extended to other cases outside of self-supervised representation learning such as unsupervised learning.\n\nIt will be also useful to provide examples in the experimental results to show the method can be applied to image and text, audio and image with the connection to the proposed theory to show the advantages. So that the readers can deeply understand how to apply the theory to the real examples.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an interesting and important task of discriminative probabilistic modeling problem on a continuous domain for (multimodal) self-supervised representation learning. The idea appears to be novel in this field.\n\nThe theoretical analysis is thorough and with a good depth. The generalization error analysis is conducted to show the limitation of the existing algorithm. \n\nThe experimental evaluation and comparison are convincing and sufficient to show the advantages of the proposed algorithm. Overall, it is a solid paper.", "weaknesses": "The weakness of the paper includes:\n\n(1) As it is a theory heavy paper, it will be better to provide more motivation of the proposed method so that the readers can deeply understand why MIS is utilized and how is the convergence of MIS. In particulr, multiple importance sampling is a routine and well-known method. I believe that the uniqueness is probably the application of MIS in the particular framework. However, the author needs to specify and highlight what exact the uniqueness it is. (Is it a different math formulation etc)\n\n(2) It is necessary to highlight the complexity and running time of the proposed method. I suggest to add a subsection for discussion the complexity of the proposed algorithm and comparing the complexity and running time with competing methods.\n\n(3) The scope of the paper seems to be narrow (Can only be applied in  a continuous domain for (multimodal) self-supervised representation learning). For instance, can the proposed method be extend to unsupervised learning or semi-supervised learning ? Moreover, since it is multimodal based solution, can the proposed method be extended to text and image, image and audio etc ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pqnyLYCVsx", "reviewer": "Reviewer_38Nw", "summary": "The authors study the DPM problem on a continuous domain for (multimodal) self-supervised contrastive representation learning by leveraging the MIS method and proposing a novel nonparametric method for approximating the sum of conditional probability densities, establish a new contrastive loss for self-supervised representation learning and optimize it by an efficient algorithm called NUCLR. Experimental results on bimodal pretraining confirm the improvement in performance of their method compared to baseline approaches\non downstream tasks.", "questions": "Besides the above weaknesses, other questions are\n1. How to determine the involved sizes m and n and is there an optimal relation between them? \n2. Should the m and n be related to dimensions of x and y spaces? What relation is to the bootstrap?\n3. Formally, (1) can replace as p_v(x|y)!  When the dimensions of x and y are imbalanced, e.g., y's dimension is far greater than that of x, whether does paired sampling influence the quality of analysis?\n4. Assumption 2 requires the same d_L, I still want to know if the large difference of x's and y's dimensions impact their corresponding E1 and E2.\n5. (7) has some flavor of the attention mechanism to great extent, it is unclear whether this can be interpreted.\n6. Is the objective or loss measure (10) robust? e,g,, x_i or y_i is noisy!\n7. In Proposition ,can its (iii) condition satisfied? can the authors give some concrete cases?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. For the DMP problem on a continuous domain for (multimodal) self-supervised representation learning, the authors first point out a challenge in computing the integral in the partition function for each anchor data, then adopt the MIS method to realize robust Monte\nCarlo integration. Particular;y, the authors make generalization error analysis.\n2. For current limitation of current InfoNCE-based contrastive loss for self-supervised representation learning, the authors propose a new non-parametric method for approximating the sum of conditional probability densities required by MIS through convex optimization, as a result, yielding a new contrastive objective which is optimized by so-designed an efficient algorithm called NUCLR.\n3. So-conducted coparative results with baselines get improved performance.", "weaknesses": "In my opinion, the manuscript is basically complete, just some weaknesses are listed as follows:\n1. Lack an analysis of robustness of their results;\n2. Assumption 2 requires the same d_L, I want to know if the large difference of x's and y's dimensions impact their corresponding E1 and E2.\n3. In Proposition ,its (iii) condition seems difficult to be satisfied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)