PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting and Advancing Fast Adversarial Training Through The Lens of Bi-Level Optimization

Yihua Zhang, Guanhua Zhang, Prashant Khanduri, Mingyi Hong, Shiyu Chang, Sijia Liu

arXiv:2112.12376v6cs.LG

TL;DR

Adversarial training is difficult to scale, and fast variants face theoretical and empirical limitations. The paper reframes robust training as bi-level optimization and proposes FAST-BAT; experiments report improved robustness across datasets and attack types.

  • Problem

    Adversarial training is costly to scale, while FAST-AT lacks theoretical guarantees and can suffer catastrophic overfitting with strong adversaries.

    Source: §1 · pp. 1–2

  • Method

    The paper formulates adversarial training as bi-level optimization, interprets FAST-AT through a linearized lower-level problem, and develops FAST-BAT using a smooth lower-level objective and implicit gradients.

    Source: §1 · p. 2

  • Results

    FAST-BAT consistently outperforms baselines across datasets and attack types, improving RA-PGD by over 1.5% and RA-AA by around 1% across datasets and both attack strengths.

    Source: §5.2 · p. 7

  • Takeaways & Limitations

    The authors report improved stability, mitigated catastrophic overfitting, and an enhanced accuracy-robustness tradeoff for FAST-BAT.

    Source: §6 · p. 9

    FAST-AT's linearized lower-level problem involves a discrete sign operator, making strong guarantees for approximated stochastic-gradient algorithms unlikely.

    Source: §3 · p. 5

Abstract

from arXiv · show

Adversarial training (AT) is a widely recognized defense mechanism to gain the robustness of deep neural networks against adversarial attacks. It is built on min-max optimization (MMO), 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 conventional MMO method makes AT hard to scale. Thus, Fast-AT (Wong et al., 2020) and other recent algorithms attempt to simplify MMO by replacing its maximization step with the single gradient sign-based attack generation step. Although easy to implement, Fast-AT lacks theoretical guarantees, and its empirical performance is unsatisfactory due to the issue of robust catastrophic overfitting when training with strong adversaries. In this paper, we advance Fast-AT from the fresh perspective of bi-level optimization (BLO). We first show that the commonly-used Fast-AT is equivalent to using a stochastic gradient algorithm to solve a linearized BLO problem involving a sign operation. However, the discrete nature of the sign operation makes it difficult to understand the algorithm performance. Inspired by BLO, we design and analyze a new set of robust training algorithms termed Fast Bi-level AT (Fast-BAT), which effectively defends sign-based projected gradient descent (PGD) attacks without using any gradient sign method or explicit robust regularization. In practice, we show our method yields substantial robustness improvements over baselines across multiple models and datasets. Codes are available at https://github.com/OPTML-Group/Fast-BAT.

1. Introduction

The introduction frames adversarial training as costly to scale and fast variants as lacking stability, robustness, and theoretical guarantees. It presents a bi-level optimization perspective and FAST-BAT as a way to advance fast adversarial training.

1. Introduction

  • AT uses min-max optimization, but iterative attack generation makes it computationally costly and difficult to scale.The introduction notes that an ImageNet AT run used 128 GPUs.Source: §1 · p. 1
  • FAST-AT uses single-step attack generation, yet can be unstable, suffer catastrophic overfitting under strong adversaries, and lack theoretical guarantees.FAST-AT-GA improves robustness but can incur a significant standard-accuracy loss at ϵ = 16/255.Source: §1 · pp. 1–2
  • The paper asks how to design fast AT with improved stability, less catastrophic overfitting, a better robust-standard accuracy tradeoff, and theoretical guarantees.Source: §1 · p. 2
  • Over 1.5% higher RA in all experimental settings, with SA gains of 9.9% on CIFAR-10 and 6.7% on CIFAR-100 at ϵ = 16/255, are reported for FAST-BAT.The introduction describes FAST-BAT as achieving the best robustness with a more graceful SA-RA tradeoff; Table 1 compares it with FAST-AT and FAST-AT-GA.Source: §1 · p. 2, Table 1 · p. 2
  • The authors formulate AT as bi-level optimization, interpreting FAST-AT as solving a low-level linearized bi-level problem rather than the vanilla min-max problem.They state that this interpretation helps explain why FAST-AT is difficult to equip with strong theoretical guarantees.Source: §1 · p. 2
  • FAST-BAT introduces a smooth lower-level objective and uses implicit gradients; experiments report improved robustness, stability, accuracy-robustness tradeoff, and reduced catastrophic overfitting.The authors report deriving a closed-form implicit gradient for FAST-BAT and evaluating it across datasets and model types.Source: §1 · p. 2

