Generalization Bounds for Adversarial Metric Learning

1 Introduction

The robustness of metric learning against adversarial perturbations has attracted increasing attention in the machine learning literature, where abundant adversarial algorithms have been proposed from various application motivations, e.g., [Huang et al., 2019; Bouniot et al., 2020; Liu et al., 2022]. Despite the previous adversarial metric learning enjoys the adversarial robustness [Madry et al., 2018; Kurakin et al., 2018; Carlini and Wagner, 2017] empirically, its generalization guarantee is touched scarcely in theory. In this paper, our goal is to fill this theoretical gap and provide the sharper high-probability generalization bounds of adversarial metric learning from the lens of statistical learning theory [Vapnik, 1999; Mohri et al., 2018].

Although theoretical foundations of metric learning have been well understood in [Huai et al., 2019; Lei et al., 2020; Ye et al., 2019], there are two-fold challenges in establishing generalization analysis for adversarial counterparts. The first one is caused by the joint perturbations on sample pairs [Huai et al., 2022], which is more complicated than the case of the single-sample perturbation [Yin et al., 2019; Xing et al., 2021; Mustafa et al., 2022]. The other arises from the nonsmoothness and non-differentiable optimization objective associated with the adversarial loss function [Xing et al., 2021; Xiao et al., 2022], which leads to the standard analysis techniques (e.g., [Cao et al., 2016]) inapplicable.

∗Corresponding author.

To surmount the above challenges, we introduce the ℓ∞ covering number [Reeve and Kaban, 2020; Mustafa et al., 2022] to measure the complexity of function space with pairwise perturbations and employ a general loss class to approximate the adversarial loss class on training samples to tackle the non-smoothness problem. In addition to providing generalization guarantees for adversarial metric learning, we also validate our theoretical findings through experimental analysis on real-world datasets. In summary, the main contributions of this paper are listed as follows:

• We establish the high-probability generalization bounds with order O(n- 12 ) for adversarial metric learning with pairwise perturbations, where n is the sample size. Indeed, our high probability bounds are beneficial to understand the robustness of optimization algorithms [Bousquet et al., 2020; Klochkov and Zhivotovskiy, 2021; Li and Liu, 2021] and are different from the existing bounds in expectation [Xing et al., 2021; Farnia and Ozdaglar, 2021; Xiao et al., 2022]. These developed learning bounds are valid for general adversarial perturbations measured by ℓr-norm (r ≥ 1), and adapt to linear metric learning models and deep metric learning models simultaneously. To the best of our knowledge, this is the first-ever-known generalization bounds for metric learning with pairwise perturbations.
• Under the self-bounding Lipschitz assumption [Reeve and Kaban, 2020] of loss function, we provide the sharper generalization bound with the order O(n-1 ) by developing the concentration estimation technique associated with the local Rademacher complexity [Bartlett et al., 2005]. As a by-product, the current generalization bounds with respect to the non-adversarial metric learning assure faster rates than the previous generalization analysis in [Huai et al., 2019; Lei et al., 2020].

2 RelatedWork

Adversarial Metric Learning. Adversarial metric learning plays a vital role in applications ranging from person re-identification [Dai et al., 2018; Bouniot et al., 2020; Liu et al., 2022] to zero-shot learning [Chen and Deng, 2019; Huang et al., 2019] and cross-modal retrieval [Xu et al., 2019]. Since metric learning methods learn on the original samples are limited in their capacity to distinguish ambiguous samples, adversarial learning methods are proposed to facilitate robust metric learning (see Appendix A). Although adversarial metric learning has shown empirical effectiveness, theoretical aspects of adversarial robustness has not been exhaustively studied.

