Provable Robustness of ReLU networks via Maximization of Linear Regions

Francesco Croce, Maksym Andriushchenko, Matthias Hein

Abstract Neural network classifiers are known to be vulnerable to adversarial perturbations, posing significant risks for safety-critical applications. This paper introduces the Maximum Margin Regularizer (MMR), a novel training scheme for ReLU-based networks. MMR improves provable robustness by geometrically maximizing the distance from training data to both decision boundaries and the boundaries of the network's local linear regions. This approach creates large linear regions around data points, facilitating exact robustness calculations and significantly accelerating formal verification. Experimental results across MNIST, Fashion-MNIST, GTS, and CIFAR-10 demonstrate that MMR achieves superior provable bounds and better accuracy trade-offs compared to existing methods.

Introduction

The susceptibility of deep learning models to adversarial attacks—small, targeted input changes that cause misclassification—remains a major hurdle for their deployment in sensitive domains. While empirical defenses offer some protection, they lack the mathematical guarantees required for high-stakes environments. Provable robustness aims to provide such guarantees, ensuring that no perturbation within a defined $l_p$ ball can alter the model's output. However, existing provable methods often struggle with scalability or impose severe penalties on standard accuracy.

This work addresses these challenges by leveraging the geometric properties of ReLU networks. As continuous piecewise affine functions, ReLU networks partition the input space into convex polytopes called linear regions. By regularizing the geometry of these regions, we can create models that are inherently more robust and easier to verify.

Methodology

The core contribution is the Maximum Margin Regularizer (MMR). For a given input, MMR penalizes the model based on two geometric metrics:

  1. Distance to Decision Boundary ($d_D$): The minimum distance required to reach a point where the model's classification changes.
  2. Distance to Region Boundary ($d_B$): The minimum distance to the nearest "seam" of the ReLU activations, where the local linear behavior changes.
Geometric illustration of the distance to the decision boundary ($d_D$, red) and the distance to the nearest linear region boundary ($d_B$, black).

By maximizing these distances, the network is encouraged to have large, flat regions around data points. A critical theoretical insight of this work is that when $d_D \le d_B$, the minimal adversarial perturbation can be calculated exactly. This transforms a typically NP-hard problem into a tractable one for a large portion of the input space.

Experimental Results

The effectiveness of MMR was evaluated on four computer vision benchmarks: MNIST, Fashion-MNIST, German Traffic Signs (GTS), and CIFAR-10.

The impact of the regularizer is visually striking. As shown below, the regularized model exhibits a significantly simplified internal geometry. The number of linear regions is reduced, and the decision boundaries are pushed further away from the data clusters, creating a wider margin of safety.

Visual comparison of original vs. regularized models. Panels (a) and (b) show decision boundaries relative to data clusters. Panels (c) and (d) illustrate the simplification of linear region boundaries under MMR.

Key findings include:

  • Enhanced Provable Robustness: MMR consistently yields better lower and upper bounds on robust test error than standard adversarial training.
  • Verification Efficiency: MMR-trained models are optimized for formal verification. For example, on the MNIST dataset, a Mixed-Integer Programming (MIP) solver verified an MMR model in under 80 minutes with nearly 100% success, compared to nearly 2,000 minutes and 1% success for a standard model.
  • Balanced Performance: Unlike many certified defense methods that drastically reduce standard accuracy, MMR maintains competitive performance on "clean" data while providing significantly higher robust guarantees.

Conclusion

The Maximum Margin Regularizer offers a principled way to build robust neural networks by directly optimizing their internal geometry. By maximizing the size of linear regions around data, MMR provides a path toward models that are not only more resistant to attacks but also fundamentally easier to verify. Future research will focus on extending these geometric principles to non-ReLU architectures and scaling the approach to larger datasets like ImageNet.

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 networ...
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