Limitations of the Lipschitz constant as a defense against adversarial examples

Introduction

Machine learning models, such as deep neural networks (DNNs), have been remarkably successful in performing many tasks . However, it has been shown that they fail catastrophically when very small distortions are added to normal data examples . These adversarial examples are easy to produce , transfer from one model to another , and are very hard to detect .

Many methods have been proposed to address this problem, but most have been quickly overcome by new attacks . This cycle has happened regularly enough that the burden of proof is on the defender that her or his defense will hold up against future attacks. One promising approach to meet this burden is to compute and optimize a certificate: a guarantee that no attack of a certain magnitude can change the classifier’s decision for a large majority of examples.

In order to provide such a guarantee, one must be able to bound the possible outputs for a region of input space. This can be done for the region around a specific input or by globally bounding the sensitivity of the function to shifts on the input, i.e., the function’s Lipschitz constant . Once the output is bounded for a given input region, one can check whether the class changes. If not, there is no adversarial example in the region. If the class does change, the model can alert the user or safety mechanisms to the possibility of manipulation.

We argue in this paper that despite the achievements reported in , Lipschitz-based approaches suffer from some representational limitations that may prevent them from achieving higher levels of performance and being applicable to more complicated problems. We suggest that directly addressing these limitations may lead to further gains in robustness.

This paper is organized as follows: Section 2 defines the Lipschitz constant and shows that classifiers with strong Lipschitz-based guarantees exist. Section 3 describes a simple method for computing a Lipschitz constant for deep neural networks, while Section 4 presents experimental and theoretical limitations for this method. Section 5 describes an alternative method for computing a Lipschitz constant and presents some of its limitations. Finally, Section 6 presents conclusions and a long term goal for future research.

Lipschitz Bounds

We now define the Lipschitz constant referenced throughout this paper.

Let a function $f$ be called $k$-Lipschitz continuous if

where $d_{X}$ and $d_{Y}$ are the metrics associated with vector spaces $X$ and $Y$, respectively.

Loosely speaking, a Lipschitz constant $k$ is a bound on the slope of $f$: if the input changes by $\epsilon$, the output changes by at most $k\epsilon$. If there is no value $\hat{k}$ where $f$ is $\hat{k}$-Lipschitz continuous and $\hat{k}<k$, then we say $k$ is the minimal Lipschitz constant. In this paper, we restrict our analysis to Minkowski $L_{p}$ spaces with distance metric $\|\cdot\|_{p}$. We now show that global Lipschitz constants can in principle be used to provide certificates far exceeding the current state-of-the-art, and thus are worthy of further development.

We relegate the full proof to appendix A.1, but we define a function meeting the criteria of the proposition that can be constructed for any dataset:

where $x^{+}$ and $x^{-}$ are the closest vectors to $x$ in $\mathcal{D}$ with $y=1$ and $y=-1$, respectively.

The function $f$ described above shows that the Lipschitz method can be used to provide a robustness guarantee against any perturbation of magnitude less than $\frac{c}{2}$. This can be extended to a multi-class setting in a straightforward manner by using a set of one vs. all classifiers. Table 1 shows the distance to the closest out-of-class example for the 95th percentile of samples; i.e., 95% of samples are at least $c$ away from the nearest neighbor of a different class. Proposition 2.2 implies the existence of a classifier that is provably robust for 95% of samples against perturbations of magnitude $\frac{c}{2}$. This bound would far exceed the certifications offered by current methods, i.e., , and even the (non-certified) adversarial performance of .

It is important to note that the existence of a $\frac{c}{2}$-Lipschitz function in Proposition 2.2 does not say anything about how easy it is to learn such a function from examples that generalizes to new ones. Indeed, the function described in the proof is likely to generalize poorly. However, we argue that current methods for optimizing the Lipschitz constant of a neural network suffer much more from underfitting than overfitting: training and validation certificates tend to be similar, and adding model capacity and training iterations do not appear to materially improve the training certificates. This suggests that we need more powerful models. The remainder of this paper is focused on how one might go about developing more powerful models.

