Revisiting and Advancing Fast Adversarial Training Through the lens of Bi-Level Optimization
Authors: Yihua Zhang
Guanhua Zhang
Prashant Khanduri
Mingyi Hong
Shiyu Chang
Sijia Liu
Venue: ICLR 2022 Submitted (2022)
Keywords: fast adversarial training
bi-level optimization
adversarial robustness
adversarial defense

Abstract: Adversarial training (AT) has become a widely recognized defense mechanism to improve the robustness of deep neural networks against adversarial attacks. It is originated from solving a min-max optimization problem, where the minimizer (i.e., defender) seeks a robust model to minimize the worst-case training loss at the presence of adversarial examples crafted by the maximizer (i.e., attacker). However,the min-max nature makes AT computationally intensive and thus difficult to scale. Thus, the problem of FAST-AT arises. Nearly all the recent progress is achieved based on the following simplification: The iterative attack generation method used in the maximization step of AT is replaced by the simplest one-shot gradient sign-based PGD method. Nevertheless, FAST-AT is far from satisfactory, and it lacks theoretically-grounded design. For example, a FAST-AT method may suffer from robustness catastrophic overfitting when training with strong adversaries.

In this paper, we foster a technological breakthrough for designing FAST-AT through the lens of bi-level optimization (BLO) instead of min-max optimization. First, we theoretically show that the most commonly-used algorithmic specification of FAST-AT is equivalent to the linearized BLO along the direction given by the sign of input gradient. Second, with the aid of BLO, we develop a new systematic and effective fast bi-level AT framework, termed FAST-BAT, whose algorithm is rigorously derived by leveraging the theory of implicit gradient. In contrast to FAST-AT, FAST-BAT has the least restriction to placing the tradeoff between computation efficiency and adversarial robustness. For example, it is capable of defending sign-based projected gradient descent (PGD) attacks without calling any gradient sign method and explicit robust regularization during training. Furthermore, we empirically show that our method outperforms state-of-the-art FAST-AT baselines. In particular, FAST-BAT can achieve superior model robustness without inducing robustness catastrophic overfitting and losing standard accuracy.

