Expressive Losses for Verified Robustness via Convex Combinations

Alessandro De Palma, Rudy Bunel, Krishnamurthy Dvijotham, M. Pawan Kumar, Robert Stanforth, Alessio Lomuscio

TL;DR

Training neural networks to be "provably" robust usually involves a painful trade-off: you gain formal guarantees at the cost of significant standard accuracy. This paper shows that simple convex combinations of adversarial and verified losses—which the authors call "expressive losses"—can outperform complex state-of-the-art methods by simply providing a tunable way to navigate the robustness-accuracy frontier.

What Problem Does This Paper Address?

Deep learning models are notoriously fragile, susceptible to tiny, human-imperceptible adversarial perturbations. While "adversarial training" (training against attacks) makes models empirically robust, it offers no formal guarantees. On the other hand, "verified training" uses mathematical over-approximations (like Interval Bound Propagation, or IBP) to guarantee robustness within a certain radius.

The catch? Verified training is notoriously difficult. The loose bounds used during training often lead to models with poor standard accuracy. Recent research has tried to bridge this gap with complex heuristics that couple adversarial attacks with over-approximations. The authors of this paper ask a fundamental question: Is the complexity of these state-of-the-art (SOTA) methods actually necessary, or is there a simpler underlying principle at play?

Methods

The authors introduce the concept of Expressive Losses. A loss function is "expressive" if it can span the entire range between a standard adversarial loss (empirical) and a verified loss (provable) using a single tuning parameter, $\alpha \in [0, 1]$.

They propose three minimalistic ways to build these losses using convex combinations:

  1. CC-IBP (Convex Combination): Combines the logit differences of an adversarial attack and the IBP lower bounds inside the loss function.
  2. MTL-IBP (Multi-Task Learning): A simple weighted sum of the adversarial loss and the verified loss.
  3. Exp-IBP (Exponential): A convex combination performed between the logarithms of the losses, effectively creating a geometric mean.

While these methods are conceptually simpler than recent SOTA techniques like SABR (which computes bounds over small "boxes" around adversarial points), they all satisfy the definition of expressivity.

Datasets

The researchers evaluated their expressive losses on standard robust vision benchmarks:

  • MNIST: The classic digit recognition task.
  • CIFAR-10: A standard object recognition dataset.
  • TinyImageNet: A subset of ImageNet with 200 classes at 64x64 resolution.
  • ImageNet64: A downscaled (64x64) version of the full ImageNet dataset.

Key Insights and Ideas

  • Expressivity > Complexity: The most striking finding is that these simple convex combinations match or beat much more complex SOTA methods. This suggests that the ability to finely tune the trade-off via $\alpha$ is more important than the specific geometric heuristic used to combine attacks and bounds.
  • The Approximation Paradox: Common wisdom suggests that tighter approximations of the "worst-case loss" should lead to better models. The authors show this isn't always true. In some cases, better mathematical approximations of the worst-case loss actually led to worse performance profiles.
  • Tuning is Everything: The sensitivity of these models to the $\alpha$ parameter is high. Finding the "sweet spot" for $\alpha$ allows practitioners to maximize verifiability for a specific verification budget while preserving as much standard accuracy as possible.
Figure 1: Sensitivity of CC-IBP, MTL-IBP and Exp-IBP to the convex combination coefficient α. We report standard, adversarial and verified robust accuracies (with different verifiers) under ℓ∞perturbations on the first 1000 images of the CIFAR-10 test set. The legend in plot 1(b) applies to all sub-figures.

Key Results

The simple expressive losses achieved new SOTA results, particularly on larger and more challenging datasets:

  • TinyImageNet: They increased standard accuracy by at least 8.58% and verified robust accuracy by 3.93% over previous best results.
  • ImageNet64: They saw improvements of at least 3.39% in standard accuracy and 2.33% in verified robust accuracy.
  • CIFAR-10: The methods remained competitive with or superior to existing ReLU-based architectures across different perturbation radii ($\epsilon$).
Table 1: Comparison of the expressive losses from §4 with literature results for ℓ∞norm perturbations on CIFAR-10, TinyImageNet and downscaled (64 × 64) ImageNet. The entries corresponding to the best standard or verified robust accuracy for each perturbation radius are highlighted in bold. For the remaining entries, improvements on the literature performance of the best-performing ReLU-based architectures are underlined.

Limitations and Future Work

  • Hyperparameter Sensitivity: The $\alpha$ parameter is powerful but requires careful tuning. The paper notes that Exp-IBP, in particular, is extremely sensitive to the choice of $\alpha$.
  • Verification Bottleneck: While these training methods are efficient, the "complete verification" (BaB) used to evaluate them remains computationally expensive, especially as we scale to larger models like VGG or ResNet.
  • Beyond Vision: The study focuses entirely on image classification. Exploring how expressive losses perform in other domains like Natural Language Processing or control systems remains an open area for research.

Summary updated

Abstract

In order to train networks for verified adversarial robustness, it is common to over-approximate the worst-case loss over perturbation regions, resulting in networks that attain verifiability at the expense of standard performance. As shown in recent work, better trade-offs between accuracy and robustness can be obtained by carefully coupling adversarial training with over-approximations. We hypothesize that the expressivity of a loss function, which we formalize as the ability to span a range of trade-offs between lower and upper bounds to the worst-case loss through a single parameter (the over-approximation coefficient), is key to attaining state-of-the-art performance. To support our hypothesis, we show that trivial expressive losses, obtained via convex combinations between adversarial attacks and IBP bounds, yield state-of-the-art results across a variety of settings in spite of their conceptual simplicity. We provide a detailed analysis of the relationship between the over-approximation coefficient and performance profiles across different expressive losses, showing that, while expressivity is essential, better approximations of the worst-case loss are not necessarily linked to superior robustness-accuracy trade-offs.
BibTeX
@inproceedings{palma2024expressive,
  author = {Alessandro De Palma and Rudy Bunel and Krishnamurthy Dvijotham and M. Pawan Kumar and Robert Stanforth and Alessio Lomuscio},
  title = {{Expressive Losses for Verified Robustness via Convex Combinations}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=mzyZ4wzKlM},
}
Figure