mlsanityData to 7 Oct 2026

Robustness Verification of Polynomial Neural Networks

arXiv 2602.06105 ↗First posted 5 Feb 2026stat.ML cs.LG math.AGcited by 3

Not on the map. Why?

Abstract (arXiv)

We study robustness verification of neural networks via metric algebraic geometry. For polynomial neural networks, certifying a robustness radius amounts to computing the distance to the algebraic decision boundary. We use the Euclidean distance (ED) degree as an intrinsic measure of the complexity of this problem, analyze the associated ED discriminant, and introduce a parameter discriminant that detects parameter values at which the ED degree drops. We derive formulas for the ED degree for several network architectures and characterize the expected number of real critical points in the infinite-width limit. We develop symbolic elimination methods to compute these quantities and homotopy-continuation methods for exact robustness certification. Finally, experiments on lightning self-attention modules reveal decision boundaries with strictly smaller ED degree than generic cubic hypersurfaces of the same ambient dimension.

Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 27 of its 61 references that are in the map. First posted on arXiv 5 Feb 2026.

Builds on

27 of 61 references.

References · 27

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2016Towards Evaluating the Robustness of Neural Networkscited by 2,976
  3. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  4. 2017Deep Neural Networks as Gaussian Processescited by 617
  5. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  6. 2018Efficient Neural Network Robustness Certification with General Activation Functionscited by 439
  7. 2018Certified Defenses against Adversarial Examplescited by 305
  8. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  9. 2017Formal Guarantees on the Robustness of a Classifier against Adversarial Manipulationcited by 182
  10. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 124
  11. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  12. 2019On the Expressive Power of Deep Polynomial Neural Networkscited by 65
15 more
  1. 2023First Three Years of the International Verification of Neural Networks Competition (VNN-COMP)cited by 58
  2. 2022Adversarial Robustness of Deep Neural Networks: A Survey from a Formal Verification Perspectivecited by 41
  3. 2021Geometry of Linear Convolutional Networkscited by 27
  4. 2024The Real Tropical Geometry of Neural Networkscited by 23
  5. 2024Geometry of Polynomial Neural Networkscited by 21
  6. 2024Geometry of Lightning Self-Attention: Identifiability and Dimensioncited by 16
  7. 2013The Euclidean distance degree of an algebraic varietycited by 15
  8. 2025Identifiability of Deep Polynomial Neural Networkscited by 12
  9. 2022Abstraction and Refinement: Towards Scalable and Exact Verification of Neural Networkscited by 11
  10. 2020Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approachcited by 6
  11. 2024SoundnessBench: A Soundness Benchmark for Neural Network Verifierscited by 5
  12. 2025Constraining the outputs of ReLU neural networkscited by 3
  13. 2024Complexity of Injectivity and Verification of ReLU Neural Networkscited by 2
  14. 2014The Euclidean Distance Degree of Fermat Hypersurfacescited by 1
  15. 2025Euclidean distance degree in manifold optimizationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Algebraic Invariants of Lightning Self-Attentioncited by 1
  2. 2026Stress-Testing Neural Network Verifiers with Provably Robust Instancescited by 0
  3. 2026Singular Learning and Occam's Razor in Deep Monomial Networkscited by 0