Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proves generalization bounds for both convolutional and ResNet networks. In both cases, both the parameter counting approach and the norm-based approach are explored. 

CNN-Norm based (Theorem 3.5, first equation): Similar to [1] expect that it relies on L2 norms instead of L\infty norms and therefore scales slightly differently depending on the regime. The main aspects are that the dependence on the input to each layer is larger than in [1] since it involves the whole of the input rather than a single convolutional patch, but on the other hand there is a factor of the post pooling width from [1] which disappears. The two could compensate each other or be in favour of one or the other bound. The norm in the batch direction is L2 instead of L\infty as well, which is an advantage in the presence of outliers, but makes the dependence on the number of classes worse. 

CNN-Parameter counting (Theorem 3.5, second equation): Similar to [3], better management of constants (it becomes explicit), cleaner proof. Other claimed improvements are not significant. Just like [2] the bound basically says that the sample complexity grows as the number of parameters.


Resent- Parameter counting: Similar to [3] in terms of the approach, but solves a different problem and offers some of the first bounds on resnets. Neat exercise but no significantly original content. Just like [2] the bound basically says that the sample complexity grows as the number of parameters.

Resnet- Norm based: similar extension of [1] but still a very long and tedious exercise (due to the larger number of connections in the architecture) which was successfully executed. 











[1] Antoine Ledent, Waleed Mustafa, Yunwen Lei and Marius Kloft. " Norm-based Generalisation bounds for convolutional neural networks"

[2] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. "Spectrally-normalized margin bounds for neural networks". NeurIPS 2017.

[3] Philip Long and Hanie Sedghi. "Generalisation bounds for deep convolutional neural networks". ICLR 2020.
strengths_and_weaknesses: 
Strengths: 

++This is a long paper with a lot of work and is quite clean and well organised. It contains a good encyclopaedic summary of the field and of many frequently misunderstood issues. 

+ A lot of progress since previous submission

Weaknesses:  

- No substantial originality in the techniques.
- Some issues not corrected since last submission.



NUMERICAL CONSTANTS: 

There is some slight dishonesty going on, including an error, in the treatment of numerical constants here: the authors results involve a constant of 12, which looks better than the corresponding constant of 36 in Bartlett et al [2]. This is only partially true. 

