Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin
Kaiwen Wu Yaoliang Yu
cs.LG stat.ML

Trade-off between Minimum and Average Margin]Understanding Adversarial Robustness: The Trade-off between Minimum and Average Margin


University of Waterloo
kaiwen.wu@uwaterloo.ca


University of Waterloo
yaoliang.yu@uwaterloo.ca



Deep models, while being extremely versatile and accurate, are vulnerable to adversarial attacks: slight perturbations that are imperceptible to humans can completely flip the prediction of deep models. Many attack and defense mechanisms have been proposed, although a satisfying solution still largely remains elusive. In this work, we give strong evidence that during training, deep models maximize the minimum margin in order to achieve high accuracy, but at the same time decrease the average margin hence hurting robustness. Our empirical results highlight an intrinsic trade-off between accuracy and robustness for current deep model training. To further address this issue, we propose a new regularizer to explicitly promote average margin, and we verify through extensive experiments that it does lead to better robustness. Our regularized objective remains Fisher-consistent, hence asymptotically can still recover the Bayes optimal classifier. 


[
    Yaoliang Yu
    December 30, 2023
=====================










§ INTRODUCTION



Traditionally, training more accurate classifiers has been much of the focus of machine learning research. More recently, as machine learning models start to penetrate into safety-critical applications, their robustness against random or even adversarial manipulations has drawn a lot of attention. The work of SzegedyZSBEGF14 demonstrated surprisingly that it is possible to craft very minimal changes to an input image that (a) is clearly not perceivable by humans but (b) can completely flip the predictions of state-of-the-art deep models. Such detrimental perturbations are called adversarial examples and have raised serious concerns on the safety of deep models.


Since the work of <cit.>, a sequence of works have proposed new attack algorithms to generate adversarial examples <cit.>, as well as defensive techniques <cit.> to train more robust models. 



There even appears to be an arm race between attack and defense techniques: new defense techniques are shown nonrobust under stronger attacks shortly after being proposed AthalyeCW18. Thus, a line of research focusing on provable certification of (non)robustness has emerged. 
For example, one can use the Lipschitz constant of the network to provide a lower bound on the amount of needed adversarial perturbations [][]HeinAndriushchenko17, WengZCYSGHD18, zhang2018efficient, WengZCSHBDD18. More recently, certification methods base on mixed integer programming (MIP) <cit.> have been proposed to provide more accurate lower bounds. However, due to the NP-hardness of MIP, convex relaxations wong2018scaling, WongKolter18, raghunathan2018semidefinite, raghunathan2018certified, SinghGMPV18,GowalDSBQUAMK18 have been popular for scaling these provable certification methods to larger models. 




	







In this paper, we study adversarial robustness from a margin perspective. The notion of margin distribution  dates back to <cit.>, which provide generalization bounds based on the margin distribution. Later on, algorithms that control margin distribution for better generalization performance have been proposed <cit.>. In this work, however, we connect the notion of margin with adversarial robustness, and we reveal a surprising trade-off between minimum and average margin in standard deep model training. In particular, the recent result in <cit.> implies that on a linearly separable dataset a linear classifier trained with (stochastic) gradient descent converges to the SVM solution, under mild conditions on the loss function. Since SVM explicitly maximizes the minimum margin, any linear classifier would eventually achieve the same. However, our experiments reveal that the average margin is greatly reduced during training. In other words, models maximize the minimum margin at the expense of reducing the average margin hence becoming more susceptible to adversarial attacks. This surprising phenomenon was also confirmed on linearly nonseparable datasets and a variety of nonlinear classifiers. Interestingly, a few defense methods based on margin maximization have been proposed <cit.>, which through our work, should be understood as maximizing the average margin, as opposed to the minimum margin.

To overcome the trade-off between minimum margin and average margin in standard training,


we propose the standard training objective with an average-margin promoting regularizer. We prove that the regularized objective remains Fisher consistent, if the original loss is so. This means as sample size grows, the classifier obtained through optimizing our regularized objective still approaches the Bayes optimal classifier, while potentially is much more robust than standard training. Our regularizer can be easily extended to multiclass and nonlinear classifiers. We confirm the latter point through extensive experiments on two standard datasets and a variety of different models and settings. 

To summarize, we make the following contributions in this work:


	
  * We reveal the intrinsic trade-off between minimum margin and average margin;
	
  * We propose a new regularizer that explicitly promotes average margin and retains Fisher consistency;
	
  * We perform extensive experiments to confirm the effectiveness of our new regularizer.










§ BACKGROUND




We consider the multi-category classification problem. Given a set of n training instances {(_i, y_i) ∈× [c]: i=1, …, n}, where the feature domain ⊆^d and [c] := {1, …, c} with c ≥ 2 the number of categories, we are interested in finding a classifier h: → [c], or equivalently, a set  partition _1, …, _c of the domain  such that ∪_k _k = and for all k l, _k ∩_l = ∅. Often in practice, the classifier h is learned through a vector-valued function : →^c, with the argmax prediction rule employed to predict the label ŷ of a test sample  as follows:
	
    ŷ = ŷ() := _k=1,…, c f_k(),     
    	f_k: →,      = (f_1, …, f_c).

	As is well-known, the two representations of a classifier, either through a set partition {_k} or through a vector-valued function , are equivalent. 
	We will use both representations interchangeably.
	
	
	In their seminal work, SzegedyZSBEGF14 defined the robustness of a classifier  on a test sample  as the minimum perturbation needed to flip its prediction ((<ref>)):
	
    () = inf{: +∈,  ŷ(+) ŷ()},

	where · is an abstract norm (the familiar ℓ_p norm) for measuring the amount of perturbation. This notion of robustness turns out to have a very intuitive geometric meaning, as we detail below.
We remind that we also represent a classifier  as a set partition {_1, …, _c}.


For any ∈, define () ∈ [c] so that ∈_(), () is the predicted label of our classifer. 
We define the distance from a point ∈ to a set ⊆ as:

    (, ) := inf{ - : ∈}.
 

Recall that the notations , ,  and  denote the closure, interior, complement and the boundary[Of course, := ∖.] of a point set , respectively. We remark that for any set :


    (, ) = 
    0,    ∈
    (, ),    
    ,

which will be important when we aim to optimize some function of the distance.


Note that (, _ŷ) is the distance to the decision boundary, which captures the definition  (<ref>) exactly:

propositiongeometric

Let : →^c be a vector-valued function that, if augmented with the argmax prediction rule (<ref>), leads to the following sets (classifier): for all k∈[c], 
 
    _k := {∈: f_k() = max_l=1,…,c f_l() },

where we break ties arbitrarily. Then the robustness definition in <Ref> equals to (, _ŷ).












We are now ready to define the individual margin of a sample pair (, y) the classifier {_k} as:






    (, y) := (, y; {_k}) := (ŷ(), y) ·(, _ŷ),

where we define (ŷ, y) = 1 if ŷ = y and (ŷ, y) = -1 otherwise. Namely, when predicting correctly, (, y) is the distance to the decision boundary, the minimum perturbation needed to change the prediction; whereas when predicting wrongly, it is the negation of the distance to the decision boundary, the minimum perturbation needed to correct the prediction. We then define





  * minimum margin: min_1 ≤ i ≤ n(_i, y_i)


  * average margin: 1/n∑_i = 1^n | (_i, y_i) |, simply the average distance to the decision boundary.


Although the definition (<ref>) applies for any norm, we will focus on l_2 margin later, as some current results of implicit minimum margin maximization <cit.> only holds for l_2 norm, which will be discussed in <ref>. From now on, we use · to denote the Euclidean norm.


























01



§ AN AXIOMATIC DEFINITION OF ROBUSTNESS


Having defined the margin of a classifier {_k} any individual sample , we now  axiomatically formalize the notion of (adversarial) robustness of a classifier a population. Our definition unifies and extends the existing ones, and provides a common framework for future comparisons in this field. 


Let (, Y) be a pair of random variables following some distribution , then _l() is a random quantity as well. While it is common to simply average the individual margins over the distribution , we propose the following axiomatic definition that is more flexible. 

First, we introduce an individual robustness measure : ^c × [c] → such that ((), y) aggregates the individual margins. A simple choice that has been used (implicitly) in previous works is 

    ((), y) = max{_y(), 0 },

, when predicting correctly we gain a reward  proportional to the minimum perturbation needed to change the correct prediction while we gain 0 reward when predicting incorrectly.
However, in many applications misclassifying an instance  with true label y into different classes l may result in totally different consequences. For instance, classifying a yellow light as red is much less severe than classifying a red light as green. This asymmetry in misclassifications can be reflected in an appropriately chosen individual robustness measure . 

Second, we introduce a population robustness measure ϱ that aggregates the individual robustness over the population. 
Let  denote the space of  real-valued random variables and consider the functional ϱ : →∪{∞} that yields the population robustness measure:

    ({_k}; ):= ϱ(((), Y)),  (, Y)∼,





It is natural to require the following axioms on the robustness measure ϱ:


  * (L)aw invariant: If U and V follow the same distribution, then ϱ(U) = ϱ(V).

  * (M)onotonic: If U ≥ V, then ϱ(U) ≥ϱ(V).

  * (N)ormalized: ϱ(0) = 0.

These properties are self-evident; any reasonable robustness measure should satisfy them.
Additionally, in some applications we might also be interested in forcing some extra ones, such as


  * (C)onvex: For all 0≤λ≤ 1, ϱ(λ U + (1-λ)V) ≤λϱ(U) + (1-λ)ϱ(V),

  * (T)ranslation equivariant: For any real value r ≥ 0 and random variable U, ϱ(U + r) = ϱ(U) + r.

The convex property basically means the population robustness measure  is smaller when  follows a mixture distribution than when  follows each of the component distributions. Translation equivariance  means if we (uniformly) increase each individual reward ((), y) then we increase the population robustness measure by the same amount. 

With all of the above properties we call ϱ a convex robustness measure, which corresponds to essentially the convex risk measure in finance [Chapter 4]FollmerSchied16, see also the upper expectation in [Chapter 10]HuberRonchetti09.






We mention a few examples of population robustness measures: 

    _α   := inf{ t: ( ((), Y) ≤ t ) ≥α}
    _α   := ( ((), Y) | ((), Y) ≤_α )
       = 1/α∫_0^α_γγ
       := ∫_0^1 _αμ(α) = ∫_0^1 _γ· s(γ)γ,

where μ is a probability distribution and s is a density function. Clearly, _α and _α are special cases of the Spectral Robustness Measure , with s(γ) = δ_α(γ) and s(γ) = 1α_[0,α](γ), respectively. Note that _α is the α-quantile, , the robustness value t such that 100α% of the data distribution have robustness measure smaller than t.  is a convex robustness measure iff the weighting function s is decreasing, , we put more weights on smaller robustness values (since these are easier to be adversarially perturbed). In particular,  is a convex robustness measure while  is not. Another popular choice is to set s ≡ 1, in which case we recover the average robustness measure [ ((), Y) ], which has been predominantly used so far in the field of adversarial machine learning. We argue that in certain applications it may be crucial to use a tailored weighting function s, based on domain knowledge. We note that variants of _α and _α (where _α  instead of α is fixed) have been used in BastaniILVNC16  to measure robustness. Notice that another measure, the robust accuracy [ min_δ≤ϵ[Ŷ( + δ) = Y]] used in <cit.>, is also included in our framework as [ () ≥ϵ ], although it is not convex.
 
 
 








§ MINIMUM AVERAGE MARGIN: A CASE STUDY





In this section, we study a simple example to demonstrate the trade-off between minimum and average margin. 
In statistical learning theory, it is well-known that we can bound the generalization error of a classifier using empirical margins <cit.>. In particular, the celebrated support vector machines (SVM) explicitly maximize the minimum margin (on any linearly separable dataset). In adversarial learning, however, we argue that average margin is more indicative of the robustness of a classifier. 















Our main observations in this section are: (a) Current machine learning models, especially when they become deep and powerful, implicitly maximize the minimum margin to achieve high accuracy; (b) there appears to be an inherent trade-off between minimum margin and average margin. In particular, by maximizing the minimum margin, the model also (unconsciously) minimizes the average margin, hence becomes susceptible to adversarial attacks. Note that we do not claim minimum margin always contradicts average margin. It does not, as can be easily shown through carefully constructed toy datasets (a hightly symmetric dataset). Our empirical observation is that there does appear to be some tension between the two notions of margin on real datasets.

To begin with, we first demonstrate that minimum margin is maximized during standard training. In fact, this can be formally established through the  implicit bias of optimization algorithms, such as (stochastic) gradient descent which is ubiquitously used in training deep models. 
Recall that on a (linearly) separable dataset, (hard-margin) linear SVM explicitly maximizes the minimum margin. The following result, due to <cit.>, confirms the same for most models currently used in machine learning, including logistic regression.













For almost all linearly separable binary datasets and any smooth decreasing loss with an exponential tail, gradient descent with small constant step size and any starting point _0 converges to  the (unique) solution  of hard-margin SVM, 


lim_t →∞_t/_t = /.


Note that the margin of a linear classifier f() = ^⊤, with decision boundary := {: ^⊤ = 0 }, can be computed in closed-form:


(, ) = 
|^⊤|,


which only depends on the direction of the weight vector . Thus, <Ref> implies in particular that if we optimize logistic regression by gradient descent on a linearly separable dataset, then we implicitly maximize the minimum margin, just as in SVM. Besides linear classifiers, the same implicit bias towards maximizing the minimum margin has also been discovered  for deep networks <cit.>.







It is then natural to ask the next question:

How does average margin change during training?

To answer this question, we train a binary logistic regression (LR) using gradient descent on MNIST to discriminate 0's from 1's. Note that the subset of MNIST consisting of only 0's and 1's is indeed linearly separable, as LR achieves zero training error (see <Ref> in appendix). All conditions of <Ref> are thus satisfied, and we expect LR to maximize minimum margin. Indeed, <Ref> confirms that the minimum margin continues to increase during training until it approaches that of hard-margin SVM, as predicted by <Ref>. Meanwhile, the average margin decreases drastically after a few epochs at the very beginning, and then keeps decreasing. Interestingly, the minimum margin continues to increase while the average margin continues to decrease even after the training error reaches zero, which means the decision boundary   still changes even after training error diminishes.

To gain further insight, in <Ref> we plot the histogram of margins at different training epochs. We observe that the margin distribution shifts towards the left during training and eventually approaches that of hard-margin SVM. In other words, during training the majority of data is pushed towards the decision boundary, leading LR to become more and more vulnerable to adversarial attacks. Indeed, <Ref> confirms this by visualizing the adversarial examples constructed at different training epochs. Note that for a linear classifier the adversarial example with minimum perturbation can be explicitly determined as

    ^adv =  - ^⊤/^2 ,

which is the point on the decision boundary that is closest to the training example .


As shown in <Ref>, the adversarial examples gradually become more and more imperceptible, indicating that LR becomes more and more vulnerable to adversarial attacks.

A few remarks are in order. First, we have carefully designed our experiment so that (a) the theoretical results in <Ref> apply; (b) the margins and adversarial examples can be explicitly computed. However, similar phenomenon is also observed for deep models on different datasets where the conditions of <Ref> may be violated or the margins can only be approximately computed; see <ref> for more of these experiments. Second, we remark that the decrease of average margin cannot be caused by overfitting. This is because the test accuracy continues to decrease during training (see training curves in  <Ref> of the appendix). Moreover, we observe that the average margin decreases on both training and test sets.
To summarize, we conclude that practically, deep models try to maximize the minimum margin during training at the expense of sacrificing the average margin, hence become susceptible to adversarial attacks. To address this issue, in the next section we propose to explicitly optimize the average margin through appropriate regularization.




















§ AN AVERAGE MARGIN REGULARIZER



In this section, we propose a regularization function to explicitly promote average margin. We first handle linear classifiers in <ref> through maximizing the average margin in the input space directly. For nonlinear classifiers, maximizing the margin in the input space directly is intractable. Instead, we maximize a lower bound of input space margins in <ref>, through simultaneously maximizing feature space margin and controlling the Lipschitz constant of the network.

The most straightforward way to improve robustness of a classifier is through explicit regularization. In particular, we consider the following regularized problem:

    min_:→^c 1/n∑_i=1^n ϕ(y_i, (_i)) - λ·1/n∑_i = 1^n_y_i = ŷ_i·_τ(_i, _y_i)

where ϕ is the loss function we use to measure the accuracy of our classifier , {_k} are the sets induced by f (using the argmax rule)



, λ≥ 0 is the regularization constant that balances the two objectives, and _τ = min{τ, } is the truncated distance. In particular, we only maximize the margin when the classifier makes a correct prediction and the margin is capped at τ to avoid being dominated by some outliers. We show next how to solve (<ref>) when  is a binary linear classifier.



























 §.§ Binary Linear Classifier


In this section we assume there are two classes, c=2 and we consider the linear classifier f() = ^⊤ (w.l.o.g. we omit the bias term). Correspondingly, let _+ = {∈: ^⊤≥ 0 } and 
the distance 
(, _+) = |^⊤|.
The regularized problem (<ref>) reduces to








    min_ = 1  ∑_i = 1^nϕ(y_i ^⊤_i) - λ·∑_i = 1^n[y_i^⊤_i]_0^τ,

where [t]_0^τ = min(max(t, 0), τ).






The second regularization term can be written as a difference of two convex functions. Indeed, define H_s(x) = max(0, s - x), then 

    -[t]_0^τ = H_τ(t) - H_0(t) + τ,

and the objective function simplifies to 

    min_ = 1  ∑_i = 1^nϕ(y_i ^⊤_i) + λ·∑_i = 1^n [H_τ-H_0](y_i^⊤_i),




where λ≥ 0 and τ≥ 0 are tuning hyperparameters.




























Quite pleasantly, our average margin regularizer not only promotes robustness, it also retains Fisher consistency (aka classification-calibrated), namely that the classifier we obtain by minimizing the regularized objective in (<ref>) still approaches the Bayes optimal classifier, as sample size n increases to infinity.


Suppose ϕ: → is a loss function and η∈[0, 1]. For any α∈ℝ, define the conditional ϕ-risk as
C_η^ϕ(α) = ηϕ(α) + (1 - η) ϕ(1 - α).
We say a loss ϕ is Fisher consistent if for any η≠1/2,

    inf_α : α(2η - 1) ≤ 0C_η^ϕ(α) > inf_α∈ C_η^ϕ(α) .



For a Fischer consistent loss functions ϕ, (<ref>) implies that to minimize the ϕ-risk, α should satisfy α (2η -1) > 0, the decision α of our classifier should match the decision (2η - 1) of the Bayes classifier (which is optimal under the 0-1 loss). Fisher-consistency is a necessary condition for any reasonable loss, if our goal is to approximate the Bayes optimal classifier. The following result confirms the Fisher-consistency of our regularized objective (<ref>) (see the proof in appendix).




Suppose the loss function ϕ is decreasing, continuous, bounded below and ϕ^'(0) < 0. Let ψ = H_τ - H_0 be our average margin regularizer. Then the regularized loss ℓ = ϕ + λψ is Fisher consistent for any λ, τ≥ 0.



The above condition on the loss ϕ is reasonable: it basically guarantees ϕ itself to be Fisher consistent. Common loss functions, such as the logistic loss, exponential loss and hinge loss, all satisfy this condition. Thus, our average margin regularizer, when combined with these typical, Fisher consistent loss functions, remains Fisher consistent.






 §.§ Extension to Multiclass Deep Models


For deep neural networks, even computing the margin in the input space is already NP-hard <cit.>, let alone optimizing it. However, the margin in the feature space provides a lower bound of the margin in the input space. For example, let  be a deep neural network with L layers, () = W_L ·σ(W_L - 1·σ( ⋯σ(W_1 ·))), where σ is the activation function. Let Φ() be the output of the second last fully connected layer, i.e. Φ() = σ(W_L - 1·σ( ⋯σ(W_1 ·))), then

    Φ(_1) - Φ(_2)≤ Lip(Φ) _1 - _2,

where Lip(Φ) is the Lipschitz constant of the feature map Φ. The tightness of this bound is determined by the Lipschitz constant of the model. For example, if the model is 1-Lipschitz with Lip(ϕ) = 1, then the margin in the input space  is exactly lower bounded by the margin in the feature space {Φ() : ∈}. The bound (<ref>) motivates a natural way to optimize the margin in input space: we simultaneously fix the Lipschitz constant and maximize the margin in feature space. Note that this perspective allows us to treat any deep network as first performing a nonlinear feature transform through Φ, and then applying a linear classifier on top.















The Lipschitz constant can be bounded by the product of norms of the weight matrices ∏_i W_i_2, where W_i is the weight matrix in layer i, assuming the activation function is 1-Lipschitz, for instance ReLU SzegedyZSBEGF14. To control the overall  Lipschitz constant Lip(Φ), ideally, we want to enforce the Lipschitz constant of each layer to be exactly 1, namely constraining the spectral norm of each weight matrix W_i to be approximately 1. 

Inspired by <cit.>, we add an orthogonal penalty βW_iW_i^⊤ - I_F^2, into our training objective, 
which encourages the weight matrices to be orthogonal hence having spectral norm close to 1. For convolutional layers, we first flatten the convolutional filter and then apply the above penalty. 








Once the Lipschitz constant is bounded, we directly maximize the average margin in the feature space, as a computationally efficient lower bound for promoting the average margin in the input space. Since our classifier is linear in the feature space, the distance to the decision boundary can be computed as in <ref>:




    (, _ŷ) = min_k ≠ŷ (_ŷ - _k)^⊤Φ(),

where _k is the (normalized) weight vector in the final layer for the k-th class. Similar to the binary case, we only maximize the margin for correctly classified examples and truncate the margin if it exceeds the threshold τ.

In the end, our regularized objective is,

    ∑_i = 1^nϕ(y_i, (_i)) - λ[ min_k ≠ y_i (_y_i - _k)^⊤Φ(_i) ]_0^τ + β∑_1 ≤ l ≤ L W_lW_l ^ ⊤ - I _F^2,

where the first term is the standard training loss (such as cross-entropy), the third term is the orthogonal constraint for controlling the Lipschitz constant of the network, and the second term is the average margin penalty in the feature space, which also maximizes the input space average margin, provided that the Lipschitz constant of the network is indeed close to unity.

01
Distance to decision boundary plays a key role in adversarial robustness. Currently, most definitions of adversarial robustness measure more or less rely on distance from a single data point to decision boundary.

In the previous experiments, we are able to observe that average distance can decrease drastically during training. Thus, it is natural to add a average distance regularizer into objective function.

Previously, we got the following formulation:

    max_w_2 = 1    ∑_i = 1^n (y_i ŷ_i)_+
    s.t.     y_i ŷ_i > 0

Change the hard constraint into soft constraint, we get

    min_w_2 = 1  - μ∑_i = 1^n (y_i ŷ_i)_+ + ∑_i = 1^n(- y_i ŷ_i)

We can view the objective function as a sum of the following loss function:

    l(α) = 
    
    -α    if α≤ 0
    
    -μα    if α > 0

A more general form, considering truncation is shown below:

    l(α) = 
    ξ + τ    if α≤ -τ
    
    -ξ - α    if -τ < α≤ 0
    ξ - (1 + μ) α    if 0 < α < ξ
    
    -μα    if ξ < α≤τ
    
    -μτ    if α > τ

Note that the loss function can be written in a fairly simple form. If we define 

    H_s(x) = max(0, s - x)

Then the loss is equal to

    H_ξ(x) - H_-τ(x) + μ (H_τ(x) - H_0(x)) - μτ

Ignoring the constant, the loss is

    H_ξ(x) - H_-τ(x)

while the regularization term is

    H_τ(x) - H_0(x)

Note that both two terms has close relation to robust truncated hinge loss, which is H_1(x) - H_0(x). Writing the loss in this way makes the decomposition trivial. Moreover, it makes the analysis of calibration concise. By the following lemma, the preceding loss function is calibrated for any ξ > 0. The method is to extend the lemma for proving truncated hinge loss (Wu and Liu, 2007), such that it can be applied in our case. (Note that Wu and Liu's proof is incorrect. One counterexample can be min(0, -x). But it can be fixed by additional assumptions.)

We introduce the definition of Fischer-consistency for loss functions, a.k.a. classification calibrated.

Suppose ϕ: R → R is a loss function and η∈[0, 1]. For any α∈ R, define conditional ϕ-risk as

    C_η^ϕ(α) = ηϕ(α) + (1 - η) ϕ(1 - α).

We say loss ϕ is calibrated if for any η≠1/2,

    inf_α : α(2η - 1) ≤ 0C_η^ϕ(α) > inf_α∈ R C_η^ϕ(α) .


Classification calibrated is a basic condition on loss functions. If a loss function is classification calibrated, then minimizing the surrogate loss over the true distribution will lead to Bayes classifier.



Suppose a nonincreasing loss function ϕ is differentiable at zero and ϕ^' (0) < 0. Then the truncated loss ψ(x)=min(ϕ(x), ϕ(s)) is calibrated for any s ≤ 0.


By the following lemma, for a wide range of loss functions, including logistic loss, hinge loss and exponential loss, the objective function remains calibrated after adding our regularizer.

Suppose a nonincreasing continuous function ϕ is bounded below and ϕ^'(0) < 0. ψ is the regularizer H_τ - H_0. Then ℓ = ϕ + μψ is calibrated.



Since both ϕ and ψ are bounded below, ℓ is also bounded below. Denote m = inf C_η^ℓ(α). We need to show inf_α(2η - 1) ≤ 0C_η^ℓ(α) is strictly greater than m for all η≠1/2. We first consider the case η > 1/2. For the case η < 1/2, the proof is similar.

The derivative of C_η^ϕ(α) at zero is (2η - 1)ϕ^'(0), which is negative. Thus there exists δ_1 > 0 such that any α∈ (0, δ_1) satisfies C_η^ϕ(α) < C_η^ϕ(0).

The right hand derivative of ψ at zero is negative, thus there exist δ_2 > 0 such that any α∈ (0, δ_2) satisfies. ψ(α) < ψ(0). Notice that ψ(α) is constant when α≤ 0. Thus any α∈ (0, δ_2) satisfies C_η^ψ(α) < C_η^ψ(0).

Combining above arguments, there exists a sufficiently small α_0 > 0, such that C_η^ℓ(α_0) < C_η^ℓ(0). Splitting the interval (-∞, 0] into (-∞, -α_0] and [-α_0, 0], it is sufficient to show that both

    inf_α≤ - α_0 C_η^ℓ(α) > m

and

    inf_- α_0 ≤α≤ 0 C_η^ℓ(α) > m

hold.

For α≤ - α_0,

    C_η^ℓ(α) - C_η^ℓ(- α)     = (2η - 1)(ℓ(α) - ℓ(-α)) 
       ≥ (2η - 1)(ℓ(0) - ℓ(- α)) 
       ≥ (2η - 1)(ℓ(0) - ℓ(α_0))

Namely, flipping the sign of α can strictly decrease the value of C_η^ℓ(α). Thus,

    inf_α≤ -α_0 C_η^ℓ(α) ≥    (2η - 1)(ℓ(0) - ℓ(α_0)) + m 
    
    >     m

For -α_0 ≤α≤ 0, by continuity there exists a minimizer α^⋆ for C_η^ℓ(α) on this compact set. If α^⋆≠ 0, then we can again flip the sign of α to get a strictly smaller value. Thus C_η^ℓ(α^⋆) > C_η^ℓ(- α^⋆) ≥ m.

If α^⋆ = 0,

    C_η^ℓ(0) > C_η^ℓ(α_0) ≥ m




By above lemma, we can combine it with most loss functions without changing the calibrated property.

A few points to be highlighted:


  * When τ = 1, the regularizer is exactly the truncated hinge.

  * The regularizer includes accuracy into it. We won't be surprise that mininizing the regularizer alone can lead to a reasonable classifier. If we want to decouple accuracy, we should use 

  * It is the regularizer, combining with the norm constraint w_2 = 1, that leads to a classifier with large average distance. Minimizing the regularizer alone can still lead to hard margin SVM. A concrete counterexample is truncate hinge SVM with sufficiently small λ:

    min λw_2 + ∑_i = 1^n H_1(y_iŷ_i) - H_0(y_iŷ_i)





 §.§ Multiclass


Suppose x is correctly classified as label c, then the distance the the decision boundary is

    min_j ≠ c(w_c - w_j)^T x + b_c - b_j/w_c - w_j

Here we do a relaxation. We only maximize the numerator, while forcing the denominator bounded. If denote

    α = min_j ≠ c(w_c - w_j)^T x + b_c - b_j/w_c - w_j

then again we add a regularization term H_τ(α) - H_0(α) to the objective function.



 §.§ Optimization

Note that our regularizer is nonconvex and nondifferentiable. In addition, the gradient of the regularizer is zero in (-∞, 0) and (τ, +∞), meaning gradient descent cannot perform any update in these intervals. Both increase the difficulty of optimization, even for linear classifiers. However, the regularizer can be written as difference of two convex functions. Thus we use DCA to optimize the objective function. For the inner loop of DCA, we use (stochastic) projected subgradient descent to minimize the subproblem. In practice, it converges very fast, comparable to normal training.










§ EXPERIMENTS



In this section, we conduct experiments to (a) verify the minimum-average margin trade-off on a variety of (nonlinear) deep models; (b) demonstrate the effectiveness of our average margin regularizer. First, we train six models with various architectures on MNIST and CIFAR10 to verify the trade-off again. Then, we retrain these models with our average margin regularizer, and confirm that our regularizer indeed can effectively promote the average margin. Finally, we compare our average margin regularizer with other state-of-the-art defense techniques in the literature and find that our regularizer achieves comparable performance in terms of robustness and accuracy.













 §.§ Approximating Distance

In general, exactly computing the distance to the decision boundary of deep models is intractable <cit.>. Instead, we use the following Lipschitz lower bound as a reasonable approximation:


Suppose : ^d →^c is a multiclass classifier (with argmax prediction rule). Then, for any r > 0:

    (, _ŷ) ≥min{min_k ≠ŷf_ŷ() - f_k()L^k_, r},

where L^k_ is the local Lipschitz constant of f_ŷ() - f_k() over the ball B(, r)




The lower bound (<ref>) is in fact exact when  is linear, and for general nonlinear , it is reasonably close to the true distance, as shown empirically in <cit.>.

Here, our estimate for the Lipschitz constant L^k_ is simply the maximum norm of the gradient (difference) of many random samples in the ball B(, r), as we found this simple strategy is reasonably efficient and accurate. For space limits, we defer the experimental details on approximating this distance to the appendix.





 §.§ Verifying the Margin Trade-off again on Deep Nonlinear Models

Due to space limits, here we only present the experimental results on the CIFAR10 dataset, while results on MNIST can be found in the appendix. For each model, we plot the average margin and minimum margin the number of training epochs










in <Ref>. It is clear that similar phenomenon as those in <ref> can be observed: the minimum margin continues increasing while at the same time the average margin keeps decreasing. This again highlights an intrinsic trade-off between minimum margin and average margin. In addition, we consistently observed that the average margin continues to decrease even after the training/test error has saturated (see training curves <Ref> in the appendix).




To investigate how the margin distribution changes during training, we plot the histograms of margins in <Ref> (appendix). As training proceeds, we observe again the margin distribution shifts towards left, meaning the majority of data points is pushed closer to the boundary. To some extent, this provides compelling explanation of the non-robustness of deep models: although achieving high accuracy by maximizing the minimum margin, the average margin, which is a better indicator of robustness, is at serious jeopardy. Note that early stopping, while helps preventing the average margin to decrease unnecessarily, is not sufficient by itself to promote average margin. Instead, an explicit average margin regularizer is more effective, as we show next.














































 §.§ Average Margin Regularizer
























We retrain six models augmented with our average margin regularizer, and compare the average margin with standard training in <Ref>. It is clear that with our average margin regularizer, the regularized models no longer sacrifice the average margin during training. For all six models, adding the average margin regularizer significantly improves adversarial robustness. For example, the average margin of LR and MLP become 2 ∼ 3 times more than those of models with standard training. For CNN, the average margin is increased by a factor of 1.5 ∼ 2.




















Next, we compare our regularizer with Lipschitz constant regularization. In our regularizer, we use the orthogonal constraint W W ^ ⊤ - I_F^2 to control the Lipschitz constant. The idea of using orthogonal constraint as Lipschitz constant regularizer has been proposed before (Paserval networks <cit.> and defensive quantization <cit.>). Here, we prvide a comparison between Lipschitz constant regularization and our average margin regularizer. We evaluate models using clean accuracy, robust accuracy under l_2 norm projected gradient descent (PGD) attack <cit.>, and the average margin. We run 1000 iterations of PGD to generate adversarial examples, whose success serves as a good approximation of robust accuracy. The results can be found in <Ref>. As we can see, when ϵ, the amount of allowed perturbations, is small, the accuracy of our average margin regularizer is comparable to that of the Lipschitz constant regularizer (LCR); but as ϵ becomes larger, the average margin regularizer consistently outperforms the latter. Interestingly, LCR alone can also improve adversarial robustness marginally cisse2017parseval, lin2018defensive, when ϵ is small. This may be caused by implicit max-margin effect of the loss function used in training. However, as ϵ becomes larger, the robust accuracy of LCR is inferior to our method, sometimes even worse than standard training,

which is also confirmed in the experimental results in <cit.>. This implies that controlling Lipschitz constant alone may not be enough to train a robust model. Instead, one needs to maximize the average margin explicitly.



We also compare our method with deep defense (DD) <cit.>, PGD adversarial training (Adv) <cit.> and the maximum margin regularizer (MMR) <cit.>, which maximizes the linear region of ReLU netowrks. The results are shown in <Ref>. Compared with standard training, our method can significantly improve  model robustness. On MNIST, our method achieves overall better robust accuracy. On CIFAR10, our method achieves comparable results as adversarial training and deep defense. In addition, our method consistently outperforms MMR on both datasets. Moreover, our method is more efficient than adversarial training and deep defense. In fact, adversarial training would increase the training time by the number of PGD iterations (typically tens or hundreds), and deep defense is even more time consuming, to a point where it can only be applied as fine-tuning <cit.>, while the training time of our method is roughly the same as the standard training. 























































































































§ CONCLUSION




In this work, we studied adversarial robustness from a margin perspective. We discovered the intrinsic trade-off between minimum and average margin, which appears across different models and datasets. We gave strong empirical evidence that deep models maximize the minimum margin during training to achieve high accuracy, but at the expense of decreasing the average margin significantly hence becoming more susceptible to adversarial attacks. To address the issue, we designed a new regularizer to explicitly maximize average margin and to retain Fisher consistency. Our extensive experiments confirmed the effectiveness of our regularizer. In the future, we will theoretically analyze the trade-off to provide further insights to the phenomenon. Moreover, we plan to go beyond just maximizing average margin, by controlling other margin distribution statistics such as variance.
















unsrtnat


















§ PROOFS










































Indeed, according to the definitions in (<ref>) and (<ref>) we have

    () 
       = inf{:  + ∉_(),  +∈}
       = inf{ (+) - :  + ∉_(),  +∈}
       = (, _()) = (, _())













Since both ϕ and ψ are bounded below, ℓ is also bounded below. Denote m = inf_α∈ C_η^ℓ(α). We need to show inf_α(2η - 1) ≤ 0C_η^ℓ(α) is strictly greater than m for all η≠1/2. We first consider the case η > 1/2. For the case η < 1/2, the proof is similar.

The derivative of C_η^ϕ(α) at zero is (2η - 1)ϕ^'(0) < 0. Thus ∃δ_1 > 0 such that ∀α∈ (0, δ_1) satisfies C_η^ϕ(α) < C_η^ϕ(0).

The right hand derivative of ψ at zero is negative, thus there ∃δ_2 > 0 such that ∀α∈ (0, δ_2) satisfies ψ(α) < ψ(0). Notice that ψ(α) is constant when α≤ 0. Thus ∀α∈ (0, δ_2) satisfies C_η^ψ(α) < C_η^ψ(0).

Notice that C_η^l(α) = C_η^ϕ(α) + λ C_η^ψ(α). Combining above arguments, there exists a sufficiently small α_0, such that 0 < α_0 < min(δ_1, δ_2), and C_η^ℓ(α_0) < C_η^ℓ(0). Splitting the interval (-∞, 0] into (-∞, -α_0] and [-α_0, 0], it is sufficient to show that both

    inf_α≤ - α_0 C_η^ℓ(α) > m

and

    inf_- α_0 ≤α≤ 0 C_η^ℓ(α) > m

hold.

For α≤ - α_0,

    C_η^ℓ(α) - C_η^ℓ(- α)     = (2η - 1)(ℓ(α) - ℓ(-α)) 
       ≥ (2η - 1)(ℓ(0) - ℓ(- α)) 
       ≥ (2η - 1)(ℓ(0) - ℓ(α_0)) 
        > 0.

The inequalities (<ref>) and (<ref>) are because l is a decreasing function. The inequality (<ref>) is because the specific choice of α_0 strictly decreases the value of l at zero. Namely, flipping the sign of α can strictly decrease the value of C_η^ℓ(α). Thus,

    inf_α≤ -α_0 C_η^ℓ(α)    ≥ (2η - 1)(ℓ(0) - ℓ(α_0)) + C_η^ℓ(- α) 
       ≥ (2η - 1)(ℓ(0) - ℓ(α_0)) + m 
        > m.

For -α_0 ≤α≤ 0, by continuity there exists a minimizer α^⋆ for C_η^ℓ(α) on this compact set. If α^⋆≠ 0, then we can again flip the sign of α to get a strictly smaller value. Thus C_η^ℓ(α^⋆) > C_η^ℓ(- α^⋆) ≥ m. If α^⋆ = 0, then

    C_η^ℓ(0) > C_η^ℓ(α_0) ≥ m.

Hence the theorem holds.







§ TRAINING CURVES

<Ref> shows the training loss, training error and test error of logistic regression in <Ref>. As training goes, the error rate on both training set and test set never increase, thus the logistic regression is not overfitting, although trained with excessive number of epochs. This again hightlights that the trade-off between minimum and average margin cannot be caused by overfitting.



<Ref> shows the training curves of six models in <Ref> by standarded training. Although there exists a generalization gap between training errors and test errors, the test errors never increase, thus the trade-off between minimum and average margin cannot be caused by overfitting.







§ MINIMUM-AVERAGE MARGIN TRADE-OFF FOR MNIST MODELS

<Ref> shows the minimum and average margin trade-off for MNIST models [In the figure of average margin of MNIST-LR (top left), we shift the curve of average margin on training set by a small constant 0.001, to avoid overlapping of two curves. This is only for illustration purpose.]. A similar trade-off between minimum and average margin can be observed as discussed in <Ref>. The minimum margin keeps increasing while the average margin keeps decreasing. The only exception is the average margin of MNIST-CNN. But the range of margin in the figure is very small (from 0.94 to 1.08), in which case the Lipschitz constant estimation in <Ref> could be inaccurate.







§ MARGIN HISTOGRAMS OF MNIST MODELS DURING TRAINING


We plot margin histograms for three MNIST models in <Ref>.









§ MARGIN HISTOGRAMS OF CIFAR MODELS DURING TRAINING

We plot margin histograms for three CIFAR models in <Ref>.







§ DETAILED EXPERIMENT SETTING

























Model Architecture:


  * MNIST-LR and CIFAR-LR: Multiclass logistic regression.

  * MNIST-MLP and CIFAR-MLP: Neural network with one hidden layer. The hidden layer has 1024 neurons and relu activation.

  * MNIST-CNN and MNIST-CNN: Two AlexNet-Like convolutional neural networks with a slight difference. They are exactly the same as the models used by WengZCYSGHD18, CarliniWagner17a. Dropout is used to alleviate overfitting on CIFAR10. No data augmentation is used.

  * ConvNet: A convolutional neural network with 5 convolutional layers, used in <cit.>.

  * LeNet: LeNet, consists of two convolutional layers and two fully connected layers.

  * LeNetSmall: A convolutional neural network with similar structure to LeNet, but with fewer filers. This model is same as the one used in <cit.>. On CIFAR10, data augmentation (random crop and random flip) is used.



Standard Training: We use SGD (learning rate 0.01) with momentum (0.9) and nestorv to train all six models. Batch size is set to 128. Linear models (LR) are trained for 1000 epochs. Nonlinear models (MLP, CNN) are trained for 200 epochs.




Average Margin Regularizer: λ = 0.1 and β = 10^-3 are used for all models, while different τ's are used for different models. τ is tuned such that it is on the same order as the Lipschitz constant of the model. MNIST-LR and MNIST-MLP use τ = 5. MNIST-CNN use τ = 10. CIFAR-LR use τ = 5. CIFAR-MLP and CIFAR-CNN use τ = 10. The idea is using larger τ for deeper models. The spectral norm of weights across layers may not be exactly 1, even after adding orthogonal constraint. In fact, the product of spectral norm will become larger as the model becomes deeper. Thus, one should use larger truncation parameter, since the range of margin in feature space may be larger. Following same idea, LeNet and LeNetSmall use τ = 40; ConvNet uses τ = 50.



In addition, for fair comparison, we set the same β = 10^-3 to train models with Lipschitz constant regularization.

Adversarial Training: We use PGD attack to perform adversarial training. We set the number of iterations 40 and step size 0.01. On MNIST, the perturbation budget ϵ is set to 2.0; on CIFAR, ϵ is set to 0.4.

Attack Method: Through out the experiment, we use projected gradient descent (PGD) attack to evaluate the robust accuracy. We set step size 0.01 and number of iterations 1000. Increasing the number of iterations does not change the robust accuracy much, thus 1000 iterations is sufficient to generate strong adversarial examples.

Approximating Distance
When using <Ref> to approximate the distance to decision boundary, we need to estimation the Lipchitz constant of the network in a small neighbourhood around the input. Following <cit.>, we simply take the maximum norm of gradient in that neighbourhood. Throughout the experiments, we set r = 5 and the sampling size equal to 1024× 50 (except for linear classifiers, whose sampling size is 1). For linear logistic regression, we perform estimation in every epoch; for nonlinear classifiers, we only perform estimation at certain epochs: 1, 10, 20, 30, 40, 50, 80, 120, 160 and 200, where we perform more estimations at the beginning, as distances may change drastically in initial stages. Due to efficiency concerns, the estimation is performed on a subset of size 500, which is randomly chosen (with a fixed random seed) from the original training and test sets.


































	

 	

	








01


§ MNIST-LR











In addition, we visualize a set of adversarial examples.




§ MNIST-MLP















§ MNIST-CNN















§ CIFAR-LR














§ CIFAR-MLP














§ CIFAR-CNN














§ VISUALIZATION OF ADVERSARIAL EXAMPLES




§ DISCUSSION

So far, the experiment result is promising. We can observe that average distance keeps decreasing during training for all models (except for MNIST-CNN). Plots of histogram of distance confirm that the majority of data is pushed towards desicion boundary.

However, unlike binary linear case, there are two points that are different:


  * We did not oberserve the increase of robustness at the very beginning. Instead, average distance decrease monotonically. This could be a result of insufficient numeber of estimations.

  * The minimum distance keeps oscillating, unlike increasing minimum distance in binary logistic regression. This may be a result of nonseparable dataset. However, several nonlinear models indeed reach zero training error after certain number of epochs. This may also be a result of insufficient number of estimations, i.e. the minimum distance may continue to increase after 200 epochs.


Again, for nonlinear classifiers, we only use the Lipschitz lower bound as a approximation of distance to decision boundary. This may be the reason for the unsatisfactory result for MNIST-CNN.





