Certifying Some Distributional Robustness with Principled Adversarial Training

Introduction

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 [ASgoodfellow2015explaining, NguyenYoCl15, ASkurakin2016adversarial, Moosavi-DezfooliFaFr16]. Consequently, researchers have proposed adversarial attack and defense mechanisms [PapernotMcGoJhCeSw16, ASpapernot2016limitations, PapernotMcWuJhSw16, RozsaGuBo16, AScarlini2017towards, HeWeChCaSo17, MadryMaScTsVl17, TramerKuPa17]. 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 [HuangKwWaWu17, ASkatz2017reluplex, KatzBaDiJuKo17] 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 [KolterWo17, RagunathanStLi18], though they may be difficult to scale to large networks. 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. Postulating a class $\mathcal{P}$ of distributions around the data-generating distribution $P_{0}$, we consider

Compared to the conference version of our manuscript [SinhaNaDu18], we have made substantial progress in our theoretical and empirical development. First, we provide additional theoretical results that allow instantiating our previous abstract computational and statistical guarantees in concrete learning scenarios involving neural networks (Section LABEL:section:examples). Secondly, we conduct extensive experiments to provide i) evaluations of adversarial training methods on more realistic large-scale classification scenarios (Sections LABEL:section:dogs) than what the current literature provides and ii) an empirical analysis of the gap between our theoretical bounds and empirical performance under various adversarial attacks (Section LABEL:section:three-choose-two).

One such heuristic uses a locally linearized loss function (proposed with $p=\infty$ as the “fast gradient sign method” [ASgoodfellow2015explaining]):

To situate the current work, we review some of the substantial body of work on robustness and learning. The choice of $\mathcal{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 finite-dimensional parametrizations for $\mathcal{P}$, such as constraint sets for moments, support, or directional deviations [ASchen2007robust, DelageYe10, ASgoh2010distributionally], as well as non-parametric distances for probability measures such as $f$-divergences [Ben-TalHeWaMeRe13, BertsimasGuKa13, LamZh15, MiyatoMaKoNaIs15, DuchiGlNa16, NamkoongDu16], and Wasserstein distances [EsfahaniKu15, Shafieezadeh-AbadehEsKu15, ASblanchet2016robust, GaoKl16, BlanchetKaZhMu17, GaoChKl17, KuhnEsNgSh19]. In constrast to $f$-divergences (e.g. $\chi^{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.

Proposed approach

For $\rho\geq 0$ and distribution $P_{0}$, we let $\mathcal{P}=\{P:W_{c}(P,P_{0})\leq\rho\}$, considering the Wasserstein form of the robust problem (1) and its Lagrangian relaxation (2) with $\gamma\geq 0$. The following duality result [BlanchetMu16, GaoKl16] gives the equality (2) for the relaxation and an analogous result for the problem (1). We give an alternative proof in Appendix LABEL:sec:proof-duality for convex, continuous cost functions.

Leveraging the insight (4), we give up the requirement that we wish a prescribed amount $\rho$ of robustness (solving the worst-case problem (1) for $\mathcal{P}=\{P:W_{c}(P,P_{0})\leq\rho\}$) and focus instead on the Lagrangian penalty problem (2) and its empirical counterpart

1 Optimizing the robust loss by stochastic gradient descent

We now develop stochastic gradient-type methods for the relaxed robust problem (7), making clear the computational benefits of relaxing the strict robustness requirements of formulation (5). We begin with assumptions we require, which quantify the amount of robustness we can provide.

To guarantee that the robust surrogate (2b) is tractably computable, we also require a few smoothness assumptions. Let $\left\|{\cdot}\right\|_{*}$ be the dual norm to $\left\|{\cdot}\right\|$; we abuse notation by using the same norm $\left\|{\cdot}\right\|$ on $\Theta$ and $\mathcal{Z}$, though the specific norm is clear from context.

Our distributionally robust framework (2) is general enough to consider adversarial perturbations to an arbitrary subset of coordinates in $Z$. For example, it is appropriate in certain applications to hedge against adversarial perturbations to a small fixed region of an image [BrownMaRoAbGi17]. By modifying the cost function $c(z,z^{\prime})$ to take value $\infty$ outside this small region, our general formulation covers such variants. In Section LABEL:sec:supervised, we illustrate this modification for supervised-learning scenarios, where we adversarially perturb feature vectors of datapoints but not their labels.