Year: 2019

Abstract:
Deep neural networks are known to be vulnerable to adversarial perturbations. In this paper, we bridge adversarial robustness of neural nets with Lyapunov stability of dynamical systems. From this viewpoint, training neural nets is equivalent to finding an optimal control of the discrete dynamical system, which allows one to utilize methods of successive approximations, an optimal control algorithm based on Pontryagin’s maximum principle, to train neural nets. This decoupled training method allows us to add constraints to the optimization, which makes the deep model more robust. The constrained optimization problem can be formulated as a semi-definite programming problem and hence can be solved efficiently. Experiments show that our method effectively improves deep model’s adversarial robustness.

text: Deep neural networks are known to be vulnerable to adversarial perturbations. In this paper, we bridge adversarial robustness of neural nets with Lyapunov stability of dynamical systems. From this viewpoint, training neural nets is equivalent to finding an optimal control of the discrete dynamical system, which allows one to utilize methods of successive approximations, an optimal control algorithm based on Pontryagin’s maximum principle, to train neural nets. This decoupled training method allows us to add constraints to the optimization, which makes the deep model more robust. The constrained optimization problem can be formulated as a semi-definite programming problem and hence can be solved efficiently. Experiments show that our method effectively improves deep model’s adversarial robustness.

heading: 1 INTRODUCTION
text: Deep neural networks achieve state-of-the-art performances on a variety of tasks (LeCun et al., 2015). However, neural nets are known to be vulnerable to adversarial examples. Imperceptibly perturbed inputs can induce erroneous outputs in neural nets (Szegedy et al., 2013). In image classification problems of computer vision, previous work has proposed various methods to attack deep models and induce low accuracy (Goodfellow et al., 2015; Madry et al., 2017; Papernot et al., 2016a; Carlini & Wagner, 2017a). Whereas multiple defenses against adversarial attacks are developed, they don’t ensure safety faced with strong attacking methods. There are also theories that explain the existence of adversarial examples (Ilyas et al., 2019; Shamir et al., 2019), but they often fail to fully explain the features and behaviors of this phenomenon. This makes the study of adversarial attacks important in that it is a threat to real-life machine learning systems (Kurakin et al., 2016).
In this paper, we propose a dynamical system view on the adversarial robustness of the models, as well as new method that significantly defense adversarial attacks.
Recent works have shown the connection between deep neural networks and dynamical systems (E, 2017; Li et al., 2017; Haber & Ruthotto, 2017; Lu et al., 2017). If we regard the neural net as a discretization of an ordinary differential equation (ODE), then training neural nets becomes finding an optimal control of the corresponding discrete dynamical system. Traditionally, we often treat training neural networks as an unconstrained non-convex optimization problem
min θ∈Θ J(θ) +R(θ),
where θ denotes the parameters of the model, J denotes the loss function and R denotes the regularizer term, and we solve the problem with (stochastic) gradient-descent based methods (Bottou, 2010; Ruder, 2016). In the training process, we feed the network with a batch of training data, and compute the gradient with forward and backward propagation (E. Rumelhart et al., 1986). The propagation process resembles solving optimal control problems that tune the parameters to make the output be close to target states. This viewpoint motivates us to bridge adversarial robustness with Lyapunov stability of a dynamical system, and to train robust networks with algorithms that find stable optimal control. We will formulate the discussion in later sections.

heading: 2 RELATED WORK

heading: 2.1 ADVERSARIAL DEFENSE
text: Many defense methods have been proposed to improve the models’ adversarial robustness. The defenses mainly fall into three types: adversarial training (Szegedy et al., 2013; Zhang et al., 2019), modifying the networks (Gu & Rigazio, 2015; Lyu et al., 2015; Papernot et al., 2016b; Nayebi & Ganguli, 2017; Ross & Doshi-Velez, 2017), and adding external models (Lee et al., 2017; Akhtar et al., 2017; Gebhart & Schrater, 2017; Xu et al., 2018; Sun et al., 2019). Although various defense methods have been developed, a defended deep model is often successfully attacked by newly developed attacks or specific counter-counter measures (Carlini & Wagner, 2017b). Therefore, it can be hoped that defenses against general attacks will be devised to make deep learning models (adversarially) robust to real-life threats.

heading: 2.2 NEURAL ODES AND OPTIMAL CONTROL
text: Recent works have bridged deep neural networks with ODEs and dynamical systems. On the one hand, deep residual networks (He et al., 2015) can be illustrated as forward Euler scheme approximating an ODE (E, 2017), which motivates us to design effective network structures (Lu et al., 2017). On the other hand, regarding the network as a dynamical system allows us to set up an optimal control viewpoint of neural nets. Pontryagin’s Maximum Principle (Boltyanskii et al., 1960) has been applied to train neural nets (Li et al., 2017; Li & Hao, 2018).

