Training robust neural networks using Lipschitz bounds

I Introduction

Neural networks (NNs) and deep learning have lately been successful in many fields , where they are mostly used for classification and segmentation problems, as well as in reinforcement learning . The main advantages of NNs are that they can be trained straightforwardly using backpropagation and as universal function approximators they have the capability to represent complex nonlinearities. While NNs are powerful and broadly applicable they lack rigorous guarantees which is why they are not yet applied to safety-critical applications such as medical devices and autonomous driving. Adversarial attacks can easily deceive an NN by adding imperceptible perturbations to the input which is a problem that has recently been tackled increasingly in a number of different ways such as adversarial training and defensive distillation . Another promising approach is to show that an NN is provably robust against norm-bounded adversarial perturbations , e.g. by maximizing margins , while yet another one is to use Lipschitz constants as a robustness measure that indicate the sensitivity of the output to perturbations in the input . There are a number of other regression methods that provide guaranteed and optimized upper bounds on the Lipschitz constant such as nonlinear set membership predictions, kinky inference and Lipschitz interpolation . Based on this notion of Lipschitz continuity, we propose a framework for training of robust NNs that encourages a small Lipschitz constant by including a regularizer or respectively, a constraint on the NN’s Lipschitz constant.

Trivial Lipschitz bounds of NNs can be determined by the product of the spectral norms of the weights which is used during training in . Similar to , we use the Lipschitz constant as a regularization functional. However, they use local Lipschitz constants whereas we penalize the global one. In , Fazlyab et al. propose an interesting new estimation scheme for more accurate upper bounds on the Lipschitz constant than the weights’ spectral norms exploiting the structure of the nonlinear activation functions. Activation functions are gradients of convex potential functions, and hence monotonically increasing functions with bounded slopes, which is used in to state the property of slope-restriction as an incremental quadratic constraint and then formulate a semidefinite program (SDP) that determines an upper bound on the Lipschitz constant. In , three variants of the Lipschitz constant estimation framework are proposed trading off accuracy and computational tractability. In this paper, we disprove by counterexample the most accurate approach presented in , and we employ the other approaches for training of robust NNs. More specifically, we include the SDP-based Lipschitz bound characterization of in the training procedure via an Alternating Direction Method of Multipliers (ADMM) scheme. We present two versions of the training method, (i) a regularizer rendering the Lipschitz constant small and (ii) enforces guaranteed upper bounds on the Lipschitz constant during training.

The main contributions of this manuscript are the two training procedures for robust NNs based on the notion of Lipschitz continuity, using a tight upper bound on the Lipschitz constant. In addition, we show that the method for Lipschitz constant estimation for NNs that was recently proposed in requires a modification for the least conservative choice of decision variables. This manuscript is organized as follows. In Section II, we introduce Lipschitz constant estimation for NNs based on but disprove their most accurate Lipschitz estimator. In Section III, we present a training procedure with Lipschitz regularization and outline the setup of the optimization problem that is solved using ADMM. Subsequently, we introduce a variation of the proposed procedure that allows to enforce Lipschitz bounds on the NN and finally, we discuss the convergence and the computational tractability of the ADMM scheme. In Section IV, we provide two examples on which we successfully apply the proposed training procedures.

II Lipschitz constant estimation

In this section, we briefly introduce robustness in the context of neural networks. We then state a method to estimate the Lipschitz constant of an NN based on and finally argue why one of the methods for Lipschitz constant estimation proposed in is incorrect.

The smallest $L$ for which (1) holds is the Lipschitz constant $L^{*}$. If the input changes from $x$ to $y$, the Lipschitz constant gives an upper bound on how much the output $f$ changes. Hence, a low Lipschitz constant indicates low sensitivity which is equivalent to high robustness. In this work, we aim to minimize the Lipschitz constant or respectively bound the Lipschitz constant from above during training to increase the robustness of the resulting NN.

Regularization, i.e., adding a penalty term to the objective function of the NN, is a prevalent measure in NN training in order to prevent overfitting. L2 regularization penalizes the squared norm of the weights and L1 regularization the weights’ L1 norm. Bounding the weights counteracts the fit of sudden peaks and outliers, promotes better generalization, and smoothens the resulting NN . Furthermore, the product of the spectral norms of the weights provides a trivial bound on an NN’s Lipschitz constant and consequently, L1 and L2 regularization improve the robustness of an NN in the sense of Lipschitz continuity. In this paper, we penalize a more accurate estimate of the Lipschitz constant, leading to a more direct and potentially more effective approach.

II-B Lipschitz constant estimation

