A Dual Approach to Verify and Train Deep Networks

Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Timothy A. Mann, Pushmeet KohliIJCAI 2019 · DOI

Introduction

Deep neural networks are notoriously fragile. Small, imperceptible changes to an input—known as adversarial perturbations—can cause a model to flip its prediction with high confidence. While "empirical" defenses like adversarial training (e.g., using Projected Gradient Descent or PGD) help, they do not offer formal guarantees. An attacker might simply find a more clever way to perturb the input that the training didn't account for.

This paper introduces a scalable framework for the formal verification of neural networks by treating verification as an optimization problem. By solving a Lagrangian relaxation of this problem, the authors obtain provable upper bounds on network violations and demonstrate a "Predictor-Verifier" training method that allows models to be trained for provable robustness at scale.

Methodology: Lagrangian Relaxation and PVT

The authors frame verification as finding the "worst-case" violation of a specification. If the maximum possible violation is less than zero, the property is verified.

1. Lagrangian Relaxation

Since finding the exact maximum violation is computationally intractable (NP-hard), the authors use Lagrangian relaxation to "relax" the hard constraints of the neural network layers into a dual problem. Solving this dual problem provides a guaranteed upper bound on the violation. This dual approach allows the verification of a deep network to break down into smaller, independent problems for each layer and neuron, making it applicable to various activation functions like ReLU, sigmoid, and tanh.

2. Predictor-Verifier Training (PVT)

To make training robust models faster, they introduce a secondary "verifier" network. This network learns to predict the optimal dual variables (the "proof parameters") for a given input. This allows the main model to be trained to minimize its provable violation without having to solve a complex optimization problem from scratch at every training step.

The Predictor-Verifier architecture: a secondary network (Verifier) learns to predict dual variables $\lambda$ to provide fast upper bounds for the Predictor's loss.

Experimental Results

The researchers evaluated their approach on standard image classification benchmarks: MNIST, CIFAR-10, and SVHN, focusing on robustness under $L_\infty$ norm-bounded attacks.

Tightness and Scaling

On the MNIST dataset, the proposed dual approach produced bounds that were nearly as tight as the actual worst-case attacks for small perturbation radii, significantly outperforming previous Semidefinite Programming (SDP) approaches. Furthermore, the authors achieved what were, at the time of publication, the first non-trivial verification bounds on CIFAR-10.

Error rates on MNIST (a) and CIFAR-10 (b) test sets. The plots show the gap between the calculated upper bounds and the lower bounds (empirical attacks).

Improved Training Efficiency

The Predictor-Verifier Training (PVT) improved verified error rates across the board. For example, on SVHN with $\epsilon=0.01$, PVT reduced the verified error rate from 45.92% (using simpler interval methods) to 41.52%. This demonstrates that amortizing the cost of the proof through meta-learning is a viable path toward scalable robust training.

Limitations and Future Outlook

Despite these advances, several challenges remain:

  • The Robustness Tax: Provably robust models often exhibit lower standard accuracy on clean images compared to non-robust counterparts.
  • Tightness vs. Speed: While the dual approach is scalable, a gap remains between the calculated upper bound and the true worst-case violation. Finding even tighter bounds during training is a vital area for future research.
  • Complex Specifications: Current work focuses largely on $L_\infty$ robustness. Extending this to semantic specifications like rotation or lighting changes is an ongoing challenge.

Summary updated

BibTeX
@inproceedings{gowal2019dual,
  author = {Sven Gowal and Krishnamurthy Dvijotham and Robert Stanforth and Timothy A. Mann and Pushmeet Kohli},
  title = {{A Dual Approach to Verify and Train Deep Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/854},
}
Figure