Towards Sharper Generalization Bounds for Adversarial Contrastive Learning

1 Introduction

Contrastive learning (CL), which learns generalizable feature representations from unlabeled data [Grill et al., 2020; Chen et al., 2020; Khosla et al., 2020], has demonstrated superior abilities in self-supervised learning [Wu et al., 2018; Misra and Maaten, 2020]. Despite the state-of-the-art performance, the vulnerability of learning models to small input perturbations [Hendrycks and Dietterich, 2019] has raised safety concerns when implementing them to high-risk applications [Lin et al., 2019; Ma et al., 2021]. These perturbations are capable of completely altering the models' decisions, commonly referred to as adversarial perturbations [Xu et al., 2019; Zhang et al., 2023].

Adversarial contrastive learning (ACL) has emerged as a prominent approach to improve the model's robustness against adversarial perturbations. Its fundamental concept involves addressing a min-max optimization problem by injecting adversarial samples into the CL objective [Gowal et al., 2020; Jiang et al., 2020]. The remarkable empirical effectiveness of ACL motivates the need for a theoretical understanding of the adversarially robust generalization of learned representations.

∗Corresponding author.

Theoretical analysis of ACL presents more challenges as compared to its non-adversarial counterpart [Arora et al., 2019; Lei et al., 2023]. The maximization operator over perturbations of adversarial learning [Xing et al., 2021; Xiao et al., 2022] introduces difficulties in measuring the generalization capability of the hypothesis class. Several previous work on this problem considers an approximate smoothness [Xiao et al., 2022] or surrogate adversarial loss [Yin et al., 2019; Khim and Loh, 2018], and then provides generalization guarantees. However, these classical results is invalid for ACL due to the inconsistency of analytical framework. They assume that inputs and true labels are known as prior knowledge, while the input label is not available to the learner of ACL, which makes the complexity estimation of hypothesis space more difficult than [Xiao et al., 2022; Yin et al., 2019; Awasthi et al., 2020; Mustafa et al., 2022]. Moreover, the interplay of instance-level perturbations, learned representations, and multi-component loss function renders standard analysis techniques of CL [Arora et al., 2019; Lei et al., 2023] inapplicable in adversarial scenarios.

To tackle these challenges, a recent study [Zou and Liu, 2023] considers the surrogate upper bound on the original adversarial risk, which reduces the analysis problem of the adversarial risk of ACL to that of the general risk using standard learning-theoretic techniques. In particular, they develop generalization bounds scale O(k) for ACL in terms of the number of negative samples k. However, the bound linearly dependent on the number of negative samples k will not be valid for large values of k [Chen et al., 2020; Lei et al., 2023]. Furthermore, the surrogate bound derived from the average supervised loss in [Zou and Liu, 2023] may overestimate the original adversarial loss, and not yield meaningful generalization guarantees [Awasthi et al., 2020].

This paper provides a comprehensive study of the generalization properties of ACL. In summary, this work makes three key contributions:

• We develop a unified generalization analysis framework

for ACL that spans both linear models and deep neural networks in its applicability, which sheds a new light on understanding the generalization properties in the self-supervised setup [Jiang et al., 2020; Fan et al., 2021]. Unlike prior work on optimizing a surrogate upper bound, we work directly with the original adversarial unsupervised risk, yielding a tighter generalization gap compared to [Zou and Liu, 2023].

• We establish generalization bounds scale O(log(k)) in the number of negative samples k, by leveraging ℓ∞- covering number and a novel vector concentration estimation technique. Our results hold for a broad range of negative samples, and exhibit a substantial advancement in the current Rademacher complexity-based bounds O(k) [Yin et al., 2019; Zou and Liu, 2023; Awasthi et al., 2019].
• We provide optimistic generalization bounds O(n-1 ) for the smooth loss by introducing robust self-bounding property [Reeve and Kaban, 2020] and using the local Rademacher complexity [Bartlett et al., 2005]. To the best of our knowledge, this is the first fast-decaying generalization bounds for ACL. Experimental observations on real-world datasets validate our theoretical findings.