First of all, there is an error in the constant in [2], and it should be 72 instead of 36 (the authors correctly divide the constant of 72 from [2] in Lemma A.8 because they are looking at Rademacher complexity without explicitly writing the results in terms of generalisation bounds. However, the correct version of Lemma A8 should be with a constant of 144. Indeed, the function class which is studied in Lemma 3.2 in [2] includes only a (2,1) norm constraint, but no constraint on the spectral norm. In the proof of Theorem 3.3, a cover on a function class including both constraints is used instead (such a cover can be obtained up to a factor of 2 by a simple extra argument).  This is a very subtle error, which is inherited in the present paper (not in [1]), so a priori anyone could be forgiven for overseeing this. However, I reviewed this paper for ICML this year, pointed out the error to the authors, and they agreed with me in the rebuttal and agreed to fix it, which they haven't done!


Next, the improvement in the constant compared to [2] (and to a lesser extent to [1]) is partially illusory. Note that there is a factor of 2 in both [2] and [1] which comes from the 2-Lipschitzness of margin-based loss functions. Here the authors do not work with a last layer loss function and work directly with the Rademacher complexity of the function class defined by the network, so the improvement in the constant is just due to solving a slightly different problem. 

Regarding the comparison to [1] in terms of numerical constants, it is correctly pointed out in line 654 (sup) that some may be unavoidable but that the bound from [4], where, according to the current paper "the constants are nor optimized". This is quite a bold statement. The results in [4] are very different and much much harder to prove that the Maurey type results used here and in [2], since they rely on L\infty norms. There is a good chance the constants are unavoidable if one goes for the L\infty approach. 


IMPROVEMENT COMPARED TO [3]


I guess we just have to agree to disagree here but again, the improvement in the parameter counting result compared to [3] is purely in terms of the proof technique and clarity of exposition (and maybe slightly in the constant). Both [3] and the present paper somewhat misleadingly claim that the results "take distance to initialization into account", with the present paper also claiming that they do so "more naturally" (see line 264), but fundamentally, in both bounds, the square root of the number of parameters is both conceptually and numerically the dominant term, and distance to initialization is only present in the logarithmic factors. The authors explain this quite clearly in other parts of the paper, so I think they understand the point. 



TWO LAST POINTS REGARDING COMPARISON TO [1]

I would like to see a comparison with the two layer version of [1]. Indeed, the factor which comes from changing between norms and scales similarly in [1] and the present paper depending on the regime is intuitively parasitic (though it seems difficult to get rid of it entirely and neither the current paper nor [1] succeed). However, in the two layer case, it is absent from [1]. I would expect the bound from [1] to be uniformly superior in this case (of course since it only applies to 2 layers it doesn't make the present paper irrelevant in general). 
Note also that the parasitic  factor can be reasonably removed from [1] in the general case at the cost of extreme cost in terms of computations (rather than loss of statistical power) by simply certifying the Lipschitz constant of the network with respect the the appropriate norms in a sufficiently large neighbourhood of all inputs.









SMALL TYPOS

Line 1089, capital letter for "For"
 Line 213 "we further fixate..." --> "we further fix"






[1] Antoine Ledent, Waleed Mustafa, Yunwen Lei and Marius Kloft. " Norm-based Generalisation bounds for convolutional neural networks"

[2] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. "Spectrally-normalized margin bounds for neural networks". NeurIPS 2017.

[3] Philip Long and Hanie Sedghi. "Generalisation bounds for deep convolutional neural networks". ICLR 2020.


[4] Tony Zhang, "Covering number bounds of certain regularised linear function classes". 
questions:    
limitations: Originality, though I don't think this should be viewed too negatively as the community also needs papers like this one, especially if the claims of originality are further toned down.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper provides new bounds for Rademacher complexity for neural networks and analyses their effect empirically. Most importantly, skip connect and convolutions are handled jointly, whereas normalisation techniques are not considered. A comparison to the existing literature is implemented. Exp[eriments try to emphasise how there is an excess in capacity and how it can be reduced. However, implementations seems to be cumbersome for now and not fully practical.
strengths_and_weaknesses: Significance
************

The relation to the state of the art is well presented. Especially, the inclusion of convolutions and skip connections is making a difference as well as the paper addressing how the respective Rademacher Complexities can be actually used for real world decision like changing the capacity of networks.

I really like Figure 1 and how it is representing the state of the art. Also, the "Relation to prior work." sections are very valuable, because they put the theorems in relation to other work and discuss advantages and disadvantages. Thus providing some valuable kind of literature overview.

According to my understanding of ResNet18, it is possible to linearly scale layers without impacting the decision boundaries. Hence, it is unclear how limiting the weight norm would impact capacity at all. What are the benefits of this "compression" and why is it called "compression" at all?

Previous work addressed convolutions and skip connections separately and it seems none addressed them sufficiently jointly.

A major caveat Is the lack of addressing normalisation techniques in the network to have ResNet18 fully addressed.

I feel like disagreeing on the necessity of data dependent bounds. I belief, model complexity and data complexity are strongly related.


Clarity
*******


The paper is very well structured and the separate steps are clear. References to the appendix are provided where required.

Whereas I am not experienced in Rademacher complexity proofs, I feel that the proof sketch fro Theorem 3.2 and the whole motivation are described very clearly.

The word "vacuous" should be replaced with a more common and less archaic word.
The figure on page 1 is missing a legend for the read dots and it is missing a caption/title/number/reference.

Tiny-ImageNet-200 is not sufficiently referenced and explained in line 304.

The experiments state that every 15th SGD update step, the projections procedure is applied but then the authors "increase the alternating projection steps to 15". 15 is not an increase of 15.

Table 1 mentions "the testing error is on a par with the unconstrained case". However, the error is no the same. So I assume that it means "the testing error is equal or better than the unconstrained case"?

Some more technical details on the experiments would be great.

It might be useful to quickly mention what the "empirical generalization gap" is and why it is important to measure.

The experiments need further clarification.

Originality
***********

The paper points out quite clear the relation to existing state of the art and how its boundaries are better than theirs. This is a great contribution in itself.

The derived boundaries seem to be non-trivial, especially since previous literature resulted in higher bounds.

It is great effort of the authors, not being satisfied with some new bounds but implementing a comparison to related work as well as addressing the respective values in empirical evaluations.


Quality
*******


The first figure needs some fixing. Overall, the paper is well structured and readable.
The paper states "Notably, modifications (2) and (3) do not harm performance, with
302 empirical testing errors on a par with a standard ResNet18 w/o batch normalization.", however, respective references are missing. Also, it is not clear, how much the quality of ResNet18 is reduced due to the lack of normalisation. This part needs much more discussion.
questions: Why can we apply Lipshitz constraints for h around line 215? I would have expected h to be unconstrained in normal deep learning.

How can Rademacher boundaries be established for the different normalisation techniques like group and batch normalisation, which are crucial parts of the algorithm. Is it possible at all to address them? If not, why? If yes, how?

Why is it not possible to run the experiments with larger networks and more importantly larger datasets?

Why are the experiments run for 200 epochs, even though even ResNet50 is able to converge in 35 epochs?

Can the limitation of norms for reducing the capacity also be achieved by different optimisers that consider layers separately like LARS or LAMB?
limitations: Complex networks, require normalisation techniques like batch norm or layer norm. These are not addressed by the paper, which is a major limitation. Whereas skip connections and convolutions are crucial for generating meaningful features and getting a large network depth, normalisation techniques are crucial for convergence.

Another limitation is that the reduced capacity in the experiments does not really have an impact on the model size and expressivity and seems more artificially related to the provided new Rademacher complexity bounds. They could be however more a sign of the insufficiency of the bounds and the benefits of regularization than the real power of the new bounds.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose an extension to prior Rademacher complexity bounds to account for more realistic neural network architectures used in practice, specifically convolution and skip connections, as found in Residual Networks, a modified form of which are also used in the empirical results. The extension relies on two capacity terms: the Lipschitz constants of each of the layers, and the (2, 1) group norm distance to the initialization of the conv filter weights. The authors show experiments based on training a modified ResNet-18 model without batch normalization across the CIFAR-10, CIFAR-100 and Tiny ImageNet classification datasets, and show that constrained models (i.e. models that have lower group norm and Lipschitz capacity terms) can achieve similar performance to models with excess capacity (reaching 100% training accuracy), while having similar capacity on what are presumed to be increasingly difficult tasks. The authors propose this indicates that, like known with parameter counts, neural networks are compressible w.r.t. weight norms.
strengths_and_weaknesses: Strengths:
* The paper is well written overall, with the motivation for the proposed capacity terms made clear, and appropriate background references
* The authors extend a complexity measure to more realistic settings — convolution all layers and skip connections are used in most contemporary neural network architectures for learning from images.
* The authors present a derivation of their proposed complexity measures

Weaknesses
* The intuition behind the capacity terms proposed was not obvious to me
* There are some reproducibility issues in the experimental results presented, notably it’s not obvious to me how the Lipschitz constant is calculated for different layers (only the classifier is explicitly addressed by construction from what I can see).
* The claim of independence of weight norm and parameter count doesn’t hold up in the real-world experimental setting. In particular, in the stated example of neural network pruning, it is often done in a manner explicitly attempting to preserve the weight norm (i.e. removing smallest magnitude weights).
questions: - The authors point to the fact that compressibility w.r.t. parameter counts is well known, but claim that their experimental results show a novel result — that neural networks are compressible w.r.t. weight norms. This presumes that weight norm and parameter counts are independent (or “orthogonal”). However, the authors use weight decay in their experiments, i.e. an L2 weight norm regularization term, and the variance of the common random initialization methods for NN layers (i.e. Xavier/He) explicitly depends on the parameter count of a layer. Can we really assume that weight norms and parameter counts are independent in the context of real-world neural network training?
- While the authors acknowledge that a significant problem in the field is that complexity bounds are often vacuous, it’s not obvious to me why complexity measures and related capacity bounds such as those explored in this paper would be a good method of analyzing excess capacity? 
- I don’t see any details on how the Lipschitz constant for all layers in the results section (i.e. Table 1) is calculated empirically, making it difficult to repeat these results.
- Training ResNets without batch norm often is problematic (increasing with depth), without using methods such as those outlined in the Fixup paper (Zhang et al., 2019). The authors don’t mention any such workarounds, and I’d just like to ask if the authors could comment on this?
- It’s not clear to me why layer-wise Lipschitz constant is important intuitively, as we do not perform layer-wise optimization? Isn’t the Lipschitz constant over all parameters (i.e. dimensions in the loss landscape) more relevant?
- Isn’t 1x1 convolution on a 1x1 spatial feature map a linear combination or dot product over the channels rather than matrix multiplication?
limitations: I saw no discussion of societal impact of this work. I think one potential question is if only looking at generalization, as done in this work, is an appropriate measure of compressibility. For example how different is the function learned in the constrained solution? Achieving similar accuracy over the entire test set doesn’t mean functions learned are similar or predictions on the same samples is similar (e.g. as analyzed in the Deep Ensembles work for different solutions). In particular, are the constrained models more/less biased in predictions to particular classes in a classification task?
review_title: null

Meta-review: metareview: This paper extends prior Rademacher complexity bounds to neural network architectures that include convolutions and skip connections. The paper is well-organized with a clear summary of the field and related work. The reviewers found that, although the techniques were not novel, the new results enhance the practical relevance of prior bounds and will be of interest to the theory community. A few technical points were raised and addressed during the discussion phase, but the consensus remains that this is a solid paper and should be published, and so I recommend acceptance.
confidence: Less certain
Decision: Accept