Neural networks, as one of the most powerful and popular machine learning tools, are vulnerable to adversarial attacks. In the field of computer vision, for instance, slight manipulations of the input images can elicit misclassifications in neural networks with high confidence [1]- [3]. Neural networks have found a wide range of applications, especially in control theory [4], where robustness is a high priority. For example, deep reinforcement learning has been used to control highly non-linear and complex systems [5], [6]. An adversarial attack on the underlying neural network may cause the control system to completely fail [7]. Thus, it is crucial to analyze the adversarial robustness of neural networks, especially when they are applied to safety-critical systems.
While there have been studies on robustness certifications [8]- [10], researchers have also been working extensively on training classifiers whose predictions are robust to adversarial inputs [3], [11]- [13]. "Adversarial training" is one of the most effective methods to train robust networks, compared with other methods such as obfuscated gradients [14]. Adversarial training replaces the standard loss function with a robust loss function and solves a bi-level min-max optimization problem. More recently, [15] and [16] proposed "randomized smoothing", complementing adversarial training by achieving certified robustness at test time. Prior works have applied convex relaxation techniques to adversarial training. These works use weak duality to upper-bound the inner maximum of the adversarial training formulation and develop upper-bound loss functions that can be optimized with back-propagation [17], [18]. While these works rely on convex relaxations, the resulting training formulations are still non-convex.
Training neural networks involves optimizing non-convex objectives. In practice, training usually relies on Stochastic Gradient Descent (SGD) back-propagation, which only guarantees convergence to a local minimum for non-convex programs. While gradient descent can converge to a global optimizer for one-hidden-layer ReLU networks when the network is wide enough [19], [20], spurious local minima still exist in general. Moreover, the non-convexity of the optimization landscape results in poor interpretability and excessive sensitivity to hyperparameters. These issues become worse when adversarial training is incorporated: adversarial training can be highly unstable in practice.
Convex programs have the favorable property that all local minima are globally optimal. To overcome the issue of arriving at spurious local minima when training neural networks, existing works have considered convexifying the neural network training problem [21], [22]. More recently, [23] proposed a convex optimization problem with the same global minimum as the non-convex cost function for a onehidden-layer fully-connected ReLU neural network.
Therefore, extending "convex training" to adversarial training has become a natural solution to the optimization difficulty issues. Unfortunately, the size of the convex program proposed in [23] grows exponentially in the training data matrix rank, leading to an exponential overall complexity. While [23] proposed a heuristic method to reduce the computation through approximation, it did not provide theoretical insights into the approximation quality. To bridge this gap, we theoretically bound the quality and show that the scale of this approximation is linear in the training data size.
With these roadblocks cleared, we build upon the aforementioned works to develop "convex adversarial training", explicitly focusing on the hinge loss (binary classification) and the squared loss (regression). We mathematically show that solving the proposed robust convex programs trains robust neural networks and empirically demonstrate the advantages over traditional methods. The theoretical analysis focuses on one-hidden-layer neural networks but can extend to more complex architectures.
The novelties of this paper include a convex robust neural network training analysis (Sections IV-VI) and a probabilistic bound on the suboptimality of a relaxation method that was previously known as a heuristic (Section III). Due to space restrictions, some of the proofs are moved to the technical report [24], which also includes additional numerical experiments.
Throughout this work, we focus on fully-connected neural networks with one ReLU-activated hidden layer and a scalar output, defined as b y = P m j=1 (Xu j ) + ↵ j , where X 2 R n⇥d is the input data matrix with n data points in R d and b y 2 R n is the corresponding output vector. We denote the target output used for training as y 2 R n . u 1 , . . . , u m 2 R d are the weight vectors of the m neurons in the hidden layer while ↵ 1 , . . . , ↵ m 2 R are the weights of the output layer. The symbol (•) + = max{0, •} indicates the ReLU activation.
Furthermore, let k•k p denote the `p-norm within R n and denote the Hadamard product. For P 2 N + , we define [P ] as the set {a 2 N + |a P }, where N + is the positive integer set. For q 2 R n , sgn(q) 2 R n denotes the sign of each entry of q and [q 0] denotes a boolean vector in {0, 1} n that represents the non-negativeness of each entry of q. The symbol diag(q) denotes a diagonal matrix Q 2 R n⇥n , where Q ii = q i for all i, and Q ij = 0 for all i 6 = j. The symbol 1 defines a column vector with all entries being 1. For a 2 R n and b 2 R, the inequality a b means a i b for all i. The notation ⇧ S (•) denotes the projection onto the set S and |S| denotes the cardinality of the set. For r 2 R n , r ⇠ N (0, I n ) indicates that r is a standard normal random vector.
Adversarial training is the main problem under study in this paper. A classifier is considered adversarially robust if it assigns the same label to all inputs within an `1 bound with radius ✏ [3]. The perturbation set can be defined formally as
o .
One standard method for training robust classifiers minimizes the "robust cost", defined as the maximum loss within the perturbation set. The process of "training with adversarial data" is often referred to as "adversarial training", as opposed to "standard training" that trains on clean data. Formally, this method solves the min-max problem
(see [12] for more details). In the prior literature, Fast Gradient Sign Method (FGSM) and Projected Gradient Descent (PGD) are commonly used to numerically solve the inner maximization of (2) and generate adversarial examples [12]. The outer minimization of ( 2) is still solved with SGD back-propagation. We abbreviate these traditional methods as GD-FGSM and GD-PGD. More specifically, PGD generates adversarial examples x by running the iterations
for t = 0, 1, . . . , where x t is the perturbed data vector at iteration t, the initial vector x0 is the unperturbed data x, ⇧ X denotes the projection onto the set X , and > 0 is the step size. The projection step can be performed by simply clipping the coordinates that deviate more than ✏ from x.
FGSM can be regarded as running PGD for a single step with a large step size. While GD-FGSM and GD-PGD have demonstrated their capabilities of training robust networks in various settings [3], [11], [12], they suffer from the following issues:
• Poor interpretability: With GD-PGD and GD-FGSM, it is hard to monitor the training status. For example, when the training loss is high, it can be unclear whether a satisfactory robustness has been achieved or the training was unsuccessful.
• Sensitivity to hyperparameters: The hyperparameters of GD-PGD include the number of epochs, batch size, and step size of SGD (for outer minimization), and the step size and the number of steps of PGD (for inner maximization). The value of each parameter affects the the performance, but is challenging to design. SGD back-propagation is also sensitive to the initializations. • Lack of optimality guarantees: The inner maximization problem of (2) is non-concave, and the outer minimization is non-convex in general. Convergence guarantees are lacking for both subproblems. • Vanishing / exploding gradients: For back-propagation, the gradients at shallower layers depend on deeper layers, thus susceptible to vanishing or exploding gradients. Moreover, iteratively solving the bi-level optimization (2) requires an algorithm with an inefficient nested loop structure.
Here, we introduce our main analysis framework -convex training. Consider the optimization for training a one-hiddenlayer network with a regularized convex loss `(b y, y):
where > 0 is a regularization parameter. Consider a set of diagonal matrices {diag([Xu 0]) | u 2 R d }, and denote the distinct elements of this set as D 1 , . . . , D P . The constant P is the total number of partitions of R d by hyperplanes passing through the origin that are also perpendicular to the rows of X [23]. Intuitively, the D i matrices represent the ReLU activation patterns associated with X.
Consider the convex optimization problem
and its dual formulation
where 6) is a convex semi-infinite program. The next theorem borrowed from [23,Theorem 6] explains the relationship between the non-convex training problem (4), the convex problem (5), and the dual problem (6) when the neural network is sufficiently wide.
Theorem 1. Let (v ? i , w ? i ) P i=1 denote a solution of ( 5) and define m ? as |{i :
, where m ? is upper-bounded by n + 1. If the loss function `(•, y) is convex, then (4), ( 5), and ( 6) share the same optimal objective. The optimal network weights (u ? j , ↵ ? j ) m j=1 can be recovered using the formulas
where the remaining m m ? neurons are chosen to have zero weights.
While Theorem 1 requires an over-parameterized neural network, convex training can be applied to networks much narrower than m ? , as will be proved in Theorem 2.
Unfortunately, the worst-case computational complexity of solving (5) is O d 3 r 3 ( n r ) 3r using standard interior-point solvers [23], prohibitively high for many practical applications. Here, r is the rank of the data matrix X and in many cases r = d. This high complexity makes convex training impractical. Before we use this framework to address the problems of adversarial training, we need to break down the complexity bottleneck of convex training.
The high complexity arises because the total number of D i matrices is upper-bounded by min 2 n , 2r e(n 1) r r . To reduce this number, [23,Remark 3.3] introduced Algorithm 1. Algorithm 1 approximately solves (5) by independently sampling a subset of the D i matrices. However, [23] did not provide theoretical insights regarding the approximation quality, and therefore the approximation remains a heuristic. The following theorem bridges this gap by providing a probabilistic bound on the suboptimality of the neural network trained with Algorithm 1.
) where a i ⇠ N (0, I d ) i.i.d. for all i, generate P s distinct diagonal matrices. 2: Solve
(2D i I n )Xw i 0, 8i 2 [P s ];
3: Recover u 1 , . . . , u ms and ↵ 1 , . . . , ↵ ms from the solution (v ? si , w ? si ) Ps i=1 of ( 8) using (7).
Theorem 2. Consider an additional diagonal matrix D Ps+1 uniformly sampled, and then construct
where and ⇠ are preset confidence level constants between 0 and 1, then with probability at least 1 ⇠, it holds that P{p ? s2 < p ? s1 } . Proof sketch: It can be shown that a dual problem of ( 5) is an instance of "uncertain convex program (UCP)". Similarly, it can be shown that a dual problem of the approximation (8) is a "sampled convex program (SCP)", which relaxes the UCP by randomly dropping some of the constraints. The quality of the SCP relaxation can then be bounded using the analysis presented in [25], which introduces the confidence level constants and ⇠.
⇤ The formal proof is presented in [24,Appendix B]. Intuitively, Theorem 2 states that independently sampling an additional D Ps+1 matrix will not reduce the training cost with high probability. One can recursively apply this bound T times to show that when P s is large, the solution with P s matrices is close to the solution with P s + T matrices for an arbitrary number T . So, the optimality gap due to sampling will be small, and the trained network is nearly optimal.
Compared with P , which is exponential in r, P s is on the order of n ⇠ , linear in n and independent of r. When r is large, solving the approximated formulation ( 8) is exponentially more efficient than solving (5). On the other hand, Algorithm 1 is no longer deterministic due to the stochastic sampling of the D i matrices, and yields upper bounds to the global optimum of (5). We have verified empirically (shown in Section VII-A) that even when P s is much smaller than P , Algorithm 1 still reliably returns a low training cost.
To conquer the drawbacks of traditional adversarial training, we leverage Theorem 1 to recast (2) as robust, convex upper bound problems that can be efficiently minimized globally.
We first develop a result about adversarial training involving general convex loss functions.
The connection between the convex training objective (5) and the non-convex true training cost (4) holds only when the linear constraints in (5) are satisfied. For adversarial training, we need this connection to hold at all perturbed data matrices X + 2 X . Otherwise, if some matrix X + violates the constraints, then this perturbation can correspond to a low convex objective but a high actual loss. To ensure the meaningfulness of the convex reformulation throughout X , we introduce the robust constraints (10b) and (10c).
Since the D i matrices in (5) reflect the ReLU patterns of X, the D i matrices can change as X is perturbed. Therefore, we include all distinct diagonal matrices diag([(X + )u 0]) that can be obtained for all u 2 R d and all : X + 2 U, denoted as D 1 , . . . , D b P , where b P is the total number of such matrices. Since D 1 , . . . , D b P include D 1 , . . . , D P in (5), we have b P P . While b P is at most 2 n in the worst case, since ✏ is often small, we expect b P to be relatively close to P , where P 2r e(n 1) r r as discussed above.
Finally, we replace the objective of ( 5) with its robust counterpart, giving rise to the optimization
s. t. min
where U is any convex additive perturbation set. The next theorem shows that ( 10) is an upper bound to the robust loss function (2). , the optimization (10) provides an upper bound on the non-convex adversarial training problem (2). The robust network weights (u ? robj , ↵ ? robj ) b m j=1 can be recovered using (7). Moreover, if ? rob denotes a solution to the inner maximization in (10a), then X + ? rob corresponds to the worst-case adversarial inputs for the recovered neural network.
Proof sketch: Since the linear constraints in ( 5) are satisfied by all matrices X + , the relationship between ( 5) and ( 4) holds for all matrices X + . Thus, ?
rob is optimal for the inner maximization of (4). Since (u ? robj , ↵ ? robj ) b m j=1 may not be optimal for the outer minimization of (4), ( 10) is an upper bound.
⇤ The formal proof is provided in [24, Appendix C]. When the perturbation set is zero, Theorem 3 reduces to Theorem 1. Rather than an exact reformulation, ( 10) is an upper bound problem because the robust constraints (10b) and (10c) enforce that the ReLU activation pattern of the perturbed data X + remains the same within X , effectively reducing the Algorithm 2 Practical convex adversarial training 1: for i = 1 to P a do 2:
for j = 2 to S do 5:
R ij [r 1 , . . . , r d ], where r h ⇠ N (0, I n ), 8h
6:
12: Recover u 1 , . . . , u ms and ↵ 1 , . . . , ↵ ms from the solution (v ? robsi , w ? robsi ) Ps i=1 of ( 12) using (7).
feasible space of neural networks and causing suboptimality. The optimality gap between ( 10) and ( 2) is solely due to this suboptimality of the outer minimization, whereas the inner maximization is exact.
In light of Theorem 3, we use optimization (10) as a surrogate for optimization (2) to train the neural network. We will show that the new problem can be efficiently solved in important cases.
For the `1 perturbation set X , the constraints in (10b) and (10c) can be equivalently replaced by the algebraic constraints
To understand this, observe that for the `1 set, (10b) and (10c) become linear programming (LP) subproblems. Solving the LPs in closed forms yields (11). The detailed derivation is provided in [24, Appendix D].
Since Theorem 2 does not rely on any assumption on the matrix X, it applies to an arbitrary matrix X + , and naturally extends to the convex adversarial training formulation (10). Therefore, an approximation to (10) can be applied to train robust neural networks with widths much less than b m ? . Similar to the strategy rendered in Algorithm 1, we use a subset of the D i matrices for practical adversarial training. Since the D i matrices depend on the perturbation , we also add randomness to the data matrix X in the sampling process to cover D i matrices associated with different perturbations, leading to Algorithm 2. P a and S are preset parameters that control the number of times we run the random weight sampling procedure, with P a • S P s .
While the inner maximization of the robust problem (10) is still hard to solve in general, it is tractable for some loss functions. The simplest case is the piecewise-linear hinge loss `(b y, y) = (1 b y y) + , which is widely used for classification. Here, we focus on binary classification with y 2 { 1, 1} n .
Consider the adversarial training problem for a one-hiddenlayer neural network with `2 regularized hinge loss:
Applying Theorem 3 leads to the following formulation as an upper bound on (13):
When generating the D i matrices, instead of enumerating an infinite number of points in X as suggested in Theorem 3, we only need to enumerate all vertices of X , which is finite. This is because the solution ?
hinge to the inner maximum is always at a vertex of X , as will be shown in Theorem 4.
Theorem 4. For binary classification, the inner maximum of ( 14) is attained at ? hinge = ✏ • sgn
⌘ , and the bi-level optimization problem ( 14) is equivalent to the classic convex optimization min
where d ik denotes the k th diagonal element of D i . Proof sketch: Observe that the regularizations in (14) are independent from and the rest of the objective is piecewise linear. Using the fact that max (•) + is equivalent to (max •) + , one can reform the inner maximization of ( 14) into an LP. The optimal ? hinge is then obtained by solving the LP in closed form. Plugging ? hinge back yields (15). ⇤ The formal proof is provided in [24,Appendix E]. The problem ( 15) is a finite-dimensional convex program that provides an upper bound on (13). We can thus solve (15) to robustly train the neural network. The `1 norm term in (15) explains the regularization effect of adversarial training.
The squared loss `(b y, y) = 1 2 kb y yk 2 2 is another commonly used loss function in machine learning. It is widely used for regression tasks, but can also be used for classification.
Consider the non-convex adversarial training problem of a one-hidden-layer ReLU neural network trained with the `2-regularized squared loss:
Applying Theorem 3 leads to the following formulation as an upper bound on (16):
Theorem 5. The optimization problem ( 17) is equivalent to the convex program:
.
Proof sketch: We rewrite (17) in the form of a robust second-order cone program (SOCP) and show that the robust SOCP is equivalent to the classic convex optimization (18) using the procedures outlined in [26].
⇤ The formal proof is provided in [24,Appendix F]. Problem ( 18) is a convex optimization that can train robust neural networks. However, directly using (18) for adversarial training can be intractable due to the large number of constraints that arise when we include all D matrices associated with all such that X + 2 X. To this end, we can use the approximation in Algorithm 2 and sample a subset of the diagonal matrices. The optimality gap again can be characterized with Theorem 2.
In this section, we focus on experimenting with the hinge loss. The experiment results with the squared loss convex adversarial training formulation (18) are provided in [24,Appendix A.1]. For all experiments, CVX [27] with the MOSEK [28] solver was used for solving the optimizations in Algorithm 1 and Algorithm 2 on a laptop computer.
We use numerical experiments to demonstrate the quality of the neural networks trained using the convex standard training algorithm (Algorithm 1). The experiment was performed on a randomly-generated dataset with n = 40 and d = 2. The upper bound on the number of ReLU activation patterns is P 4 e(39) 2 2 = 11239. We ran Algorithm 1 to train neural networks using the hinge loss with the number of D i matrices equal to 4, 8, 16, . . . , 2048, and with chosen as a commonly-used value 10 4 . We repeated this experiment 15 times for each setting, and plotted the mean optimized loss in Figure 1. The error bars show the loss achieved in the best and the worst runs. When there are more than 128 matrices (much less than the theoretical bound on P ), Algorithm 1 yields consistent and favorable results. Further increasing the number of D i matrices does not produce a significantly lower loss. This result supports the findings of Theorem 2.
By Theorem 2, P s = 128 corresponds to a confidence level of ⇠ = 0.318.
To analyze the decision boundaries obtained from convex adversarial training, we ran Algorithm 1 and Algorithm 2 on 34 random points in 2-dimensional space for binary classification. The algorithms were run with the parameters = 10 9 , P s = 360 and ✏ = 0.08. A bias term was included by concatenating a column of ones to the data matrix X. The decision boundaries shown in Figure 2 confirm that Algorithm 2 fits the perturbation boxes as designed, coinciding with the theoretical prediction [12,Figure 3]. For illustration purposes, the regularization parameter is small to reduce the smoothing of `2 regularization. Experiments with different choices of [24,Appendix A.2] show that larger values yield similar behaviors, and that the decision boundaries by Algorithm 2 are more robust than GD-PGD boundaries.
This subsection visualizes that for a neural network trained with Algorithm 2, the convex landscape and the non-convex landscape overlap for an `1-norm bounded perturbation with radius ✏ added upon a training point x k . We use the same data and parameters as in Section VII-B to train a neural network. We then randomly pick one of the training points x k , and plot the loss around x k for the convex objective (10a) and the non-convex objective (2). Specifically, we define
where d ik is the k th entry of D i , y k is the training label corresponding to x k , and v ? i , w ? i are the optimizers returned by Algorithm 2. Moreover, u ? j and ↵ ? j are the neural network weights recovered from v ?
i and w ? i with (7). We plot `convex `nonconvex for k k 1 0.3 and zoom in to k k 1 0.08 in Figure 3. When `convex `nonconvex is zero, the convex objective provides an exact certificate for the non-convex loss function. The right figure shows that the difference is zero for k k 1 0.08, and thereby verify that the convex objective (10a) provides an exact certification of the non-convex loss function (2) around the training points.
We then verified the real-world performance of the proposed convex training methods on a subset of the CIFAR-10 image classification dataset [29] for binary classification between the second class and the eighth class. The subset consists of 600 images downsampled to d = 147. The parameters were chosen as ✏ = 10, = 10 4 , and P s = 36, so the widths of the recovered neural networks were at most 72. For back-propagation methods, the network width m was set to 72.
The hinge loss has a flat part with zero gradient. To generate adversarial examples even in this part, we treat it as "leaky hinge loss": max(⇣(1 ŷ • y), 1 ŷ • y), where ⇣ ! 0 + . Hence, the FGSM calculation evaluates to Algorithm 1 and Algorithm 2 are compared with traditional back-propagation methods GD-FGSM and GD-PGD. For GD-PGD, we used = ✏/30 and ran PGD for 40 steps.
Table I presents the CIFAR-10 experiment results. Algorithm 1 achieved a slightly higher clean accuracy compared with GD-std, and returned a much lower training cost. Such behavior supports the findings of Theorem 2. The convex adversarial training algorithm (Algorithm 2) achieved better accuracy on clean data and adversarial data compared with GD-FGSM and GD-PGD. While Algorithm 2 solves the upper bound problem (15), it returned a lower training objective compared with GD-FGSM and GD-PGD, showing that the back-propagation methods failed to find an optimal network. Moreover, the back-propagation methods are highly sensitive to initializations and hyperparameter choices. In contrast, since Algorithm 1 and Algorithm 2 solve convex programs, they are much less sensitive and are guaranteed to converge to their global optima. Compared with Algorithm 1, Algorithm 2 retains the advantage in the absence of spurious local minima while vastly improving adversarial robustness.
This paper proposes a novel "convex adversarial training" method that solves convex programs to train robust neural networks. Compared with traditional adversarial training methods, the favorable properties of convex optimization endow convex adversarial training with the following advantages:
• Global convergence to an upper bound: For the hinge loss and the squared loss, convex adversarial training provably converges to an upper bound on the globally optimal cost, offering superior interpretability. • Guaranteed adversarial robustness on training data:
As shown in Theorem 4, the inner maximization over the robust loss function is solved exactly. • Hyperparameter-free: In practice, Algorithm 2 can automatically determine its step size with line search, not requiring any preset parameters. • Immune to vanishing gradients: The convex training method avoids this problem completely because it does not rely on back-propagation. Overall, convex adversarial training makes it easier to train robust and interpretable neural networks, potentially facilitating their applications in the control of safety-critical systems. While this work explicitly focuses on one-hiddenlayer fully-connected networks, the same robust optimization analysis extends to more sophisticated architectures, since deeper networks [30], vector-output networks [31], and certain ConvNets [32] also have similar convex training representations.
Authorized licensed use limited to: Univ of Calif Berkeley. Downloaded on December 31,2022 at 10:02:38 UTC from IEEE Xplore. Restrictions apply.