2 RelatedWork

Adversarial Contrastive Learning. Recently, adversarial robustness has become a crucial requirement when designing learning algorithms. Conventional adversarial learning methods commonly use labeled data to adversarially train robust models [Madry et al., 2018; Zheng et al., 2020]. Due to the difficulty and high cost of acquiring large-scale labeled data, recent work has proposed ACL methods to achieve superior model robustness on unlabeled data, by incorporating the adversarial learning strategy with CL [Jiang et al., 2020; Lee et al., 2021; Kim et al., 2020]. A summary of relevant empirical work is provided in Supplementary Material B. Although these work show impressive performance, there is a lack of theoretical guarantees of the generalization of ACL.

Adversarial Robustness. Szegedy et al. (2014) have found that machine learning models are highly susceptible to imperceptible perturbations added to input samples. A recent work focuses on designing models robust to adversarial perturbations [Jiang et al., 2020; Liu et al., 2022; Kim et al., 2020], and investigating adversarially robust generalization from a theoretical perspective [Xing et al., 2021; Xiao et al., 2022; Zou and Liu, 2023].

Yin et al. (2019) study the adversarial generalization under ℓ∞ attacks by employing Rademacher complexity. They consider a surrogate adversarial loss based on the SDP relaxation. However, the relaxation is quite weak, causing the risk bound to be greatly overestimated. Awasthi et al. (2020) extend the prior work of [Yin et al., 2019] and provide a general analysis of ℓr attacks (r ≥ 1). The studies of Awasthi et al. (2020) and Yin et al. (2019) are both limited to simple models and architectures (e.g., one-hidden-layer neural networks). Khim and Loh (2018) establish the adversarial risk bounds for multi-layer neural networks by introducing the tree-transform, which can be vacuous since they assume that the perturbations propagate through each path in the network independently. Mustafa et al. (2022) obtain the generalization bounds for deep neural networks by leveraging the notion of coverage. Their bounds apply to the original network and grow as O(log(K)) in the number of label classes K, while the existing bounds mostly grow as O(K) [Yin et al., 2019; Awasthi et al., 2020; Khim and Loh, 2018].

The aforementioned work is confined to supervised learning paradigms. Theoretical understanding of self-supervised learning under adversarial scenarios remains underdeveloped. A recent work [Zou and Liu, 2023] studies the generalization properties of ACL based on the supervised surrogate risk. Specifically, they derive a surrogate upper bound on the original adversarial unsupervised loss by exploiting the monotonicity of the function and introducing the notion of average supervised risk. By analyzing the Rademacher complexity of the surrogate, they establish the generalization bounds scale O(k) in the number of negative samples k. In contrast, we consider a general class and a novel adversarial sample set with cardinality nk to approximate the adversarial unsupervised loss class. With these in mind, we develop the bounds scale O(log(k)) by quantifying the covering number of the general class over adversarial samples. The relevant work is summarized in Table 1.

3 Adversarial Contrastive Learning

Let the vectors are denoted by boldface lowercase letters (e.g., w), and the elements in the vector be denoted by italics letters with subscripts (e.g., wi). The matrices are denoted by uppercase letter (e.g., W). For a matrix W = (w1, . . . ,wd′ ) ∈ Rd×d′ , the (p, q) matrix norm of W is defined as ‖W‖p,q = ‖(‖w1‖p, . . . , ‖wd′‖p)‖q. The Frobenius norm of matrices is denoted by ‖ · ‖F . Let p∗ be the number satisfying 1/p + 1/p∗ = 1.

Let X ⊆ Rd denote the space of all possible sample points, and C denote the set of all latent classes. Suppose there exists a probability distribution Dc over X that quantifies the relevance of sample x to the class c, where c is randomly drawn according to the distribution ρ on the classes C. The probability of similar samples x and x+ drawn from the same class c is expressed as

and the probability of drawing the negative sample x- unrelated to x is expressed as

