PaperlayerView exact revision on arXiv

Source-linked AI summary

Scaling provable adversarial defenses

Eric Wong, Frank R. Schmidt, Jan Hendrik Metzen, J. Zico Kolter

arXiv:1805.12514v2cs.LGcs.AImath.OCstat.ML

TL;DR

Provably robust adversarial training had been limited to relatively small feedforward networks. The paper extends it to general architectures, introduces linearly scalable random-projection training, and uses cascades; verified robust error improves on MNIST and CIFAR, while experiments remain below ImageNet scale.

  • Problem

    Provably robust training methods had been limited to relatively small networks, leaving their extension to larger, more representationally complex models unclear.

  • Method

    The paper combines modular dual-layer constructions for general networks, nonlinear random projections for linearly scalable ReLU training under ℓ∞ attacks, and model cascades.

  • Results

    Cascading reduces CIFAR10 robust error from 46.1% to 36.4% for ε = 2/255, while the best MNIST cascade reaches 3.1% error for ε = 0.1.

  • Takeaways & Limitations

    The methodology makes it possible to train larger provably robust ReLU networks against ℓ∞-bounded attacks, with further bound improvements from cascades.

  • Takeaways & Limitations

    The experiments currently max out at CIFAR10 and do not yet reach ImageNet-scale datasets, so the emphasis is on potential scaling properties.

Abstract

from arXiv · show

Recent work has developed methods for learning deep network classifiers that are provably robust to norm-bounded adversarial perturbation; however, these methods are currently only possible for relatively small feedforward networks. In this paper, in an effort to scale these approaches to substantially larger models, we extend previous work in three main directions. First, we present a technique for extending these training procedures to much more general networks, with skip connections (such as ResNets) and general nonlinearities; the approach is fully modular, and can be implemented automatically (analogous to automatic differentiation). Second, in the specific case of $\ell_\infty$ adversarial perturbations and networks with ReLU nonlinearities, we adopt a nonlinear random projection for training, which scales linearly in the number of hidden units (previous approaches scaled quadratically). Third, we show how to further improve robust error through cascade models. On both MNIST and CIFAR data sets, we train classifiers that improve substantially on the state of the art in provable robust adversarial error bounds: from 5.8% to 3.1% on MNIST (with $\ell_\infty$ perturbations of $ε=0.1$), and from 80% to 36.4% on CIFAR (with $\ell_\infty$ perturbations of $ε=2/255$). Code for all experiments in the paper is available at https://github.com/locuslab/convex_adversarial/.

1 Introduction

Provably robust training had been limited to small feedforward networks, and the paper extends these methods toward larger, more general architectures while improving verified robust error.

  • Provable robustness methods had been possible only for reasonably small networks, leaving extension to larger, more representationally complex models unclear.
  • The framework extends to networks with arbitrary residual or skip connections, moving beyond pure feedforward architectures.
  • Nonlinear random projections reduce worst-case robust-loss bound computation from quadratic to linear scaling in the number of hidden units.
  • Cascade models further improve robust performance, but at the expense of worse non-robust error.

2 Background and related work

Prior adversarial defenses span heuristic robustness, formal verification, and training with verified bounds, but existing provable-training approaches remained limited in scale. This paper addresses that gap with a modular, linearly scalable training procedure and model cascades.

  • Heuristic adversarial defenses are largely empirical and have often been broken by stronger attacks, despite progress in apparent robustness.
  • Formal verification has used exact SMT or integer-programming solvers to assess neural-network robustness.
  • Several methods integrate verification bounds into training, including surrogate bounds, semidefinite relaxations, and linear-programming bounds.
  • Existing approaches remained limited to relatively small networks and tasks such as MNIST because some methods scale quadratically with hidden units or input dimensions.
  • The paper extends verified training to general networks, linear scaling, minimal accuracy degradation, and improved bounds through model cascades.

3 Scaling provably robust networks

The paper scales provably robust training to general networks by composing modular dual functions, including arbitrary operations and skip connections. For ℓ∞-bounded perturbations in ReLU networks, random projections replace quadratic bound computation with a linear-scaling estimate, while preserving a tunable tightness–efficiency trade-off.

  • 3.1 Robust bounds for general networks via modular dual functions: Modular dual functions automatically construct robust bounds for arbitrary sequences of network operations, including skip connections.The framework derives each operation’s dual separately and composes the resulting toolkit across architectures.
  • 3.1 Robust bounds for general networks via modular dual functions: Batch normalization is formally outside the approach because it depends on entire minibatches and is approximated using test-time scaling and shifting parameters.Although it may improve convergence, batch normalization can loosen the robust bound by centering activations nearer the origin.
  • 3.1 Robust bounds for general networks via modular dual functions: Fenchel duality converts the adversarial optimization problem into a dual network whose bounds can be optimized with standard deep-learning tools.Training minimizes the loss evaluated on the bound of possible network outputs under perturbations.
  • 3.1 Robust bounds for general networks via modular dual functions: Residual and skip connections remain in the dual network but reverse direction, while residual-network biases enter the dual objective.The figure illustrates this construction for a residual block using the dual layers for linear operators and ReLU activations.
  • 3.2 Efficient bound computation for ℓ∞ perturbations via random projections: Exact ℓ∞ bounds for ReLU networks require explicitly forming matrices across input dimensions and unstable units, making computation quadratic in hidden units.This motivates random projections for larger networks.
  • 3.2 Efficient bound computation for ℓ∞ perturbations via random projections: With fixed projection dimension r, random projections reduce the computational complexity from quadratic to linear in the relevant network dimensions.The bound can be computed exactly at test time because gradients no longer need to be stored.

