Generalization Bounds with Logarithmic Negative-Sample Dependence for Adversarial Contrastive Learning
Authors: Naghmeh Ghanooni
Waleed Mustafa
Yunwen Lei
Anthony Widjaja Lin
Marius Kloft
Venue: Accepted by TMLR ()

Abstract: Contrastive learning has emerged as a powerful unsupervised learning technique for extracting meaningful representations from unlabeled data by pulling similar data points closer in the representation space and pushing dissimilar ones apart. However, its vulnerability to adversarial attacks remains a critical challenge. To address this, adversarial contrastive learning — incorporating adversarial training into contrastive loss — has emerged as a promising approach to achieving robust representations that can withstand various adversarial attacks. While empirical evidence highlights its effectiveness, a comprehensive theoretical framework has been lacking. In this paper, we fill this gap by introducing generalization bounds for adversarial contrastive learning, offering key theoretical insights. Leveraging the Lipschitz continuity of loss functions, we derive generalization bounds that scale logarithmically with the number of negative samples, 
$K$, and apply to both linear and non-linear representations, including those obtained from deep neural networks (DNNs). Our theoretical results are supported by experiments on real-world datasets.

Published in Transactions on Machine Learning Research (11/2024)
Generalization Bounds with Logarithmic Negative-Sample Dependence for Adversarial Contrastive Learning
Naghmeh Ghanooni
ghanooni@cs.umi-4 www.iiiwww....ii..iioo..
Deportment of Computer Science RPTU, Kaiserslautern, Germany
Walced Mustafa
mustafa dastaffaecss.oo uni-kl.
Department of Computer Science RPTU, Kaiserslautern, Germany
Yunwen Lei
leigw@kku.hh
Department of Mathematics University of Hong Kong, Hong Kong, China
Anthony Widjaja Lin
Kin@cc.cmm uni-kl.
MPI-SWS
RPTU, Kaiserslaulern, Germany
Marius Kloft
kloft und-kl.de
Department of Computer Science RPTU, Kaiserslautern, Germany
Reviewed OpenReview: Sttps://openrevieee net/ forum? id= id=0aVityidEe
Abstract
Contrastive learning has emerged as a powerful unsupervised learning technique for extracting meaningful representations from unlabeled data by pulling similar data points closer in the represontation space and pushing dissimilar ones apart. However, its vulncrability to adver- sarial atlacks remains a critical challenge. To address this, adversarial costrastive learning - -incorporating adversarial training into contrastive loss has emerged as promising approach to achieving robust representations that can withstand various adversarial attacks. While empirical evidence highlights its effectiveness, a comprehensive theoretical framework has been lacking. In this paper, fill this gap by introducing generalization bounds for adversarial contrastive learning, offering key theoretical insights. Leveraging the Lipschitz continuity of loss functions, we derive gencralization bounds that scale logarithmically with the number of negative samples, K, and apply both linear and non-linear represent including those obtained from deep neural networks (DNNs). Our theoretical results are supported by experiments on real-world datasets.
1 Introduction
Learning meaningful representations from unlabeled data plays crucial role in enhancing the performance of machine learning models. Representation learning has shown great success in fields such as computer vision (Chen et al. 2020b He ct al.] 2020: Caron et al. 2020) and natural language processing (Brown et al.] 2020 Gao et al. 2021 Radford et al. 2021). Among various representation learning techniques, self-supervised contrastive learning (CL), popularized by the SimCLR framework (Chen et al.] 2020b), stands out. The core idca behind contrastive learning
bring similar pairs (x, (. closer together the embedding space while pushing apart negative samples from x, (denoted as (x, .... ,²x)). These learned representations then be leveraged for downstream tasks, such classification task, whether

---

Published in Transactions on Machine Learning Research (11/2024)
supervised unsupervised (Chen et al. 2020b He et al. 2020 Khosla et al. 2020 Notably, extensive
research in contrastive learning has revealed that a sufficient number of negative samples is essential for
achieving high-quality representations (Chen et al. 2020b; Khosla et al. 2020 Henafi 2020).
2020
Tian et al.
Despite significant progress in representation learning, these representations remain susceptible to advessaiial examples (Szegody et al. 2013 Biggio et al.) 2013), which are subtly perturbed samples carefully crafted to manipulate a model's predictions. Specifically, adversarial attacks aim to maximize the model's loss by slightly perturbing imput samples. To mitigate this vulnerability, researchers have proposed adversarial training (Chen et al. 2020a; Tramer & Bonch, 2019). This technique employs a min-max optimization approach, where the model simultaneously minimizes its loss while facing maximally perturbed examples. By doing so, adversarial training enhances the robustness of the learned represenlations against, adversarial attacks. Adversarial contrastive learning (ACL) emerges from applying adversarial training to contrastive learning. In this paradigm, adversarial training enhances the robustness of representations Icarned from unlabeled data during unsupervised training. Empirical evidence supports the effectiveness of ACL in improving the quality of these robust representations (Kim et al. 2020 Ho & Nvasconcelos 2020: Jiang et al. 2020). Despite its empirical success, the theoretical foundations of ACL remain somewhat limited.
Recent work by Zou & Liu (023) leverages Rademacher complexity to show the connection between unsupervised contrastive learning and the downstream classification task and claimed that the average adversarial risk of downstream tasks can be upper bounded by the adversarial unsupervised risk of the upstream task. Specifically, they derive a surrogate upper bound for the adversarial risk by analyzing the average supervised risk. In the case of a single negative sample, they bound the adversarial supervised risk using the surrogate unsupervised risk. For multiple negative samples, they introduce average adversarial supervised risk, which is similarly bounded by the surrogate unsupervised risk. This results in bound that scales as O(K, where K represents the number of negative samples, leading to a linear dependence on K. However, their approach does not fully exploit the coupling between negative samples, resulting in suboptimal bounds. As a result, their approach is not well-suited for scenarios involving a large number of negative samples, which is essential for achieving optimal generalization performance (Chen el al., 2020b Tian el al., 2020; Henafi 2020 Khosla et al. 2020). In contrast, our work extends this analysis to the general case with large number of negative samples, aiming to improve the dependency the sample size and provide more effective bounds.
In this paper, we present the following contributions:
We apply the Lipschiii property of loss functions to derive generalization error bounds for ACL. These bounds incorporate the covering number of feature classes and show improved dependency the number of negative examples, resulting in tighter bounds compared to existing literature by ZZo
& Liu 20023)
Our general results are applied to two specific scenarios of unsupervised representation learning: learning linear features and learning non-linear features via DNNs. In both cases, the bounds show logarithmic dependence on the number of negative samples.
The remainder of the paper is organized as follows: Section reviews related work and state-of-the-art approaches. In Section generalization error bound for ACT, is presented in Section 4 Section 5 applies this result to both linear and nonlinear feature representations, demonstrating the corresponding generalization bounds. Empirical evaluations are provided in Section 0 All proofs for the lemmas and thcorems can be found in Section 7 and the appendix. Finally, Section g concludes the paper.
define the problem and set up framework. Our main theorem the
2 Related work
Contrastive Learning Our work is primarily related to the theoretical analysis of contrastive learning by Arora et al. (2019) and Lei et al. (2023). Arora et al.] (2019) provided generalization bounds for contrastive learning by analyzing the Rademacher complexity of the representation function class and examining the performance of linear classifiers trained on the learned representations. They showed that the classification
2

---

Published in Transactions on Machine Learning Research (11/2024)
error of a mean classifier is bounded by the unsupervised errors of learned representation functions, indicating that downstream tasks such as classification tasks benefit from representation ions with low unsupervised errors. However, their generalization bounds scale linearly with K, the mumber of negative samples, which becomes impractical when K is large, as is often the case in CL. Motivated by this, Lei et al. (2023) improved the dependence on the number of negative samples. For l Lipschitz loss, their bound is independent of K, and for for Lipschitz loss, they achieved reduction by a factor of K. Ji et al. (2023) introduced a theoretical framework for contrastive learning under the linear representation setting, providing a detailed analysis of the feature learning performance in the spiked covariance model. Their work theoretically justified why contrastive learning can remove more noise compared to autoencoders and GANs by constructing contrastive samples via augmentations. In a PAC-Bayesian setting, Nozawa et al. (2200) derived PAC-Bayesian generalization bounds on the posterior distribution of representation functions. Another key challenge in CL is the random selection of negative samples, which can result in some negatives sharing the same label as the anchor point. This introduces bias into the CL loss function and can potentially reduce performance in practico. [Chann et al. 2020) addressed this by deriving an approximation for the unbiased contrastive loss and establishing generalization bounds for downstream tasks.
Adversarial Robustness Since Szegedy et al. 2013 first revealed the vulnerability of neural networks to small input perturbations (Jiang et al. 2020 Kim et al. 2020 numerous studies have focused on establishing generalization bounds for adversarial learning, primarily in the supervised setting. Montasser et al. (2019)
explored the PAC lcarnability of adversarial robust learning, and Xu & Liu 2022) extended these findings to the multi-class classification problem. Additionally, several works have used Rademacher complexity to analyze adversarial learning under f--norm additive perturbation attacks (Yin et al., 2019: Awasthii et al., 2020:
Khim & Loh] 2018; Xiao et al.; 2022; Mustafa et al., 2022). Yin et al. (2019) derived Rademacher complexity- baased bounds for linear models and single-layer neural networks using surrogate loss, while Awasthi et al. (2020) introduced bound based on the direct loss for linear models and two-layer neural networks. Expanding on this approach, Mustafa et al. (2022) developed bounds for broader range of attacks, directly applied to the loss function, and showed that their results grow at rate of Ollog C)2, where C is the number of label classes. In contrast, Khim & Loh (2018) proposed a tree-transform method to propagate adversarial noise through the network, leading to bound that scales exponentially with the number of classes, OCC).
Adversarial Contrastive Learning Recent studies have increasingly applied adversarial training to contrastive learning loss to improve model robustness (Kim et al. 2020 Ho & Nvasconcelos 2020 Jiang
et al. 2020 However, the theoretical foundations of ACL. remain underexplored. Zou & Liu (2023) leveraged Rademacher complexity to show that the average adversarial risk in downstream tasks can be bounded by the adversarial unsupervised risk of the upstream lask. Specifically, they derived a surrogate upper bound for the adversarial risk by analyzing the average supervised risk. For the case of a single negative sample, they provided bounds on the adversarial supervised risk using the surrogate unsupervised risk and extended their approach to multiple negative samples by introducing an average adversarial supervised risk, also bounded by the unsupervised risk. However, their bound scales linearly as O(K) with the number of negative samples K. A concurrent work studied ad adversarial contrastive learning by using structural result on infinity-norm covering numbers (Wen et )
3 Problem Formulation
3.1 Contrastive Representation Learning
In the contrastive learning setting, we aim to learn representations by contrasting similar and dissimilar data points. Let X' be an input space (c.g., a set of input images). Given an anchor sample x, we use a positive sample xt, which is drawn from a distribution of similar data Dam, and multiple negative samples x2 , ,kx which are drawn from a negative distribution Dueg. The goal is to learn a representation where the anchor and positive pair are pulled closer together, while the anchor and negative samples are pushed apart in the feature space. In this setup, a single positive sample paired with multiple negative samples, creating an inherent asymmetry that is standard in both theoretical (Arora et al. 2019
Tei et al.
3

---

Published in Transactions on Machine Learning Research (11/2024)
2023 and empirical contrastive learning (Chen et al. 2020b; Khosla et al. 2020 This approach simplifies implementation and analysis while reducing computational complexity. Adding more positive samples does not always yield proportional performance improvements and can increase the risk of overfitting by reducing contrast between similar and dissimilar examples. Conversely, multiple nogative samples are essential for enhancing feature representations, as they offer diverse examples for the model to distinguish from the positive pair. We follow the framework of Arora et al. (2019) to define the distribution of siim and Dneg- The distributions Pamm and Pegg are generally characterized through set of latent classes C and an associated probability distribution p over these classes. For each latent class E C, let De be the conditional distribution of the inputs given the latent class Daim and Dneg are defined as:
Daim (2, xx = Eoup (Dcx)DDc
Dueg = (DoppDD(<=T))
That is, Datm (2, ) measures the probability of drawing a and x+ from the same class c~ p, which means that and x are conditionally dependent, given e, while [x= mcasures the probability of drawing x that is independent of and x², coming from other latent classes. The objective of CL is select feature map f X + Rd from class of representation functions F {f [If(())]1 S R), for some R R> O, where || ||2 denotes the fi-norm, and d E N represents the dimensionality of the feature space. This is achieved using the training set
"ii. (TT)): S [<11,1 "I" ""Ti) (w2, xh F21 ",,"""",, xz2)). (Inn a Fnis" Fnk)),
where (1z, x)) Dai and (f, FK)) ~ negs with j [n]] (1...., .n) and K indicating the number of negative samples. However, the specific distributions Deim and Dueg are abstracted out once we are dealing with a fixed dataset S. The quality of the representation f evaluated using the loss E (f((=) fxx))) where f R + [0, B] is some loss function and f(x)T the transpose of [(x). The population and empirical risks are then defined as follows.
Definition 3.1 (Upstream unsupervised risk). The population unsupervised risk is defined as:
lsn()) = E(((U(())) {(T))))
and the empirical unsupervised risk on S is defined as:
Zf) Σ
n
To find the representations f in an unsupervised manner, we employ an unsupervised loss function E IR R+ which can be chosen to be hinge loss. Given vector u, the hinge loss is defined as:
E(u) max (0, 1 max max(-u;))
(E[K]
3.2 Adversarial Contrastive Representation Learning
In this paper, we examine adversarial scttings where an attacker employs a noise function A: X' B with B being a noise set, to subtly introduce noise 5 E B to an input x E X in order to maximize the loss. For example, in the L-paadiiive attack, A(x, 5) === x + and B is the ball (ō: [|0]|p S B}. The attacker's objective to select 8" E B that maximizes the loss:
8" arg max
-(E))))
The adversarial and empirical risks are subsequently defined as follows. Definition 3.2. (Unsupervised adversarial contrastive risk). The population unsupervised adversarial contrastive risk defined as:
I Ladv(1 (f) E [aa (0) 1(
dEB
4

---

Published in Transactions on Machine Learning Research (11/2024)
and the empirical unsupervised adversarial contrastive risk is defined as:
" max dEB
i Lady (f) =
In our definition of adversarial contrastive risk, the adversary is restricted perturbing only the anchor sample H, while the positive sample x+ and negalive samples x" remain clean. This is consistent with standard practices in both theoretical (Zu & Liu 2023 and practical applications of ACL (Kim et al. 2020 Ho & Nvasconcelos 2020 Jiang et al. 2020), where adversarial perturbations are typically applied to the anchor sample alone. This setup allows us to evaluate the robustness of the learned representation without. disrupting the fundamental contrastive structure between positive and negative samples.
Our goal is to derive a generalization bound for ACL, that is a bound on Ladv (f) - Ī (f)-
4 Generalization Error Bounds
In this section, we establish a generalization bound for ACL. Our technique relies on the concept of covering numbers of the adversarial contrastive loss class. Covering numbers measure the complexity of a function class JF by counting the minimum number of "balls" needed to cover all functions in F, where each ball represents a region of approximation with specified level of accuracy.
Definition 4.1 (Covering number). Let F {(f(x)), .... f(x))) be a real-valued function class, that maps X' Rd defined over a vector space V. and let == f-1.... .nn) X" be dataset. For any e <> 0, the f--norm covering number, denoted as F,S), is defined as the size of the smallest set of vectors U1,'" Um that covers F. Specifically, it satisfies:
2 E (f(x)) - sc TEFjElm) sE[n]
sup min
where "1 Um forms the (c, -cover of F with respect to S. Moreover, when the fp-norm is taken as the -orm,, we denote the covering number as No (e, Finally, the worst-case covering number is defined as Np(c, = maxsex* Ny, where the maximum taken over all possible datasets S C.C. X of size n.
To analyze the complexity of a function class involving a nonlinear loss function (e.g., hinge loss), we use Lipschitz continuity simplify the analysis by reducing the complexity to that of a function class without the loss function t. We consider a general Lipschitz continuity w.r.t. f--norm, defined as follows:
Definition 4.2 (Tipschitz continuity). function f: RCC - R_ is said to be X-Lipschitz continuous with respect to the fy-norm (p 1) if for any v, CR, the following inequality holds:
[e(v) - {(v') s Al|u- -1llpp
v'lpp-
In other words, Lipschitz continuous function exhibits only small change in its output when its inputs slightly change.
We now proceed to derive the generalization bounds for ACL. The function class of interest is defined follows:
Gadv {2x,x L ,x.,,,,,,;
max () -( BEB
We use covering numbers to measure the complexity of our function class Gaav by quantifying how well it can be approximated using simpler functions. This approximation helps establish generalization bounds, as a smaller covering number indicates a less complex function class, leading to tighter bounds on the adversarial contrastive loss.

---

Published in Transactions on Machine Learning Research (11/2024)
The structure of the analysis is as follows: 1) The Lemma 4.1 simplifies the adversarial contrastive learning function class (Gadv) by leveraging the Lipschitz continuity of the loss function (A2) and maxses to reduce its complexity to that of an intermediate class, H. 2) Building on this, the Lemma 4.2 further reduces H to an even simpler function class, F. 3) This final simplified function class, F. forms the basis of our main Theorem 4.1] which depicts that the generalization error of ACL governed by the covering number of this reduced function class.
The main challenge for the analysis of the ACL function class is due to the max operator. The maxseB operator adds complexity by requiring optimization over all perturbations, making the function class hard to analyze. To address this, our main strategy is to leverage the properties f f-o-coviingg numbers to control the complexity of the ACL function class, This approach allows us to effectively handle the high-dimensional function class and alleviate the challenges posed by the maximization operator (Mustafa et al. 2022). Removing this operator simplifies the class, enabling tractable analysis and the derivation of generalization bounds.
The following lemma shows bound on the covering number of Gady in terms of the covering number of extended function class that does not contain the maxses-operator and the loss function l on f. The extended function class is defined as:
H =
That is, the functioons in H are explicitly parameterized by the adversarial noise 8. Consequently, the data set is extended to:
Su = f =5, : E [n], k [K], 8 Cal, 6 }
2X1
where Co(2Á,) is an (2), cover of B, for some x, > O. Specifically, for any 8 E B, there exists 8 E C5((2 2A, such that ||ō 01000 I - We now introduce our first lemma, which establishes a relationship between the covering number Gadv on S and that of H on SH-
Lemma 4.1. Let 8 + ((ff(A(z, (f(x() f(x,, ))kk) be Ai-Lisschitz and & be X with respect to the -nomm, for all (z, I [R. E x and f F. Then, we have:
No S) < No
e H, SH,
2A2
The lemma shows that we can upper-bound the -overring number of the ACT. function class by that of the class H. with the extended training set Sy. Notably, the class H docs not include the max operator, significantly simplifying the analysis. Furthermore, it shifts the dependence on the nunber of negative samples from the dimensionality of the function class's output to the size of the training set. For most classes, the dependence of the covering numbers on the size of the training set is only logarithmic (Zhang) 2002 Consequently, our bound will lead to generalization bound that only has a logarithmic dependence on the number of negative samples K. The proof of Lemma 4.1 begins by eliminating the maxags-operator, an approach based on Mustafa et al. (2022). Details of the proof are provided in the appendix.
Remark. The Lipschitz condition on the function 8 + it is a mild yet standard assumption that most adversarial attacks in the literature satisfy (Engstrom et al., 2019 Awasthi et al. 2021 Madry et al. 2017). This condition ensures that the loss function behaves smoothly and predictably, which essential for the success of gradient-basee adversarial attacks. Additionally, this Lipschitzness allows us bound the covering number of the adversarial class Gadv-
f(x is crucial because
Remark. The size of the exlended training set SH grows linearly with the size of the cover CF( (1,)x C=(25,) While the size of C=( can grow exponentially with the dimensionality of the perturbation set B, it's important to note that the dependence of the generalization performance is typically of the order ((log2/((Sxx)] as shown in prior work (Bartlett et al., 2017 Zhang [002 Mustafa et al. 2021p. Thus, the generalization bounds will exhibit a squarc-root dependency the dimensionality of B, leading to manageable bounds even in the presence of large perturbation sets.
While Lemma 4.1 provides an upper bound on the ACL class Gudy in terms of the non- con-adversarial class H. the class H is not directly the representation function class F. This makes it challenging to utilize existing
6

---

Published in Transactions on Machine Learning Research (11/2024)
covering number results for typical models (e.g., linear models (Zhang 2002 DNNs (Ledent et al. 2021b The following lemma establishes a relationship between the covering numbers of H and those of F.
Lemma 4.2. Assume the previous conditions hold and that [[(())] R, for all X. We define the function class F as follows:
(+ [ EE [d]
over the training set Sy:
S [(A((A,,)))))) 0).1) : [n],j [d].ö Cs( - ))U((( : In], [K],j e [d]o[(a]] (1) () :ie (n].j [d].
(x 2
Then, we have:
Noc -e H. SH S Noo (8 F, F,Sz).
2\2
The proof of this lemma is provided in the appendix. The lemma upper-bounds the covering number of H. by the covering number of the class F. Notably, F is class of scalar-values functions of the same form as the representation function class F. This simplifies the analysis by (1) reducing the form of the functions in H to that of the representation class, and (2) simplifying the analysis from vector-valued functions to scalar functions of the same form. Note that the number of dimensions contributes only through the size of the dataset 5j, and for many typical function classes, this contribution only logarithmic. This achieves the best known rate for vector-valued functions (Lei et al., 2019). Combining Lemmas 4.2 and 4.1 with Dudley's
entropy integral (Boucheron al. 2003 Bartlett et al. 2017 Ledent et al. 2021a Srebro et al. 2010 gives
main result.
Theorem 4.1. Let 5 (0, 1), and F= {f [|(0I)I s RJ, for some 0, where || Il denotes the 4-norm,
and d N represents the dimensionalitt of the feature space and F = { {(x,j) + fy(#) : F,z E X, [d] }. With probability at least 1 - over the randomness of the training data S with size we have for all f E F:
3B log(?)
Vn log Noo (.S)dde ['
24
B
Lady (f) Ladx (f)
+ inf
8a
v 22n
SRX2
The theorem demonstrates that we can control the generalization error of ACL by controlling the covering number of the class F. The covering numbers of many classes F (e.g., linear models (Zhang] 2002). ) MLPs (Bartlett et al. 2017). CNNs (Ledent et al., (2021)), and structured learning models (Mustafa al., 2021
can be directly applied here to derive genera lizatonizatio bounds for ACL across large family of models.
5
Applications
To learn the representations in an unsupervised setting, we employ an unsupervised loss function é R R4, which can be selected as the hinge loss. For simplicity, assume the loss function is bounded by B for any / E F. Specifically, this means:
AUS(A(,,)) (U)((( (())))))))((())))))))) -
VSEF.
This assumption is valid because we can impose constraints on the norms of the model's weights and inputs, ensuring the loss function remains bounded. In this section, we instantiate our bound (Theorem 4.1 for two models: linear and DNN-based features. Throughout the section, we consider feature extractors of the form x + Uv(x), where U E Rdxd' is a transformation matrix, and v X' + Ed is a map from the original data E X to some intermediate embedding space in Rdd.. We consider the lincar feature extractor in Section 5.1 while in Scction 5.2 we explore features from DNN.
5.1 Linear Features
First, focus the linear features. That is, we assume that is the identity map.
7

---

Published in Transactions on Machine Learning Research (11/2024)
We consider the -ttack,, in which the attacker uses additive noise function A(z,6) + 6, for X and 8 E B, where the noise set, B, is the ba-bal
B = :::10000 2 CR
8))² We begin by showing that the function 8 + [((v(< + 8))" (Uv(=t)) Uv(az ) is indeed Lips- chitz. The following lemma establishes and quantifics the upper bound on the Lipschitz constant of 8 - (<(U(( (U)=( ((x
Lemma 5.1. Consider the function gu (2.6) E((U(( (U) -x( and assume [| so.2 S A1. Then, for any x, the function ~ gu (x, is -ipssccci with the Lipschitzness constant 2A [-]12
Now that have the Lipschitzness of å the loss function e, we bound the covering number of our linear scalar-valued feature class in the following lemma.
Lemma 5.2. Let F be the linear feature class and Sy be given dataset in Lemma 4.2 with ||a||2 V for all E X, and ||0||,,2 A, then for all >> O, have
oo F, s CRPAZA? VD3)2
8R22
22
where is an absolute constant, m m= CB (CB((5))1, }|, v = v + VD3 and
Log log 2 1RRAAV +2 (nmd ndk + nd)
D 12BA
+1
If we plug Lemma 5.2 back into the Theorem 4.1 we get the following corollary.
Corollary 5.1. Assuming the above assumptions, for all f E F, with probability at least over the training data, we have
Lady (f) < adv (f) + 8 log(2/8)
VCRAAN Liog
3B
2n
vn
where C' is constant, v' VV3, m m= CB( -- )1 N amd ndK + nd and
Loog = log+ [4[RA2AA''+11 N
1288A|1==122 (128A1 +1) (log(n) + log( (B).
Remark. Our bound has dependency on the square root of the input dimension, VD, in the term v This arises due to the mismatch between the fz-norm of the input and the lx-nnorm in the ball B, encapsulated by the inequality ||ō]|2 < / Additionally, the bound has logarithmic dependence on the negative samples, K. The logarithmic dependency shows the appealing behavior of ACL for learning with a large number of negative examples.
5.2 Nonlinear Features
Now, we consider the covering numbers for learning the nonlincar features by DNNs. We say an activation function a IR + R is x -'). The ReLU activation function ozz) = max(2,.0 0} is both assume the DNN feature map is defined as (removing matrix U for now),
((x)) = ax for a > O, and is contracting if (a(x) - -(x') <
and contractive, Now
y= fz v(z) (VV (Vix))) E [[].
Each layer E [L] has the width of uy, where wp D (the input dimension) and wy (the number of feature dimension).
8

---

Published in Transactions on Machine Learning Research (11/2024)
Let V E V be the weight of the network. Suppose that V is such that, for all V E V, [Vil I aj and | 8t for all I E [T. 16-1,, 1]. Further, suppose that, for all V E V, |VVil12 S ot, |V S st. and ||Vil S 81.
We now consider the -adadiii perturbation applied to the DNN. As with the linear case, we first establish the Lipschitzness of the funetion 8 - {((Uv(x (Uvv(=+)) Uv(xx)) )===) w.r.t. || looom. The following lemma establishes the Lipschitz continuity of the loss as function of 6.
Uv(x ()= and assume |0,, S A and v(.) is the neural network. Then, for any x X and V V, the function + guvv(x, is || Ilxs-Lips with constant 2A / II $1 II St-
Lemma 5.3. Consider the function (uv(2, [(UUv( + 8))
Now, we can get the upper bound of the covering number of the neural network scalar-valued feature class w.r.t. --llo--ormm.
Lemma 5.4. Let F be the DNN (nonlinear) feature class the extended dataset Sz. defined before. Let B = (ō |00 S f3. Assume the previous assumptions on the weights of DNN, and ||l|2 I W. Then, for Sy and c > 0, we have
log log ( $ S
C
Loog:
8RA2
where
Loog = log ((c.VTR>N//++ C2u (nmd + ndK + nd)
1 12BAAs/ /wi ||21/2 I 81 Ih 81
+1).
V = - (V3), P (r s:)a////s, v maxte(r] Wt, m (CB(25) )1, and C, C1, C2 are universal
constants.
Plugging Lemma 5.4 into Theorem
4.1 we get the following corollary.
Corollary 5.2. Under the previous assumptions, for all f F, with probability at least 5 over the training data, we have
log(2/0)
+ CLRA2 V
L II
Σ d
um Lady (f) < jadv (f) + + +3 2n
Loog
vn
1=1
where C' is absolute constant, V' v + vD3, |CB( 24, }1, N nund+ + nad and
Loog= ((CITTTCCa)) (12BA) Vull 1
D (log(n) +lo((B)).
II
81 II [=1
am 2
+1
Remark. Similar to the results for the linear case, our analysis reveals dependency on the square root of the input dimension. This issue can be resolved if we assume the & attack, where B 8= {0 ||0l2 S B}. As in the linear case, our results maintain logarithnic dependence the negalive samples, K.
6 Experiments
We evaluate our theoretical results lo two widely used benchmark datasets from the image domain: CIFAR-10 and CIFAR-100 (Krizhevsky) 2009). CIFAR-10 and CIFAR-100 consist 50,000 training images and 10,000 testing images, organized into and 100 classos, respectively.
For linear features, we use a one-layer neural network, while for nonlinear features, implement fayr-layer neural network with ReLU activation. Both models are trained using the Adam optimizer, with a learning rate of le - 3. We perform adversarial training on the following objective function:
Experimental Setup
arg max ((ff(((z, ()) (f) fxx 1) dEB
9

---

Published in Transactions on Machine Learning Research (11/2024)
with step size of e/255, where represents the maximum allowable perturbation. A Afterward, a PGD attack is performed to evaluate the generalization error. The generalization error is calculated as the difference between the training accuracy and testing accuracy, a standard method commonly used the literature Yin et al. (2019). We calcu- late the generalization error for different values = (2/255, 4/255, 8/255, 16/255, 32/ 255, 64/ 205,155,11 128/255), with varying negative samples, K {63, 127, 511, 1023).
To generate adversarial perturbations, employ the &o PGD algorithm (Madry 2017
6.1 Results
We analyze how the generalization error varies with respect different parameters by examining the effect of step size (e) and the number of negalive samples (K). The results are presented in Figure 1 for CIFAR-10 and CIFAR-100. As expected, the generalization error increases the number of negative samples (K) grows. While this behavior is consistent with our theoretical bounds, it contrasts with findings in prior work showing that increasing K can enhance rownstream classification performance (Wang et al. 2022 Bao et al. 2022 Awasthi et al., 2022). This apparent discrepancy arises from the different objectives these two types of analyses. The generalization error increases with K because the function class becomes more complex, as the loss function must handle a greater number of comparisons. Furthermore, a larger K can make the model more prone to overfitting to the negative examples, thereby amplifying the generalization gap particularly if the loss function becomes overly sensitive to the contrast between positive and negative pairs. These two phenomena are not inherently contradictory but rather highlight the distinction between task-specific performance and the broader ability of the learned representations to generalize across diverse tasks.
CIRA8:10
CIFAR-10
-Wh ke53
0.7
0.40
k=127
kn
5-511
k-511
0.39
1--1
1-1023
Gteer ratton Brior
0.30
0.25
0.0
033
0.0
(spolion)
(epsiton)
CIFAR-100
CIFAR-100
0.7
k-1033
k-1523
Genersigaatin Breer
0.4
0.5
0.3
0.3
Figure 1: Generalization error with varying mumbers of negative samples. On the left, the features are learned using a linear model, and on the right, the features are learned using nonlinear model (4-layer neural network). As the number of nogative samples (K) incrcases, the generalization error rises.
10

---

Published in Transactions on Machine Learning Research (11/2024)
7 Proofs
7.1 Proofs of Results in Section 5.1
In this subsection, we present the omitted proofs of section 5.1 when the features are linear. Our approach relies on -overingg numbers for the feature classes. First, we show that the loss function is -ii-sscchii with respect the noise parameter J. Next, we derive a bound on the size of the set Cg(c/2A1). Finally, we establish a bound on the -ooeriigg number of the feature class FF on the extended data set Sz.
Initially, prove the bounds of l. aadditie attacks applied to linear models stated in Lemma 5.1 Our first step is to derive the || -Lipschp constant of the function å (([(U(z + o0) (U(x+) - U U k=
K
The following is the proof of Lemma 5.1
Proof of Lemma 5.1 The proof is direct derivation. For all x E E |U|| & A1, 8,8' E B, we have:
$ $1000-++1|1000001110000000000040 (U
<IUU(x 5100+++0)((411100000000000000000
$ [|00=-000-0((0000000000000011110
8') (z+ U( l
A - ((|U(=))]2 [U(=))) A 8'1 //=l/ s 2A lo
The second inequality is derived from the fact that hinge loss is loo Lipschitz with constant The fifth inequality uses the triangle inequality [[([+t)- - U(=))lla lll & |1 [U(x)))] )|22- The last inequality follows from || [zl|2,, for all E R.
In this paper, need upper bounds covering numbers of bounded balls in RD, We start by reviewing result that provides an upper bound on the size of the set CB(() defined w.r.t. general norm || ||.
Lemma 7.1 [Long & Sedghi 2019). Let d be positive integer, || be norm, be the metric induced by it, and K, e > 0. A ball of radius k in Idd w.r.t. can be covered by (3x y balls of radius e.
We now review the upper bounds on the -oveeriig numbers of linear models.
Lemma 7.2 [Zhang 2002). Let L be a class of linear functions on a set of size n. That is, L= {(w, w e J. If |x<1| S and [ S a, where S q < oo and 1/p + 1/q = 1, then for any e >> 0, we have
22 log[2[ 27 +1.
(c, s 36(g 1)
where Noc (c, C, n) is the worst-case covering number of the class L dataset of size
In the following, we present the proof of Lemma 5.2
Proof of Lemma 2.2 First, consider the foc-norm on the set B. According to Lemma 5.1 the function 8 ([((U(x + 8))² (U(x+)= (x is || Lipschis with constant of 2A Next, consider the set C=(e/4Af((o((2). By applying Lemma 7.1 and noting that || I B, we have for all 8 E B:
(2A 12A/|1=1223
[cs(c/4A]]|/1l2)
Thus, the size of our dataset is:
| n [2A (12A|10 d ndK nd.
For & E Sz, where à (xx 8), we have: ||ā||| $ ||ا|| l + 1101|2 S VDIl0lloc V. Therefore, the result
follows from Lemma 7.2
11

---

Published in Transactions on Machine Learning Research (11/2024)
Below, we provide the proof for Corollary 5.1
Proof of Corollary 5.1 The proof follows directly from Theorem 4.1 by setting to A Therefore, consider
the following integral
J.a logNos (SHA
B
c FF 1 {" CR + VD3)2 LIoR de S VCRYAAW Liog log(n) E
[
B 1
de
8R222
6²
Ling log(n) [ VORYAAW log(n)
Long (log(B) log(n)).
S VCRMAW
The first inequality follows from the monotonicity property of integrals. The second inequality derives from the observation that replacing by 1 Liog can only increase its value. Substituting this into Theorem 4.1 yiclds the desired result.
n
7.2 Proofs of Results in Section 5.2
In this subsection, we provide the omitted proofs from section 5.2 for the case when the features are non-linear. As in the linear case, we begin by showing that the loss function is Lie-Lips with respect to the noise parameter 5. We then establish bound the set CB(c/2X1) and apply the -overring number results of the non-linear feature class f on the extended dataset S
First, we prove the bounds of the - attacks applied to non-linear models as stated in Lemmaa 5.3, The first step is to derive the Lipsichhc constant of the function 8 + (({(Uv(x+ (Uv)((((()))))) (Uv(rt)-( - Uv(2, ())
1=)=
The following is the proof Lemma 5.3.
Proof of Lemma have:
5.3 The proof is a direct derivation. For all x, 2,,t,08 o0 E Ex ||0 I Ar, 8,8' E B, we
$ (X0- -UV())))))
h/tp://0(00oooooooo/////-///---- -V(2
(V) -V((x < [(Uv(x+0) -Uv(z (Uv(())) Uv(x -(v(z)
< ([V((=+))" - UV((
< ||U(v(x v(x (0)+))lvu(((((((+" (())))
$ A1llv(a + v(x (UV)= v(x ))22,
where we have used the 1-Lipschitzz property of the loss function L. Since ||0 S Ad, we further get
- - (U)
()) -
< A1
II
st
sis (lle) v(x v(xT))l1 -00 (V((x+) v(x ))12 - A II
1=2
1=2
S A 1=2
II
stv
w1
8111o - v( )222 s Assi II
siv
wi 88
llv v(x lo,
8'
L
L
L
$ A1s1
81
W1
8
8' Ao II s1||z - x 1 & A18
II
$/
811,2112
s|||0||2 st
1=2
1=2
un |
81 8' loo
1=2
where we have used the 1-Lipschitz property of the non-linearity and induction over the layers. The eight inequality results from converting the no-l nnor... Finally, the eleventh incquality based on the fact that ||æ -1 < 2|||,|1,, for all x E RD.
12

---

Published in Transactions on Machine Learning Research (11/2024)
We now review the upper bounds on the -overiing numbers of norm-bounded neural networks (non-linear) function classes.
2021b). Let V be the class of neural networks, that is, V fo + v(z),, where = (V) ..... Vh) are set of weights the DNN v(-) and is defined above. Suppose that | S and | I for all / E [L - 1], || aL, 122,c s2, || S b, and wy is the width of the l'th layer. Then given data set S with elements and > 0, we have
Lemma 7.3 (Ledent
oo s CL362 L
1.
Σ
log (1 ((C,bT/c+ Cn
where 1' ma (T a)mm//s w max L) wi, and C, C₁, C2 are universal constants.
In the following, present the proof of Lemma 5.4
Proof of Lemma 5.4 First, consider the loo -orm on the set B. By Lemma 5.3 we have the function + [(((Uv(x+ (Uv(2t)) )) is Ill-lac-Lipschitz with constant 2A s wi |æl| I 8t II $t. | I I st). By Lemma 7.1 and that || S 3, we have for all
Consider the set 8 E B:
L
/2
|2l1a I 81 II s1B
D
II
81
[I
s1)
<
1=2
Thus, the size of our dataset is
12A7$/ /0
IT
81 I $133
1 = n
d + ndK + nd.
For ä E S5,, where ă = (Ir we have
| S ||1||| + ||ā||2 s v + vDI1001 = V.
Therefore, the result follows from Lemrn
7.3
In the following, present the proof of Corollary 5.2
Proof of Corollary
The proof is similar to the proof Corollary
5.1
It is direct application of Theorem
4.1 by setting a
8
Conclusion
We conducted a generalization analysis of ACT, showing that the generalization error is bounded by the covering number of the feature class. Our results leverage the Lipschitz continuity and boundedness of the hinge loss our unsupervised loss function, given the constraints applied this bound on both linear and non-linear features, subject to aadadiiiive attacks. Unlike previous work, such as Zou & Liu (2023), our bounds are directly applied to the adversarial contrastive loss, avoiding the use of surrogate losses. Moreover, our bounds scale logarithnically with the number of negative samples K, with a complexity (log K). Although these are
the model's weights and inputs. We
bounds, they could be extended algorithm-dependent bounds understand how the optimization process affects the generalization error. In this paper, we have applied only addiiiie attacks; nonetheless, other types of adversarial attacks can also be tested, especially non-additive tacks..
13

---

Published in Transactions on Machine Learning Research (11/2024)
References
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A thcoretical analysis of contrastive unsupervised representation learning. arXiv preprint orXiv: 1900..0229, 2019.
Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. Adversarial learning guarantees for linear hypotheses and neural networks. In International Conference on Machine Learning, pp. 431 441. PMLR, 2020.
Pranjal Awasthi, George Yu, Chun-Sung Ferng, Andrew Tomkins, and Da-Cheng Juan. Adversarial robustness across representation spaces. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 7608 7616, 2021.
Pranjal Awasthi, Nishanth Dikkala, and Pritish Kamath. Do more negative samples necessarily hurt in contrastive learning? In International conference on machine learning, pp. 1101-1116. PMT.R 2022.
Han Bao, Yoshihiro Nagano, and Kento Nozawa. On the surrogate gap between contrastive and supervised losses. In International Conference on Machine Learning, pp. 1585-1606. PMLR, 2022.
Peter Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normalized margin bounds for neural networks. Advances in neurol informalion processing systems, 30, 2017.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim Srndić, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In Machine Learning and Knowledgee Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part III 13, pp. 387-402. Springer, 2013.
Stéphane Boucheron, Gábor Lugosi, and Olivier Bousquet. Concentration incqualitics. In Summer school machine learning, pp. 208 240. Springer, 2003.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neurol information processing systems, 33:1877 1901, 2020.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Advances in neural information processing systems, 33:9912-9922 2020.
Kejiang Chen, Yuefeng Chen, Hang Zhou, Xiaofeng Mao, Yuhong Li, Yuan He, Hui Xue, Weiming Zhang, and Nenghai Yu. Self-supervised adversarial training. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2218 2222. IEEE, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020b.
Ching Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka. Debiased contrastive learning. Advances in neural information processing systems, 33:8765-8775, 2020.
Logan Engstrom, Brandon Tran, Dimitris Tsipras, Ludwig Schmidt, and Alcksander Madry. Exploring the landscape of spatial robustness. In International conference on machine learning, pp. 1802 1811. PMLR, 2019.
Tianyu Gao, Xingcheng Yao, and Danqi Chen. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint arXiv:2104.0888 088221, 2021.
Kaiming Hc, Haoqi Fan, Yuxin Wu, Saining Xic, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pottern recognition, pp. 9729 99389,7788488 2020.
14

---

Published in Transactions on Machine Learning Research (11/2024)
Olivier Henaff. Data-efficient image recognition with contrastive predictive coding. In International conference PMLR, 2020.
machine learning, pp.
Chih-Hui Ho and Nuno Nvasconcelos. Contrastive learning with adversarial examples. Advances in Neural Information Processing Systems, 33:17081-17093, 2020.
Wenlong Ji, Zhun Deng, Ryumei Nakada, James Zou, and Linjun Zhang. The power of contrast for feature
learning: A theoretical analysis. Journal of Machine Learning Research, 24(30))1-77, 2023.
Ziyu Jiang, Tianlong Chen, Ting Chen, and Zhangyang Wang. Robust pre-training by adversarial contrastive learning. Advances in neural information processing systems, 33:16199-16210, 2020.
Justin Khim and Po-Ling Loh. Adversarial risk bounds via function transformation. arXiv preprint 1xii:1810.0955 2018.
Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in neural information processing systems, 13:18661-18677 2020.
Minseon Kim, Jihoon Tack, and Sung Ju Hwang. Adversarial superviid contrastive learning. Advances in Neural Information Processing Systems, 33:2983 2994, 2020.
Alex Krizhevsky. Learning multiple layers features from tiny images. Technical Report, 2009.
Antoine Ledent, Rodrigo Alves, Yunwen Lei, and Marius Kloft. Fine-grained generalization analysis of inductive matrix completion. In Advances in Newral Information Processing Systems, volume 34, pp. 25552, 2021a.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 8279-8287, 2021b.
Yunwen Lei, Ürün Dogan, Ding- Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5): 3021, 2019.
Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuai Zhou. Generalization analysis for contrastive PMLR, 2023. Philip M Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. arXiv preprint Xii::1905.12600, 35:4053 4061, 2019.
representation learning. In International Conference on Machine Learning, pp.
Aleksander Madry. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.060M 2017.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. CoRR, 101111006000000 2017.
Mchryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Omar Montassor, Steve Hanneke, and Nathan Srebro. Ve classes are adversarially robustly learnable, but only improperly. In Conference on Learning Theory, pp. 2512 2530. PMLR, 2019.
Walced Mustafa, Yunwen Lei, Antoine Ledent, and Marius Kloft. Fino-grained generalization analysis of structured output prediction. arXie preprint arXiv:2106.001 2021.
Walced Mustafa, Yunwen Lei, and Marius Kloft. On the generalization analysis of adversarial learning. In International Conference on Machine Learning, pp. 16174 16196. PMLR, 2022.
Kento Nozawa, Pascal Germain, and Benjamin Guedj. Pac-bayesian contrastive unsupervised representation learning. In Conference Uncerlainly in Artificial Intelligence, pp. 21-30. PMTR, 2020.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning, 8748 8763. PMLR, 2021.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. Smoothness, low noise and fast rates. Aduances in Neural Information Processing Systems, 23, 2010.
Christian Szegedy, Wojciech Zaremba, Lyya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint ar (rXx:1312.61999 2013.
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, Port XI 16, pp. 776-794. Springer, 2020.
Florian Tramer and Dan Boneh. Adversarial training and robustness for multiple perturbations. Advances in neural information processing systems, 32, 2019.
Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is a ladder: A new theoretical understanding contrastive learning via augmentation overlap. arXiv preprint arXiv:2203. 13457, 2022.
Wen Wen, Han Li, Tieliang Gong, and Hong Chen. Towards sharper generalization bounds for adversarial contrastive learning.
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, and Zhi-Quan Luo. Adversarial rademacher complexity of deep neural networks. Xic preprint orXiv:2211.14966 2022.
Jingyuan Xu and Weiwei Liu. On robust multiclass learnability. Advances in Neural Information Processing Systems, 35:32412 32423, 2022.
Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for adversarially robust
generalization. In International conference on machine learning, pp. 7085 7094. PMLR, 2019.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527 550, 2002.
Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, 24(114):1-54, 2023.
A Appendix
this section, we provide the missing proofs of section 4
A.1 Proofs of Lemma 4.1 and Lemma 4.2
To discretize the function space, we assume + ((( is Ay-Lipschitz for all x E X and f E F. Let Cs(2ú) be an (2f.. B. Assume the discretized class of loss function is Gadv, defined below:
Gudv = (I1 2x. -
with an extended training set $:
3 = ( "
[n]. 8 Co(e)(2x1))
Now, we review a lemma from Mustafa et al. (022) to relate the loc covering number of class Gady to the covering number of the discretized version Gudu
16

---

Published in Transactions on Machine Learning Research (11/2024)
Lemma A.1 MMustaaa et al. 2022 Let Gadv be defined as above. Then, the following holds:
Ne, Iadv: S) S Noc (c/2, S).
This lemma simplifies the complexity of our function class by discretizing the loss function according to 6. Now, we can prove Lemma
Proof of Lemma 4.1 According to Lemma A.1 it suffices to show that
No (c/22 S) S Noc (c/(222) H. Sn).
The observation here is that we can construct a cover for the function class Gndv on the training set from the elements of the cover of the function class H. Additionally, from the Definition 4.1 we know that the covering number a set is the cardinality of the smallest cover for a sct.
For any S, define h as
hy(r, xt _) .8) f(A(z, (f)e, - f(x
Let CB(e/(2A1)) {ō1,
J. The projection of H onto the set Sy is
h (11, TT,
hy(r1, ot. TiI 8m)
H.sn
: if F
RRKxm
hn(In, 2xx
h2 : In 8m)
Let
(51)
(6m)
C#
i 1..., M C Rukxm
Cop (81)
c (6m))
be an (e/(2>z), cover of Hsy This means, for all F, there exists E [M]] such that
1y at F 8) c2h S 2X2
max max max (E|D] KE[K] (E)
Now we show the following set is an (c/2, -oover of Gado w.r.t. S:
Te(c (8)))
(6m)))
Cruac
:1' = 1..., M C Raxm
((mc)((mm))
Indeed, for any f E F, know
max max *E|n] sECs( ZÁT |e(U(A(E) (U(()));))))))))))))))))))))))
- -(( ()
(())
sE|n] (EC e(thrlo of FT 8)3 - E(te (8)){<))
max max
S X2 max max rE[n] 6ECo(
max (( xt F 5)) max (() KE[K]
kE[K]
S X2 max max rE(n] deCul
max KE[K]
(e(h,(ri, xt Fit. 8)) E(c,t (8))
X2 max tE(n] SECs(IiT) kE(K]
max h at I 0) ctth (8) I X2 2 2
The first inequality derives from the fact that l is Lipschitz with constant x with respect to the norm. The second inequality comes from max, f(z) max, g(x)) & max, [f(x) g(x) and the third inequality follows from the Ay-Lipschitzness of the loss function t. Since the cardinality of Ch and Co are the same, have Noo Sadv. 5) S Noc H. Sz).
17

---

Published in Transactions on Machine Learning Research (11/2024)
Now, are going to prove Lemma 4.2
Proof of Lemma 4.2 Our goal is to control the -overrig number of the function class H. using the covering number of the representation function class F. We will prove the lemma in two parts. First, we claim to show:
Noc 2x2 2x, HH, s Nox ( F,ST)
88R22
where we introduce S follows:
Sy = f j jje E [nm nK +n]} = (A(z,,)) : [n], Cs(c/(2A))))Uzzz : : [n],k [a]] : [n]]
and = [Cs(e/2\1)1 Consider the following class of functions defined on SF
Fs, (f(G)).... if F} C R amm+nK+n
which can be expanded as:
()) 8m)), (.)) ((T)).... ((
Suppose the function class Fsy has proper (e/(8RA2) )oover below
CF (() ch ..... क o
,4.., 20 )):") [M]] C pam+nn+n
Then for all f E F, there exists an E [M] such that:
max [A( 5a)) [5,)
XE [n] aE mm]
8RA2
max
sE(n] {fxxt) -
8R\2
max xE|n &E[K] [ at!-| 8R\₂
Now, for the following function class
Hsn = (11 f(Ti)). 6m)) (f [(xTK))) c Rmnm
projected onto the dataset Sy, we construct a cover as follows
CH C== = (c)( ....,..
ak (5m)) : o' E [M/]] c RuKm
18

---

Published in Transactions on Machine Learning Research (11/2024)
where c2 (ca) ) We then have
max max max ([(A(1,,8.)) *E RE K] [G]]Kaa(n am(m)
(8a))
max max max ( (f(())(())))()))))) - f(z7)) (dT - -C,tT
sE|n] [E[K]aE[m)
max max max [f(A (f(o)) f(())) ((A(I1,)a)) (ct - z
:e[n] kE[K] ae[m)
(((A(o).88))
- T
S max max max iE(n] KE[K]aE[m)
(IF(A(())))) (f(x)) - f(xū)) - f(A(T,) ++t))
-
+ (((A(1),5))) (c)) - - (c+ - -x---)
S max max max [S(A(es (f(()) द,- - ((xxe) + x ) |0,, - ( (3,, Ra)) ((63))
sEin] [[]m
+ max max max AE[n] KE(K] aE(m!
Smax max TE[n] [c(m]
[[((A 31)
mmax max iE(n] RE(K)
-+ 1|x
+max max
|
-2-h 1 max max f(A(2, -
22h
TE|n] kE(K]
sE(m mEim)
c + 2R
c
S 2R
4R
8RA2
8RA2
8R22
2d2
In the second equality, we added and subtracted [(A(s;, (T) - a*-) and used the subadditivity property of absolute values in the first inequality (ie. Ix + yl S |z| (yl). Here, the third inequality uses the property that j2' S |olllo and the fact that (A, da))ll S R. Since the cardinality of CF and Cy
are the same, we have: No (25g, H. Sn) S Noc (BRA F, Sz).
For the second part of the proof, we need to show
Noc e
F,55 s
F, F,ST)
SNa
F, F,)z)
8R22
88822
We introduce Sz:
8 ((ē,t) 1 [ndm + ndK + nd]}
{(A(z,,)),)) : [nl.j [d], E Co(, 2X1
{ () :ie [m], [K],5 e [d]] U ((t((t)))) (att)))ie :ie [m],j e [d].
Assume
== ((,,)) + -
[d]
over Sy has (c/(8R>2), loo) -cover defined as below:
C# = (())
(21) (1)),
and (5m)
and+
2 znkd : i' E [M] c andm+ndK +nd
This means the projection of f. on the extended dataset Sy is:
8sy = (((((A((1))))) (.))).......((((( fa(A((n, fmm)). JI (x fi ... ( C Rnd
+ndk + tnd
Then for all f E F, there exists an E [M], such that:
max max max (A(x,, 8a)) - 256 8R\² se[n] aE|m) sE[d]
sE|n| jEld [f)()) -t 8R\₂
max max
E
max max max [
*E|m| ke K] sE[d]
8R12
19

---

Published in Transactions on Machine Learning Research (11/2024)
Now, for the function class
..... Fsy ((f(A(21, 61)), 5 ((A(Fn (.. ((t)) f( ( ((nx)))
we construct cover as follows
Cy = (...
...))...,,............. (8))) ..... ctt cq
oft .......' ) :t' E [M]} C Runtnkkn
where (ō.) = (,),),.....)( ot = = ". y and ctt (2ik1- 2kd exd- Therefore, we have
.....
max max [[((A(i;)))) 8a)) - (ôa0lloo = max max max (A(Ti, 8n)) max き.e (da) xE[n] mm(m]
ic[n] aE[m] SE[4]
jEld
S max max max J (1;,, 80)) - S 8R\2 iE[n] a6|ml jE'd
max [x(x); - 1100 iE|n]
max
max jE[d]
[5
max a JE|d]
max max iE|n] sE(d]
[5(x,]] 235 S 8R)2
iE(n]
and
2k 10 max max max (1
max zikj
max max <c(n] kE[K]
iE|n] kE(K] JE[d
jE(d]
max max max f, (2 - 4E|n] KE[K] sEld
askj S 8R\2
The sccond incquality comes from max, fxx max, g(>)l )1 S max, ffxx) g(x)] and the cardinality of C and Cy are the same. then follows that Cf is an loc to F. Thus, we have
Noc e F,F F,Sr) S
_ S
c
F.
8RX2
8R12
The proof is completed.
A.2 Proof of Theorem 4.1
To prove Theorem we define the Rademacher complexity and review the theorem A.1 from Mohri et al. (2018), which controls generalization of learning algorithms by Rademacher complexity of function classes. Definition A.1 (Rademacher complexity). Given a class of real-valued functions F and dataset S= {2 ) drawn from the distribution over space Z, the empirical Rademacher complexity of F w..tt. is defined as Ag = E_ 1 ( where each 6; is independent Rademacher variable, uniformly m
distributed over [+1,-1] The worse-case Rademacher complexity is then Rz,m st (
Thcorem A.1 Mohri et al. 2018). Let S = {m be i.i.d. random sample from a distribution D defined over Z. Further let. F [0, 1 be a loss class. Then for all å E (0, 1), we have with probability at least 5 over the draw of the sample S, for all f e F that
log(2/8)
B(f) < +()) +3
2n
Our approach relies, however, on another complexity measure, namely coveriig numbers. The following classical result of Dudley's entropy integral (Boucheron al. 2003 Bartlett et al. 2017 Ledent et al. 2021a Srebro et al. 2010 gives relationship between the Rademacher complexity and t -overrig number. We
apply the version by Srebro et al. (0010).
Theorem A.2 (Srebro et al. 2010). Lot F be a class of functions mapping from a space and taking values
in [0, b], and assume that 0 E F. Let be a finite sample of size m and [[f())² = 1
m Em f(z)2. Then
sup [
12 Vn Ja
R(F) < inf
4a +
Vog F,
a>0
20

---

Published in Transactions on Machine Learning Research (11/2024)
We now ready to present the proof of Theorem 4.1
Proof of Theorem 4.1 The proof is direct application of Theorems A.2 - 6, for all f E F and 8 E (0, 1), we have,
and
A.1
With probability at least
log(2/0)
Lad (f) < L adv (f) + (9av)) + 3B
2n.
24
B
log (2/5)
I Ladv (f) + inf
8a +
Vlog log.Noo (E, Gadv, S)de
+ +3BV
as0
2n
< Lady (f) + inf
8a +
24
B
c NoggNos
F, Sz)de
+BBV
log (2/(2))
Vn
8R1²
2n.
The first and the second inequality follow from Theorem inequality is derived from Lemmas
A.1
and Theorem
A.2
respectively. The final
and
21


Reviews:
[{"review_id": "ffKvLC5Sb6", "reviewer": "Reviewer_9AcV", "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. Contrastive learning is an important learning paradigm, and analyses of which factors are important for generalization performance are valuable to inform algorithm design. \n\n2. The paper describes a theoretical technique to deal with the $max$ operator over a set $\\mathcal{B}$ in a risk bound, by passing to a cover of $\\mathcal{B}$. This technique is potentially useful beyond the scope of this paper.\n\nWeaknesses:\n1. The notation is confusing at times, and sometimes inconsistent, making it difficult to closely follow every equation in the arguments in the paper. More generally, the manuscript seems to require more technical proof reading.\n2. There is a general lack of an intuitive explanation of the various components involved in the bounds, how the various function classes defined relate to one another, and how the final results relate to prior work, making it hard for the reader to appreciate the finer details of the main contribution.\n3. The Lipschitz bounds in the paper might blow up with deep feature extractors, making the risk bounds vacuous in a practically viable number of data points. Even though this is a common shortcoming of current results in generalization theory, there should be a discussion to this effect in the paper, if true.", "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 analyses the generalization properties of empirical risk minimization for the _adversarial_ version of the so called _contrastive learning_ setting. In the setting of contrastive learning, the learner has access to two distributions $D_{pos}$ and $D_{neg}$, and aims to find a mapping $f \\colon X \\to R^d$ that pushes positive samples closer by minimizing $\\langle f(x), f(x^+) \\rangle$ where $x, x^+ \\sim D_{pos}$, and negative samples farther apart by maximizing $\\langle f(x), f(x^-) \\rangle$ where $x \\sim D_{pos}, x^- \\sim D_{neg}$. In the adversarial version of contrastive learning defined in this paper, an adversary perturbs $x$ to any $x + \\delta$ where the perturbation $\\delta$ lies in a ball $\\mathcal{B}$ around the origin. There are several knobs in these settings, e.g., what is the measure of \"closeness\", and, what is the strategy of the adversary.\n\nOne way to obtain such a $f$ is to minimize the quantity, $\\max_{\\delta \\in \\mathcal{B}} \\langle f(x + \\delta), f(x^+) \\rangle - \\langle f(x + \\delta), f(x^-) \\rangle$, averaged over the training data samples. In this paper, the objective is slightly more complicated, by using $K$ negatives samples, instead of $1$. This leads to the learning objective as minimizing the loss defined by $L(f, \\ldots) = \\max_{\\delta \\in \\mathcal{B}} l(\\langle f(x + \\delta), f(x^+) - f(x^-_1)\\rangle, \\langle f(x + \\delta), f(x^+) - f(x^-_2)\\rangle, \\ldots, \\langle f(x + \\delta), f(x^+) - f(x^-_K)\\rangle)$, averaged over the data samples, for a suitable aggregation function $l \\colon R^K \\to R^{\\geq 0}$. The notion of closeness is thus taken to be the inner product, and the strategy of the adversary is taken to maximize the learner's loss. \n\nThe main contribution of the paper is then to derive a generalization bound on the performance of the learning algorithm, i.e., a high probability bound over the draw of the training data, on the difference between the population loss and the empirical loss, $| \\mathbb{E} L(f, \\ldots) - \\widehat{\\mathbb{E}} L(f, \\ldots)|$, as a function of the number of data samples, and various properties of the function class $\\mathcal{F}$ that the learner searches over, and the perturbation set $\\mathcal{B}$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The following is a list of changes that would be good to improve the paper, ordered by the line number in the paper. Critical requested \nchanges are marked with [C]. \n\n1. Abstract: Would be good to write a sentence on what _constrastive learning_ is before delving into vulnerability to adversarial attacks. \n2. Abstract: The reader might now know what is the _covering number technique_ , and does this have to do with a generalization bound. Would be good to either remove this, or provide more details here.\n3. Abstract: _which have improved ..._ grammar error in the sentence, what improvement is being referenced here?\n4. P1: _the average adversarial risk of downstream tasks ... is bounded by ... the unsupervised risk of the upstream task_: this seems bold. Doesn't this result need some kind of relationship between the tasks? What are these tasks?\n5. P1: _the bound depends on_: it is difficult for a reader to appreciate the bound here without having any knowledge of what exactly is being bounded, especially when the downstream task or of the upstream task is not specified yet. Recommend moving to later.\n6. P2: _isto_: typo\n7. P2: contribution 1: _show improved dependency_: the reader does not know yet what is being improved upon. Recommend providing more details of prior work, before presenting the contribution.' Similar suggestion for _tighter bounds_. \n8. P2: contribution 2: _is also_: grammar\n9: P2: _as well an additional theorem used in our proofs_: unnecessary to mention here. Recommend removal. \n10. [C]. Related Work section: to a reader unfamiliar with any papers on developing analyses in contrastive learning, this section is very hard to understand. Basic questions like what is being bounded, what is the relationship between the unsupervised tasks and what is a risk bound for unsupervised learning, make it hard to understand dives into nuanced statements about what is used in which bound so early on in the paper. Recommend moving this section to later, and comparing and contrasting to the main theorem, once it has been presented. This is important, as currently the paper does not have a thorough comparison with the bounds in related work, and how their dependence on parameters of the problem differ from Theorem 4.1. \n11. P3: _some input space_ -> \"an\" input space\n12. [C] The asymmetry between positive and negative samples is present throughout the paper, but is never expilictly commented on. Specifically, what happens when $K'$ positive samples are also used in the loss similar instead of just $1$. Is it important that there is an asymmetry between them? Why should this matter? At an intuitive level, contrastive learning is trying to learn close representations for $D_{pos}$ and push $D_{neg}$ apart. There seems to be no reason apriori to use a different number of samples used for $D_{neg}$ vs $D_{pos}$. A comment on this would be valuable. \n13. Is the set of classes $\\mathcal{C}$ discrete?\n\n14. [C] Please define the random variables, and the sampling procedure clearly. Currently, from the description, it seems like $D_{sim}$ is just the same as $D^2$, and then it seems like $D_{neg}$ is completely independent of both. Is this the correct interpretation? Is $x^-$ dependent on $x$, $x^+$? Are $D_{sim}$ and $D_{neg}$ densities? Ignoring for a moment that these are continuous random variables, the equations read: $D_c(x) = P(X = x | C)$, $D_{sim}(x, x^+) = E_c [P(X = x | C = c) P(X^+ = x^+ | C = c)]$. If $x, x^+$ are drawn independently, then this simplifies to $D_{sim}(x, x^+) = E_c [P(X = x, X^+ = x^+| C = c)] = P[X = x] P[X^+ = x^+]$, which is the density $D^2$. Is this intended, or perhaps there is something wrong in my statements?\n\n15. [C] Coming back to 14 after reading the main theorem, it seems that the distributions do not really matter once the dataset $S$ has been sampled, as from then on all quantities in the bounds are functions of $S$. This should be clarified, as, in contrastive learning, the performance of the final representation learnt is affected by whether the positive and negative sampling distributions are set up properly. A comment is needed after the main theorem if the result is in fact independent of the relationships between the sampling distributions. \n\n16. _D_ is undefined in $L_{un}$. Should perhaps remove it. \n17. [C] For the definition of the adversarial contrastive risk, it should be commented and stressed that the adversary is _not_ allowed to affect the positive samples $x^+$ or the negative samples $x^-$. This is different from a standard practical setting of adversarial attacks on contrastive learning, where a large part of the power of an adversary does come from being able to get the sampler to fail. \n\n18. [C] (17) also signals that a comparison or atleast a comment on the techniques in standard adversarial robustness, and the generalization analysis there is warranted. This is because the \"contrastive learning\" aspect of the problem is expressed via the form of the loss function, and the \"adversarial\" aspect of the problem is expressed via perturbing one of the inputs, and presumably the generalization aspects of the later have been studied in prior work. \n\n19. Defn 4.1, $\\mathcal{F}$ is self-referenced in its definition. Perhaps there is a typo here.\n\n20. [C]. Defn. 4.1, Covering Number: The text description is fine, but there is something wrong with the symbols. Why is the $1/n$ appearing in the definition? Does it scale the $\\epsilon$? What if there exists no $\\epsilon$ cover with m vectors? Please refer to a standard definition of cover, e.g., [these notes](https://www.stat.berkeley.edu/~bartlett/courses/2013spring-stat210b/notes/12notes.pdf). \n\n21. [C]. _we define the worst case covering number_ is this re-defining $\\mathcal{N}_p$? Then $S$ appears on the LHS, but is marginalized over in the RHS. \n\n22. [C]. From the definition of $\\mathcal{H}$, and onwards, it is unclear to the reader why does one care about the covering number of function classes. Perhaps it is good to have a description here mentioning the steps that will now be followed, and how covering number of the function classes are important in what is going to happen. \n\n23. _extended_ function class: Terms like \"extended\" or \"of the same form\" are used sometimes, without a clear interpretation. For instance, the function classes $G_{adv}$ and $H$ are not compatible, the input space for a function $g \\in G_{adv}$ is $2d + dK$ dimensional, whereas that for $H$ is $4d$ dimensional. Similar comments on $\\tilde F$ being of the same form as $F$. \n\n24. [C] Lemma 4.1: It would be good to comment on (1) Should one expect $\\lambda_1$ to blow up with the number of layers in $f$? (2) Explicitly mention the dependence of $\\lambda_1$ in the bound (currently it is hidden in $\\mathcal{H}$) (3) How does this bound scale with $K$? Currently this is quite implicit (as in I imagine the covering number on the RHS depends on $S_H$, which depends on $K$). \n\n25. [C]. _for most classes ... dependence ... is logarithmic_: Sure, but there is a blowup due to the covering number of the perturbation set $\\mathcal{B}$. This should be mentioned, and the tradeoff should be commented on. \n\n26. Lemma 4.2: Does $\\\\|f(\\tilde x)\\\\| \\leq R$ hold for all $\\tilde x$? Would be good to define the condition on $f$ more precisely here, and in the following results. In the definition of $\\tilde F$, is the condition $x \\in \\mathcal{X}$ a typo?\n\n27. _Dudley's Integral_: reference here\n\n28. Theorem 4.1: It would be good to collect all the conditions on $F$ and $\\tilde F$ here. These conditions are currently scattered around the text, for instance, Lemma 4.2 mentions $\\\\| f(x) \\\\|_1 \\leq R$. \n\n29. [C]. Theorem 4.1: It would be very useful to have a discussion on how the covering number arguments have to do with the generalization bound. Otherwise the above part of the paper feels very disconnected from the main theorem, and Th 4.1 comes out of the blue. Perhaps the key here is the sentence \"combining with Dudley's integral\", which should be explained.\n\n30. [C]. Theorem 4.1: Some comments on this result would be good in the general setting, even before jumping into specific $F$. For instance, what is the dependence on $K$? $D$? How should one be interpreting the integral in the result, how large should one expect it to be? Without such statement it is hard to understand the contribution of this result. Additionally, is there any prior work whose bound can be compared to here?\n\n31. Lemma 5.1. Notation: $U_2$ is the spectral norm, is $U_{2, 2}$ the same? Would be good to use one notation.\n\n32. [C]. Lemma 5.2: What is $C$ here? What is C? Please write the expression here, the reader has to go through the proof of the result to get $C$, even then it is a bit opaque because that proof refers to another paper.\n\n33. Corrolary 5.1: _logarithmic dependence on K_: How does one see this? $K$ appears in the expression for $N$. Then $N$ appears in multiple places in the expression for $L_{log}$. A clearer description would be good. Then, how does one see that this is an appealing behavior of ACL? Some prior work that suggests that the dependence is worse in other settings should be mentioned here.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DB52PizM1k", "reviewer": "Reviewer_DDN2", "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": "Paper strengths: \n- The paper presents interesting and novel findings in the context of adversarial attacks on contrastive learning methods. The motivation to consider a large number of negative samples is well explained and allows the authors to formulate a generalised version of the bound.\n- The proposed findings have the potential to improve the generalisation of current ACL methods and help make them more robust against adversarial attacks.\n- In addition to deriving the bound, the paper provides two simple scenarios where this bound is applicable, namely linear and non-linear features. These scenarios also reflect new insights into the dependence of the generalisation bound on the number of negative samples, the input dimension and the depth of deep neural networks.\n- The paper provides detailed and complete proofs and lemmas supporting the main theorems. In general, the method is well written and easy to follow.\n\n\nPaper weaknesses: \n- In the case of non-linear feature evaluation, it is considered a very specific case of a positive homogeneous contracting activation function, i.e. ReLU. While I understand that the reason for this specific case could be the simplicity of the proof, it makes sense to see how the nature of the activation function (homogeneous, positive, contracting, etc.) changes the applicability of the bound and whether the proposed generalised bound can be applied to other activation functions, e.g. sigmoid and GeLU.\n- Although the paper is well written, the mathematical analysis is difficult to follow.  It would help the paper to include additional information and guidance on the deviations, e.g. in the appendix.\n- While the paper provides important theoretical insights, the empirical validation of the given generalisation bounds is limited. While it is unrealistic to expect detailed large-scale empirical validation, small-scale experiments would be necessary, and if not, an explanation of why the validation is limited should be provided.", "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 motivation of this paper is to introduce and derive new tighter generalisation bounds for Adversarial Contrastive Learning (ACL). It considers the scenario of a single negative sample in the contrastive learning setting by analysing the impact of a large number of negative samples. To provide a tighter and more generally applicable bound, the approach uses the covering number technique and Lipschitz continuity of loss functions. Finally, the applicability of the proposed bounds is demonstrated in two general settings - linear features and non-linear features (from activation functions) derived from deep neural networks (DNNs). The evaluation shows that in both settings, the generalisation error is bounded by the covering number of the feature class. Furthermore, this bound depends on $\\sqrt{D}$, where $D$ is the input dimension, and on the logarithm of the number of negative samples ($K$).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Improving the paper understanding.\n- Including more empirical validation.", "broader_impact_concerns": "- Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cleeI96rul", "reviewer": "Reviewer_g1J8", "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:\n\n1. This paper studies a timely topic, and the theoretical support for adversarial contractive learning is mostly missing.\n2. Authors use the covering number of the feature class to bound the generalization bounds, and the deduction seems solid to me. I didn't check the entire proof procedure in detail.\n\nWeaknesses:\n1. This paper is lack of experimental supports. Adding a suite a simulation could help readers understand your theoretical results.\n2. Some part of writing could be improved, e.g.\n\n2.1 What is $N_\\infty$? Is it the worst case covering number? The definition is missing;\n\n2.2 Before assuming Lipshitzness, it would be better to justify or explain why this assumption is proper. And in Lemma 4.2, \"assume the previous conditions hold\", it would be better if the authors could explicitly write out all assumptions since it is a core Lemma for your work.\n\n2.3 For the loss function, it would be better if the authors could give some concrete examples in Section 3 Problem Formulation.\n\n2.4 One subsection (4.3) of Zou, Li 2023 is named Multiple Negative Sample Case, and hence it would be better if the authors could further elaborate when saying \"this work only considers one negative sample\"\n\n2.5 It would be better if the authors could use one paragraph to summarize their theoretical contributions in brief.", "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 aims to provide a generalization bounds and theoretical support for the adversarial contrastive learning. The authors derive generalization bounds on the unsupervised adversarial contrastive learning function class under some assumptions, and then apply their theoretical results to both linear and non-linear representations, including the deep neural networks with basic activation functions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Could the authors add some experimental results to demonstrate their theory findings?\n2. Please refer to the above \"Weaknesses\" section.", "broader_impact_concerns": "No ethical issue.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Because this submission sparked a lively debate among the reviewers about whether we should accept it, AE checked the whole manuscript again. During the discussion, the main arguments supporting the rejection were as follows:

1. All reviewers have concerns about the clarity of the paper.
2. Reviewers DDN2 and g1J8 have concerns about the lack of experiments.

As for the clarity, the quality has been improved significantly by the authors' great effort in revision (and special thanks to Reviewer 9AcV for the dedicated comments!). In the latest version, the entire proof flow, techniques, intuition about why the proof works for this setup, and the implications of the derived generalization bounds have been made much more transparent. It is also quite nice to remark on the limitations of the analysis, including the Lipschitz continuity assumption and bounded loss assumption. All of these are above the bar to convince me of the correctness of the proof flow. After checking the proof, AE also believes the correctness of the important lemma, such as Lemma 4.1.

As for the experiments, the authors also made significant efforts to obtain good results in the updated Section 6. The experiments effectively demonstrate the main theoretical finding, the large $K$ (# of neg samples) tends to degrade the generalization error. Although the experiments are performed with only CIFAR-10 and CIFAR-100 datasets and four-layer nets, this is sufficient for the "sanity-check" of the theoretical results.

For these reasons, AE has decided to recommend this manuscript for acceptance with minor revision. However, I want the authors to note that several concerns still remain in the manuscript. Specifically, Reveiwer 9AcV has left several good suggestions in the official recommendation---for example, the overview of how the covering number bound works could be briefly described for those unfamiliar with it. It would be essential for broadening the potential audiences, although the current overview would be sufficient for theory researchers.

From AE side, there are a few minor comments. Please consider taking them in during the camera-ready revision.

+ The paper title conflicts with one of the closely related work, Zou and Liu (2023), which might be not very appropriate and misleading. Let's brainstorm an alternative, nice title.
+ The finding that large $K$ degrades the generalization error is interesting because some previous papers have revealed that large $K$ improves the downstream classification performance, by contrast. Please refer to Wang et al. (2022), Bao et al. (2022), and Awasthi et al. (2022). While these two phenomena do not conflict, the contrast looks interesting and deserves to be mentioned in the paper.
+ Lemma 4.1 is a fundamental lemma to eliminate the max-operator when dealing with the covering number, and its proof largely owes to Mustafa et al. (2022). AE supposes that this fact can also be acknowledged briefly in the main body.

Lastly, the TMLR system does not provide us another opportunity to check the camera-ready submission, so AE's decision (accept with minor revision) indicates our reliance on the authors to complete the remaining revision. AE supposes this is possible. Good luck, and we look forward to seeing the camera-ready version.

----

Wang, Yifei, et al. "Chaos is a Ladder: A New Theoretical Understanding of Contrastive Learning via Augmentation Overlap." International Conference on Learning Representations, 2022.

Bao, Han, Yoshihiro Nagano, and Kento Nozawa. "On the surrogate gap between contrastive and supervised losses." International Conference on Machine Learning. PMLR, 2022.

Awasthi, Pranjal, Nishanth Dikkala, and Pritish Kamath. "Do more negative samples necessarily hurt in contrastive learning?." International Conference on Machine Learning. PMLR, 2022.
Decision: Accept (poster)