Using proof techniques involving @math covering numbers, we show generalisation error bounds for deep learning with two main improvements over the state of the art. First, our bounds have no explicit dependence on the number of classes except for logarithmic factors. This holds even when formulating the bounds in terms of the @math -norm of the weight matrices, while previous bounds exhibit at least a square-root dependence on the number of classes in this case. Second, we adapt the Rademacher analysis of DNNs to incorporate weight sharing---a task of fundamental theoretical importance which was previously attempted only under very restrictive assumptions. In our results, each convolutional filter contributes only once to the bound, regardless of how many times it is applied. Finally we provide a few further technical improvements, including improving the width dependence from before to after pooling. We also examine our bound's behaviour on artificial data.
@cite_29 , building on earlier work @cite_23 , the authors provide bounds on the Rademacher complexity of the function class consisting of fully connected neural networks of a given fixed width and length, with fixed constraints on the Frobenius norms of the weight matrices, which scale as the product @math of the Frobenius norms @math of the weight matrices of each layer.
@cite_29 @cite_23
2963038205 2962857907
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 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. We investigate the capacity, convexity and characterization of a general family of norm-constrained feed-forward networks.