  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.
