Provable Robustness of ReLU networks via Maximization of Linear Regions

Francesco Croce, Maksym Andriushchenko, Matthias Hein

Abstract

Neural network classifiers are notoriously susceptible to adversarial perturbations, raising significant safety concerns. We propose a regularization scheme for ReLU networks that provably improves robustness by maximizing the linear regions of the classifier and the distance to the decision boundary. Our approach, the Maximum Margin Regularizer (MMR), facilitates the calculation of minimal adversarial perturbations for a large fraction of test points, even in large networks. Experimental results demonstrate that MMR improves upon adversarial training in both lower and upper robustness bounds while maintaining competitive test error.

Introduction

Deep neural networks are fragile; imperceptible input changes can flip predictions. While empirical defenses exist, they are often bypassed by stronger attacks. This necessitates provable robustness—mathematical guarantees that no perturbation within a specific radius can alter the model's output. However, verifying ReLU networks is computationally expensive because they partition the input space into a complex patchwork of numerous small "linear regions" (polytopes). The combinatorial complexity of these regions makes verification an NP-hard problem. We bridge this gap by training models to be inherently "verifiable" through geometric regularization.

Methodology: Maximum Margin Regularizer (MMR)

ReLU networks are piecewise affine, behaving linearly within specific polytopes. For any input $x$, we define two critical geometric distances:

  1. $d_D(x)$: The distance to the nearest decision boundary (where the class would change).
  2. $d_B(x)$: The distance to the boundary of the current linear region (the edge of the polytope).
Geometric distances $d_D$ (to decision boundary) and $d_B$ (to region boundary) within a linear region.

If the decision boundary is closer than the region boundary ($d_D \le d_B$), the robustness of the network at that point is exactly $d_D$. If not, $d_B$ serves as a guaranteed lower bound. Our Maximum Margin Regularizer (MMR) penalizes the model if either $d_D$ or $d_B$ is too small, effectively "stretching" linear regions around training data and pushing decision boundaries further away. We also evaluate MMR+at, which integrates this geometric regularization with standard adversarial training.

Experimental Evaluation

We evaluated MMR on four standard benchmarks: MNIST, Fashion-MNIST (F-MNIST), German Traffic Signs (GTS), and CIFAR-10.

Maximization of Linear Regions

The primary effect of MMR is a drastic simplification of the model's decision space. By reducing the number of linear regions and increasing their size, the combinatorial complexity for verification tools (like Mixed Integer Programming) is significantly reduced.

Comparison of linear regions in original vs. regularized models. Regularization significantly reduces the number of regions and increases their size.

Key Results

  • Superior Provable Robustness: MMR+at achieved state-of-the-art lower bounds on robust error on MNIST and F-MNIST, often maintaining better clean accuracy than competing methods like the "KW" approach.
  • Massive Verification Speedup: On MNIST, verification time using Mixed Integer Programming (MIP) dropped from nearly 2,000 minutes for a standard model to under 100 minutes for an MMR-regularized model—a 20x speedup.
  • Exact Certificates: For over 98% of test points in fully connected networks on the GTS dataset, the MMR-trained models allowed the calculation of the globally optimal adversarial perturbation.
  • Gradient Interpretability: MMR-trained models exhibit sparser, more salient gradients, focusing on relevant object features rather than background noise.

Conclusion and Future Work

MMR successfully aligns training objectives with verifiability. By maximizing linear regions, we achieve models that are both robust and computationally easier to certify. While there is a slight trade-off between clean accuracy and robustness, particularly on complex datasets like CIFAR-10, the gains in provable security and verification efficiency are substantial. Future work will focus on scaling these geometric calculations to deeper architectures and optimizing solvers for the large-region polytopes produced by MMR.

Summary updated

Abstract

It has been shown that neural network classifiers are not robust. This raises concerns about their usage in safety-critical systems. We propose in this paper a regularization scheme for ReLU networks which provably improves the robustness of the classifier by maximizing the linear regions of the classifier as well as the distance to the decision boundary. Our techniques allow even to find the minimal adversarial perturbation for a fraction of test points for large networks. In the experiments we show that our approach improves upon adversarial training both in terms of lower and upper bounds on the robustness and is comparable or better than the state-of-the-art in terms of test error and robustness.
BibTeX
@inproceedings{croce2019provable,
  author = {Francesco Croce and Maksym Andriushchenko and Matthias Hein},
  title = {{Provable Robustness of ReLU networks via Maximization of Linear Regions}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=25J0lD-_o6Wb},
}
Figure