PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Robustness of ReLU networks via Maximization of Linear Regions

Francesco Croce, Maksym Andriushchenko, Matthias Hein

arXiv:1810.07481v2cs.LGstat.ML

TL;DR

Neural networks can be highly non-robust, creating concerns for safety-critical use and motivating certifiable robustness. The paper regularizes ReLU networks by enlarging linear regions and distances to decision boundaries, obtaining provable guarantees and globally minimal perturbations in some cases. Experiments show competitive or improved robustness and test-error performance, with certification depending on evaluation method and l2 MIP evaluation often timing out.

  • Problem

    Neural networks can change decisions under small input perturbations, while existing defenses often lack robustness guarantees needed for safety-critical applications.

  • Method

    The paper regularizes ReLU networks by maximizing distances to linear-region boundaries and decision boundaries, using piecewise-affine geometry to derive robustness guarantees.

  • Results

    The method improves provable robustness, matches state-of-the-art certified robust test error, and finds globally minimal adversarial perturbations for a significant fraction of cases in large fully connected networks.

  • Takeaways & Limitations

    Linear-region maximization yields models that can be certified by current state-of-the-art methods while retaining good test error and integrating with adversarial training.

  • Takeaways & Limitations

    For l2 evaluation, the MIP method usually reaches its timeout, so those MIP results are discarded.

Abstract

from arXiv · show

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.

1 Introduction

Neural networks can change decisions under nearly imperceptible input changes, undermining safety-critical use and motivating robustness guarantees. The paper proposes a ReLU-network regularizer that maximizes linear-region size and decision-boundary distance to improve provable robustness.

  • Motivation: Small, nearly imperceptible image changes can cause highly confident misclassifications, raising concerns for safety-critical neural-network applications.The issue also complicates interpreting classifier decisions when small input changes produce different outputs.
  • Motivation: Existing attacks and defenses have advanced together, but many proposed defenses remain successfully attackable.The paper identifies an empirically robust exception under the l∞ norm while emphasizing the need for guarantees.
  • Motivation: Robustness guarantees should provide a certified radius around each test point within which the classifier’s decision is unchanged.The paper contrasts such guarantees with methods that only encourage large margins without directly optimizing a robustness certificate.
  • Contribution: The proposed regularization scheme targets ReLU networks, including convolutional and residual architectures with max- or sum-pooling layers.It exploits the continuous piecewise-affine structure of these networks.
  • Contribution: The method derives optimal minimal perturbations or lower bounds from the containing linear region and directly maximizes the resulting robustness lower bound.Experiments on four datasets report improved lower and upper bounds on robust test error, while preserving good test error and supporting adversarial-training integration.

2 Local properties of ReLU networks

Piecewise-affine networks partition input space into polytopes where the classifier is affine. For ReLU networks, these regions and their class-specific subsets can be characterized from activation patterns and network parameters.

  • Piecewise-affine structure: Networks with piecewise-affine activations and a linear output layer can be represented as continuous piecewise-affine functions.ReLU and leaky-ReLU feedforward networks are included in this formulation.
  • Piecewise-affine structure: A piecewise-affine function is affine on each member of a finite polytope partition of the input space.The polytopes cover the domain, and the restriction of the function to every polytope is affine.
  • Classifier geometry: A ReLU classifier assigns each input the class with the largest output component, while linear regions and decision boundaries remain distinct geometric objects.This distinction allows linear regions to be shared across classifier components.
  • Network representation: ReLU activation is σ(t)=max{0,t}, and the network recursively computes layerwise pre- and post-activation outputs before a final affine output layer.The final classifier is f^(L+1)(x)=W^(L+1)g^(L)(x)+b^(L+1).
  • Local affine form: Activation-status diagonal matrices determine the affine restriction f^(k)(x)=V^(k)x+a^(k) within the region containing x.A forward pass computes the effective affine parameters with only small overhead relative to evaluating the network.
  • Local affine form: The local region Q(x) is characterized by linear inequalities induced by hidden-unit activation patterns, and its class-specific subset Q_c(x) is also a polytope.The construction extends to max-pooling, residual, dense, and other piecewise-linear architectures.

3 Robustness guarantees for ReLU networks

