A Multicover Approach to Neural Networks Sample Complexity

• The new multicover technique is only used to recover known bounds. Therefore, it is not clear that the new techniques will be useful to prove new results. The authors claim that the fact that covering number do not work well inductively is a major flaw, however solving this major flaw does not seem to lead to better theoretical results directly. It could be beneficial to include additional discussion on the type of settings/assumptions/architectures under which the multicovers can improve existing results or prove new ones.

• Several `well-known' results are cited without references, including these references would help the readers a lot, for instance in Lines 72, 78. In general a more in-depth literature review (regarding sample complexity bounds neural networks and how they are related to coverings) might be missing (there are only 11 references, including classical textbooks). For me, it makes it hard to judge the novelty of the work. I am not an expert on the question, but the following papers might be relevant: Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. Simon Du and Jason Lee. On the power of over-parametrization in neural networks with quadratic activation. Guohao Shen - Exploring the Complexity of Deep Neural Networks through Functional Equivalence.

• Several notations are used before they are defined, eg, in Section 1.1 or Lemma 2.1. The notations section should be moved at the beginning of Section 1.1.

• As multicover calculus seems to be very closely related to the previously introduced notion of Approximate Description Length (ADL). Therefore, one may ask what do multi covers bring compared to ADL. This fact should be discussed in greater detail in the main part of the paper.

A very poorly written manuscript. There is no readability. The manuscript is just a listing of basic facts and simple existing lemmas of covering numbers with lots of typos and unclear definitions. The final claimed result is nothing but a recovery of the results in Daniely & Granot (2019) without proper comparison with existing results and shows no advantages over the existing one (overclaimed in the abstract).

The authors show little care for presentation. There are many typos, concepts being used before their definition, and, more generally, the writing makes ideas much harder to understand than necessary. It gives the impression that the work was produced in a hurry.

Still, to the extent I managed to check, what the authors write seems to be correct in essence, at least, so I guess this community tolerates the disregard for communication. Accordingly, I concluded that the fairest course of action would be

1. Lean towards rejection based on presentation, as this is the only aspect I managed to evaluate properly;
2. To assign minimal confidence to the review (suitably warning the AC), as it is unfeasible for me to fully evaluate this work. This also mitigates the weight of the rejection recommendation.

To be clear, I normally would have enough expertise in the relevant areas to review the paper so the allocation system is not to blame. It is the presentation that, in my opinion, makes it so that reviewing this work with a reasonable amount of effort requires someone specialized in the very specific literature around it (e.g., authors of related works).

1. While the multicovers technique is shown to be effective for deriving tight sample complexity bounds for deep neural networks with smooth activation functions, as established by previous ADL methods, further discussion is needed on how this technique could enhance the exploration of sample complexity in areas of deep learning that have not been thoroughly investigated. This includes potential applications to other deep learning models and fields, and how multicovers might provide insights or advancements in those contexts.

2. There are some typos in the paper, and the authors should conduct a thorough review to correct these issues.

Considering related work, it appears that the sample complexity bound achieved in this work is essentially the same as the one achieved via ADL, up to polylog factors. It also requires smoothness property that a relevant portion of prior work does not require. The notion of multicover is nevertheless interesting in its own right, as it is more tightly related to the standard notion of covering adopted in classical uniform convergence results.

Moreover, the authors somewhat overlooked a thorough comparison with relevant prior work. This causes a lack of contextualization (albeit only to some extent) for the results contained in this submission. It also causes to miss the (still ongoing, apparently) debate about on the practical utility of characterizing the generalization for neural networks via uniform convergence. The authors should at least provide some clarification about the discussions in, e.g., [1-4].

Unfortunately, the overall writing is lacking clarity and, in some parts, even detail. It is often the case that some specific notation is used way before its actual definition (as in a different section). Typos and misuse of the English language are also particularly frequent throughout the entire text. Readers might easily be hindered by these shortcomings in the overall presentation, thus hindering a smooth and complete understanding of the results in this work. Except for the introductory part, these issues are so radicated that fixing them would require a fundamental restructuring of the overall structure of the submitted paper (e.g., reordering sections and fixing typos seem unavoidable).

References:

[1] Nagarajan & Kolter. "Uniform convergence may be unable to explain generalization in deep learning". NeurIPS 2019.

[2] Neyshabur, Li, Bhojanapalli, LeCun, & Srebro. "The role of over-parametrization in generalization of neural networks". ICLR 2019.

[3] Negrea, Dziugaite, & Roy. "In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors". ICML 2020.

[4] Koehler, Zhou, Sutherland, & Srebro. "Uniform convergence of interpolators: Gaussian width, norm bounds and benign overfitting". NeurIPS 2021.