heading: 3 ADVERSARIAL ROBUSTNESS AND LYAPUNOV STABILITY

heading: 3.1 DYNAMICS OF DEEP NEURAL NETS
text: Given a T -layer neural net, we let the dynamical system {ft(xt, θt) : t = 0, . . . , T} represents the network, where xt is the input of t-th layer, θt is the parameter, and ft : Rdt × Θt → Rdt+1 denotes the t-th layer’s transformation, which is usually a non-linear function σ(θtxt + bt) for fully-connected layers, convolution layers and batch normalization layers, etc. Therefore, training the neural net can be regarded as controlling the parameters to let the dynamics fit the training data. Specifically, the training optimization problem can be formulated as a typical optimal control problem as follows:
min θ B∑ i=1 J(xiT ) + T∑ i=0 L(θi),
subj. to xit+1 = ft(x i t, θt), t = 0, . . . , T − 1,
where we use xi to denote the i-th input in the batch and B denote the batch size. J and L are the loss function and the regularizer, respectively. Specially, if the model is a deep residual network with structure xt+1 = xt+ft(xt, θt), we can regard the problem as the forward Euler discretization of the following continuous optimal control problem:
min θ J(x(T )) + ∫ T 0 L(θ(t)) dt,
subj. to ẋ = f(t, x(t), θ(t)), x(0) = x, 0 ≤ t ≤ T,
where x(t) is a continuous trajectory from the input to the output logits.

heading: 3.2 LYAPUNOV STABILITY
text: Adversarial examples are usually clean images added by a small calculated perturbation η. The model predicts correct labels fed with clean inputs x0, while the output is completely different when it is fed with perturbed input x0 + η. The dynamical system view of neural nets motivate us to characterize this sensitivity with Lyapunov stability of a system (Hirsch et al., 2004). Definition 1 (Lyapunov Stability). For a given dynamical system ẋ = f(x), x(0) = x0, xe is an equilibrium, then
• The system is Lyapunov stable, if, ∀ > 0, ∃ δ > 0 such that, if ‖x(0)− xe‖ < δ, then for every t ≥ 0, ‖x(t)− xe‖ < .
• The system is asymptotically stable if it is Lyapunov stable and ∃ δ > 0 such that if ‖x(0)− xe‖ < δ, then limt→∞ ‖x(t)− xe‖ = 0.
• The system is exponentially stable if it is asymptotically stable and ∃α > 0, β > 0, δ > 0 such that if ‖x(0)− xe‖ < δ, then ‖x(t)− xe‖ ≤ α‖x(0)− xe‖e−βt, for all t ≥ 0.
The definitions can be easily extended to discrete-time systems.
Intuitively, the Lyapunov stability states that for any small perturbation η, the trajectory is still “close enough” to the original one. If we regard a neural net as a dynamical system, and ensure the network is Lyapunov stable, then the model is robust to all (adversarial) perturbations.

heading: 3.3 ADVERSARIALLY ROBUST NEURAL NETS
text: Due to the connection between numerical ODEs and residual networks, we first consider robustness (i.e. Lyapunov stability) of continuous ODEs. Theorem 1 (Stable ODEs). For a given ODE ẋ = f(t, x, θ) = σ(Ax+b), where σ is the activation function, e.g., Sigmoid function or ReLU function, it is stable if Re(λi(A)) ≤ 0, ∀i, where Re denotes the real part, and λi denotes the i-th eigenvalue.
One can see, e.g. Hirsch et al. (2004), for the proof of this theorem.
Theorem 1 provides a set of conditions for stable ODEs. However, deep residual network is only a forward Euler discretization scheme of continuous ODE. To ensure numerical stability, we require |1− λi(A)h| ≤ 1 (Ascher & Petzold, 1998), where the step size h = 1 in residual networks. Added by the identity mapping in residual networks, we can get the stable conditions for discrete dynamics. Theorem 2 (Stable Discrete Networks). For a discrete neural network, i.e., discrete dynamics {ft(xt, θt) : t = 0, . . . , T}, where ft(xt, θt) = σ(θtxt) (we omit the bias term for simplicity), the network is stable if the ρ(θt) ≤ 1, where ρ(A) = maxi(|λi(A)|) is the spectral radius.
If the conditions are added to the unconstrained optimization problem of training, we can greatly improve the adversarial robustness of neural nets. The methods will be discussed in the following section.

heading: 4 TRAINING ROBUST NEURAL NETS

