Complexity of One-Dimensional ReLU DNNs
By: Jonathan Kogan, Hayden Jananthan, Jeremy Kepner
Potential Business Impact:
Makes AI understand patterns with fewer parts.
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.
Similar Papers
Constraining the outputs of ReLU neural networks
Algebraic Geometry
Maps how computer brains learn to think.
Parameterized Hardness of Zonotope Containment and Neural Network Verification
Computational Complexity
Makes AI harder to check for mistakes.
Coordinate Descent for Network Linearization
Machine Learning (CS)
Makes AI faster by cutting down on calculations.