Dependencies

Let \(n \ge 1\) and \(k \ge 0\). If \(\Delta _{n-1}\) admits a polyhedral subdivision \(Q_1, \dots , Q_m\) with \(Q_i \in \mathcal{P}_k\) for all \(i\), then \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,k}\).

For every \(n \ge 4\) we have \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,\, \lceil \log _3(n-2)\rceil + 1}\).

For every \(n \ge 1\) we have \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,\, 2\lceil \log _5 n \rceil }\).

\(\mathrm{MAX}_4 \in \mathrm{ReLU}_{4,2}\), realized geometrically by the rhombic-pyramid subdivision (a network different from the binary tree construction).

\(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\). (Alternative, geometric proof of Proposition 42.)

The convex hull \(\mathrm{conv}(A)\) of a set \(A \subseteq \mathbb {R}^d\) is the smallest convex set containing \(A\).

A function \(f\colon \mathbb {R}^n \to \mathbb {R}\) is continuous piecewise linear (CPWL) if \(f\) is continuous and there exist finitely many affine functions \(g_1, \dots , g_p \colon \mathbb {R}^n \to \mathbb {R}\) such that for every \(x \in \mathbb {R}^n\) there is an index \(i\) with \(f(x) = g_i(x)\). We write \(\mathrm{CPWL}_n\) for the set of all CPWL functions on \(\mathbb {R}^n\); it is a real vector space under pointwise operations.

In \(\mathbb {R}^3\) let

and let \(x_{ij} = \tfrac 12(x_i + x_j)\) denote midpoints. Define the tetrahedron \(T = \mathrm{conv}\{ x_1, x_2, x_3, x_4\} \) and the four pyramids

each listed as apex; base.

Let \(P \subseteq \mathbb {R}^d\) be a polytope and \(u \in \mathbb {R}^d\). The face of \(P\) in direction \(u\) is

the set of maximizers of \(\langle u, \cdot \rangle \) over \(P\); it is nonempty by compactness. A face of \(P\) is any set of this form (taking \(u = 0\) gives \(P\) itself).

A polytope \(X\) is a formal Minkowski difference of polytopes \(P\) and \(Q\) if \(X + P = Q\).

For \(P, Q \subseteq \mathbb {R}^d\) define \(P * Q = \mathrm{conv}(P \cup Q)\).

Define \(M \colon \mathbb {R}^5 \to \mathbb {R}\) by

For \(n \ge 1\), the function \(\mathrm{MAX}_n \colon \mathbb {R}^n \to \mathbb {R}\) is defined by

It is a member of \(\mathrm{CPWL}_n\).

For \(P, Q \subseteq \mathbb {R}^d\), the Minkowski sum is \(P + Q = \{ p + q : p \in P,\ q \in Q\} \).

For a convex, positively homogeneous \(f \in \mathrm{CPWL}_d\), the Newton polytope \(N(f)\) is the unique polytope \(P\) with \(f = h_P\) provided by Theorem 79.

