Dependencies

Every function in \(\operatorname {CPWL}_n\) can be represented by a ReLU network with \(\lceil \log _2(n+1)\rceil \) hidden layers; equivalently \(\operatorname {CPWL}_n\subseteq \operatorname {ReLU}_{n,\lceil \log _2(n+1)\rceil }\).

For every \(m\ge 4\), \(\operatorname {MAX}_m\) can be computed with \(\lceil \log _3(m-2)\rceil +1\) hidden layers.

For decimal-fraction ReLU networks, the construction of Corollary 41 is within at most one hidden layer of the lower bound of Averkov–Hojny–Merkert.

An affine map \(A : \mathbb {R}^m \to \mathbb {R}^n\) has the form \(A(x)=L(x)+b\) for a linear map \(L : \mathbb {R}^m \to \mathbb {R}^n\) and a vector \(b \in \mathbb {R}^n\).

For real numbers \(a,b \in \mathbb {R}\), their binary maximum is \(\max (a,b)\), characterized by \(\max (a,b) \ge a\), \(\max (a,b) \ge b\), and if \(c \ge a\) and \(c \ge b\) then \(c \ge \max (a,b)\).

Let \(\mathcal{T}_{a,b}\) be the vector space spanned by all functions of the form \(T_{a,b}\circ L\), where \(L:\mathbb {R}^{4a+b}\to \mathbb {R}^{4a+b}\) is linear.

The convex hull \(\operatorname {conv}(S)\) of a set \(S\subseteq \mathbb {R}^n\) is the smallest convex set containing \(S\).

A function \(f:\mathbb {R}^n\to \mathbb {R}\) is continuous piecewise linear, abbreviated CPWL, if \(\mathbb {R}^n\) admits a finite polyhedral subdivision such that \(f\) restricts to an affine function on every cell of the subdivision and the restrictions agree continuously on common faces.

Let \(\operatorname {CPWL}_n\) be the set of CPWL functions \(f:\mathbb {R}^n\to \mathbb {R}\). Let \(\operatorname {ReLU}_{n,k}\) be the subset of \(\operatorname {CPWL}_n\) consisting of functions representable by ReLU networks with \(k\) hidden layers.

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

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

For \(n\ge 1\), define

For subsets \(P,Q\subseteq \mathbb {R}^n\), the Minkowski sum is

The convex hull of their union is denoted

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

Equivalently,

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

equivalently

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

equivalently

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

equivalently

Let \(\mathcal{P}_0\) be the set of one-point polytopes in a fixed ambient dimension. For \(k\ge 0\), define

The complexity of a polytope \(P\) is the least \(k\) with \(P\in \mathcal{P}_k\).

A polytope in \(\mathbb {R}^n\) is the convex hull of finitely many points of \(\mathbb {R}^n\).

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

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

Thus \(R_{13}(x)=\max (2x_5,x_1+x_3,x_1+x_2,x_3+x_4)\).

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

Thus \(R_{14}(x)=\max (2x_5,x_1+x_4,x_1+x_2,x_3+x_4)\).

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

Thus \(R_{23}(x)=\max (2x_5,x_2+x_3,x_1+x_2,x_3+x_4)\).

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

Thus \(R_{24}(x)=\max (2x_5,x_2+x_4,x_1+x_2,x_3+x_4)\).

The rectified linear unit is the function \(\operatorname {ReLU}: \mathbb {R}\to \mathbb {R}\) defined by \(\operatorname {ReLU}(t)=\max \{ 0,t\} \). Applied to a vector, \(\operatorname {ReLU}\) acts coordinatewise.

A ReLU network on \(\mathbb {R}^n\) with \(k\) hidden layers is specified by affine maps \(T^{(i)}:\mathbb {R}^{n_{i-1}}\to \mathbb {R}^{n_i}\) for \(i=1,\ldots ,k+1\), with \(n_0=n\) and \(n_{k+1}=1\). It computes

The support function of a polytope \(P\subseteq \mathbb {R}^n\) is

Conversely, when a convex positively homogeneous CPWL function \(f\) is equal to \(h_P\), the unique such polytope \(P\) is called the Newton polytope \(\operatorname {Newt}(f)\).

For nonnegative integers \(a,b\), define \(T_{a,b}:\mathbb {R}^{4a+b}\to \mathbb {R}\) by

Thus \(T_{0,b}=\operatorname {MAX}_b\).

For ReLU networks whose weights are decimal fractions, the maximum function \(\operatorname {MAX}_m\) requires at least \(\lceil \log _3 m\rceil \) hidden layers.

