Depth Separation in Norm-Bounded Infinite-Width Neural Networks
This addresses a theoretical gap in understanding depth's role in learnability for norm-bounded networks, providing insights for researchers in machine learning theory, though it is incremental as it builds on prior depth separation work.
The paper tackles the problem of depth separation in infinite-width neural networks by showing that depth-3 ReLU networks can learn certain functions with polynomial sample complexity, while depth-2 networks require sub-exponential sample complexity for the same functions, but not vice versa.
We study depth separation in infinite-width neural networks, where complexity is controlled by the overall squared $\ell_2$-norm of the weights (sum of squares of all weights in the network). Whereas previous depth separation results focused on separation in terms of width, such results do not give insight into whether depth determines if it is possible to learn a network that generalizes well even when the network width is unbounded. Here, we study separation in terms of the sample complexity required for learnability. Specifically, we show that there are functions that are learnable with sample complexity polynomial in the input dimension by norm-controlled depth-3 ReLU networks, yet are not learnable with sub-exponential sample complexity by norm-controlled depth-2 ReLU networks (with any value for the norm). We also show that a similar statement in the reverse direction is not possible: any function learnable with polynomial sample complexity by a norm-controlled depth-2 ReLU network with infinite width is also learnable with polynomial sample complexity by a norm-controlled depth-3 ReLU network.