Size-Independent Sample Complexity of Neural Networks
This work addresses the theoretical challenge of understanding learning efficiency in neural networks, which is incremental as it builds on prior bounds with refinements.
The paper tackles the problem of sample complexity for neural networks by deriving new bounds on Rademacher complexity with norm constraints, resulting in improved dependence on depth and, under certain assumptions, full independence from network size (depth and width).
We study the sample complexity of learning neural networks, by providing new bounds on their Rademacher complexity assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth, and under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.