Year: 2021

Abstract:
Adversarial training (AT) has become a widely recognized defense mechanism to 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 to 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 signbased 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 FASTAT, 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.

heading: 1 INTRODUCTION
text: Given the fact that machine learning (ML) models can be easily fooled by tiny adversarial perturbations (also known as adversarial attacks) on the input (Goodfellow et al., 2014; 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; Athalye et al., 2018a) are built on the adversarial training (AT) recipe, first developed in (Szegedy et al., 2014) 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 classification (Goodfellow et al., 2014; Madry et al., 2018; Kurakin et al., 2017), object detection (Zhang & Wang, 2019), natural language processing (Miyato et al., 2016; 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
(required by an iterative attack generator) are needed at 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. (2019) used 128 GPUs to make AT practical on ImageNet. Thereby, how to speed up AT without losing accuracy and robustness is now a grand challenge for adversarial defense.
Very recently, some work attempted to develop computationally-efficient alternatives of AT, which we call ‘fast’ versions of AT (Shafahi et al., 2019; Zhang et al., 2019a; Wong et 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-GA (Andriushchenko & Flammarion, 2020), are the two state-of-the-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., 2020) replaces an iterative attack generator used in AT with a heuristics-based 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.e., large variance in performance (Li et al., 2020), and (ii) robustness catastrophic overfitting, i.e., a large drop of robustness when training with strong adversaries (Andriushchenko & Flammarion, 2020). To alleviate these problems, Andriushchenko & Flammarion (2020) proposed FAST-AT-GA by penalizing FAST-AT using an explicit robust regularization given by GA. However, we will show that FAST-AT-GA encounters a new problem (iii): FAST-AT-GA hampers standard accuracy, making a poor accuracy-robustness tradeoff at large attack budget ( = 16/255), i.e. the improvement on RA is at cost of a sharp drop on SA. Given the limitations (i)-(iii), we ask:
How to design a theoretically-grounded ‘fast’ version of AT with improved stability, mitigated catastrophic overfitting, and enhanced accuracy-robustness tradeoff ?
To address above question, paper we revisit and advance AT through the lens of bi-level optimization (BLO) (Dempe, 2002), 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 a 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, we propose a novel, theoretically-grounded ‘fast’ AT framework, fast bi-level AT (FAST-BAT). Practically, Table 1 highlights some achieved improvements over FAST-AT and FAST-AT-GA: When a stronger train-time attack (i.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 a significant SA loss (over 21%) at = 16/255. By contrast, FAST-BAT yields a more graceful SA-RA tradeoff: 9% improvement of SA without loss of RA. Different from FAST-AT-GA, FAST-BAT achieves above improvements in stability, RA and SA without resorting to any extra robust regularization and thus takes less computation cost.
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-grounded interpretation of FAST-AT.
 We propose a new systematic and effective fast BLO-oriented AT framework, termed FAST-BAT, with rigorously-established theory and algorithm.
® We conduct extensive experiments on FAST-BAT, showing its improved stability, mitigated catastrophic overfitting, and enhanced accuracy-robustness tradeoff; see illustrations in Table 1.

heading: 2 RELATED WORK
text: 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 `p-norm ball constrained attack (p ∈ {0, 1, 2,∞}). 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., 2020; Kumar et al., 2020), surveillance (Thys et al., 2019; Xu et al., 2020), and healthcare (Finlayson et al., 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 et 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., 2018a). Extended from AT, TRADES (Zhang et al., 2019b) sought the optimal balance between robustness and generalization ability. Further, AT-type defense has been generalized to the semi-/self-supervised settings (Carmon et al., 2019; Chen et al., 2020) and integrated 1 with certified defense techniques such as 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 an open question. Some recent works attempted to impose algorithmic simplifications to AT, leading to fast but approximate AT algorithms, such as ‘free’ AT (Shafahi et al., 2019), you only propagate once (YOPO) (Zhang et al., 2019a), FASTAT (Wong et al., 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 is far from satisfactory. For example, FAST-AT has poor training stability (Li 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 a poor accuracy-robustness tradeoff (e.g., Table 1). 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 FAST-BAT can lead to stable robust learning without suffering catastrophic overfitting and graceful tradeoff between accuracy and robustness.
Bi-level optimization (BLO). BLO is a unified hierarchical learning framework, where the objective 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 et al., 2020; Hong et al., 2020). In practice, some successful applications of BLO to ML have been witnessed in meta-learning (Rajeswaran et al., 2019), data poisoning attack design (Huang et al., 2020), and reinforcement learning (Chen et al., 2019). However, as will be evident later, the existing BLO approach is not directly applied to 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 a rigorous connection between adversarial defense and BLO for the first time.

heading: 3 A BI-LEVEL OPTIMIZATION VIEW ON FAST-AT
text: Preliminaries on FAST-AT. FAST-AT is designed for solving the adversarial training problem (Madry et al., 2018) given below
minimize θ
E(x,y)∈D [
maximize δ∈C `tr(θ,x+ δ, y)
] , (1)
where θ ∈ Rn denotes model parameters, D is the training set consisting of labeled data pairs with feature x and label y, δ ∈ Rd represents adversarial perturbations subject to the perturbation
constraint C, e.g., C = {δ | ‖δ‖∞ ≤ , δ ∈ [0,1]} for -toleration `∞-norm constrained attack (normalized to [0,1]), (x+ δ) is then called adversarial example, and `tr(·) represents a training loss. The standard solver to problem (1) is known as 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 a 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 al., 2020). The algorithm backbone of FAST-AT is summarized below.

