Generalization bounds for deep convolutional neural networks
Authors: Philip M. Long
Hanie Sedghi
Venue:  (2020)
Keywords: generalization
convolutional networks
statistical learning theory

Abstract: 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 using CIFAR-10 with varying
hyperparameters of a deep convolutional network, comparing our bounds
with practical generalization gaps.

Published as a conference paper at ICLR 2020
GENERALIZATION BOUNDS FOR DEEP CONVOLUTIONAL NEURAL NETWORKS
Philip M. Long" and Hanie Sedghi' Google Brain
(plong, hsedghi /égoogle e. com
ABSTRACT
We prove bounds 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 using CIFAR-10 with varying hyperparameters of deep convolutional network, comparing our bounds with practical generalization gaps.
INTRODUCTION
Recently, substantial progress has been made regarding theoretical analysis of the generalization of deep learning models (see Neyshabur et al., 2015; Zhang et al., 2016; Dziugaite and Roy, 2017; Bartlett et al., 2017; Neyshabur et al., 2017; 2018; Arora al., 2018; Golowich et al., 2018; Neyshabur et al., 2019; Wei and Ma, 2019a; Cao and Gu, 2019; Daniely and Granot, 2019). One interesting point that has been explored, with roots in (Bartlett, 1998), is that even there are many parameters, the set of models that can be represented using weights with small magnitude is limited enough to provide leverage for induction (Neyshabur et al., 2015; Bartlett et al., 2017; Neyshabur et al., 2018). Intuitively, if the weights start small, since the most popular training al 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 (Gunasckar et al., 2017; 8a;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 (Dziugaite and Roy, 2017; Bartlett et al., 2017; Neyshabur et al., 2019; Nagarajan and Kolter, 2019). This important because small initial weights may promote vanishing gradients; it is advisable instead to choose initial weights that maintain strong but non-ee con-exxloding signal as computation flows through the network (see LeCun al., 2012; Glorot and 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, accurate models can be found by traveling a short distance in parameter space (see Du et al., 2019b;a; Allen-Zhu et al., 2019; Zou et al., 2018; Lee et al., 2019). Thus, the distance from initialization may be expected to be significantly smaller than the magnitude of the weights. Furthermore, there is theoretical reason expect that, as the number of parameters increases, the distance from initialization decreases. This motivates generalization bounds in terms of distance from initialization (Dziugaite and Roy, 2017; Bartlett et al., 2017).
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 networks with fully connected layers. Since 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 the convolutional layer constrains the set of functions computed by the layer. This additional restriction should be expected to aid generalization.
Authorrs ordered alphahetically.

---

Published as a conference paper at ICLR 2020
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 independent of the number of pixels in the input, or the height and width of the hidden feature maps.
Our most general bounds apply 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; Neyshabur et al., 2018).) Covering bounds may be applied to obtain a huge variety of generalization bounds. We present two examples for each covering bound. One is 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/c)W, W where c is the granularity of the cover, B is proportional 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é and 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 terms of different notions of distance from initialization. (Applying bounds in terms of Dudley's 's entropy integral in the standard way leads to an exponentially worse dependence on B.)
Related previous work. Du et al. (2018) proved 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 and 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 the parameters. Lee and Raginsky (2018) provided a size-free bound for CNNs in a general unsupervised learning framework that includes PCA and codebook learning.
Related independent work. Ledent et al. (2019) proved bounds for CNNs that also took account of the effect of weight-tying. (Their bounds retain the exponential dependence the depth of the network from earlier work, and are otherwise qualitatively dissimilar to ours.) Wei and Ma (2019b) obtained bounds for fully connected networks with an improved dependence on the depth of the network. Daniely and Granot (2019) obtained improved bounds for constant-depth fully-connected networks. Jiang al. (2019) conducted wide-ranging empirical study of the dependence of the generalization gap on variety of quantities, including distance from initialization.
Notation. If K00 is the kernel of convolutional layer number i, then op(K ((())) refers to its operator matrix and vec( denotes the vectorization of the kernel tensor K70) For matrix M, ||M]] denotes the operator norm of M. For vectors, ||| represents the Euclidian norm, and || is the L1 norm. For a multiset S of elements of some set Z, and a function from Z to R, let m > (2x). We will denote the function parameterized by θ by fe.
Es[g] = -
2 BOUNDS FOR A BASIC SETTING
In this section, we provide a bound for clean and simple setting.
Convoluuionn is a linear operator and can thus be written a matrix-vector product. The operator matrix of kernel K, refers to the matrix that describes convolving the input with kernel K. For details, see (Sedghi et al., 2018).
2

---