In the following, we outline a method to estimate bounds on the Lipschitz constant of multi-layer NNs exploiting the slope-restricted structure of the nonlinear activation functions, as it was shown in . This method named LipSDP yields more accurate bounds than trivial bounds, i.e., the product of the spectral norms of the weights.

results in an incremental quadratic constraint for the stacked activations:

Suppose there exist $L^{2}>0$, $T\in\mathcal{D}_{n}$ such that

Then, (3) is globally Lipschitz continuous with Lipschitz bound $L\geq L^{*}$.

The proof directly follows from A.4 in , the extended version of . Note that this result differs from Theorem 2 in as $T$ in our case is a diagonal matrix. As we show in Section II-C, the result does not hold in general for the larger parametrization of $T$ provided in . The smallest value for the Lipschitz upper bound is determined by solving the SDP

where $T$ and $L^{2}$ serve as decision variables.

In the case of one hidden layer the matrix $P_{1}$ reduces to

II-C Counterexample for LipSDP with coupling

In , three versions of the method LipSDP for Lipschitz constant estimation are stated that reconcile accuracy of the Lipschitz bound and computational complexity of the method by adjusting the number of the decision variables in the SDP. In this section, we give an illustrative counterexample to show that Theorems 1 and 2 in are incorrect for the most accurate variant of LipSDP.

Theorem 2 in resembles Theorem 1 of this manuscript with the difference that in a set of symmetric coupling matrices

is introduced whereas we state Theorem 1 for a set of diagonal matrices $\mathcal{D}_{n}$. In the following, we give a minimal counterexample to show that, as suggested in this manuscript, a further restriction of the class of $T$ is required. For that purpose, consider an NN with one hidden layer of size $n_{1}=2$, input and output size $n_{0}=n_{2}=1$, activation function $\tanh$ and weights and biases

The resulting NN provides a good fit for the cosine function on $x\in[-\frac{\pi}{2},\frac{\pi}{2}]$ with a maximum deviation in the output of 0.0843. Therefore, the maximum slope of the cosine gives a good approximation of the Lipschitz constant of this NN, which is $\pm 1$ at $x=\pm\frac{\pi}{2}$, such that $L^{*}\approx 1$. However, the linear matrix inequality (LMI) (5) is feasible for arbitrarily small $L^{2}$ and $T=(e_{1}-e_{2})(e_{1}-e_{2})^{\top}\in\mathcal{T}_{n}$. An arbitrarily small $L$ is obviously no upper bound on the Lipschitz constant of a cosine like function, thus contradicting Theorem 1 in .

III Training robust NNs

In Section II-B, we stated a method that provides certificates on an NN’s Lipschitz constant. In this section, we employ these certificates to design a training procedure for robust NNs. The proposed approach allows us to directly regularize the Lipschitz constant during training, which is only possible indirectly in regularization methods such as L2 regularization. We present two versions of it, the first one allows for minimization of the upper bound on the Lipschitz constant and the second one allows to enforce a desired bound on the Lipschitz constant.

Eq. (6) can be used to assess an NN’s robustness after training, whereas in this manuscript, to promote robustness during training, we use Eq. (6) to update the weights while minimizing the bound on the Lipschitz constant. Applying the Schur complement to (5) for $\alpha=0$, the LMI can be rearranged, yielding an equivalent LMI that is linear in $L^{2}$ and $W=(W^{0},\cdots,W^{l})$, for fixed $T\in\mathcal{D}_{n}$:

For the single-layer case, $M_{1}$ conveniently reduces to

While the Lipschitz constant estimation scheme in optimizes over $T$, throughout the manuscript, we choose $T$ to be a fixed matrix. This introduces conservatism into the framework and necessitates a suitable choice for $T$ in order to keep the introduced conservatism to a minimum. For instance, the matrix $T$ may be determined from the Lipschitz constant estimation outlined in Section II-B on the vanilla NN or the L2 regularized NN trained on the same problem.

III-B Lipschitz regularization

In general, NNs are trained on input-output data with the objective of minimizing a predefined loss, e.g. the mean squared error, cross-entropy, or hinge loss. We propose to not only minimize the NN’s loss but also its Lipschitz constant. This yields an optimization problem with two separate objectives that can be solved conveniently using ADMM.