Atomic Lipschitz Constants

The simplest method for constructing a Lipschitz constant for a neural network composes the Lipschitz constants of atomic components. If $f_{1}$ and $f_{2}$ are $k_{1}$- and $k_{2}$-Lipschitz continuous functions, respectively, and $f(x)=f_{2}(f_{1}(x))$, then $f$ is $k$-Lipschitz continuous where $k=k_{1}k_{2}$. Applying this recursively provides a bound for an arbitrary neural network.

For many components, we can compute the minimal Lipschitz constant exactly. For linear operators, $l_{W,b}(x)=Wx+b$, the minimal Lipschitz constant is given by the matrix norm of $W$ induced by $L_{p}$:

For $p=\infty$, this is equivalent to the largest magnitude row of $W$:

The $L_{2}$ norm of $W$ is known as its spectral norm and is equivalent to its largest singular value. The element-wise ReLU function $ReLU(x)=max(x,0)$ has a Lipschitz constant of 1 regardless of the choice of $p$. Therefore, for a neural network $f$ composed of $n$ linear operators $l_{W_{1},b_{2}},...,l_{W_{n},b_{n}},$ and ReLUs, a Lipschitz constant $k$ is provided by

Several recent papers have utilized this concept or an extension of it to additional layer types. uses it to analyze the theoretical sensitivity of deep neural networks. and enforce constraints on the singular values of matrices as a way of increasing robustness to existing attacks. Finally, penalizes the spectral norms of matrices and uses equation 6 to compute a Lipschitz constant for the network.

Limitations of Atomic Lipschitz Constants

One might surmise that this approach can solve the problem of adversarial examples: compose enough layers together with the right balance of objectives, overcoming whatever optimization difficulties arise, and one can train classifiers with high accuracy, guaranteed low variability, and improved robustness to attacks. Unfortunately, this does not turn out to be the case, as we will show first experimentally and then theoretically.

First, we can observe the limits of this technique in a shallow setting. We train a two layer fully connected neural network with 500 hidden units $f=l_{W_{2},b_{2}}\circ ReLU\circ l_{W_{1},b_{1}}$ on the MNIST dataset. We penalize $\|W_{1}\|_{p}\|W_{2}\|_{p}$ with weight $\lambda_{p}$. We denote the score for class $i$ as $f_{i}(x)$ and the computed Lipschitz constant of the difference between $f_{i}(x)$ and $f_{j}(x)$ as $k_{ij}$. We certify the network for example $x$ with correct class $i$ against a perturbation of magnitude $\epsilon$ by verifying that $f_{i}(x)-f_{j}(x)-k_{ij}\epsilon>0$ for $i\neq j$.

Figures 1 (a) and (b) show results for $L_{\infty}$ and $L_{2}$, respectively. In both cases, adding a penalty provides a larger region of certified robustness, but increasing the penalty hurts performance on unperturbed data and eventually ceases to improve the certified region. This was true for both test and training (not shown) data. This level of certification is considerably weaker than our theoretical limit from Proposition 2.2.

There also does not appear to be much certification benefit to adding more layers. We extended the methodology to multi-layer networks and show the results in figures 1 (c) and (d). Using the $\lambda_{\infty}$ penalty proved difficult to optimize for deeper networks. The $\lambda_{2}$ penalty was more successful, but only saw a mild improvement over the shallow model. The results in (d) also compare favorably to those of , which uses a 4 layer convolutional network.

2 Theoretical Limitations

We now consider the set of neural networks with a given atomic Lipschitz bound and the functions it can compute. This set of functions is important because it limits how well a neural network can split a dataset with particular margins, and thus how strong the certificate can be.

