On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias
This provides theoretical guarantees for the implicit bias and generalization of shallow ReLU networks, even under mild over-parameterization, which is an incremental but important contribution to neural network theory.
The paper tackles the problem of understanding gradient flow dynamics in shallow univariate ReLU networks for binary classification, showing that with high probability it converges to a network with perfect training accuracy and at most O(r) linear regions, providing a generalization bound.
We study the dynamics and implicit bias of gradient flow (GF) on univariate ReLU neural networks with a single hidden layer in a binary classification setting. We show that when the labels are determined by the sign of a target network with $r$ neurons, with high probability over the initialization of the network and the sampling of the dataset, GF converges in direction (suitably defined) to a network achieving perfect training accuracy and having at most $\mathcal{O}(r)$ linear regions, implying a generalization bound. Unlike many other results in the literature, under an additional assumption on the distribution of the data, our result holds even for mild over-parameterization, where the width is $\tilde{\mathcal{O}}(r)$ and independent of the sample size.