Size-Independent Sample Complexity of Neural Networks

We provide new and improved bounds on the sample complexity of deep neural networks, based on the norms of the parameter matrices at each layer. In particular, we show how certain norms lead to the first explicit bounds which are fully independent of the network size (both depth and width), and are therefore applicable to arbitrarily large neural networks. These results are derived using some novel techniques, which may be of independent interest and applicable to analyzing other deep learning systems. Joint work with Noah Golowich (Harvard) and Alexander Rakhlin (MIT).