heading: FAST-AT algorithm
text: Let θt be the model parameters at iteration t. The (t+ 1)th iteration is given by ¬ (Inner maximization by 1-step PGD): δ ←− PC (δ0 + α · sign (∇δ`tr(θt,x+ δ0, y))), where PC(a) denotes the projection operation that projects the point a onto C, i.e., PC(z) = argminδ∈C ‖δ − z‖22, δ0 is a random uniform initialization within [0,1], α > 0 is a proper learning rate (e.g., 1.25 ), and sign(·) is the element-wise sign operation.  (Outer minimization for model training): This can be conducted by any standard optimizer, e.g., SGD. That is, θt+1 ←− θt − β∇θ`tr(θt,x+ δ, y), where β > 0 is a proper learning rate (e.g., cyclic learning rate), and δ is provided from the inner maximization step.
Roughly speaking, FAST-AT is a 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 sophisticated hyperparameter choices in α, δ0, and β. Despite the efficacy of FAST-AT in some cases, Andriushchenko & Flammarion (2020) demonstrated that it 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 a unified formulation of robust training. BLO (bi-level optimization) is a 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 a robust training paradigm. Specifically, we can cast robustification as an upper-level problem whose optimization relies on a lower-level problem defined for attack generation. Thus, the BLO formulation of (1) is given by
minimize θ E(x,y)∈D[`tr(θ,x+ δ∗(θ;x, y), y)] subject to δ∗(θ;x, y) = argmin
δ∈C `atk(θ, δ;x, y),
(2)
where `atk denotes an attack objective. For notation simplicity, we will use data-omitted expressions of `tr, `atk, and δ∗. The formulation (2) has two key differences from (1):
– First, the lower-level attack objective `atk is customizable, not necessarily to be same as the opposite of the training objective, −`tr. 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 (1). Even if we set `atk = −`tr, problem (2) does not reduce to (1) due to the presence of lower-level constraint δ ∈ C (see rigorous analysis in Appendix B). Specifically, solving the upper-level problem of (2) by gradient descent yields
d`tr(θ, δ ∗(θ))
dθ = ∇θ`tr(θ, δ∗(θ)) +
dδ∗(θ)> dθ︸ ︷︷ ︸ IG ∇δ`tr(θ, δ∗(θ)), (3)
where the superscript > denotes the transpose operation, and ∇θ`tr(θ, δ∗(θ)) denotes the partial derivative with respect to (w.r.t.) the first input argument θ. In (3), dδ ∗(θ)>
dθ ∈ R n×d is referred to
as implicit gradient (IG) because it is defined through an implicit constrained optimization problem minδ∈C `atk. The dependence on IG is a ‘fingerprint’ of BLO (1) in contrast to AT or FAST-AT.
BLO-enabled interpretation of FAST-AT. In what follows, we demonstrate how FAST-AT relates to BLO. Our main finding is summarized below.

heading: Bi-level interpretation of FAST-AT
text: FAST-AT can be interpreted as the lower-level linearized BLO with z = δ0 and λ = 1/α:
minimize θ
E(x,y)∈D[`tr(θ, δ∗(θ))]
subject to δ∗(θ) = argmin δ∈C [(δ − z)>sign(∇δ=z`atk(θ, δ)) + (λ/2)‖δ − z‖22], (4)
where z is the linearization point, ∇δ=z`atk denotes the partial derivative of `atk (w.r.t. δ) evaluated at z, sign(∇δ=z`atk(θ, δ)) is the linearization direction, and λ > 0 is a regularization parameter associated with the quadratic residual of linearization.
Our justification on the above claim is elaborated on below.
– First, the simplified lower-level problem of (4) leads to the closed-form solution δ∗(θ) = argmin
δ∈C (λ/2)‖δ − z+ (1/λ)sign(∇δ=z`atk(θ, δ))‖22
=PC (z− (1/λ)sign(∇δ=z`atk(θ, δ))) , (5)
which is given by the 1-step PGD attack with initialization z and learning rate (1/λ). In the linearization used in (4), a quadratic regularization term (with regularization parameter λ) is introduced to ensure the strong convexity of the inner-level attack objective within the constraint set δ ∈ C. Assisted by that, the lower-level solution is unique and its closed form is given by (5). Note that imposing such a strongly convex regularizer is also commonly used to stabilize the convergence of min-max optimization and BLO (Qian et al., 2019; Hong et al., 2020). If we set z = δ0 and λ = 1/α, then (5) precisely depicts the inner maximization step used in 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 of IG dδ ∗(θ)>
dθ . If we regard PC is differentiable, then based on the closed-form of δ∗(θ) in (5), IG becomes
dδ∗(θ)>
dθ = 0, (6)
where we use two facts: (1) The linearization point z is independent of θ, i.e. z = δ0; And (2) dsign(·) dθ = 0 holds almost everywhere. Please refer to Appendix C for a rigorous proof of (6) using KKT conditions. Clearly, the use of gradient sign method simplifies the IG computation. Substituting (6) into (3), the upper-level optimization of (4) yields θ ←− θ− β∇θ`tr(θ, δ∗(θ)) (with learning rate β), which is precisely same as the outer minimization step used in FAST-AT.
The aforementioned analysis shows that the linearized BLO (4) is equivalent to FAST-AT by setting the linearization point z and the regularization parameter λ as z = δ0 and λ = 1/α.

heading: 4 FAST-BAT: ADVANCING FAST-AT BY BLO
text: 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 (4) can be modified to the form of FAST-BAT
minimize θ
E(x,y)∈D[`tr(θ, δ∗(θ))]
subject to δ∗(θ) = argmin δ∈C [(δ − z)>∇δ=z`atk(θ, δ) + (λ/2)‖δ − z‖22], (7)
where similar to (5), the lower-level problem can be solved analytically as
δ∗(θ) = PC (z− (1/λ)∇δ=z`atk(θ, δ)) . (8)
In contrast to (6), the IG associated with (7) is no longer vacant since the gradient sign operation is not present in (8). To compute IG, the auto-differentiation (which calls the chain rule) can be applied to the closed-form of δ∗(θ). However, this will not give us an accurate and generalizable IG solution since the projection operation PC is not smooth and thus, the use of chain rule does not yield a rigorous derivation. Therefore, the IG challenge arises, which will be addressed in what follows.
IG theory for FAST-BAT. The problem of FAST-BAT (7) falls into a class of very challenging BLO problems, which require constrained lower-level optimization. The unconstrained case is easier to handle since one 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 = {‖δ‖∞ ≤ , δ ∈ [−x,1− x]} ⇐⇒ Bδ ≤ b, with B := [ I −I ] , b := [ min{ 1,1− x} −max{− 1,−x} ] . (9)
By exploiting above linearly constrained problem structure, we show that the IG challenge associated with (7) can be addressed via Karush–Kuhn–Tucker (KKT) conditions. We summarize our main theoretical result below and refer readers to Appendix A for detailed derivation.
Theorem 1 With a Hessian-free assumption, i.e.,∇δδ`atk = 0, the IG (implicit gradient) of (7) is dδ∗(θ)>
dθ = −(1/λ)∇θδ`atk(θ, δ∗)HC , with HC :=
[ 1p1<δ∗1<q1e1 · · · 1p1<δ∗d<qded ] , (10)
where δ∗ is given by (8), and ∇θδ`(θ, δ∗) ∈ Rn×d denotes the second-order partial derivative evaluated at θ and δ∗(θ), respectively. In HC ∈ Rd×d, 1pi<δ∗i<qi ∈ {0, 1} denotes the indicator function over the constraint of {δi | pi < δ∗i < qi}, which returns 1 if the constraint is satisfied, δ∗i denotes the ith entry of δ
∗(θ), pi = max{− ,−xi} and qi = min{ , 1 − xi} characterize the boundary of the linear constraint (9) for the variable δi, and ei ∈ Rd denotes the basis vector with the ith entry being 1 and others being 0s.
In Theorem 1, the rationale behind the Hessian-free assumption is that ReLU-based neural networks commonly lead to a 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) ∇δδ`atk is close to zero. In Appendix E, we will empirically show that the Hessian-free assumption is reasonable for both ReLU and non-ReLU 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 (8). We summarize the FAST-BAT algorithm below.

heading: FAST-BAT algorithm
text: The (t+ 1)th upper-level iteration of FAST-BAT is given below ¬ (Lower-level solution): Obtain δ∗(θt) from (8);  (Upper-level model training): Integrating the IG (10) into (3), call SGD to update
θt+1 = θt − α1∇θ`tr(θt, δ∗(θt))− α2(−1/λ)∇θδ`atk(θt, δ∗(θt))HC∇δ`tr(θt, δ∗(θt)), (11)
where α1, α2 > 0 are learning rates associated with the standard model gradient and the IG-augmented descent direction, respectively.
It is clear from (11) that to train a robust model, FAST-BAT can be dissected into the regular FAST-AT update (i.e., α1-associated term) and the additional update that involves IG, (i.e., α2-associated term). To successfully implement FAST-BAT, we highlight some key hyper-parameter setups different from FAST-AT (Wong et al., 2020) and FAST-AT-GA (Andriushchenko & Flammarion, 2020).
Remark 1 Choice of learning rate for IG-involved descent term: In (11), the choice of α2 could affect the trade-off between accuracy and robustness (see empirical justification in Appendix E). Clearly, if α2 = 0, then the upper-level model parameter updating step reduces to the standard FAST-AT. In Sec. 5.1, we will show that the α2-associated term plays a positive role in alleviating catastrophic robust overfitting. Meanwhile, λ in (7) could also affect the accuracy-robustness tradeoff. For example, if λ→∞, then δ = 0 (no robustness gain). Spurred by above, we choose the following combination of α2 and λ, α2/λ = 0.1α1, which works well in practice; see Table A1.
Remark 2 Choice of linearization point z: To specify (7), we investigate two classes of linearization schemes. The first class is random constant linearization, which includes: “uniformly random
linearization”, i.e., z = δ0 as FAST-AT, and “random corner linearization" under the -radius `∞- ball, i.e., z ∈ {− , }d. The second class is 1-step perturbation warm-up-based linearization, which includes the other two specifications: “1-step PGD" z = PC (δ0 + α · sign (∇δ`tr(θt, δ0))), and “1-step PGD w/o sign" z = PC (δ0 + α∇δ`tr(θt, δ0)). 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 to the best defense performance; see justification in Table A3.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENT SETUP
text: Datasets and model architectures. We will evaluate the effectiveness of our proposal under CIFAR-10 (Krizhevsky & Hinton, 2009) and ImageNet (Deng et al., 2009). Unless specified otherwise, we will train DNN models PreActResNet (PARN)-18 (He et al., 2016b) for CIFAR-10, and ResNet (RN)-50 (He et al., 2016a) for ImageNet. As a part of ablation study, we also train larger models PARN-50 and WideResNet (WRN)-16-8 (Zagoruyko & Komodakis, 2016) on CIFAR-10.
Baselines. We consider three methods as our baselines: FAST-AT (Wong et al., 2020), FAST-ATGA (Andriushchenko & Flammarion, 2020), and PGD-2-AT (Madry et al., 2018), i.e., the 2-step PGD attack-based AT. The primal criterion of baseline selection is computation complexity. The training time of all methods including ours falls between the time of FAST-AT and that of FAST-ATGA. 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 ∈ {2, 4, . . . , 16}/255 for CIFAR10 and = 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× 10−4. For CIFAR-10, we train each model for 20 epochs in total, where we use 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 λ from 255/5000 to 255/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/3000. For each method, we use the early stopping method to pick the model with best robust accuracy, following (Rice et al., 2020). All the CIFAR-10 experiments are conducted on a single Tesla P-100 GPU and all ImageNet experiments run on a single machine with two Tesla P-100s. All the baselines are implemented using the recommended training configurations in their official GitHub repos. We refer readers to Appendix D 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 ( ) same as the train-time value, and take 50-step PGD with 10 restarts for both CIFAR-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 are averaged over 5 independent trials with different random seeds.
5.2 RESULTS Table 3: SA and RA on ImageNet.
Method SA (%) RA-PGD (%)
FAST-AT 60.90 43.43 FAST-BAT 60.18 44.64 Overall performance of FAST-BAT. In Table 2 and 3, we compare the performance of our proposed FAST-BAT with baselines on CIFAR-10 and ImageNet, respectively.
First, we find that FAST-BAT 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 = 8/255 in the training setup (CIFAR-10, = 8/255). On ImageNet, FAST-BAT outperforms FAST-AT by 1.23% when facing attacks with = 2/255.
Second, FAST-BAT leads to a better SA-RA trade-off compared with the other baselines. For example, in the setup of (CIFAR-10, PARN-18 trained with = 8/255), we observe that FAST-BAT outperforms FAST-AT-GA in RA, without losing SA.And in the setup of (CIFAR-10, PARN-18 trained with = 16/255), FAST-BAT significantly outperforms FAST-AT-GA, with 9.28% SA improvement and comparable or even better RA. Compared with PGD-2-AT, 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 at = 8/255), and 8.55% (evaluated at = 2/255) in the case of (CIFAR-10, trained with = 16/255).
Performance under different model architectures. Besides PARN-18 reported above, Table 4 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 baseline in terms of SA, e.g., the case of (PARN-50, = 8/255). In contrast to FAST-AT and FAST-AT-GA, FAST-BAT is the only approach that yields an evident RA improvement over PGD-2-AT.
Mitigation of robustness catastrophic overfitting. As shown in (Andriushchenko & Flammarion, 2020), FAST-AT suffers robustness catastrophic overfitting when the train-time and test-time attack strength grows. Following (Andriushchenko & Flammarion, 2020), Figure 1 presents two RA-PGD trajectories, i.e., training w/o early stopping and training w/ early stopping, versus the train- and test-time . As
we can see, FAST-AT encounters a sharp RA drop when > 8 when early stopping is not used, consistent with (Andriushchenko & Flammarion, 2020). Assisted by early stopping, the overfitting
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 a more 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 1 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 overfitting. The insight from Figure 1 suggested that FAST-BAT can mitigate overfitting without using explicit GA regularization. Spurred by above, Figure 2 presents the GA score versus the training epoch number, 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-BAT 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 of 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 state-of-the-art model robustness. 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.
Method RA-PGD(%) RA-Transfer Attack(%)PARN-18 PARN-50 WRN-16-8
FAST-AT 45.44 76.35 76.94 77.23 PGD-2-AT 44.71 77.56 78.64 78.84
FAST-AT-GA 47.31 77.34 78.34 78.53 FAST-BAT(Ours) 48.67 78.03 79.93 79.21 Sanity check for obfuscated gradients As pointed out by Athalye et al. (2018a), model robustness could be overestimated due to obfuscated gradients. The model with obfuscated gradients could have ‘obfuscated’ stronger resilience to white-box attacks than transfer (black-box) attacks. To justify the validity of FAST-BAT, Table 2 summarizes the comparison between our proposal and the other baselines when facing white-box adaptive and black-box transfer attacks. Firstly, RA increases if the transfer attack is 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-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 2, and the flatness of adversarial loss landscape in Figure. A1.
Ablation studies. In Appendix E, we present additional empirical studies including 1) the sensitivity analysis of the linearization hyperparameter λ, 2) the choice of the linearization point, 3) the sensitivity analysis of α2, 4) the influence of Hessian matrix on ReLU, and 5) non-ReLU neural networks.

