Lower Bounds on Neural Network Depth via (Lattice) Polytopes

This talk will be centered around the following open problem about neural networks with rectified linear units (ReLUs): What is the minimum number of hidden layers required to represent every continuous piecewise linear function with input dimension n? While it is known that log(n) layers are always sufficient, no lower bound larger than 2 has been proven so far. We conjecture that the logarithmic upper bound is indeed the true answer. We provide evidence for our conjecture by proving special cases using methods from mixed-integer programming and polyhedral theory. In particular, we demonstrate how previously discovered connections between neural networks and tropical geometry can be used to translate the problem into the language of Newton polytopes. Using theory of lattice polytopes, we then prove the conjecture under some integrality assumption.

This talk is based on joint works with Amitabh Basu, Marco Di Summa, and Martin Skutella, as well as with Christian Haase and Georg Loho.