L2-NONEXPANSIVE NEURAL NETWORKS
Year: 2019

Abstract:
This paper proposes a class of well-conditioned neural netw orks in which a unit amount of change in the inputs causes at most a unit amount of c hange in the outputs or any of the internal layers. We develop the known metho dology of controlling Lipschitz constants to realize its full potential in ma ximizing robustness, with a new regularization scheme for linear layers, new ways to ad apt nonlinearities and a new loss function. With MNIST and CIFAR-10 classifiers, we demonstrate a number of advantages. Without needing any adversarial tra ning, the proposed classifiers exceed the state of the art in robustness against white-boxL2-bounded adversarial attacks. They generalize better than ordinary etworks from noisy data with partially random labels. Their outputs are quanti t tively meaningful and indicate levels of confidence and generalization, among oth er desirable properties.

text: This paper proposes a class of well-conditioned neural networks in which a unit amount of change in the inputs causes at most a unit amount of change in the outputs or any of the internal layers. We develop the known methodology of controlling Lipschitz constants to realize its full potential in maximizing robustness, with a new regularization scheme for linear layers, new ways to adapt nonlinearities and a new loss function. With MNIST and CIFAR-10 classifiers,we demonstrate a number of advantages. Without needing any adversarial traning, the proposed classifiers exceed the state of the art in robustness againstwhite-boxL2-bounded adversarial attacks. They generalize better than ordinaryetworks from noisy data with partially random labels. Their outputs are quantit tively meaningful and indicate levels of confidence and generalization, among other desirable properties.

heading: 1 INTRODUCTION
text: Artificial neural networks are often ill-conditioned systems in that a small change in the inputs can cause significant changes in the outputs (Szegedy et al.,2014). This results in poor robustness and vulnerability under adversarial attacks which has beenr ported on a variety of networks including image classification (Carlini & Wagner, 2017a; Goodfellow et al., 2014), speech recognition (Kreuk et al., 2018; Alzantot et al., 2018; Carlini & Wagner,2018), image captioning (Chen et al., 2017) and natural language processing (Gao et al., 2018; Ebrahimi et al., 2017). These issues bring up both theoretical questions of how neural networks generalize (Kawaguchi et al., 2017; Xu & Mannor, 2012) and practical concerns of security in applications (Akhtar & Mian, 2018).
A number of remedies have been proposed for these issues and will be discussed in Section 4. Whitebox defense is particularly difficult and many proposals have failed. For example, Athalye et al. (2018) reported that out of eight recent defense works, onlyMadry et al. (2017) survived strong attacks. So far the mainstream and most successful remedy is that of adversarial training (Madry et al., 2017). However, as will be shown in Tables 1 and 2, the robustnes by adversarial training diminishes when a white-box attacker (Carlini & Wagner, 2017a) isllowed to use more iterations.
This paper explores a different approach and demonstrates that a combination of the following three conditions results in enhanced robustness: 1) the Lipschitz onstant of a network from inputs to logits is no greater than 1 with respect to theL2-norm; 2) the loss function explicitly maximizes confidence gap, which is the difference between the largest and second largest logits of a classifier; 3) the network architecture restricts confidence gaps as little as possible. We will elaborate.
There are previous works that achieve the first condition (Cisse et al., 2017; Hein & Andriushchenko, 2017) or bound responses to input perturbations by other means (Kolter & Wong, 2017; Raghunathan et al., 2018; Haber & Ruthotto, 2017). For example, Parseval networks (Cisse et al., 2017) bound the Lipschitz constant by requiring each linear or convolution layer be composed of orthonormal filters. However, the report d obustness and guarantees are often under weak attacks or with low noise magnitude, and none of these works has demonstrated results that are comparable to adversarial training.
In contrast, we are able to build MNIST and CIFAR-10 classifiers, without needing any adversarial training, that exceed the state of the art (Madry et al., 2017) in robustness against white-boxL2bounded adversarial attacks. The defense is even stronger if adversarial training is added. We will refer to these networks asL2-nonexpansive neural networks(L2NNNs). Our advantage comes
from a set of new techniques: our weight regularization, which is key in enforcing the first condition, allows greater degrees of freedom in parameter training than the scheme in Cisse et al. (2017); a new loss function is specially designed for the second condition; we adapt various layers in new ways for the third condition, for example norm-pooling and two-sided ReLU, which will be presented later.
Let us begin with intuitions behind the second and third conditions. Consider a multi-class classifier. Let g (x) denote its confidence gap for an input data pointx. If the classifier is a single L2NNN,1 we have a guarantee2 that the classifier will not change its answer as long as the inputx is modified by no more than anL2-norm ofg (x) / √ 2. Therefore maximizing the average confidence gap directly boosts robustness and this motivates the second condition.T explain the third condition, let us introduce the notion of preserving distance: the distance between any pair of input vectors with two different labels ought to be preserved as much as possible atth outputs, while we do not care about the distance between a pair with the same label. Letd (x1,x2) denote theL2-distance between the output logit-vectors for two input pointsx1 andx2 that have different labels and that are classified correctly. It is straightforward to verify the condition3 of g (x1) + g (x2) ≤ √ 2 · d (x1,x2). Therefore a network that maximizes confidence gaps well mustbe one that preserves distance well. Ultimately some distances are preserved while others are lost, and ideally the decision of which distance to lose is made by parameter training rather than by artifacts of network architecture. Hence the third condition involves distance-preserving architecture choices that leave the decision to parameter training as much as possible, and this motivates many of our design decisions such as Sections 2.2 and 2.3.
In practice we employ the strategy of divide and conquer and buil each layer as a nonexpansive map with respect to theL2-norm. It is straightforward to see that a feedforward network composed of nonexpansive layers must implement a nonexpansive map overall. How to adapt subtleties like recursion and splitting-reconvergence is included in the appendix.
Besides being robust against adversarial noises, L2NNNs have other desirable properties. They generalize better from noisy training labels than ordinarynetworks: for example, when 75% of MNIST training labels are randomized, an L2NNN still achieves 93.1% accuracy on the test set, in contrast to 75.2% from the best ordinary network. The problem of exploding gradients, which is common in training ordinary networks, is avoided because the gradient of any output with respect to any internal signal is bounded between -1 and 1. Unlike ordina y networks, the confidence gap of an L2NNN classifier is a quantitatively meaningful indicat on of confidence on individual data points, and the average gap is an indication of generalization.
2 L2-NONEXPANSIVE NEURAL NETWORKS
This section describes how to adapt some individual operators in neural networks for L2NNNs. Discussions on splitting-reconvergence, recursion and normalization are in the appendix.