heading: 6 CONCLUSION
text: In this paper, we introduce a novel bi-level optimization (BLO)-based fast adversarial training framework, termed FAST-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 BLO 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-robustness 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 are provided to demonstrate the superiority of our method to state-of-the-art accelerated AT baselines.

heading: A PROOF OF THEOREM 1
text: Proof: Upon defining g(θ, δ) = (δ − z)>∇δ=z`atk(θ, δ) + (λ/2)‖δ − z‖22, we repeat (7) as minimize
θ E(x,y)∈D[`tr(θ, δ∗(θ))]
subject to δ∗(θ) = argmin Bδ≤b g(θ, δ), (12)
where we have used the expression of linear constraints in (9).
Our goal is to derive the IG dδ ∗(θ)>
dθ shown in (3). To this end, we first build implicit functions by leveraging KKT conditions of the lower-level problem of (12). We say δ∗(θ) and λ∗(θ) (Lagrangian multipliers) satisfy the KKT conditions:
Stationarity: ∇δg(θ, δ∗(θ)) +B>λ∗(θ) = 0, Complementary slackness : λ∗(θ) · (Bδ∗(θ)− b) = 0
Dual feasibility: λ∗(θ) ≥ 0 (13)
where · denotes the elementwise product. Active constraints and definition of B0: Let B0 denote the sub-matrix of B and b0 the sub-vector of b, which consists of only the active constraints at δ∗(θ), i.e., those satisfied with the equality B0δ
∗(θ) = b0 (corresponding to nonzero dual variables). The determination of active constraints is done given θ at each iteration.
With the aid of (B0,b0), KKT (13) becomes
∇δg(θ, δ∗(θ)) +B>0 λ∗(θ) = 0, and B0δ∗(θ)− b0 = 0, (14) where the nonzero λ∗(θ) only correspond to active constraints. We take derivatives w.r.t. θ for (14), and thus obtain
d∇δg(θ, δ∗(θ))>
dθ +∇θλ∗(θ)>B0 = 0
=⇒∇θδg(θ, δ∗(θ)) + dδ∗(θ)>
dθ︸ ︷︷ ︸ IG ∇δδg(θ, δ∗(θ)) +∇θλ∗(θ)>B0 = 0, (15)
and dδ∗(θ)>
dθ︸ ︷︷ ︸ IG B>0 = 0, (16)
where ∇θδ ∈ R|θ|×|δ| denotes second-order partial derivatives (recall that |θ| = n and |δ| = d). According to (15), we have
dδ∗(θ)>
dθ = −[∇θδg(θ, δ∗(θ)) +∇θλ∗(θ)>B0]∇δδg(θ, δ∗(θ))−1. (17)
Substituting the above into (16), we obtain
∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1B>0 +∇θλ∗(θ)>B0∇δδg(θ, δ∗(θ))−1B>0 = 0, (18) which yields:
∇θλ∗(θ)> = −∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1B>0 [B0∇δδg(θ, δ∗(θ))−1B>0 ]−1, (19) and thus,
∇θλ∗(θ)>B0 = −∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1B>0 [B0∇δδg(θ, δ∗(θ))−1B>0 ]−1B0. (20)
Substituting (20) into (17), we obtain the IG
dδ∗(θ)>
dθ = −∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1 −∇θλ∗(θ)>B0∇δδg(θ, δ∗(θ))−1
= −∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1
+∇θδg(θ, δ∗(θ))∇δδg(θ, δ∗(θ))−1B>0 [B0∇δδg(θ, δ∗(θ))−1B>0 ]−1B0∇δδg(θ, δ∗(θ))−1. (21)
To further compute (21), the Hessian matrix ∇δδ`atk is needed. Recall from the definition of the lower-level objective that the Hessian matrix is given by
∇δδg(θ, δ∗(θ)) = ∇δδ`atk + λI = 0+ λI. (22)
Here we used the assumption that ∇δδ`atk = 0. The rationale behind that is neural networks commonly leads to a 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)∇δδ`atk is close to zero. Based on the simplification (22), we have
dδ∗(θ)>
dθ =− (1/λ)∇θδg(θ, δ∗(θ))
( I−B>0 [B0B>0 ]−1B0 )︸ ︷︷ ︸ :=HC
− (1/λ)∇θδ`atk(θ, δ∗(θ))HC , (23)
where we have used the fact that∇θδg = ∇θδ`atk. What is HC in (23)? Since B = [ I −I ] , we can obtain that B0B>0 = I and B > 0 B0 is a sparse diagonal
matrix with diagonal entries being 0 or 1. Thus, HC can be first simplified to
HC = I−B>0 B0. (24)
Clearly, HC is also a diagonal matrix with either 0 or 1 diagonal entries. The 1-valued diagonal entry of HC corresponds to the inactive constraints in Bδ∗(θ) < b, i.e., those satisfied with strict inequalities in {‖δ‖∞ ≤ ,0 ≤ δ ≤ 1}. This can be expressed as
HC = [ 1p1≤δ∗1≤q1e1, . . . , 1p1≤δ∗d≤qded ] (25)
where 1pi≤δ∗i≤qi ∈ {0, 1} denotes the indicator function over the constraint {pi ≤ δ ∗ i ≤ qi} and returns 1 if the constraint is satisfied, δ∗i denotes the ith entry of δ ∗(θ), pi = max{− ,−xi} and qi = min{ , 1 − xi}, and ei ∈ Rd denotes the basis vector with the ith entry being 1 and others being 0s.
Based on the definition of g, (23) and (25), we can eventually achieve the desired IG formula (10). The proof is now complete.
B DISCUSSION ON CASE `atk = −`tr
We provide an explanation on the argument "Even if we set `atk = −`tr, problem (2) does not reduce to problem (1) due to the presence of lower-level constraint" from the following two points.
• In the absence of the constraint δ ∈ C, if we set `atk = −`tr, then Problem 2 will reduce to Problem 1. This is a 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 unconstrained lower-level optimization, we have ∇δ`atk(θ, δ∗) = 0. Since `atk = −`tr, we have ∇δ`tr(θ, δ∗) = 0. As a result, the second term in Eq. 3 becomes 0 and solving problem 2 becomes identical to solving the min-max problem 1.
• In the presence of the constraint δ ∈ C, the stationary condition cannot be applied since the stationary point may not be a feasible point in the constraint. In other words,∇δ`atk(θ, δ∗) = 0 does not hold in the case of `atk = −`tr. As a matter of fact, one has to resort to KKT conditions instead of the stationary condition for a constrained lower-level problem. Similar to our proof in Theorem 1, the implicit gradient (and thus the second term of Eq. 3) cannot be omitted in general. This makes problem 2 different from the problem 1.

heading: C DERIVATION OF IMPLICIT GRADIENT FOR FAST-AT
text: We can derive Eq. 6 using KKT condition similar to Theorem 1. Specifically, let
g(θ, δ) = 〈sign(∇δ=z`atk(θ, δ;x, y)), δ − z〉+ λ
2 ‖δ − z‖22, (26)
we have
∇θδg = 0. (27)
Following (21), we can further obtain (6) based on (27).

