Rank and computation of the pathlifting Jacobian of a DAG ReLU network

The architecture of deep feedforward neural networks is ubiquitous in deep learning, either as a whole system or as a subnetwork of other architectures, and thus its mechanism is a key ingredient of the black box of neural networks. On the basis of the simplest two-layer ReLU network, this paper systematically studies the mechanism of deep feedforward ReLU networks with multiple hidden layers and successfully explains the training solution obtained by the back-propagation algorithm. The concept of a path, especially in terms of the relationships between paths, plays a central role in uncovering the mystery of the black box. It is shown that a unit of a deep ReLU network can form a piecewise linear manifold to divide the input space, instead of a hyperplane of the two-layer case. How to efficiently use the hidden-layer units to produce both linear functions and partitions of the input space is also a central problem. The principles of a two-layer ReLU network can be generalized to the deeper case to a large extent, such as multiple strict partial orders and continuity restriction. The combination of the basic and simple principles proposed can yield complicated instantiations including the training solutions, and in this sense the black box of deep feedforward ReLU networks is revealed.

Two deep ReLU networks can have entirely different architectures and parameters, yet realize the same function. We provide a complete characterization of this nonuniqueness. This is effected by building a symbolic calculus for deep ReLU networks, equivalence and simplification of networks becoming derivation of formulae, in close parallel to Shannon's analysis of switching circuits through Boolean logic. Inspired by Shannon, who turned circuit synthesis into the manipulation of Boolean formulae by the axioms of Boolean algebra, we turn ReLU network identification into the derivation of Łukasiewicz formulae by the axioms of many-valued (MV) logic. Two non-degenerate ReLU networks realize the same function on the unit cube if and only if one is obtained from the other by finitely many applications of the MV axioms for integer weights and biases, the divisible MV axioms for rational ones, and the Riesz MV axioms for real ones. The MV logic axioms characterize all symmetries of ReLU networks, the single-layer ones, which for tanh networks are the only kind, and the deep ones, spanning three or more layers. Our framework consists of three steps, an extraction algorithm turning a network into a substitution graph, whose represented formula has the network's input-output map as its truth function, a completeness theorem, by which functionally equivalent formulae are interderivable, and a construction algorithm returning from graphs to networks. The substitution graph is layered, carrying at each node a formula in the variables of the layer feeding it, encodes the network uniquely, and induces a new normal form for MV logic, compositional rather than flat as in the literature, hence retaining the algebraic structure of the network, with three local operations--node rewrite, layer collapse, layer expansion--realizing every derivation.

We prove a depth hierarchy for ReLU neural networks in which every additional ReLU layer can save exponentially many neurons. For all $k\geq2$, we construct a globally $[0,1]$-valued, $1$-Lipschitz function realized by a depth-$(k+1)$ network of width $\mathcal{O}(d^4)$, whereas any depth-$k$ network with unrestricted weights and width at most $\frac{2^d}{2d(k-1)}$ has squared $L_2$ error at least $1/24$ under an absolutely continuous distribution supported at exponential distance from the origin. To the best of our knowledge, this is the first exponential hierarchy across all adjacent fixed depths, and the first exponential separation for ReLU networks between two fixed depths whose shallower network has depth at least $3$. The lower bound also immediately yields the corresponding hierarchy for exact computation. Moreover, the case $k=2$ gives a compactly supported separation between depths $3$ and $2$ with unrestricted shallow-network weights, answering a question raised by Safran, Eldan, and Shamir (2019). The distribution used in our construction nevertheless has all its mass at exponential radius, placing the hierarchy outside the regularity regime in which such a separation would imply major threshold-circuit lower bounds. We also prove an exact separation for a more regular target, which is globally $[0,1]$-valued and $\mathcal{O}(\sqrt d)$-Lipschitz and maps the unit hypercube onto $[0,1]$. It is computed by a polynomial-width depth-$4$ network, whereas any depth-$3$ network agreeing with it on the unit hypercube requires exponentially many first-layer neurons, even with unrestricted weights.