mlsanityData to 7 Oct 2026

A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks

arXiv 1902.08722 ↗First posted 23 Feb 2019cs.LG cs.AI cs.CRcited by 124

Not on the map. Why?

Abstract (arXiv)

Verification of neural networks enables us to gauge their robustness against adversarial attacks. Verification algorithms fall into two categories: exact verifiers that run in exponential time and relaxed verifiers that are efficient but incomplete. In this paper, we unify all existing LP-relaxed verifiers, to the best of our knowledge, under a general convex relaxation framework. This framework works for neural networks with diverse architectures and nonlinearities and covers both primal and dual views of robustness verification. We further prove strong duality between the primal and dual problems under very mild conditions. Next, we perform large-scale experiments, amounting to more than 22 CPU-years, to obtain exact solution to the convex-relaxed problem that is optimal within our framework for ReLU networks. We find the exact solution does not significantly improve upon the gap between PGD and existing relaxed verifiers for various networks trained normally or robustly on MNIST and CIFAR datasets. Our results suggest there is an inherent barrier to tight verification for the large class of methods captured by our framework. We discuss possible causes of this barrier and potential future directions for bypassing it. Our code and trained models are available at http://github.com/Hadisalman/robust-verify-benchmark .

Key facts. Cited by 124 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Feb 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 27; 2022: 28; 2023: 28; 2024: 12; 2025: 13; 2026: 16.

124 papers.

Sort:

By area:

  1. 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 224
  2. 2021Robust Reinforcement Learning on State Observations with Learned Optimal Adversarycited by 133
  3. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 102
  4. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  5. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  6. 2021The Second International Verification of Neural Networks Competition (VNN-COMP 2021): Summary and Resultscited by 71
  7. 2022Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspectivecited by 48
  8. 2021Improved Branch and Bound for Neural Network Verification via Lagrangian Decompositioncited by 44
  9. 2021Certified Patch Robustness via Smoothed Vision Transformerscited by 44
  10. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  11. 2022Don't Lie to Me! Robust and Efficient Explainability with Verified Perturbation Analysiscited by 38
  12. 2022DensePure: Understanding Diffusion Models towards Adversarial Robustnesscited by 33
38 more
  1. 2021Low Curvature Activations Reduce Overfitting in Adversarial Trainingcited by 29
  2. 2023Provably Bounding Neural Network Preimagescited by 28
  3. 2021Boosting the Certified Robustness of L-infinity Distance Netscited by 24
  4. 2022An Abstraction-Refinement Approach to Verifying Convolutional Neural Networkscited by 24
  5. 2022Efficient Neural Network Analysis with Sum-of-Infeasibilitiescited by 24
  6. 2021ANCER: Anisotropic Certification via Sample-wise Volume Maximizationcited by 23
  7. 2023Certified Robustness for Large Language Models with Self-Denoisingcited by 23
  8. 2022IBP Regularization for Verified Adversarial Robustness via Branch-and-Boundcited by 21
  9. 2023DiffSmooth: Certifiably Robust Learning via Diffusion Models and Local Smoothingcited by 20
  10. 2023Convex Bounds on the Softmax Function with Applications to Robustness Verificationcited by 19
  11. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  12. 2021ROMAX: Certifiably Robust Deep Multiagent Reinforcement Learning via Convex Relaxationcited by 17
  13. 2021Robustness Certification for Point Cloud Modelscited by 16
  14. 2022Toward Certified Robustness Against Real-World Distribution Shiftscited by 16
  15. 2021Towards Evaluating and Training Verifiably Robust Neural Networkscited by 15
  16. 2022Double Bubble, Toil and Trouble: Enhancing Certified Robustness through Transitivitycited by 15
  17. 2021Learning Security Classifiers with Verified Global Robustness Propertiescited by 14
  18. 2021Neural Network Verification in Controlcited by 14
  19. 2022Can pruning improve certified robustness of neural networks?cited by 14
  20. 2023Incremental Verification of Neural Networkscited by 14
  21. 2023Provable Preimage Under-Approximation for Neural Networks (Full Version)cited by 13
  22. 2021On the Paradox of Certified Trainingcited by 12
  23. 2021GoTube: Scalable Stochastic Verification of Continuous-Depth Modelscited by 12
  24. 2022A Unified View of SDP-based Neural Network Verification through Completely Positive Programmingcited by 12
  25. 2021Scaling the Convex Barrier with Sparse Dual Algorithmscited by 10
  26. 2021Shared Certificates for Neural Network Verificationcited by 10
  27. 2022Linearity Grafting: Relaxed Neuron Pruning Helps Certifiable Robustnesscited by 10
  28. 2022CARE: Certifiably Robust Learning with Reasoning via Variational Inferencecited by 10
  29. 2023Efficient Error Certification for Physics-Informed Neural Networkscited by 10
  30. 2024Detecting Brittle Decisions for Free: Leveraging Margin Consistency in Deep Robust Classifierscited by 10
  31. 2025SDP-CROWN: Efficient Bound Propagation for Neural Network Verification with Tightness of Semidefinite Programmingcited by 10
  32. 2022Improved techniques for deterministic l2 robustnesscited by 9
  33. 2025Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verificationcited by 9
  34. 2021DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splittingcited by 8
  35. 2022Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networkscited by 8
  36. 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
  37. 2024PREMAP: A Unifying PREiMage APproximation Framework for Neural Networkscited by 8
  38. 2024Verification of Geometric Robustness of Neural Networks via Piecewise Linear Approximation and Lipschitz Optimisationcited by 7

50 most cited of 124 All 124 (JSON)