heading: D DETAILED EXPERIMENT SETTINGS

heading: D.1 TRAINING SET-UP
text: For CIFAR-10, we summarize the training setup for each method. 1) FAST-AT: We use FGSM with an attack step size of 1.25 to generate perturbations; 2) PGD-2-AT: 2-step PGD attacks1 with an attack step size of 0.5 is implemented; 3) FAST-AT-GA: The gradient alignment regularization parameter is set to the recommended value for each ; 4) FAST-BAT: We select λ from 255/5000 to 255/2000 for different . At the same time, we adjust α2 accordingly, so that the coefficient of the second term in (11), namely α2/λ always equals to 0.1α1.
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 λ at 255/3000 and adopt the same α2 selection strategy as CIFAR-10.
Parameter for FAST-AT-GA Regarding FAST-AT-GA with different model types, we adopt the same regularization parameter recommended in its official repo2 intended for PreActResNet-18 (namely 0.2 for = 8/255 and 2.0 for = 16/255).
1We use random initialization to generate perturbations for PGD, while in the paper of FAST-AT-GA (Andriushchenko & Flammarion, 2020), 2-step PGD is initialized at zero point, which we believe will underestimate the effect of PGD-2-AT
2FAST-AT-GA: https://github.com/tml-epfl/understanding-fast-adv-training/ blob/master/sh