heading: 2.1 WEIGHTS
text: This section covers both the matrix-vector multiplicationn a fully connected layer and the convolution calculation between input tensor and weight tensor in a convolution layer. The convolution calculation can be viewed as a set of vector-matrix multiplications: we make shifted copies of the input tensor and shuffle the copies into a set of small vectorssuch that each vector contains input entries in one tile; we reshape the weight tensor into a matrix by flattening all but the dimension of the output filters; then convolution is equivalent to multiplying each of the said small vectors with the flattened weight matrix. Therefore, in both cases, abasic operator isy = Wx. To be a nonexpansive map with respect to theL2-norm, a necessary and sufficient condition is
yTy ≤ xTx =⇒ xTWTWx ≤ xTx, ∀x ∈ RN
ρ ( WTW ) ≤ 1 (1)
whereρ denotes the spectral radius of a matrix.
1This is only an example and we recommend building a classifier as multiple L2NNNs, see Section 2.4. 2See Lemma 1 in Appendix D for the proof of the guarantee. 3See Lemma 2 in Appendix D for the proof of the condition.
The exact condition of (1) is difficult to incorporate into training. Instead we use an upper bound:4
ρ ( WTW ) ≤ b (W ) , min ( r(WTW ), r(WWT) )
, wherer (M) = max i
∑
j
|Mi,j | (2)
The above is where our linear and convolution layers differ from those in Cisse et al. (2017): they requireWWT to be an identity matrix, and it is straightforward to see that eir scheme is only one special case that makesb (W ) equal to 1. Instead of forcing filters to be orthogonal to eachother, our bound ofb (W ) provides parameter training with greater degrees of freedom.
One simple way to use (2) is replacingW with W ′ = W/ √
b (W ) in weight multiplications, and this would enforce that the layer is strictly nonexpansive. Another method is described in the appendix.
As mentioned, convolution can be viewed as a first layer of making copies and a second layer of vector-matrix multiplications. With the above regularizat on, the multiplication layer is nonexpansive. Hence we only need to ensure that the copying layer is nonexpansive. For filter size ofK1 by K2 and strides ofS1 byS2, we simply divide the input tensor by a factor of √ ⌈K1/S1⌉ · ⌈K2/S2⌉.

heading: 2.2 RELU AND OTHERS
text: Let us turn our attention to the third condition from Section1. ReLU, tanh and sigmoid are nonexpansive but do not preserve distance well. This section presents a method that improves ReLU and is generalizable to other nonlinearities. A different approach to improve sigmoid is in the appendix.
To understand the weakness of ReLU, let us consider two inputdata points A and B, and suppose that a ReLU in the network receives two different negative values for A and B and outputs zero for both. Comparing the A-B distance before and after this ReLU layer, there is a distance loss and this particular ReLU contributes to it. We usetwo-sided ReLUwhich is a function fromR to R2 and simply computes ReLU(x) and ReLU(−x). Two-sided ReLU has been studied in Shang et al. (2016) in convolution layers for accuracy improvement. It is straightforward to verify that two-sided ReLU is nonexpansive with respect to anyLp-norm and that it preserves distance in the above scenario. We will empirically verify its effectiveness in increasingconfidence gaps in Section 3.
Two-sided ReLU is a special case of the following general technique. Letf(x) be a nonexpansive and monotonically increasing scalar function, and note that ReLU, tanh and sigmoid all fit these conditions. We can define a function fromR to R2 that computesf(x) andf(x) − x. Such a new function is nonexpansive with respect to anyLp-norm5 and preserves distance better thanf(x) alone.