Adversarial Generalization. The nonsmoothness and nondifferentiability with respect to adversarial loss are central difficulties in the generalization analysis of adversarial learning. To overcome these obstacles, Xing et al. (2021) propose a noise injection method to avoid non-differentiability, and establish stability upper bound and lower bound for a generic adversarial training algorithm. Xiao et al. (2022) tackle the non-smooth problem by considering the η-approximate smoothness on adversarial loss. Based on this, they derive stability-based generalization bounds for stochastic gradient descent on the general class, which covers the adversarial loss. Tu et al. (2019) fit the adversarial learning problem into the minimax framework by introducing a transport map between distributions. They derive a new risk bound for the minimax problem through the lens of covering numbers under the Lipschitz assumption. Mo et al. (2022) extend the prior work of Tu et al. (2019) to pairwise learning and establish the generalization bounds for adversarial bipartite ranking. Yin et al. (2019) and Khim et al. (2018) derive a surrogate upper bound on the adversarial loss, and then show upper bounds for the adversarial Rademacher complexity of the surrogate. All the above generalization analysis are limited to adversarial learning with pointwise perturbation. To the best of our knowledge, there is no the related generalization analysis for adversarial learning with pairwise perturbation. This paper try to fill this gap. Table 1 summarizes the related work on adversarial learning.

3 Preliminaries

This section introduces the main notations used in this paper, the necessary backgrounds on adversarial metric learning [Wang et al., 2020; Liu et al., 2022; Yang et al., 2021], and some theoretical techniques and structural results used for the generalization analysis.

3.1 Notations

We denote vectors as lowercase letters (e.g., x) and matrices as uppercase letters (e.g., X). We write ∥w∥p to denote the ℓp-norm of a vector w ∈ Rn . The dual norm of w is denoted by a star (i.e., ∥w∥p∗ ). For a matrix W ∈ Rn×n with columns Wi, i ∈ [n], the matrix (p, q)-norm is defined by ∥W∥p,q = ∥(∥W1∥p, . . . , ∥Wn∥p)∥q.

3.2 Adversarial Metric Learning

Let S = {(xi, yi)}ni=1 be a set of training samples drawn according to an unknown distribution P, where xi ∈ Rd is the d dimensional feature vector and yi ∈ R is the class label. The d × n input feature matrix is denoted by X = (xi : i ∈ [n]). Given a mapping f : Rd → Rd′ , which maps the d-dimensional input into an embedding space with d′ - dimension, then the distance between samples xi and xj is measured by

The target of metric learning is to learn an adequate f such that reflects the similarity between sample pairs [Wang et al., 2020; Huai et al., 2022]. The widely adopted method of seeking such f is to minimize the following empirical risk over the given training samples

where ℓ : R → R+ is a given loss function such as the hinge loss function, and τ(yi, yj) ∈ {-1, 1} indicates whether two samples are affiliated to the same class, i.e., τ(yi, yj) = 1 if yi = yj , and τ (yi, yj ) = -1 otherwise.

However, in the presence of adversaries, there will be imperceptible perturbations on the input samples that lead to maximizaing empirical risk (2). Throughout this paper, we assume that the perturbation θ is adversarially chosen in the ℓr-ball B(ε) ⊆ Rd of radius ε, for an arbitrary r ≥ 1. Given a sample pair (xi, yi), (xj, yj) and a learned mapping f, the adversary selects valid perturbations θ∗ i and θ∗ j by [Huai et al., 2022]

and the adversarial loss ℓadv((xi, yi), (xj, yj); f) of f at (xi, yi), (xj , yj ) can be written as

We then have the following adversarial empirical risk ˜ En(f )

and the adversarial expected risk ˜ E (f )

The adversarial empirical risk ˜ En(f ) measures the ability of f to place similar samples nearby and separate dissimilar samples on the training samples with adversarial perturbations. The adversarial expected risk ˜ E(f) measures how well f generalizes to unseen adversarial samples. In this paper, we are interested in the difference between ˜ En(f) and ˜ E(f). Our main tool for bounding the generalization error for adversarial metric learning (i.e., ˜ E(f) - ˜ En(f)) is the ℓ∞-covering number defined below.

Definition 1 (ℓ∞-covering number). Let υ > 0 and let (A, ∥· ∥∞) be a metric space. We say that C ⊆ A is an (υ,∥ · ∥∞)- covering of A if