Let (xi, x+i ) ∼ Dsim and (x-i1 , . . . , x-ij , . . . , x-ik ) ∼ Dneg, where k denotes the number of negative samples. Given a training set S = {(xi, x+i , x-i1 , . . . , x-ik )}ni=1 of size n, the target of CL is to learn a representation function f : X ↦→ Rd′ on unlabeled samples such that pulls together similar pairs (xi, x+i ) and pushes apart dissimilar pairs (xi, x-ij ) [Chen et al., 2020; Arora et al., 2019; He et al., 2020]. Let F be a family of functions mapping from X to Rd′ . A popular approach for seeking a good representation f ∈ F is to minimize the following empirical risk on S

where f(xi)T denotes the transpose of f(xi), and ℓ : Rk ↦→ R+ is an unsupervised loss function, such as the hinge loss ℓ(τ) = max{0, 1 +maxj∈[k] {-τj}}, and the logistic loss ℓ(τ) = log(1 + ∑j∈[k] exp(-τj)) for τ = (τ1, . . . , τk) ∈ Rk .

In ACL, an adversary carefully designs adversarial samples to fool the learned model, resulting in performance deterioration [Kim et al., 2020; Fan et al., 2021]. From a representation perspective [Ho and Nvasconcelos, 2020; Kim et al., 2020; Zou and Liu, 2023], one can perturb x in a manner that its feature representation is as far away from f(x+) as possible and as close as possible to f(x-). Let Br(ε) be the perturbation space and defined as {θ : ‖θ‖r ≤

ε}. Given a sample (x, x+, x-1 , . . . , x-k ), a learned representation function f, the adversary selects the perturbation parameter by

where gf(x + θ, x+, x-) := f(x + θ)T (f(x+) - f(x-)) and its corresponding hypothesis class is defined by

A common strategy [Madry et al., 2018] for obtaining a robust representation f is to minimize the following adversarial empirical risk

The risk ˜ En(f) measures the empirical performance of f on training samples subjected to adversarial perturbation. The generalization performance of f in adversarial scenarios is measured by the adversarial population risk, defined by

In this paper, we are interested in the uniform deviation between adversarial population risk and adversarial empirical risk, denoted as ˜ E(f) - ˜ En(f ).

Results in learning theory [Bartlett and Mendelson, 2002] show that we can bound ˜ E(f) - ˜ En(f) by quantifying the complexity of the adversarial loss class ˜ Ladv, where

One of the main tools used in this paper to measure complexity of hypothesis classes is the ℓ∞-covering number [Zhou, 2002], as defined below.

Definition 1 (ℓ∞-covering number). Let S = {z1, z2, . . . , zn} ∈ Z n , and H be a function class defined over the space Z. For any µ > 0, the ℓ∞-covering number of H w.r.t. S, denote as N∞(H, µ, S), is defined as the smallest cardinality m of a collection of vectors v1, . . . , vm ∈ {(h(z1), . . . , h(zn)) : h ∈ H} such that

where vji is the i-th component of vector vj.

As pointed out by Mustafa et al. (2022), quantifying ℓ∞- covering number of class ˜ Ladv (i.e., N∞( ˜ Ladv, µ, S)) is difficult since it takes values in an infinite space. We utilize the following general class to approximate the adversarial loss class, i.e., ˜ Ladv :

which incorporates perturbations into the argument to remove the maximum over Br(ε). We further approximate k components of functions in Ladv by employing an adversarial set of cardinality nk.

To this end, we introduce some necessary Lipschitzness assumptions.

Assumption 1. Let functions ℓ : Rk ↦→ R+ and gf : X 3 ↦→ R be Lipschitz continuous:

1. The function ℓ is ξ-Lipschitz w.r.t. the ‖ · ‖∞-norm if, for ∀τ1, τ2 ∈ Rk and ξ > 0

1. The function gf is η-Lipschitz w.r.t. the ‖ · ‖r-norm if, for ∀x, x+, x-, θ1, θ2 ∈ Rd , and η > 0