Let $\mathcal{A}_{k}^{p}$ be the set of neural networks with an atomic Lipschitz bound of k in $L_{p}$ space:

We focus our analysis here on $L_{\infty}$ space. To show the limitations of $\mathcal{A}_{k}^{\infty}$, consider the simple 1-Lipschitz function $f(x)=|x|$. Expressing $f$ with ReLU’s and linear units is simple exercise, shown in figure 2. However, since

the neural network in figure 2 is a member of $\mathcal{A}_{2}^{\infty}$, but not $\mathcal{A}_{1}^{\infty}$. This is only one possible implementation of $|x|$, but as we will show, the atomic component method cannot express this function with a Lipschitz bound lower than 2, and the situation gets worse as more non-linear variations are added.

We now provide two definitions that will help delineate the functions that the neural networks in $\mathcal{A}_{k}^{\infty}$ can compute.

where $\mathcal{T}$ is the set of partitions of the interval $[a,b]$.

The total variation captures how much a function changes over its entire domain, which we will use on the gradients of neural networks. $V_{-\infty}^{\infty}$ is finite for neural network gradients, as the gradient only changes when a ReLU switches states, and this can only happen a finite number of times for finite networks. Clearly, for the slope of the absolute value function, this quantity is 2: the slope changes from -1 to 1 at $x=0$.

and call it the intrinsic variability of $f$.

As we will show, the intrinsic variability is a quantity that is nonexpansive under the ReLU operation. The intrinsic variability the slope of the absolute value function is 4: we add the magnitude of the slopes at the extreme points, 1 in each case, to the total variation of 2. We now begin a set of proofs to show that $\mathcal{A}_{k}^{\infty}$ is limited in the functions it can approximate. This limit does not come from the Lipschitz constant of a function $f$, but by the intrinsic variability of its derivative, $f^{\prime}$.

For a linear combination of functions $f(x)=\sum_{i}w_{i}f_{i}(x)$,

Let $f(t)$ be a function where $f^{\prime}(t)$ is eventually constant. For the ReLU activation function $g(t)=max(f(t),0)$,

A function in $\mathcal{A}_{k}^{\infty}$ has a hard limit on the intrinsic variability of its slope along a line through its input space. If we try to learn the absolute value function while penalizing the bound $k$, we will inevitably end up with training objectives that are in direct competition with one another. One can imagine more difficult cases where there is some oscillation in the data manifold and the bounds deteriorate further: for instance $sin(x)$ is also 1-Lipschitz, but can only be approximated with arbitrarily small error by a member of $\mathcal{A}_{\infty}^{\infty}$. While this limit is specific to $\mathcal{A}_{k}^{\infty}$, since $\|W\|_{2}\leq\|W\|_{\infty}$, it also provides a limit to $\mathcal{A}_{k}^{2}$.

Paired-layer Lipschitz Constants and Their Limitations

We have shown the limitations of the atomic bounding method both experimentally and theoretically, so naturally we look for other approaches to bounding the Lipschitz constant of neural network layers. A fairly successful approach was given by . presents a method for bounding a fully connected neural network with one hidden layer and ReLU activations, which yielded impressive performance on the MNIST dataset. This approach optimizes the weights of the two layers in concert, so we call it the paired-layer approach. The paper does not attempt to extend the method to deeper neural networks, but it can be done in a relatively straightforward fashion.

Ignoring biases for notational convenience, a two-layer neural network with weights $W_{1}$ and $W_{2}$ can be expressed

where $s=W_{1}x>0$. We consider a single output, although extending to a multi-class setting is straightforward. If $s$ were fixed, such a network would be linear with Lipschitz constant $\|W_{2}diag(s)W_{1}\|_{p}$. accounts for a changeable $s$ by finding the assignment of $s$ that maximizes the $L_{\infty}$ Lipschitz constant and using this as a bound for the real Lipschitz constant:

