Complexity of One-Dimensional ReLU DNNs
This provides theoretical insights into the complexity of neural networks for researchers in machine learning theory, but it is incremental as it builds on existing expressivity studies.
The paper tackles the expressivity of one-dimensional ReLU deep neural networks by analyzing their linear regions, proving that the expected number of linear regions grows as a sum of neurons per layer plus lower-order terms in the infinite-width limit, and introduces a function-adaptive sparsity measure for approximation efficiency.
We study the expressivity of one-dimensional (1D) ReLU deep neural networks through the lens of their linear regions. For randomly initialized, fully connected 1D ReLU networks (He scaling with nonzero bias) in the infinite-width limit, we prove that the expected number of linear regions grows as $\sum_{i = 1}^L n_i + \mathop{o}\left(\sum_{i = 1}^L{n_i}\right) + 1$, where $n_\ell$ denotes the number of neurons in the $\ell$-th hidden layer. We also propose a function-adaptive notion of sparsity that compares the expected regions used by the network to the minimal number needed to approximate a target within a fixed tolerance.