Then, the ℓ∞-covering number of A is the minimum cardinality of any subset covers A at scale υ, denoted as N∞(υ, A).

As a special case of Zhang et al. (2002), Definition 1 generally characterizes the complexity of the function space measured by the infinite norm [Reeve and Kaban, 2020; Mustafa et al., 2022].

Let the mapping f be selected from the hypothesis class F := {x ↦→ fW(x) : x ∈ Rd ,W ∈ Rd×d′ }. The class of adversarial loss functions (3) is written as

We have the following relationship between the generalization error (i.e., ˜ E(f) - ˜ En(f)) and ℓ∞-covering number of adversarial loss class Ladv on the training sample S (i.e., N∞(Ladv, υ, S)), which extends the previous results of Bartlett et al. (2017) to adversarial learning.

Lemma 1. Let Ladv be the adversarial loss class defined in (4) and bounded by 1. Then, for any δ ∈ (0, 1), with probability at least 1 - δ over a sample S of size n, the following holds for all f ∈ F

Lemma 1 allows us to control the generalization error by bounding the ℓ∞-covering number of the adversarial loss class on training samples. However, deriving an upper bound on N∞(Ladv, υ, S) is intractable due to the outer maximization of loss functions in class Ladv and the joint action of pairwise perturbations θi, θj . Our approach is to approximate the loss class Ladv on sample S by the following class ˜ Ladv

and incorporate perturbations θi, θj into the argument. Based on this, we reduce the problem of measuring the complexity of the adversarial loss class on training samples to measuring the complexity of a general loss class. Some necessary Lipschitz conditions are introduced for our theoretical analysis.

Definition 2. Let ∥ · ∥ denote a norm metric, and ξ, ζ ≥ 0. For a loss function ℓ : F → R and a distance function Df : Rd × Rd → R parametrized by f ∈ F,

1) the loss function ℓ is ξ-Lipschitz if, for ∀f, f ′ ∈ F

2) the distance function Df is the Muti-variate Lipschitz continuity if, for ∀θi, θj, θ′i , θ′j ∈ Rd

The Lipschitzness on the loss function in Definition 2 is a mild condition, which is satisfied by some common losses, e.g., the hinge loss and logistic loss [Yin et al., 2019; Tu et al., 2019; Lei et al., 2020]. By utilizing this Lipschitzness and the notion of Multi-variate Lipschitz continuity [Zantedeschi et al., 2016], we have the Lipschitzness on the functions θi, θj ↦→ ℓ(τ(yi, yj)(1 - Df(xi + θi, xj + θj))) for f ∈ F, which is necessary and fulfilled by most attacks [Madry et al., 2018; Awasthi et al., 2021].

We now present our first main result as follows.

Theorem 1. Let θi, θj ↦→ ℓ(τ(yi, yj)(1 -Df(xi + θi, xj + θj))) be the Lipschitzness with constant L. Let CB(3υ/4L) be a 3υ/4L-cover of B(ε), and define the adversarial sample set

Then, we have

Detailed proofs are contained in Appendix C.2. Theorem 1 illustrates that the ℓ∞ covering number of adversarial loss class Ladv on set S can be bounded by the ℓ∞ covering number of class ˜ Ladv on adversarial set ˜ S, which extends the Lemma 4.4 of Mustafa, Lei and Kloft (2022) for adversarial pointwise learning to adversarial pairwise learning. It will be served to derive high-probability generalization bounds of adversarial metric learning.

4 The Generalization Bounds for Adversarial Metric Learning

In this section, we provide a sharp characterization of the generalization for two commonly-used adversarial metric learning models: the linear and deep metric learning models. The adversarial perturbation is measured in ℓr-norm. Moreover, we establish fast generalization bounds for adversarial metric learning through the local Rademacher complexity under the smooth Lipschitz assumption on loss functions.

4.1 Linear Metirc LearningModel

We consider the following linear hypothesis class:

