On the Local Complexity of Linear Regions in Deep ReLU Networks

We define the local complexity of a neural network with continuous piecewise linear activations as a measure of the density of linear regions over an input data distribution. We show theoretically that ReLU networks that learn low-dimensional feature representations have a lower local complexity. This allows us to connect recent empirical observations on feature learning at the level of the weight matrices with concrete properties of the learned functions. In particular, we show that the local complexity serves as an upper bound on the total variation of the function over the input data distribution and thus that feature learning can be related to adversarial robustness. Lastly, we consider how optimization drives ReLU networks towards solutions with lower local complexity. Overall, this work contributes a theoretical framework towards relating geometric properties of ReLU networks to different aspects of learning such as feature learning and representation cost.

The input-output relationships implemented by many modern neural networks can be regarded as large ``folded maps'' with many sharp bends. These bends are determined by the activation patterns of the different neurons in the network and are thought to affect how well the network is able to learn from data and resist adversarial attacks. We introduce a notion of local complexity that measures the distribution of such bends near a given dataset. We prove that this measure is tied to several important properties, such as the dimension of the data representations learned by the network, the variability of the computations that it implements over different inputs, as well as phenomena observed late in training. Local complexity can give researchers and practitioners a new diagnostic for building smoother and more robust neural networks.