ADMM is an algorithm that solves optimization problems by splitting them into smaller subproblems that are easier to handle individually . In order to apply the ADMM algorithm, the objective must be separable. The resulting subobjectives are then defined on uncoupled convex sets and are subject to linear equality constraints. The ADMM scheme solves the resulting optimization problem through independent minimization steps on the augmented Lagrangian of the optimization problem and a dual update step. The objectives at hand, i.e., the NN’s loss and the Lipschitz bound, are indeed separable and defined on uncoupled convex sets. However, the problems are not completely independent and need to be connected through a linear constraint that requires the introduction of additional variables $\bar{W}=(\bar{W}^{0},\dots,\bar{W}^{l})$ of equal size as $W$. The loss of the NN $\mathcal{L}(W)$ is an explicit function of the weights $W$ and the Lipschitz bound $L$ depends on $\bar{W}$ through the LMI (7), yielding the following optimization problem:

where $\mu>0$ is a weighting parameter adjusting the trade-off between accuracy and robustness and

is the indicator function. Applying the ADMM scheme to problem (8), results in the augmented Lagrangian function

For training of robust NNs, we carry out the corresponding updates consecutively until convergence. The loss function is optimized analytically using backpropagation (Eq. (9a)) whereas the Lipschitz update step (9b) is an SDP, as implementation of the indicator function corresponds to an LMI constraint. Hence, the Lipschitz update step requires to solve an SDP in every iteration and thereby adds additional computations compared to the training of a vanilla NN.

It is possible to extend the framework and optimize over $L^{2}$, $T$, and $W$ at the same time which requires a second LMI constraint in (8) and an additional update step in (9), resulting in a multi-block ADMM scheme. This reduces conservatism but increases computation time.

III-C Enforcing Lipschitz bounds

The training procedure based on (10) allows to choose the value of the Lipschitz bound and to train NNs with Lipschitz guarantees. This way, a desired degree of robustness can be directly enforced. However, the choice of such a constraint on $L$ is always connected to the trade-off between accuracy and robustness, as the fit generally deteriorates when decreasing the Lipschitz constant constraint. In addition, it is helpful to initialize the weight parameters appropriately which does not only accelerate training but may also facilitate a better fit.

III-D Convergence

ADMM was first introduced for optimization problems with convex subobjectives and later, analyses of the ADMM scheme for non-convex objectives including further structural assumptions on the objective were formulated . In the proposed framework, the loss $\mathcal{L}(W)$ clearly is not convex and has no obvious structural properties which renders a thorough convergence analysis complicated and beyond the scope of this work. However, looking at the subproblems (9a) and (9b) separately, we point out that for (9a) gradient descent almost surely converges to local minima even for non-convex problems , and that (9b) is a semidefinite program with a unique minimizer. Thus adding the convex regularization term and the indicator function of a convex set to the optimization problem of NN training, that converges reliably, does not add complexity in the form of non-convexity to the optimization problem.

III-E Computational tractability

Computational tractability and scalability of the proposed framework depend on the number of decision variables of the SDP. Generally, the complexity of SDP solvers scales cubically with the number of decision variables. Hence, for high-dimensional decision variables, solving an SDP is computationally more expensive than solving an unconstrained optimization problem using gradient descent. Therefore, the Lipschitz update step (9b) becomes the bottleneck of the proposed method as the number of neurons per hidden layers and the number of hidden layers, that together determine the size of the weights, increases. For example for picture inputs as commonly used in classification problems, the input dimension is usually high, potentially leading to high computation times or computational intractability. Nevertheless, downscaling the input using convolutional or pooling layers provides an option to improve computation time on larger scale problems and makes the proposed method indeed a worthwhile one to infer robustness to a neural network and obtain guarantees on the Lipschitz bound, also on large-scale problems. In Section IV, we show in an example that our method is applicable to MNIST, a typical benchmark classification problem.

In order to keep the number of Lipschitz update steps to a minimum, we advise to first fully train a neural network without regularizers or with standard regularizers, such as the L2 regularizer, which serves as an initialization of the matrix $T$ and the weights $W$, $\bar{W}$. Loosely speaking, our method provides a refinement of the pretrained neural network and allows to subsequently optimize robustness or impose robustness guarantees on the network by minimizing or respectively, by enforcing an upper bound on the Lipschitz constant.

IV Simulation Results