heading: 2.3 POOLING
text: The popular max-pooling is nonexpansive, but does not preserv distance as much as possible. Consider a scenario where the inputs to pooling are activations that represent edge detection, and consider two images A and B such that A contains an edge that passes a particular pooling window while B does not. Inside this window, A has positive values while B has all zeroes. For this window, the A-B distance before pooling is theL2-norm of A’s values, yet if max-pooling is used, the A-B distance after pooling becomes the largest of A’s values, which can be substantially smaller than the former. Thus we suffer a loss of distance between A and B whilepassing this pooling layer.
We replace max-pooling with norm-pooling, which was reported in Boureau et al. (2010) to occasionally increase accuracy. Instead of taking the max of values inside a pooling window, we take the L2-norm of them. It is straightforward to verify that norm-pooling is nonexpansive6 and would entirely preserve theL2-distance between A and B in the hypothetical scenario above. OtherLp-norms can also be used. We will verify its effectiveness in increasing confidence gaps in Section 3. If pooling windows overlap, we divide the input tensor by √ K whereK is the maximum number of pooling windows in which an entry can appear, similar to convolution layers discussed earlier.
4The spectral radius of a matrix is no greater than its naturalL∞-norm.WTW andWWT have the same non-zero eigenvalues and hence the same spectral radius.
5See Lemma 4 in Appendix D for the proof of nonexpansiveness. 6See Lemma 5 in Appendix D for the proof of nonexpansiveness.

heading: 2.4 LOSS FUNCTION
text: For a classifier withK labels, we recommend building it asK overlapping L2NNNs, each of which outputs a single logit for one label. In an architecture withno split layers, this simply implies that theseK L2NNNs share all but the last linear layer and that the last linear layer is decomposed intoK single-output linear filters, one in each L2NNN. For a multi-L2NNN classifier, we have a guarantee7 that the classifier will not change its answer as long as the inputx is modified by no more than an L2-norm ofg (x) /2, where againg (x) denotes the confidence gap. As mentioned in Section 1, a single-L2NNN classifier has a guarantee ofg (x) / √ 2. Although this seems better on the surface, it is more difficult to achieve large confidence gaps. We will assume the multi-L2NNN approach.
We use a loss function with three terms, with trade-off hyperparametersγ andω:
L = La + γ · Lb + ω · Lc (3)
Let y1, y2, · · · , yK be outputs from the L2NNNs. The first loss term is La = softmax-cross-entropy(u1y1, u2y2, · · · , uKyK , label) (4) whereu1, u2, · · · , uK are trainable parameters. The second loss term is Lb = softmax-cross-entropy(vy1, vy2, · · · , vyK , label) (5) wherev can be either a trainable parameter or a hyperparameter. Note thatu1, u2, · · · , uK andv are not part of the classifier and are not used during inferenc. The third loss term is
Lc = average
( log ( 1− softmax(zy1, zy2, · · · , zyK)label ))
z (6)
wherez is a hyperparameter.
The rationale for the first loss term (4) is that it mimics cross-entropy loss of an ordinary network. If an ordinary network has been converted to L2NNNs by multiplying each layer with a small constant, its original outputs can be recovered by scaling up L2NNN outputs with certain constants, which is enabled by the formula (4). Hence this loss term is meant to guide the training process to discover any feature that an ordinary network can discover. The ration le for the second loss term (5) is that it is directly related to the classification accuracy. Multiply ng L2NNN outputs uniformly withv does not change the output label and only adapts to the value rangeof L2NNN outputs and drive towards better nominal accuracy. The third loss term (6) approximates verage confidence gap: the log term is a soft measure of a confidence gap (for a correct prediction), and is asymptotically linear for larger gap values. The hyperparameterz controls the degree of softness, and has relatively low impact on the magnitude of loss due to the division byz; if we increasez then (6) asymptotically becomes the average of minus confidence gaps for correct predictionsand zeroes for incorrect predictions. Therefore loss (6) encourages large confidence gaps and yet is smooth and differentiable.
A notable variation of (3) is one that combines with adversarial training. Our implementation applies the technique of Madry et al. (2017) on the first loss term (4):we use distorted inputs in calculating La. The results are reported in Tables 1 and 2 as Model 4. Anotherpossibility is to use distorted inputs in calculatingLa andLb, whileLc should be based on original inputs.

heading: 3 EXPERIMENTS
text: Experiments are divided into three groups to study different properties of L2NNNs. Our MNIST and CIFAR-10 classifiers are available at http://researcher.watson.ibm.com/group/9298

