mlsanityData to 7 Oct 2026

Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming

arXiv 2010.11645 ↗First posted 22 Oct 2020cs.LG cs.AIcited by 65

Not on the map. Why?

Abstract (arXiv)

Convex relaxations have emerged as a promising approach for verifying desirable properties of neural networks like robustness to adversarial perturbations. Widely used Linear Programming (LP) relaxations only work well when networks are trained to facilitate verification. This precludes applications that involve verification-agnostic networks, i.e., networks not specially trained for verification. On the other hand, semidefinite programming (SDP) relaxations have successfully be applied to verification-agnostic networks, but do not currently scale beyond small networks due to poor time and space asymptotics. In this work, we propose a first-order dual SDP algorithm that (1) requires memory only linear in the total number of network activations, (2) only requires a fixed number of forward/backward passes through the network per iteration. By exploiting iterative eigenvector methods, we express all solver operations in terms of forward and backward passes through the network, enabling efficient use of hardware like GPUs/TPUs. For two verification-agnostic networks on MNIST and CIFAR-10, we significantly improve L-inf verified robust accuracy from 1% to 88% and 6% to 40% respectively. We also demonstrate tight verification of a quadratic stability specification for the decoder of a variational autoencoder.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 22; 2023: 13; 2024: 8; 2025: 6; 2026: 2.

65 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. 2022Natural Language Descriptions of Deep Visual Featurescited by 136
  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. 2022Certified Training: Small Boxes are All You Needcited by 51
  7. 2021Boosting Randomized Smoothing with Variance Reduced Classifierscited by 47
  8. 2022Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspectivecited by 41
  9. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  10. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  11. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  12. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
38 more
  1. 2021Boosting the Certified Robustness of L-infinity Distance Netscited by 24
  2. 2023Expressive Losses for Verified Robustness via Convex Combinationscited by 23
  3. 2021Safe Control with Neural Network Dynamic Modelscited by 21
  4. 2023Certified Robustness via Dynamic Margin Maximization and Improved Lipschitz Regularizationcited by 19
  5. 2021Make Sure You're Unsure: A Framework for Verifying Probabilistic Specificationscited by 18
  6. 2021Provably Robust Detection of Out-of-distribution Data (almost) for freecited by 17
  7. 2021Towards Evaluating and Training Verifiably Robust Neural Networkscited by 15
  8. 2023Wasserstein distributional robustness of neural networkscited by 15
  9. 2021Neural Network Verification in Controlcited by 14
  10. 2021On the Paradox of Certified Trainingcited by 12
  11. 2022A Unified View of SDP-based Neural Network Verification through Completely Positive Programmingcited by 12
  12. 2022Adversarial robustness of sparse local Lipschitz predictorscited by 11
  13. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  14. 2023TAPS: Connecting Certified and Adversarial Trainingcited by 11
  15. 2022Linearity Grafting: Relaxed Neuron Pruning Helps Certifiable Robustnesscited by 10
  16. 2022Closing the Loop: A Framework for Trustworthy Machine Learning in Power Systemscited by 9
  17. 2022Improved techniques for deterministic l2 robustnesscited by 9
  18. 2025Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verificationcited by 9
  19. 2021DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splittingcited by 8
  20. 2024Lipschitz constant estimation for general neural network architectures using control toolscited by 8
  21. 2022On the Safety of Interpretable Machine Learning: A Maximum Deviation Approachcited by 7
  22. 2024ModelVerification.jl: a Comprehensive Toolbox for Formally Verifying Deep Neural Networkscited by 7
  23. 2024Verification of Geometric Robustness of Neural Networks via Piecewise Linear Approximation and Lipschitz Optimisationcited by 7
  24. 2022DRIP: Domain Refinement Iteration with Polytopes for Backward Reachability Analysis of Neural Feedback Loopscited by 6
  25. 2023Optimization and Optimizers for Adversarial Robustnesscited by 6
  26. 2022(De-)Randomized Smoothing for Decision Stump Ensemblescited by 5
  27. 2022Zonotope Domains for Lagrangian Neural Network Verificationcited by 5
  28. 2022Data Models for Dataset Drift Controls in Machine Learning With Optical Imagescited by 5
  29. 2022Probabilistic Verification of ReLU Neural Networks via Characteristic Functionscited by 5
  30. 2022Improving Adversarial Robustness via Joint Classification and Multiple Explicit Detection Classescited by 4
  31. 2022Global Performance Guarantees for Neural Network Models of AC Power Flowcited by 4
  32. 2022Tight Certification of Adversarially Trained Neural Networks via Nonconvex Low-Rank Semidefinite Relaxationscited by 4
  33. 2023GPU-Accelerated Verification of Machine Learning Models for Power Systemscited by 4
  34. 2023Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketchingcited by 4
  35. 2025Logic Gate Neural Networks are Good for Verificationcited by 4
  36. 2021Reduced-Order Neural Network Synthesis with Robustness Guaranteescited by 3
  37. 2022Robustness Certification of Visual Perception Models via Camera Motion Smoothingcited by 3
  38. 2023Semidefinite Relaxations for Robust Multiview Triangulationcited by 3

50 most cited of 65 All 65 (JSON)