mlsanityData to 7 Oct 2026

The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification

arXiv 2006.14076 ↗First posted 24 Jun 2020cs.LG stat.MLcited by 50

Not on the map. Why?

Abstract (arXiv)

We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike previous single-neuron relaxations which focus only on the univariate input space of the ReLU, our method considers the multivariate input space of the affine pre-activation function preceding the ReLU. Using results from submodularity and convex geometry, we derive an explicit description of the tightest possible convex relaxation when this multivariate input is over a box domain. We show that our convex relaxation is significantly stronger than the commonly used univariate-input relaxation which has been proposed as a natural convex relaxation barrier for verification. While our description of the relaxation may require an exponential number of inequalities, we show that they can be separated in linear time and hence can be efficiently incorporated into optimization algorithms on an as-needed basis. Based on this novel relaxation, we design two polynomial-time algorithms for neural network verification: a linear-programming-based algorithm that leverages the full power of our relaxation, and a fast propagation algorithm that generalizes existing approaches. In both cases, we show that for a modest increase in computational effort, our strengthened relaxation enables us to verify a significantly larger number of instances compared to similar algorithms.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 16; 2023: 9; 2024: 6; 2025: 5; 2026: 1.

50 papers.

Sort:

  1. 2021Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Robustness Verificationcited by 224
  2. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 102
  3. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
  4. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  5. 2022Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspectivecited by 41
  6. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  7. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  8. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  9. 2022Efficient Neural Network Analysis with Sum-of-Infeasibilitiescited by 24
  10. 2023Expressive Losses for Verified Robustness via Convex Combinationscited by 23
  11. 2022IBP Regularization for Verified Adversarial Robustness via Branch-and-Boundcited by 21
  12. 2023Convex Bounds on the Softmax Function with Applications to Robustness Verificationcited by 19
38 more
  1. 2022Scalable Verification of GNN-based Job Schedulerscited by 18
  2. 2022Toward Certified Robustness Against Real-World Distribution Shiftscited by 16
  3. 2021Neural Network Verification in Controlcited by 14
  4. 2022Can pruning improve certified robustness of neural networks?cited by 14
  5. 2021On the Paradox of Certified Trainingcited by 12
  6. 2021GoTube: Scalable Stochastic Verification of Continuous-Depth Modelscited by 12
  7. 2021Scaling the Convex Barrier with Sparse Dual Algorithmscited by 10
  8. 2021Learning Optimal Prescriptive Trees from Observational Datacited by 10
  9. 2022Linearity Grafting: Relaxed Neuron Pruning Helps Certifiable Robustnesscited by 10
  10. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  11. 2025Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verificationcited by 9
  12. 2021DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splittingcited by 8
  13. 2022Provably Tightest Linear Approximation for Robustness Verification of Sigmoid-like Neural Networkscited by 8
  14. 2023Expressivity of ReLU-Networks under Convex Relaxationscited by 8
  15. 2024Verification of Geometric Robustness of Neural Networks via Piecewise Linear Approximation and Lipschitz Optimisationcited by 7
  16. 2021Deep Policy Iteration with Integer Programming for Inventory Managementcited by 5
  17. 2021Reachability Analysis of Convolutional Neural Networkscited by 4
  18. 2024On Using Certified Training towards Empirical Robustnesscited by 3
  19. 2021Towards Optimal Branching of Linear and Semidefinite Relaxations for Neural Network Robustness Certificationcited by 2
  20. 2021A Primer on Multi-Neuron Relaxation-based Adversarial Robustness Certificationcited by 2
  21. 2022Neural Network Verification as Piecewise Linear Optimization: Formulations for the Composition of Staircase Functionscited by 2
  22. 2023A Tale of Two Approximations: Tightening Over-Approximation for DNN Robustness Verification via Under-Approximationcited by 2
  23. 2024Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certificationcited by 2
  24. 2025Adaptive Branch-and-Bound Tree Exploration for Neural Network Verificationcited by 2
  25. 2022An Overview and Prospective Outlook on Robust Training and Certification of Machine Learning Modelscited by 1
  26. 2022Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networkscited by 1
  27. 2023Boosting Verified Training for Robust Image Classifications via Abstractioncited by 1
  28. 2023RNN-Guard: Certified Robustness Against Multi-frame Attacks for Recurrent Neural Networkscited by 1
  29. 2023Expediting Neural Network Verification via Network Reductioncited by 1
  30. 2025Formal Verification of Markov Processes with Learned Parameterscited by 1
  31. 2025Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verificationcited by 1
  32. 2022On the tightness of linear relaxation based robustness certification methodscited by 0
  33. 2022DualApp: Tight Over-Approximation for Neural Network Robustness Verification via Under-Approximationcited by 0
  34. 2023Robustness Analysis of Continuous-Depth Models with Lagrangian Techniquescited by 0
  35. 2024Towards General Robustness Verification of MaxPool-based Convolutional Neural Networks via Tightening Linear Approximationcited by 0
  36. 2024Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activationscited by 0
  37. 2025Efficient Neural Network Verification via Order Leading Exploration of Branch-and-Bound Treescited by 0
  38. 2026Branch and Bound for Relational Verification of Neural Networkscited by 0