heading: 3.1 ROBUSTNESS
text: This section evaluates robustness of L2NNN classifiers for MNIST and CIFAR-10 and compares against the state of the art Madry et al. (2017). The robustnes metric is accuracy under whitebox non-targetedL2-bounded attacks. The attack code of Carlini & Wagner (2017a) is used. We
7See Lemma 6 in Appendix D for the proof of the guarantee. The guarantee in either Lemma 1 or Lemma 6 is only a loose guarantee and it has been shown in Hein & Andriushchenko(2017) that a larger guarantee exists by analyzing local Lipschitz constants, though it is expensive to compute.
downloaded the classifiers8 of Madry et al. (2017) and report their robustness againstL2-bounded attacks in Tables 1 and 2.9 Note that their defense diminishes as the attacks are allowed more iterations. Figure 1 illustrates one example of this effect: the first image is an attack on MNIST Model 2 (0 recognized as 5) found after 1K iterations, with noiseL2-norm of 4.4, while the second picture is one found after 10K iterations, the same 0 recognized as 5, with noiseL2-norm of 2.1. We hypothesize that adversarial training alone provides little absolute defense at the noise levels used in the two tables: adversarial examples still exist and are only more difficult to find. The fact that in Table 2 Model 2 accuracy is lower in the 1000x10 row than the10K row further supports our hypothesis.
In contrast, the defense of the L2NNN models remain constantwhen the attacks are allowed more iterations, specifically MNIST Models beyond 10K iterations and CIFAR-10 Models beyond 1000
8At github.com/MadryLab/mnist_challenge andgithub.com/MadryLab/cifar10_challenge. These models (Model 2’s in Tables 1 and 2) were built by adversarial training withL∞-bounded adversaries (Madry et al., 2017). To the best of our knowledge, Tsipras et al. (2019) from the same lab is the only paper in the literature that reports on models trained withL2-bounded adversaries, and it reports that training withL2-bounded adversaries resulted in weakerL2 robustness than theL2 robustness results from training withL∞-bounded adversaries in Madry et al. (2017). Therefore we choose to compare against the best available models, even though they were trained withL∞-bounded adversaries. Note also that our own Model 4’s in Tables 1 and 2 are trained with the sameL∞-bounded adversaries.
9In reading Tables 1 and 2, it is worth remembering that the norm of after-t ack accuracy is zero, and for example the 7.6% on MNIST is currently the state of the art.
iterations. The reason is that L2NNN classifiers achieve their defense by creating a confidence gap between the largest logit and the rest, and that half of this gap is a lower bound ofL2-norm of distortion to the input data in order to change the classification. Hence L2NNN’s defense comes from a minimum-distortion guarantee. Although adversarial training alone may also increase the minimum distortion limit for misclassification, as suggested in Carlini et al. (2017) for a small network, that limit likely does not reach the levels used in Tables 1 and 2 and hence the defense depends on how likely the attacker can reach a lower-distortion misclassification. Consequently when the attacks are allowed to make more attempts the defense with guarantee stands while the other diminishes.
For both MNIST and CIFAR-10, adding adversarial training boosts the robustness of Model 4. We hypothesize that adversarial training lowers local Lipschitz constants in certain parts of the input space, specifically around the training images, and therefore makes local robustness guarantees larger (Hein & Andriushchenko, 2017). To test this hypothesis on MNIST Models 3 and 4, we measure the averageL2-norm of their Jacobian matrices, averaged over the first 1000 images in the test set, and the results are 1.05 for Model 3 and 0.83 for Model 4. Note that theL2-norm of Jacobian can be greater than 1 for multi-L2NNN classifiers. These measur ments are consistent with, albeit does not prove, the hypothesis.
To test the effects of various components of our method, we build models for each of which we disable a different technique during training. The results arereported in Table 3. To put the confidence gap values in context, our MNIST Model 3 has an average gap of 2.8. The first one is without weight regularization of Section 2.1 and it becomes an ordinary network which has little defense against adversarial attacks; its large average confidence gap is meaningless. For the second one we remove the third loss term (6) and for the third one we replace norm-pooling with regular max-pooling, both resulting in smaller average confidence gap and less defenseagainst attacks. For the fourth one, we replace two-sided ReLU with regular ReLU, and this leads to degradation in nominal accuracy, average confidence gap and robustness. Parseval networks (Cisseet al., 2017) can be viewed as models withoutLc term, norm-pooling or two-sided ReLU, and with a more restrictive scheme for weight matrix regularization.
Model 3 in Table 1 and the second row of Table 3 are two points along a trade-off curve that are controllable by varying hyperparameterω in loss function (3). Other trade-off points have nominal accuracy and under-attack accuracy of (98.8%,19.1%), (98.4%,22.6%) and (97.9%,24.7%) respectively. Similar trade-offs have been reported by other robustness works including adversarial training (Tsipras et al., 2019) and adversarial polytope (Wong etal., 2018). It remains an open question whether such trade-off is a necessary part of life, and please see Section 3.3 for further discussion on the L2NNN trade-off.
Although we primarily focus on defending againstL2-bounded adversarial attacks in this work, we achieve some level of robustness againstL∞-bounded attacks as a by-product. Table 4 shows
our results, again measured with the attack code of Carlini &Wagner (2017a). Theǫ values match those used in Raghunathan et al. (2018); Kolter & Wong (2017); Madry et al. (2017). Our MNIST L∞ results are on par with Raghunathan et al. (2018); Kolter & Wong (2017) but not as good as Madry et al. (2017). Our CIFAR-10 Model 4 is on par with Madry et al. (2017) forL∞ defense.

