Neural networks are vulnerable to adversarial examples and researchers have proposed many heuristic attack and defense mechanisms. We address this problem through the principled lens of distributionally robust optimization, which guarantees performance under adversarial input perturbations.   By considering a Lagrangian penalty formulation of perturbing the underlying data distribution in a Wasserstein ball, we provide a training procedure that augments model parameter updates with worst-case perturbations of training data. For smooth losses, our procedure provably achieves moderate levels of robustness with little computational or statistical cost relative to empirical risk minimization. Furthermore, our statistical guarantees allow us to efficiently certify robustness for the population loss. For imperceptible perturbations, our method matches or outperforms heuristic approaches.
 Consider the classical supervised learning problem, in which we minimize an expected loss E P0 [ (θ; Z)] over a parameter θ ∈ Θ, where Z ∼ P 0 , P 0 is a distribution on a space Z, and is a loss function. In many systems, robustness to changes in the data-generating distribution P 0 is desirable, whether they be from covariate shifts, changes in the underlying domain BID2 , or adversarial attacks BID22 BID29 . As deep networks become prevalent in modern performance-critical systems (perception for self-driving cars, automated detection of tumors), model failure is increasingly costly; in these situations, it is irresponsible to deploy models whose robustness and failure modes we do not understand or cannot certify.Recent work shows that neural networks are vulnerable to adversarial examples; seemingly imperceptible perturbations to data can lead to misbehavior of the model, such as misclassification of the output BID22 BID40 BID29 BID36 . Consequently, researchers have proposed adversarial attack and defense mechanisms BID41 BID53 BID47 BID12 BID23 BID33 BID51 . These works provide an initial foundation for adversarial training, but it is challenging to rigorously identify the classes of attacks against which they can defend (or if they exist). Alternative approaches that provide formal verification of deep networks BID24 BID26 are NP-hard in general; they require prohibitive computational expense even on small networks. Recently, researchers have proposed convex relaxations of the NP-hard verification problem with some success BID28 BID45 , though they may be difficult to scale to large networks. In this context, our work is situated between these agendas: we develop efficient procedures with rigorous guarantees for small to moderate amounts of robustness.We take the perspective of distributionally robust optimization and provide an adversarial training procedure with provable guarantees on its computational and statistical performance. We postulate a class P of distributions around the data-generating distribution P 0 and consider the problem minimize DISPLAYFORM0 The choice of P influences robustness guarantees and computability; we develop robustness sets P with computationally efficient relaxations that apply even when the loss is non-convex. We provide an adversarial training procedure that, for smooth , enjoys convergence guarantees similar to non-robust approaches while certifying performance even for the worst-case population loss sup P ∈P E P [ (θ; Z)]. On a simple implementation in Tensorflow, our method takes 5-10× as long as stochastic gradient methods for empirical risk minimization (ERM), matching runtimes for other adversarial training procedures BID22 BID29 BID33 . We show that our procedure-which learns to protect against adversarial perturbations in the training dataset-generalizes, allowing us to train a model that prevents attacks to the test dataset.We briefly overview our approach. Let c : Z × Z → R + ∪ {∞}, where c(z, z 0 ) is the "cost" for an adversary to perturb z 0 to z (we typically use c(z, z 0 ) = z − z 0 2 p with p ≥ 1). We consider the robustness region P = {P : W c (P, P 0 ) ≤ ρ}, a ρ-neighborhood of the distribution P 0 under the Wasserstein metric W c (·, ·) (see Section 2 for a formal definition). For deep networks and other complex models, this formulation of problem FORMULA0 is intractable with arbitrary ρ. Instead, we consider its Lagrangian relaxation for a fixed penalty parameter γ ≥ 0, resulting in the reformulation minimize θ∈Θ F (θ) := sup DISPLAYFORM1 where φ γ (θ; z 0 ) := sup z∈Z { (θ; z) − γc(z, z 0 )} .(See Proposition 1 for a rigorous statement of these equalities.) Here , we have replaced the usual loss (θ; Z) by the robust surrogate φ γ (θ; Z); this surrogate (2b) allows adversarial perturbations of the data z, modulated by the penalty γ. We typically solve the penalty problem (2) with P 0 replaced by the empirical distribution P n , as P 0 is unknown (we refer to this as the penalty problem below).The key feature of the penalty problem (2) is that moderate levels of robustness-in particular, defense against imperceptible adversarial perturbations-are achievable at essentially no computational or statistical cost for smooth losses . Specifically , for large enough penalty γ (by duality, small enough robustness ρ), the function z → (θ; z) − γc(z, z 0 ) in the robust surrogate (2b) is strongly concave and hence easy to optimize if (θ, z) is smooth in z. Consequently , stochastic gradient methods applied to problem (2) have similar convergence guarantees as for non-robust methods (ERM). In Section 3, we provide a certificate of robustness for any ρ; we give an efficiently computable data-dependent upper bound on the worst-case loss sup P :Wc(P,P0)≤ρ E P [ (θ; Z)]. That is, the worst-case performance of the output of our principled adversarial training procedure is guaranteed to be no worse than this certificate. Our bound is tight when ρ = ρ n , the achieved robustness for the empirical objective. These results suggest advantages of networks with smooth activations rather than ReLU's. We experimentally verify our results in Section 4 and show that we match or achieve state-of-the-art performance on a variety of adversarial attacks.Robust optimization and adversarial training The standard robust-optimization approach minimizes losses of the form sup u∈U (θ; z + u) for some uncertainty set U BID46 BID3 BID54 . Unfortunately, this approach is intractable except for specially structured losses, such as the composition of a linear and simple convex function BID3 BID54 BID55 . Nevertheless, this robust approach underlies recent advances in adversarial training BID49 BID22 BID42 BID12 BID33 , which heuristically perturb data during a stochastic optimization procedure.One such heuristic uses a locally linearized loss function (proposed with p = ∞ as the "fast gradient sign method" BID22 ): DISPLAYFORM2 One form of adversarial training trains on the losses (θ; (x i + ∆ xi (θ), y i )) BID22 BID29 , while others perform iterated variants BID42 BID12 BID33 BID51 . BID33 observe that these procedures attempt to optimize the objective E P0 [sup u p ≤ (θ; Z + u)], a constrained version of the penalty problem (2). This notion of robustness is typically intractable: the inner supremum is generally non-concave in u, so it is unclear whether model-fitting with these techniques converges, and there are possibly worst-case perturbations these techniques do not find. Indeed, it is NP-hard to find worst-case perturbations when deep networks use ReLU activations, suggesting difficulties for fast and iterated heuristics (see Lemma 2 in Appendix B). Smoothness, which can be obtained in standard deep architectures with exponential linear units (ELU's) BID15 , allows us to find Lagrangian worst-case perturbations with low computational cost.Distributionally robust optimization To situate the current work, we review some of the substantial body of work on robustness and learning. The choice of P in the robust objective (1) affects both the richness of the uncertainty set we wish to consider as well as the tractability of the resulting optimization problem. Previous approaches to distributional robustness have considered finitedimensional parametrizations for P, such as constraint sets for moments, support, or directional deviations BID13 BID16 BID21 , as well as non-parametric distances for probability measures such as f -divergences BID4 BID5 BID30 BID34 , and Wasserstein distances BID48 BID7 . In constrast to f -divergences (e.g. χ 2 -or Kullback-Leibler divergences) which are effective when the support of the distribution P 0 is fixed, a Wasserstein ball around P 0 includes distributions Q with different support and allows (in a sense) robustness to unseen data.Many authors have studied tractable classes of uncertainty sets P and losses . For example, BID4 and BID38 use convex optimization approaches for fdivergence balls. For worst-case regions P formed by Wasserstein balls, , BID48 , and BID7 show how to convert the saddle-point problem (1) to a regularized ERM problem, but this is possible only for a limited class of convex losses and costs c. In this work, we treat a much larger class of losses and costs and provide direct solution methods for a Lagrangian relaxation of the saddle-point problem (1). One natural application area is in domain adaptation BID31 ; concurrently with this work, Lee & Raginsky provide guarantees similar to ours for the empirical minimizer of the robust saddle-point problem (1) and give specialized bounds for domain adaptation problems. In contrast, our approach is to use the distributionally robust approach to both defend against imperceptible adversarial perturbations and develop efficient optimization procedures. Explicit distributional robustness of the form (5) is intractable except in limited cases. We provide a principled method for efficiently guaranteeing distributional robustness with a simple form of adversarial data perturbation. Using only assumptions about the smoothness of the loss function , we prove that our method enjoys strong statistical guarantees and fast optimization rates for a large class of problems. The NP-hardness of certifying robustness for ReLU networks, coupled with our empirical success and theoretical certificates for smooth networks in deep learning, suggest that using smooth networks may be preferable if we wish to guarantee robustness. Empirical evaluations indicate that our methods are in fact robust to perturbations in the data, and they match or outperform less-principled adversarial training techniques. The major benefit of our approach is its simplicity and wide applicability across many models and machine-learning scenarios.There remain many avenues for future investigation. Our optimization result (Theorem 2) applies only for small values of robustness ρ and to a limited class of Wasserstein costs. Furthermore, our statistical guarantees (Theorems 3 and 4) use · ∞ -covering numbers as a measure of model complexity, which can become prohibitively large for deep networks. In a learning-theoretic context, where the goal is to provide insight into convergence behavior as well as comfort that a procedure will "work" given enough data, such guarantees are satisfactory, but this may not be enough in security-essential contexts. This problem currently persists for most learning-theoretic guarantees in deep learning, and the recent works of BID1 , BID18 , and BID39 attempt to mitigate this shortcoming. Replacing our current covering number arguments with more intricate notions such as margin-based bounds BID1 would extend the scope and usefulness of our theoretical guarantees. Of course, the certificate (15) still holds regardless.More broadly, this work focuses on small-perturbation attacks, and our theoretical guarantees show that it is possible to efficiently build models that provably guard against such attacks. Our method becomes another heuristic for protection against attacks with large adversarial budgets. Indeed, in the large-perturbation regime, efficiently training certifiably secure systems remains an important open question. We believe that conventional · ∞ -defense heuristics developed for image classification do not offer much comfort in the large-perturbation/perceptible-attack setting: · ∞ -attacks with a large budget can render images indiscernible to human eyes, while, for example, · 1 -attacks allow a concerted perturbation to critical regions of the image. Certainly · ∞ -attack and defense models have been fruitful in building a foundation for security research in deep learning, but moving beyond them may be necessary for more advances in the large-perturbation regime.
We provide a fast, principled adversarial training procedure with computational and statistical performance guarantees.
{"src": "scitldr-AIC_train", "paper_id": "Hk6kPgZA-"}