Neural Networks and (Virtual) Extended Formulations

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.