Depth Separation in Norm-Bounded Infinite-Width Neural Networks
Suzanna Parkinson Greg Ongie Rebecca Willett Ohad Shamir Nathan Srebro
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.