Certify or Predict: Boosting Certified Robustness with Compositional Architectures

Mark Niklas Müller, Mislav Balunovic, Martin T. VechevICLR 2021 · OpenReview

Introduction

The "ACE" (Architecture for Certification) framework bridges the gap between high-performance deep learning and mathematical safety guarantees. By using a compositional approach that routes inputs to either a high-accuracy "core" network or a provably robust "certification" network, ACE achieves record-breaking natural accuracy (e.g., 90.1% on CIFAR-10) while maintaining non-trivial certified robustness.

The Problem: The "Accuracy Tax"

In adversarial machine learning, practitioners face a frustrating "accuracy tax." You can deploy a state-of-the-art model (like EfficientNet) that is incredibly accurate but easily fooled by tiny, invisible perturbations. Alternatively, you can use certified defenses—methods that provide a mathematical guarantee that a model's prediction won't change within a certain "noise" radius.

The problem is that certified models usually suffer from abysmal "natural accuracy" on clean data. For many real-world applications, sacrificing 20-30% accuracy for a safety guarantee is a non-starter. This paper tackles the fundamental roadblock to the practical adoption of certified defenses: the severe trade-off between being right and being provably robust.

Methods: The ACE Architecture

The authors propose a novel compositional architecture called ACE (Architecture for Certification). Instead of trying to train one "super-network" that is both highly accurate and robust, they split the labor among three components:

  1. Core-Network ($h_t$): A standard, high-performance model optimized for natural accuracy.
  2. Certification-Network ($h_b$): A model trained specifically using certified defense techniques (like IBP or COLT). It doesn't need to be highly accurate on all data, just robust on the samples it handles.
  3. Selection Mechanism ($g$): The "gatekeeper" that decides which network should process a given input.
ACE Architecture Variants: SelectionNet and Entropy ACE

The brilliance of ACE lies in how it handles this selection. To provide an end-to-end robustness guarantee, the selection mechanism itself must be certifiable. The authors propose two ways to achieve this:

  • SelectionNet: An auxiliary binary classifier trained to predict whether the certification network can successfully certify a sample.
  • Entropy Selection: A method that thresholds the entropy of the certification network's output. If the robust network is "confused" (high entropy), the system defaults to the core network; if it is "certain" (low entropy), it uses the robust prediction.

To make the entropy-based selection certifiable, the authors developed new Zonotope Transformers for entropy functions, allowing them to propagate bounds through the complex math of log-sum-exp operations.

Key Insights

  • Divide and Conquer: A model doesn't have to be robust on every possible input to be useful. By identifying "easy" samples that can be certified and routing "hard" samples to a high-accuracy core, ACE shifts the Pareto front of the accuracy-robustness trade-off.
  • Certifying the Gatekeeper: The bottleneck for compositional robustness isn't the networks themselves, but the robustness of the routing decision. If an attacker can flip the "gate" from the robust network to the core network, the guarantee vanishes.
  • Resolution Independence: Because the architecture is compositional, the core network can run on high-resolution images (improving accuracy) while the certification network runs on low-resolution versions (reducing the computational cost of certification).
  • Orthogonality: ACE is a "meta-architecture." It doesn't replace existing certified defenses; it wraps around them. As better robust training methods or better core architectures are developed, they can be plugged directly into ACE.

Key Results

The researchers evaluated ACE on standard computer vision benchmarks (CIFAR-10, TinyImageNet, and ImageNet200), demonstrating a significant leap over prior state-of-the-art (SOTA) certified models.

Certifiable vs. Natural Accuracy on CIFAR-10
  • CIFAR-10 ($\ell_\infty$ perturbation of 2/255): ACE achieved 90.1% natural accuracy with 27.5% certified robustness. For context, prior methods that achieved similar robustness levels typically saw natural accuracy drop into the 70s or low 80s.
  • CIFAR-10 ($\ell_\infty$ perturbation of 8/255): ACE reached 80.1% natural accuracy and 10.5% certified robustness.
  • ImageNet200: ACE demonstrated scaling to larger tasks, achieving 70.0% natural accuracy with a non-trivial 3.1% certified robustness at $\epsilon=1/255$.

Limitations and Future Work

While ACE represents a major step forward, it has a few limitations:

  • Conservative Guarantees: The current framework assumes that certification of the core network always fails. While safe, this is highly conservative. If the core network happens to be robust for a specific sample, ACE doesn't currently "know" how to prove it.
  • Computational Overhead: At inference time, the system may need to run multiple networks (the selector and one of the classifiers), which increases latency and memory usage.
  • The "Robustness Ceiling": The total certified robustness is ultimately limited by the performance of the certification network. If the robust network can only certify 30% of the data, the entire ACE system can never exceed 30% certified robustness.

Future work could involve training the core and certification networks jointly to further optimize the routing logic and push the boundaries of certified defenses even further.

Summary updated

Abstract

A core challenge with existing certified defense mechanisms is that while they improve certified robustness, they also tend to drastically decrease natural accuracy, making it difficult to use these methods in practice. In this work, we propose a new architecture which addresses this challenge and enables one to boost the certified robustness of any state-of-the-art deep network, while controlling the overall accuracy loss, without requiring retraining. The key idea is to combine this model with a (smaller) certified network where at inference time, an adaptive selection mechanism decides on the network to process the input sample. The approach is compositional: one can combine any pair of state-of-the-art (e.g., EfficientNet or ResNet) and certified networks, without restriction. The resulting architecture enables much higher natural accuracy than previously possible with certified defenses alone, while substantially boosting the certified robustness of deep networks. We demonstrate the effectiveness of this adaptive approach on a variety of datasets and architectures. For instance, on CIFAR-10 with an $\ell_\infty$ perturbation of 2/255, we are the first to obtain a high natural accuracy (90.1%) with non-trivial certified robustness (27.5%). Notably, prior state-of-the-art methods incur a substantial drop in accuracy for a similar certified robustness.
BibTeX
@inproceedings{muller2021certify,
  author = {Mark Niklas Müller and Mislav Balunovic and Martin T. Vechev},
  title = {{Certify or Predict: Boosting Certified Robustness with Compositional Architectures}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=Sy9hgUi71K8},
}
Figure