Published as a conference paper at ICLR 2020
2.1 THE SETTING AND THE BOUNDS
In the basic setting, the input and all hidden layers have the same number of channels. Each input Rdxdxe satisfies] vec(1))] S 1.
We consider a deep convolutional network, whose convolutional layers use zero-padding (see Good- fellow al., 2016). Each layer but the last consists of convolution followed by an activation function that is applied componentwise. The activations are 1-Lipschitz and nonexpansive (examples include ReLU and tanh). The kernels of the convolutional layers are K E R & xexxxxx for E {1...., L). Let K = (K ..... k())) be the I. x x k x e x c-tensor obtained by concatening the kernels for the various layers. Vector w represents the last layer; the weights in the last layer are fixed with ||e||| = 1. Let W = 2.k2²² be the total number of trainable parameters the network.
We let Kg"
k(")) K6 take arbitrary fixed values (interpreted the initial values of the kernels) subject to the constraint that, for all layers i, op Kg || = (This often the goal of initialization schemes.) Let Ko be the corresponding L x k l X ex tensor. We provide generalization bound in terms of distance from initialization, along with other natural parameters of the problem. The distance is measured with K
Kollo
del Σ (p(((()))) - op(Kg)) )|l-
For B >> 0, define Ks to be the set of kernel tensors within || llo distance ,3 of Ko. and define F3 to be set of functions computed by CNNs with kernels in Kgg. That is, F3 {sk || Kollo S $).
Let : R x I + j0, 1] be a loss function such that e(., v) is X-Lipschitz for all y. An example is the 1/ 1/A-margin loss.
For function from Rdxdxe to R. let (x = {(((x),))
We will use S to denote set ((11,31), .... (Imm vm)) } = (31,... of random training examples where each 2, (x4,
Theorem 2.1 (Basic bounds), For any y > O, there is a C > such that for any 3,5 2 for any joint probability distribution P over Rdxdxe R. if training set S of n examples drawn independently at random from P, then, with probability at least 1 8, for all f E Fg.
Ex- [()=)]] < (1 Ess] C(W(B + log(An)) + log(1/8))
n
and, B 5, then
W(3 + log(A)) ) log (1/5)
[==) Esles) + CV
n
and otherwise
W
log (1/6)
E. (
+
n
n
If Theorem 2.1 is applied with the margin loss, then [ [[]] is in turn upper bound on the probability of misclassification on test data. Using the algorithm from (Sedghi et al., 2018), ||- may be efficiently computed. Since || - Koll. < vee(K) vee vec(Ko)ll (Sedghi et al., 2018), Theorem 2.1 yields the same bounds as a corollary if the definition of F3 replaced with the analogous definition using || vec(K) vec(Ko)ll.
2.2 TOOLS
Definition 2.2. For d E N, set G of real-valued functions functtion with a common domain Z, we say that is (B, d)-Lisschitz parameterized if there is a norm || on Bdd and mapping & from the unit bull w.r. in Rd to G such that, for all 0 and O' such that ||| < 1 and ||0'|| < 1, and all a E Z,
(()(0))))) (=)) B| 0'|]-
The following lemma is essentially known. Its proof, which uses standard techniques (see Pollard, 1984; Talagrand, 1994; 1996; Barron et al., 1999; Van de Geer, 2000; Giné and Guillou, 2001; 10 Mohri et al., 2018), is in Appendix A.
3

---