The paper compares the distance from an input to its linear-region boundary with the distance to the classifier’s decision boundary. The smaller distance yields either a robustness lower bound or the exact minimal adversarial perturbation.

  • Problem formulation: The minimal adversarial perturbation is the smallest constrained input change that alters the classifier’s decision.The general optimization is typically non-convex, and standard neural networks often have very small perturbation norms.
  • Problem formulation: For linear classifiers, the minimal perturbation can be computed in closed form, motivating analogous guarantees for ReLU networks within each linear region.The approach applies under norm constraints and can incorporate box constraints such as image values in [0,1]^d.
  • Geometric quantities: The distance d_B(x) measures the input’s l_p distance to the boundary of its containing polytope Q(x).This distance determines how far the classifier remains in the same affine region around x.
  • Geometric quantities: The distance d_D(x) measures the distance to candidate decision hyperplanes of the affine classifier restricted to Q(x), using the dual norm for hyperplane distance.The closest relevant decision and region-boundary hyperplanes can be selected efficiently.
  • Guarantees: The two cases have a direct geometric interpretation: the nearer polytope boundary gives a certificate, while the nearer decision boundary gives the optimal adversarial perturbation.These guarantees apply pointwise, and neighboring regions can further improve lower bounds.
  • Guarantees: If d_B(x)≤d_D(x), d_B(x) is a lower bound on the perturbation needed to change class; if d_D(x)≤d_B(x), d_D(x) is the exact minimum.The first case certifies an unchanged decision throughout B_p(x,d_B(x)); the second keeps the closest decision-boundary point inside Q(x).

4 Large margin and region boundary regularization

The paper regularizes ReLU classifiers by increasing both the distance to linear-region boundaries and the distance to decision boundaries. This yields non-trivial robustness guarantees, while MMR also increases the size of the classifier’s linear regions.

  • Design motivation: Robustness guarantees require large distances to both linear-region boundaries and decision boundaries, rather than only maximizing decision-boundary distance.The method targets both geometric quantities because decision-boundary distance alone may not provide good lower bounds.
  • Signed margin: MMR introduces a signed decision-boundary distance so correctly and wrongly classified points are treated differently during regularization.The signed distance is nonnegative for correctly classified points and negative for wrongly classified points; wrongly classified points are always penalized.
  • MMR regularizer: MMR penalizes points near the polytope boundary and correctly classified points with insufficient decision-boundary distance, using thresholds γB and γD.The regularizer also penalizes wrongly classified points, and its decision-boundary component is motivated by robustness geometry.
  • Certification implications: The regularization also moves multiple nearby hyperplanes, which can speed training and support lower-bound certification methods requiring stable activation statuses.The scheme optimizes the kD-closest decision boundaries and kB-closest region-boundary hyperplanes rather than only the closest ones.
  • Training objective: The regularization objective combines cross-entropy with λ-weighted MMR, applying the regularizer across training points.The objective uses the training data and a nonnegative regularization parameter λ.
  • Empirical effect: MMR significantly increases linear-region size compared with an unregularized model in the illustrated networks.Figure 2 compares one-hidden-layer networks on a two-class toy dataset and on a two-dimensional slice of MNIST input space.

5 Experiments

Experiments evaluate MMR across four datasets, two perturbation norms, multiple training schemes, and verification procedures. MMR improves provable robustness and verifiability, while sometimes yielding globally optimal perturbations and exposing overestimation by attack-based evaluation.

  • Experimental setup: Experiments compare plain, adversarial, KW, Xiao et al, MMR, and MMR+at training across MNIST, GTS, Fashion MNIST, and CIFAR-10.Evaluations use fully connected and convolutional architectures, with robustness measured for l2 and l∞ distances.
  • Evaluation scope: MIP evaluation is effective for l∞ but generally reaches its timeout for l2, so l2 MIP results are discarded.The reported robustness bounds combine PGD, MIP, and other attack or certification procedures depending on the norm.
  • Verifiability: 51 times more verification time is required for the plain model than for MMR-trained models, while only 1% of plain-model points are certified.MMR models are verified in 35–79 minutes with 99.3%–100% of points certified; increasing λ improves certification statistics up to λ = 2, but λ = 3 worsens runtime and robustness.
  • Main robustness results: MMR and MMR+at generally outperform plain and adversarial training in provable robustness, with MMR+at often preserving better clean test error than KW for l∞.For l2, KW generally performs better than MMR+at except on GTS, while MMR-based methods frequently produce tight lower and upper bounds.
  • Further experiments: Around 10% of Fashion MNIST points and over 98% of GTS points yield globally optimal l2 perturbations for fully connected MMR models.These optimal solutions have approximately 7% larger l2-norm on Fashion MNIST and 0.5% larger on GTS than the compared lower bounds.
  • Further experiments: 18.5% of GTS test points have CW perturbation norms at least 10% larger than optimal, while 9.1% are at least 20% larger.The maximum relative difference is 235%; MMR computes lower bounds and optimal solutions in 1701s versus 16327s for CW on the evaluated setting.