heading: 3.2 MEANINGFUL OUTPUTS
text: This section discusses how to understand and utilize L2NNNs’ output values. We observe strong correlation between the confidence gap of L2NNN and the magnitude of distortion needed to force it to misclassify, and images are included in appendix.
In the next experiment, we sort test data by the confidence gapof classifier on each image. Then we divide the sorted data into 10 bins and report accuracy separately on each bin in Figure 2. We repeat this experiment for Model 2 (Madry et al., 2017) and our Model 3 of Tables 1 and 2. Note that the L2NNN model shows better correlation between confide ce and robustness: for MNIST our first bin is 95% robust and second bin is 67% robust. This indicates that the L2NNN outputs are much more quantitatively meaningful than those of ordinaryneural networks.
It is an important property that an L2NNN has an easily accessible measurement on how robust its decisions are. Since robustness is easily measurable, it can be optimized directly, and we believe that this is the primary reason that we can demonstrate the robustness results of Tables 1 and 2. This can also be valuable in real-life applications where we needto quantify how reliable a decision is.
One of the other practical implications of this property is that we can form hybrid models which use L2NNN outputs when the confidence is high and a different model when the confidence of the L2NNN is low. This creates another dimension of trade-off between nominal accuracy and robustness that one can take advantage of in an application.We built such a hybrid model for MNIST with the switch threshold of 1.0 and achieved nominal accuracy of 99.3%, where only 6.9% of images were delegated to the alternative classifier. We built such a hybrid model for CIFAR-10 with the switch threshold of 0.1 and achieved nominal accuracy of 89.4%, where 25% of images were delegated. To put these threshold values in context, MNIST Model 3 has an average gap of 2.8 and CIFAR-10 Model 3 has an average gap of 0.34. In otherwords, if for a data point the L2NNN confidence gap is substantially below average, theclassification is delegated to the alternative classifier, and this way we can recover nominal accuracy at a moderate cost of robustness.

heading: 3.3 GENERALIZATION VERSUS MEMORIZATION
text: This section studies L2NNN’s generalization through a noisy-data experiment where we randomize some or all MNIST training labels. The setup is similar to Zhang et al. (2017), except that we added three scenarios where 25%, 50% and 75% of training labels arecrambled.
Table 5 shows the comparison between L2NNNs and ordinary networks. Dropout rate and weightdecay weight are tuned for each WD/DR run, and each WD+DR+ES runuses the combined hyperparameters from its row. In early-stopping runs, 5000 training images are withheld as validation set and training stops when loss on validation set stops decreasing. The L2NNNs do not use weight decay, dropout or early stopping. L2NNNs achieve the best accur y in all three partially-scrambled
scenarios, and it is remarkable that an L2NNN can deliver 93.1% accuracy on test set when three quarters of training labels are random. More detailed data and discussions are in the appendix.
To illustrate why L2NNNs generalize better than ordinary networks from noisy data, we show in Table 6 trade-off points between accuracy and confidence gapon the 50%-scrambled training set. These trade-off points are achieved by changing hyperparametersω in (3) andv in (5). In a noisy training set, there exist data points that are close to each other yet have different labels. For a pair of such points, if an L2NNN is to classify both points correctly, he two confidence gaps must be small. Therefore, in order to achieve large average confidence gap, an L2NNN must misclassify some of the training data. In Table 6, as we adjust the loss function to favor larger average gap, the L2NNNs are forced to make more and more mistakes on the training set. The results suggest that loss is minimized when an L2NNN misclassifies some of the scrambled labels while fitting the 50% original labels with large gaps, and parameter training discovers this trade-off automatically. Hence we see in Table 6 increasing accuracies and gaps on the test set. The above is a trade-off between memorization (training-set accuracy) and generalization(training-set average gap), and we hypothesize that L2NNN’s trade-off between nominal accuracy and robustness, reported in Section 3.1, is due to the same mechanism. To be fair, dropout and early stopping are also able to sacrifice accuracy on a noisy training set, however they do so through differentmechanisms that tend to be brittle, and Table 5 suggests that L2NNN’s mechanism is superior. More discussions and the trade-off tables for 25% and 75% scenarios are in the appendix.
Another interesting observation is that the average confidece gap dramatically shrinks in the last row of Table 5 where the training is pure memorization. This is not surprising again due to training data points that are close to each other yet have different labels. The practical implication is that after an L2NNN model is trained, one can simply measure its averageconfidence gap to know whether and how much it has learned to generalize rather than to memorize the training data.