They convert this problem to a mixed integer quadratic program and bound it in a tractable and differential manner using semi-definite programming, the details of which are explained in . We can add a penalty on this quantity to the objective function to find a model with relatively high accuracy and low Lipschitz constant. We did not have access to the training procedure developed by , but we were able to closely replicate their results on MNIST and compare them to the atomic bounding approach, shown in figure 3 (a).

2 Theoretical Benefits and Limitations of Paired-layer Approach

Figure 3 shows that there are practical benefits to the paired-layer approach, and we can also show a corresponding increase in expressive power. Similar to $\mathcal{A}_{k}^{p}$, we define a set of neural networks $\mathcal{M}_{k}$, although we will restrict the definition to 2 layer networks in $L_{\infty}$ space:

Let $\mathcal{M}_{k}$ be the set of two-layer neural networks with a paired-layer Lipschitz bound of k in $L_{\infty}$ space:

$\mathcal{M}_{k}$ can express functions that $\mathcal{A}_{k}^{\infty}$ cannot. For example, we can apply the paired-layer method to the neural network in figure 2 by enumerating the different cases. In this case the bound is tight, meaning that the neural network is in $\mathcal{M}_{1}$. From Theorem 4.9, we know that this function cannot be expressed by any member of $\mathcal{A}_{1}^{\infty}$. It is easy to see that any two layer neural network in $\mathcal{A}_{k}^{\infty}$ is also in $\mathcal{M}_{k}$, so we can say confidently that the paired-layer bounds are tighter than atomic bounds.

This additional expressiveness is not merely academic. Figure 3 (b) shows the output of the networks from (a) along a particular line in input space, scaled by the given Lipschitz bound. The function learned by the paired-layer method does in fact exhibit an intrinsic variability larger than $2k$, meaning that function cannot be represented by a network in $\mathcal{A}_{k}^{\infty}$. This suggests that the gains in performance may be coming from the increased expressiveness of the model family.

It is still easy to construct functions for which the paired-layer bounds are loose, however. Figure 4 shows a 1-Lipschitz function and a corresponding neural network that is only in $\mathcal{M}_{2}$. The problem arises from the fact that the two hidden units cannot both be on, but the quadratic programming problem in equation 17 implies that they can. For a 1-D problem, the bound essentially adds up the magnitudes of the paths with positive weights and the paths with negative weights and takes the maximum. A higher dimensional problem can be reduced to a 1-D problem by considering arbitrary lines through the input space.

The expressive limitations of $\mathcal{M}_{k}$ are apparent when we consider its components. Any neural network in $\mathcal{M}_{k}$ is a sum of combinations of the four basic forms in figure 5, with various biases and slopes. The sum of the slope magnitudes from the positive paths can be no greater than $k$, and likewise for the negative paths. Each form has a characteristic way of affecting the slope at the extremes and changing the slope. For instance form (a) adds a positive slope at $+\infty$ as well as a positive change in $f^{\prime}$. From here we can see that there is still a connection between the total variation and extreme values of $f^{\prime}$ and the bound $k$. While the paired-layer bounds are better than the atomic ones, they still become arbitrarily bad for e.g., oscillating functions.

Conclusions

We have presented a case that existing methods for computing a Lipschitz constant of a neural network suffer from representational limitations that may be preventing them from considerably stronger robustness guarantees against adversarial examples. Addressing these limitations should enable models that can, at a minimum, exhibit strong guarantees for training data and hopefully extend these to out-of-sample data. Ideally, we envision universal Lipschitz networks: a family of neural networks that can represent an arbitrary k-Lipschitz function with a tight bound. The development of such a family of models and methods for optimizing them carries the potential of extensive gains in adversarial robustness.