2. Related work

Related work covers adversarial attacks and defenses, the challenge of speeding up adversarial training, and bi-level optimization. It positions FAST-BAT among fast AT methods and distinguishes its formulation from prior BLO work on AT.

2. Related work

  • AT and its variants are used for robust training, with extensions including TRADES, semi- or self-supervised settings, and randomized smoothing.Source: §2 · p. 3
  • Speeding up AT without losing performance remains an open question, and fast approximate methods such as FAST-AT and FAST-AT-GA are particularly relevant low-computation baselines.Source: §2 · p. 3
  • Fast AT methods simplify AT to reduce computation, but FAST-AT is associated with poor stability and catastrophic overfitting, while FAST-AT-GA has a poor accuracy-robustness tradeoff.Source: §2 · p. 3
  • BLO is hierarchical, with upper-level objectives and variables depending on lower-level problems; prior AT work used a Stackelberg Game for NLP generalization, unlike this paper's vision-robustness focus.The authors say their generic lower-level formulation models adversarial learning and can support theoretical analysis under conditions on that problem.Source: §2 · p. 3

3. A Bi-Level Optimization View on FAST-AT

The paper formulates adversarial training as bi-level optimization (BLO) and interprets FAST-AT as an approximate solver for a linearized BLO problem rather than the original min-max problem. Its sign-based gradient approximation complicates theoretical guarantees.

3. A Bi-Level Optimization View on FAST-AT

  • FAST-AT replaces the iterative inner maximization of standard adversarial training with a single-step PGD attack to improve scalability.The paper notes that FAST-AT’s inner update starts from the initial perturbation rather than the most recent one.Source: §3 · pp. 3–4
  • BLO models training-loss minimization as an upper-level problem and attack generation as a nested lower-level problem, with independently chosen objectives.Choosing the attack objective as the negative training loss recovers the standard min-max formulation.Source: §3 · p. 4
  • FAST-AT corresponds to an approximate stochastic-gradient method for a lower-level linearized BLO, not the original min-max problem.With z = δ0 and λ = 1/α, the lower-level solution matches FAST-AT’s one-step PGD attack.Source: §3 · pp. 4–5
  • FAST-AT’s sign operation simplifies implicit-gradient computation, but its discrete nature and gradient approximations leave objective reduction and strong guarantees unclear.The paper notes that projection and sign operations complicate differentiation in this formulation.Source: §3 · p. 5

4. FAST-BAT: Advancing FAST-AT by BLO

FAST-BAT advances the BLO formulation by replacing FAST-AT’s sign-based linearization with a first-order Taylor expansion and deriving an implicit gradient for the constrained lower-level problem. Its algorithm combines that gradient with model training, and the paper establishes convergence under stated gradient-bias assumptions.

4. FAST-BAT: Advancing FAST-AT by BLO

  • FAST-BAT uses a first-order Taylor expansion rather than FAST-AT’s sign-based linearization of the lower-level attack objective.The resulting lower-level optimizer retains an implicit gradient that cannot be approximated by zero as in the sign-based formulation.Source: §4 · p. 5
  • KKT conditions yield an analytical implicit gradient for FAST-BAT’s linearly constrained lower-level problem.The formula involves second-order derivatives and matrix inversion.Source: §4 · p. 5
  • The Hessian-free assumption sets the attack-objective Hessian to zero, which the authors motivate by piecewise-linear decision boundaries and report as reasonable across ReLU and non-ReLU networks.This approximation simplifies the implicit-gradient computation.Source: §4 · pp. 5–6
  • FAST-BAT alternates lower-level attack optimization with an upper-level model update that adds an implicit-gradient term to the regular FAST-AT update.A suitable α2 helps mitigate catastrophic overfitting; the experiments use 1-step PGD without sign for the linearization point and set α2/λ = 0.1α1.Source: §4 · p. 6
  • Under assumptions on gradient bias, FAST-BAT converges to a first-order stationary point or a small neighborhood at rate O(1/T).The analysis identifies the coupled derivatives in the model update as its main difficulty.Source: §4 · p. 6

5. Experiments