heading: 4 RELATED WORK
text: Adversarial defense is a well-known difficult problem (Szegedy et al., 2014; Goodfellow et al., 2014; Carlini & Wagner, 2017a; Athalye et al., 2018; Gilmer et al., 2018). There are many avenues
to defense (Carlini & Wagner, 2017b; Meng & Chen, 2017), and here we will focus on defense works that fortify a neural network itself instead of introducing additional components.
The mainstream approach has been adversarial training, where examples of successful attacks on a classifier itself are used in training (Tramèr et al., 2017; Zantedeschi et al., 2017). The work of Madry et al. (2017) has the best results to date and effectively flattens gradients around training data points, and, prior to our work, it is the only work that achieves sizable white-box defense. It has been reported in Carlini et al. (2017) that, for a small network, adversarial training indeed increases the average minimumL1-norm andL∞-norm of noise needed to change its classification. However, in view of results of Tables 1 and 2, adversarial-training results may be susceptible to strong attacks. The works of Drucker & Le Cun (1992); Ross & Doshi-Velez (2017) are similar to adversarial training in aiming to flatten gradients around training data set but use different mechanisms.
While the above approaches fortify a network around trainingdata points, others aim to bound a network’s responses to input perturbations over the entire input s ace. For example, Haber & Ruthotto (2017) models ResNet as an ordinary differential equation and derive stability conditions. Other examples include Kolter & Wong (2017); Raghunathan et al. (2018); Wong et al. (2018) which achieved provable guarantees againstL∞-bounded attacks. However there exist scalability issues with respect to network depth, and the reported results so far are against relatively weak attacks or low noise magnitude. As shown in Table 4, we can match their measuredL∞-bounded defense.
Controlling Lipschitz constants also regularizes a network over the entire input space. Szegedy et al. (2014) is the seminal work that brings attention to this topic. Bartlett et al. (2017) proposes the notion of spectrally-normalized margins as an indicator ofgeneralization, which are strongly related to our confidence gap. Pascanu et al. (2013) studies the role of th spectral radius of weight matrices in the vanishing and the exploding gradient problems. Yoshida & Miyato (2017) proposes a method to regularize the spectral radius of weight matrices and show its effect in reducing generalization gap. The work on Parseval networks (Cisse et al., 2017) showsthat it is possible to control Lipschitz constants of neural networks through regularization. The cor of their work is to constrain linear and convolution layer weights to be composed of Parseval tight frames, i.e., orthonormal filters, and thereby force the Lipschitz constant of these layers to be 1;they also propose to restrict aggregation operations. The reported robustness results of Cisse et al.(2017), however, are much weaker than those by adversarial training in Madry et al. (2017). We differ rom Parseval networks in a number of ways. Our linear and convolution layers do not require filtrs to be orthogonal to each other and subsume Parseval layers as a special case, and therefore provide more freedom to parameter training. We use non-standard techniques, e.g. two-sided ReLU, to modify various network components to maximize confidence gaps while keeping the network nonexpansive, and we propose a new loss function for the same purpose. We are unable to obtain Parseval n tworks for a direct comparison, however it is possible to get a rough idea of what the comparison might be by looking at Table 3 which shows the impacts of those new techniques. The work of Hein & Andriushchenko (2017) makes an important point regarding guarantees provided by local Lipschitz constants, which helps explain many observations in our results, including why adversarial training on L2NNNs leads to lasting robustness gains. The regularization proposed by Hein & Andriushchenko (2017) however is less practical and again introduces reliance on the coverage of training data points.

heading: 5 CONCLUSIONS AND FUTURE WORK
text: In this work we have presentedL2-nonexpansive neural networks which are well-conditionedsystems by construction. Practical techniques are developed for building these networks. Their properties are studied through experiments and benefits demonstrated, including that our MNIST and CIFAR-10 classifiers exceed the state of the art in robustnesagainst white-box adversarial attacks, that they are robust against partially random training labels, and that they output confidence gaps which are strongly correlated with robustness and generalization. There are a number of future directions, for example, other applications of L2NNN, L2NNN-friendly neural network architectures, and the relation between L2NNNs and interpretability.

heading: B MNIST IMAGES
text: Let us begin by showing MNIST images with the largest confidence gaps in Figure 3 and those with the smallest confidence gaps in Figure 4. They include images before and after attacks as well as Model 3’s confidence gap, the misclassified label andL2-norm of the added noise. The images with large confidence gaps seem to be ones that are most different from other digits, while some
of the images with small confidence gaps are genuinely ambiguous. It’s worth noting the strong correlation between the confidence gap of L2NNN and the magnitude of distortion needed to force it to misclassify. Also note that our guarantee states that the minimumL2-norm of noise is half of the confidence gap, but in reality the needed noise is much stronge than the guarantee. The reason is that the true local guarantee is in fact larger due to localLipschitz constants, as pointed out by Hein & Andriushchenko (2017).
Figure 5 shows additional details regarding the example in Figure 1. The first image is the original image of a zero. The second image is an attack on Model 2 (Madryet al., 2017) found after 1K iterations, with noiseL2-norm of 4.4. The third is one found after 10K iterations for Model 2, with noiseL2-norm of 2.1. The last image is the best attack on our Model 3 found after one million iterations, with noiseL2-norm of 3.5. These illustrates the trend shown in Table 1 that the defense by adversarial training diminishes as the attacks are allowed more iterations, while L2NNNs withstand strong attacks and it requires more noise to fool an L2NNN. It’s worth noting that the slow degradation of Model 2’s accuracy is an artifact of the attacker (Carlini & Wagner, 2017a): when gradients are near zero in some parts of the input space, which is true for MNIST Model 2 due to adversarial training, it takes more iterations to make progress. It is conceivable that, with a more advanced attacker, Model 2 could drop quickly to 7.6%. What truly matter are the robust accuracies where we advance the state of the art from 7.6% to 24.4%.

