Triangulating PL functions and the existence of efficient ReLU DNNs
Danny Calegari · 2025
Read Triangulating PL functions and the existence of efficient ReLU DNNs by Danny Calegari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07137.txt.
Introduction
Danny Calegari proves a structural result about jagged functions and neural networks in a 2025 paper. A piecewise linear function is assembled from flat pieces, like a folded paper surface. Such functions are exactly what a common kind of neural network, built from ReLU units, computes.
Calegari shows any such function, living on a bounded polyhedron, splits into a sum of simple tent-like pieces tied to triangles. The splitting comes from a topological construction that fills the space between the domain and the function's graph. From that short proof falls a clean guarantee: modest networks of this type can compute every such function of bounded complexity at once.
Catalog record
| CREATOR | Danny Calegari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 11 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07137
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Triangulating PL functions and the existence of efficient ReLU DNNs Danny Calegari Abstract . We show that every piecewise linear function f : ℝ d → ℝ f:\mathbb{R}^{d}\to\mathbb{R} with compact support a polyhedron P P has a representation as a sum of simplex functions . Such representations arise from degree 1 triangulations of the relative homology class (in ℝ d + 1 \mathbb{R}^{d+1} ) bounded by P P and the graph of f f , and give a short elementary proof of the existence of efficient universal ReLU neural networks that simultaneously compute all such functions f f of bounded complexity. 1. Introduction The purpose of this note is to give a short proof of a normal form theorem for piecewise-linear functions \mathbb{R}^{d}\to\mathbb{R} of compact support, which gives rise to a fixed architecture ReLU neural network capable of computing all such functions (of fixed complexity). The proof is direct and constructive and gives more or less optimal constants, and is (from the perspective of a topologist) much more elementary than existing proofs in the literature. We emphasize that this is a new proof of a well-known theorem with many well-known proofs in the literature (see e.g. [ 7 ] Chapter 5 especially Theorem 5.14, and e.g. [ 1 , 4 , 5 , 6 , 7 , 9 , 10 ] ) The proofs in these references all rely on the efficient representation of PL functions as sums of functions of an explicit sort, and our proof is no exception. The novelty of our method (such as it is) is that our representation is tied directly to the combinatorial (simplicial) structure of the graph of the function in question, so that firstly its meaning is more transparent and it may be computed very easily, and secondly one may obtain lower bounds on the complexity of the representation by geometric methods (explicitly: hyperbolic geometry). Thus we hope to suggest an analogy to other well-known contexts in theoretical computer science where there is a direct connection between hyperbolic volume and computational complexity — e.g. the Sleator–Tarjan–Thurston theory of rotations of binary trees [ 8 ] , or the Cohn–Kenyon–Propp theory of entropy of dimer tilings [ 2 ] . 2. An approximation theorem Fix a dimension d and an integer n . Let \mathcal{PL}(d,n) be the class of piecewise-linear functions from \mathbb{R}^{d} to \mathbb{R} with compact support which are linear on a triangular mesh of at most n simplices (and zero away from these simplices). We first define the class of simplex functions . The meaning of these functions is very simple: take a simplex \Delta in \mathbb{R}^{d+1} made of rubber, and ‘drop’ it vertically onto \mathbb{R}^{d} . It will deform into a pyramid whose base is a rather simple polyhedron in \mathbb{R}^{d} , and whose height at every point p is the length of the intersection of the vertical line through p with \Delta . A simplex function is the function whose graph is the top of this pyramid. Definition 2.1 (Simplex function) . Say that an d+1 -simplex in \mathbb{R}^{d+1} is nondegenerate if it is full dimensional in \mathbb{R}^{d+1} , and if no face of \Delta is vertical (i.e. the image of every face of \Delta is a full dimensional d -simplex in \mathbb{R}^{d} ). The simplex function \tau(\Delta):\mathbb{R}^{d}\to\mathbb{R} is the element of \mathcal{PL}(d,n) whose value at a point x\in\mathbb{R}^{d} is the length of the segment \ell_{x}\cap\Delta , where \ell_{x} is the vertical line in \mathbb{R}^{d+1} whose first d coordinates give x . Lemma 2.2 (Max-min normal form for simplex function) . Let \tau(\Delta):\mathbb{R}^{d}\to\mathbb{R} be a simplex function. Then there are at most d^{2} linear functions g_{1},\cdots,g_{d^{2}}:\mathbb{R}^{d}\to\mathbb{R} so that \tau(\Delta)=\max\left(0,\min_{i}g_{i}\right) Consequently there is a fixed ReLU neural network T with (1) depth at most 2\log_{2}(d)+2 ; (2) width at most d^{2}C_{1} ; and (3) size at most d^{2}C_{2} so that for every simplex function \tau(\Delta) there is some assignment of weights and biases to T that computes \tau . Proof. It is well-known (and elementary) how to construct a simple depth 1 ReLU neural network that can compute \max or \min of two real-valued inputs. Thus the lemma is proved if we can exhibit a description of \tau of the desired form. Let P\subset\mathbb{R}^{d} be the image of \Delta under orthogonal projection. By nondegeneracy, the image of each face of \Delta is a full dimensional simplex. Thus P is the convex hull of one of these simplices D and an additional point q\in\mathbb{R}^{d} which is the image of a vertex \hat{q} of \Delta . The polyhedron P therefore has at most d^{2} faces, which are the projections of some of the codimension 2 faces of \Delta (the correct upper bound is quadratic in d ; there is no point writing down a precise number). We claim that the graph of \tau (in \mathbb{R}^{d+1} ) is the top of a pyramid with base P and apex a point \hat{p} projecting to some p in the interior of P . This is an exercise in elementary Euclidean geometry, but it is easy enough to give a sketch of a proof, which explains the meaning of \hat{p} and p . Extend the faces of D to planes in \mathbb{R}^{d} so that they form a hyperplane arrangement. The point q is in one of the chambers of this arrangement, dual to a face F of D which is the image of a face \hat{F} of \Delta . Let \hat{F}^{\prime} be the face of \Delta spanned by the vertices of \Delta-\hat{F} and \hat{q} , and let F^{\prime} be the projection of \hat{F}^{\prime} . Then F and F^{\prime} intersect transversely at a point p\in P , and the graph of \tau(\Delta) is a pyramid, obtained by coning P to a point \hat{p} in \mathbb{R}^{d+1} mapping to p , and such that the last coordinate of \hat{p} is \tau(p) . In particular, if we triangulate P by coning its faces to p (which gives a decomposition into at most d^{2} simplices) then \tau is linear on each of these simplices; and if g_{i} are the linear functions that agree with \tau on these simplices, then \tau=\min_{i}g_{i} on P . Since \tau is 0 outside P , we have \tau=\max(0,(\min_{i}g_{i})) as claimed. ∎ Remark 2.3 . It is easy to write a simplex function as a bounded linear sum of simplex functions each of which is the max of the min of d+\text{constant} linear functions, but explaining this detail seems superfluous for a note whose virtue is its brevity. Theorem 2.4 . Any f\in\mathcal{PL}(d,n) may be written as the sum of at most 2n simplex functions. Hence there are small, easily estimated constants C_{0},C_{1},C_{2} so that for any d and n there is a ReLU neural network \Phi with (1) depth at most 2\log_{2}(d)+C_{0} ; (2) width at most d^{2}nC_{1} ; and (3) size at most d^{2}nC_{2} so that for every f\in\mathcal{PL}(d,n) there is some assignment of weights and biases to \Phi that computes f . Proof. Let’s pick a function f in \mathcal{PL}(d,n) . We may assume (by adding more simplices if necessary) that the support of f is a polyhedral ball C in \mathbb{R}^{d} which we think of as the subspace of \mathbb{R}^{d+1} with last coordinate