It is worth noting that the Lipschitz property of ℓ is a fairly standard assumption, encompassing commonly used loss functions such as the hinge loss and the logistic loss [Arora et al., 2019]. Moreover, the Lipschitz condition on θ ↦→ gf (x+θ, x+, x-) plays a key role in our analysis and is readily satisfied by a wide range of attacks [Madry et al., 2018; Awasthi et al., 2020; Fan et al., 2021].

4 Theoretical Analysis for ACL

In this section, we present the high probability bound of generalization gap in Section 4.1. We further derive the optimistic generalization bound for the specific case in Section 4.2. Please refer to the Supplementary Material for complete proofs.

4.1 The Generalization Error Bound for ACL

We first derive an upper bound on the ℓ∞-covering number of the adversarial class ˜ Ladv .

Lemma 1. With definitions of (1), (2), (3), and Assumption 1. Let the set CB(µ/2ξη) be a µ/2ξη-cover of Br(ε) and define the adversarial sample set

Then, we have

Remark 1. The first inequality above allows us to control the ℓ∞-covering number of ˜ Ladv by the ℓ∞-covering number of Ladv, which extends previous work of [Mustafa et al., 2022] for supervised adversarial learning to unsupervised ACL. By exploiting the Lipschitz continuity of ℓ and covering the perturbation space Br(ε), we reduce the complexity analysis of the loss class Ladv w.r.t. k components to that of the function class G on ˜ S of cardinality nk.

Motivated by previous work [Srebro et al., 2010; Anthony et al., 1999; Lei et al., 2023], we derive the relationship between the ℓ∞-covering number and the worst-case Rademacher complexity, which serves as the key step in developing the generalization bounds.

Definition 2 (The worst-case Rademacher complexity). Let H be a real-valued function class. Given a sample S = {zi}ni=1 , the worst-case Rademacher complexity is defined as Rn(H) = sup|S|≤n RS(H), where |S| is the cardinality of S and RS(H) is the empirical Rademacher complexity of H on S defined as RS(H) = Eϵ[suph∈H 1n ∑i∈[n] ϵih(zi)], where ϵ = (ϵ1, . . . , ϵn) ∼ {±1}n are i.i.d. Rademacher random variables.

Theorem 1. With the same conditions in Lemma 1. Assume that ‖f(x)‖2 ≤ Λ for any f ∈ F and x ∈ X. Let the cardinality of cover set be defined as Mµ := |CB(µ/2ξη)|. Then

where C1 = 256, C2 = 128e, and R˜ S,nkMµ (G) is

and denotes the worst-case Rademacher complexity of G defined on the set ˜ S.

We then obtain the following high-probability generalization bound.

Theorem 2. With the same conditions in Theorem 1. Assume that the function ℓ is bounded by B. Then for all f ∈ F and gf ∈ G, with probability at least 1 - δ, we have

Remark 2. As we can see, the worst-case Rademacher complexity R ˜ S,nkMµ (G) is the key quantity for the generalization of ACL. In a typical case, R˜ S,nkMµ (G) = O((nkMµ)- 1 2 ), where Mµ is the cardinality of the set covering perturbation space Br(ε) and is heavily associated with the feature dimension. In this case, the generalization error bound has the order O(log(nkMµ)n- 1 2 ), similar to the bounds in [Lei et al., 2023; Mustafa et al., 2022]. This result is more favorable for downstream k-category classification tasks with larger k compared to existing bounds scale O(k) [Zou and Liu, 2023; Awasthi et al., 2020; Yin et al., 2019].

Remark 3. Despite Zou and Liu (2023) develop generalization bounds for ACL, they take the label into consideration for analyzing the adversarial risk. In contrast, our result derived from Theorem 1 directly applies to the original adversarial unsupervised risk, which provides a tighter generalization guarantee for ACL in a self-supervised manner [Fan et al., 2021; Lee et al., 2021].