heading: C DETAILS OF SCRAMBLED-LABEL EXPERIMENTS
text: For ordinary networks in Table 5, we use two network architectures. The first has 4 layers and is the architecture used in Madry et al. (2017). The second has 22 layers and is the architecture of Models 3 and 4 in Table 1, which includes norm-pooling and two-sidedR LU. Results of ordinary networks using these two architectures are in Tables 7 and 8 respectively. The ordinary-network section of Table 5 is entry-wise max of Tables 7 and 8.
In Tables 7 and 8, dropout rate and weight-decay weight are tun d for each WD/DR run, and each WD+DR+ES run uses the combined hyperparameters from its row.In early-stopping runs, 5000 training images are withheld as validation set and trainingstops when loss on validation set stops decreasing. Each ES or WD+DR+ES entry is an average over ten runs to account for randomness of the validation set. The L2NNNs do not use weight decay, dropout or early stopping.
Table 9 shows L2NNN trade-off points between accuracy and cofidence gap on the 25%-scrambled training set. Table 10 shows L2NNN trade-off points betweenaccuracy and confidence gap on
the 75%-scrambled training set. Like Table 6, they demonstrate the trade-off mechanism between memorization (training-set accuracy) and generalization(training-set average gap).
To be fair, dropout and early stopping are also able to sacrifice accuracy on a noisy training set. For example, the DR run in the 50%-scrambled row in Table 7 has67.5% accuracy on the training set and 72.6% on the test set. However, the underlying mechanisms are very different from that of L2NNN. Dropout (Srivastava et al., 2014) has an effect of data augmentation, and, with a noisy training set, dropout can create a situation where the effective data complexity exceeds the network capacity. Therefore, the parameter training is stalled at alowered accuracy on the training set, and we get better performance if the model tends to fit more of original labels and less of the scrambled labels. The mechanism of early stopping is straightforwardan simply stops the training when it is mostly memorizing scrambled labels. We get better performance from early stopping if the parameter training tends to fit the original labels early. These mechanisms from dropout and early stopping are both brittle and may not allow parameter training enough opportunity to learn from the useful data points with original labels. The comparison in Table 5 suggests that they are inferior to L2NNN’s trade-off mechanism as discussed in Section 3.3 andillustrated in Tables 6, 9 and 10. The L2NNNs in this paper do not use weight decay, dropout or earlystopping, however it is conceivable that dropout may be complementary to L2NNNs.

