PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Stable and Efficient Training of Verifiably Robust Neural Networks

Huan Zhang, Hongge Chen, Chaowei Xiao, Sven Gowal, Robert Stanforth, Bo Li, Duane Boning, Cho-Jui Hsieh

arXiv:1906.06316v2cs.LGcs.CRstat.ML

TL;DR

Training verifiably robust neural networks requires bounds that are both computationally manageable and sufficiently tight for stable optimization. The paper proposes CROWN-IBP, combining IBP forward bounds with CROWN backward bounds, and reports consistent improvements over IBP baselines and state-of-the-art verified errors for ℓ∞ robustness.

  • Problem

    Linear-relaxation bounds can increase training time by hundreds of times, while IBP is efficient but unstable because its bounds are initially loose.

    Source: §1 · p. 2, §3.1 · p. 5

  • Method

    CROWN-IBP combines an IBP-based forward bounding pass with a tight CROWN-style backward bounding pass inside certified adversarial training.

    Source: §1 · p. 2, §3.2 · pp. 5, 7

  • Results

    CROWN-IBP consistently outperforms IBP baselines and achieves state-of-the-art verified test errors for ℓ∞ robustness on MNIST and CIFAR-10.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    CROWN-IBP provides an efficient and flexible certified-defense approach that can trade off standard and verified accuracy through training settings.

    Source: §4 · p. 8, §5 · p. 9

    Pure IBP training can diverge or require an ϵ schedule and mixed loss to stabilize optimization, motivating CROWN-IBP's design.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Training neural networks with verifiable robustness guarantees is challenging. Several existing approaches utilize linear relaxation based neural network output bounds under perturbation, but they can slow down training by a factor of hundreds depending on the underlying network architectures. Meanwhile, interval bound propagation (IBP) based training is efficient and significantly outperforms linear relaxation based methods on many tasks, yet it may suffer from stability issues since the bounds are much looser especially at the beginning of training. In this paper, we propose a new certified adversarial training method, CROWN-IBP, by combining the fast IBP bounds in a forward bounding pass and a tight linear relaxation based bound, CROWN, in a backward bounding pass. CROWN-IBP is computationally efficient and consistently outperforms IBP baselines on training verifiably robust neural networks. We conduct large scale experiments on MNIST and CIFAR datasets, and outperform all previous linear relaxation and bound propagation based certified defenses in $\ell_\infty$ robustness. Notably, we achieve 7.02% verified test error on MNIST at $ε=0.3$, and 66.94% on CIFAR-10 with $ε=8/255$. Code is available at https://github.com/deepmind/interval-bound-propagation (TensorFlow) and https://github.com/huanzhang12/CROWN-IBP (PyTorch).

1 INTRODUCTION

Verifiable robustness training must balance computational cost, bound tightness, and training stability. CROWN-IBP combines efficient IBP forward bounds with tighter CROWN backward bounds and achieves strong verified robustness on MNIST and CIFAR-10.

  • Linear relaxation methods can increase training time by hundreds of times despite providing tractable robust-optimization bounds.These methods construct convex adversarial polytopes through linear relaxations of neural networks.Source: §1 · p. 2
  • IBP is efficient and achieves state-of-the-art verified error on many datasets, but its initially loose bounds can destabilize training and increase hyperparameter sensitivity.Source: §1 · p. 2
  • CROWN-IBP combines a fast IBP forward bounding pass with a tight CROWN convex-relaxation backward pass.The backward pass scales linearly with neural-network output size and is efficient for low-dimensional outputs.Source: §1 · p. 2
  • 7.02% IBP verified error is achieved on MNIST at ℓ∞ distortion ϵ = 0.3, compared with 8.55% for the IBP baseline.At ϵ = 0.4, the corresponding verified errors are 12.06% for CROWN-IBP and 15.01% for IBP.Source: §1 · p. 2
  • 46.03% verified error is achieved on CIFAR-10 at ϵ = 2/255, down from 55.88% with IBP, while larger ϵ values yield a noticeable advantage over other methods.Source: §1 · p. 2

2 RELATED WORK AND BACKGROUND