heading: E ADDITIONAL EXPERIMENTAL RESULTS

heading: FAST-AT FAST-AT-GA FAST-BAT
text: Figure A1: Visualization of adversarial loss landscapes of FAST-AT, FAST-AT-GA and FAST-BAT trained using the ResNet-18 model on the CIFAR-10 dataset. The losses at are calculated w.r.t. the same image example ID #001456, and the landscape is obtained by tracking the loss changes w.r.t. input variations following Engstrom et al. (2018). That is, the loss landscape is generated by z = loss(I +x · r1 + y · r2), where I denotes an image, and the x-axis and the y-axis correspond to linear coefficients associated with the sign-based attack direction r1 = sign(∇I loss(I)) x̂ and a random direction r2 ∼ Rademacher(0.5), respectively.
Table A1: Performance of FAST-BAT with different parameter λ. We train and evaluate with the same attack budget = 16/255 on CIFAR-10 to show the influence brought by λ.
CIFAR-10, PreActResNet-18, = 16/255
1/λ (/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

heading: Sensitivity to regularization parameter λ
text: In Table A1, we show the sensitivity of FASTBAT to the regularization parameter λ. All the parameters remain the same as default setting, except that for different λ. We always adjust α2 so that α2/λ = 0.1α1 holds. Note 1/λ also serves as the attack step in (8). As λ decreases, the improvement on robust accuracy is evidently strengthened, and there is a obvious trade-off between robust accuracy (SA) and standard accuracy (RA). At a certain level of λ, namely when λ ≤ 255/2000, RA starts to converge and stop surging.
Table A2: Performance of FAST-BATwith different α2 choices on CIFAR-10. Models are trained and evaluated with the same attack budget ( = 16/255). Here α1 is set as the cyclic learning rate and thus, is not a constant parameter. α2 is always set proportionate to α1 for simplicity. α2 (CIFAR-10,
PreActResNet18, = 16/255) 0.025α1 0.0167α1 0.0125α1 0.008α1
SA (%) 75.06 69.31 67.81 57.92 RA-PGD (%) 21.42 23.34 26.07 20.53 Sensitivity to different α2 choices We consider the case of robust training with the large choice (16/255). As we can see from Table A2, if α2 is set too small (α2 = 0.008α1), then both SA and RA will drop significantly. Here α1 is set as the cyclic learning rate and thus not a constant parameter. However, in the α2 interval [0.0125α1, 0.025α1], we observed a tradeoff between standard accuracy (SA) and robust accuracy (RA): That is, the improvement in RA corresponds to a loss in SA. In our experiments, we choose α2 when the tradeoff yields the best RA without suffering a significant drop of SA (which still outperforms the baseline approaches).
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 [− , ]d (Uniformly Random); uniformly random corner {− , }d (Random Corner); and perturbation from 1-step PGD attack with 0.5 as attack step (PGD).
CIFAR-10, PreActResNet-18, = 16/255
Linearization Method PGD w/o Sign Uniformly Random Random Corner PGD
SA (%) 69.31 43.42 62.19 75.30 RA-PGD (%) 23.34 21.25 16.5 19.42 Sensitivity of linearization schemes FastBAT needs a good linearization point z in (7). In experiments, we adopt the perturbation generated by 1-step PGD without sign as our default linearization scheme. In Table A3, we show the performance of the other possible linearization options. We can find 1-step PGD without sign achieves best robust accuracy among all the choices. This is not spurring since this linearization point choice is consistent with the firstTaylor expansion that we used along the direction of input gradient without sign involved. By contrast, FAST-BAT linearized with uniformly random noise suffers from catastrophic overfitting and reaches a rather low standard accuracy (SA). FAST-BAT with other linearizations also yields worse SA-RA trade-off than our proposal.
Table A4: Performance of Hessian-free and Hessian-aware FAST-BATon CIFAR-10. We train and evaluate with the same attack budgets = 8/255 and = 16/255 to show the influence brought by Hessian matrix.
Method RA-PGD (%)( = 8/255) RA-PGD (%) ( = 16/255) RA-AA (%) ( = 8/255) RA-AA (%) ( = 16/255) SA (%) ( = 8/255) SA (%) ( = 16/255) Time (s/epoch)
Hessian-free Fast-BAT 48.67 26.07 44.86 18.18 79.47 67.81 135 Hessian-aware Fast-BAT 48.52 26.12 44.81 18.31 79.54 67.93 179
Table A5: Performance of FAST-ATand FAST-BATwith different activation functions on CIFAR-10. ReLU, Swish and Softplus are taken into consideration. For FAST-BAT, we compare the Hessian-free and Hessian-aware version to verify the influence of Hessian matrix. The results are averaged over 3 independent trials.
Setting SA (%)( = 8/255) RA-PGD (%) ( = 8/255) SA (%) ( = 16/255) RA-PGD (%) ( = 16/255) Time (s/epoch)
Fast-AT-ReLU 81.88 45.44 46.13 21.75 42 Fast-BAT-ReLU (Hessian-aware) 79.54 48.52 67.93 26.12 179 Fast-BAT-ReLU (Hessian-free) 79.47 48.67 67.81 26.07 135
Fast-AT-Softplus 81.29 47.26 45.39 22.40 42 Fast-BAT-Softplus (Hessian-aware) 79.59 49.74 68.63 25.54 178 Fast-BAT-Softplus (Hessian-free) 79.48 49.67 68.57 25.59 137
Fast-AT-Swish 75.61 44.43 52.03 23.08 49 Fast-BAT-Swish (Hessian-aware) 73.93 45.97 62.49 23.99 196 Fast-BAT-Swish (Hessian-free) 73.89 45.90 62.59 23.81 141
Influence of Hessian matrix In Theorem 1, the Hessian-free assumption, i.e.∇δδ`atk = 0, was made to simplify the computation of IG term (implicit gradient). To examine how the Hessian matrix ∇δδ`atk 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 (21). 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-BATas around 30% more time is needed. Therefore, the Hessian-free assumption is reasonable and also necessary in terms of the efficiency of the algorithm.
Ablation study on smooth activation functions The Hessian-free assumption is based on the fact that the commonly used ReLU activation function is piece-wise linear w.r.t. input. We further conduct experiments to verify the feasibility of such assumption on models with non-ReLU activation functions. We choose two commonly used activation functions, Swish(Ramachandran et al., 2017) 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-free assumption still holds for the non-ReLU neural network. The results are shown in 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 assumption is reasonable across different activation function choices.

Review summaries:
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: - Fast-AT: carefully perform single-step PGD (otherwise known as FGSM) to train $\ell_\inf$ robust models - from Wong, Rice and Kolter 2020 - Fast-AT-GA: single-step PGD + a gradient alignment loss function - from Andriushchenko and Flammarion 2020.  The work then lists a problem with Fast-AT: - 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)  Finally, 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%. 

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.

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.