4.2 The Optimistic Generalization Bound for ACL

We further refine the result of Theorem 2, and then develop the fast-rate bound for the generalization of ACL by using the smooth assumption of the loss function [Srebro et al., 2010; Reeve and Kaban, 2020]. Our analysis is based on the local Rademacher complexity [Bartlett et al., 2005] over adversarial samples.

Let the local adversarial loss class ˜Ladv|γ be defined as ˜Ladv|γ := {(x, x+, x-1 , . . . , x-k ) ↦→ maxθ∈Br(ε) ℓ({gf(x + θ, x+, x-j )}kj=1 ) : f ∈ F, ˜ En(f) ≤ γ}, which is the set of adversarial losses with empirical adversarial training errors at most γ, for f ∈ F. We consider the smooth loss function with the following robust self-bounding Lipschitz property [Reeve and Kaban, 2020; Mustafa et al., 2022].

Assumption 2. A loss function ℓ : Rk ↦→R+ is said to be λrobust-self-bounding Lipschitz continuous w.r.t. a set Br(ε) if, for any measurable functions φ, ψ : Br(ε) → Rk , we have

Based on Assumption 2, we show that the covering number of the local adversarial class ˜Ladv|γ can be bounded by the covering number of the function class G.

Lemma 2. Let G be defined in (1). Assume Assumption 2 holds. Further let the set CB(µ/2√2γλη) be a µ/2√2γληcover of Br(ε) and the adversarial set be defined as

Then, we have the upper bound

Then, we have the following structural result on the ℓ∞- covering number of the local adversarial class. It serves as a key step in developing the fast-rate bound by a sub-root bound on the local Rademacher complexity [Bartlett et al., 2005].

Theorem 3. With the same conditions in Lemma 2. Assume that ‖f(x)‖2 ≤ Λ for any f ∈ F and x ∈ X. Let the cardinality of cover set be defined as ˆMµ := |CB(µ/2√2γλη)|. Then

where C3 = 512, C4 = 256e, and Rˆ S,nk ˆMµ (G) is

and denotes the worst-case Rademacher complexity of G defined on the set ˆ S.

In the following theorem, we provide the optimistic generalization bound for the adversarial loss function under the smooth assumption.

Theorem 4. With the same conditions in Theorem 3. Suppose that the function ℓ is bounded by B. With probability at least 1 - δ, for all f ∈ F and gf ∈ G, we have

where the logarithmic factors are hidden in ˜ O.

Remark 4. Theorem 4 provides a fast-rate generalization bound, in the sense that the bound depends on adversarial training errors. Typically, we have Rˆ S,nk ˆMµ (G) = O((nk ˆMµ)- 1 2 ) [Yin et al., 2019; Lei et al., 2023]. Then, the first term grows as O(n-1 ), while the second term grows at the usual O(n- 1 2 ). However, if ˜ En(f) = 0, Theorem 4 implies generalization bounds

This achieves faster rates of convergence than existing generalization bounds [Zou and Liu, 2023; Awasthi et al., 2020; Yin et al., 2019].

5 Explicit Bounds for Hypothesis Classes

Theoretical results in Section 4 indicate that the generalization can be guaranteed in terms of the worst-case Rademacher complexity of hypothesis classes. In this section, we provide clear characterizations of the Rademacher complexity for linear hypotheses and deep neural networks, and establish corresponding generalization error bounds. Please refer to the Supplementary Material for complete proofs.

5.1 Linear Hypothesis Class

Let F be a class of linear functions from X to Rd′ , defined by

We derive the following upper bound for linear hypothesis classes.

Theorem 5. Let the class G be defined in (1), and the hypothesis class F be defined in (4). Suppose that the loss ℓ : R+ ↦→ R+ is ξ-Lipschitz and bounded by B. Let the perturbation be chosen in ℓr norm ball of radius ε. Assume ‖f(x)‖ ≤ Λ, δ ∈ (0, 1). Then, we have

and with probability at least 1 - δ for all f ∈ F

