Triangulating PL functions and the existence of efficient ReLU DNNs
This work addresses a foundational problem in machine learning by establishing theoretical guarantees for efficient neural network representations, though it appears incremental as it builds on existing triangulation concepts.
The paper tackles the problem of representing piecewise linear functions with compact support as sums of simplex functions, providing a short elementary proof for the existence of efficient universal ReLU neural networks that compute all such functions of bounded complexity.
We show that every piecewise linear function $f:R^d \to R$ with compact support a polyhedron $P$ has a representation as a sum of so-called `simplex functions'. Such representations arise from degree 1 triangulations of the relative homology class (in $R^{d+1}$) bounded by $P$ and the graph of $f$, and give a short elementary proof of the existence of efficient universal ReLU neural networks that simultaneously compute all such functions $f$ of bounded complexity.