13 papers
Shallower ReLU Network Representations via Exact Linear Algebra
Kilian RueÃ, Gennadiy Averkov, Florestan Brunck +7
We prove that the maximum of real numbers is exactly representable by a ReLU network with two hidden layers for every . The constructions are obtained by reducing the…
Decomposition Polyhedra of Piecewise Linear Functions
Marie-Charlotte Brandenburg, Moritz Grillo, Christoph Hertrich
In this paper we contribute to the frequently studied question of how to decompose a continuous piecewise linear (CPWL) function into a difference of two convex CPWL functions. Eve…
Neural Networks and (Virtual) Extended Formulations
Christoph Hertrich, Georg Loho
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 ma…
Better Neural Network Expressivity: Subdividing the Simplex
Egor Bakaev, Florestan Brunck, Christoph Hertrich +2
This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that hidden layers are suffi…
The Computational Complexity of Counting Linear Regions in ReLU Neural Networks
Moritz Stargalla, Christoph Hertrich, Daniel Reichman
An established measure of the expressive power of a given ReLU neural network is the number of linear regions into which it partitions the input space. There exist many different,…
Arithmetic Circuits and Neural Networks for Regular Matroids
Christoph Hertrich, Stefan Kober, Georg Loho
We prove that there exist uniform -circuits of size to compute the basis generating polynomial of regular matroids on elements. By tropicalization, this…