4 Experiments

Experiments evaluate the approach on MNIST and CIFAR10 across convolutional and residual architectures, with random projections and cascades improving verified robust error. The results also examine projection dimensions and the trade-off between robust and nominal error.

  • Dataset and Architectures: MNIST and CIFAR10 experiments span deep and wide convolutional architectures, with and without residual connections.The evaluated models include small and large convolutional networks and residual networks.
  • Summary of results: 3.1% robust error is achieved on MNIST at ε = 0.1 with the best cascade, versus 5.8% for the previous best bound.The non-cascaded large model reaches 3.7% robust error under the same perturbation budget.
  • Summary of results: 36.4% robust error is achieved on CIFAR10 at ε = 2/255 with a cascade, versus 80% for the previous best verified robust error.The non-cascaded ResNet reaches 46.1% robust error before cascading.
  • Number of random projections: Lower projection dimensions do not significantly affect test error on MNIST, while reducing the computational burden of training.Using 10 random projection dimensions is sufficient for the referenced convolutional architecture.
  • Cascades: Cascading models improves robust error but increases nominal error throughout the cascade.The cascade is described as forcing robust and nominal errors to match more closely.
  • Cascades: Improving single-model networks and integrating cascades both provide substantial value for robust prediction.

5 Conclusion

The paper presents a conjugate-function methodology for deriving dual networks from compositions of dual layers and uses it to train provably robust classifiers. Its conclusion emphasizes scalable ReLU defenses, cascade-based bound improvements, and remaining scope for better architectures and perturbation models.

  • Conclusion: The methodology derives dual networks from compositions of dual layers using conjugate functions to train provably robust classifiers.
  • Conclusion: For ReLU networks under ℓ∞-norm-bounded attacks, the method scales linearly and enables training larger provably robust networks.
  • Conclusion: Model cascades can further improve the obtained robust bounds.
  • Conclusion: Future work includes developing architectures with more robust or more efficient dual layers.
  • Conclusion: A major open direction is characterizing adversarial perturbations beyond norm-bounded attacks.

A.2 Proof of Theorem 1

The proof derives a lower bound for the adversarial optimization problem by introducing indicator functions, conjugate functions, and dual variables. It then constructs dual layers for linear, skip-connected, ReLU, and hardtanh components.

  • Proof strategy: The primal adversarial problem is rewritten with indicator functions before applying a lemma to obtain a lower bound.
  • Input constraints: Input constraints contribute a conjugate term involving the dual norm when perturbations are norm-bounded.The framework can also use other input constraints when their conjugates can be bounded.
  • Dual layers: The framework derives dual layers for standard deep-learning building blocks, including linear operations and skip-connected linear structures.
  • ReLU activations: The ReLU proof uses its conjugate together with lower and upper preactivation bounds and convex outer relaxations.
  • Hardtanh activation: The hardtanh dual layer uses a convex relaxation whose form depends on the input bounds, with some cases reducing to exact linear regions.

B.4.1 u > 1, ℓ< −1

The section develops convex hardtanh relaxations for bounded inputs and shows that the resulting dual layer remains linear, preserving efficient random-projection estimation. It also describes cascade training and a batch-normalization trade-off.

  • B.4.1 u > 1, ℓ < −1: For u > 1 and ℓ < −1, the hardtanh upper and lower bounds are defined by lines through (ℓ, −1), (1, 1), (−1, −1), and (u, 1).Their slopes are 2/(1−ℓ) and 2/(u+1), respectively.
  • B.4.1 u > 1, ℓ < −1: The conjugate upper bound is obtained by taking the maximum over the two linear relaxation cases.The resulting constraint gives the dual-layer representation.
  • B.4.1 u > 1, ℓ < −1: The hardtanh dual layer is linear, so random projections remain applicable for efficient bound estimation.This preserves the scalable estimation strategy used for linear dual networks.
  • B.5 Batch normalization: Batch normalization can improve convergence but reduces bound quality because centering activations near the origin loosens the robust bound.The analysis assumes fixed mean and variance statistics.
  • C Cascade construction: Cascade models remove certified examples after each robustly trained stage, allowing later classifiers to address the remaining examples.The two-stage illustration shows the first model certifying three datapoints before the second stage handles the remainder.

