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

arXiv: https://arxiv.org/abs/2410.23362 · HTML: https://mlsanity.com/paper/2410.23362/

## Key facts

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

## Builds on (most cited first, 30 of 36)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [A Dual Approach to Scalable Verification of Deep Networks](https://mlsanity.com/paper/1803.06567/) (2018)
- [A Convex Relaxation Barrier to Tight Robustness Verification of Neural Networks](https://mlsanity.com/paper/1902.08722/) (2019)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [SoK: Certified Robustness for Deep Neural Networks](https://mlsanity.com/paper/2009.04131/) (2020)
- [General Cutting Planes for Bound-Propagation-Based Neural Network Verification](https://mlsanity.com/paper/2208.05740/) (2022)
- [Maximum Resilience of Artificial Neural Networks](https://mlsanity.com/paper/1705.01040/) (2017)
- [Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound](https://mlsanity.com/paper/2205.00263/) (2022)
- [Measuring Neural Net Robustness with Constraints](https://mlsanity.com/paper/1605.07262/) (2016)
- [PRIMA: General and Precise Neural Network Certification via Scalable Convex Hull Approximations](https://mlsanity.com/paper/2103.03638/) (2021)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (2020)
- [Global Deterministic Optimization with Artificial Neural Networks Embedded](https://mlsanity.com/paper/1801.07114/) (2018)
- [Empirical Bounds on Linear Regions of Deep Rectifier Networks](https://mlsanity.com/paper/1810.03370/) (2018)
- [Individual Fairness Guarantees for Neural Networks](https://mlsanity.com/paper/2205.05763/) (2022)
- [Scaling Up Exact Neural Network Compression by ReLU Stability](https://mlsanity.com/paper/2102.07804/) (2021)
- [Convex Bounds on the Softmax Function with Applications to Robustness Verification](https://mlsanity.com/paper/2303.01713/) (2023)
- [Combinatorial Attacks on Binarized Neural Networks](https://mlsanity.com/paper/1810.03538/) (2018)
- [Between steps: Intermediate relaxations between big-M and convex hull formulations](https://mlsanity.com/paper/2101.12708/) (2021)
- [Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling](https://mlsanity.com/paper/2205.14189/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regions](https://mlsanity.com/paper/2301.07966/) (2023)
- [PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs](https://mlsanity.com/paper/2312.08074/) (2023)

## 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.