Towards Efficient Contrastive PAC Learning
Authors: Jie Shen
Venue: Accepted by TMLR ()

Abstract: We study contrastive learning under the PAC learning framework. While a series of recent works have shown statistical results for learning under contrastive loss, based either on the VC-dimension or Rademacher complexity, their algorithms are inherently inefficient or not implying PAC guarantees. In this paper, we consider contrastive learning of the fundamental concept of linear representations. Surprisingly, even under such basic setting, the existence of efficient PAC learners is largely open. We first show that the problem of contrastive PAC learning of linear representations is intractable to solve in general. We then show that it can be relaxed to a semi-definite program when the distance between contrastive samples is measured by the $\ell_2$-norm. We then establish generalization guarantees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions. To the best of our knowledge, this is the first efficient PAC learning algorithm for contrastive learning.

Published in Transactions on Machine Learning Research (06/2025)
Towards Efficient Contrastive PAC Learning
Jie Shen Deportment of Computer Science Stevens Institute of Technology
Beshen.sjju@gmaillcc
Reviewed on OpenReview: https: http::///ppereevieee net/ forum?? id= dBJo9hyKV
Abstract
We study contrastive learning under the PAC learning framework. While a series of recent works have shown statistical results for learning under contrastive loss, based either on the VC-dimension or Rademacher complexity, their algorithms are inherently inefficient or not implying PAC guarantees. In this paper, we consider contrastive learning of the fundamental concept of linear representations. Surprisingly, even under such basic setting, the existence of efficient PAC learners is largely open. We first show that the problem of contrastive PAC learning of linear representations is intractable to solve in general. We then show that it can be relaxed to a semi-definite program when the distance between contrastive samples is measured by the f--norm. We then establish generalization guaranlees based on Rademacher complexity, and connect it to PAC guarantees under certain contrastive large-margin conditions. To the bost of our knowlodge, this is the first efficient PAC learning algorithm for contrastive learning.
1 Introduction
Contrastive learning has been a successful learning paradigm modern machine learning Gutmann & Hyvärinen 2010 Logeswaran & Leo 2018). In general, is assumed that learner has access to an anchor example v, a positive example y, and a number of negative examples {21,..., 2k), and the goal of contrastive learning is to learn a represcntation function f on the examples such that y is closer to than all sss under ʃ.
Motivated by the empirical success of contrastive learning, there have been surge of recent interests that attempt to understand it from a thcoretical perspective, primarily throngh the lens of Rademacher complexity or that of VC-theory. For example, Arora et al. (2019) initiated the study of generalization ability of contrastive learning by analyzing the Rademacher complexity of a commonly used rastive loss, and showed that under certain structural assumptions on the data, minimizing the unsupervised contrastive loss leads to low classification error. There were few follow-up works in this line which aimed to understand
and improve the sample complexity; see e.g. Ash et al. 2022 Awasthi et al.
2022 Lei et al. 2023
Orthogonal to the Maadmaachrr-basee theory, a very recent work of Alon et al. problem under the classical probably approximately correct (PAC) learning framework (Valiant) 1984). Unlike prior works that assumed rich strutuere for the data distribution in order to estimate the classification error from contrastive loss, Alon et al. (2024) considered that there is an unknown distribution on the instances and labels, where labels are produced by an unknown distance function. Tight bounds on sample complexity were established for arbitrary distance functions, --distances, and tree metrics.
2024 proposed to study this
In this work, we follow the contrastive PAC learning framework of Alon et al. 22024) Let X' C Rd be the space of examples (i.e. image patches). An instance u is a tuple (I, 2) E 233 thus we denote by U := 2 The label, 6, of tuple (ε,9,2) ) either -1 or 1; here, we write B == {-1,1} as the label space. Let : (h 44 - B) be a hypothesis class. Suppose that there an unknown distribution on x B. We are mainly interested in the realizable setting in this paper, namely, there exists an h E H. such that for all (u,b) b) D, it holds almost surely that b = h² (u). Now for any hypothesis h E H, we can define its error
1

---