heading: 4.1 PMP AND MSA
text: For deterministic systems, the Pontryagin’s Maximum Principle (PMP) (Boltyanskii et al., 1960) provides a set of necessary conditions for optimal control of the system. Various algorithms have been proposed to solve the deterministic optimal control problem based on PMP. Among them, the Method of Successive Approximations (MSA) (Krylov & Chernous’ko, 1963) is one of the simplest algorithms. In the field of deep learning, previous work has utilized MSA to train neural networks (Li et al., 2017; Li & Hao, 2018).
Formally, consider the optimal control problem for training neural nets in section 3. For dynamics {ft(xt, θt) : t = 0, . . . , T}, assume θ∗ = { θ∗0 , . . . , θ ∗ T−1 } is a solution to the optimal control problem. Also, we define the Hamiltonian function H : Rdt × Rdt+1 × Θt × [T ] → R by H(x, p, θ, t) = p · ft(x, θ)−L(θt), where the dot denotes the inner product. We have the following necessary conditions for θ∗. Theorem 3 (Pontryagin’s Maximum Principle for Discrete Systems). Assume ft and J are sufficiently smooth. There exists co-states p∗ = {p∗0, . . . , p∗T } s.t. the following conditions hold:
x∗t+1 = ∇pH(x∗t , p∗t+1, θ∗t , t), x∗0 = x0, p∗t = ∇xH(x∗t , p∗t+1, θ∗t , t), p∗T = −∇xJ(x∗T ),
θ∗t = arg max θ H(x∗t , p ∗ t+1, θ, t).
For simplicity of notations, here we assume the batch size is 1. One can easily extend the theorem to minibatch training case by summing over the batch.
The theorem can be proved by KKT conditions (Boyd & Vandenberghe, 2004), where the co-states can be seen as the Lagrangian dual variables.
Consider the conditions in PMP, one can find the x equations are exactly the forward propagation of a neural net, and the p equations resemble the backward propagation process. The third condition states that the model parameters must maximize the Hamiltonian function. This motivates us to iteratively compute forward and backward propagation, and solve the Hamiltonian maximization to find the optimal control, which is exactly the Method of Successive Approximations (Algorithm 1). In practice, we usually add regularizer terms that penalize great changes in the maximization step to prevent drastic steps that cause divergence. For the connection between MSA and back-propagationbased gradient descent algorithms, see the appendix of Li & Hao (2018).
Algorithm 1 The Method of Successive Approximations Initialize θ0 = { θ00, . . . , θ 0 T−1 } , set k = 0;
repeat Compute the states (forward propagation): xt+1 = ∇pH(xt, pt+1, θkt , t), t = 0, . . . , T − 1; Compute the co-states (backward propagation): pt = ∇xH(xt, pt+1, θkt , t), t = T − 1, . . . , 0, with initial pT = −∇xJ(xT ); For each t = 0, . . . , T − 1, solve the maximization θk+1t = arg maxθH(xt, pt+1, θ, t); Set k = k + 1; until Converge;
The advantages of training by MSA compared with gradient descent algorithms has been discussed in (Li et al., 2017), among which the most significant feature is that the optimization steps on different layers are decoupled. Concretely, after computing the states x and co-states p, the optimization step on layer t is only searching for parameters θt. This not only suggests that the optimization process can be accelerated by parallelization, but also allows us to utilize the features of the problem. The parameter space is greatly reduced compared with the original intractable optimization problem, and hence the optimization is much more easier. This allows us to add constraints that ensure robustness of the model.