where Mµ = (12nξR2BxBε)d , Bε = max(1, d1- 1p - 1 r )ε, Bx = max{‖xi‖2, ‖x+i ‖2, ‖x-ij ‖2 : i ∈ [n], j ∈ [k]}, and Bp x = max(√p∗ -1, 1)max{‖xi‖2, ‖x+i ‖2, ‖x-ij ‖2 : i ∈ [n], j ∈ [k]}.

Remark 5. The generalization bound has additional dimension dependent terms associated with the adversarial perturbation, i.e., Bε and Mµ. The dependence d1- 1p - 1 r in Bε arises from the norm mismatch between the input dimension and the weight, which is consistent with Lemma 1 in [Awasthi et al., 2020]. In particular, if p ∈ [1, r∗ ], one can avoid a polynomial dimension dependence in Bε. As discussed in Remark 2, the dependence d in Mµ is due to the complexity of the perturbation space Br(ε). Therefore, we can narrow the generalization gap by reducing the effective dimensionality of the adversarial perturbation through a low-dimensional feature projection (d′ < d). In this case, the dependence on d is reduced to O(d′ ).

Remark 6. It is worth noting that the bound in [Zou and Liu, 2023] has as an extra polynomial dimension dependence dmax{ 1p - 1 p∗ , 1 p∗ - 1p } , and grows as O(k) in the number of negative samples k. In contrast, our result avoids such dependence and only grows as O(log(k)), which benefits from the application of the vector-concentration inequality [Maurer, 2016] and the covering number [Zhou, 2002], enabling us to obtain an optimistic generalization bound of order 1n by plugging an upper bound of ℜ ˆMµ and ˆMµ back into Theorem 4.

5.2 Multi-layer Neural Network

We consider L-layer feed-forward networks with the following hypothesis class

where σ(·) is an elementwise 1-Lipschitz activation function with σ(0) = 0, e.g., the ReLU activation, and Wl ∈ Rhl×hl-1 , where hL = d′ , h0 = d.

By applying the "peeling" argument [Neyshabur et al., 2015; Golowich et al., 2018] and the vector-contraction inequality [Maurer, 2016], we derive the upper bound on the generalization error of deep neural networks. The theoretical results are summarized in the theorem below.

Theorem 6. Let G be defined in (1), and F be a class of neural networks defined in (5). Suppose that the loss ℓ : R+ ↦→ R+ be ξ-Lipschitz and bounded by B. Let the perturbation be selected in ℓr ball with radius ε. Assume ‖f(x)‖ ≤ Λ, ‖W1‖2,p ≤ B1, and δ ∈ (0, 1). Then, we have

and with probability at least 1 - δ for all f ∈ F

where Bx = max{‖xi‖2, ‖x+i ‖2, ‖x-ij ‖2 : i ∈ [n], j ∈ [k]}, Bp x = max(√p∗ -1, 1)max{‖xi‖2, ‖x+i ‖2, ‖x-ij ‖2 : i ∈ [n], j ∈ [k]}, Bε = max(1, d1- 1p - 1 r )ε, and Mµ = (12nξ ∏Ll=1 B2 l BxBε)d .

Remark 7. The generalization bound above suffers from additional dimension dependent terms compared to its nonadversarial counterpart. As discussed in the linear case, one can indeed avoid d1- 1p - 1 r dependence in Bε by choosing an appropriate p-norm regularizer on the weight matrix (W1) of the first layer, where p ∈ [1, r∗ ]. A projection on a low-dimensional representation space can help alleviate d dependence in Mµ caused by the complexity of the perturbation. While the bound in Theorem 6 of order O(n- 12 ) is similar to the generalization bound in [Zou and Liu, 2023], our result scale O(log(k)) holds for a large k in the number of negative samples. By applying Theorem 4, we have a faster convergence rate O(n-1 ), which improves existing results [Zou and Liu, 2023; Yin et al., 2019; Awasthi et al., 2019].

6 Experimental Evaluation