heading: D PROOFS
text: Lemma 1. Let g (x) denote a single-L2NNN classifier’s confidence gap for an input data pointx. The classifier will not change its answer as long as the inputx is modified by no more than an L2-norm ofg (x) / √ 2.
Proof. Let y (x) = [y1 (x) , y2 (x) , · · · , yK (x)] denote logit vector of a single-L2NNN classifier for an input data pointx. Letx1 andx2 be two input vectors such that the classifier outputs different labelsi andj. By definitions, we have the following inequalities:
yi (x1)− yj (x1) ≥ g (x1) yi (x2)− yj (x2) ≤ 0
(12)
Because the classifier is a single L2NNN, it must be true that:
‖x2 − x1‖2 ≥ ‖y (x2)− y (x1) ‖2
≥ √ (yi (x2)− yi (x1))2 + (yj (x2)− yj (x1))2
=
√
(yi (x1)− yi (x2))2 + (yj (x2)− yj (x1))2
≥
√
(yi (x1)− yi (x2) + yj (x2)− yj (x1))2 2
=
√
((yi (x1)− yj (x1)) + (yj (x2)− yi (x2)))2 2
≥
√
(g (x1) + 0) 2
2
= g (x1) / √ 2
(13)
Lemma 2. Let g (x) denote a classifier’s confidence gap for an input data pointx. Letd (x1,x2) denote theL2-distance between the output logit-vectors for two input points x1 andx2 that have different labels and that are classified correctly. Then this condition holds:g (x1) + g (x2) ≤√ 2 · d (x1,x2).
Proof. Let y (x) = [y1 (x) , y2 (x) , · · · , yK (x)] denote logit vector of a classifier for an input data pointx. Let i andj be the labels forx1 andx2. By definitions, we have the following inequalities:
yi (x1)− yj (x1) ≥ g (x1) yj (x2)− yi (x2) ≥ g (x2)
(14)
Therefore, d (x1,x2) , ‖y (x2)− y (x1) ‖2
≥ √ (yi (x2)− yi (x1))2 + (yj (x2)− yj (x1))2
=
√
(yi (x1)− yi (x2))2 + (yj (x2)− yj (x1))2
≥
√
(yi (x1)− yi (x2) + yj (x2)− yj (x1))2 2
=
√
((yi (x1)− yj (x1)) + (yj (x2)− yi (x2)))2 2
≥
√
(g (x1) + g (x2)) 2
2
= g (x1) + g (x2)√
2
(15)
Lemma 3. For anya ≥ 0, b ≥ 0, p ≥ 1, the following inequality holds:ap + bp ≤ (a+ b)p.
Proof. If a andb are both zero, the inequality holds. If at least one ofa andb is nonzero:
ap + bp = (a+ b) p ·
(
a
a+ b
)p
+ (a+ b) p ·
(
b
a+ b
)p
≤ (a+ b)p · a a+ b + (a+ b) p · b a+ b = (a+ b) p
(16)
Lemma 4. Let f(x) be a nonexpansive and monotonically increasing scalar functio . Define a function fromR to R2: h(x) = [f(x), f(x) − x]. Thenh(x) is nonexpansive with respect to any Lp-norm.
Proof. For anyx1 > x2, by definition we have the following inequalities:
f(x1)− f(x2) ≥ 0 f(x1)− f(x2) ≤ x1 − x2
(17)
For anyp ≥ 1, invoking Lemma 3 witha = f(x1)− f(x2) andb = x1 − x2 − f(x1) + f(x2), we have:
((f(x1)− f(x2))p + (x1 − x2 − f(x1) + f(x2))p ≤ (x1 − x2)p
(((f(x1)− f(x2))p + (x1 − x2 − f(x1) + f(x2))p)1/p ≤ x1 − x2 (|f(x1)− f(x2)|p + |(f(x1)− x1)− (f(x2)− x2)|p)1/p ≤ x1 − x2
‖h(x1)− h(x2)‖p ≤ x1 − x2
(18)
Lemma 5. Norm-pooling within each pooling window is a nonexpansive map with respect toL2norm.
Proof. Let x1 andx2 be two vectors with the size of a pooling window. By triangle in quality, we have
‖x1 − x2‖2 + ‖x1‖2 ≥ ‖x2‖2 ‖x1 − x2‖2 + ‖x2‖2 ≥ ‖x1‖2
(19)
Therefore, ‖x1 − x2‖2 ≥ ‖x2‖2 − ‖x1‖2 ‖x1 − x2‖2 ≥ ‖x1‖2 − ‖x2‖2
(20)
Therefore, ‖x1 − x2‖2 ≥ |‖x1‖2 − ‖x2‖2| (21)
Lemma 6. Let g (x) denote a multi-L2NNN classifier’s confidence gap for an inputdata pointx. The classifier will not change its answer as long as the inputx is modified by no more than an L2-norm ofg (x) /2.
Proof. Let y (x) = [y1 (x) , y2 (x) , · · · , yK (x)] denote logit vector of a multi-L2NNN classifier for an input data pointx. Letx1 andx2 be two input vectors such that the classifier outputs different labelsi andj. By definitions, we have the following inequalities:
yi (x1)− yj (x1) ≥ g (x1) yi (x2)− yj (x2) ≤ 0
(22)
For a multi-L2NNN classifier, each logit is a nonexpansive function of the input, and it must be true that:
‖x2 − x1‖2 ≥ |yi (x1)− yi (x2)| ‖x2 − x1‖2 ≥ |yj (x2)− yj (x1)|
(23)
Therefore,
‖x2 − x1‖2 ≥ |yi (x1)− yi (x2)|+ |yj (x2)− yj (x1)|
2
≥ |yi (x1)− yi (x2) + yj (x2)− yj (x1)| 2 = |(yi (x1)− yj (x1)) + (yj (x2)− yi (x2))|
2
≥ |g (x1) + 0| 2
= g (x1) /2
(24)

Review summaries:
This paper presents a combination of methods that, together, yield neural networks that are robust to small changes in L2 distance. The main idea is to ensure that changing the input by a bounded L2 distance never changes the output by more than the same L2 distance. Then, the difference between the highest-scoring class and the second-highest scoring class provides a bound on how much the input must change. The trivial way to do this is to rescale the final output layer so that all of the magnitudes are very small; however, this would give no additional robustness at all. To counteract this, the paper introduces several additional heuristics for increasing the gap between the highest-scoring class and the second-highest scoring one. Adversarial training can be used to make the models even more robust. 

The paper presents techniques for training a non expansive network, which keeps the Lipchitz constant of all layers lower than 1. While being non-expansive, means are taken to preserve distance information better than standard networks. The architectural changes required w.r.t standard networks are minor, and the most interesting changes are made to the loss minimized. The main claim of the paper is that the method is robust against adversarial attacks of a certain kind. However, the results presented show that a) such robustness comes at a high cost of accuracy for standard examples, and b) even though the network is preferable to a previous alternative in combating adversarial examples, the accuracy obtained in the face of adversarial attacks is too low to be of practical value. Other properties of the networks, explored empirically, are that the confidence of the prediction is indicative of robustness (to adversarial attacks) and that the networks learn better in the presence of high label noise.