We prove bounds on the generalization error of convolutional networks.
 The bounds are in terms of the training loss, the number of
 parameters, the Lipschitz constant of the loss and the distance from
 the weights to the initial weights.  They are independent of the
 number of pixels in the input, and the height and width of hidden
 feature maps.  We present experiments with CIFAR-10, along with varying
 hyperparameters of a deep convolutional network, comparing our bounds
 with practical generalization gaps. Recently, substantial progress has been made regarding theoretical analysis of the generalization of deep learning models (see Zhang et al., 2016; Dziugaite & Roy, 2017; Bartlett et al., 2017; Arora et al., 2018; Neyshabur et al., 2019; Wei & Ma, 2019) . One interesting point that has been explored, with roots in (Bartlett, 1998) , is that even if there are many parameters, the set of models computable using weights with small magnitude is limited enough to provide leverage for induction (Bartlett et al., 2017; . Intuitively, if the weights start small, since the most popular training algorithms make small, incremental updates that get smaller as the training accuracy improves, there is a tendency for these algorithms to produce small weights. (For some deeper theoretical exploration of implicit bias in deep learning and related settings, see (Gunasekar et al., 2017; 2018a; b; Ma et al., 2018) . ) Even more recently, authors have proved generalization bounds in terms of the distance from the initial setting of the weights instead of the size of the weights (Bartlett et al., 2017; Neyshabur et al., 2019) . This is important because small initial weights may promote vanishing gradients; it is advisable instead to choose initial weights that maintain a strong but non-exploding signal as computation flows through the network (see LeCun et al., 2012; Glorot & Bengio, 2010; Saxe et al., 2013; He et al., 2015) . A number of recent theoretical analyses have shown that, for a large network initialized in this way, a large variety of well-behaved functions can be found through training by traveling a short distance in parameter space (see Du et al., 2019b; a; Allen-Zhu et al., 2019; Zou et al., 2018) . Thus, the distance from initialization may be expected to be significantly smaller than the magnitude of the weights. Furthermore, there is theoretical reason to expect that, as the number of parameters increases, the distance from initialization decreases. Convolutional layers are used in all competitive deep neural network architectures applied to image processing tasks. The most influential generalization analyses in terms of distance from initialization have thus far concentrated on networks with fully connected layers. Since a convolutional layer has an alternative representation as a fully connected layer, these analyses apply in the case of convolutional networks, but, intuitively, the weight-tying employed in the convolutional layer constrains the set of functions computed by the layer. This additional restriction should be expected to aid generalization. In this paper, we prove new generalization bounds for convolutional networks that take account of this effect. As in earlier analyses for the fully connected case, our bounds are in terms of the distance from the initial weights, and the number of parameters. Additionally, our bounds are "size-free", in the sense that they are independent of the number of pixels in the input, or the height and width of the hidden feature maps. Our most general bounds apply to networks including both convolutional and fully connected layers, and, as such, they also apply for purely fully connected networks. In contrast with earlier bounds for settings like the one considered here, our bounds are in terms of a sum over layers of the distance from initialization of the layer. Earlier bounds were in terms of product of these distances which led to an exponential dependency on depth. Our bounds have linear dependency on depth which is more aligned with practical observations. As is often the case for generalization analyses, the central technical lemmas are bounds on covering numbers. Borrowing a technique due to Barron et al. (1999) , these are proved by bounding the Lipschitz constant of the mapping from the parameters to the loss of the functions computed by the networks. (Our proof also borrows ideas from the analysis of the fully connected case, especially (Bartlett et al., 2017; .) Covering bounds may be applied to obtain a huge variety of generalization bounds. We present two examples for each covering bound. One is a standard bound on the difference between training and test error. Perhaps the more relevant bound has the flavor of "relative error"; it is especially strong when the training loss is small, as is often the case in modern practice. Our covering bounds are polynomial in the inverse of the granularity of the cover. Such bounds seem to be especially useful for bounding the relative error. In particular, our covering bounds are of the form (B/ ) W , where is the granularity of the cover, B is proportional to the Lipschitz constant of a mapping from parameters to functions, and W is the number of parameters in the model. We apply a bound from the empirical process literature in terms of covering bounds of this form due to Giné & Guillou (2001) , who paid particular attention to the dependence of estimation error on B. This bound may be helpful for other analyses of the generalization of deep learning in terms of different notions of distance from initialization. (Applying bounds in terms of Dudley's entropy integral in the standard way leads to an exponentially worse dependence on B.) Related work. Du et al. (2018) proved size-free bounds for CNNs in terms of the number of parameters, for two-layer networks. Arora et al. (2018) analyzed the generalization of networks output by a compression scheme applied to CNNs. Zhou & Feng (2018) provided a generalization guarantee for CNNs satisfying a constraint on the rank of matrices formed from their kernels. Li et al. (2018) analyzed the generalization of CNNs under other constraints on the parameters. Lee & Raginsky (2018) provided a size-free bound for CNNs in a general unsupervised learning framework that includes PCA and codebook learning. is the kernel of convolutional layer number i, then op(K (i) ) refers to its operator matrix 1 and vec(K (i) ) denotes the vectorization of the kernel tensor K (i) . For matrix M , M 2 denotes the operator norm of M . For vectors, || · || represents the Euclidian norm, and || · || 1 is the L 1 norm. For a multiset S of elements of some set Z, and a function g from Z to R, let We will denote the function parameterized by Θ by f Θ .
We prove generalization bounds for convolutional neural networks that take account of weight-tying Studies the generalization power of CNNs and improves the upper bounds of generalization errors, showing correlation between the generalization error of learned CNNs and the upper bound's dominant term. This paper presents a generalization bound for convolutional neural networks based on the number of parameters, the Lipschitz constant, and the distance of the final weights from initialization.