Neural Networks and (Virtual) Extended Formulations
SIAM Journal on Mathematics of Data Science · 31.12.2026 · 8 (4) · 1350-1369
DOI: 10.1137/25m180130x ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 09.11.2026. Verfasst von Christoph Hertrich und 1 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Gefördert von: Horizon 2020 Framework Programme.
Abstract (Originalsprache)
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 [Formula: see text] of a polytope [Formula: see text]. This is a well-studied quantity in combinatorial optimization and polyhedral geometry describing the number of inequalities needed to model [Formula: see text] as a linear program. We show that [Formula: see text] is a lower bound on the size of any monotone or input-convex neural network that solves the linear optimization problem over [Formula: see text]. 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 [Formula: see text], which generalizes [Formula: see text] and describes the number of inequalities needed to represent the linear optimization problem over [Formula: see text] as a difference of two linear programs. We prove that [Formula: see text] is a lower bound on the size of any neural network that optimizes over [Formula: see text]. While it remains an open question to derive useful lower bounds on [Formula: see text], we argue that this quantity deserves to be studied independently from neural networks by proving that one can efficiently optimize over a polytope [Formula: see text] given a virtual extended formulation with small encoding size.
Förderung
- Horizon 2020 Framework Programme
Zitieren
APA
Hertrich, C., & Loho, G. (2026). Neural Networks and (Virtual) Extended Formulations. SIAM Journal on Mathematics of Data Science, 8(4), 1350-1369. https://doi.org/10.1137/25m180130x
Vancouver
Hertrich C, Loho G. Neural Networks and (Virtual) Extended Formulations. SIAM Journal on Mathematics of Data Science. 2026;8(4):1350-1369. doi:10.1137/25m180130x
BibTeX
@article{Hertrich2026,
author = {Hertrich, Christoph and Loho, Georg},
title = {Neural Networks and (Virtual) Extended Formulations},
journal = {SIAM Journal on Mathematics of Data Science},
year = {2026},
volume = {8},
number = {4},
pages = {1350--1369},
doi = {10.1137/25m180130x}
}
EUVIMED