heading: 4.2 ROBUST CONSTRAINTS
text: Consider a layer in the form of ft(x) = θtx, where we leave the activation as an individual layer with no parameters for simplicity, we can derive the following optimization problem for Hamiltonian maximization:
max θ
pt+1 · (θtxt)− α‖θt‖22 − β‖θt − θ′t‖22,
subj. to ρ(θt) ≤ 1, where α‖θt‖22 is the L2 norm regularizer (weight decay), and θ′t is the initial parameter (i.e., θkt in the algorithm). The last term keeps the training process from drastic steps that cause divergence. The constraint, as illustrated in section 3, is the stable condition for discrete systems. It makes the optimization quite difficult if we directly add the constraints in gradient descent based algorithms, but the decoupled optimization in MSA allows us to do so.
With regard to the constraint of parameter’s spectral radius, a simple method is to apply special forms of matrices for parameters, e.g. anti-symmetric matrices. For continuous deep models, the only constraint is Theorem 1, i.e., Re(λi(θt)) ≤ 0. Anti-symmetric matrices have only imaginary eigenvalues, and hence we can replace θt with θt − θTt − γI , where γ is a small positive constant. For general forms of parameters, one can prove the following transformation. Theorem 4. One sufficient condition of ρ(A) ≤ 1 is[
I A AT I
] 0,
where A B denotes A−B is positive semi-definite.
Proof. Recall that ρ(A) ≤ ‖A‖2 = √ λmax(ATA), we have
‖A‖2 ≤ 1⇔ ATA I ⇔ [ I A AT I ] 0.
Hence we can replace ρ(θt) ≤ 1 with a positive semi-definite condition, and we turn the Hamiltonian maximization into a new optimization problem, where the target function is quadratic and the constraint is a semi-definite condition. This can be reduced to a semi-definite programming (SDP) problem (Vandenberghe & Boyd, 1998), which is a special case of convex optimization, and thus can be solved efficiently by, e.g., interior point methods (Helmberg et al., 1970) in polynomial time.
Here we summarize our method. For a given neural network, we use MSA to train the model, i.e., iteratively computing the states (forward propagation) and co-states (backward propagation), and solving the optimization for each layer. Instead of directly maximizing the Hamiltonian, we add a positive semi-definite constraint to the optimization problem, which leads to a stable control of the dynamics.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENT SETUP
text: To evaluate the effectiveness of our method, we conduct experiments on CIFAR10. We trained the network on clean data, with adversarial training (PGD-10) and with robust training (our method), respectively. We used FGSM (Goodfellow et al., 2015), PGD-10 (Madry et al., 2017) and C&W (Carlini & Wagner, 2017a) to attack the network.
Due to the limitation of TensorFlow, we used a simple interior point method with gradient descent to solve SDP. The network model was an 18-layer residual network (He et al., 2015), with 8 residual blocks. We set the perturbation size as = 0.1 for both FGSM and PGD. For C&W, we used the L0 metric. We trained the model for 150 epochs with a batch size of 200. The learning rate was set to be 10−2 initially, and was divided by 5 at epoch 30, 60 and 100. The regularizer term constant was set to be 10−3.

heading: 5.2 RESULTS
text: The results can be seen in Table 1. The accuracy of robust models on clean data is lower than vanilla model’s in that robust training and generalization is more difficult and requires more data (Schmidt et al., 2018).
Our method improves model’s adversarial robustness, compared with the vanilla model. Figure 1 displays the eigenvalues of the last fully-connected layer’s parameter. The complex norm of eigenvalues (spectral radius) of the model trained by our method are effectively bounded below 1, which satisfies the robust constraint on parameters in section 4.2, while eigenvalues of natural training are randomly distributed in the complex plane.
Our method is not as effective as traditional adversarial training method. However, it mainly has the following advantages: (a) The training process doesn’t require large numbers of gradient propagation, which consumes much time in adversarial training. In our experiment, adversarial training
spends about 10 times GPU time as much as our method. (b) The decoupled training process allows us to set different hyperparameters and training methods for different layers, which is more maneuverable for large scale training. We can further control the behavior of different layers in adversarial settings. (c) Lyapunov stability provides a framework for analyzing adversarial robustness of deep models, which may lead to theoretical analysis of adversarial samples in future work.

heading: 6 DISCUSSION AND FUTURE WORK
text: Motivated by the dynamical system view of neural networks, this work bridges adversarial robustness of deep neural models with Lyapunov stability of dynamical systems, and we also propose a method that uses a stable optimal control algorithm to train neural networks to improve the adversarial robustness of deep neural models. Though the result didn’t surpass STOA defense methods, the stable control view of training neural nets points out another direction towards adversarially robust models.
For future work, on the one hand, mathematical analysis on Lyapunov stability of neural models may be studied to provide theoretical understanding of adversarial robustness. On the other hand, popular platforms for deep learning, e.g., TensorFlow, PyTorch, didn’t provide frameworks for optimal control. We will obtain better results if specific algorithms for SDP are applied to solve the optimization problem.

Review summaries:
The goal of this paper is to train neural networks (NNs) in a way to be robust to adversarial attacks. The authors formulate training a NN as finding an optimal controller for a discrete dynamical system. This formulation allows them to use an optimal control algorithm, called method of successive approximations (MSA), to train a NN. The authors then show how constraints can be added to this optimization problem in order to make the trained NN more robust. They show that the resulted constraint optimization problem can be formulated as a semi-definite programming and provide some experimental results. 

Neural Networks are vulnerable to adversarial perturbations. This paper proposes a method that based on optimal control theory that uses semidefinite-programming. This is a quite popular topic in Adversarial training recently, there has been a few works in that line. There are almost no experiments in this paper. There are several typos in the paper and writing of this paper requires more work. There are several typos in this paper, for example STOA, should be SOTA (in the Section 6.) In its current state, this paper looks very rushed.