# Neural Networks and (Virtual) Extended Formulations

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 54 references that are in the map.
- First posted on arXiv 5 Nov 2024.

## Builds on (most cited first, 19 of 19)

- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Lower bounds over Boolean inputs for deep neural networks with ReLU gates](https://mlsanity.com/paper/1711.03073/) (2017)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Size and depth of monotone neural networks: interpolation and approximation](https://mlsanity.com/paper/2207.05275/) (2022)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [CDiNN -Convex Difference Neural Networks](https://mlsanity.com/paper/2103.17231/) (2021)
- [Strengthening Convex Relaxations of 0/1-Sets Using Boolean Formulas](https://mlsanity.com/paper/1711.01358/) (2017)
- [Which Nonnegative Matrices Are Slack Matrices?](https://mlsanity.com/paper/1303.5670/) (2013)

## Built on by (most cited first, 9 of 9)

- [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)
- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Parameterized Hardness of Zonotope Containment and Neural Network Verification](https://mlsanity.com/paper/2509.22849/) (2025)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [Maxout Polytopes](https://mlsanity.com/paper/2509.21286/) (2025)
- [On the expressivity of sparse maxout networks](https://mlsanity.com/paper/2510.14068/) (2025)
- [Two Linear Programs are Better than One](https://mlsanity.com/paper/2610.15909/) (2026)

## Abstract (arXiv)

Neural networks with piecewise linear activation functions, such as rectified linear units (ReLU) or maxout, are among the most fundamental models in modern machine learning. We make a step towards proving lower bounds on the size of such neural networks by linking their representative capabilities to the notion of the extension complexity xc(P) of a polytope P. This is a well-studied quantity in combinatorial optimization and polyhedral geometry describing the number of inequalities needed to model P as a linear program. We show that xc(P) is a lower bound on the size of any monotone or input-convex neural network that solves the linear optimization problem over P. This implies exponential lower bounds on such neural networks for a variety of problems, including the polynomially solvable maximum weight matching problem. In an attempt to prove similar bounds also for general neural networks, we introduce the notion of virtual extension complexity vxc(P), which generalizes xc(P) and describes the number of inequalities needed to represent the linear optimization problem over P as a difference of two linear programs. We prove that vxc(P) is a lower bound on the size of any neural network that optimizes over P. While it remains an open question to derive useful lower bounds on vxc(P), we argue that this quantity deserves to be studied independently from neural networks by proving that one can efficiently optimize over a polytope P given a virtual extended formulation with small encoding size.