Define \(P_1 \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(P_2 \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(P_3 \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(P_4 \colon \mathbb {R}^5 \to \mathbb {R}\) by

Fix the ambient dimension \(d\). Let \(\mathcal{P}_0\) be the set of one-point subsets of \(\mathbb {R}^d\). For \(k \ge 0\) define

where the sum is a Minkowski sum.

A polyhedral subdivision of a polytope \(X\) is a finite collection \(Q_1, \dots , Q_m\) of polytopes with \(X = \bigcup _i Q_i\) such that for all \(i \neq j\) the intersection \(Q_i \cap Q_j\) is either empty or a face of both \(Q_i\) and \(Q_j\).

A polytope in \(\mathbb {R}^d\) is the convex hull of a nonempty finite set of points.

Define \(Q \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(R_{13} \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(R_{14} \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(R_{23} \colon \mathbb {R}^5 \to \mathbb {R}\) by

Define \(R_{24} \colon \mathbb {R}^5 \to \mathbb {R}\) by

The rectified linear unit is the function \(\mathrm{ReLU}\colon \mathbb {R} \to \mathbb {R}\) defined by \(\mathrm{ReLU}(x) = \max \{ 0, x\} \). Applied to a vector, \(\mathrm{ReLU}\) acts component-wise.

A ReLU network with \(k\) hidden layers (equivalently, of depth \(k+1\)) on \(\mathbb {R}^n\) is a tuple of affine transformations \(T^{(i)}\colon \mathbb {R}^{n_{i-1}} \to \mathbb {R}^{n_i}\) for \(i = 1, \dots , k+1\), where \(n_0 = n\) and \(n_{k+1} = 1\). The network computes the function

the alternating composition of the affine maps with component-wise applications of \(\mathrm{ReLU}\). The entries of the matrices and translation vectors of the \(T^{(i)}\) are the weights and biases of the network.

For integers \(n \ge 1\) and \(k \ge 0\), denote by \(\mathrm{ReLU}_{n,k}\) the set of all functions \(f\colon \mathbb {R}^n \to \mathbb {R}\) computed by some ReLU network with at most \(k\) hidden layers. (For \(k = 0\) these are exactly the affine functions.)

The \((n-1)\)-dimensional standard simplex is \(\Delta _{n-1} = \mathrm{conv}\{ e_1, \dots , e_n\} \subseteq \mathbb {R}^n\), where \(e_i\) is the \(i\)-th standard unit vector; equivalently, the set of componentwise nonnegative vectors with coordinate sum \(1\).

Let \(K \subseteq \mathbb {R}^d\) be a nonempty compact convex set. Its support function \(h_K \colon \mathbb {R}^d \to \mathbb {R}\) is

the maximum being attained by compactness and continuity.

Let \(a, b \ge 0\) with \(a + b \ge 1\). Define \(T_{a,b} \colon \mathbb {R}^{4a+b} \to \mathbb {R}\) as the maximum of \(a\) block terms of the form \(\max (\cdot ,\cdot ) + \max (\cdot ,\cdot )\) and \(b\) extra arguments:

Let \(a, b \ge 0\) with \(a + b \ge 1\) and let \(d \ge 1\). Define \(\mathcal{T}_{a,b}^{(d)}\) as the linear span of the functions \(T_{a,b} \circ L\) where \(L \colon \mathbb {R}^d \to \mathbb {R}^{4a+b}\) ranges over all linear maps. (The paper works with the square case \(d = 4a+b\) and passes to other \(d\) by “ignoring coordinates”; the formulation with an arbitrary source dimension makes those steps literal inclusions.)

For every \(n \ge 1\) and every \(d \ge 1\),

Let \(a, b \ge 0\) with \(a + b \ge 1\), put \(i = 4a+b\), and let \(S \colon \mathbb {R}^{i+4} \to \mathbb {R}^5\) be given by \(S(x) = (x_{i+1}, x_{i+2}, x_{i+3}, x_{i+4}, T_{a,b}(x_1, \dots , x_i))\). Then \(P_j \circ S \in \mathcal{T}_{a+1,b+1}^{(i+4)}\) for each \(j \in \{ 1, 2, 3, 4\} \).

In the setting of Lemma 52, \(Q \circ S \in \mathcal{T}_{a,b+2}^{(i+4)}\).

In the setting of Lemma 52, \(R_{13} \circ S,\ R_{14} \circ S,\ R_{23} \circ S,\ R_{24} \circ S \in \mathcal{T}_{a,b+3}^{(i+4)}\).

Let \(F \subseteq \mathbb {R}^d\) be a polytope contained in an affine hyperplane \(H\), let \(v \in \mathbb {R}^d \setminus H\), and let \(Q_1, \dots , Q_m\) be a polyhedral subdivision of \(F\). Then \(v * Q_1, \dots , v * Q_m\) is a polyhedral subdivision of \(v * F\).

For each \(i\), \(Q^{(i)} = p_i * Z_i\), where \(p_i\) is the apex and \(Z_i\) is the base parallelogram, a Minkowski sum of two segments. Consequently \(Z_i \in \mathcal{P}_1\) and \(Q^{(i)} \in \mathcal{P}_2\).

Let \(P\) be a polytope, \(F\) a face of \(P\), and \(G\) a face of \(F\). Then \(G\) is a face of \(P\).

Let \(P\) be a polytope and let \(F_u(P)\), \(F_v(P)\) be faces with \(F_u(P) \cap F_v(P) \neq \emptyset \). Then \(F_u(P) \cap F_v(P) = F_{u+v}(P)\) is a face of \(P\).

Let \(P, Q\) be polytopes and \(u \in \mathbb {R}^d\). Then

In particular every face of \(P * Q\) is a face of \(P\), a face of \(Q\), or a join of a face of \(P\) with a face of \(Q\).

Let \(P = \mathrm{conv}\{ v_1, \dots , v_m\} \) and \(u \in \mathbb {R}^d\). Then \(F_u(P) = \mathrm{conv}\{ v_i : \langle u, v_i\rangle = h_P(u)\} \); in particular every face of a polytope is a polytope.

Let \(P, Q\) be polytopes and \(u \in \mathbb {R}^d\). Then \(F_u(P + Q) = F_u(P) + F_u(Q)\). In particular every face of \(P + Q\) is a Minkowski sum of a face of \(P\) and a face of \(Q\).

Let \(X\) and \(Q_1, \dots , Q_m\) be polytopes in \(\mathbb {R}^n\) with \(X = \bigcup _{i \in [m]} Q_i\). For \(\emptyset \neq S \subseteq [m]\) write \(Q_S = \bigcap _{i \in S} Q_i\). Let \(\mathcal{T}^0\) be the collection of nonempty sets \(S \subseteq [m]\) of even size with \(Q_S \neq \emptyset \), and \(\mathcal{T}^1\) the collection of sets \(S \subseteq [m]\) of odd size with \(Q_S \neq \emptyset \). Then

For all \(A, B \subseteq \mathbb {R}^d\), \(\mathrm{conv}(A) + \mathrm{conv}(B) = \mathrm{conv}(A + B)\). In particular, the Minkowski sum of two polytopes is a polytope.

The identity function \(x \mapsto x\) on \(\mathbb {R}\) lies in \(\mathrm{ReLU}_{1,1}\).

For all \(P, Q, R \subseteq \mathbb {R}^d\),

Let \(a \ge 1\), \(b \ge 0\) and \(k \ge 0\). If \(T_{0,a+b} \in \mathrm{ReLU}_{a+b,\, k}\) then \(T_{a,b} \in \mathrm{ReLU}_{4a+b,\, k+1}\).

Let \(x \in \mathbb {R}^5\) with \(x_1 \ge x_i\) for \(i = 2, \dots , 5\). Then \(M(x) = x_1\).

Let \(x \in \mathbb {R}^5\) with \(x_5 \ge x_i\) for \(i = 1, \dots , 4\). Then \(M(x) = x_5\).

For all \(x \in \mathbb {R}^5\), \(M(x_2, x_1, x_3, x_4, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

For all \(x \in \mathbb {R}^5\), \(M(x_1, x_2, x_4, x_3, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

For all \(x \in \mathbb {R}^5\), \(M(x_3, x_4, x_1, x_2, x_5) = M(x_1, x_2, x_3, x_4, x_5)\).

\(M \in \mathrm{ReLU}_{5,2}\).

For all real numbers \(a, b, c, d\),

For every \(n \ge 1\) we have \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,\lceil \log _2 n \rceil }\).

Let \(1 \le m \le n\) and \(k \ge 0\). If \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,k}\) then \(\mathrm{MAX}_m \in \mathrm{ReLU}_{m,k}\).

\(\mathrm{MAX}_2 \in \mathrm{ReLU}_{2,1}\).

\(\mathrm{MAX}_3 \notin \mathrm{ReLU}_{3,1}\); that is, two hidden layers are necessary to compute the maximum of three numbers.

Let \(d \ge 1\), let \(1 \le r \le 4\) and let \(g_1, \dots , g_r \colon \mathbb {R}^d \to \mathbb {R}\) be affine. Then \(x \mapsto \max (g_1(x), \dots , g_r(x))\) lies in \(\mathrm{ReLU}_{d,2}\).

For every \(n \ge 1\) we have \(h_{\Delta _{n-1}} = \mathrm{MAX}_n\); equivalently, \(N(\mathrm{MAX}_n) = \Delta _{n-1}\).

For all \(x \in \mathbb {R}^5\),

For all \(x \in \mathbb {R}^5\),

For all \(x \in \mathbb {R}^5\),

For all \(x \in \mathbb {R}^5\),

Let \(f \in \mathrm{CPWL}_d\) be convex and positively homogeneous. Then there exist finitely many vectors \(a_1, \dots , a_m \in \mathbb {R}^d\) with \(f(x) = \max _i \langle a_i, x\rangle \) for all \(x\).

Let \(A \colon \mathbb {R}^d \to \mathbb {R}^d\) be an affine map and let \(P \in \mathcal{P}_k\). Then \(A(P) \in \mathcal{P}_k\).

Let \(k \ge 0\), \(P \in \mathcal{P}_k\), and let \(F\) be a face of \(P\). Then \(F \in \mathcal{P}_k\).

For every \(k \ge 0\) we have \(\mathcal{P}_k \subseteq \mathcal{P}_{k+1}\).

For every \(k \ge 0\), every member of \(\mathcal{P}_k\) is a polytope.

Let \(k \ge 0\) and \(P, Q \in \mathcal{P}_k\). Then \(P + Q \in \mathcal{P}_k\).

Every polytope \(P \subseteq \mathbb {R}^d\) is nonempty, compact, and convex.

For all \(n \ge 1\) and \(k \ge 0\) we have \(\mathrm{ReLU}_{n,k} \subseteq \mathrm{CPWL}_n\).

Let \(f \in \mathrm{ReLU}_{m,k}\) and let \(A\colon \mathbb {R}^n \to \mathbb {R}^m\) be affine. Then \(f \circ A \in \mathrm{ReLU}_{n,k}\).

Let \(g_1, \dots , g_m \in \mathrm{ReLU}_{n,k}\) and \(f \in \mathrm{ReLU}_{m,j}\). Then the function \(x \mapsto f(g_1(x), \dots , g_m(x))\) lies in \(\mathrm{ReLU}_{n,k+j}\).

Let \(n \ge 1\), \(k \ge 0\), let \(f_1, \dots , f_s \in \mathrm{ReLU}_{n,k}\) and \(c_1, \dots , c_s \in \mathbb {R}\). Then \(c_1 f_1 + \dots + c_s f_s \in \mathrm{ReLU}_{n,k}\).

For all \(n \ge 1\) and \(k \ge 0\) we have \(\mathrm{ReLU}_{n,k} \subseteq \mathrm{ReLU}_{n,k+1}\).

Let \(d \ge 1\) and let \(g_1, \dots , g_6 \colon \mathbb {R}^d \to \mathbb {R}\) be affine. Then the function

lies in \(\mathrm{ReLU}_{d,2}\).

For every polytope \(P \subseteq \mathbb {R}^d\), the support function \(h_P\) is convex, positively homogeneous (\(h_P(\lambda x) = \lambda h_P(x)\) for \(\lambda \ge 0\)), and CPWL.

Let \(S = \{ v_1, \dots , v_m\} \subseteq \mathbb {R}^d\) be finite and nonempty. Then for all \(x\),

Let \(K, K' \subseteq \mathbb {R}^d\) be nonempty compact convex sets with \(h_K = h_{K'}\). Then \(K = K'\).

Let \(K, K' \subseteq \mathbb {R}^d\) be nonempty compact convex sets such that \(K \cup K'\) is convex. Then \(K \cap K'\) is nonempty, compact, and convex, and \(h_{K \cap K'} = \min (h_K, h_{K'})\) pointwise.

Let \(K, K' \subseteq \mathbb {R}^d\) be nonempty compact convex sets. Then \(K * K' = \mathrm{conv}(K \cup K')\) is nonempty, compact, and convex, and \(h_{K * K'} = \max (h_K, h_{K'})\) pointwise.

Let \(K, K' \subseteq \mathbb {R}^d\) be nonempty compact convex sets. Then \(K + K'\) is nonempty, compact, and convex, and \(h_{K+K'} = h_K + h_{K'}\).

For every \(b \ge 1\) we have \(T_{0,b} = \mathrm{MAX}_b\).

Let \(a, b \ge 0\) with \(a + b \ge 1\) and put \(i = 4a + b\). For all \(x \in \mathbb {R}^{i+4}\),

Let \(a, b \ge 0\) with \(a + b \ge 1\), and let \(k \ge 0\), \(d \ge 1\). If \(T_{a,b} \in \mathrm{ReLU}_{4a+b,\, k}\) then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathrm{ReLU}_{d,k}\).

Let \(a \ge 0\), \(b \ge 1\), \(d \ge 1\). Then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathcal{T}_{a,b+1}^{(d)}\).

Let \(a \ge 0\), \(b \ge 2\), \(d \ge 1\). Then \(\mathcal{T}_{a,b}^{(d)} \subseteq \mathcal{T}_{a+1,b-2}^{(d)}\).

Let \(f \in \mathcal{T}_{a,b}^{(d)}\) and let \(L \colon \mathbb {R}^{d'} \to \mathbb {R}^{d}\) be linear. Then \(f \circ L \in \mathcal{T}_{a,b}^{(d')}\).

Let \(a, b \ge 0\) with \(a + b \ge 1\) and let \(d \ge 1\). Then \(\mathcal{T}_{a,b+4}^{(d)} \subseteq \mathcal{T}_{a+1,b+1}^{(d)}\).

Let \(K, K' \subseteq \mathbb {R}^d\) be nonempty compact convex sets such that \(K \cup K'\) is convex. Then

The four pyramids \(Q^{(1)}, \dots , Q^{(4)}\) form a polyhedral subdivision of the tetrahedron \(T\). Moreover

Embed \(\mathbb {R}^3 = \mathbb {R}^3 \times \{ 0\} \subseteq \mathbb {R}^4\) and let \(x_5 = (0,0,0,1)\). With \(T\) and \(Q^{(i)}\) as in Definition 101, the four polytopes

form a polyhedral subdivision of the \(4\)-simplex \(x_5 * T\), and each lies in \(\mathcal{P}_2\).

For every \(n \ge 1\) there is a ReLU network with \(n + 1\) hidden layers computing \(\mathrm{MAX}_{3^n+2}\) all of whose weights and biases lie in \(\mathbb {Z}[\tfrac 12]\), the ring of binary fractions. (In particular the construction of Theorem 60 falls into the decimal-fraction setting of the \(\lceil \log _3 n\rceil \) lower bound of Averkov, Hojny, and Merkert.)

The minimum number of hidden layers needed to compute \(\mathrm{MAX}_5\) is exactly two: \(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\) and \(\mathrm{MAX}_5 \notin \mathrm{ReLU}_{5,1}\).

\(\mathrm{MAX}_5 \in \mathrm{ReLU}_{5,2}\).

The Newton polytopes \(N(P_1), N(P_2), N(P_3), N(P_4) \subseteq \mathbb {R}^5\) of the four terms \(P_1, \dots , P_4\) form a polyhedral subdivision of the dilated simplex \(2\Delta _4\), corresponding to the subdivision of Proposition 106 under a suitable affine isomorphism; the Newton polytopes of \(Q\), \(R_{13}\), \(R_{14}\), \(R_{23}\), \(R_{24}\) are lower-dimensional faces of these four pieces.

For every \(n \ge 1\) we have \(\mathrm{CPWL}_n \subseteq \mathrm{ReLU}_{n, \lceil \log _2 (n+1) \rceil }\).

For every \(n \ge 3\) we have

For every polytope \(X \subseteq \mathbb {R}^n\), the minimum number \(k\) of hidden layers of a ReLU network representing the support function \(h_X\) (i.e., the least \(k\) with \(h_X \in \mathrm{ReLU}_{n,k}\)) equals the minimum \(k\) for which there exist \(P, Q \in \mathcal{P}_k\) with \(X + P = Q\).

Let \(n \ge 1\) and \(k \ge 0\). Suppose there are polytopes \(Q_1, \dots , Q_m\) with \(\Delta _{n-1} = \bigcup _{i \in [m]} Q_i\) and \(Q_S := \bigcap _{i \in S} Q_i \in \mathcal{P}_k\) for every nonempty \(S \subseteq [m]\) with \(Q_S \neq \emptyset \). Then \(\mathrm{MAX}_n \in \mathrm{ReLU}_{n,k}\).

For all \(x \in \mathbb {R}^5\) we have \(\mathrm{MAX}_5(x) = M(x)\).

For every \(n \ge 1\) we have \(\mathrm{MAX}_{3^n+2} \in \mathrm{ReLU}_{3^n+2,\, n+1}\).

For every convex, positively homogeneous \(f \in \mathrm{CPWL}_d\) there is a unique polytope \(P \subseteq \mathbb {R}^d\) with \(f = h_P\).

Let \(a, b \ge 0\) with \(a + b \ge 1\) and put \(i = 4a+b\). Then \(T_{a,b+4} \in \mathcal{T}_{a+1,b+1}^{(i+4)}\).

For every \(f \in \mathrm{CPWL}_n\) there exist \(s \in \mathbb {N}\), affine maps \(A_1, \dots , A_s \colon \mathbb {R}^n \to \mathbb {R}^{n+1}\) and signs \(\sigma _1, \dots , \sigma _s \in \{ \pm 1\} \) such that