Trajectory growth lower bounds for random sparse deep ReLU networks

Deep neural networks continue to set new benchmarks for machin e learning accuracy across a wide range of tasks, and are the basis for many algorithms we use routinely and on a daily basis. One fundamental set of theoretical questions concerning deep networks relates t o their expressivity. There remain different approaches to understanding and quantifying neural network ex pressivity. Some results take a classical approximation theory approach, focusing on the relationship betw een the architecture of the network and the classes of functions it can accurately approximate ([15, 3, 10]). Another more recent approach has been to apply persistent homology to characterise expressivity ([7]), wh ile [18] focus on global curvature, and the ability of deep networks to disentangle manifolds. Other works c oncentrate specifically on networks with piecewise linear activation functions, using the number of linear r egions ([17]) or the volume of the boundaries between linear regions ([9]) in input space. In 2017, [19] p roposed trajectory length as a measure of expressivity; in particular, they consider the expecte d change in length of a one-dimensional trajectory as it is passed through Gaussian random neural netwo rks (see Figure 1 for an illustration). Their primary theoretical result was that, in expectation, the length of a one-dimensional trajectory which is passed through a fully-connected, Gaussian network is lower bounded by a factor that is exponential with depth, but not with width.