Published as a conference paper at ICLR 2020
Lemma 2.3. Suppose set G of functions from common domain Z to [0, M is (B, Liipsshit parameterized for B >> O and d E N.
Then, for any 1 O. there is C such that, for all large enough E N. for any 8 > 0. for any probability distribution P over Z, if S is obtained by sampling n times independently from P. then, with probability at least 1 for all g E G,
E [g]()] (1 + Es + (d (m) + log(1/6))
and if B 5.
d log B + log 5
Bnwpl(()) & Es[g] CMV
n
and, for all B,
B d + M
log n
Eg [g[g] C
2.3 PROOF OF THEOREM 2.1
Definition 2.4. Let lF = (2r f
We will prove Theorem 2.1 by showing that Epg is (BXc², W) -iisschtttzz parameterized. This will be achieved through a series of lemmas.
Lemma 2.5. Choose K E Kg and layer j. Suppose Kn KB satisfies K(0) (((1) for all i #
Then, for all examples (x, v). (e(fx(z), [(f U)1 Xe ) op((
Proof. For each layer i, let B, = op( op( (pp((())))) )12
Since is X-Lipschitz w.r.t. its first argument, we have that (x) v)) ((((((())))))) S. (x) fg (z)], so suffices to bound (x) - fg (z)). Let Sup be the function from the inputs to the whole network with parameters K to the inputs to the convolution in layer j, and let 9down be the function from the output of this convolution to the output of the whole network, so that fx Jdown ktp Sup- Choose input the network, and let a (up( Recalling that ||||||
and the non con-lincasities are nonexpansive, we have ||u|| $ III
/p(( (9) i<.
Since the non-li -onelinaassiiss
are I-Lipschitz, and, recalling that (i) k6) for + j. we have
1 (x) - [x(x) = M9owwa (op( K )u)
Jdown (op( ((())(
opp ( 1/2)
(op(k())u-oop(
op( 1
|op(K())- - op( | ||2|||
lopCkTOO |
op(
II (1+ 81)
<
(56
4

---

Published as a conference paper at ICLR 2020
where the last inequality uses the fact that -op() )|22 s 3 for all i and (oo((K"))l I for all i.
)l|2
Now Hig (1 (.) - I1 + Bc), and the latter is maximized over the nonnegative 3 subject
to Eitg 8 S 3 when each of them is 3/ L. Since (1 + 3/L)4 < e this completes the proof. 0
Now we prove a bound when all the layers can change between K and K. Lemma 2.6. For any K, K Kg. for any input to the network, (e(fx(x)) (t)
8
K
K
Proof. Consider transforming K to K by replacing one layer of K at a time with the corresponding layer in K. Applying Lemma 2.5 to bound the distance traversed with each replacement and combining this with the triangle inequality gives
L. -( s A Σ 1op(K()) -op())))) =de K |
|ee||
Now we are ready to prove our basic bound.
Proof (of Theorem 1) Consider the mapping & from the ball w.r.t. 11-11- of radius in R LA
centered at vec( K₂) to Ep, defined by <(0) l + k(a)" where vec v0c is the reshaping of
into a x x Is x с x c-tensor. Lemma 2.6 implies that this mapping is BAc -iissshis Applying Lemma 2.3 completes the proof.
2.4 COMPARISONS
Since a convolutional network has an alternative parameterization as a fully connected network, the bounds of (Bartlett et al., 2017) have consequences for convolutional networks. To compare our bound with this, first, note that Theorem 2.1, together with standard model selection techniques, yields
o
( W (I (
Ko la + log(A)) 1og(1/8)
bound on Ez- (2)pp(y(()) [=]] (For more details, please see Appendix B.) Translating the bound of (Bartlett et al., 2017) setting and notation directly yields bound on -xs) whose main terms are proportional to
A (II i (lop((()))))
D/ ()) oop( ((())))
112/3
3/2
log(d'c21.) + Vlog(188)
((pp((()) 178
Vn
where, for a p X matrix A. ||A||,, = IK]. /|.l/lA.............. (12)11 One can get an idea how this bound relates to (1) by comparing the bounds simple concrete case. Suppose that each of the convolutional layers of the network parameterized by K, computes the identity function, and that K is obtained from Ko by adding each entry. In this case, disregarding edge effects, c and || Kollo 2k2cL (as proved in Appendix C). Also, |l (p((( - ( ( l2.1 = (ad?) (EV = 3/2 k2.. We get additional simplification if we set Rz In this case, (2) gives constant times
for all ()((())))
(c 1)¹ Vod L3/ log(dcL) + + llg
5

---

Published as a conference paper at ICLR 2020
where (1) gives constant times
@LekL + ckyy log(A) (A) + log(1/6)
vn
In this scenario, the new bound is independent of d, and grows more slowly with X, c and L. Note that Is I d (and, typically, is much less).
This specific case illustrates more general phenomenon that holds when the initialization is close to the identity, and changes the parameters are on similar scale.
Golowich et al. (2017) established bounds that improve on the bounds of (Bartlett et al., 2017) in some cases. Their bound requires a restriction on the activation function (albeit one that satisfied by the ReLU). For large n, the main term of the natural consequence of Corollary of their paper in the setting of this section, with the required additional assumption on the activation function, grows like
XVL
ML vn
Vn
when = 1/k2. (We note, however, that, in addition to not trying to take account of the convolutional structure, Golowich al. (2017) also did make effort obtain stronger bounds in the case that the distance from initialization is small. On the other hand, we suspect that modifying their proof analogously to (Bartlett et al., 2017) to do would not remove the exponential dependence on L.)
A MORE GENERAL BOUND
In this section, we generalize Theorem 2.1.
3.1 THE SETTING
The more general setting concerns a neural network where the input is d x d x tensor whose flattening has Euclidian norm at most X. and network's output is m-dimensional vector, which may be logits for predicting one-hot encoding of an m-class classification problem.
The network is comprised of L. convolutional layers followed by L, fully connected layers. The followed by
ith convolutional layer includes convolution, with kernel (() X& componentwise non-linearity and an optional pooling operation. We assume that the non-linearity and any pooling operations are I-Lipschitz and nonexpansive. Let V be the matrix of weights for the ith fully connected layer. Let = (K(2) (.,,,.,,,,,,,, (L,),, v()) ..., v(4r)) be all of the parameters of the network. Let L = L. Ly-
We assume that, for all y, E( y) is X-Lipschitz for all y and that ($.8) E MM] for all ğ and y. An example (x, y) includes d d x e-tensor æ and y E R
We let K." K((a), v ..... V/ (Tx)) take arbitrary fixed values subject to the constraint that, for
all convolutional layers i, (x(( Ill 1+v, and for all fully connected layers i, ||V( [|2 < 1+
Let On (K(") .... (Le)) (1)
,... V/ ((r)).
For θ = (K))) ..... k(Le), va), y. v((r)) and = (R(1), ..... K(le), 1(1), ..... v((r)). define
Le - -
by Σ -1110--00 -
ōllv= Σ
For 3, v 2 O, define FB.u to be set of functions computed by CNNs as described in this subsection with parameters within II-IIv-distanne -dittance
of On. Let OR.y be the set of their parameterizations.
Theorem 3.1 (General Bound). For any 11 0, there is constant C such that the following holds. For any B, v. X > O. for any > 0, for any joint probability distribution P over & x I such that, with probability 1, (x. y) P satisfies vee(x:) l| X. under the assumptions this section,

---

Published as a conference paper at ICLR 2020
if a training set S of n examples is drawn independently random from P, then, with probability at least for all f E FB.m.
CM (W (3 4L log(xA8n)) log(1/)))
[a>p]ts(z)] - (1 E
1
and, xf + 8/b)² 2 5,
Rzwr (ewr(es(>)] & Es(es) + CMy W (3 ( (8++L. log(x log (1/6)
n
and a bound of
W + M (ss xxA(1++ +
log 1
n
holds for all X, x, > 0.
3.2 PROOF OF THEOREM 3.1
We will prove Theorem 3.1 by using I|-1Iav xy witness the fact that Ero., is (xA8(1 + w)- Lipschitz parameterized.
The first two lemmas concern the effect of changing single layer. Their proofs are very similar to the proof of Lemma 2.5, and are in the Appendices D and E.
(K .... K(Lo), v(1,, ,.., ...,), θ (K()) .... ((,),)), V(t,... v(T)) Oz, and a convolutional layer j. Suppose that K k-0 for all convolutional layers # j and vi)) (()) for all fully connected layers i. Then, for all examples (xr, v).
Lemma 3.2. Choose
S XA11 + + - op(())))
- ((Gll))))
Lemma 3.3. Choose
(KO), IC(1.)), v(), V(,,))
(K((1) ..... (((L,), f((1) V(L)) E O3 and a fully connected layer j. Suppose that K k( for all convolutional layers and (i) = ( for all fully connected layers # j. Then, for all examples (ær,) v).
(e(fe(z).)) ((fa(z).)) S xA +1 (() -800l
Now we prove a bound when all the layers can change between O and θ.
Lemma 3.4. For any + (K(1) K(Lo), v())... ..... v(L)) E Oz for any input
(K K(L,,) v()) ...., v((,)),
=
[e(f(()) - ((fa(z), & x1 1- 661
Proof. Consider transforming to ê by replacing one layer at time of with the corresponding layer é. Applying Lemma 3.2 to bound the distance traversed with each replacement convolutional layer, and Lemma 3.3 to bound the distance traversed with each replacement of a fully connected layer, and combining this with the triangle inequality gives the lemma.
Now we are ready to prove our more general bound.
Proof (of Theorem l). Consider the mapping & from the ball of || -rdiuu 1 centered at Oo to (Fe. defined by o(O) = f Lemma 2.6 implies that this mapping is (1+ .w -ipsschit. Applying Lemma 2.3 completes the proof.
7

---

Published as a conference paper at ICLR 2020
0.06
Generalization Gap
0.05
0.04
0.03
0.02
0.01
0.00
0.0
0.5
10
W WIK- Kolla
1e8
Figure 1: Generalization gaps for 10-layer all-conv model on CIFARIO dataset.
0.040
Generalization Gap
0.035
0.005
0.000
500000 aa00o0tooomm00000000000000000000
W
Figure 2: Generalization gap as function of W
3.3 MORE COMPARISONS
Theorem 3.1 applies in the case that there are no convolutional layers, iee for a fully connected network. In this subsection, compare its bound in this case with the bound of (Bartlett al., 2017). Because the bounds are in terms of different quantities, we compare them in a simple concrete case. In this case, for D ed? each hidden layer has D components, and there D classes. For all i, v(()) the Sylvester construction), and x M
and (() = I + H/VD, where is a Hadamard matrix (using Then, dropping the superscripts, each layer V has ||V||2 = 2, |IV Voll2 = 1, V|V - Vol|a,1 = D.
Further, in the notation of Theorem 3.1, W = DºL, and 3 = L, and P = 0. Plugging into to Theorem 3.1 yields bound on the generalization gap proportional
DL + D DV log((A) + vlog(1/5)
Vn
where, in this case, the bound of (Bartlett et al., 2017) proportional to
x2 13/ log (L) + Vlog(1/6)
Vn
and, when D is large relative L. Corollary of (Golowich al., 2017) (approximately) gives /2 + (1/6)
8

---

Published as a conference paper at ICLR 2020
340
100
Ko
80
Koll
15-
K
20-
0-
0g
500000 aa0o0000000002200000ooosss
500000 10000000000000000000000000000000
W
and error bar
(h) median
Figure 3: |K
Kolla as a function of W.
4 EXPERIMENTS
We trained a 10-layer all-convolutional model on the CIFAR-10 dataset. The architecture was similar VGG (Simonyan and Zisserman, 2014). The network was trained with dropout regularization and an exponential learning rate schedule. We define the generalization gap as the difference between train eиror and test error. order analyze the effect of the number of network parameters on the generalization gap, we scaled up the number of channels in each layer, while keeping other elements of the architecture, including the depth, fixed. Each network was trained repeatedly, sweeping over different values of the initial learning rate and batch sizes 32, 64, 128. For each setting the results were averaged over five different random initializations. Figure shows the generalization gap for different values of W WIKK Kolla- As in the bound of Theorem 3.1, the generalization gap increases with W|K Kolla. Figure shows that as the network becomes more werr-paaametrized the generalization gap remains almost flat with increasing W. This is expected due to role of over- parametrization on generalization (Neyshabur et al., 2019). An explanation of this phenomenon that consistent with the bound presented here is that, ultimately, increasing W leads value of K Kollo: see Figure 3a. The fluctuations in Figure 3a are partly due to the fact that training neural networks is not an stable process. We provide the medians || Kollo for different values of W in Figure 3b.
decrease in
ACKNOWLEDGMENTS
We thank Peter Bartlett, Jacho Lee and Sam Schoenholz for valuable conversations, and anonymous reviewers for helpful comments.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. ICML, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for 2018.
deep nets via a compression approach. arXiv preprint
Andrew Barron, Lucien Birgé, and Pascal Massart. Risk bounds for model selection via penalization. Probability theory and related fields, 13(3):301-413, 1999.
Bartlett. Dudley's entropy integral, 2013. http://www..aaabbbd..../////uttt stat210b/notes/ httpl////ootes//ootssssooooo 4notes.ppff downloaded 4/17/19.
Peter I. Bartlet. The sample complexity of pattern classification with neural networks: the size the weights is more important than the size of the network. IEEE transactions Information Theory,
44(2):525-536, 1998.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-normalline normaliized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6240-6249, 2017.

---

Published as a conference paper at ICLR 2020
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint arXiv:1905.13220, 2019.
Amit Daniely and Elad Granot. Generalization bounds for neural networks via approximate de- scription length. In Advances in Neural Information Processing Systems, pages 1988811996, 2019.
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Ruslan Salakhutdinov, and Aarti Singh. How many samples needed estimate convolutional neural network? In Advances in Neural Information Processing Systems, pages 373-383, 2018.
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang. and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. ICML, 2019a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes ever-parameterized neural networks. ICLR, 2019b.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. UAI, 2017.
Evarist Giné and Armelle Guillou. On consistency of kernel density estimators for randomly censored data: rates holding uniformly over adaptive intervals. In Annales de I'IHP Probabilités et statistiques, volume 37, pages 503-522, 2001.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pages 249-256, 2010.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- iizeeindependent sample complexity of neural networks. arXiv preprint arXiv:1712.06541, 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size- Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299, 2018.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pages 6151-6159, 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint arXiv:180.008246, 2018a.
Suriya Gunasckar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pages 9461-9471, 2018b.
D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78-155)) 1992.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 1026-1034. 2015.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. ICLR, 2019.
A. N. Kolmogorov and V. M. Tikhomirov. s-entropy and s-capacity of sets in function spaces. Uspekhi Matematicheskikh Nauk, 14(2):3-86, 1959.
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus-Roben Müller. Efficient backprop. In Neural networks: Tricks of the trade, pages 9-48. Springer, 2012.
Antoine Ledent, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for multi-class convolutional neural networks. arXiv 1905. 12430, 2019.
10

---

Published as a conference paper at ICLR 2020
Jacho Lee and Maxim Raginsky. Learning cennitt-iimessiona coding schemes with nonlinear recon- struction maps. arXiv preprint arXiv:1812.09658, 2018.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pages 8570-8581, 2019.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint arXiv:1806.05//55 159, 2018.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In ICML, pages 3351-3360, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Vaishnavh Nagarajan and Zico Kolter. Generalization in deep networks: The role of distance from initialization. arXiv preprint 1rXiv:1901.0167,, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theoor, pages 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generaliza- tion in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-hayesian approach to spectrally- normalized margin bounds for neural networks. ICIR, 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards understanding the role of over-parametrization in generalization of neural networks. ICLR, 2019.
D. Pollard. Convergence of Stochustic Processes. Springer Verlag, Berlin, 1984.
D. Pollard. Empirical Processes Theory and Applications, volume of WSF-CBMS Regional Conference Series in Probability and Statistics. Institute of Math. Stat. and Am. Stat. Assoc., 1990.
Andrew M Saxe, James I. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv: 1312.6120, 2013.
Hanie Sedghi, Vineet Gupta, and Philip M Long. The singular values of convolutional layers. arXiv preprint 1rXiv:1805.1000 10408, 2018
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1s: 2014.
M. Talagrand. Sharper bounds for Gaussian and empirical processes. Annals of Probability 22: 28-76, 1994.
Michel Talagrand. New concentration inequalities in product spaces. Inventiones mathematicae, 126 (3):505-563) 1996.
Sara A Van de Geer. Empirical Processes in M-estimation, volume 6, Cambridge university press, 2000.
V. N. Vapnik. Estimation of Dependencies based on Empirical Data. Springer Verlag, 1982.
V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Applications, 16(2):64-280, 1971.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. arXiv preprint arXiv: 1905.03684 2019a.

---

Published as a conference paper at ICLR 2020
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via am all-layer margin. ICLR, 2019b.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint wrxiv:/61..03500 2016.
Pan Zhou and Jiashi Feng. Understanding generalization and optimization performance deep cnns. In ICML, pages 5955-5964 2018.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks. arXiv preprint arXiv:1811.0888 2018
A
PROOF OF LEMMA 2.3
Definition A.1. If (X, p) is a metric space and H C X, we say that G is an E-cover of H with respect p if every h E H has ag E G such that p(g. h) Then (,(H, denotes the size of the smallest c-cover of H w.n.. p.
Definition A.2. For a domain Z, define a metric Pmax on pairs of functions from to R by Pmax (J, () supsez (f(z) - -
We need two lemmas in terms of these covering numbers. The first is by now standard bound from Vapnik-Chervone Chervonenkis theory (Vapnik and Chervonenkis, 1971: Vapnik, 1982; Pollard, 1984). For example, it is a direct consequence of (Haussler, 1992, Theorem 3).
Lemma A.3. For any 1j > O, there is a constant C depending only on 1) such that the following holds. Let G be an arbitrary set of functions from a common domain Z [0, M). If there are constants B and d such that, N (G,+) < 2) for all >> O, then, for all large enough E N. for any 8 > O, for any probubility distribution P over Z, if obtained by sampling n times independently from P. then, with probability at least 1 8. for all G.
Cd + log(1/5))
En-p(g(>) S (1 Bs|y
We will also use the following, which is the combination of (2.5) and (2.7) of (Giné and Guillou, 2001).
Lemma A.4. Let G be an arbitrary set of functions from a common domain Z to [0, M). J. If there are constants B 2 5 and d such that No (G,c) < (2) d for all <> 0, for all large enough n E N. for any 5 >> 0, for any probability distribution over Z, if is obtained by sampling n times independently from P. then, with probability at least 1 8, for all g E G.
doo B + log
Ex>Plg(=) & Es|g] + CM
n
where C is an absolute constant.
The above bound only holds for B 2 5. The following, which can be obtained by combining Talagrand's 's Lemma with the standard bound Rademacher complexity in terms of the Dudley entropy integral (see (Van de Geer, 2000; Bartlett, 2013)), yields a bound for all B.
Lemma A.5. Let be an arbitrary set of functions from a common domain Z to [0, If there are constants B and such that No (G. é) < B for all e 0, then, for all large enough E N, for any 5 > 0. for any probability distribution P over Z, if S is obtained by sampling n times independently from P, then, with probability at least
for all g E G.
d n
log
Eg-r(g(=)] Es[g] +
B
+ M
n
where C. is an absolute constant.
12

---

Published as a conference paper at ICLR 2020
So now want bound on N Pmma (G, c) for notion of a packing which we now define.
classes. For this, need the
Definition A.6. For any metric space (X, p) and any S S, let M,(H, be the size of the largest subset of H whose members are pairwise at distance greater than w.r.l.
Lemma A.7 (KKolmogorov and Tikhomirov, 1959)). For any metric space (X, any H C X, and any have
N S Mp(H.e).
We will also need a lemma about covering a ball by smaller balls. This is probably also already known, and uses standard proof (see Pollard, 1990, Lemma 4.1), but we haven't found reference for it.
Lemma A.8. Let
d be a positive integer,
|| be norm
p be the metric induced by || I|. and
K, 6 O.
A ball in Rd of radius K w.r.l. p can be covered by (2x) balls of radius
Proof. We may assume without loss of generality that ball w.r.t. p Rd. Then the volume of any a-ball with respect to p is a²q, Let be the ball of radius in Rd. The c/2-balls centered at the members of any e-packing of B are disjoint. Since these centers are contained B, the balls are contained in a ball of radius ń + c/2. Thus
Let q O be the volume of the unit
MD(B,e) e) ( a K
d
3R
q
g.
2
Solving for (D( e) and applying Lemma A.7 completes the proof.
We prove Lemma 2.3. Let || be the witnessing the fact that G is (B, d).issiis parameterized, and let be the unit ball Rd w.r.t. ||. and let p be the metric induced by || Then, for any e, an e/ B-cover of B w.r.t p induces an e-cover of G w.r.t. Pmax.
N Nomn (G, S (B(B,e/B))
Applying Lemma A.8, this implies
3B d
No (G,e) S
Then applying Lemma A.3, Lemma A.4 and Lemma A.5 completes the proof.
B PROOF OF (1)
For 8 > O, and for each j N. let B3 x 2 let 65 25 Taking union bound over an
application Theorem 1. for each value of j. with probability at least - E, dg 2 - 6, for all j. and all f E F3,
C(W(3, + log(An)) + log(j/0))
E.
and
W(3, + log(A)) + log(j/8)
Ex-p(fy(3]] Es]ly(>)] + CV
13

---

Published as a conference paper at ICLR 2020
For any K, if we apply these bounds in the case of the least such that || - Kullo - B3, get
- Ez-pley(3)) < (1+))) C(W - Kollo + + (oo Kollo)/o)
and
Ez-ples(=)] Es [s(e)(=)] + CV W (2)lK Kollo + log(A)) log([og([] K - Kolla//))
and simplifying completes the proof.
C THE OPERATOR NORM OF ()(
Let J = =(K K.6". Since |/op(<())l 1 || [lop(J)ll it suffices find //)p()
For the rest of this section, we number indices from 0, let [d] = {0. 1}. and define w exp(2ri/d) To facilitate the application of matrix notation, pad the x x tensor J out with zeros make d x d X tensor J.
The following lemma is an immediate consequence of Theorem 6 of Sedghi et al. (2018).
Lemma C.1 (Sedghi al. (2018)). Let be the complex d matrix defined by Fij w
For each E [d] x [d], let p(a.)) be the x matrix given by plu.v) (FT J...k,F) Then
[|op(J]]lz max |(
First, note that, by symmetry, for each and v, all components of p(ua)) are the same. Thus,
|| = c/P(N
(3)
For any u,
Σ
www "4
I ck?
p.q
and p(0.0) = ek2. Combining this with (3) and Lemma C.I, op(()] eck2 which implies ||op())] Il1 1 eck
D PROOF OF LEMMA 3.2
For each convolutional layer i, let 3, = ( I|.. and, for each fully connected layer let 7/ [)v(() 12.
Since f X-Lipschitz w.r.t. its first argument, we have that [((ff()),)))))))))))))))(()))))) ((f(()) v) S Affe(z) fa (=)) Let gup be the function from the inputs to the whole network with parameters θ to the inputs to the convolution in layer j, and let Jaown be the function from the output this convolution to the output of the whole network, that Se Sdown [oo(K()) Sup. Choose input x to the network, and let (z). Recalling that ||>||| < X. and that the non-linearities and pooling operations
non-expansive, we have ||u]|| < III (p((
I|,
Using the fact that the non-linearities are
K<
14

---

Published as a conference paper at ICLR 2020
1 I-Lipschitz, have
(x) Se [a()]]= = 1g (op K K())a)
-down (op( (x)))
op(
ooppp (
II
1 )m op((R()))))
-pp(k |uu||
X
(F)
(I[a+t+1a) [loeccon) - op(()(0))1
x x
[ + + 8.)
where the last inequality uses the fact that op (()) - op( K66 (k )|( S 3 for all i, [|V() Vo'h 1|2 S
Di for all i, || op( (K) K60 1|2 I 1 + for all and ||v/0)|2 1|2 I 1 + for all
Since (Ile,) + v + 3.)
(II, (1 + 4 + < (1 8.)) (TI, (1 + +x)). and the latter
is maximized subject to E Bt) + E. S 3 when each summand is 3/ L. this completes the proof.
E PROOF OF LEMMA 3.3
For each convolutional layer i, let B. (lop(K()) op (p(KK()))l 1|2 and, for each fully connected layer i, let 7/- ||v(() - 1
Since e is X-Lipschitz w.r.t. its first argument, we have that (e(fe(z),)))))))))))))(()))))( v) ((f((z) v) ())e(z) Le ( Let Sup be the function from the inputs to the whole network with parameters θ to the inputs to fully connected layer layer j. and let Jdown be the function from the output of this layer to the output of the whole network, so that fe Idown o fyus o 9up. Choose an input x to the network, and let u = (x). Recalling that ||==|| S X. and that the non-linearities and pooling operations are
non-expansive, we have ||u|| S x II |oOCK
II
Thus
[ fa(x)) = 19down (v))) - Idown! (V()
[1ool1] (/)) ||rOle 1100l-vchaa
ドンj
|066 11ool1 |uu||
i>j
II (1o0 |0a -
xx
xx [[(+++8))
| - -60
Since [I1 B,)) (Th (1 + + < [[ 8.))
and the latter
is maximized subject to (E; Bi) E. when each summand is 3/ TT, this completes the proof.
15


Reviews:
[{"review_id": "rkegKo2aKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThis paper studied the generalization power of CNNs and showed several upper bounds of generalization errors. Their results have two characteristics. First, the bounds are in terms of the quantity that is independent of the input dimension (size-free). Second, the upper bounds involve the distance between initial and learned parameters. These results improved the upper bounds that we can derive by naively applying the results of Bartlett et al. (2017) or Neushubar et al. (2017), because the dominant term of the existing upper bounds contained $l_{2, 1}$ or $l_2$ norms, which could depend on the input dimensions in the worst case. The authors empirically showed that there is a correlation between the generalization error of learned CNNs and the dominant term of the upper bound (i.e., the product of the parameter size and the distance from the set of initial parameters).\n\n\nDecision\n\nTo the best of my knowledge, this is the first work that proved the size-free generalization bound for multi-layer CNNs. However, I think the assumption on the hypothesis class is very restrictive and significantly eases the problem, as I discuss in detail later. Therefore, I judge the technical contribution of the paper is moderate and recommend to reject the paper weakly.\nBy the standard argument of the statistical learning theory (such as Theorem A.4), we can typically bound the generalization error by $O(B\\sqrt{D/N})$ where $B$ is the infimum of Lipschitz constant of hypotheses, $D$ is the intrinsic dimension of the hypothesis class, and $N$ is the sample size. Therefore, we can derive the size-free generalization bound if $B$ does not depend on the input dimension. Since the hypothesis class $F_\\beta$ is defined via the spectral norm of CNNs, it is not surprising that we can derive the size-freeness of $B$. The size-free generalization bound has been already proven by Du et al., (2017), although it was the two-layered case. They imposed a restricted eigenvalue assumption. I think it implies that we need more sophisticated analysis if we do not assume the size-freeness of the hypothesis class.\n\n\nComments\n\n- The authors claimed that Figure 3 is consistent with theorems because, according to the upper bound of theorems, the distance from the initialization point decreases when the generalization error is the same and the parameter size increases. However, I think it is too aggressive to conclude it from Figure 3 because the decreasing trend in the value of $\\|K-K_0\\|_\\sigma$ is found only around $2\\times 10^6\\leq W \\leq 3\\times 10^6$. Furthermore, the value of $\\|K-K_0\\|_\\sigma$ for  $W\\approx 5\\times 10^5$ is approximately the same as the value for $W\\approx 3\\times 10^6$.\n\n\nSuggestions\n\n- Please add the conclusion section which summarizes the paper and discusses the possible research directions.\n\n\nMinor Comments\n\n- page 1, section 1, paragraph 1\n\t- ... with roots in (Bartett, 1998) , is that ... → Use \\citet\n- page 2, section 2.1, paragraph 2\n\t- Write the definition of \"expansive\" activations.\n- page 3, section 2., theorem 2.1\n\t- I think we should replace $\\log(\\lambda n)$ and $\\log(\\lambda)$ in equations with $\\log(\\beta \\lambda n)$ and $\\log(\\beta \\lambda)$, respectively.\n- page 3, section 2.2, definition 2.2\n\t- $N$ → $\\mathbb{N}$", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1xkWFYgcr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the generalization bound for deep neural networks, specifically, convolutional neural networks, which is one of the popular and crucial topics in the machine learning community, which has gathered a lot of attention.\n\nThe paper presents a generalization bound based on the number of parameters, the Lipschitz constant of the loss function and the distance of the final weights from the initialization, without dependence on the dimension of the input. The bound improves upon previous bound in some regimes when the size convolutional kernel is much less than the width of the network, which is a reasonable assumption. The paper also gives another bound which works for fully connected layers with an additional term that is linear with the depth of the network. \n\nThe paper has some nice ideas, but the contribution of the paper is not clear for me. The main theorems are based on previous results (Lemma 2.3). And the remaining work of the paper is mainly deriving the Lipchitz bound to be used in the theorem for various kinds of networks. I think this should be clearly stated in the paper.\n\nThe experiment part is not quite convincing. It is not clear from the figures that the norm decreases with the number of parameters in the network, which is claimed in the paper.\n\nThe writing of the paper also can be improved. The paper presents math, which is nice, but without much intuition explained.\n\nOverall I would not recommend this paper for admission.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Byx_mr2g9H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper describes new norm-based generalization bounds that were specifically adapted to convolutional neural networks. Since convolutional neural networks do not explicitly depend on the input dimension, these bounds share the same property. Further additional improvement over Bartlett et al. ‘17 bound, is that this new bound depends on the sum of the operator norms of the parameter matrices, rather than the product.\n\nThe paper is clearly written and self-contained. I appreciate that the authors added a detailed comparison to Bartlett et al. ‘17 bound. However, the main result seems to be very incremental. The experiments are also very limited and not too convincing. Further empirical evaluation is needed to demonstrate progress. I would be willing to increase my score if the authors added a comparison to Wei and Ma ‘19, and more evidence was provided that the bound is tighter for typical convolutional networks found in practice (please see detailed comments below).\n\nDetailed comments:\n\nI see Wei and Ma ‘19 cited in the beginning only, but there is no further comparison. They also proved bounds with similar dependencies. How do the bounds presented in the paper compare to Wei and Ma bounds?\n\nWhat is the dependence of the constant C on \\eta in the bounds presented in Theorem 2.1? It is unclear what trade-off comes with eta and how the empirical risk term is balanced with the complexity term, since \\eta only appears next to the empirical risk term.\n\nThe authors demonstrate via a concrete example that there exists a setting (depending on epsilon), under which this new bound (up to constants) is tighter than Bartlett et al. bound. Three things remain unclear to me:\n - How do the constants differ? Is the bound presented in the paper tighter in absolute terms?\n - Is the bound tighter when the norms in the bounded are measured on typical trained neural network weights? An analysis of a few networks used in practice would make the comparison more meaningful (included the comparison to Wei and Ma).\n - Is the bound not worse than a VC bound in any (reasonable) setting? If not, is the bound tighter under typical settings when training standard vision networks?\n\nOther minor comments. In the introduction, the authors: \n - say that their bounds are size-free, which refers to the bounds not having an explicit dependence on the input size. In my opinion, this comes almost “for free” when using convolutional neural network. Also, I think that size-free in the title is misleading, and should be replaced with input size-free.\n - mention that most recent bounds depend on the distance from the initialization instead of the size of the weights. This idea was first presented in Dziugate and Roy ‘17, which does not seem to be cited there.\n\n\n*** UPDATE ***\n\nI've reread the rebuttals and feel that most of my concerns have been addressed. I increased my score to weak accept.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present several theorems bounding the generalization error of a class of conv nets (CNNs) with high probability by 
    
      O(sqrt(W(beta + log(lambda)) + log(1/delta)]/sqrt(n)), 

where W is the number of weights, beta is the distance from initialization in operator norm, lambda is the margin, n is the number of data, and the bound holds with prob. at least 1-delta. (They also present a bound that is tighter when the empirical risk is small.)

The bounds are "size free" in the sense that they do not depend on the size of the *input*, which is assumed to be, say, a d x d image. While there is dependence on the number of parameters, W, there is no implicit dependence on d here.

The paper received the following feedback:

1. Reviewer 3 mostly had clarifying questions, especially with respect to (essentially independent) work by Wei and Ma. Reviewer 3 also pressed the authors to discuss how the bounds compared in absolute terms to the bounds of Bartlett et al. The authors stated that they did not have explicit constants to make such a comparison. Reviewer 3 was satisfied enough to raise their score to a 6.

2. Reviewer 1 admitted they were not experts and raised some issues around novelty/simplicity. I do not think the simplicity of the paper is a drawback. The reviewers unfortunately did not participate in the rebuttal, despite repeated attempts.

3. Reviewer 2 argued for weak reject, despite an interaction with the authors. The reviewer raised the issue of bounds based on control of the Lipschitz constant. The conversation was slightly marred by a typo in the reviewers original comment. I don't believe the authors ultimately responded to the reviewer's point. There was another discussion about simultaneously work and compression-based bounds. I would agree with the authors that they need not have cited simultaneous work, especially since the details are quite different. Ultimately, this reviewer still argued for rejection (weakly).

After the rebuttal period ended, the reviewers raised some further concerns with me. I tried to assess these on my own, and ended up with my own questions.

I raise these in no particular order. Each of them may have a simple resolution. In that case, the authors should take them as possible sources of confusion. Addressing them may significantly improve the readability of the paper.

i. Lemma A.3. The order of quantification is poorly expressed and so I was not confident in the statement. In particular, the theorem starts \forall \eta >0 \exists C, .... but then C is REINTRODUCED later, subsequent to existential quantification over M, B, and d and so it seems there is dependence. If there is no dependence, this presentation is sloppy and should be fixed.

ii. Lemma A.4, the same dependence of C on M, B and d holds here and this is quite problematic for the later applications. If this constant is independent of these quantities, then the order of quantifiers has been stated incorrectly. Again, this is sloppy if it is wrong. If it's correct, then we need to know how C grows.

Based on other claims by the authors, it is my understanding that, in both cases, the constant C does not depend on M, B, or d. Regardless, the authors should clarify the dependence. If C does in fact depend on these quantities, and the conclusions change, the paper should be retracted.

iii. Proof of Lemma 2.3. I'd remind the reader that the parametrization maps the unit ball to G. 

iv. The bound depends on control of operator norms and empirical margins. It is not clear how these interact and whether, for margin parameters necessary to achieve small empirical margin risk, the bounds pick up dependence on other aspects of the learning problem (e.g., depth). I think the only way to assess this would be to investigate these quantities empirically, say, by varying the size and depth of the network on a fixed data set, trained to achieve the same empirical risk (or margin).

I'll add that I was also disappointed that the authors did not attempt to address any of the issues by a revision of the actual paper. In particular, the authors promise several changes that would have been straightforward to make in the two weeks of rebuttal. Instead, the reviewers and myself are left to imagine how things would change. I see at least two promises:

A. To walk back some of the empirical claims about distance from initialization that are based on somewhat flimsy empirical evaluations. I would add to this the need to investigate how the margin and operator norms depend on depth empirically.

B. Attribute Dziugate and Roy for establishing the first bounds in terms of distance from initialization, though their bounds were numerical. I think a mention of simultaneously work would also be generous, even if not strictly necessary.

Decision: Accept (Poster)