Across multiple datasets, attack strengths, and model types, FAST-BAT improves robustness over the baselines while preserving a better standard-accuracy–robust-accuracy trade-off. Experiments also examine catastrophic overfitting, gradient alignment, adaptive and transfer attacks, and the Hessian-free assumption.

5.1. Experiment Setup

  • Experiments cover CIFAR-10, CIFAR-100, Tiny-ImageNet, and ImageNet, using PGD-based baselines and reporting RA-PGD, RA-AA, and SA.Results are averaged over 10 trials; evaluation uses 50-step PGD with 10 restarts unless specified otherwise.Source: §5.1 · pp. 6–7

5.2. Results

  • FAST-BAT improves RA-PGD by over 1.5% and RA-AA by around 1% across datasets and attack strengths, with a gain over 2% on Tiny-ImageNet at ϵ = 16/255.On ImageNet, it outperforms FAST-AT by 1.23% at ϵ = 2/255.Source: §5.2 · p. 7
  • At ϵ = 16/255, FAST-BAT improves SA over FAST-AT-GA by 9.9%, 6.7%, and 4.6% on CIFAR-10, CIFAR-100, and Tiny-ImageNet, respectively.The paper characterizes this as a better SA-RA trade-off than the baselines.Source: §5.2 · p. 7
  • On deeper PARN-50 and wider WRN-18-6 models, FAST-BAT improves RA over the other methods and is the only approach with an evident RA gain over PGD-2-AT.PGD-2-AT can remain competitive in SA.Source: §5.2 · pp. 7–8
  • FAST-BAT mitigates robust catastrophic overfitting and improves RA without explicit robustness-stability regularization.FAST-AT's RA drops sharply above ϵ = 8 without early stopping; early stopping alleviates the drop only to some extent.Source: §5.2 · p. 8
  • FAST-BAT's GA score stays close to FAST-AT-GA's while it mitigates overfitting without explicit GA regularization.The authors suggest a high GA score may be necessary but not sufficient to avoid catastrophic overfitting.Source: §5.2 · p. 8, Figure 2 · p. 8
  • FAST-BAT consistently outperforms the baselines under adaptive and transfer attacks; for all methods, RA is higher under transfer attacks.The authors take the latter pattern as consistent with transfer attacks being weaker than adaptive attacks, and use the results to support the absence of obfuscated gradients.Source: §5.2 · pp. 8–9, Table 4 · p. 8
  • Hessian-aware FAST-BAT shows little performance difference from the Hessian-free version but requires around 30% more time.The authors therefore regard the Hessian-free assumption as reasonable and necessary for efficiency.Source: §5.2 · p. 9, Table 5 · p. 9

6. Conclusion

FAST-BAT is a bi-level optimization-based fast adversarial training framework that provides a theoretical interpretation of FAST-AT and improves reported training outcomes.

6. Conclusion

  • FAST-AT is equivalent to lower-level linearized bi-level optimization along the input-gradient sign direction.The paper presents this connection through implicit gradients.Source: §6 · p. 9
  • FAST-BAT improves performance stability, mitigates catastrophic overfitting, and enhances the accuracy-robustness trade-off.Experiments are reported to demonstrate superiority over state-of-the-art accelerated adversarial training baselines.Source: §6 · p. 9
  • The paper establishes a theory and algorithmic foundation for bi-level optimization in adversarial training.Source: §6 · p. 9

A. Proof of Proposition 1 and Corollary 1

The proof derives FAST-BAT's implicit gradient using lower-level KKT conditions, active constraints, and a Hessian-free approximation.

A. Proof of Proposition 1 and Corollary 1

  • The proof uses the linear-constraint expression and the definition of g to obtain the implicit-gradient formula in equation (12).Source: A. Proof of Proposition 1 and… · pp. 12–13
  • KKT conditions for the constrained lower-level problem define implicit functions for the optimal perturbation and its Lagrangian multipliers.The derivation then differentiates these conditions with respect to model parameters.Source: A. Proof of Proposition 1 and… · p. 12
  • Active constraints are those satisfying equality at the optimal perturbation, and only these constraints enter the reduced KKT system.Their determination is made for each parameter iterate.Source: A. Proof of Proposition 1 and… · p. 12
  • Assuming the attack-loss Hessian with respect to perturbations is zero simplifies the implicit-gradient derivation.The stated rationale is that neural-network decision boundaries are commonly piece-wise linear with respect to inputs, making the Hessian close to zero.Source: A. Proof of Proposition 1 and… · p. 13

