Sjoerd Dirksen (UU)
The Separation Capacity of Random Neural Networks

ABSTRACT:
Neural networks with random weights appear in a variety of machine learning applications, most prominently as the initialization of many deep learning algorithms and as a computationally cheap alternative to fully learned neural networks. The goal of this talk is to enhance the theoretical understanding of random neural networks by addressing the following data separation problem: under what conditions can a random neural network make two classes (with positive distance) linearly separable? I will show that a sufficiently large two-layer ReLU-network with Gaussian weights and uniformly distributed biases can solve this problem with high probability. The number of required neurons in the two layers is explicitly linked to geometric properties of the two sets and their mutual arrangement. This instance-specific viewpoint allows to overcome the curse of dimensionality (exponential width of the layers). I will connect the presented separation result with related lines of work on approximation, memorization, and generalization.
The talk is based on joint work with Martin Genzel, Laurent Jacques, and Alexander Stollenwerk (arXiv:2108.00207).