For any linear mapping f ∈ F, the distance metric function is defined by

The Lipschitz constant of the function θi, θj ↦→ ℓ(τ(yi, yj) (1-Df (xi +θi, xj +θj ))) required in Theorem 1 is provided in the following lemma.

Lemma 2. Let Df be the linear distance function defined in (6). Then, for any sample pair (xi, yi) and (xj, yj), the function θi, θj ↦→ ℓ(τ(yi, yj)(1 - Df(xi + θi, xj + θj))) is 4ξΛ2Ψ-Lipschitz, where 4Λ2Ψ is the Multi-variate Lipschitz constant of the function θi, θj ↦→ Df (xi + θi, xj + θj), and Ψ is max(1, d1- 1p - 1 r )(∥X∥r,∞ + ε).

The proof is provided in Appendix.D.1. Based on the Lipschitzness of the adversarial loss function in Lemma 2, we obtain an upper bound on the covering number of the loss class ˜ Ladv on the sample ˜ S in the theorem below.

Theorem 2. With the notation in Lemma 2. Let ˜ Ladv be defined in (5) and ˜ S be defined in Theorem 1. Then, for υ > 0, we have

where

The detailed proof is contained in Appendix D.1. Based on Theorem 2 and Lemma 1, we establish the following highprobability generalization bound.

Theorem 3. With the notation above. For any fixed ξ > 0 and all f ∈ F, with probability at least 1 - δ, we have

where ̂Ψ = max(1, d1- 1p - 1 r )(∥X∥r,∞ + ε)2 and C is a constant.

The proof of this theorem is provided in Appendix D.2.

Remark 1. The generalization bound in Therorem 3 suffers from additional dimension dependent terms as compared to its non-adversarial counterpart. The first d1- 1p - 1 r dependence in ̂Ψ is due to the mismatch between the norm on the input x and the norm in the ball B(ε). Indeed, we have used the inequality ∥xi + θi∥p∗ ≤ max(1, d1- 1p - 1 r )∥xi + θi∥r in

Awasthi et al. (2021), where 1 - 1/p = 1/p∗ . If 1p + 1r ≥ 1,

̂Ψ is dimension independent, which implies that one should choose a p-norm regularizer on W (i.e., the weight matrix), where p ∈ [1, r∗ ]. The second √d dependence in square root of the third term on the right side of Therorem 3, is attributed to the complexity of the perturbation ball B(ε). For example, if B(ε) is contained in a low dimensional space d′ < d, the dependence is reduced to O(√d′ ). This motivates the mapping f to project the input x ∈ Rd into a low-dimensional subspace to reduce the effective dimensionality of adversarial perturbations.

Remark 2. Theorem 3 is a high-probability generalization bound for adversarial metric learning in the linear case, motivated by the recent analyses in the adversarial pointwise learning (Awasthi et al. 2021; Mustafa, Lei and Kloft 2022). In contrast with prior work of Mustafa et al. (2022) that studies ℓ∞-norm perturbations, we consider the general case where the perturbations are measured in ℓr-norm. Moreover, our theoretical analysis is novel since it is the first touch for adversarial pairwise learning with pairwise perturbations than existing work [Yin et al., 2019; Mo et al., 2022; Mustafa et al., 2022].

Remark 3. Setting ε = 0, we obtain a standard risk bound for linear metric learning in non-adversarial case; see (7). Although the bound (7) with order O(1/√n) is similar to the generalization bounds in Cao at al. (2016), Ye et al. (2019), and Let et al. (2020), our result applies to a wider range of loss functions such as hinge loss and logistic loss.

4.2 DeepMetirc LearningModel

Let the mapping f be a L-layer neural network parametrized by the weights W = {W l ∈ Rhl×hl-1 }Ll=1 , where hl is the number of neurons in the l-th layer of the network and h0 = d. Given the input sample xi ∈ Rd , the output of the final layer in the network can be written as

where ρ(·) denotes the non-linear 1-Lipschitz activation function. We consider norm-bounded networks with the following hypothesis class

