# When Deep Learning Meets Polyhedral Theory: A Survey

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 209 of its 363 references that are in the map.
- First posted on arXiv 29 Apr 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Hierarchical Text-Conditional Image Generation with CLIP Latents](https://mlsanity.com/paper/2204.06125/) (2022)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Intriguing properties of neural networks](https://mlsanity.com/paper/1312.6199/) (2013)
- [MobileNetV2: Inverted Residuals and Linear Bottlenecks](https://mlsanity.com/paper/1801.04381/) (2018)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [SpecAugment: A Simple Data Augmentation Method for Automatic Speech Recognition](https://mlsanity.com/paper/1904.08779/) (2019)
- [Self-training with Noisy Student improves ImageNet classification](https://mlsanity.com/paper/1911.04252/) (2019)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Deep Learning in Neural Networks: An Overview](https://mlsanity.com/paper/1404.7828/) (2014)
- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [VectorNet: Encoding HD Maps and Agent Dynamics from Vectorized Representation](https://mlsanity.com/paper/2005.04259/) (2020)
- [Efficient Neural Network Robustness Certification with General Activation Functions](https://mlsanity.com/paper/1811.00866/) (2018)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)

## Built on by (most cited first, 30 of 39)

- [Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes](https://mlsanity.com/paper/2501.00200/) (2024)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Topological Expressivity of ReLU Neural Networks](https://mlsanity.com/paper/2310.11130/) (2023)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs](https://mlsanity.com/paper/2312.08074/) (2023)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [The Computational Complexity of Counting Linear Regions in ReLU Neural Networks](https://mlsanity.com/paper/2505.16716/) (2025)
- [Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks](https://mlsanity.com/paper/2312.16699/) (2023)
- [Generating Likely Counterfactuals Using Sum-Product Networks](https://mlsanity.com/paper/2401.14086/) (2024)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Reinforcement learning with combinatorial actions for coupled restless bandits](https://mlsanity.com/paper/2503.01919/) (2025)
- [Time to Spike? Understanding the Representational Power of Spiking Neural Networks in Discrete Time](https://mlsanity.com/paper/2505.18023/) (2025)
- [Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming](https://mlsanity.com/paper/2602.16944/) (2026)
- [Deep Learning for Two-Stage Robust Integer Optimization](https://mlsanity.com/paper/2310.04345/) (2023)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification](https://mlsanity.com/paper/2410.06816/) (2024)
- [Relating Piecewise Linear Kolmogorov Arnold Networks to ReLU Networks](https://mlsanity.com/paper/2503.01702/) (2025)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [A rank decomposition for the topological classification of neural representations](https://mlsanity.com/paper/2404.19710/) (2024)
- [A Computational Tropical Geometry Framework for Neural Networks](https://mlsanity.com/paper/2405.20174/) (2024)
- [Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees](https://mlsanity.com/paper/2506.03531/) (2025)
- [Decision-focused predictions via pessimistic bilevel optimization: complexity and algorithms](https://mlsanity.com/paper/2312.17640/) (2023)
- [Parallel Algorithms for Exact Enumeration of Deep Neural Network Activation Regions](https://mlsanity.com/paper/2403.00860/) (2024)
- [Implicit Hypersurface Approximation Capacity in Deep ReLU Networks](https://mlsanity.com/paper/2407.03851/) (2024)

## Abstract (arXiv)

In the past decade, deep learning became the prevalent methodology for predictive modeling thanks to the remarkable accuracy of deep neural networks in tasks such as computer vision and natural language processing. Meanwhile, the structure of neural networks converged back to simpler representations based on piecewise constant and piecewise linear functions such as the Rectified Linear Unit (ReLU), which became the most commonly used type of activation function in neural networks. That made certain types of network structure unicodex2014such as the typical fully-connected feedforward neural networkunicodex2014 amenable to analysis through polyhedral theory and to the application of methodologies such as Linear Programming (LP) and Mixed-Integer Linear Programming (MILP) for a variety of purposes. In this paper, we survey the main topics emerging from this fast-paced area of work, which bring a fresh perspective to understanding neural networks in more detail as well as to applying linear optimization techniques to train, verify, and reduce the size of such networks.