On Expressivity of Height in Neural Networks

In this work, beyond width and depth, we augment a neural network with a new dimension called height by intra-linking neurons in the same layer to create an intra-layer hierarchy, which gives rise to the notion of height. We call a neural network characterized by width, depth, and height a 3D network. To put a 3D network in perspective, we theoretically and empirically investigate the expressivity of height. We show via bound estimation and explicit construction that given the same number of neurons and parameters, a 3D ReLU network of width W, depth K, and height H has greater expressive power than a 2D network of width H× W and depth K, textiti.e., O((2H-1)W)K) vs O((HW)K), in terms of generating more pieces in a piecewise linear function. Next, through approximation rate analysis, we show that by introducing intra-layer links into networks, a ReLU network of width O(W) and depth O(K) can approximate polynomials in [0,1]d with error Oleft(2-2WKright), which improves Oleft(W-Kright) and Oleft(2-Kright) for fixed width networks. Lastly, numerical experiments on 5 synthetic datasets, 15 tabular datasets, and 3 image benchmarks verify that 3D networks can deliver competitive regression and classification performance.