Published in Transactions on Machine Learning Research (06/2025)
rate as follows: (h) == (h(() * b) = Pru-De (h(u) * 1²(w)), where Dy denotes the marginal distribution of D on U. We are now in the position to define the contrastive PAC learning problem.
Definition 1 (Contrastive PAC learning). Let e, (0, 1) be target error rate and failure probability, respectively. An adversary EX h²) chooses a distribution Du on U and h" E H and fixes them throughout the learning process. Each time the learner requests a sample from the adversary, the adversary draws a sample u from Dv, labels it by b:= ht (u) and returns (u, b) to the learner. The goal of the learner is to find concept 4 + B, such that with probability at least 1 - 5 (over the random draws of samples and all internal randomness of the learning algorithm), it holds that e S e for all D, h-
One example of the hypothesis class is H. {h: : (I, y: 2) sign(1) both f()) and p are to be learned from samples. This is a contrastive PAC learning problem considered in |lln et al. (0224). : We note that since learning distance functions inherently challenging, the PAC guarantees of Alon et al. (2024) were established only for finite domains, i.e. |Xx is finite, and the learning algorithm is inherently ineficient. On the other side, |Aora et al. (2019) and many of its follow-up works such as Awasthi et al. (2022); ; Lei et al. (202)) considered a fixed and known distance function, e.g. p= 2, and aimed to learn the representation function f()) among a certain family. This makes the problem more tractable, though in general, it is still inefficient due to the non-convexity of the contrastive loss - only convergence to stationary points is known Yuan et al. 2022). In addition, the approaches in this line were not immodiately implying PAC guarantces.
(()) - f(2)11- [l(())) f(w)l)) where
In this paper, we investigate the contrastive PAC learning problem for fixed p 2 and we aim to develop computationally efficient algorithms with PAC guarantees. Our setup is thus interpolating Arora et al 2019 and Alon et al. (024)). Despite the relatively new setup, it is surprising that even efficient contrastive PAC learning for linear representation functions on R is largely open. Indeed, as to be shown later, this is already a non-trivial problem from the computational perspective.
From now on, we will focus on the very fundamental class of linear representation functions:
F= (sw : Wx, W E W).
(1.1)
In the above, W can be certain constraint set such as the Frobenius ball. We will discuss in more detail the choice of W and related results later. Denote
(w z) == I|Wx W=ll2 I[> - Wyl2.
(1.2)
Now we can spell out the hypothesis class to be learned:
H = {hw (x, y, 2) + sign (z, (x), W E W].
(1.3)
1.1
Main results
Our main results for contrastive PAC learning of (13) is as follows.
Theorem (Theorem 10 informal). Suppose that b- gw- (x, 2, 2 1 for all (x, (0. ~ D. There erists an algorillmm salisfying the following. By drawing poly(1 /e, , 1og 1/8) samples from D, with probabilily - 8, A outputs a hypothesis W such that (W)) < e. In addition, A runs in poly(1/e, 1/8) time.
We remark that the condition b (a, 2 1 is similar to the largo-margin condition for learning halfspaces. Such large-margin condition was broadly assumed to analyze performance of learning algorithms such Perceptron (Rosenblatt) 1958) and boosting (Schapire & Freund 2012). Our condition is adapted to the contrastive samples, and we will call it contrastive large-margin condition. The constant 1 therein can be readily replaced by a margin parameter > O, which will then lead to sample complexity proportional to 1/>2 by our analysis. This is standard in learning theory (Anthony & Bartlett. 1999.. However, to keep our results concise, we do not pursue it here.
Our sample complexity in Theorem omits dependence on other quantities such as the magnitude of samples and the size of the constraint set W. A complete description can be found in Theorem 10
2

---

Published in Transactions on Machine Learning Research (06/2025)
What really hope to highlight in the informal version is that developed polynomial-time algorithm that PAC learns fundamental concept class from contrastive samples, and this is the first efficient PAC learner in the literature.
1.2 Overview of our techniques
We first view the contrastive PAC learning problem as binary classification, as suggested in (13) We then apply standard learning principles such as empirical risk minimization with suitable loss function. turns out, however, that the quadratic form of gw makes the problem inherently intractable even under the hinge loss function. We thus make use of the property that quadratic functions can be lincarized by introducing new matrix variable, which turns the problem into semi-definite program (SDP) that be solved in polynomial time. In order to analyze the error rate, we establish generalization bounds via Rademacher complexity on the SDP. We then show that with the contrastive large-margin condition, the empirical risk goes to zero on the target concept W*. This implies that the error rate of a solution of the SDP can as small as e, Lastly, we apply eigenvalue decomposition on the SDP solution to obtain a linear representation, which completes the proof.
1.3 Roadmap
A concrete problem setup well a collection of useful notations are presented in Section In Section 3 elaborate on our algorithm and the theoretical guarantees. Section concludes this paper and proposes few open questions.
2 Preliminaries
The PAC learning framework was proposed by Valiant (1844.. Let U and B be the instance and label space, respectively. It assumed that there is an underlying distribution on x B such that all samples are drawn from D. Let be hypothesis class that maps U B. The error rate of h H is defined errp(h) == PT(u.))=D (h(u) + b). Under the realizable setting, there exists target hypothesis h" E H, such that with probability 1, b h² (u) for (u, b) ~ D.
In contrastive learning, an instance E l is often tuple of the form u = (x, U,)), where V, z are from X C Rdd For example, X' can be the space of image patches with size d, and consists of three image patches. More generally, u may contain a number of patches x, y, 21,..,,, where the 2/'s are often referred to as negative examples the literature and y is referred to as positive example. In our main results, we did not pursue such generalization to keep our algorithm and theory concise. However, is known that such extension is possible and we will illustrate it in Section 3
With 44 = 3 and B 1-1,1} in mind, sample (I, z) of contrastive learning should be interpreted as follows: if b = 1, it indicates that is closer to x than z is to; otherwise, is closer to x. More formally, there exists distance function p² X' x X + Rzo, such that It" y, =) = sign(p" (x, p² ()).)). We note that Alon et al. (2024) aimed to learn such general distance functions over a finite domain, while most prior works assumed certain parameterized form such as p²(x, v) || w - Wyll 2 as in this work. Once we confine ourselves to the specific distance function, we can think of the mapping Wr as a new representation æ. Thus, sometimes the problem of contrastive learning is also regarded as representation learning. Denote
(w(x,y, ||
W W2ll
|W Wyll2
(2.1)
Observe that h² h² y, z) (x,
As typical in machine learning, one may want to impose certain constraint on W in order to prevent overfitting. Of particular interest would be the Frobenius-norm ball Wr (W Rd ||W]], I| I re). the f--norm ball Wi = {W R xd ||W]|, S r for sparsity, or the nuclcar-norm ball W, (W E Rd'xd [[W]] s r.) for low-rankness. Different constraints will lead to different generalization bounds, which will be shown in Sention g
3

---

Published in Transactions on Machine Learning Research (06/2025)
For square matrix M, write tr(M) for its trace. The inner product of two matrices A and B with same size is defined as (A, B) == tr(AT B), where sometimes we simply write as A B. In addition to the matrix norms that are just mentioned, we may also use the spectral norm; it is denoted by ||
We will mainly be interested in the hinge loss as a surrogate function to the error rate. Denote
U(W = max (0, WWWWU) L(G:U) = max G
(2.2)
The W, G, and U will be matrices in this paper.
Let F be a class of real-valued functions on U x B and S = = be a sample set of U x B. The empirical Rademacher complexity of under F is defined as R(FoS) = E sup o. f(si), where a = (o1....; :......y,. On) is the Rademacher random vector.
3 Algorithms and Performance Guarantees
Let = {( Mc. 2z, b,))== be a set of samples independently drawn from D, where the tuple (æ,, Uk 2,) E u and b; B. Recall that we study the realizable PAC learning. Thus there exists an unknown W E such that for all yz,y,z, z, D, gw (I, y, 2).
At first glance, one may seek hypothesis W H. that minimizes the empirical risk. That is,
min Σ [b; gw (2 34, 23) < 0), WEW 72
(3.1)
where 1[E] is the indicator function which outputs 1 if the event E occurs and 0 otherwise.
Since gw( (-) is quadratic in W, it is easy to show by algebraic calculation that:
Lemma 3. |[Wx Wyll = (WT W, (x () T>
Therefore, let
U bi ((3r 21)(1: - 2;) (x; (i) vt) T.
(3.2)
We can obtain
by Ww 24) (WT,U3) U.).
Plugging the above into 3. gives
min WEW
Σ [( (WTWW, W,U < <]-
(3.3)
Unfortunately, solving the above program is intractable, due to the 1) non-convexity of the 0/1-loss, and 2) the quadratic formula with respect to W. In the following, we propose approachos based on semi-definite programming, that solvable in polynomial time.
First, by standard technique, we could alternatively minimize the hinge loss:
min Σ L(WUU)) WeW 1=1
(3.4)
where L(:--) was defined in (2.2 We note that Verma & Branson 2015) also studied the above loss function in the context of Mahalanobis distance metrics, and they obtained statistical sample complexity. Observe that the problem may still be non-convex, since U; may have negative eigenvalues this is in stark rast. to learning from standard examples. Since the non-convexity comes from the quadratic term W WTW: W, we consider replacing the variable WTW W with a new variable G. Henco, (G, U,) is a lincar function with respect to G, turning the objective function into convex. This is a well-known technique that has been used in many contexts (Williamson & Shmoys 2011 d' d'Aspremont et al. 2007
4

---

Published in Transactions on Machine Learning Research (06/2025)
Suppose that based the fact W E W, obtain constraint set & D (WTWe W: W W). As far as is constructed convex, the overall program becomes convex. Note that such convex set 9 always exists, and the minimal is called convex hull (Boyd & Vandenberghe 2004). The empirical risk minimization program that we are going to analyze is given as follows:
min Σ L(G.U))
(3.5)
GEg n
where ((:+)) defined in 2.2
3.1
Rademacher complexity
We provide bounds on the Rademacher complexity of 3.5 for two popular choices of W (and thus ().
3.1.1
Frobenius-norm ball
We first consider the Frobenius-norm ball, one of the most widely used constraints in machine learning. That is, W WF := {W IRd xd ||W]] I (rr for some parameter ry > 0. Here and after, the subscript of W and is used only identify the type of constraints. Since G = W W, by singular value decomposition, it is not hard to show that ||G||, s r where II-1l, denotes the nuclear norm (also known the trace norm).
Therefore, we can choose
9- := (G Rddd G 0, |||| r
(3.6)
Lemma Consider the function class O == (0 U L(G;U), 9.). Let (U.) and assume maxu;es |U,]| a. Then the empirical Rademacher complerity
R(O. o 8) S r3 a logd
n
Proof. Let = (o1....; be the Rademacher random variable. By the contraction property of Rademacher complexity, we have
n R(O, o oS)= =E sup GEB.
or max G U.}
i=1
< Eg sup
o,G U;
GEG. i=1
rF
max U,ES
|Ui||
log d
where the last inequality follows from Kakade et al. (2012) (see Table therein). The result follows by noting that the spectral norm of U; is assumed to be upper bounded by
Recall that U, was defined in 33. Suppose that the example space X is subset of bounded fg-norm ball, say X' C (x | S k). Then can show that.
| <
||l, vill2 + || - 22122 < 2n...
Thus setting 2x. in Lemma gives the following:
Corollary 5. Consider the function class θ == {0 U i(G;U),G Suppose X fa: ||0||| S s} and let = {U:}__ be draw of sample set from x Then
log d n
R(O. o5) 2r x2
5

---

Published in Transactions on Machine Learning Research (06/2025)
3.1.2 f-omr ball (sparsity)
Now we consider that the linear representation matrix W is constrained by an fororm which typically promotes spansity palierns [Tibshirani 1996 Chen et al., 1998 Candés & Tao 2005). That is, Wp == {W E gd'xd, xd |[W], S ri} for some parameter r1 Now derive the formr for W W. To do so, let write W in column form: W = (W1,..., Wa) where wy denotes the i-th column of W. It follows that
Σ Isi
wyy - wy
Σ
||wa|li
||m
bo
Isijsd
Σ
|wy|
|
ISjsd
Isidd
S
Σ
|wy||
'71 .r.
15j5d
This suggests that we could choose
9- = {G E Raxd G 0, |G]| Sr...
(3.7)
Lemma 6. Consider the function class O == (0 : U + (GG Let S = {U:)_ and assume
maxu,es |Usllo S a. Then the empirical Rademacher complerity
44 log((2))
R(O1 0) a
Proof. For matrix M, let M be the vector obtained by concatenating all columns of M. Let a (oI...., σx) be the Rademacher random variable. By the contraction property of Rademacher complexity, we have
n R(O, o S) Eg sup GEG
o, max (0,1 G. U.}
< Egg sup GE i=1
o,G.ui U
o.G.U. UÜ. < rî 222log
Ex sup GEM i=1
where the last inequality follows from Lemma 26.11 of Shalev-Shwartz Ben- David (014)) Dividing both sides by n completes the proof.
Suppose that X c fx ||olloc S n). Then we can show that
| S || 11. + ||x; 2ill33 s 2x
Therefore, specifying a 2x in the above lemma gives the following corollary.
Corollary 7. Consider the function class O₁ := {0 U + G(G Suppose X C fx: ||x|| S k] and let = {U,) be a draw of sample set from X Then
4 log (2d)
R(O, o oS) 2n x2
n

---

Published in Transactions on Machine Learning Research (06/2025)
3.2 PAC guarantees
We analyse the PAC guarantees under new type of margin condition, which we call the contrastive large-margin condition.
Definition 8 (Contrastive large-margin condition). We say that the data distribution D satisfies the contrastive large-margin condition if there exists W E W, such that for all (z, 2, ~ D, the following holds with probability 1: b(Il">> -=
I W' v112) 2.
Geometrically, this condition ensures that there is non-trivial separation between positive examples and negative examples for any given anchor æ. It follows that when the condition is satisfied, (3.4) attains an optimal objective value of O. Since the feasible set of convex program (3.5 contains that of (3.4). is easy to get the following.
Lemma 9. Assume that the contrastive large-maryin condition holds. Then there exists G E G, such that the objective value of (3.5) at G equals O.
Now we can prove the main result of this section, the PAC guarantees.
Theorem 10. Assume that the contrastive large-margin condition satisfied for some W* W, and G is such that 3 (WTW W: W W}. Let G G be an optimal solution to (3.5) and let G = VVV be its eigenvalue decomposition. Let W = E1/2VT Then by drawing contrastive sample set S {(I1, Vi, 2i, b:)) with probability at least 1 - 6, it holds that
log(8/8) n
errD(W) s 2R(O + 5
where c: supoeg. L(G:U) When G is convex set, our algorithm runs in polynomial time.
Proof. Let == = 10:0- [G: 9}. Let e ueuxe [(G.U)]
We apply standard uniform concentration via Rademacher complexity that with probability 8,
(Bartlett & Mendelson 2002 to obtain
log(8/6)
S) + 5cy BUNDi(G;U) UU) 2R(0 S
In view of the contrastive large-margin condition, we have L(W*;U) 0. On the other hand, we always have L(G:U) 2 1 U <].
This implies
2 log(8/0)
E EunDI(G. <0 2R(0 e S) + /
(3.8)
n
Now recall that U = b((( (x 2) - (x - y)(x y) as in
3.2 and & WTW by the eigenvalue
dccomposition. Thercfore,
G.U (Iivs- Wall
|| wyl3
Thus, 3.8 is equivalent to
2lgg(8/8 (8/5)
erID(w) < (R( o S)+ 5cg
(3.9)
The proof is complete.
Theorem 10 allusion to the Rademacher complexity bounds in Section 3.1 lead the sample complexity bounds for efficient contrastive PAC learning.

---

Published in Transactions on Machine Learning Research (06/2025)
Corollary 11. Assume same conditions in Theorem 10 Consider θ Oa in Corollary 5 Suppose
X' C fo ||ا|| I ni.. Then by drawing n = (5+5r log sd contrastive samples from D, we have 8
eII S with probability 1 1- where W is defined in Theorem 10
Proof. We just need to compute the supremum of L(G.U)). It turns out that L(G.U) S 1
++ +||||,, || r The result follows by plugging this upper bound and the Rademacher complexity
in Corollary into Theorem 10
Corollary 12. Assume same conditions as in Theorem 10
Consider θ = θ1 in Corollary 7 Suppose
X C {x | I =n). Then by drawing n. = 5 log 8d 8 (TD(WW) S with probability 1 8, where W is defined in Theorem
contrastive samples from D, we have
10
Proof. Again, only need to compute the supremum of of [(G It turns out that L(G:U) s L+|G. UI + ++|| || 11+r3 The result follows by plugging this upper bound and the Rademacher complexity
in Corollary into Theorem
10
We remark that both O, and O₁ are convex sets, thus our PAC guarantees obtained from computationally efficient algorithm, i.c. the convex program 3.5
3.3 Extension to multiple negative examples
One important extension of our contrastive PAC learning framework is to consider multiple negative samples, which are commonly used in practice and its importance has been broadly studied (Ash et al. 2022 Awasthi lt al. 2022 Lei et al. 2023). That is, suppose the label b = 1, in addition to the anchor example x and a positive example y; a learner collects & negative examples 21....; Ak. Together, these serve as a sample x while the label space remains same as before. The learning paradigm still follows from Definition D More generally, one can think of an instance as (I, u1...., Mk+1) and label b E f1...., & + 1} that specifies the index among all u;'s that is closest æ. Since we can always reorder the examples wI....: uk+1 such that the closest example is arranged at the first place, without loss of generality, we will always assume b = 1 and the example following is closest, which we denote as y, and the remaining examples are denoted by ,1,..., in the literature.
u := (x, y, 21.....: Zk: 1). Therefore, the instance space
Zk- This is also notation typically seen
Now given a set of contrastive samples S = { Vis 2a..... Zak, b where the samples are independently drawn from D, we aim establish PAC guarantees the case k = 1. For any i, we know by the realizability assumption that |[**; W
"ill2 2 - | x; W* 24s llz for all 1 < j < k. Define
U. = (x: - 21r)(;; 211) (a; y1 (x TT
(3.10)
By Lemma have ((W") (W*)"W",U W*)U)) 0 for all 1 minigiss ((W W U,i) 2 0. Thus, natural empirical risk, based on hinge loss, is as follows:
S k. This is equivalent to
min
Σ
max
min (W WWW,CUM U.)) 1555k
(3.11)
WEW
As discussed in the preceding subsection, the above program is non-convex, and we will consider SDP as convex relaxation. This gives the following program:
min - GEg
max (0, 0, min (G)) 15jsk
(3.12)
1=1
Consider the function class Q {gG : (z. y, 21,..., + max minisjss G K.U,),.G. G E 9), where
U.J (x 21)(x 2,) (ar (x y) Let == (a..ee (et. #1, 24] and denote
8

---

Published in Transactions on Machine Learning Research (06/2025)
G global optimum of 33.12 Write (z, Vr 21 21...... .2).. Then standard concentration results tell that (u-D S Bu-DUG- (u) + 2R S) + 5ey
2 2log(8/6)
where G = W"* Under the contrastive large-margin condition, we have qo- (u) = 0. Thus, it remains to bound the empirical Rademacher complexity R(Q S). S). To this end, we think of the function qG E Q a composition of two functions: 4G q c qG, where (c(u)) (G U.....,. U.+) E I and q(V,,..., ux) max mimisisauy By Corollary of Maurer 2016), have
k og UUg,
n. R(Q e) 9) & VLL., sup GEg (=1
ΣΣ
(3.13)
where L denotes the Lipschitz constant of ğ.
When G = G- and X C fz || S k), we have shown that the expectation on right-hand side is less than v d n.... Therefore, it remains to estimate L. Observe that q can further be thought of as @(t) = max (0, 1-11-1 t and = minigss Vy. The Lipschitz constant of with respect to Ug. is upper bounded by 1. Thus, 1.
Putting together gives
k logd
log(88/)
Ev Euw S 22V223"" V
+ 5oy
(3.14)
when G G.. We note that 1 13 by algebraic calculation.
Lastly, similar to the proof of Theorem the above implies PAC guarantee of W with & WWTW.
4 Conclusion and Open Questions
In this paper, we studied the power convex relaxations for contrastive PAC learning. We showed that even for lcarning linear representations via contrastive learning, the problem is generally intractable, which is in stark contrast to the classic problem of PAC learning linear models. We then proposed convex program based techniques from semi-dcfinite programming. Under contrastive large-margin condition, we proved that the solution to the convex program enjoys PAC guarantees.
This is the first work that establishes PAC guarantees for contrastive learning for arbitrary domain, while the very recent work is confined to finite domains (and considers a more involved learning scenario). Our convex relaxation techniques seem suitable for the fz-distance between contrastive samples. An important question is whether there exists more general approach dealing with other distance metrics such as the fıddistance. We expect that this is possible, since f--ormm is closely related a family of linear functions by introducing additional variables. Another important question is whether it is possible to learn nonlinear representation functions, for example, the family of polynomial threshold functions neural networks. We conjecture that learning neural networks from contrastive samples is rather challenging, since the optimization landscape for linear classes is already drastically changed with contrastive samples. On the algorithmic design front, it appears that one needs to carefully design convex surrogate functions whenever the underlying representation functions are modified. Does there exist a principled approach that guides the design, and it necessary consider convex surrogate functions for the problem? In the literature of PAC learning halfspaces, there have been rich set of algorithmic results showing that one may optimize certain non-convex loss functions whose stationary point really enjoys PAC guarantees (Diakonikolas et al. 2020 Zhang et al.) 2020 Shen 202 2025). Can we show similar results for contrastive PAC Icarning? In particular, can we design non-convex loss functions that may serve as a proxy to (3.1] and that a good stationary point can be efficiently found?
We believe that our work will serve as a first step towards these questions. Lastly, it is known that in practice, the contrastive examples and labels can both be noisy. it possible develop noise-tolerant algorithms for
contrastive PAC learning, by extending ideas from algorithmic robustness (Diakonikolas Kane 2019 Shen
& Zhang 2021 Shen 2021b 2023
9

---

Published in Transactions on Machine Learning Research (06/2025)
References
Noga Alon, Dmitrii Ardiukhin, Dor Elboim, Orr Fischer, and Grigory Yaroslavtsev. Optimal sample complexity of contrastive learning. In Proceedings of the 12th International Conference Learning Representations, 2024.
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoret- ical analysis of contrastive unsupervised representation learning. In Proceedings of the 36th International Conference on Machine Learning, pp. 5628-5637, 2019.
Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of negatives contrastive representation learning. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, pp. 7187 7209, 2022.
Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath. Do more negative samples necessarily hurt in contrastive learning? In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, pp. 1101-1116, 2022.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-488 2002.
Stephen P. Boyd and Lieven Vandenberghe. Conver optimization. Cambridge University Press, 2004.
Emmanuel J. Candès and Terence Tao. Decoding by linear programming. IEEE Transactions on Information Theory, (211):44203427 4215, 2005.
Scott Shaobing Chen, David L.. Donoho, and Michael A. Saunders. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 20(1):33 61, 1998.
Alexandre d' Aspremont, Laurent El Ghaoui, Michael I. Jordan, and Gert R. G. Lanckriet. A direct formulation for sparse PCA using semidefinite programming. SIAM Review, 49(3):434-445, 2007.
Ilias Diakonikolas and Daniel M. Kane. Recent advances in algorithmic high-dimensional robust statisties. CoRR, Abs/1911 1.0911,, 2019.
Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. Learning halfspaces with Massart noise under structured distributions. In Proceedings of the 33rd Annual Conference on Learning Theory, pp. 1486 1486-1513, 2020.
Michael Gutmann and Aapo Hyvärinen. coita-con estimation: A new estimation principle for unnormalized statistical models. In Proceedings the 13th International Conference on Artificial Intelligence and Statistics, pp. 297 304, 2010.
Sham M. Kakade, Shai Shalev-Shwartz, and Ambuj Tewari. Regularization techniques for learning with matrices. Journal of Machine Learning Research, 13:1865-1890, 2012.
Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou. Generalization analysis for contrastive representation learning. In Proceedings of the 40th International Conference Machine Learning, pp- 19200 19227, 2023.
Lajanugen Logeswaran and Honglak Lee. An efficient framework for learning sentence representations. In Proceedings of the 6th International Conference on Learning Representations, 2018
Andreas Maurer. A cector-contraction inequality for rademacher complexities. In Proceedings of the 27th International Conference on Algorithmic Learning Theory, pp. 3 3-17, 2016.
10

---

Published in Transactions on Machine Learning Research (06/2025)
Frank Rosenblatt. The Perceptron: A probabilistic model for information storage and organization in the brain. Psychological review, 65(6):386-40) 1958.
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. The MIT Press, 05 2012.
Shai Shalev-Shwartz and Shai Ben-David. Underslanding Machine Learning: From Theory to Algorithms.
Cambridge University Press, 2014.
Jie Shen. On the power of localized Perceptron for label-optimal learning of halfspaces with adversarial noise.
In Proceedings of the 38th International Conference on Machine Learning, pp. 9503-9514, 2021a.
Jie Shen. Sample-optimal PAC learning of halfspaces with malicious noise. In Proceedings of the 38th
International Conference on Machine Learning, pp. 9515 9524, 2021b.
Jie Shen. PAC learning of halfspaces with malicious noise in nearly linear time. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 30 46, 2023.
Jie Shen. Efficient PAC learning of halfspaces with constant malicious noise rate. In Proceedings of the 36th International Conference on Algorithmic Learning Theory, 1108-1137, 2025.
Jie Shen and Chicheng Zhang. Autribute-efficient learning of halfspaces with malicious noise: Near-optimal label complexity and noise tolerance. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, pp. 1072-1113, 2021.
Robert Tibshirani. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Sociely: Series B (Methadological), 58(1):267 288, 1996.
Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134 1142, 1984.
Nakul Verma and Kristin Branson. Sample complexity of learning mahalanobis distance metrics. In Proceedings of the 29th Conference Neural Information Processing Systems, 2015.
David Williamson and David B. Shmoys. The design of approrimation algorithms. Cambridge University Press, 2011.
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. Proceedings of the 39th International Conference on Machine Learning, pp. 25760 25782, 2022.
Chicheng Zhang, Jie Shen, and Pranjal Awasthi. Elficient active learning of sparse halfspaces with arbitrary bounded noise. In Proceedings of the 34th Annual Conference on Neural Information Processing Systems, pp. 7184-7197, 2020.
11


Reviews:
[{"review_id": "bw9VuezBNf", "reviewer": "Reviewer_pE9y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper develops PAC guarantees for the case with linear function class, fixed p=2, which is new in the literature. \n\nWeaknesses:\n\nThis paper focuses on the linear function class and assumes realizability. Then the results were established using Rademacher complexity. However, it is commonly known that the approach of  Rademacher complexity is difficult to generalize to large neural networks, which are the ones used in practice. Therefore, a question here is whether the developed methodology can be combined with recent advancements of deep learning theory, e.g., those used in analyzing large-scale neural networks, to obtain guarantees for contrasive learning problems in this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the PAC guarantee for contrastive learning under the setting with a fixed $\\ell_2$ distance with a linear function class and realizability assumption. It is shown that a complexity of polynomial of 1/\\epsion and log 1/\\delta is need to guarantee an error less than \\epsilon with high probability. This paper is more general than Alon 2024 in that it studies a potentially infinite subspace of the real space, while Alon 2024 focus on finiite \\mathcal X; and the approach in Arora 2019 does not apply to obtain the PAC guarantees. On the other hand, this pape focuses on $p=2$ which is less general than the one in Alon 2024.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discuss the extension to large-scale neural networks.\n2. Discuss other relaxations to the non-convex problem than the one used in 3.12, and whether they can imply similar generalization results.", "broader_impact_concerns": "None are noted.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vY2nTSjklQ", "reviewer": "Reviewer_Snpm", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As far as I can tell, the theoretical contributions - the algorithm based on convex optimization and sample complexity based on Rademacher complexity - look solid. My main concerns are regarding novelty. I think the authors missed the following papers:\n* Regarding sample complexity: [\"Sample Complexity of Learning Mahalanobis Distance Metrics\" by Verma & Branson](https://www.cs.columbia.edu/~verma/papers/mlearn_nips15.pdf). The paper introduces a similar model (including assumptions on bounded inputs and bounded Frobenius norm of the matrix). Admittedly, they only prove sample complexity for paired comparisons, and then say \"the results are easily extended to triplet comparisons.\" However, their techniques and results look similar.\n* Regarding the algorithm: [\"Sparse Compositional Metric Learning\" by Shi, Bellet, Sha](https://researchers.lille.inria.fr/abellet/papers/aaai14.pdf) (also implemented as a [library](https://contrib.scikit-learn.org/metric-learn/weakly_supervised.html#learning-on-triplets)). Their optimization problem is different, but, as they claim, it's also convex, and it's clearly an ERM. While they don't explicitly consider constraints on the learnable matrix, this can be handled by projected gradient descent.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers learning of a Mahalanobis distance function in contrastive learning. The paper introduces the algorithm for efficient learning of the distance, as well as sample complexity for this problem.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In light of the works above, please clarify the novelty of your paper.", "broader_impact_concerns": "No ethical concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8gHdQBGqj1", "reviewer": "Reviewer_yznr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is technically sound, and it solves a problem that is -- surprisingly enough -- still open. The writing could be improved. My requested changes are limited, as this is not my primary area of expertise.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The author studies contrastive learning of the fundamental concept of linear representations under the PAC learning framework. They are the first one to derive an efficient PAC learning algorithm for contrastive learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "How is $\\text{EX}(D,h^*)$ defined in Definition 1? Is it a function? If so, does it map from the space $\\mathcal{P} \\times \\mathcal{H}$ of probabilities over $\\mathcal{X}$ times the space of models, to the space $\\mathcal{U} \\times \\mathcal{B}$?\n\nThere's a typo in eq 1.3, it should be closed curly bracket.\n\nAre $r_F$, $r_1$, and $r_*$ at the bottom of page 3 used to simply distinguish between different radiuses of the considered balls, or do they have another meaning? The first one seems to be the correct answer, but this is only explained later in sections 3.1.1 and 3.1.2.\n\nThere's an extra \"Then\" at the beginning of Lemma 9. More in general, the writing of the paper could be slightly improved.\n\nSome Corollaries are not explicitly proven. While it is easy to see that they are true, I'd suggest to include the proofs in the final version.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)