Under review as a conference paper at ICLR 2022
REVISITING AND ADVANCING FAST ADVERSARIAL TRAINING THROUGH THE LENS OF BI-LEVEL OPTI- MIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Adversarial training (AT) has become a widely recognized defense mechanism improve the robustness of deep neural networks against adversarial attacks. It originated from solving a min-max optimization problem, where the minimizer (i.e., defender) seeks a robust model minimize the worst-case training loss in the presence of adversarial examples crafted by the maximizer (i.e., attacker). However, the min-max nature makes AT computationally intensive and thus difficult to scale. Thus, the problem of FAST-AT arises. Nearly all the recent progress is achieved based on the following simplification: The iterative attack generation method used in the maximization step of AT is replaced by the simplest one-shot gradient sign- based PGD method. Nevertheless, FAST-AT AT is far from satisfactory, and lacks theoretically- groundeed design. For example, FAST-AT method may suffer from robustness catastrophic overfitting when training with strong adversaries.
In this paper, we foster a technological breakthrough for designing FAST-AT through the lens of bi-level optimization (BLO) instead of min-max optimization. First, we theoretically show that the most commonly-used algorithmic specification of FAST-AT is equivalent the linearized BLO along the direction given by the sign of input gradient. Second, with the aid of BLO, we develop new systematic and effective fast bi-level AT framework, termed FAST-BAY whose algorithm is rigorously derived by leveraging the theory of implicit gradient. In contrast to FAST- AT, FAST-BAY BAT has the least restriction to placing the tradeoff between computation efficiency and adversarial robustness. For example. it is capable of defending sign-based projected gradient descent (PGD) attacks without calling any gradient sign method and explicit robust regularization during training. Furthermore, we empirically show that our method outperforms state-of-the-an art FAST-AL AT baselines. In particular, PAST-BAT can achieve superior model robustness without inducing robustness catastrophic overfitting and losing standard accuracy.
INTRODUCTION
Given the fact that machine learning (MI.) models can be easily fooled by tiny adversarial perturba- tions (also known as adversarial attacks) on the input (Goodfellow al. 20114; Carlini & Wagner
2017 Papernot et al. 2016),, learning robust deep neural networks (DNNs) is now a major focus in
research. Nearly all existing effective defense mechanisms (Madry et al. 2018 Zhang et al. 2019b Shafahi et al, 2019 Wong et al.) 2020; Zhang et al. 2019a; Athalyy et al. 2018a) are built on the ad- versarial training (AT) recipe, first developed in (Szegedy et 20.440114) and later formalized in (Madry
et al. 2018) using min-max optimization. In contrast to standard model training using empirical risk minimization, AT (Madry et al., 2018) calls min-max optimization. That is, a minimizer (i.e. defender) seeks to update model parameters against a maximizer (i.e. attacker) that aims to worsen the training loss by perturbing each training example.
The AT-type defenses have been widely adopted in various application domains including image 2014 Madry et al. 2018 Kurakin et al. 2017). object detection (Zhang & Wang 2019), natural language processing (Miyato et al. [016 Zhu et al.) 2019). and healthcare (Finlayson et al. 2019 Mahmood et al. 2019). Despite their effectiveness, the min-max optimization nature makes them difficult to scale. This is because multiple maximization steps
classification (Goodfellow et al.

---

Under review as a conference paper at ICLR 2022
(required by an iterative attack generator) are needed every model training step in AT. The resulting prohibitive computation cost prevents AT from a feasible solution to enhance adversarial robustness when computing resource is limited. For example, Xie et al. (2099) used 128 GPUs to make AT practical on ImageNet. Thereby, how to speed up AT without losing accuracy and robustness is now grand challenge for adversarial defense.
Very recently, some work attempted to develop computationalll--ffiicenn alternatives of AT, which we call 'fast' versions of AT (Shafahi al.) 2019 Zhang al. 2019a] WWnn al. 2020; Andriushchenko & Flammarion 2020). To the best of our knowledge, FAST-AT (Wong et al. 2020) and FAST-AT with gradient alignment (GA) regularization, termed FAST-AT- AT-GA (Andriushchenko Flammarion 2020), are the two state-of-th of-the--rrt art (SOTA) 'fast' versions of AT, since they achieve a significant reduction in computation complexity and preserve accuracy and robustness to some extent. To be specific, FAST-AT (Wong et al.] (020) replaces an iterative attack generator used in AT with a heuristics-base single-step attack generation method. Thus, it merely takes computation cost comparable to standard model training. However, FAST-AT suffers two main issues: (i) lack of stability, i.., large variance in performance (Li et. 2020), and (ii) robustness catastrophic overfitting, i.e. large drop of robustness when training with strong adversaries (Andriushchenko & Flammarion 2020). To alleviate these problems, AAnrrushcheenko & Flammarion (2020) proposed FAST-AT-GA by penalizing FAST-AT using an explicit robust regularization given by GA. However, will show that FAST-AT-GA encounters a new problem (iā): FAST- AT-GA hampers standard accuracy, making a poor accuracy-robustren tradcoff large attack budget (E 16/255), i.e. the improvement on RA is at cost of a sharp drop on SA. Given the limitations (i)- we ask:
How to design a eheooetically-groundeed 'fast' version of AT with improved stability, mitigated catastrophic overfitting, and enhanced accuracy-robustnes tradeoff?
To address above question, paper we revisit and advance AT through the lens of bi-level optimization (BLO) (Dempel (002). where we cast the attack generation problem as a lower-level optimization problem with constraints and the defense as an upper-level optimization problem in the objective. To the best of our knowledge, this is the first work to make solid connection between adversarial defense and BLO. Technically, we show that FAST-AT can be interpreted as BLO with linearized lower-level problems. Delving into linearization of BLO, propose novel, theoretically- groundde 'fast' AT framework, fast bi-level AT (TAST-BAT) Practically, Table I Table[highllihts highlights some achieved improvements over FAST-AT and FAST-AT-GA: When stronger train-time attack (i.e., e 16/255 vs. 8/255) is adopted, FAST-AT suffers a large degradation of robust accuracy (RA) and standard accuracy (SA), together with higher variances than proposed FAST-BAT Although FAST-AT-GA outperforms FAST-AT, it still incurs significant SA loss (over 2)) at 16 16/255. By contrast, FAST-BAT yields a more graceful SA-RA tradeoff: 9% improvement of SA without loss of RAA Different from FAST-AT-GA AT-GA, FAST- achieves above improvements in stability, RA and SA without resorting to any extra robust regularization and thus takes less computation cost.
Table I: Performance overview of proposed FAST- BAT vs. the baselines FAST-AT WWong al. 2020 and FAST-AT-GE (Andriushchenko Flammarion 2020) on (CIFAR-IO, PreActResNet-18) All methods are robustly trained under two perturbation budgets c 8/255 and 16/255 over 20 epochs. We use the early- policy (Rice et al. 2020) to report the model of best rohustness for each method. The evaluation metrics include robust accuracy (RA) against PGD-50-15 10 attacks (50-step PGD attack with 10 restarts) (Madry et 2018)) at 8/ /255 and 16/ 16/255 (test-time is same as the train-time), RA against Auto (AA) (Crace & Hein 2020 at < 8/ 8/255 and 16/255, and computation time (per epoch). The result a+s represents mean a and
standard deviation b over 10 random trials. All experiments are run on a single Tesla-P100 GPU.
RA- (%)
RA-PGD (%)
RA-AA (%)
RA-AA (%)
SA (%)
SA (%)
Method
Time (s)
(c 8/255)
(c = 16/255)
(c = 8/255)
(c = 16/255)
(c = 8/255)
(c 16/255)
FAST-AT
45.47=0.39
21.79=0.93
41.97=00.1
12.57=0.33
81.72-0.36
46.02=2.79
42
FAST-AT-GA
47.43-00.2
26.22=40.19
43.52++0.22
18.03-40.30
79 -9.84-0.49
58.57-t1.19
150
FAST-BAT
48.74=0.11
26.15=0.12
44.89+0.12
18.21=0.15
79.43=0:08
67.79:2.08
135
Contributions. We summarize our contributions below.
@ We propose a new formulation of adversarially robust training through the lens of BLO, yielding a
novel and theoretically- groonndd interpretation of FAST-AT.
@ We propose a new systematic and effective fast BLO-oriented AT framework, termed FAST-BAT. with rigorously-establiste theory and algorithm.
2

---

Under review as a conference paper at ICLR 2022
I We conduct extensive experiments FAST-BAT, showing its improved stability, mitigated catastrophic overfitting, and enhanced accuracy-robustness tradeoff; see illustrations in Table
2 RELATED WORK
Adversarial attack. Adversarial attacks are techniques to generate malicious perturbations that are
imperceptible to humans but can mislead the machine learning (ML. models (Goodfellow et al. 2014
Carlini & Wagner 2017; Croce & Hein 2020; Xu et al., 2019 Athalye et al. 2018b). A popular threat model that an adversary used is known as norm ball constrained attack (p {0, 1, 2, }o))
This is also the focus of this paper. The adversarial attack has become a major approach to evaluate the robustness of deep neural networks (DNNs) and thus, help build safe artificial intelligence in
many high stakes applications such as autonomous driving (Deng et al. 20200] Kumar et al. 2020).
surveillance (Thys et al. 2019 Xu et al. 2020), and healthcare (Finlayson et 2019).
Adversarial defense and robust training at scale. Our work falls into the category of robust training, which was mostly built upon min-max optimization. For example, Madry al. (2018) established the framework of AT for the first time, which has been recognized as one of the most powerful defenses (Athalye et al. (0188).. Extended from AT, TRADES (Zhang et al. 2019b) sought the optimal balance between robustness and generalization ability. Further, AT -tppe defense has been generalized to the semi-/self semiersel--superviseed settings (Carmon al. 2019 Chen et al.) 2020) and integrated [ with certified defense techniques such randomized smoothing (Salman et al. 2019).
Despite the effectiveness of AT and its variants, they need to take high computation costs. How to speed up AT without losing performance remains open question. Some recent works attempted to impose algorithmic simplifications to AT, leading to fast but approximate AT algorithms, such 'free" AT (Shafahi et al. 2019), you only propagate once (YOPO) (Zhang et al.. 2019a), FAST- AT (Wong et J (2020), and FAST-AT regularized by gradient alignment (termed FAST-AT-GA) (Andriushchenko Flammarion| 2020). In particular, FAST-AT and FAST-AT-GA are the baselines most relevant to ours since they were designed with the least computation complexity. However, their defense performance far from satisfactory. For example, FAST-AT has poor training stability
(i et al. 2020) and suffers catastrophic overfitting when facing strong attacks (Andriushchenko & Flammarion 2020). In contrast to FAST-AT, FAST-AT-GA yields improved robustness but has poor accuracy robusstees tradeoff (e.g.. T..le[]. In this paper, we aim to advance the algorithm foundation of 'fast robust training' through the lens of BLO (bi-level optimization). We will show that the proposed PAST-BAT can lead stable robust learning without suffering catastrophic overfitting and graceful tradeoff between accuracy and robustness.
Bi-level optimization (BLO). BLO is unified hierarchical learning framework, where the objec- tive and variables of an upper-level problem depend on the optimizer of certain lower-level problems. The BLO problem in its most generic form is a class of very challenging problems, and thus, the
design of algorithms and theory for BLO focuses on special cases (Vicente et al.) 1994] White
Anandalingam 1993, Gould et al. 2016 Ghadimi & Wang 2018 Ji al. 2020 Hong al. 2020). In practice, some successful applications of BLO to ML have been witnessed in meta-lcarning (Rajeswaran et al., 2019). data poisoning attack design (Huang et al. 2020). and reinforcement learning (Chen et al.) (019). However, as will be evident later, the existing BLOO approach is not directly applied adversarial defense due to the presence of the constrained nonconvex lower-level problem (for attack generation). To the best of our knowledge, our work makes rigorous connection between adversarial defense and BLO for the first time.
A BI-LEVEL OPTIMIZATION VIEW ON FAST-AT
Preliminaries on FAST-AT. FAST-AT is designed for solving the adversarial training problem (Madry et al. 2018) given below
minimize E(xaiED
maximize (0, 5.y)
(I)
bEc
where E R denotes model parameters, D is the training set consisting of labeled data pairs with feature and label y, 8 E Idd represents adversarial perturbations subject the perturbation
3

---

Under review as a conference paper at ICLR 2022
constraint C, e.g., C {6 ||0|| S E [0, 1]} for e-toleration -orm constrained attack (normalized to [0, 1). (x + 6) is then called adversarial example, and ex represents a training loss.
The standard solver to problem I is known AT (Madry et al. 2018). However, it has to call an iterative optimization method (e.g. K-step PGD attack) to solve the inner maximization problem of ①1. As result, AT' is computationally intensive. To improve its scalability, FAST-AT that only takes the single-step PGD attack for inner maximization was proposed and successfully implemented in (Wong et 2020).
The algorithm backbone of FAST-AT is summarized below.
FAST-AT algorithm
Let O2 be the model parameters at iteration t. The (t 1) iteration is given by ① (Inner maximization by 1-step PGD): 8 t- Pe (60 + a sigu (V srrr x + on v))),
where Pa(a) denotes the projection operation that projects the point onto C, i.e., Pc(z) arg minsec |6 II. 6n is a random uniform initialization within [0. 1]. >>>>>>>> is a proper learning rate (e.g.. 1.25e), and sign(.) ) the element-wise sign operation.
@ (Outer minimization for model training): This can be conducted by any standard optimizer, e.g., SGD. That is, 0.+1 t 0: 3V oz (0,,x x + 8, y). where / > 0 a proper learning rate
(e.g., cyclic learning rate), and 5 is provided from the inner maximization step.
Roughly speaking, FAST-AT is simplification of AT using 1-step PGD for inner maximization. However, as shown in [Wong et al. (2020), the successful implementation of FAST-AT is different from the 1-step PGD-based AT (Madry et al. 2018) due to the former's s sophisticated hyperparameter choices in a. 5u. and B. Despite the efficacy of FAST-AT in some cases, /Andriushchenko & Flammarion| (2020) demonstrated that could lead to the issue of robustness catastrophic overfitting when facing strong adversaries during training. In the literature, there was no grounded theory to justify the pros and cons of FAST-AT, We will show that BLO provides a promising solution.
BLO: Towards unified formulation of robust training. BLO (bi-level optimization) is unified hierarchical learning framework, involving two levels (i.e., upper and lower levels) of optimization tasks, where one task is nested inside the other (i.e., the objective and variables of an upper-level problem depend on the optimizer of the lower-level problem). The hierarchical learning framework provided by BLO can be used to precisely depict robust training paradigm. Specifically, we can cast robustification as an upper-level problem whose optimization relies on lower-level problem defined for attack generation. Thus, the BLO formulation of (I) is given by [4..)) 8" (0; x, x0:x,)), v)] subject to (0 v) arg min fat 6;
minimize
dEc
where latk denotes an attack objective. For notation simplicity, we will use data-omitted expressions of fu. latk. and 8* The formulation (2) has two key differences from
First, the lower-level attack objective fatk is customizable, not necessarily to be same as the opposite of the training objective, -ht- As will be evident later, the flexibility of attack configuration in 2 enables us to interpret FAST-AT through the lens of BLO.
Second, BLO calls an optimization routine different from min-max optimization used by ( Even
we set latk = far, problem (2) does not reduce to (1) due to the presence of lower-level constraint
8 E C (see rigorous mallysis in Appendix B). Specifically, solving the upper-level problem of 2 by gradient descent yields
dl (0, (0)) (oli.
d8 d0)(
(0,
(3)
d0
d0
IG
where the superscript T denotes the transpose operation, and V Veln (0, 8 (0)) denotes the partial
derivative with respect to (w.It.) the first input argument 0. In (3) d (0)
de E x is referred to as implicit gradient (IG) because is defined through an implicit constrained optimization problem mingec Latk- The dependence IG is 'fingerprint' of BLO ( in contrast to AT or FAST-AT.
-LObled interpretation of FAST-AT. In what follows, we demonstrate how FAST-AT relates to BLO. Our main finding is summarized below.
4

---

Under review as a conference paper at ICLR 2022
Bi-level interpretation of FAST-AT
FAST-AT can be interpreted as the lower-level linearized BLO with = do and À = 1/0:
minimize 0
(1, (0)
subject (0) arg min [(6 " (ign(Vs=faau(0000) (A/2) 2|
(4)
SEC
where z is the linearization point, Va=zfatk denotes the partial derivative of Latk (w.r.t. d) evaluated at z, sign( Vo=zlatk (0, 8)) is the lincarization direction, and is regulariza- tion parameter associated with the quadratic residual of linearization.
Our justification on the above claim elaborated on below.
First, the simplified lower-level problem of leads to the closed-form solution
8 (0) arg min (A/2) 8 (L/A)sign(Va-<<4n
sgc
=cc (z (1/ (s/))sign( (o==zatk 6))),
(5)
which is given by the 1-step PGD attack with initialization and learning rate (1/A). In the lin- carization used in ( quadratic regularization term (with regularization parameter X) is introduced ensure the strong convexity of the inner-level attack objective within the constraint set 8 E C. Assisted by that, the lower-level solution is unique and its closed form is given by ( Note that imposing such strongly convex regularizer is also commonly used to stabilize the convergence of min-max optimization and BL.O (Qian et al. 2019 Hong et al. 2020). If we set z óg and 1/a, then (5) precisely depicts the inner maximization step used FAST-AT.
Second, by substituting (5) into the upper-level problem of (4) we can then follow (3) to update the model parameters However, this calls the computation differentiable, then based the closed-form of (0) in (5), IG becomes
(0) If we regard Pc is de
dō' (0)
de = 0,
(6)
where we use two facts: (1) The lincarization point z is independent 0, i.e. z = o And (2) deign(-) = 0 holds almost everywhere. Please refer to Appendix C for a rigorous proof of using
d0
KKT conditions. Clearly, the use of gradient sign method simplifies the IG computation. Substituting (6) into (3), the upper-level optimization of 4 yields 0 + 0 - 3V ee (0, 8* (0)) (with learning rate
3), which is precisely same as the outer minimization step used in FAST-AT.
The aforementioned analysis shows that the linearized BLO is equivalent to FAST-AT by setting the linearization point and the regularization parameter
óg and À = 1/a.
FAST-BAT: ADVANCING FAST-AT BY BLO
FAST-BAT and rationale. The key take-away from (4) is that the conventional FAST-AT adopts the sign of input gradient to linearize the lower-level attack objective. However, a more natural and wiser choice is to use the first-order Taylor expansion for linearization. By doing so, problem can be modified to the form of FAST-BAT
Bx.,) (0, 80))
subject to (0) arg min [66 z) Va-zzauu 8) (A/2)]18 - sec
where similar to ( the lower-level problem can be solved analytically as
(0) Pc (z (L/A)V
(8)
In contrast to (6) the IG associated with 7 is no longer vacant since the gradient sign operation
not present in 88 b. To compute IG, the auto titto-iiffrrentittion (which calls the chain rule) can be applied to the closed-form of 80))). However, this will not give solution since the projection operation Pe is not smooth and thus, the use of chain rule does not yield rigorous derivation. Therefore, the IG challenge arises, which will be addressed in what follows.
accurate and generalizable IG
5

---

Under review as a conference paper at ICLR 2022
IG theory for FAST-BAT.
The problem of FAST-BAT falls into class of very challenging BLO problems, which require constrained lower-level optimization. The unconstrained case is easier to handle since can apply the implicit function theory to the stationary condition of the lower-level problem to obtain IG (Hong et al. 2020). Yet, in the case of constrained problems, a stationary point could violate the constraints, and thus the stationary condition becomes non-applicable.
In problem
7. we are dealing with a special class of lower-level constraints linear constraints:
C = {118] S e, E [-x, x|] B5 & b, with B == [ b max ( (-11,
min 1 1-
By exploiting above linearly constrained problem structure, we show that the IG challenge associated with 7 can be addressed via MaiisshKKhn---eeee (KKT) conditions. We summarize main theoretical result below and refer readers to Appendix AAarr detailed derivation.
Theorem With Hessian-free assumption, i.e., Vaslatk = 0, the IG (implicit gradient) of is
d5 (0) -L/A) d0
He, with He = [1 <91 ...
1pi587 ea].
(10)
where 8' is given by (8) and (o 8*) Raxd denotes the second-order partial derivative
evaluated at and 6* (0), respectively. In Hc E Raxdd pp <q. E {0,1) denotes the indicator function over the constraint of {5 pr < 8 < q:). which returns 1 if the constraint is satisfied, 5 denotes the ith entry of 6 (0). P. max{-c,- -1; and qi minfc, 1 x; characterize the boundary of the linear constraint ( for the variable 6,, and e, Rd denotes the basis vector with the ith entry being 1 and others being Os.
In Theorem T the rationale behind the Hessian-free assumption is that ReI neural networks commonly lead to piece-wise linear decision boundary w.r.t. the inputs (Moosavi-Dezfooli et al. 2019 Alfarra et al. 2020), and thus, its second-order derivative (Hessian) Va is close zero. In Appendix H we will empirically show that the Hessian-free assumption is reasonable for both ReLU and non ReUU neural networks.
FAST- BAT algorithm and implementation. Similar to FAST-AT or AT, the FAST-BAT algorithm follows the principle of alternating optimization. Specifically, it consists of the IG-based upper-level gradient descent (3) interlaced with the lower-level optimal attack ( We summarize the FAST-BAT algorithm below.
PAST-BAT algorithm
The (t + 1)th upper-level iteration of FAST-BAT BAT is given below @ (Lower-level solution): Obtain 5* (0,) from 8);
@ (Upper-level model training): Integrating the IG I0 into
3 call SGD to update
8" 80) He (O., 8' (0.), (11) where a1, 02 > are learning rates associated with the standard model gradient and the IG-augmented descent direction, respectively.
oc+1 0: - a1 (olu, 8' (0.)) az( (-2(-1/))
is clear from IT that to train robust model, FAST- BAT can be dissected into the regular FAST-AT update (i.e., a1 asssociatd term) and the additional update that involves IG, (i.e., assaassccated term). To successfully implement FAST-BAT, we highlight some key FAST-AT (Wong et al. 2020) and FAST-AT-CE (Andriushchenko & Flammarion, 2020
setups different from
Choice of learning rate for IG-involved descent term: In [ the choice of 02 could affect the trade-off between accuracy and robustness (see empirical justification in AppendixE Clearly, if = O. then the upper-level model parameter updating step reduces to the standard FAST-AT. In Sec. we will show that the Or ces-associated term plays a positive role alleviating catastrophic robust overfitling. Meanwhile, X in ( could also affect the accuracy- robuutesssossstness tradeoff. For example, if + 0o, then 8 = 0 (no robustness gain). Spurred by above, we choose the following combination of 02 and X, 02/ X 0.101, which works well in practice; see Table AT.
Remark 1
we investigate two classes of linearization schemes. The first class is random constant linearization, which includes: "uniformly random
Remark 2 Choice of linearization point z: To specify 7

---

Under review as a conference paper at ICLR 2022
linearization", f.e., ôu as FAST-AT, and "random comerr linearization" under the c-radius Eoo- ball, i.e., z E c]. The second class is 1-step perturbation warm-up-based linearization, which includes the other specifications: "1-step PGD" Pe (òg + sign (V (0,, 6,))), and "1-step PGD w/o sign" z = Pc (ōg + +oV ).)). We consider the aforementioned linearization schemes since FAST-BAT combined with these linearizations takes computation cost comparable to the baselines FAST-AT and FAST-AT-GA, Our experiments show that FAST-BAT using " "1-step PGD w/o sign" leads the best defense performance; see justification in Table
EXPERIMENTS
5.1 EXPERIMENT SETUP
Datasets and model architectures. We will evaluate the effectiveness of our proposal under CIFAR- 10 (Krizhevsky & Hinton| 2009) and ImageNet (Deng et al.] (009). Unless specified otherwise, we will train DNN models PreActResNet (PARÑ)- 18 (He et 2006b) for CIFAR- 10, and ResNet (RN)-50 (He al. 2016a) for ImageNet. As a part of ablation study, we also train larger models PARN- 50 and WideResNet (WRN)-1688 Zagoruyko & Komodakis 2016) on CIFAR-10.
Baselines. We consider three methods our baselines: FAST-AT (Wong et al. 2020 FAST-AT- GA (Andriushchenko & Flammarion 2020). and PGD-2-AT (Madry et al. 20,8), i.e., the 2-step PGD attack-based AT. The primal criterion of baseline selection computation complexity. The training time of all methods including ours falls between the time of FAST-A' AT and that of FAST-AT- GA. We remark that when evaluating on ImageNet, we only compare ours with FAST- AT since as shown in Table 6 of (Andriushchenko & Flammarion] 2020), the other baseline methods did not show improvement over Fast-AT at the attack budget 2/255.
Training details. We choose the training perturbation strength c E (2.4.... 16] /655 for CIFAR- 10 and e 2/255 for ImageNet following (Wong et al. 2020 Andriushchenko & Flammarion 2020). Throughout the experiments, we utilize an SGD optimizer with a momentum of 0.9 and weight decay of 5 x 10-1 For CIFAR-10, train each model for 20 epochs in total, where we cyclic scheduler to adjust the learning rate. The learning rate linearly ascends from 0 to 0,2 within the first 10 epochs and then reduces to 0 within the last 10 epochs. Our batch size is set to 128 for all settings. In the implementation of FAST-BAT, we adjust the hyperparameter X from 255 /5000000 to 255/2000 2000 based on the specification of train-time For ImageNet, we strictly follows the setup given by Wong et al. (2020). In FAST-BAT, we set À = 255/300 /3000 For each method, we use the early stopping method to pick the model with best robust accuracy, following (Rice al. 2020). All the CIFAR-10 experiments are conducted on a single Tesla P-100 GPU and all ImageNet experiments run on single machine with two Tesla P- P00s. All the baselines are implemented using the recommended training configurations in their official GutHuub repos. We refer readers to AppendixD]fo for more details on training setup.
Evaluation details. For adversarial evaluation, we report robust test accuracy (RA) of a learned model against PGD attacks (Madry et al., 2018) (RA-PGD). Unless otherwise specified, we set the test-time perturbation strength (c) same as the train- value, and take 50-step PGD with 10 restarts for both CIFAR-10 10 and ImageNet evaluation. We also measure robust accuracy against AutoAttacks (Croce& & Hein| 2020), termed RA-AA. Further, we measure the standard accuracy (SA) against natural examples. Results averaged over 5 independent trials with different random seeds.
5.2 RESULTS
Table 3: SA and RA on ImageNet.
Overall performance of FAST-BAT. In Table 2 and 3 we compare the performance of our proposed FAST-BAT with base- lines on CIFAR- 10 and ImageNet, respectively.
Mothod
SA (%)
RA-PGD (%)
FAST-AT
60.90
43.43
FAST-BAT
60.18
44.64
First, we find that FAST-BAY consistently outperforms the other baselines across datasets and attack types. For example, FAST-BAT at least improves 1.35% RA-PGD and 1.41% RA-AA with test-time E == 8/255 in the training setup (CIFAR-10, 10, e = 8/255). On ImageNet, FAST-BAT outperforms FAST-AT by 1.23% when facing attacks with 2/255.
7

---

Under review as a conference paper at ICLR 2022
Table 2: SA, RA-PGD and RA-AA of different robust training methods in the setup (CIFAR-10, PARN-18 training with = 8/255) and (CIFAR-10, PARN-18 training with = 16/255), respectively. All the results are averaged over 5 independent trials with different random seeds.
CIFAR-10, 10, PARN-I8 trained with 8/255
RA-PGD (%)
RA-AA (%)
Method
(%)
12
<= 16
c=
<
16
FAST-AT
81.89-0.311
65.92 +0.11
45.44 +0.38
23.69
72.54
41,95 +0.13
7.91 =0.06
FAST-AT-GA
79.78.0047
65.74 10.19
47.32
10.35
28.67 10.26
11.57.0.32
71.60 10.39
43.45 10:27
9.48 _0.15
PGD-2-AT
83.26:0.28
65.59 +0.34
44.71
+0:42
23.67 +0.35
9.42 +0.35
73.28+0.155
41.73 +0:20
7:54+0:25
FAST-BAT
79.47 10:14
10:18
10:21
72.07
10:34
11.51 10.20
CIFAR-10,
PARN-18 trained with
16/255
FAST-AT
46.1312225
42.74 10.91
37.17
10.74
27.99
10.71
36.31
31,66
12.48
PAST-AT-GA
18.53=11.20
51.71
+0.90
43.86
+0067
35.46 +0.36
26.29 =0.14
53.61
11:10
38.69 +0.56
18.11 #:0.56
PGD-2-AT
69.40 10.30
59.25
10.16
48.79
10.31
32.12 15.63
24.30
10.48
61.90
20
41.59
10.22
15,40 10.29
FAST-BAT
67.81 2:0.8
59.35 10.13
1.012
37.71 10.36
26.07
20.25
62.16
10
43.64 1:0.25
18.18 10.34
Second, FAST-BAT leads to better SA-RA trade-off compared with the other baselines. For example, in the setup of (CIFAR-10 10, PARN-18 trained with e = 8/255), we observe that FAST-BAT outperforms FAST-AT-GA GA in RA, without losing SA.And in the setup of (CIFAR-10. PARN-18 trained with e = 16/255), FAST-BA BAST-BAT significantly outperforms FAST-AT-GA, with 9.28% SA improvement and comparable even better RA. Compared with PGD-2-AT, A-,, FAST-BAT is much more resilient against strong adversaries, e.g., 16.
Third, the robustness advantage of our method becomes more notable when the test-time attack budget becomes smaller than the train-time budget. For examples, the RA-AA improvement of FAST-BAT over FAST-AT-GA grows from 0.07% (evaluated at 16/255) to 4.95% (evaluated c = 8/255), and 8.55% (evaluated at e = 2/255) in the case of (CIFAR-10, trained with e 16/255)
Performance under different model architectures. Besides PARN-18 reported above, Table presents experiment results on both deeper (PARN-50) and wider (WRN-18-6) models. As we can see, FAST-BAT consistently yields RA improvement over the other baselines. We also note that PGD-2-AT could be a competitive bascline terms of SA, e.g., the case of (PARN-50, e = 8/255). In contrast to FAST-AT and FAST-AT AT-GA, FAST-BAY BAT is the only approach that yields an evident RA improvement over PGD-2-AT.
Table 4: Performance of different robust training methods under different model types. All the models are both trained and evaluated with same perturbation strength
SA(S)
RA-PGD(X)
SA(%)
RA-PGD(%)
Model
Method
(e 8/255)
= 8/255)
(e 16/255)
= 16/255)
PARN-50
FAST-AT
73.15+6.10
41,03+2.99
43.86:44.31
22.08+0.27
FAST-AT-GA
77.40.0.81
46.16.10.98
22.87.11.25
2G
83.53-0.17
46.17-40.59
68.88 08.88
22.37++0.41
PAST-BAT
78.9110.68
49.18.10.35
69.01
20.55
WR--
FAST-AT
84.3940.46
45.80++0.57
49, 19.39422.17
21.99+0.41
FAST-AT-GA
81.5110.38
48.29:10.20
45.95111366
23.1013.00
PGD-2-AT
10.52
45.47.10.14
72.11 10.33
23.61 10.16
FAST-BAT
81,6620.54
49,93-10.16
68. 12:00.47
25.63:0044
Mitigation of robustness catas- trophic overfitting. As shown in (Andriushchenko & Flammarion| 2020). FAST-AT suffers robust- ness catastrophic overfitting when the train-time and test-time attack strength 6 grows. Following (An- driushchenko & Flammarion, 2020). Figure presents two RA-PGD tra- jectories, i.e., training w/o early stop- ping and training w/ early stopping, versus the train- and test-time As we can see, FAST-AT AT encounters a sharp RA drop when >> 8 when early stopping is not used, consistent with (Andriuscchenko & Flammarion 2020). Assisted by early stopping, the overfitting
TAAR-KT PED 2 AT
Fast-RT PSD AT
70
Fist-AT-GA
Bobust Accurascy 1961
Fist-AT-A
BAT
60
Fest-BAT
38 32 16
(a) Without carly stopping
(b) With carly stopping
Figure I: RA-PGD of different robust training methods for (CIFAR- 10, PARN-18) with the same training and evaluation attack strengths.
8

---

Under review as a conference paper at ICLR 2022
of RA can be alleviated to some extent for FAST-AT, but its performance still remains the worst. Moreover, different from (Andriushchenko & Flammarion, 2020), we find that PGD-2-AT yields resilient performance against robustness catastrophic overfitting Our implementation gives more (Andrriinnnnhnheeeeeeee
positive baseline than the implementation of PGD-2-AT in (Andriushchenko & Flammarion 2020).
since the latter did not use random initialization to generate train-time attacks. Furthermore, Figure shows that our proposal mitigates the issue of robustness catastrophic overfitting and yields improved RA over the other baselines. We highlight that such a achievement made by FAST-BAT is 'free' of any robustness stability regularization, like gradient alignment used in FAST-AT-GA.
Gradient alignment for 'free'. As shown by Andriushchenko & Flammarion (2020), gradient alignment (GA) is a key performance indicator to measure the appearance of robustness catastrophic over- fitting. The insight from Figure suggested suggested that BAST-BAT mit- igate overfitting without using explicit GA regularization. Spurred by above, Figure presentss the GA score versus the training epoch num- ber, where GA characterizes the sensitivity of loss landscape against random input perturbations; see derivations in (Andriushchenko & Flammarion 2020). The higher GA is. the more stable the robust training is Figure 2 shows that FAST-BAY automatically enforces GA and it outperforms FAST-AT and PGD-2-AT. FAST-BAT remains very close to FAST-AT-GA- which maximizes GA using an extra train-time regularization The above empirical results imply that gradient alignment may be just a necessary condition for avoiding catastrophic overfitting, but not a sufficient one. A possible justification can be made from the perspective the flatness of the loss landscape. A higher gradient alignment implies a flatter loss landscape with respect to input perturbations. However, the direct penalization on the norm of the input gradient may not achieve the -fate-of-the-art model robustness.
14
Gradtene Alignment Scaee
Fest AT
PGD-2-AT
Fast-AF-GA
0.4
Fast
Number
Figure GA evaluation.
Table 5: RA of robust PARN-18 trained by the four differ- ent methods against adaptive attacks ('RA-PGD" column) and transfer attacks ( ("Transfer Attack' columns). Naturally trained PARN-18, PARN-50, and WRN-16-8 are used as surrogate models for PGD-20 attack with 8/255.
Sanity check for obfuscated gradients As pointed out by Athalyy al.) (2) model robustness could be overestimated due to obfuscated gradients. The model with obfuscated gradients could have "ob- fuscated' stronger resilience to white-box attacks than transfer (black-box) attacks. To justify the validity of FAST-BAT, Table summarizes the comparison between proposal and the other baselines when facing white-box adaptive and black-box transfer attacks. Firstly, RA increases if the transfer attack present for each method, implying that the transfer attack is weaker than the white-box adaptive attack. This is desired in the absence of obfuscated gradients. Moreover, FAST-BA BAT consistently outperforms the other three baselines when defending against both adaptive and transfer attacks. The absence of obfuscated gradients can also be justified by RA vs. the growth of attack budget in Table and the flatness of adversarial loss landscape in Figure. AT
RA RA-Tnesseer Attack(S))
Method
RA-PGD(S)
PARN-18
PARN-50
WRN-16-8
FAST-AT
45.44
76.35
76.94
77.23
PGD-2-XT
44.71
77.56
AAST-AT-GA
47.31
77.34
78.34
78.53
FAST-BAT(OHrS)
48.67
78.03
79.93
79.21
Ablation studies. In Appendix B we present additional empirical studies including 1) the sensitivity analysis of the linearization hyperparameter X, 2) the choice of the lincarization point, 3) the sensitivity analysis of a2, 4) the influence of Hessian matrix on ReLU, and 5) non non-ReLU neural networks.
6 CONCLUSION
In this paper, we introduce a novel bi-level optimization (BLO)-based fast adversarial training framework, termed BAT. The rationale behind designing fast robust training through the lens of BLO lies in two aspects. First, from the perspective of implicit gradients, we show that existing FAST-AT framework is equivalent to the lower-level linearized BLOO along the sign direction of input gradient. Second, we show that FAST-BAT enables the least restriction to achieve improved staibility of performance, mitigated catastrophic overfitting, and enhanced accuracy- robusstessss trade-off. To the best of our knowledge, we for the first time establish the theory and the algorithmic foundation of BLO for adversarially robust training. Extensive experiments provided to demonstrate the superiority of our method to state-of-the-a accelerated AT baselines.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Motasem Alfarra, Adel Bibi, Hasan Hammoud, Mohamed Gaafar, and Bernard Ghanem. On the decision boundaries of deep neural networks: A tropical geometry perspective. arXiv preprint arXiv:2002.08 088888 2020.
Maksym Andriushchenko and Nicolas Flammarion. Understanding and improving fast adversarial training. NeurlPS, 2020.
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give false sense security: Circumventing defenses to adversarial examples. arXiv preprint wrXiv:/802.00420 2018a.
Anish Athalye. Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In International Conference on Machine Learning, pp. 284-293,20 2018b.
Nicholas Carlini and David Wagner. Towards evaluating the robustness neural networks. IEEE Symposium on S&P, 2017.
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt, Percy Liang, and John C Duchi. Unlabeled data improves adversarial robustness. arXiv preprint arXiv: 13736, 2019.
Chen, Liu, S. Chang, Y. Cheng, L. Amini, and Z. Wang. Adversarial robustness: From self-supervised pretraining to fine-tuning. In CVPR, 2020.
Zhangyu Chen, Dong Liu, Xiaofei Wu, and Xiaochun Xu. Research distributed renewahle energy transaction decision makion based on multi-agent bilevel cooperative reinforcement learning. 2019.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with ensemble of diverse parameter- free attacks. International Conference on Machine Learning, pp. 2206 2216. PMLR, 2020.
Stephan Dempe. Foundations of bilevel programming. Springer Science & Business Media, 2002.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009, CVPR 2009. IEEE Conference on, pp. 248-255. IEEE, 2009.
Yao Deng, Xi Zheng, Tianyi Zhang, Chen Chen, Guannan Lou, and Miryung Kim. An analysis of adversarial attacks and defenses autonomous driving models. In 2020 IEEE International Conference on Pervasive Computing and Communications (PerCom). pp. 1-10. IEEE, 2020.
Logan Engstrom, Andrew Ilyas, and Anish Athalye. Evaluating and understanding the robustness of adversarial logit pairing. arXiv preprint 18X 10272, 2018
Samuel G Finlayson, John D Bowers, Joichi Ito, Jonathan L Zittrain, Andrew Beam, and Isaac Kohane. Adversarial attacks on medical machine leaming. Science, 363 2019.
Saced Ghadimi and Mengdi Wang. Approximation methods for bilevel programming. arXiv preprint: (ooprint:1802.000 1802.02246. 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 14Xiv:1412.6572 2014.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application to bi-level optimization. arXiv preprint arXiv: 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference on computer vision, pp. 630-645 Springer. 2016b.
Mingyi Hong. Hoi-To Wai, Zhaoran Wang, and Zhuoran Yang. A two wwo-timescale framework for bilevel optimization: Complexity analysis and application to actor-critic. arXiv preprint arXiv:000..05770, 2020.
W Ronny Huang, Jonas Geiping, Liam Fowl, Gavin Taylor, and Tom Goldstein. Mctapoison: Practical purrral-purpose clcan-label data poisoning. arXiv preprint arXiv:2004.0022 2020.
Kaiyi Ji, Junjie Yang, and Yinghin Liang. Bilevel optimization: Nonasymptotic analysis and faster algorithms. arXiv preprint arXiv:2010.07962, 2020.
10

---

Under review as a conference paper at ICLR 2022
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
K Naveen Kumar, Vishnu, Reshmi Mitra, and Krishna Mohan. Black-hox adversarial attacks in vehicle technology. 2020 IEEE Applied Imagery Pattern Recognition Workshop (AIPR), pp. 1-7. IEEE, 2020.
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio, Adversarial machine learning at scale. 2017 ICLR, arXiv preprint arXiv: 16101366,. 2017. URL
org/ www.//11....... 01236
Bai Li, Shiqi Wang, Suman Jana, and Lawrence Carin. Towards understanding fast adversarial training. arXiv preprint arXiv:2006.03000 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference Learning Representations, 2018.
Faisal Mahmood, Daniel Borders, Richard Chen, Gregory McKay, Kevan Salimiam, Alexander Baras, and Nicholas Durr. Deep adversarial training for multi-organ nuclei segmentation histopathology images. IEEE transactions on medical imaging, 39(1 12:27---3267 2019.
Takeru Miyato, Andrew M Dai, and Ian Goodfellow. Adversarial training methods for semi-supervised text classification, arXiv preprint arXiv: 1605.07725, 2016.
Seyed-Mohsen Moosavi-Dezfooe Albussein Fawzi, Jonathan Uesato, and Pascal Frossard. Robustness via curvature regularization, and vice versa. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 0078-9086, 2019.
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. The limitations deep learning in adversarial settings. Security and Privacy (FuroS&P), 2016 IEEE European Symposium on, pp. 372-387. IEEE, 2016.
Qi Qian, Shenghuo Zhu, Jiasheng Tang, Rong Jin, Baigui Sun, and Hao Li. Robust optimization over multiple domains. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 4739-474555 4746, 2019.
Aravind Rajeswaran, Chelsea Finn, Sham Kakade, and Sergey Levine. Meta-learning with implicit gradients. 2019.
arXiv preprint arXiv: /
Prajit Ramachandran, Barret Zoph, and Quoe V Le. Searching for activation functions. arXiv preprint 17X1v:1710.05941, 2017.
Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learning. In International Conference on Machine Learning, pp. 8093-8104. PMIRR, 2020.
Hadi Salman, Greg Yang, Jemry Li, Pengehuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprint arXiv: 9906044844 2019.
Ali Shafahi, Mahyar Najibi, Mohammad Amin Ghiasi, Zheng Xu, John Dickerson, Christoph Studer, Larry Davis, Gavin Taylor, and Tom Goldstein. Adversarial training for free! In Advances in Neural Information Processing Systems, pp. 3353-33 33643364,220 2019.
Christian Szegedy, Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
Simen Thys, Wiebe Van Ranst, and Toon Goedemé. Fooling automated surveillance cameras: adversarial patches to attack person detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 0-0, 2019.
Luis Vicente, Gilles Savard, and Joaquim Júdice. Descent approaches for quadratic bilevel programming. Journal of Optimization Theory and Applications, 81(2):379-333 1994.
Douglas J White and G Anandalingam. A penalty function approach for solving bi-level linear programs. Journal of Globol Optimization, 3(4):397 419,, 1993.
Fric Wong, Leslie Rice, and J. Zico Kolter. Fast is better than free: Revisiting adversarial training. In International Conference on Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2022
Cihang Xie, Yuxin Wu, Laurens der Maaten, Alan L Yuille, and Kaiming He. Feature denoising for improving adversarial robustness. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 501-509, 2019.
Kaidi Sijia Liu, Zhao, Pin-Yu Yu Chen, Huan Zhang. Quanfu Fan, Deniz Erdogmus, Yanzhi Wang. and Xue Lin. Structured adversarial attack: Towards general implementation better interpretability. In ICLR, 2019.
Kaidi Xu, Gaoyuan Zhang, Liu, Quanfu Fan, Mengshu Sun, Hongge Chen, Pin- Chen, Yanzhi Wang, and
Xue Lin. Adversarial T-Shirt! evading person detectors in physical world. In ECCV, 2020.
Sergey Zagoruyko Nikos Komodakis, Wide residual networks. arXiv preprini urXiv:1605.07146, 2016.
Dinghuai Zhang, Tianyuan Zhang. Yiping Lu, Zhanxing Zhu, and Bin Dong. You only propagate Accelerating adversarial training via maximal principle. arXiv preprint vrXiv1195.00077 2019a.
Haichao Zhang and Jianyu Wang. Towards adversarially robust object detection. In Proceedings the IEEE/CVF International Conference on Computer Vision, pp- 421-430, 2019.
Hongyang Zhang. Yaodong Yu, Jiantao Jiao, Eric Xing. Laurent Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. JCML, 2019b.
Chen Zhu, Yu Cheng, Zhe Gan, Siqi Sun, Tom Goldstein, and Jingjing Liu. Freelb: Enhanced adversarial training for natural language understanding. arXiv preprint arXiv: 2019.
12

---

Under review as a conference paper at ICLR 2022
A
PROOF OF THEOREM
Proof: Upon defining g(0, 6) = (8 - 2)
Vozzlack (0,8) + (A/2) 212. we repeat 7 as
minimize Ø subject to
(0) arg min g(0,)),
(12)
Bash
where we have used the expression of linear constraints in
dB) shown in (3). To this end, we first build implicit functions by Our goal is to derive the IG d0
leveraging KKT conditions of the lower-level problem of (12). We say 8 (0) and X (0) (Lagrangian
multipliers) satisfy the KKT conditions:
Stationarity:
"5g(0,8' + +B (0) +B) =0,
Complementary slackness:
(0) (0)* - b) =
(13)
Dual feasibility:
(0)
where denotes the elementwise product.
Active constraints and definition of By: Let B, denote the sub-matrix of B and bg the sub-vector of b, which consists of only the active constraints at 8 (0), i.e., those satisfied with the equality B = by (corresponding to nonzero dual variables). The determination of active constraints is done given 0 at each iteration.
With the aid of (Bo, ba). KKT 13 becomes
ag ( 6" (0) (0))
B. (0) 0, and BBo"(() bu 0,
(14)
where the nonzero X (0) only correspond active constraints. We take derivatives w.r.t. i for (14) and thus obtain
dV 89 0 5 (O)) + (0) B =0
d0
(0)
V (esg(0,8~(0)) +
()))())00())) + (0) B, 0,
(15)
d0
dō' (0)T T
and
B =0
(16)
d0
where Vos E R. 0 (8) denotes second-order partial derivatives (recall that [0] and |8| = d).
According to (5). we have
(0)
- (e B.
(17)
d0
Substituting the above into (16). we obtain
Vesg(0, 8 sag (e) -B VoX Bo 8' (0)) -B = =0,
(18)
which yields:
VoA-(0) = (ss BB B. V
BB
(19)
and thus,
(o)* B = -Vagg(0 8* (0) V
'B, B, (0,5(( B
'Bp (20)
Substituting 20 into 17). we obtain the IG
d
Vesg(O, 8 Vssg(0 -
vo\ B, (
d0
-
'B
[ (0 -BB - (0)
(21)
13

---

Under review as a conference paper at ICLR 2022
To further compute (1).
the Hessian matrix V Vaslatk is needed. Recall from the definition of the lower-level objective that the Hessian matrix is given by
(0, 8" (0)) atk XI 0 + AI.
(22)
Here we used the assumption that V Vag O. The rationale behind that is neural networks commonly leads to piece-wise linear decision boundary w.r.t. the inputs (Moosavi-Dezfooll et al. 2019 Alfarra et al. 2020). and thus, its second-orde derivative (Hessian) Vsslatk close zero.
Based on the simplification (22 we have
(0)
(I- [--B, B [BoB Bo)
d0
He
(1/A)V 00 Lak (0,8" (O)
(23)
where we have used the fact that Veag Voglatk-
I -
What is He in (23 Since B =
we can obtain that BoBj = I and Bj Bo is sparse diagonal
matrix with diagonal entries being 0 or Thus, Hc can be first simplified to
He = I B Bo-
(24)
Clearly, Hc is also diagonal matrix with either 0 or diagonal entries. The 1-valued diagonal entry of He corresponds to the inactive constraints in Bð < b, i.e., those satisfied with strict inequalities { S e, 0 < 8 < 1}. This can be expressed as
He = [ P115 Son c1....: 1pssss
(25)
where 1p. {0, }} denotes the indicator function over the constraint {p: S 8 < 9: and returns if the constraint is satisfied, o7 denotes the ith entry of (0), max -e, - } and
= min(f, - };}. and e, E Rd denotes the basis vector with the ith entry being 1 and others being Os.
Based on the definition of g: The proof is complete.
23 and 25
we can eventually achieve the desired IG formula 10
14

---

Under review as a conference paper at ICLR 2022
B DISCUSSION ON CASE lack lir
We provide an explanation on the argument "Even we set las = - lu. problem ( does not reduce
problem due the presence lower-level constraint" from the following two points.
In the absence of the constraint C, if set lask - then Problem will reduce to Problem[]]
This is known BLO result (e.g. Ghadimi & Wang (2018) and can be readily proven using the stationary condition. To be specific, based on the stationary condition of uncon- strained lower-level optimization,
have aa 8*) O. Since Lat - -ur have V 8*) O. As result, the second term in Eq becomes and solving problem becomes identical solving the min-max problem
In the presence of the constraint ô E C, the stationary condition cannot be applied since the stationary point may not a feasible point in the constraint. In other words, & (0, 6*) = 0 does not hold in the case of Lak -lu- As matter of fact, one has to resort KKT conditions instead of the stationary condition for a constrained lower-level problem. Similar proof in Theorem T the implicit gradient (and thus the second term of Eq. cannot be omitted in general. This makes problem different from the problem
C DERIVATION OF IMPLICIT GRADIENT FOR FAST-AT
We can derive Eq, 6 using KKT condition similar to Theorem | Specifically, let
>
g(0,8) 6) (sign( Biign(Vo=zlaae (Vo=aaatt(0, u)), z) 2 2|2
(26)
we have
Vosg 0.
(27)
Following 21
we can further obtain (6) based on (27
D DETAILED EXPERIMENT SETTINGS
D.1 TRAINING SET-UP
For CIFAR-10, we summarize the training setup for each method. 1) FAST-AT: We use FGSM with attack step size of 1.25c generate perturbations: 2) PGD-2-AT: 2-step PGD attacks with attack step size of 0.5c is implemented; 3) FAST-AT-GA: The gradient alignment regularization parameter is set the recommended value for each e; 4) FAST-BAT: We select À from 255/5000 to 255/20 /550 for different e. At the same time, we adjust 02 accordingly, so that the coefficient of the second term in 11 namely 02/ always equals 0.1an.
For ImageNet, we set to 2/255, and we strictly follow the training setting adopted by Wong et al. (2020). In FAST-BAT, we fix À 255/3000 /3000 and adopt the same a2 selection strategy CIFAR-IO
Parameter for FAST-AT-GA Regarding FAST-AT-GA with different model types, we adopt the same regularization parameter recommended in its official repe intended for PreActResNet-I1 (namely 0.2 for 8/255 and 2.0 for 16/255).
We random initialization to generate perturbations for PGD, while the paper of FAST-AT-GA (An driushchenko Flammarion 2020), 2-step PGD initialized zero point, which helieve will underestimate the effect of PGD-2-AT
httpAAAAAAA..aaee////t.otottaaaa ing fast blob/master/e
15

---

Under review as a conference paper at ICLR 2022
E
ADDITIONAL EXPERIMENTAL RESULTS
FAST-AT
FAST-AT-GA
FAST-BAT
232
2.00
2.00
300
2.70
240
3.50. 125
2.5 25
9..00 3.25
2.50 ty
-3.00,15 1.25
-asplagtinl 25
Figure A1: Visualization of adversarial loss landscapes of FAST-AT, FAST-AT-GA and FAST-BAT trained using the ResNet-18 model the CIFAR-10 10 dataset. The losses are calculated w.r.t. the same image example ID #001456, and the landscape is obtained by tracking the loss changes w.n.t. input variations following Enggstrom et al. 2018). That is, the loss landscape is generated by = loss(! + x r1 + 12), where / denotes an image. and the z-axis and the y-axis correspond to linear coefficients associated with the sign-based attack direction Sign(V,lon losss(()) & and random direction r2 Rademacher(0.5). respectively.
Sensitivity to regularization parameter À In Table|A]] we show the sensitivity of FAST- BAT to the regularization parameter X. All the parameters remain the same as default setting, except that for different X. We always adjust 02 so that 02/ À 0.1 holds. Note 1/A also serves as the attack step in (8). As À decreases, the improvement on robust accuracy is evidently strengthened, and there is obvious trade-off between robust accuracy (SA) and standard ac- curacy (RA). At certain level of X, namely when À < 255/2000, RA starts to converge and stop surging.
Table A1: Performance of FAST-BA BAT with different parameter X. We train and evaluate with the same attack
budget = 16/255 on CIFAR-10 10 to show the influence
brought by A.
CIFAR- 10, PreActResNet-Ie 18, e 16/255
1/A (/255)
500
1000
1500
2000
2500
SA (%)
83,20
75.06
69.31
67.81
67.59
RA-PGD (%)
19.02
21.42
23.34
26.07
26.12
Sensitivity to different a2 choices We con- sider the case of robust training with the large choice (16/255), /255). As we can see from Table|A2 if Q2 is set too small (a2 0.008a1), then both SA and RA will drop significantly. Here 0₁ is set the eyclic learning rate and thus not constant parameter. However, in the 02 inter- val [0.0125ar 0.025ai). we observed tradeoff between standard accuracy (SA) and robust ac- curacy (RA): That is, the improvement in RA corresponds to loss in SA. In our experiments, we choose a2 when the tradeoff yields the best RA without suffering significant drop of SA (which still outperforms the baseline approaches).
Table A2: Performance of FAST FAST-BATwin BAT different or choices on CIFAR-IO. Models are trained and evaluated with the same attack budget (e = 16/255). Here ai is set as the cyclic learning rate and thus, is not constant parameter. 02 is always set proportionate to ti for simplicity.
aa (CIFAR-10.
PreActResNed118
0.025m;
0.0167e1
0.0125o
0.0 0.0080
16/255)
(S) (%)
75.06
69.31
67.81 26.07
57.92 20.53
RA-PGD (%)
21.42
23.34
Sensitivity of linearization schemes Fast- BAT needs good linearization point in (7) In experiments, we adopt the perturbation gener- ated by 1-step PGD without sign as our default linearization scheme. In Table A3 we show the performance of the other possible lineariza- tion options. We can find 1-step PGD without sign achieves best robust accuracy among all the choices. This is not spurring since this lineariza- tion point choice is consistent with the first- Taylor expansion that used along the direc- tion of input gradient without sign involved. By contrast, FAST-Br FAST-BAT linearized with uniformly random noise suffers from catastrophic overfitting and reaches a rather low standard accuracy (SA).
Table A3: Performance of FAST-BAT with different linearization schemes. Besides 1-step PGD without sign (PGD w/o Sign), we further generate linearization point with the following methods: uniformly random noise [-e, e) (Uniformly Random); uniformly random cor- ner c- (Random Corner); and perturbation from 1-step PGD attack with 0.5c as attack step (PGD).
CIFAR-10, PreActResNet-183.
16/255
Linearization Method
PGD w/o Sign
Unifornly Random
Random Comer
PGD
SA (%)
69.31
43.42
62. 19
75.30
RA-PGD (%)
23.34
21.25
16.5
19.42
FAST-BAN with other linearizations also yields worse SA-RA trade-off than our proposal.
16

---

Under review as a conference paper at ICLR 2022
Table A4:
Performance of Hessian-free and Hessian-aware with the same attack budgets c = 8/255 and = 16/255 to show the influence brought by Hessian matrix.
CIFAR-10. We train and evaluate
RA-PGD (%) (c = 8/255)
RA-PGD (%)
RA-AA (%)
RA-AA (%)
SA (%)
SA (%)
Time (s/epoch)
Method
( = 16/255)
(e = 8/ 8/255)
16/255)
(c 8/255)
(< 16/255)
Hessian-free
48.67
26.07
44.86
18.18
79.47
67.81
135
Fast-BAT
Hessian-awe aware
Fast-BAT
48.52
26.12
44.81
18.31
79.54
67.93
179
Table AS: Performance of Aaand FAST- BATwith different activation functions on CIFAR- IO. ReLU, Swish and Softplus are taken into consideration. For FAST- BAT, we compare the Hessian free and Hessian-awarc version to verify the influence of Hessian matrix. The results are averaged over 3 independent trials.
SA (%)
RA-PGD (%)
SA (%)
RA-PGD (%)
Time (s/epoch)
Setting
8/255)
(c 8/255)
(c 16/255)
(c 16/255)
-ast-AT-ReI.U
81.88
45.44
46.13
21.75
42
Fast-BAT-ReLU
79.54
48.52
67.93
26.12
179
(Hlessiun-aware)
BAU--BATReLLU
79.47
48.67
67.81
26.07
135
(Hessian-freo)
Fast-AT-Softplus
81.29
47.26
45.39
22.40
42
Fast-BAT-Sofillus
(Hessiun-uwaree)
79.59
49.74
68.63
25.54
178
Sootpls
(Hessian-free)
79.48
49.67
68.57
25.59
137
Fast-AT -Tss-h Bast-BAT-Swish
75.61
44.43
52.03
23.08
49
73.93
45.97
62.49
23.99
196
(Hessiann-aaar Fast- BAT--wish
(Hessian-free)
73.89
45,90
62.59
23.81
141
Influence of Hessian matrix In Theorem [ the Hessian-free assumption, i.e. Va = 0, was made simplify the computation of IG term (implicit gradient). To examine how the Hessian matrix Vaseatk affects the performance of Fast-BAT, we conduct experiments to compare the Hessian- free FAST-BATwith the Hessian-aware version. In Hessian-aware FAST-BAT, the implicit gradient is calculated based on (2I). In Table A4] the results do not indicate much difference when Hessian is used. However, the extra calculation brought by Hessian heavily slows down FAST- -ATas around 30% more time is needed. Therefore, the Hessian-free assumption is reasonable and also necessary terms of the efficiency of the algorithm.
Ablation study smooth activation functions The Hessian ffrse assumption is based the fact that the commonly used ReLU activation function is piece-wing wiiee-wise linear w.E.t. input. We further conduct experiments verify the feasibility of such assumption on models with Ron- activation functions. We choose two commonly used activation functions, and Softplus, as alternatives for non-smooth ReLU function. We compare the results both calculating Hessian as well as the Hessian- free version to see if the Hessian -reee assumption still holds for the non-ReLU neural network. The results are shown Table A5] As we can see, the use of Hessian does not affect performance much. A similar phenomenon can be observed across different and different model activation functions (ReLU, Softplus, and Swish). However, the introduction of Hessian leads to an increase in time consumption by more than 30%. Therefore, we can draw the conclusion that the Hessian-free free assumption is reasonable across different activation function choices.
arrish(Ramachadrran et al.) (017))
17


Reviews:
[{"review_id": "qTX7OkYLwp", "reviewer": "Reviewer_6Qs9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: the work outperforms Fast-AT-GA at $\\epsilon=16/255$, obtaining better standard accuracy in less time while matching robust accuracy (standard accuracy ~68% instead of ~59%).\n\nWeaknesses:\nBaselines and experimental evaluation: \n- When comparing performance on a system that has evaluation metrics of both accuracy and training speed, the evaluation must take both into account. Currently it does not: all we see is a table with times and accuracies. One standard way of comparing training speed and accuracy is to measure either the \"maximum accuracy in a fixed amount of time\" or \"minimum time to attain a fixed accuracy\" while varying the metric of interest (time or accuracy respectively). Using this type of evaluation, a reader can see the speed/adv. accuracy frontier necessary to compare across algorithms. Currently the evaluation is not sufficiently detailed to compare across algorithms.\n- As a suggestion, one natural way of trading off time for accuracy is to treat the number of epochs as a free parameter; an illuminating here would be adv. performance vs training time as the number of epochs changes for each method.\n- The performance analysis is currently not informative; it uses a fixed training configuration for each training method (according to the Table 1 description, all the algorithms use early stopping yet according to Figure 1 this heavily disadvantages Fast-AT compared to no early stopping). One must choose the pareto (trading off speed and accuracies) optimal configurations for each training algorithm. The analysis must ablate across different training configurations to be fair.\n- The time does not have a standard deviation.\n- How is it that $\\epsilon=8/255$ and $\\epsilon=16/255$ trained models always have the same runtime, as reported in Table 1? Does early stopping always exit the same epoch for both?\n\nCharacterization of previous work: \n- What is the difference between problem (i) and problem (ii) on page 2? Robust performance is always properly evaluated against the strongest possible adversary.\n- The authors claim to solve an issue with Fast-AT stemming from its tendency towards catastrophic overfitting. The authors should give more background on when Fast-AT fails to catastrophic overfitting; how often does it happen? How does the $\\epsilon$ impact Fast-AT's convergence?", "summary_of_the_paper": "This work focuses on the problem of speeding up adversarial training in the $\\ell_\\inf$ threat model. The work first describes two previous works designed to speed up adversarial training:\n- Fast-AT: carefully perform single-step PGD (otherwise known as FGSM) to train $\\ell_\\inf$ robust models - from Wong, Rice and Kolter 2020\n- Fast-AT-GA: single-step PGD + a gradient alignment loss function - from Andriushchenko and Flammarion 2020.\n\nThe work then lists a problem with Fast-AT:\n- Fast-AT experiences catastrophic overfitting (i.e. provides no robustness on held-out data) for $\\epsilon = 16/255$ (Note: Fast-AT-GA does not have this catastrophic overfitting issue)\n\nFinally, the authors present a new method based on bi-level optimization to perform fast $\\ell_\\inf$-robust learning. They evaluate it and compare with Fast-AT-GA using a 20 epoch schedule, finding that for $\\epsilon = 16/255$, the technique can provide the same robustness except with standard accuracy ~68% instead of ~59%. ", "summary_of_the_review": "While the work shows a promising approach (as measured by outperforming Fast-AT-GA at $\\epsilon=16/255$ in terms of standard accuracy while beating it in speed and in robust accuracy), the evaluation is lacking. In particular, the evaluation does not give a speed/accuracy tradeoff for each training routine, and does not properly hyperparameter search for each compared algorithm in the comparison. Finally, the work has some minor issues in its characterization of previous work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "a3laIqJRpdr", "reviewer": "Reviewer_N6su", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In general, I like this perspective due to the realizing of the implicit gradient term since actually the adversarial perturbation depends on the network weights, and this is also related to some versions of GANs’ training. However, in the current version of the paper, there exists several key points that requires careful justification to make it as a much stronger piece of work. I list them in the below. If these questions could be handled properly, I will increase my score. \n\n1.\tIn the Remark 1, it seems an very important conclusion the authors want to claim on the role of the second term associated with alpha2. Then what is evidence for the claim that “the choice of alpha2 could affect the tradeoff between accuracy and robustness…alpha2-associated term plays a positive role in boosting robustness, especially for training with large epsilon”? \n2.\tWhy does FAST-BAT produce better gradient alignment? Is it just an empirical observation or is there any good theoretical justification?\n3.\tIs there any connection between FAST-BAT and standard PGD adversarial training? \n\nOther questions: \nAbout the Hessian-free assumption. What about the non-ReLU activation function for which the function is not piece-wise linear wrt to input? \n", "summary_of_the_paper": "This paper aims to interpret the fast adversarial training methods from the perspective bi-level optimization. Though the discovery is straightforward, it is worthy of letting the community know this important connection. And then the authors proposed a new linearization of the lower-level optimization problem and introduced a new FAST-BAT approach for improving both accuracy and robustness. Various experiments were conducted to verify the effectiveness of the proposed method. ", "summary_of_the_review": "Good perspective for interpreting fast adversarial training, but in the current version, there exists several key points that requires careful justification to make it as a much stronger piece of work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DT9fJ9Ab8b5", "reviewer": "Reviewer_c58a", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Rewriting (robust) AT as a bi-level optimization problem is a nice formalization that allows the use of implicit differentiation for training robust models. This contribution seems however straightforward and the deployed techniques for optimizing the problem (linearized proximal form, differentiable projection) are standard in the literature.\nThe other advantage of rewriting the problem in this way is in making a distinction between training loss $\\ell_{tr}$ and attack loss $\\ell_{atk}$, but this does not seem to be explored in the experiments.\n\nThe paper presents some inaccuracies when reporting the related work and in the derivations:\n\nContrary to what stated in the paper, Adversarial Training was proposed before [Madry 2018] in the seminal work of [1]. In [Madry 2018] adversarial training was formulated as a Robust Optimization problem. The attribution should be rectified.\n\nTo write Problems (5) and (7) it is never explained how the term $\\frac{\\lambda}{2}$ squared norm 2 of $\\delta - z$ appears. It does not come directly from the linearization otherwise this term would be multiplied by the second order derivate of $\\ell_{atk}$ and there wouldn't be any $\\lambda$ hyper-parameter. Instead it seems that the $\\lambda$ proximal operator is applied, but this is never mentioned.\nThe assumptions on the loss functions needed in order to linearize the BLO problem are not reported.\n\nIn order to compute the implicit gradient of FAST-AT, $\\mathcal{P}_{\\mathcal{C}}$ does not need to be differentiable as the derivative of the sign function is 0 null on the dimensions that need an update. The statement \"the projection function is not smooth, and thus the use of chain rule is not legitimate\" is somehow incorrect, as this projection is still differentiable as it is shown later in page 6, it just gives a piece-wise derivative depending on the box constraints.\n\nIn Theorem 1, it is not explained why the so-called Hessian-free assumption is needed. Moreover, its naming seems inaccurate as not all the components of the Hessian should be null (in particular those w.r.t $\\theta \\delta$).\n\nThe following notions essential for understanding the paper are not defined: robustness catastrophic overfitting, random corner linearization, gradient alignment.\n\nThe methods used as baselines in the experiments are not sufficiently described, namely FAST-AT-GA and PGD-2-AT. Also AutoAttacks should be described and the reason why this type of attack is chosen to measure robust accuracy should be provided. In the tables, the standard deviations should be used to determine which score differences are significant. At the moment, it seems that the result marked in bold is the one with the best average score, but a significance test should be used instead. \nWhy does PGD-2-AT generally achieve better results than FAST-AT and FAST-AT-GA and comparable with FAST-BAT? \n\n(Minor) The following reference is defined twice: Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018b.\n\n[1] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian J. Goodfellow, and Rob Fergus. Intriguing properties of neural networks, ICLR 2014", "summary_of_the_paper": "The paper proposes a bi-level optimization problem for training models robust to norm constrained adversarial attacks that can be optimized via argmin/implicit differentiation by linearizing the inner problem (the search for the worst perturbation). The new technique is then compared empirically to other existing approximations of the robust training problem (referred to in the paper as Adversarial Training) and shown to provide improved or comparable results in terms of standard and robust accuracy, for different attacks.", "summary_of_the_review": "I'd tend to reject the paper because of the highlighted inaccuracies and unclear points, and because the contributions seem straightforward applications of BLO theory to adversarial training. Additionally, the new linearization does not seem to significantly improve state-of-the-art results.\n\n## UPDATE\nMy final evaluation is based on the current version of the paper, as the authors had the chance to update it.\nI increased my score to 5, as the inaccuracies have been corrected, namely:\n- the attribution of adversarial training has been rectified\n- the additional $\\lambda$ norm_2 term in the linearized inner problems has been explained\n- the phrasing for the Hessian-free assumption and projection's derivative has been corrected\n \nI still tend to reject the paper for the following reasons:\n- definition of gradient alignment and autoattacks is not provided\n- justification for using autoattacks is not provided. \"everybody is doing it\" is not a sufficient justification per se\n- comparison wrt baselines is based on mean values, hence the reader cannot judge the significance of the improvements. Doubts about the significance of the empirical results has been raised by other reviewers as well.\n\nFinally, I still have some doubts about the contributions of the paper to the BLO literature. In the rebuttal the authors claim \"(1) we show that the choice of lower-level linearization (gradient sign-based vs. non-sign case) could be a key to simplifying BLO with lower-level constraints, and (2) we derive the closed-form of the implicit gradient of lower-level constrained BLO assisted by lower-level linearization.\"\nHoewever the two linearization schemes are not novel, neither the derivative of the projection onto a convex set.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6pEA1oN1eeM", "reviewer": "Reviewer_TZX8", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Relevance: the paper focuses on the important problem of designing computationally attractive algorithms for adversarial training -- this is an important problem that is relevant to ICLR.\n\nResults: The main strength of the paper is the empirical study. Given that within the same computation budget as the baselines, the proposed method has lower variance and resolves catastrophic overfitting in several settings, I found the results important. The results are only averaged over 5 random experiments, therefore, given the complexity and the size of the task, I’m not sure how reliable the estimates of mean/variance are. I think the empirical results can be much more compelling if the authors include more experiments.\n\nPresentation: Although the paper is well-written for the most part, there is much room for improvement in sections 3 and 4. In particular, some claims are not well-justified, there are some issues with the notation and the presentation lacks mathematical rigor. Here are some examples:\n\n            - in page 3, the authors state that “FAST-AT-GA yields improved robustness but has a poor accuracy-robustness tradeoff (e.g. Table 1)“. I do not see how FAST-AT-GA has a poor accuracy-robustness tradeoff in Table 1. Can you elaborate?\n\n            - the description of set C = {delta | || delta ||_infty < epsilon,  delta in [0, 1]} is very confusing. What does delta in [0, 1] mean? attacks are always point-wise positive? How is it not vacuous since epsilon < 1?\n\n            - in page 4, the authors say “Even if we set ell_atk = - ell_tr, problem 2 does not reduce to 1 due to the presence of lower-level constraint”. Regardless of whether this claim is true or not, the justification is far from satisfactory. In order to argue two optimization “problem” are equivalent, or if one reduces to another, one needs to prove/disprove that solutions to one constitute solutions to the other. The fact that gradients are different — as argued in the paper — does not a-priori inform us of anything useful about the equivalence of the two. In particular, when ell_atk = - ell_tr, then delta* in (2) is very well a maximizer of the inner attack problem in (1). Again, whether two optimization problems are equivalent has nothing to do with certain optimization procedures (such as PGD being considered here) generating different trajectories.\n\n            - the bi-level interpretation of Fast-At is trivial — this is how gradient updates are motivated in the literature of first-order optimization.\n\n            - in page 5, the derivation of the implicit gradient in (6) seems reasonable but lacks mathematical rigor. I suggest authors include careful proof here.\n\n            - The Hessian-free assumption in Theorem 1 essentially means that the attack loss ell_atk is linear. I do believe that this is not true for most interesting cases, and I do not buy the argument “the rationale behind the Hessian-free assumption is that neural networks commonly lead to a piece-wise linear decision boundary”. Are you suggesting that the loss landscape in deep learning is almost linear?\n\n            - in page 6, remark 1, the authors state that “Clearly, if alpha_2 = 0, then it reduces to the standard Fast-AT”. How is this true? here the updates will be based on the gradient of the loss whereas in standard Fast-At the updates are based on the sign of the gradient.\n", "summary_of_the_paper": "The paper studies adversarial training as a bi-level optimization problem. The authors show that Fast Adversarial Training can be viewed as a bi-level optimization problem where the lower-level problem is a linearization of the loss in the direction of the sign of the gradient. Motivated by this observation, the authors propose Fast Bi-level Adversarial Training, where the lower-level optimization linearizes the loss in the direction of the gradient (as opposed to the sign of the gradient). The authors then show analytically how to obtain the gradient of the upper-level problem under the assumption that the loss Hessian is equal to zero. This gradient is then used in an iterative manner similar to standard adversarial training. The proposed method is evaluated on CIFAR10 and ImageNet against multiple baselines including Fast-AT, Fast-AT-GA, and PGD-2. The empirical results show that compared to the baselines, within the same order of computational cost, the proposed method enjoys improved stability and mitigates the catastrophic overfitting present in other baselines.", "summary_of_the_review": "To summarize:\nStrengths:\n          - the paper studies an important and relevant problem.\n          - the experiments are well done. \n          - the proposed adversarial training approach has nice theoretical motivations.\n          - the paper is well-written for the most part.\n\nWeakness:\n          - several ideas and claims are handwavy and lack mathematical rigor \n          - the assumption behind the main theoretical result is too stringent\n          - statistical significance --> only 5 random experiments", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper investigates fast adversarial training methods as a bilevel optimization problem. The proposed algorithm compares well with the existing techniques in overall runtime (obtaining better clean-test accuracy, which is not the goal, and) matching the robust accuracy of existing adversarial training methods. The proposed framework, however, is more general and flexible and is theoretically grounded. The problem studied here is exciting and the approach the authors take is interesting. 

The current version, unfortunately, has some serious shortcomings. The empirical comparisons are a bit lacking — in general, the wall clock time is not a very good measure, it depends heavily on the implementation and various optimizations therein. A more suitable comparison would be in terms of floating-point operations, or in terms of iteration complexity. 

The paper reports other interesting findings such as how the proposed method avoids robust overfitting. However, there is little theoretical evidence or insight for how the proposed method avoids it. 

The writing can be improved with more emphasis on the novelty and significance of the contributions — some of the statements regarding improvements over prior work are somewhat misleading given the incremental gains (e.g., see Table 1). I believe the comments from the reviewers have already helped improve the quality of the paper. I encourage the authors to further incorporate the feedback and work towards a stronger submission.
Decision: Reject