Adversarial Training and Provable Robustness: A Tale of Two Objectives

Jiameng Fan, Wenchao Li

Abstract

We propose a principled framework that combines adversarial training and provable robustness verification for training certifiably robust neural networks. We formulate the training problem as a joint optimization problem with both empirical and provable robustness objectives and develop a novel gradient-descent technique that can eliminate bias in stochastic multi-gradients. We perform both theoretical analysis on the convergence of the proposed technique and experimental comparison with state-of-the-arts. Results on MNIST and CIFAR-10 show that our method can consistently match or outperform prior approaches for provable $l_\infty$ robustness. Notably, we achieve 6.60% verified test error on MNIST at $\epsilon = 0.3$, and 66.57% on CIFAR-10 with $\epsilon = 8/255$.

Introduction

Deep neural networks are notoriously fragile, often susceptible to small, intentional perturbations known as adversarial examples. To address this, researchers have developed two primary defense strategies: Adversarial Training (AT) and Provable Robustness. AT involves training models on adversarial examples generated during training (e.g., via PGD attacks), providing strong empirical defense but no mathematical guarantees. Conversely, provable robustness methods use abstract interpretation, such as Interval Bound Propagation (IBP), to compute a mathematical upper bound on the worst-case loss. While these provide guarantees, they often suffer from "loose" bounds that are difficult to optimize or lead to lower standard accuracy.

The gap between these two objectives is significant. Minimizing adversarial loss does not guarantee a provable certificate, and minimizing the provable bound does not always yield a model that performs well against actual attacks. This paper introduces AdvIBP, a framework that bridges this gap by simultaneously optimizing for both empirical and provable robustness.

The AdvIBP Framework

The core idea of AdvIBP is to "sandwich" the true robust loss between an adversarial lower bound and an abstract upper bound. By minimizing both, the true robust loss is effectively squeezed from both ends, leading to a more stable and robust model.

For efficiency, AdvIBP utilizes the Fast Gradient Sign Method (FGSM) with random initialization for the adversarial component and IBP for the provable component. The training objective is formulated as a joint optimization problem: $$ \min_{\theta} \mathcal{L}_{joint}(\theta) = \alpha \mathcal{L}_{adv}(\theta) + (1-\alpha) \mathcal{L}_{IBP}(\theta) $$ where $\alpha$ is a weighting factor. However, simple weighted sums can be problematic due to conflicting gradients and the introduction of bias when using stochastic weights.

Unbiased Multi-Gradient Descent and Dynamic Prioritization

To address the challenges of multi-objective optimization, the authors propose a novel unbiased gradient-descent technique. Instead of static weights, they use moment estimates—moving averages of gradients and their norms—to adaptively weight the objectives.

Furthermore, they implement dynamic prioritization using the First-Order Stationary Condition (FOSC) to measure attack strength, denoted as $c(\mathbf{x}_{adv})$. This allows the algorithm to decide when to focus on empirical defense versus tightening mathematical certificates.

Illustration of the multi-gradient descent strategy. The final gradient $g_{final}$ is adaptively computed based on the alignment of the adversarial gradient $g_{adv}$ and the IBP gradient $g_{IBP}$, as well as the attack strength $c(\mathbf{x}_{adv})$.

As shown in the figure above, the strategy handles three main cases:

  1. Aligned Gradients ($g_{adv}^T g_{IBP} > 0$): When gradients are in the same general direction, they are combined to reinforce the common descent path.
  2. Conflicting Gradients, Weak Attack ($g_{adv}^T g_{IBP} \le 0$ and $c(\mathbf{x}_{adv}) \le c_t$): If the attack is weak, the algorithm prioritizes tightening the provable bounds while projecting the gradient to avoid harming empirical robustness.
  3. Conflicting Gradients, Strong Attack ($g_{adv}^T g_{IBP} \le 0$ and $c(\mathbf{x}_{adv}) > c_t$): If the attack is strong, the algorithm prioritizes adversarial training to find a more robust region in the parameter space.

Experimental Results

The AdvIBP method was evaluated on MNIST and CIFAR-10 benchmarks under $l_\infty$ perturbations.

  • MNIST: At $\epsilon=0.3$, AdvCROWN-IBP (a variant using tighter CROWN bounds) achieved a state-of-the-art 6.60% verified test error.
  • CIFAR-10: At $\epsilon=8/255$, the method achieved 66.57% verified test error, outperforming existing IBP and CROWN-based baselines.

AdvIBP demonstrated consistent improvements across various model sizes (Small, Medium, Large) and maintained high efficiency. Since it relies on FGSM and IBP, its training time is comparable to standard adversarial training, making it significantly faster than methods requiring complex solvers.

Conclusion and Future Work

AdvIBP provides a principled way to combine empirical and provable robustness. By eliminating gradient bias and dynamically prioritizing objectives, it achieves superior performance on standard benchmarks. Future work includes addressing the inherent "looseness" of IBP and scaling these provable techniques to high-resolution datasets like ImageNet, where computational costs remain a significant barrier.

Summary updated

Abstract

We propose a principled framework that combines adversarial training and provable robustness verification for training certifiably robust neural networks. We formulate the training problem as a joint optimization problem with both empirical and provable robustness objectives and develop a novel gradient-descent technique that can eliminate bias in stochastic multi-gradients. We perform both theoretical analysis on the convergence of the proposed technique and experimental comparison with state-of-the-arts. Results on MNIST and CIFAR-10 show that our method can consistently match or outperform prior approaches for provable l∞ robustness. Notably, we achieve 6.60% verified test error on MNIST at ε = 0.3, and 66.57% on CIFAR-10 with ε = 8/255.
BibTeX
@inproceedings{fan2021adversarial,
  author = {Jiameng Fan and Wenchao Li},
  title = {{Adversarial Training and Provable Robustness: A Tale of Two Objectives}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=AgAaT5BHYM},
}
Figure