Accelerating Adversarially Robust Model Selection for Deep Neural Networks via Racing

Matthias König, Holger H. Hoos, Jan N. van RijnAAAI 2024 · DOI

Introduction

Deep neural networks are notoriously vulnerable to adversarial attacks—small, imperceptible perturbations that can cause a model to misclassify inputs. To guarantee safety, researchers employ formal verification to mathematically prove a model's robustness. However, this process is computationally intensive, often taking hours per image. When selecting the most robust model from a large pool of candidates, such as in Neural Architecture Search (NAS), the total verification time can reach thousands of GPU hours. This paper introduces a "racing" framework that significantly accelerates this selection process by disqualifying underperforming models early and prioritizing the most informative test instances.

The Racing Framework

The core idea behind the proposed approach is to treat model selection as a competition. Instead of exhaustively verifying every model on every image in a test set, the authors propose two main racing algorithms:

  1. Naive Racing: This aggressive strategy verifies models on one image at a time. If a model's robust accuracy falls below that of its competitors, it is immediately discarded.
  2. F-Race: A more conservative approach that uses statistical tests (Cochran’s Q and McNemar’s test) to ensure a model is statistically inferior before elimination, mitigating the risk of premature disqualification due to the random order of test images.

Δ-Sorting: A Smart Selection Mechanism

Standard racing algorithms typically select test images at random. This paper introduces Δ-sorting to make the racing process more efficient. The Δ-value is defined as the difference between a model's highest and second-highest output scores (logits). A small Δ indicates that the model is "unsure," suggesting the input is near a decision boundary and thus more likely to be vulnerable to adversarial attacks.

Cumulative distribution of Δ-values for MNIST and CIFAR-10, showing that non-robust (unsat) instances typically have lower Δ-values.

As shown in Figure 2, there is a clear statistical correlation: non-robust (unsat) instances consistently exhibit lower Δ-values than robust (sat) ones. By sorting the test set and evaluating these "hard" images first, the racing algorithm can expose model weaknesses much earlier, leading to faster disqualifications.

Experimental Evaluation

The authors evaluated their framework on MNIST (31 models) and CIFAR-10 (27 models) using state-of-the-art verifiers like VeriNet and β-CROWN.

Efficiency Gains

The racing method achieved dramatic speedups compared to exhaustive evaluation:

  • MNIST: Up to 108x faster.
  • CIFAR-10: Up to 42x faster.

For CIFAR-10, where exhaustive verification required 558 GPU hours, the racing approach identified the optimal model in a fraction of the time.

Model Pruning Dynamics

The effectiveness of the sorting mechanism is most evident when observing how quickly the pool of candidate models shrinks.

Reduction in candidate models over iterations for MNIST and CIFAR-10 across different racing strategies.

As illustrated in Figure 6, the "Naive racing with sorting mechanism" (red dotted line) prunes the search space almost instantly. Surprisingly, despite its aggressiveness, Naive Racing consistently reached zero "regret"—meaning it successfully identified the absolute best model—after processing only a tiny fraction of the test data.

Conclusion and Future Work

The racing framework, combined with Δ-sorting, offers a powerful solution to the bottleneck of robust model selection. By focusing computational resources on the most vulnerable instances and the most promising models, it achieves order-of-magnitude speedups without sacrificing the quality of the final selection.

Future research could explore the applicability of Δ-sorting to other perturbation types, such as rotations or brightness changes, and investigate whether these efficiency gains scale to even larger, more complex neural architectures.

Summary updated

BibTeX
@inproceedings{konig2024accelerating,
  author = {Matthias König and Holger H. Hoos and Jan N. van Rijn},
  title = {{Accelerating Adversarially Robust Model Selection for Deep Neural Networks via Racing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i19.30121},
}
Figure