In this section, we illustrate the benefits of the presented framework for training of robust NNs on a 2D toy example and on MNIST. Our first illustrative example is a classification problem of 2D data with three classes, shown in Fig. 1(a). We design a feed-forward NN with two hidden layers of $n_{1}=n_{2}=10$ neurons each, activation function $\tanh$ that is slope-restricted with $\alpha=0$, $\beta=1$, and the cross entropy loss (CEL) as the loss function. For comparison, we train three NNs, a vanilla NN, an NN with L2 regularization (L2-NN) for benchmarking and finally the Lipschitz regularized NN (Lipschitz-NN) according to Section II-B, wherein the NN loss update step (9a) is solved using stochastic gradient descent and the SDP (9b) is solved using numerical SDP solvers . Before training, we initialize the Lipschitz-NN with the L2 regularized NN with penalty parameter $\lambda=4\times 10^{-3}$. The hyperparameters $\rho=0.25$ and $\mu=1\times 10^{-5}$ are chosen such that for comparability the Lipschitz constants of the L2-NN and the Lipschitz-NN are roughly the same. The resulting cross-entropy losses, accuracies on test data and bounds on the Lipschitz constant, that are summarized in Table I, show that the nominal NN achieves a small CEL, yet a high Lipschitz bound of $242$. Comparing the two regularizers, we see that Lipschitz regularization here leads to both a lower Lipschitz bound $L$, hence higher robustness, and a lower CEL than L2 regularization. Even though, due to the trade-off between accuracy and robustness, the CEL of the Lipschitz-NN is higher than the CEL of the nominal NN, the accuracy of the Lipschitz-NN is not compromised. On the contrary, the Lipschitz-NN even provides the highest accuracy, as the nominal NN tends to overfit the data whereas the L2 regularized NN fails to provide a good fit in this example. Fig. 1(b) shows a projection at $x_{2}=0.5$ of the logits resulting from the three NNs for all three classes (blue, green, and orange) onto the $x_{1}$ dimension. We clearly see the effect of a lower Lipschitz constant in the less steep slopes of the curves while the decision boundaries of the Lipschitz-NN remain accurate. The price to pay for the improved robustness is an increase in computation time (compare Table I), since training of the Lipschitz-NN requires several computationally involved ADMM iterations. Note that for low-dimensional problems the Lipschitz update step (9b) is faster than the loss update step (9a), yet it becomes computationally expensive for high-dimensional problems (cf. Section III-E).

In our second example, we apply the Lipschitz regularization framework to the high-dimensional benchmark data set MNIST . We train a feed-forward NN with one pooling layer, one hidden layer with $n_{1}=50$ neurons, the activation function $\tanh$, the cross entropy loss (CEL) and again, we train three NNs, a vanilla NN, an L2-NN, and a Lipschitz-NN with $\rho=0.25$ and $\mu=0.01$, initializing the Lipschitz-NN from the L2-NN with penalty parameter $\lambda=3\times 10^{-3}$. The input dimension of the data is $28\times 28$ that is downscaled by the pooling layer to an input size of $14\times 14$. Note that the method also works on the $28\times 28$ data without a pooling layer, yet the Lipschitz step becomes significantly more time-consuming. From the resulting accuracies on test data and bounds on the Lipschitz constant shown in Table I, we conclude that on MNIST our framework also finds an NN with a low Lipschitz constant but comparable accuracy to the nominal NN, while the accuracy of an L2-NN with a comparably low Lipschitz constant is significantly compromised. Fig. 2 shows the evaluation of the three NNs on noise corrupted data, that was created by adding Gaussian noise $\mathcal{N}(0,\sigma^{2})$ and respectively, uniform noise $\mathcal{U}(-b,b)$ to the $(0,1)$-normalized MNIST data. Advantages of the Lipschitz-NN become apparent for Gaussian noise with low standard deviation and noise from a narrow uniform distribution.

Altogether, the results show that Lipschitz regularization can be used to effectively train robust NNs while trading off robustness and accuracy. Code to reproduce the examples can be found at https://github.com/st157640/Training-robust-neural-networks-using-Lipschitz-bounds.git.

V Conclusion

We proposed a framework for training of multi-layer NNs that encourages robustness, by both considering Lipschitz regularization and by enforcing Lipschitz bounds during training. The underlying SDP estimates the upper bound on the Lipschitz constant more accurately than traditional methods as it exploits the fact that activation functions are slope-restricted. We designed an optimization scheme based on this SDP that trains an NN to fit input-output data and at the same time increases its robustness in terms of Lipschitz continuity. We used ADMM to solve the underlying optimization problem and to therein conveniently incorporate the trade-off between accuracy and robustness. In addition, we presented a variation of the framework that allows for bounding the Lipschitz constant by a desired value, i.e., training NNs with robustness guarantees. We successfully tested our method on two examples where we benchmarked it with L2 regularization.

Next steps include the application of our method to control problems by using LMI constraints to verify and enforce properties, such as closed-loop stability, on feedback interconnections that include NN controllers. Also, we plan to explore alternatives for the ADMM algorithm that solve the underlying optimization problem in an accelerated manner. In addition, for benchmarking purposes, we plan to compare the proposed methods to other training procedures that improve robustness.

References