Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes

Christian Alexander Haase; Christoph Hertrich; Georg Loho

ICLR 2023poster23 citations

Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes

Christian Alexander Haase, Christoph Hertrich, Georg Loho

Abstract

We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that $\lceil\log_2(n)\rceil$ hidden layers are indeed necessary to compute the maximum of $n$ numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument on the normalized volume of faces of such polytopes.

Rectified Linear UnitNeural Network ExpressivityNeural Network DepthLattice PolytopeNormalized Volume

BibTeX

@inproceedings{
haase2023lower,
title={Lower Bounds on the Depth of Integral Re{LU} Neural Networks via Lattice Polytopes},
author={Christian Alexander Haase and Christoph Hertrich and Georg Loho},
booktitle={The Eleventh International Conference on Learning Representations },
year={2023},
url={https://openreview.net/forum?id=2mvALOAWaxY}
}