6 Conclusion

The paper introduces MMR, a geometrically motivated regularizer that produces provably robust models and can find globally minimal adversarial perturbations for a significant fraction of cases.

  • The full MMR regularizer significantly improves lower bounds over penalizing only distance to the decision boundary.
  • MMR produces models provably robust under current state-of-the-art certification methods.
  • MMR performs as well as state-of-the-art models in certified robust test error and better or similarly to the compared alternative.
  • MMR obtains guaranteed globally minimal adversarial perturbations for a significant fraction of points in large fully connected networks.

A.1 Integration of box constraints into robustness guarantees

The robustness computation incorporates input-box constraints into distances to hyperplanes and efficiently searches constrained and neighboring linear regions for tighter guarantees.

  • Input constraints such as x ∈ [0, 1]^d can increase the minimal perturbation and must be included in lower-bound computation.
  • The box-constrained distance problem is convex, and its one-dimensional dual can be solved efficiently.
  • The method sorts unconstrained hyperplane distances, then solves only the necessary box-constrained problems until the ordering certifies the stopping condition.
  • 20%: integrating box constraints improves lower bounds on average by this amount.
  • Neighboring regions are checked by changing the relevant activation-matrix entry and recomputing the region hyperplanes when the lower and upper bounds leave a gap.

B.1 Experimental details

Experiments use fully connected and convolutional networks trained with specified learning-rate schedules, MMR settings, adversarial training, and robustness-evaluation attacks.

  • FC1 has one hidden layer with 1024 units, while FC10 has ten hidden layers totaling 1024 units.
  • MMR training decreases kB from 10% to 2% of hidden units and increases λ from λ/10 to λ during the first 10 epochs.
  • Hyperparameters λ, γB, and γD are selected by grid search for each dataset and architecture.
  • Adversarial training uses PGD with batches containing 50% clean and 50% adversarial examples.
  • Evaluation uses PGD, the untargeted Carlini-Wagner l2 attack, and mixed-integer programming with a 5-second timeout.

C Further experiments

Further experiments show that MMR improves robustness bounds over plain and adversarial training, with especially strong gains for fully connected networks, while CNN gains are smaller.

  • Comparison to Cross-Lipschitz regularization: 5.2% and 6.4%: KW and MMR+at provide better upper bounds on robust error than Cross-Lipschitz regularization’s 7.2% bound.
  • Analysing l2-robustness with different metrics: Adversarial training often improves upper bounds but rarely improves lower bounds, whereas MMR significantly improves lower bounds over plain and adversarial training.
  • Analysing l2-robustness with different metrics: For FC1 and FC10 on GTS and F-MNIST, MMR or MMR+at lower bounds exceed plain-training upper bounds.
  • Analysing l2-robustness with different metrics: MMR is provably more robust than competing methods in the reported GTS configurations and generally improves upper bounds over adversarial training.
  • Analysing l2-robustness with different metrics: For CNNs, KW and MMR improve lower and upper bounds less than they do for fully connected networks.

D Visualizing the structure of provably robust models

Robust training produces sparser, more interpretable gradients and convolutional filters than plain training across MNIST, GTS, and CIFAR-10, with MMR often emphasizing salient image content.

  • Convolutional filters: The filter visualizations compare plain, adversarial, KW, MMR, and MMR-plus-adversarial training across the first and second convolutional layers.Rows are independently rescaled, and filter intensity represents distance from zero weights.
  • Gradient structure: Robust training schemes produce interpretable, sparse gradients, whereas plain-training gradients do not consistently highlight relevant features.For MNIST and GTS, robust models reduce sensitivity to irrelevant directions or background variations.
  • Gradient structure: On GTS, robust models become less sensitive to background variations and highlight traffic signs more strongly.MMR and adversarially trained models have the most interpretable gradients in this comparison.
  • Convolutional filters: KW and MMR produce the sparsest convolutional filters, while MMR combined with adversarial training is less sparse and resembles adversarial training.This pattern appears for GTS and CIFAR-10, while MNIST visualizations also show especially sparse MMR and MMR+adversarial-training filters in the second layer.
  • Gradient structure: On CIFAR-10, robust gradients differ qualitatively from plain-model high-frequency noise, with MMR concentrating more on objects than backgrounds.The shallow CNNs nevertheless have relatively high clean test error, limiting how clearly interpretability appears.
Loading 1810.07481v2…