Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new generalization bound for deep neural networks based on the effective depth. The idea is motivated by the empirical observation that neural networks’ representations exhibit neural collapsing. The authors define the notions of effective depth and minimal depth of a neural network, and establish a generalization bound based on the comparison between them. The paper also provides empirical estimation of the bound which is shown to be tighter than previous bounds.
strength_and_weaknesses: Strength:
- The idea of establishing a generalization bound based on the neural collapsing phenomenon is novel and interesting.
- The experiments are comprehensive and details are provided.

Weakness:
- It's unclear whether some of the technical settings are necessary. For example, I don't see how the specific structures of Conv-L-H and MLP-L-H come into play in the theory.
- I somehow feel the first term in the bound could be pretty large, hence making the bound vacuous. The authors provide some experiments to justify that the term is small, however, the way they compute d_min is by relying on the implicit bias of SGD, which is really not reliable since SGD may not be able to find really the best shallow network that fits the data. I wonder we can find a smaller d_min with the following algorithm: given some target depth d, we train a (d-1)-layer NN classifier to achieve less than eps error, then we embed the last linear layer into an additional layer by add a bunch of 0 weights. Would this lead to a d-layer NN with epsilon error? If so I feel this might give us a smaller depth than train d+1 layer NN and then chop off the last linear layer.
clarity,_quality,_novelty_and_reproducibility: The paper is clear and novel, the writing is of reasonably good quality.
summary_of_the_review: I think this paper provides a novel perspective of generalization bounds from the angle of neural collapsing. Although the theory is not complicated, it's idea is novel as far as I can tell, and could be of interest to many theoreticians in the ML community. Thus I would be happy to see this work getting accepted.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes a method for evaluation the generalising capabilities of neural networks through neural collapse
strength_and_weaknesses: Strengths:
- I kind of like the idea of evaluating neural collapse for measuring generalisation.
- Mathematical analysis seems interesting (although I did not check it in detail).

Weakneses:
- I am not convinced that this is better measure than what is already present as there is real no proof of that. In the introduction and other parts it states "In many practical settings [...] making the bounds vacuous". This is repeated several times, but I failed to see an in-depth analysis of those "practical settings" and what are those "vacuous bounds". One finds something at the end of section 3 but is the same repetition about vacuous bounds and sqrt(m), and not an in-depth analysis in how it compares to the other "classical measures". It all becomes very vague and repetitive when addressing the advantages of the presented measure when compared to those "classical" ones.
- All plots are awful as they are barely visible. Labels must be font size 2.
clarity,_quality,_novelty_and_reproducibility: Clarity and quality is not the strength of this paper as plots are ridiculously small and one can barely guess what they show. Reproducibility I did not see a link to the code used to produce the values in tables and figures.
summary_of_the_review: I have mixed feelings. I am up for new ideas, but the paper does not do a good job on:

 1. Showing that is better measure than other measures. Instead of repeating over and over that "classical measures" provide "vacuous bounds", how about using that space for and in-depth analysis and comparison with each one of those measures?. and 

2. I do not think authors spent the time necessary on the figures so that the reader would not need a microscope to see what is plotted there.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to understand the generalization of deep neural networks. It characterizes the effective depth as the first layer for which sample embeddings are separable using the nearest-class center classifier. Then a generalization bound based on the effective depth is suggested as an indicator of generalization performance. Some experiments are conducted to validate the effectiveness of this bound in estimating the generalization. 



strength_and_weaknesses: Strength:
- Several insightful phenomena are observed (or validated): the network collapses until very late. The collapse in the middle layers matters for generalizations. 
- A theoretical generalization bound in effective depth is proposed, the bound can serve as a good indicator for MLPs and ConvNets.

Weakness:
- The experiments are only done for ConvNets and MLPs, how does this estimation work for more practically used architectures such as ResNets or Transformers? 
- The plots are very difficult to read because they are way too small.
- The author did not provide enough support on why the current bound is better than what have defined before. 
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to understand, but the figures are bad. 
summary_of_the_review: This work points to a new angle of understanding the generalization performance -- how neural collapse in the middle layer affects generalization. The neural collapse in the middle layer is further quantified by the "effective depth". The only concern that comes from the reviewer is the gap between theory and practice. It would be nice to see some experiential results on more "advanced" neural networks.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The submission proposes a very interesting theoretical analysis of the implicit bias of SGD to produce networks with low effective depth.  They subsequently develop a generalization bound that appears to have strongly improved performance over those based on uniform convergence bounds, giving non-trivial generalization bounds when others are in practice completely vacuous.  These results are interesting, and I strongly believe they should in the end be published in a good quality ML venue.  I have concerns, though, about the current presentation.  The reviewers were unanimous in their opinion that the clarity of the submission is lacking, and that improvement over classical results was not sufficiently demonstrated.  With the rebuttal text, and additional results, this becomes more convincing, but the presentation in the paper is not very clear, and the significance not clearly stated.  The real results are hidden in tiny figures with tiny font, and not stated sufficiently clearly in the results and discussion, although the background results in the introduction are improved.  The paper has improved over the initial submission, but needs a thorough revision, and clear statement of improvement in bounds that has appropriate emphasis and discussion in the results, discussion and conclusions of the paper.  Making clear figures to illustrate this may not fit in the page limits for a conference like ICLR, and so either the focus of the paper might need to change to fit in a conference format, or a journal might need to be considered.

Theoretical justification of architecture choices missing, this can be OK, but the question from the first reviewer wasn't really answered in the rebuttal.
justification_for_why_not_higher_score: The presentation of the main results is too implicit, and the figures and tables are borderline unreadable without constant zooming.  The submission simultaneously doesn't say enough explicitly in the discussion of results, and is unclear in the figures presenting the results.  The results are indeed important and good, but need a substantially improved presentation to have an appropriate impact.
Decision: Reject