Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper discusses interplay of network width, depth and initialization on their average robustness with theoretical bounds. The authors show that width hurts robustness in the under-parameterized setting and improves robustness in the over-parameterized setting. Effect of depth depends on network intialization and training mode. In lazy training regime, depth helps robustness with LeCun initialization but hurts robustness with NTK and He-initialization. Under non-lazy training regime they demonstrate width helps robustness of a two-layer ReLU network. 
strengths_and_weaknesses: Strengths:
* Originality: The theoretical bounds derived by the authors studying network robustness wrt. depth, width and initialization are original. 
* Quality: The theoretical derivation are well established with analysis and numerical evidence. 

Weakness: 
* Clarity: Some statements in the paper is confusing: definition 2 calls the mesaurement perturbation stability while inidicating a small measurement implies more robust function: so low stability means high robustness ? Same goes for the remak in 4.1 
* Significance: The authors discussed the interplay of width, depth and initialization on network robustness and given the theoretical derivation found the effect on robustness has a change of phase as network goes from under-parameterized to over-parameterized which may settle some contradiction in previous literature, making a fair significance contribution. 

questions: 1. Some statements in the paper is confusing: definition 2 calls the mesaurement perturbation stability while inidicating a small measurement implies more robust function: so low stability means high robustness ? Same goes for the remak in 4.1 
2. In numerical evidence section 5.4, validation for depth only showed 2 choices of depth which could take more choices to be more convincing. NTK is also missing for validation. 
limitations: Theoretical assumptions are properly stated and explained.
review_title: null

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: The paper analyzes perturbation stability of fully connected feed-forward ReLU networks with respect to the networks width, depth, and initialization for the NTK regime, and with respect to width in the "non-lazy" regime. The results indicate that for overparameterized networks, stability increases with the width and that depth can increase or decrease robustness depending on the initialization. Moreover, the paper provides a criterion under which a network will train in the non-lazy regime (i.e., with large changes to the weights). The theoretical results are supported by an empirical evaluation.

The paper is well-written, the results are significant and interesting. The theoretical results are properly interpreted and empirically tested. This makes them quite insightful. This is a good paper. I vote for acceptance.
strengths_and_weaknesses: Strengths:
- insightful theoretical results
- empirical validation of theory
- in-depth interpretation of results
- reproducible (code is provided)

Weaknesses:
- some minor improvements in clarity are necessary
questions: - please define average robustness directly or at least be more clear how you use the terms (in the introduction, you use average robustness and $\epsilon$-stability interchangeably, in the remark after Def. 2 you clarify that $\epsilon$-stability is an approximation to average robustness).
- Def. 2 is a repitition from the intro and could be avoided
- the interpretation of the results could be written a bit clearer, in particular by using only $\epsilon$-stability or average robustness, so that it is more intuitive what it means if it goes up or down (also, exacerbate is a bit ambiguous here, since it can mean "make worse" or "enlarge", which was a bit confusing to me, in particular since I was not sure which of the two would be good).
- Out of curiosity: the results in [2] seem to indicate that flatness of the loss surface wrt. a single layer (independent of the rest of the network) implies average robustness. Can these results be related, e.g., through impacts of width and depth on flatness?
limitations: Please add a brief discussion on the difference of perturbation stability in expectation (as in Def. 2), and the also often used stability wrt. all data points (cf. [1]).

[1] Schmidt, Ludwig, et al. "Adversarially robust generalization requires more data." Advances in neural information processing systems 31 (2018).

[2] Petzka, Henning, et al. "Relative flatness and generalization." Advances in Neural Information Processing Systems 34 (2021): 18420-18432.
review_title: null

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 work explores the (average) robustness of neural networks with respect to the width, the depth, and the initialization. After related work and problem settings, it derives theoretical bounds on average robustness (measured by perturbation stability, defined therein) for lazy (Theorem 1) and non-lazy (Theorem 3) training regimes. Interpreting these results novel conclusions are derived shedding light on contradictions in the previous literature outlined in Related Work. The experimental section is brief (FFN on MNIST dataset, accompanied by CNN experiments on CIFAR10 in Appendix) but well selected and clearly in support of theoretical results derived.
strengths_and_weaknesses: To the best of the reviewer's knowledge, the work contains novel results and significantly extends the previous results on the robustness of neural networks. Experiments neatly presented in Figures, emphasize the main conclusions and suitably underpin the main narrative.

Significance is two-fold: 
Firstly, it is due to improving previous perturbation stability bounds by Theorem 1 (and 3 for non-lazy training regime), neatly captured in Table 1. making the difference obvious. 
The second novel result and perhaps evenly impactful is due to shedding light on previously contradicting results of the role of width related to robustness (discussed in the Related Works section as well). This is done by interpreting Theorem 1 (average perturbation stability upper bound for lazy training) and revealing a phase-transition-like phenomenon occurring in average stability w.r.t. width under a lazy training regime! This was only possible due to the less vacuous result of Theorem 1, compared to previous works.

Overall, the presented work is of high quality, clearly written, self-contained and wide in scope. Including a well-built argument and reasonably detailed proofs with preparatory lemmas (in appendix). The scope covers three different yet realistic initialization schemes (He, LeCun, and NTK) as well as lazy and non-lazy (limited to the two-layer net, but well-argued why in the appendix) training regimes.

Besides detailed proofs and additional experiments, the appendix includes a useful table of notation and analysis of the limitations of the work + comments on Societal Impact.

questions: Experiments use early stopping after 50 epochs. I understand that accuracy is not of concern given the scope of the work. Yet to confirm training has reached a somewhat reasonable level of loss, I suggest reporting on training/validation losses after early stopping is applied. It would further add to the clarity and relevance of the results. 
limitations: Nothing to add to what is elaborated on in appendices F and G.
review_title: null

Meta-review: metareview: This paper studies an average notion of robustness and its relation to the depth, the width, and the initialization scheme. The reviewers found the theoretical results insightful and novel, the empirical results thorough, and the paper overall well-written and of high quality. Therefore, I recommend acceptance.
confidence: Certain
Decision: Accept