Robustness verification seeks tractable bounds on network outputs because exact ranges are computationally difficult. Certified adversarial training uses upper bounds of robust loss, while IBP and linear-relaxation approaches trade off scalability, tightness, and stability.

  • Exact neural-network output ranges are non-convex and NP-complete to compute, motivating relatively tight tractable bounds.Source: §2.1 · p. 2
  • PGD-based adversarial training does not provide verified error guarantees because PGD computes only a lower bound of the inner maximization.Failure to find a high-loss perturbation does not establish that no such perturbation exists.Source: §2.2 · p. 3
  • Certified adversarial training instead computes an upper bound of the inner maximum and updates model parameters using that bound.Minimizing this upper bound preserves the robust-optimization guarantee described in the paper.Source: §2.2 · p. 3
  • Linear-relaxation training provides upper bounds but is computationally expensive because convex adversarial-polytope propagation is costly.Source: §2.2 · p. 3
  • IBP scales to larger networks and can outperform prior results, but its loose initial bounds make training unstable and difficult to tune.Gowal et al. mitigate this instability with a mixture of regular and minimax robust cross-entropy loss.Source: §2.2 · p. 3

3 METHODOLOGY

CROWN-IBP combines efficient IBP propagation with tighter CROWN bounds to stabilize certified training while reducing the computational cost of linear-relaxation methods.

Verification framework

  • Certified robustness is evaluated through lower bounds on class margins over norm-bounded perturbation sets.If every lower-bounded margin is positive, the input is verifiably robust.Source: §3 · p. 4

IBP and linear relaxation

  • IBP is efficient and can perform well at large ε, but its loose initial bounds make training unstable and sensitive to hyperparameters.Pure IBP frequently diverges, motivating schedules and mixed natural and robust losses.Source: §3.1 · p. 5, §3.2 · p. 5
  • Linear-relaxation training can over-regularize networks at large ε by driving weight norms downward, potentially reducing capacity and increasing verified error.In the MNIST analysis, the second CNN-layer norm begins decreasing around ε = 0.2, approximately at epoch 40.Source: §3.1 · p. 5, §3.2 · p. 5

CROWN-IBP

  • CROWN-IBP uses an IBP forward pass for intermediate bounds and a CROWN backward pass for tighter output bounds.The backward pass propagates a small specification matrix using transposed operators and scales with output size.Source: §3.2 · pp. 5, 7
  • CROWN-IBP reduces bound-propagation complexity from O(Ln^2(Ln + nL)) to O(Ln^2nL), avoiding ordinary CROWN’s quadratic dependence on depth.The IBP forward pass takes twice regular forward-propagation time, while backward propagation is O((L −1)nLn^2).Source: §3.2 · p. 7

4 EXPERIMENTS

Experiments compare CROWN-IBP with IBP across datasets, perturbation settings, κ schedules, and model architectures. CROWN-IBP consistently improves verified performance and the standard–verified accuracy trade-off, while stability is evaluated across models and ramp-up schedules.

Comparison to IBP

  • 7.02% verified error replaces 8.21% for IBP on MNIST at ε = 0.3.Source: §4 · p. 8
  • 46.03% verified error replaces 55.88% for IBP on CIFAR-10 at ε = 2/255.Source: §4 · p. 8

Trade-off Between Standard Accuracy and Verified Accuracy

  • At verified error 70%, CROWN-IBP reduces standard error from roughly 55% to 45%.Across κ settings, lower verified errors generally accompany higher standard errors, but CROWN-IBP improves both metrics and shifts the Pareto front lower-left.Source: §4 · p. 8

Comparison to IBP

  • CROWN-IBP outperforms IBP under all κ settings on MNIST and CIFAR-10 across the reported perturbation strengths.Table 2 reports standard, verified, and PGD attack errors for DM-large models.Source: §4 · p. 8, Table 2 · p. 9

Training Stability

  • CROWN-IBP performs better consistently across schedule lengths, while IBP with κ = 0 may fail to stably converge on all models when schedules are short.The stability experiments cover multiple small and medium architectures on MNIST and CIFAR-10.Source: §4 · pp. 8–9

5 CONCLUSIONS