where ∥ · ∥σ represents spectral norm and ∥ · ∥F denotes the Frobenius norm.

As with the linear case, we first establish the Lipschitzness of the function θi, θj ↦→ ℓ(τ (yi, yj)(1-Df (xi+θi, xj+θj))). The results are summarized in the following lemma.

Lemma 3. Let f ∈ F be the neural network defined in (8) and Df be the distance metric function defined as (1). For all (xi, yi), (xj, yj) and f ∈ F, the function ℓ(τ(yi, yj)(1 - Df(xi + θi, xj + θj))) is 4ξ ∏Ll=1 s2l Ψ-Lipschitz in θi, θj, where 4 ∏Ll=1 s2l Ψ is the Multi-variate Lipschitz constant of the function θi, θj ↦→ Df(xi + θi, xj + θj), and Ψ is max(1, d1- 1p - 1 r )(∥X∥r,∞ + ε).

The proof is given in Appendix E. With this lemma, we establish the following upper bound on the ℓ∞-covering number of the class ˜ Ladv in nonlinear cases.

Theorem 4. With the notation in Lemma 3. Let ˜ Ladv be defined in (5) and ˜ S be defined in Theorem 1. Then, for ϵ > 0, we have

where

The proof is given in Appendix E. By combining Theorem 4 with Lemma 1, we obtain the following sharp bound with high probability.

Theorem 5. With the notation in Theorem 4. For any fixed ξ > 0 and all f ∈ F, with probability at least 1 - δ, we have

where ˜Llog is defined by

Remark 4. Similar to the linear case, the bound in Theorem 5 has max(1, d1- 1p - 1 r ) and √d dependencies. The first is in ̂Ψ, which arises from the mismatch of norms and can be avoided by simply picking the appropriate norm regularization (ℓp) on the weight matrices (W) as discussed above. The second √d dependence in ˜Llog. As discussed in the linear case, a projection on a low-dimensional represent space can help alleviate such dependence incurred by the complexity of the adversarial perturbation ball B(ε).

Remark 5. Theorem 5 provides generalization guarantees for adversarial metric learning in nonlinear case. The bounds in Yin et al. (2019) and Awasthi et al. (2021) apply only to a one-hidden-layer neural network. This contrasts with our bound, which applies to multi-layer networks. While the bounds in Khim and Loh (2018) and Mustafa, Lei and Klof (2022) apply to multi-layer networks, they are only applicable to pointwise learning and the single-sample perturbation case.

Remark 6. Similar to the linear case, Theorem 5 can recover the non-adversarial generalization bound (9) by setting ε = 0. The bound (9) is of the order O(√d log(ˆh)/√n), where ˆh is the width of the hidden layer. The generalization bound in Huai et al. (2019) grows as O(√ˆh), while ours is O(log(ˆh)).

4.3 Optimistic Bounds

Optimistic bounds have been studied in [Srebro et al., 2010; Reeve and Kaban, 2020], where they have resulted in fastrate generalization bounds for smooth losses under low-noise conditions. We aim to extend these approaches to adversarial metric learning. Our results are based on the local Rademacher complexity [Bartlett et al., 2005] with respect to sample pairs [Cao et al., 2016].

Definition 3 (Local Rademacher complexity). Let H : X × X → R be a hypothesis class. Given a sample S = {(x1, y1), . . . , (xn, yn)} of size n, The local Rademacher complexity is the worst-case Rademacher complexity of H on S of cardinality n, that is, Rn(H) := sup|S|≤nRS(H), where RS(H) is the empirical Rademacher complexity with respect to sample pairs defined by

where σ1, . . . , σn are i.i.d Rademacher random variables with P{σi = 1} = P{σi = -1} = 1 2 .