For every \(m\ge 1\), \(\operatorname {MAX}_m\) can be computed with \(\lceil \log _2 m\rceil \) hidden layers.

For all \(a,b\), one has \(\mathcal{T}_{a,b+2}\subseteq \mathcal{T}_{a,b+3}\subseteq \mathcal{T}_{a+1,b+1}\) after ignoring unused last coordinates.

Viewing \(T_{a,b+4}\) as a function on \(\mathbb {R}^{4a+b+5}\) that ignores the last coordinate, one has \(T_{a,b+4}\in \mathcal{T}_{a+1,b+1}\).

If \(T_{3^n-1,2}\) can be computed in depth \(k\), then \(T_{0,3^n+2}\) can also be computed in depth \(k\).

If \(T_{0,3^{n-1}+2}\) can be computed in depth \(k-1\), then \(T_{3^{n-1},2}\) can be computed in depth \(k\).

The four full-dimensional cells in Construction 61 have support functions corresponding to \(P_1,P_2,P_3,P_4\), and their lower-dimensional intersections have support functions corresponding to \(Q,R_{13},R_{14},R_{23},R_{24}\). Lemma 57 therefore yields the signed formula defining \(M\).

If each cell \(Q_i\) of a polyhedral subdivision lies in \(\mathcal{P}_k\) and every nonempty intersection \(Q_S\) is a face of one of the cells, then every such \(Q_S\) lies in \(\mathcal{P}_k\).

Let \(X,Q_1,\ldots ,Q_m\) be polytopes in \(\mathbb {R}^n\) with \(X=\bigcup _{i\in [m]}Q_i\). Let \(\mathcal{T}_0\) be the collection of nonempty subsets \(S\subseteq [m]\) of even size and \(\mathcal{T}_1\) the collection of nonempty subsets of odd size. For \(Q_S=\bigcap _{i\in S}Q_i\),

The expression \(M\) is invariant under swapping indices \(1\) and \(2\), under swapping indices \(3\) and \(4\), and under simultaneously swapping the pair \((1,2)\) with the pair \((3,4)\).

If \(x_1=\operatorname {MAX}_5(x)\), then \(M(x)=x_1\).

If \(x_5=\operatorname {MAX}_5(x)\), then \(M(x)=x_5\).

The function \(\operatorname {MAX}_2(x_1,x_2)=\max \{ x_1,x_2\} \) is representable by a ReLU network with one hidden layer.

The function \(\operatorname {MAX}_3\) cannot be represented by a ReLU network with one hidden layer; it needs at least two hidden layers.

For every \(x\in \mathbb {R}^5\), \(\operatorname {MAX}_5(x)=M(x)\).

The Newton polytope of \(\operatorname {MAX}_n\) is the simplex \(\Delta _{n-1}=\operatorname {conv}\{ e_1,\ldots ,e_n\} \subseteq \mathbb {R}^n\).

Each of \(P_1,P_2,P_3,P_4,Q,R_{13},R_{14},R_{23},R_{24}\) can be computed by a ReLU network with two hidden layers.

In the proof of Claim 5, the four terms corresponding to \(P_1,P_2,P_3,P_4\) lie in \(\mathcal{T}_{a+1,b+1}\).

For each \(k\), a finite Minkowski sum of polytopes in \(\mathcal{P}_k\) again belongs to \(\mathcal{P}_k\).

In the proof of Claim 5, the term corresponding to \(Q\) lies in \(\mathcal{T}_{a,b+2}\), and the terms corresponding to \(R_{13},R_{14},R_{23},R_{24}\) lie in \(\mathcal{T}_{a,b+3}\).

For every polytope \(X\), the required number of hidden layers for representing \(h_X\) is the minimum \(k\) such that there exist \(P,Q\in \mathcal{P}_k\) with \(X+P=Q\).

Every function computed by a ReLU network is CPWL.

The required number of hidden layers for \(\operatorname {MAX}_n\) is at most the minimum \(k\) for which there are polytopes \(Q_1,\ldots ,Q_m\) satisfying \(\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]\).

Support functions of polytopes are exactly the convex, positively homogeneous CPWL functions, and the representing polytope is unique.

If \(i=4a+b\), then \(T_{a,b+4}\) can be written as

If \(P\) and \(Q\) are polytopes and \(P\cup Q\) is a polytope, then

The minimum number of hidden layers needed to compute \(\operatorname {MAX}_5\) is exactly two.

For \(n\ge 3\),

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

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