On Certifying Non-uniform Bound against Adversarial Attacks

Chen Liu, Ryota Tomioka, Volkan CevherarXiv 2019 · arXiv

Abstract

Traditional certified robustness for neural networks relies on uniform perturbation bounds, which often fail to capture the varying sensitivity of individual input features. This paper introduces a framework for certifying non-uniform bounds by maximizing the volume of the certified neighborhood. By assigning per-feature budgets, the authors demonstrate that robust models achieve significantly larger certified regions and exhibit highly interpretable "bounding maps" that highlight task-relevant features. Experimental results across multiple datasets show that non-uniform bounds provide a more accurate and insightful measure of model stability compared to standard uniform approaches.

Introduction

Deep neural networks are notoriously fragile; tiny, imperceptible changes to an input can flip a model's prediction. To combat this, researchers developed certified robustness, which mathematically guarantees that a model's output won't change within a certain "neighborhood" around a data point.

Traditionally, these neighborhoods are uniform—think of a perfect sphere or a cube where every dimension has the same radius. However, real-world data isn't uniform. Some pixels in an image might be critical to a classification, while others (like background noise) are irrelevant. By forcing a uniform bound, existing methods often "under-certify" the model, finding a small safe zone that fits the most sensitive feature while ignoring the fact that other features could tolerate much larger changes.

A 2D visualization showing that non-uniform bounds (cyan) can cover significantly more area than uniform bounds (yellow) while staying within the decision boundaries (black).

Methodology

The authors propose a framework to find the largest non-uniform neighborhood $S$ around a data point $\mathbf{x}$ such that the model's prediction remains constant.

Optimization Framework

The problem is defined as maximizing the volume of the neighborhood (the product of per-feature budgets $\epsilon_j$) subject to the constraint that the "true" label's logit remains higher than all others.

Hybrid Bound Estimation

To handle the non-linearities of neural networks, the authors combine two techniques:

  • Simple Algorithm: A fast, layer-wise interval propagation.
  • Quadratic Algorithm: A more precise method using linear relaxations (similar to the CROWN algorithm) that captures dependencies between layers.

Combining these ensures the tightest possible bound in each layer. The resulting constrained optimization problem is solved using the Augmented Lagrangian Method, which provides greater stability than simple penalty methods for enforcing hard constraints.

Experimental Results

The researchers evaluated their approach on synthetic 2D data, MNIST, Fashion-MNIST, and SVHN.

Larger Certified Volumes

Non-uniform bounds consistently certified larger regions than uniform ones. The ratio of non-uniform to uniform average bounds ranged from 1.05x to over 5.2x. This advantage was much more pronounced in models trained with adversarial defense (e.g., PGD training). For example, on SVHN, the ratio reached 5.204 for a robust model.

Interpretability via Bounding Maps

By visualizing the per-pixel budget $\epsilon$ as an image (a "bounding map"), the authors found that for robust models, these maps clearly highlight the shape of the object. For a digit '1', the map shows a clear vertical stroke where the model is most sensitive, effectively "masking" the background. In contrast, normal models produce maps that appear as random noise.

Bounding maps for the digit '1'. The robust model (right) produces a map that clearly captures the intrinsic shape of the digit, while the normal model (middle) produces a noisy, uninterpretable map.

Key Insights

  • The "Long Tail" of Robustness: In robust models, the distribution of per-feature bounds has a long tail. A few features are very sensitive, but many others can be changed significantly without affecting the output.
  • Robustness = Simplicity: Robust models tend to rely on fewer, more meaningful features. The non-uniform bounds for these models are much larger because the model has "learned" to ignore the dimensions that don't matter for the task.
  • Geometric Similarity: The direction of the $\epsilon$ vector is highly consistent across different images for the same model, suggesting that the shape of the non-uniform bound is a data-agnostic property of the model's decision boundary.

Discussion and Limitations

While the proposed method offers significant advantages in certification and interpretability, it faces some challenges:

  • Computational Complexity: The quadratic part of the algorithm has $O(N^2 n^3)$ complexity, which can be slow for very large, deep networks.
  • Tightness of Bounds: Linear relaxation still introduces some looseness as the perturbation budget grows or the network depth increases.

Future work may explore "soft bounds" to speed up optimization and considering oblique bounds (using an orthogonal matrix to rotate the neighborhood) to better capture correlations between different input features.

Conclusion

Shifting from uniform to non-uniform bounds provides a more nuanced and powerful tool for evaluating neural network robustness. Not only does it certify larger safe regions, but it also provides a novel lens for model interpretability, revealing how robust models prioritize essential features while ignoring noise.

Summary updated

Abstract

This work studies the robustness certification problem of neural network models, which aims to find certified adversary-free regions as large as possible around data points. In contrast to the existing approaches that seek regions bounded uniformly along all input features, we consider non-uniform bounds and use it to study the decision boundary of neural network models. We formulate our target as an optimization problem with nonlinear constraints. Then, a framework applicable for general feedforward neural networks is proposed to bound the output logits so that the relaxed problem can be solved by the augmented Lagrangian method. Our experiments show the non-uniform bounds have larger volumes than uniform ones and the geometric similarity of the non-uniform bounds gives a quantitative, data-agnostic metric of input features' robustness. Further, compared with normal models, the robust models have even larger non-uniform bounds and better interpretability.
BibTeX
@misc{liu2019certifying,
  author = {Chen Liu and Ryota Tomioka and Volkan Cevher},
  title = {{On Certifying Non-uniform Bound against Adversarial Attacks}},
  year = {2019},
  eprint = {1903.06603},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.06603},
}
Figure