Let ˜D := {((xi, θi), yi), ((xj , θj ), yj ) ↦→ Df (xi +θi, xj + θj) : f ∈ F}. The local class ˜D|γ = {((xi, θi), yi), ((xj, θj) , yj) ↦→ Df(xi + θi, xj + θj) : f ∈ F, ˜ En(f) ≤ γ} ⊂ ˜D is defined as the set of function Df ∈ ˜D with the adversarial empirical error at most γ. Similarly, the local adversarial loss class is defined as Ladv|γ := {(xi, yi), (xj, yj) ↦→ maxθi,θj∈B(ε) ℓ(τ(yi, yj)(1 -Df(xi + θi, xj + θj))) : f ∈ F, ˜ En(f ) ≤ γ}.

We introduce the self-bounding Lipschitz [Reeve and Kaban, 2020] for the loss function, which assumes that the loss function is smooth. Srebro et al. (2010) show that such smoothness condition can give rise to an optimistic bound having a fast rate O(n-1 ) in the realisable case. Under smoothness assumption, we derive an upper bound on the local Rademacher complexity of adversarial loss class, which serves as a key step in developing fast-rate bounds.

Lemma 4. Let Ladv|γ and ˜D be defined as above. Suppose that for any f ∈ F, ∥f∥∞ ≤ B, and the loss ℓ is (λ, η)- self-bounding Lipschitz bounded by b. Further let θi, θj ↦→ ℓ(τ(yi, yj)(1 - Df(xi + θi, xj + θj))) be ∥ · ∥-Lipschitz with constant L and ˜ S = {((xi, θi), yi) : i ∈ [n], θi ∈ CB( 3υ λ(2γ)η 8L )}. Suppose further that n ↦→ √nR| ˜ S| ( ˜D) is non-decreasing. Then, we have

where Ω grows at the order of

The detailed proof is provided in Appendix F.1. Based on Lemma 4 and the sub-root property in [Bartlett et al., 2005], fast generalization bounds adversarial metric learning with smooth losses are given in the following theorem.

Theorem 6. With the above notation and assumption of Lemma 4, for all f ∈ F, with probability at least 1 - δ, we have

where K = 4b n (log(1/δ) + log(log(n))).

Remark 7. The convergence rate of the generalization bound in Theorem 6 grows as R2| ˜ S| ( ˜D). For the majority of function classes (e.g., linear models [Yin et al., 2019]), the Rademacher complexity is at least O(n-1/2 ). The second term would then grow as O(n-1 ), while the fourth term would grow at the usual O(n-1/2 ) rate. However, if ˜ En(f ) = 0, the fourth term vanishes, thus achieving a fast rate of convergence at least O(n-1 ).

Remark 8. We establish the fast-rate generalization bound with high probability for metric learning in non-adversarial case,

where D is the class of distance function and ˆΩ grows at the order O(log3/2 ( n Rn(D) ) - log3/2 ( B2 nλ b1-η )). It extends the previous optimistic results [Srebro et al., 2010] of pointwise learning to pairwise learning. In contrast with the bounds of order O(n-1/2 ) [Cao et al., 2016; Huai et al., 2019; Lei et al., 2020], this is the improved result.

5 Experiments

5.1 Experimental Setup

Datasets. We adopt the following real-world datasets for experiments: the Wine 1 , Spambase 2 , MNIST 3 and CIFAR10 4 datasets. Table 2 provides details of dimension (d) and size (n). Note that the input for adversarial metric learning models is a set of sample pairs rather than single samples. For the original dataset with single samples, we make oneby-one matching to form n(n - 1) sample pairs, and then randomly select n pairs to construct the new dataset. The pair composed of samples with the same category is assigned to label 1, and the other is assigned to 0. We randomly split the new dataset into training, validation and test sets with a ratio of 6 : 2 : 2, where the validation set is used for early stopping to prevent overfitting of model.

Model and Attack Settings. We use one-layer neural networks without nonlinear activation as the linear model. Denote the number of units in the output layer by d′ . We utilize five-layer feed-forward neural networks with ReLU activation [Hahnloser et al., 2000] as the non-linear model, where the number of the units in each layer is (512, 256, 128, 64, d′ ). All models trained with the Adam optimizer. The learning rates of the linear model and the nonlinear model are set as 1e - 2 and 1e - 3, respectively.