D.1 Proof of Theorem 2

This proof constructs scalable certificate estimates by rewriting dual-network terms as linear network operations and estimating them with Cauchy random projections. It then combines multiple estimators with a union bound to obtain high-probability certificates, while exposing a tail-probability limitation.

  • D.1 Proof of Theorem 2: The dual-network terms are rewritten as linear operations on modified inputs, including lower-bound scaling, indicator masking, and summation.These transformations express the relevant quantities through forward passes of the linearized network.
  • D.1 Proof of Theorem 2: Cauchy random projections estimate the expensive term by passing projected inputs through the network and taking median values.Intermediate transformed projections can be cached layer by layer.
  • D.1 Proof of Theorem 2: If the estimated certificate objective is negative, the example is certified robust with high probability.The approximate objective uses a high-probability ℓ1 upper bound.
  • D.1 Proof of Theorem 2: The proof enumerates N = n2 + 2n3 + ··· + (k − 2)n_(k−1) estimates and allocates failure probability δ/N to each before applying a union bound.This yields an overall probability 1 − δ that all estimates are valid upper bounds.
  • D.1 Proof of Theorem 2: When δ/N becomes small, the required estimator parameter ϵ grows and the resulting bound worsens.For fixed k, the text also identifies a lower limit on how small δ/N can become.
  • D.1 Proof of Theorem 2: Taking the maximum of m independent geometric estimators reduces the tail probability from δ to δ^m.The reduction is exponential in the number of estimators m.

E.5 High probability tail bounds for network certificates

The section evaluates estimator behavior and computational scaling for high-probability network certificates. Median-estimator error decreases with more projections, while random projections scale linearly and avoid the exact method’s memory limit.

  • E.6 Estimation quality and speedup: The exact method runs out of memory at 52,800 hidden units, while random projections reach 4,202,240 hidden units in 0.96 seconds.The random-projection timing slope is 2.26 × 10^-7 seconds per hidden unit on a single Titan X.
  • E.5 High probability tail bounds for network certificates: The median estimator’s relative-error distribution is approximately normal, with decreasing variance as the number of projections increases.This behavior appears for both random and robustly trained convolutional layers.
  • E.6 Estimation quality and speedup: The exact bound scales quadratically in hidden units, whereas the median estimator scales linearly and reaches millions of hidden units.The comparison is made on a convolutional MNIST example.

F AutoDual

AutoDual generalizes dual-network bound computation to general networks and automatically constructs the required bounds and dual layers. Layer-specific optimizations reduce unnecessary computation during this process.

  • AutoDual generalizes the Wong–Kolter bounds computation algorithm to general networks using dual layers.
  • Affine dual-layer operators allow all intermediate lower and upper bounds, and the dual network, to be constructed with a single forward pass.
  • Skip-connected operators that do not exist in a given architecture become no-ops and can be ignored.
  • Dual variables can be initialized with a smaller matrix than the identity when the relevant dual functions depend on a projected matrix product.
  • The method can automatically create dual-layer operators from network operations, activation bounds, and the corresponding functions.

G Experiments

The experiments vary network width and depth across MNIST and CIFAR10 using convolutional architectures and report results for these configurations. The setup also includes residual and cascaded variants in the reported tables.

  • The experiments examine how model width and depth affect performance using a shared architecture-width parameter k.
  • Wide(k) networks use two convolutional layers followed by a 128 × k fully connected layer, while Deep(k) networks vary convolutional depth and filter counts with k.
  • MNIST experiments use Adam with learning rate 0.001, batch size 50, and 60 training epochs with scheduled perturbation and learning-rate decay.
  • Increasing MNIST model capacity through greater width and depth improves performance, but excessive width degrades test robust error because of overfitting.
  • CIFAR10 experiments use SGD with learning rate 0.05, batch size 50, and the same 60-epoch perturbation and learning-rate scheduling pattern.
  • The reported tables cover MNIST and CIFAR10 configurations including small, large, residual, and cascaded variants.

H Results for ℓ2 perturbations

The paper evaluates analogous experiments under ℓ2 perturbations by replacing the objective norm and using random normal projections. Larger and cascaded models show robustness trends similar to those under ℓ∞ perturbations.

  • ℓ2 experiments replace the objective’s ℓ1 norm with an ℓ2 norm and use random normal projections instead of random Cauchy projections.
  • For MNIST, the volume-equivalent perturbation is ϵ2 = 1.58 for ϵ∞ = 0.1, while the minimum within-dataset ℓ2 digit distance is at least 3.24.
  • The complete ℓ2 experiments show similar robustness trends for larger and cascaded models to those observed with ℓ∞ perturbations.
Loading 1805.12514v2…