On Certifying Non-Uniform Bounds against Adversarial Attacks

Chen Liu, Ryota Tomioka, Volkan Cevher

Deep neural networks are notoriously fragile; small, calculated tweaks to an input—known as adversarial attacks—can easily flip a model's prediction. To counter this, researchers develop "certified defenses" that mathematically guarantee a model's output will remain constant within a certain neighborhood around a data point.

However, most existing methods assume uniform bounds, treating every pixel or feature as equally sensitive (e.g., using an $\ell_\infty$ or $\ell_2$ ball). This is a significant simplification. In reality, a model might be highly sensitive to changes in a specific pixel but robust to large changes in another. By forcing a uniform "safety bubble," we likely underestimate the true volume of the safe region and miss crucial insights into how the model actually processes the data.

This paper moves beyond "one-size-fits-all" robustness by proposing a framework to certify non-uniform adversarial bounds. By allowing different input features to have different perturbation budgets, the authors find larger safe regions around data points and reveal that robust models naturally prioritize certain features, leading to better interpretability.

Methodology

The authors formulate the search for the largest non-uniform neighborhood as a constrained optimization problem.

Instead of a single scalar budget $\epsilon$, they utilize a vector $\epsilon \in \mathbb{R}^{n_1}$, where each component represents the allowed perturbation for a specific feature. To estimate these bounds, they propose a hybrid approach for bounding the output logits of a feedforward network. This combines a fast but loose "Simple algorithm" (interval bound propagation) with a tighter but slower "Quadratic algorithm" (similar to CROWN, using linear relaxations of activation functions).

To find the largest volume—effectively minimizing the negative log of the product of $\epsilon_j$—they solve the optimization problem using the Augmented Lagrangian Method. This handles the non-linear constraints imposed by the neural network's architecture while iteratively updating the perturbation budget $\epsilon$.

The framework was evaluated across several datasets, including Synthetic 2D Data, MNIST, Fashion-MNIST, and SVHN (Street View House Numbers).

Key Insights and Results

Moving from uniform to non-uniform bounds yields several critical insights into model behavior and robustness.

Volume Gains: Non-uniform bounds consistently certify much larger volumes than uniform ones. By "stretching" the bound in robust directions and "shrinking" it in sensitive ones, the algorithm finds a more accurate representation of the model's safety zone.

2D visualization of non-uniform vs. uniform bounds

The ratio of improvement is significant. For a robust MNIST model, the non-uniform bound was 2.77x larger than the uniform equivalent. For SVHN, the ratio reached as high as 5.20x. Robust models not only have higher accuracy under attack but also possess significantly larger non-uniform certified regions compared to standard models.

Bounding Maps as Interpretability Tools: By visualizing the $\epsilon$ vector as an image (a "bounding map"), the authors demonstrate that robust models (trained via PGD) focus on the actual structure of the object, such as the strokes of a digit. In contrast, standard models produce noisy bounding maps, suggesting they rely on irrelevant or brittle features.

Bounding maps comparing normal and robust models

Geometric Similarity and Simpler Boundaries: Interestingly, the "direction" of the $\epsilon$ vector is highly correlated across different images for the same model. For robust models, the mean cosine similarity between $\epsilon$ vectors of different test images was remarkably high (e.g., 0.9964 for a robust MNIST model). This suggests that feature robustness is a property of the model itself, providing a data-agnostic metric for which features a model considers important. Furthermore, robust models exhibit even higher correlation in their $\epsilon$ directions than normal models, implying their decision boundaries are geometrically simpler and exist in a lower-dimensional subspace.

Limitations and Future Work

While promising, the approach has limitations:

  • Computational Complexity: The "Quadratic" algorithm used for tight bounds has an $O(N^2n^3)$ computational complexity (where $n$ is the number of neurons), making it difficult to scale to very deep or wide architectures like large ResNets.
  • Element-wise Independence: The current method assumes neurons in intermediate layers are bounded element-wise. Considering joint bounds for neurons in a layer could lead to even tighter results.
  • Oblique Bounds: The paper suggests moving from axis-aligned rectangles to "oblique bounds" (using a transformation matrix $A$ instead of just a vector $\epsilon$) to better capture correlations between input features. This represents a mathematically complex but exciting future direction.

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 exis...
BibTeX
@inproceedings{liu2019certifying,
  author = {Chen Liu and Ryota Tomioka and Volkan Cevher},
  title = {{On Certifying Non-Uniform Bounds against Adversarial Attacks}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
}
Figure