We apply ℓ∞ PGD attack [Madry et al., 2018] adversarial training to minimize the following objective function

where ℓ(·) is cross entropy loss, fW is the mapping function parameterized by W = {W l ∈ Rhl×hl-1 }Ll=1 , where hl is the number of neurons in the l-th layer of the network (especially, h0 = d, hL = d′ ), and λ ≥ 0 is the regularization parameter. Then, we run PGD attack to check the generalization error. Similar to Yin et al. (2019), the generalization error is approximately calculated by

During the training and test phases, the adversarial samples are generated by PGD algorithm with step size ε/5, where ε is the maximum magnitude of the allowed perturbations that varies in {0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4}. Overall, each experiment is independently repeated 10 times, and average generalization error with standard deviation of adversarial metric learning models are reported.

1 https://archive.ics.uci.edu/ml/datasets/wine/

2 https://archive.ics.uci.edu/ml/datasets/spambase/

3 http://yann.lecun.com/exdb/mnist/

4 https://www.kaggle.com/competitions/cifar-10/data

5.2 Experiment Results

Theorem 3 and 5 suggest that projecting the input feature to low-dimensional output and applying appropriate regularization to the weights of models, can reduce the generalization error of adversarial metric learning models. Here, we conduct linear and non-linear experiments to validate these theoretical findings.

The Effect of the Output Dimension. To investigate the effect of the output dimension on the generalization performance, we train models with different dimensional outputs. In the linear case, we consider three cases where the output dimension (i.e., d′ ) is set as d, ⌈d/2⌉ and ⌈d/3⌉, respectively. For the nonlinear case, the output dimension of the final layer of neural networks is set as 512, 128 and 32, respectively. Figure 1 plots the generalization errors (10) of linear and nonlinear models on the adopted datasets. As we can see, the fewer the output features, the smaller the generalization error, which suggests that projecting input into the low-dimension feature space can potentially reduce the generalization gap of adversarial metric learning models.

The Effect of Regularization. We evaluate the effect of the weight parameters on the generalization of adversarial metric learning models by comparing the performance of the models with and without regularization. We employ linear and nonlinear models with output dimensions d and 32, respectively, and apply the L1 regularization to W 1 (i.e., the weights of the first layer of models). The regularization parameter λ is set as 0, 0.01 and 0.02. Note that λ = 0 indicates the model trained without regularization. The generalization errors (10)

Figure 2: The generalization error (10) (mean and standard deviation over 10 runs) for adversarial metric learning models with (λ ̸= 0) and without (λ = 0) L1 regularization. λ denotes regularization parameter, and ε denotes the perturbation bound. Subfigures (a) and (b) present results for linear models. Subfigures (c) and (d) present results for nonlinear models on adopted datasets.

of linear and nonlinear models on the adopted datasets are presented in Figure 2. We can see that generalization gap of the model with regularization is smaller than that of the model without regularization, thus we conclude that applying L1-norm regularization to adversarial metric learning models is helpful for reducing generalization error.

6 Conclusions

This paper presents a detailed study of the generalization properties of adversarial metric learning under ℓr adversarial perturbations. We derive the high-probability generalization bounds for adversarial metric learning with pairwise perturbations by developing the uniform convergence analysis techniques. Our results apply to both linear and deep metric learning models, as well as to various loss functions. To our knowledge, this is the first generalization analysis for adversarial pairwise learning with pairwise perturbations. We further extended our analysis to the case of smooth losses, and establish a fast generalization bound at a rate of O(n-1 ) by the local Rademacher complexity. In future work, we will investigate the generalization properties of models under nonadditive attacks.

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grant No. 12071166, the Fundamental Research Funds for the Central Universities of China under Grant Nos. 2662021JC008, 2662022XXYJ005, and HZAUAGIS Cooperation Fund No. SZYJY2023010.

1

1