mlsanityData to 7 Oct 2026

Towards Fast Computation of Certified Robustness for ReLU Networks

arXiv 1804.09699 ↗First posted 25 Apr 2018stat.ML cs.CR cs.CVcited by 254

Not on the map. Why?

Abstract (arXiv)

Verifying the robustness property of a general Rectified Linear Unit (ReLU) network is an NP-complete problem [Katz, Barrett, Dill, Julian and Kochenderfer CAV17]. Although finding the exact minimum adversarial distortion is hard, giving a certified lower bound of the minimum distortion is possible. Current available methods of computing such a bound are either time-consuming or delivering low quality bounds that are too loose to be useful. In this paper, we exploit the special structure of ReLU networks and provide two computationally efficient algorithms Fast-Lin and Fast-Lip that are able to certify non-trivial lower bounds of minimum distortions, by bounding the ReLU units with appropriate linear functions Fast-Lin, or by bounding the local Lipschitz constant Fast-Lip. Experiments show that (1) our proposed methods deliver bounds close to (the gap is 2-3X) exact minimum distortion found by Reluplex in small MNIST networks while our algorithms are more than 10,000 times faster; (2) our methods deliver similar quality of bounds (the gap is within 35% and usually around 10%; sometimes our bounds are even better) for larger networks compared to the methods based on solving linear programming problems but our algorithms are 33-14,000 times faster; (3) our method is capable of solving large MNIST and CIFAR networks up to 7 layers with more than 10,000 neurons within tens of seconds on a single CPU core. In addition, we show that, in fact, there is no polynomial time algorithm that can approximately find the minimum ℓ1 adversarial distortion of a ReLU network with a 0.99ln n approximation ratio unless mathsfNP=mathsfP, where n is the number of neurons in the network.

Key facts. Cited by 254 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Apr 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 73; 2022: 67; 2023: 42; 2024: 28; 2025: 23; 2026: 21.

254 papers.

Sort:

By area:

  1. 2021Globally-Robust Neural Networkscited by 106
  2. 2021Robustness of Graph Neural Networks at Scalecited by 100
  3. 2021AugMax: Adversarial Composition of Random Augmentations for Robust Trainingcited by 89
  4. 2022Learning Smooth Neural Functions via Lipschitz Regularizationcited by 86
  5. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  6. 2021Skew Orthogonal Convolutionscited by 67
  7. 2021Training Certifiably Robust Neural Networks with Efficient Local Lipschitz Boundscited by 64
  8. 2022Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspectivecited by 48
  9. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  10. 2021Improved deterministic l2 robustness on CIFAR-10 and CIFAR-100cited by 47
  11. 2022Efficiently Computing Local Lipschitz Constants of Neural Networks via Bound Propagationcited by 45
  12. 2021Improved Branch and Bound for Neural Network Verification via Lagrangian Decompositioncited by 44
38 more
  1. 2021Certified Patch Robustness via Smoothed Vision Transformerscited by 44
  2. 2022Make Some Noise: Reliable and Efficient Single-Step Adversarial Trainingcited by 42
  3. 2021CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothingcited by 41
  4. 2021Reachability Analysis of Neural Feedback Loopscited by 41
  5. 2022Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspectivecited by 41
  6. 2021Towards Certifying L-infinity Robustness using Neural Networks with L-inf-dist Neuronscited by 40
  7. 2021On the Certified Robustness for Ensemble Models and Beyondcited by 40
  8. 2021Boosting Fast Adversarial Training with Learnable Adversarial Initializationcited by 40
  9. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  10. 2022How to Robustify Black-Box ML Models? A Zeroth-Order Optimization Perspectivecited by 39
  11. 2022Certified Neural Network Watermarks with Randomized Smoothingcited by 39
  12. 2022On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learningcited by 39
  13. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  14. 2021POLAR: A Polynomial Arithmetic Framework for Verifying Neural-Network Controlled Systemscited by 38
  15. 2021Scalable Certified Segmentation via Randomized Smoothingcited by 35
  16. 2021A Review of Formal Methods applied to Machine Learningcited by 33
  17. 2021Towards Scalable Verification of Deep Reinforcement Learningcited by 33
  18. 2022Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizabilitycited by 32
  19. 2021Pay attention to your loss: understanding misconceptions about 1-Lipschitz neural networkscited by 30
  20. 2021On the Existence of the Adversarial Bayes Classifier (Extended Version)cited by 25
  21. 2022COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attackscited by 25
  22. 2021Intriguing Properties of Input-dependent Randomized Smoothingcited by 24
  23. 2021Boosting the Certified Robustness of L-infinity Distance Netscited by 24
  24. 2022An Abstraction-Refinement Approach to Verifying Convolutional Neural Networkscited by 24
  25. 2022Efficient Neural Network Analysis with Sum-of-Infeasibilitiescited by 24
  26. 2022Open- and Closed-Loop Neural Network Verification using Polynomial Zonotopescited by 24
  27. 2021DNNV: A Framework for Deep Neural Network Verificationcited by 23
  28. 2021ANCER: Anisotropic Certification via Sample-wise Volume Maximizationcited by 23
  29. 2022Certified Robustness Against Natural Language Attacks by Causal Interventioncited by 23
  30. 2022Robust Explanation Constraints for Neural Networkscited by 23
  31. 2021Robust Models Are More Interpretable Because Attributions Look Normalcited by 21
  32. 2022Denoising Masked AutoEncoders Help Robust Classificationcited by 21
  33. 2021Adversarial Training is Not Ready for Robot Learningcited by 20
  34. 2021Pruning and Slicing Neural Networks using Formal Verificationcited by 20
  35. 2021Neural Network Repair with Reachability Analysiscited by 19
  36. 2022PRoA: A Probabilistic Robustness Assessment against Functional Perturbationscited by 19
  37. 2023Convex Bounds on the Softmax Function with Applications to Robustness Verificationcited by 19
  38. 2023Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularizationcited by 19

50 most cited of 254 All 254 (JSON)