B. Discussion on case ℓatk = −ℓtr

With no lower-level constraint, setting the attack loss to the negative training loss makes the implicit-gradient method reduce to ordinary gradient descent; constraints generally prevent this reduction.

B. Discussion on case ℓatk = −ℓtr

  • Without the constraint δ ∈ C, setting ℓatk = −ℓtr makes the implicit-gradient descent method reduce to ordinary gradient descent.The unconstrained lower-level stationary condition makes the second term in the update zero.Source: B. Discussion on case ℓatk = −ℓtr · p. 14
  • With δ ∈ C, the stationary condition may fail at the constrained solution, so the implicit-gradient term generally cannot be omitted.The constrained problem instead requires KKT conditions, leaving its optimization routine different from the min-max problem.Source: B. Discussion on case ℓatk = −ℓtr · p. 14

C.1. Training Set-up

The appendix specifies CIFAR-10 and ImageNet training parameters and compares initialization choices for FAST-BAT's lower-level linearization.

C.1. Training Set-up

  • For CIFAR-10, FAST-AT uses FGSM with step size 1.25ϵ, PGD-2-AT uses two steps of size 0.5ϵ, and FAST-BAT selects λ by ϵ.FAST-BAT adjusts α2 so α2/λ equals 0.1α1; for ImageNet it fixes ϵ at 2/255 and λ at 255/3000.Source: §C.1 · p. 15

C.2. The choice of initialization point z

  • FAST-BAT tests random-constant and one-step warm-up linearization points; one-step PGD without sign gives the best defensive performance at comparable computation cost.For PGD initialization, the authors use random initialization and say zero initialization in Andriushchenko & Flammarion (2020) may underestimate PGD-2-AT's effect.Source: §C.2 · p. 15

D. Additional Experimental Results

Additional experiments compare FAST-BAT with fast-training baselines and examine its performance across ImageNet, parameter choices, linearization schemes, and activation functions. They report robust-accuracy gains alongside trade-offs and implementation costs.

Results on ImageNet

  • FAST-BAT outperforms FAST-AT by 1.23% against PGD-50-10 attacks at ϵ = 2/255 on ImageNet.The comparison uses ResNet-50; the reported benefit from alleviating robust catastrophic overfitting is less evident at this small training perturbation strength.Source: Table 6 · p. 16, D. Additional Experimental Results · p. 16

Sensitivity to regularization parameter λ

Sensitivity to different α2 choices

  • With ϵ = 16/255, α2 = 0.008α1 lowers both SA and RA, while choices in [0.0125α1, 0.025α1] trade improved RA against lower SA.The selected α2 aims for the best RA without a significant SA drop, while still outperforming baseline approaches.Source: Table 8 · p. 16, D. Additional Experimental Results · p. 16

Sensitivity of linearization schemes

Comparisons with more baselines

  • FAST-BAT stands out among fast robust-training methods across perturbation strengths, while PGD-7-AT typically achieves the best robust accuracy at the highest computation cost.The comparison includes PGD-7-AT, BACKSMOOTH, ATTA, FREE-AT, and YOPO.Source: Table 10 · p. 17, D. Additional Experimental Results · p. 17

The validity of the Hessian-free assumption on non-ReLU based neural networks

  • Across ReLU, Softplus, and Swish, adding the Hessian changes performance little but increases time consumption by more than 30%.The authors conclude that the Hessian-free assumption is reasonable across these activation functions.Source: D. Additional Experimental Results · p. 17, Table 11 · p. 18

E. Convergence Analysis

The convergence analysis considers FAST-BAT with minibatch gradient estimates, whose bias and variance depend on batch size. Under smoothness and a step-size condition, it derives an inequality relating expected gradient magnitude to loss decrease and estimation error.

E. Convergence Analysis

  • FAST-BAT approximates its training gradient with a batch of size b, modeled with batch-dependent bias β(b) and variance σ².Both quantities are zero when b = N, the full training-set size.Source: E. Convergence Analysis · pp. 18–19
  • For a smooth training loss and a step size satisfying αt ≤ 1/[4L(2+σ²)], the analysis bounds expected squared gradient magnitude by loss decrease and batch-estimation terms.The bound includes β(bt) and σ², as well as the step size and smoothness constant.Source: E. Convergence Analysis · p. 19

Related papers

Loading 2112.12376v6…