mlsanityData to 7 Oct 2026

Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations

arXiv 2410.23362 ↗First posted 30 Oct 2024math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

The non-convex nature of trained neural networks has created significant obstacles in their incorporation into optimization models. In this context, Anderson et al. (2020) provided a framework to obtain the convex hull of the graph of a piecewise linear convex activation function composed with an affine function; this effectively convexifies activations such as the ReLU together with the affine transformation that precedes it. In this article, we contribute to this line of work by developing a recursive formula that yields a tight convexification for the composition of an activation with an affine function for a wide scope of activation functions, namely, convex or ``S-shaped". Our approach can be used to efficiently compute separating hyperplanes or determine that none exists in various settings, including non-polyhedral cases.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 36 of its 81 references that are in the map. First posted on arXiv 30 Oct 2024.

Builds on

36 of 81 references.

References · 36

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  3. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  4. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  5. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  6. 2018A Dual Approach to Scalable Verification of Deep Networkscited by 125
  7. 2019A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networkscited by 124
  8. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  9. 2022General Cutting Planes for Bound-Propagation-Based Neural Network Verificationcited by 102
  10. 2020SoK: Certified Robustness for Deep Neural Networkscited by 100
  11. 2017Maximum Resilience of Artificial Neural Networkscited by 97
  12. 2022Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Boundcited by 92
24 more
  1. 2016Measuring Neural Net Robustness with Constraintscited by 90
  2. 2021PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximationscited by 77
  3. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  4. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  5. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  6. 2024The SCIP Optimization Suite 9.0cited by 37
  7. 2020Lossless Compression of Deep Neural Networkscited by 34
  8. 2018Global Deterministic Optimization with Artificial Neural Networks Embeddedcited by 32
  9. 2018Empirical Bounds on Linear Regions of Deep Rectifier Networkscited by 23
  10. 2022Individual Fairness Guarantees for Neural Networkscited by 23
  11. 2021Scaling Up Exact Neural Network Compression by ReLU Stabilitycited by 19
  12. 2023Convex Bounds on the Softmax Function with Applications to Robustness Verificationcited by 19
  13. 2018Combinatorial Attacks on Binarized Neural Networkscited by 11
  14. 2021Between steps: Intermediate relaxations between big-M and convex hull formulationscited by 11
  15. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  16. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  17. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  18. 2023PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programscited by 8
  19. 2022P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraintscited by 7
  20. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  21. 2024Bound Tightening using Rolling-Horizon Decomposition for Neural Network Verificationcited by 6
  22. 2021A Primer on Multi-Neuron Relaxation-based Adversarial Robustness Certificationcited by 2
  23. 2019Using two-dimensional Projections for Stronger Separation and Propagation of Bilinear Termscited by 1
  24. 2021Convex envelopes for ray-concave functionscited by 1

Built on by

Not cited yet.