The paper concludes that CROWN-IBP combines IBP efficiency with CROWN tightness to stabilize certified training. Experiments support consistent improvements over IBP baselines and state-of-the-art verified errors for ℓ∞ robustness.

5 CONCLUSIONS

  • CROWN-IBP combines a fast IBP forward bounding pass with a tight CROWN backward bounding pass.The backward CROWN bound scales linearly with neural network output size.Source: §5 · p. 9
  • CROWN-IBP consistently outperforms IBP baselines in standard and verified errors and achieves state-of-the-art ℓ∞ verified test errors.The paper reports this conclusion across MNIST and CIFAR-10 experiments.Source: §5 · p. 9
  • IBP training can be viewed as training a simple augmented ReLU network whose inputs are xk − ε and xk + ε.Its negated lower-bound margins are passed to softmax, and correct prediction corresponds to positive margins throughout the perturbation interval.Source: A IBP AS A SIMPLE AUGMENTED NETWORK · p. 14
  • IBP bounds are initially loose, making robust-loss optimization ineffective and training sensitive to initialization, κ, and schedule length.This instability can produce large performance variance and sub-optimal verified errors.Source: B TIGHTNESS COMPARISON BETWEEN IBP AND… · p. 15
  • CROWN-IBP begins with tighter bounds and gradually replaces them with IBP bounds, allowing the network to learn tighter IBP bounds during training.The described transition uses βstart = 1 and βend = 0.Source: B TIGHTNESS COMPARISON BETWEEN IBP AND… · p. 15

D HYPERPARAMETERS AND MODEL STRUCTURES FOR TRAINING STABILITY EXPERIMENTS

Training-stability experiments use many small and medium models with short, controlled single-GPU runs. MNIST and CIFAR settings vary warmup, ε ramp-up, optimization, augmentation, and model structures.

MNIST

CIFAR

  • CIFAR training uses 200 epochs, batch size 128, ten warmup epochs, and an ε ramp-up schedule of length 120.Training uses random flips and crops, with the three channels normalized by dataset statistics.Source: D HYPERPARAMETERS AND MODEL STRUCTURES… · p. 17

Verification setting

Models and training settings

  • 18 MNIST and 17 CIFAR-10 architectures are evaluated in the stability experiments, using small and medium model groups.Models A–J are small; models K–T are medium, with model A excluded from CIFAR-10 because it is too small.Source: D HYPERPARAMETERS AND MODEL STRUCTURES… · p. 17

E OMITTED RESULTS ON DM-SMALL AND DM-MEDIUM MODELS

Across model structures and κ settings, CROWN-IBP consistently outperforms IBP in the reported MNIST and CIFAR-10 experiments.

F ADDITIONAL EXPERIMENTS ON SMALLER MODELS USING A SINGLE GPU

Additional single-GPU experiments compare IBP and CROWN-IBP across many smaller models, while documenting an MNIST small-ε overfitting condition and evaluation details.

G REPRODUCIBILITY

Repeated MNIST runs provide evidence that CROWN-IBP produces reproducible verified and standard test errors across the evaluated models.

  • Standard deviations of verified errors are very small across five runs of each MNIST experiment.The experiments cover 10 MNIST models and report means and standard deviations for verified and standard errors.Source: G REPRODUCIBILITY · p. 21
  • Each of the 10 MNIST models is trained five times to compute mean and standard deviation estimates.Source: G REPRODUCIBILITY · p. 21

H TRAINING STABILITY EXPERIMENTS ON OTHER ϵ

Across varied ε schedule lengths and κ settings, CROWN-IBP improves training stability and consistently outperforms IBP in the reported MNIST and CIFAR-10 experiments.

I OVERFITTING ISSUE WITH SMALL ϵ