This research was partially sponsored by the U.S. Army Research Laboratory and was accomplished under Cooperative Agreement Number W911NF-13-2-0045 (ARL Cyber Security CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on.

References

Appendix A Proofs

where $x^{+}$ and $x^{-}$ are the closest vectors to $x$ in $\mathcal{D}$ with $y=1$ and $y=-1$, respectively. Since $||x^{+}-x^{-}||_{p}>c$, the conditions are mutually exclusive. When $y_{i}=1$ and $||\delta||_{p}<\frac{c}{2}$,

The inverse is true for $y_{i}=-1$, therefore $sign(f(x_{i}+\delta))=y_{i}$ holds for all $i$. $f$ is continuous at the non-differentiable boundaries between the piecewise conditions of $f$ and the selections of $x^{+}$ and $x^{-}$. Therefore, it suffices to show that each continuously differentiable piece is $\frac{2}{c}$-Lipschitz. Using Definition 2.1, we must show

For the first condition of $f$ with a fixed $x^{+}$, we get

which holds for $p\geq 1$ due to the Minkowski inequality. The same holds for the second condition. Since the third condition is constant, $f(x)$ must be $\frac{2}{c}$-Lipschitz and the proof is complete. ∎

A.2 Proof of Lemma 4.4

The triangle inequality gives us the following two inequalities

Let $T_{f^{\prime}}$ be a maximal partition for $V_{\infty}^{\infty}(f^{\prime})$, giving us

We complete the proof by substituting with (25) and (26) and reordering the terms :

A.3 Proof of Lemma 4.7

Let $[t_{-},t_{+}]$ be an interval outside of which $f^{\prime}(t)$ is constant. Assume that $f^{\prime}(t)>0$ for $t\in[t_{-},t_{+}])$. In this case,

If $f^{\prime}(-\infty)>0$ then at some point $t<t_{-}$, $f(t)=0$ and $g^{\prime}$ transitions from $f^{\prime}(-\infty)$ to 0. Otherwise for $t<t_{-}$, $g^{\prime}(t)=f^{\prime}(t)$. Therefore,

Putting the different intervals together, we get

So the statement holds when our assumption about $f$ is met. To address cases where $f$ has negative values in $[t_{-},t_{+}]$, consider an interval $(t_{1},t_{2})$ where $g(t_{1})=f(t_{1}),g(t_{2})=f(t_{2}),g(t)\neq f(t)fort_{1}<t<t_{2}$. We note that $f^{\prime}(t_{1})<0$ and $f^{\prime}(t_{2})>0$. Since $f^{\prime}$ must transition from $f^{\prime}(t_{1})$ to $f^{\prime}(t_{2})$, over $(t_{1},t_{2})$,

Since $g^{\prime}$ transitions from $f^{\prime}(t_{1})$ to 0 to $f^{\prime}(t_{2})$ over $(t_{1},t_{2})$ so,

Applying this to all such intervals gives us

and therefore $I(g^{\prime})\leq I(f^{\prime})$

A.4 Proof of Theorem 4.9

Combining the definition of $h_{W_{0},b_{0}}$ with Definition 4.1, we can see that $h_{W_{0},b_{0}}=l_{W_{n},b_{n}}\circ\dots\circ ReLU\circ l_{W_{1},b_{1}}\circ l_{W_{0},b_{0}}$ and $\prod_{i=0}^{n}\|W_{i}\|_{\infty}\leq k$. We consider the additional linear transform as the zeroth layer of a modified network. Consider unit $u$ in the zeroth layer as a function $\sigma_{0,u}(t)$. $\sigma_{0,j}^{\prime}(t)$ is constant, with

where $w^{i}_{u,v}$ is element $(u,v)$ of $W_{i}$. Therefore

We also have $\forall t,\lvert\sigma_{0,u}^{\prime}\rvert=\lvert w^{0}_{u,1}\rvert$, so by Definition 4.3

We recursively define functions for each unit in layers $1$ to $n$:

Applying Lemma 4.7 and noting that a function composed of ReLU and linear operators is eventually constant, we get

Finally, we conclude the proof by recursively applying (45) on the base case in (40) to yield