The Sample Complexity of One-Hidden-Layer Neural Networks
  We study norm-based uniform convergence bounds for neural networks, aiming at
a tight understanding of how these are affected by the architecture and type of
norm constraint, for the simple class of scalar-valued one-hidden-layer
networks, and inputs bounded in Euclidean norm. We begin by proving that in
general, controlling the spectral norm of the hidden layer weight matrix is
insufficient to get uniform convergence guarantees (independent of the network
width), while a stronger Frobenius norm control is sufficient, extending and
improving on previous work. Motivated by the proof constructions, we identify
and analyze two important settings where a mere spectral norm control turns out
to be sufficient: First, when the network's activation functions are
sufficiently smooth (with the result extending to deeper networks); and second,
for certain types of convolutional networks. In the latter setting, we study
how the sample complexity is additionally affected by parameters such as the
amount of overlap between patches and the overall number of patches.