For small ϵ, CROWN-IBP can overfit, while shorter ϵ schedules and small ℓ1 regularization improve verified test error. Across tested schedule lengths, CROWN-IBP achieves the best verified errors.

  • CROWN-IBP can overfit at small ϵ because its training verified error becomes very small, sometimes exactly zero.The authors attribute this to IBP’s strong learning power without sufficient over-regularization.Source: I OVERFITTING ISSUE WITH SMALL ϵ · p. 21
  • Shorter ϵ schedules improve verified error for small ϵ because early stopping prevents overfitting.Figure D compares schedule lengths 10, 15, 30, and 60 on 8 medium MNIST models.Source: Figure D · p. 22
  • All best verified errors are achieved by CROWN-IBP regardless of schedule length on the tested MNIST models.This result is reported for both 8 medium models and 10 small models.Source: Figure D · p. 22, I OVERFITTING ISSUE WITH SMALL ϵ · p. 22
  • A small ℓ1 regularization term improves CROWN-IBP’s verified test error when ϵ_train = 0.1 or 0.2.With λ = 5 × 10^-5, CROWN-IBP reaches 3.60% best certified error at ϵ = 0.1, versus 3.67% for convex adversarial polytope training on the reported models.Source: I OVERFITTING ISSUE WITH SMALL ϵ · p. 22

J TRAINING TIME

CROWN-IBP substantially reduces the training-time cost of tight certified bounds compared with purely linear-relaxation methods, while remaining moderately slower than IBP.

  • CROWN-IBP is practically 1.5 to 3.5 times slower than IBP on representative models.Experiments were measured on RTX 2080 Ti GPUs, using 4 GPUs for two DM-Large models.Source: J TRAINING TIME · p. 22
  • Theoretically, CROWN-IBP is up to 10 times slower than IBP.The footnote specifies a more precise upper factor of 9 times because an all-zero row can be omitted from the specification matrix.Source: J TRAINING TIME · p. 22
  • Purely linear-relaxation methods can be over hundreds times slower than IBP, especially on deeper networks.The paper uses 50 random Cauchy projections for the convex adversarial polytope comparison, but random projections alone do not scale to larger datasets.Source: J TRAINING TIME · p. 23
  • The timing comparison covers IBP, CROWN-IBP, and convex adversarial polytope training under GPU and batch-size settings specified in Table G.The reported batch sizes are 256 for MNIST and 128 for CIFAR-10 for IBP and CROWN-IBP.Source: J TRAINING TIME · p. 23

K REPRODUCING CIFAR-10 RESULTS ON MULTI-GPUS

The paper evaluates CROWN-IBP across TPU and multi-GPU implementations and describes the CROWN bounds used within its propagation procedure. GPU training produces comparable verified errors to TPU training.

Reproducing CIFAR-10 results on multi-GPUs

CROWN-IBP bound construction

  • CROWN replaces nonlinear activations with linear upper and lower hyperplanes, allowing linear bounds to propagate through network layers.The framework can handle activations including ReLU, tanh, sigmoid, and max-pooling when suitable bounds are provided.Source: L EXACT FORMS OF THE CROWN-IBP… · pp. 23–24

ReLU relaxation

  • For ReLU neurons, CROWN uses diagonal relaxation matrices whose coefficients depend on whether neurons are always active, always inactive, or otherwise unstable.The listed cases assign coefficients 1, 0, or α with 0 ≤ α ≤ 1, depending on the pre-activation range.Source: L EXACT FORMS OF THE CROWN-IBP… · p. 24

CROWN-IBP bound construction

  • CROWN-IBP uses IBP to obtain pre-activation bounds required by CROWN-style linear bounds.These bounds are assumed valid for all inputs in the perturbation set S.Source: L EXACT FORMS OF THE CROWN-IBP… · p. 24

CROWN lower bound

  • The general CROWN lower-bound theorem provides an output bound for every class of an L-layer network over the input set S.The construction uses network weight matrices, ReLU relaxation matrices, and a standard unit vector for the selected output neuron.Source: L EXACT FORMS OF THE CROWN-IBP… · pp. 24–25

CROWN-IBP implementation

  • CROWN-IBP computes only the lower bound needed for m, avoiding upper-bound A matrices and saving half the computation cost of ordinary CROWN.Affine layers, including CNN convolutional layers, are supported; transposed convolutions implement the procedure efficiently on GPUs.Source: L EXACT FORMS OF THE CROWN-IBP… · p. 25

Scope

  • Although the paper focuses on ReLU activations, CROWN supports other general activation functions.The authors refer to prior work for the more general derivation.Source: L EXACT FORMS OF THE CROWN-IBP… · p. 25

Related papers

Loading 1906.06316v2…