In this section, we conduct several experiments to validate our theoretical results in Theorem 5&6.

6.1 Experimental Setup

Datasets. We use real-world datasets from UCI Machine Learning Repository 1 for experiments: theWine, A9a, Spambase, Waveform, CIFAR-10, and MNIST datasets. Statistics of datasets are provided in Table 2.

Model Settings. We adopt a one-layer network architecture without activation function as the linear model. A fivelayer feedforward neural network with ReLU [Hahnloser et al., 2000] activation is used as the non-linear model, where the number of units is (1024, 512, 256, 128, 64). All models trained by the Adam [Kingma and Ba, 2015] optimizer with the learning rate 1e - 3. Inspired by theoretical analysis of Theorem 5&6, we train an adversarial robust model by minimizing the objective

where ℓ(·) is contrastive loss defined in [Chen et al., 2020], W1 denotes the weight matrix of the first layer, and λ ≥ 0 denotes the regularization parameter. The ℓ∞ PGD algorithm [Madry et al., 2018] with step size ε/5 is used to generate adversarial perturbations, where ε denotes the maximum allowable perturbation.

Evaluation Metric. After adversarial training, we run a PGD attack to check the adversarial test AUC [Ling et al., 2003] for downstream classification tasks. Similar to [Yin et al., 2019], we evaluate the generalization performance of ACL models by calculating the generalization error:

Each experiment is independently repeated 10 times, with the mean value and standard deviation of the results across the 10 trials presented in Figure 1 and 2.

6.2 Experiments for Theoretical Observations

Effect of Feature Dimension. We first investigate the effect of feature dimension on the generalization behavior of ACL models. Specifically, we compare the generalization error (7) with different feature dimensions (i.e., d). As shown in Figure 1, the generalization error decreases as the number of features d decreases. This empirical observation implies that low-dimensional input can mitigate the impact of perturbations and improve the generalization ability.

1 https://archive.ics.uci.edu

Effect of Regularization. We evaluate the effect of the regularization on the generalization ability of ACL models. Here, we consider the objective with ℓ1 regularization (6), and observe the generalization error (7) of models trained with different regularization parameters λ. As shown in Figure 2, models trained without regularization (i.e., λ = 0) have larger generalization errors, which suggests that regularization is beneficial for enhancing the robustness of the model.

7 Conclusions

This paper provides a systematic analysis of the generalization properties for ACL. We significantly improve the existing generalization bounds O(k) to a logical factor O(log k) by developing the concentration estimation technique associated with the ℓ∞-covering number. Under robust selfbounding Lipschitz condition, we further provide the optimistic bound with the fast convergence rate, when adversarial empirical error is zero. Our analysis is easily applicable to various models: it requires simply quantifying the worst-case Rademacher complexity of the hypothesis class. We present the general results for linear models and multi-layer neural networks with ℓr additive perturbations. Our results show that the generalization error bounds have additional perturbation terms associated with the feature dimension and the weight matrix, as compared to their non-adversarial counterparts. One can alleviate dimension dependence in the perturbation term by imposing a p-norm regularization on the weight matrix, where 1 ≤ p ≤ r∗ , and thus reduce the generalization gap. Moreover, projecting the input into the low-dimensional feature space help reduce the effective dimension of adversarial perturbations and improve adversarially robust generalization. Experimental observations on real-world datasets validate these theoretical findings. In future work, we will investigate the generalization behavior of ACL under various adversarial attacks (possibly non-additive).

Figure 2: The generalization performance (mean value and standard deviation) under different regularization (λ). The dashed and solid lines represent the results of models trained without and with regularization, respectively. The first four subfigures and the last two subfigures show the results of linear and non-linear models, respectively. ε denotes the maximum allowable perturbation.

1

1

1

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Nos. 62376104, 62106191, 12071166, and 11801201), the Fundamental Research Funds for the Central Universities of China (No. 2662023LXPY005), and HZAU-AGIS Cooperation Fund (No. SZYJY2023010).