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 presents lower and upper bounds for the number of parameters needed in a ReLU neural network to learn a robust classifier on well-separated data. The analysis considers robust training and testing error respectively, as well as general and linear separability and intrinsic low-dimensional structural assumption in terms of the structure of the dataset.
strengths_and_weaknesses: This paper addresses the underlying reason of the decay of robust generalization error observed in real-world experiments through analyzing the expressive capability of ReLU neural networks and thus establishes the desired hardness result based on the shown exponential lower-bound on network size, instead of usual algorithmic approaches which mainly constructs sample complexity or SQ super-poly lower-bounds for specific problem instances. Hence in terms of originality this paper potentially opens up interesting new techniques for investigating similar problems. The paper is also written clearly and its argument meets the desired technical quality for a deep learning theory paper.
However, it is unclear whether the bounds the paper presents are tight, which will make the results even more compelling if their optimality can be established as well. Another interesting analysis that is good to have is identifying in addition to data being well-separated, under what extra conditions is achieving low robust test error attainable with non-exponential network size (or even slightly super-polynomial). 
questions: In Def. 3.1, I assume you meant $\mathrm{sgn}(f(x')) \neq y$ instead of $f(x') \neq y$?

limitations: This paper is theoretical in nature, hence it should not have any potential adverse social impact.
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 studies the approximation power of feed-forward neural networks with ReLu activations (FFNs) to approximate robust functions. Robustness of a model is neccessary to avoid adverserial attacks. However, training a robust model seems to be hard. Different from prior studies on algorithmic aspects, this paper investigates approximation ability of FFNs. Four main results are presented, and indicate both possitive and negative aspects. The possitive result is that there exists a FFN with moderate size that has zero training error. The negative results are that, to ensure small test error, one may need FNNs with exponential size in dimensionality of data. This result also holds even under a separability condition. The authors provide both upper and lower bounds for the size of those FNNs. Those bounds can be improved when the data lies on a low dimensional manifold.
strengths_and_weaknesses: Strengths:
- This paper provides a novel view about the hardness of training robust models, by investigating approximation ability.
- The lower bounds on the network size seem to be novel and provide evidences for why training robust models are hard.


Weaknesses:
- The scope of this paper is unclear. This paper only studies FFNs with ReLu activations, and their results hold true for those families. However the current writing may make readers to confuse with general neural networks. Some other network families may have stronger ability, and the results of this paper may not hold true. The authors should indicate this point clearly from the beggining.
- The proof of the main theorems (4.3) seems to borrow some ideas or results from (Shen et al. 2022). One example is the connection between VC dimension and approximation error. However this point is not indicated in the paper. 
- The depth of FNNs seems not to be important in their bounds.

Minor: family F_{N_d} in Theorem 4.3 is not defined explicitly.
questions: The depth often plays an important role in approximation power of neural networks in non-robust settings. How about the role of depth in robust training?
limitations: NA
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 analyses the number of parameters of a ReLU neural network required for robust generalization. The results are derived by defining a function that would robustly classify (train and test) and to show that this function can be approximated by a ReLU network with a certain amount of parameters. The paper provides interesting insights into the required level of overparameterization both for achieving low robust training and test error, in particular showing that robust test error in general requires a number of parameters exponential in the data dimension. If data lies on a low-dimensional manifold, this can be mitigated, though. 

The paper is well-written, the theoretical results are sound, interesting, and relevant. I vote for acceptance.
strengths_and_weaknesses: Strength:
- strong theoretical results
- relevant analysis

Weakness:
- no empirical validation of the theoretical results
questions: - After Def. 1.1. the authors remark that data needs to be $\epsilon$-seperated to ensure the existence of a robust classifier. Although it might seem trivial, for me it would have been helpful to formalize this result. I honestly was thinking for a bit how a suitable representation of the data would make it $\epsilon$-separated until I realized that no representation can actually solve the problem, since we assume perturbations on the input data so that the required radius is transformed by the representation as well.
- Generalization bounds based on flatness of the loss surface (cf. Thm. 6 in [1]) guarantee low test error (the bound in [1] is also exponential in the dimension), but flatness of the loss surface also seems to imply a robust test error as defined in Def. 3.1, i.e., robustness in expectation. The bound in [1] is exponential in the dimension of the representation, not the input data, though. Is this related to the results on learning from a low-dimensional manifold? 
- Given the papers results on low-dimensional maniforlds, it would be great to also study the required number of parameters to project on such a manifold. To me it seems possible that a proper representaion reduces the overall number of parameters required. More formally, assume a robust classifier $f=\psi\circ\phi$ with representation $\phi$ and classifier $\psi$, if $\phi$ projects on a low-dimensional manifold and the projection requires only $n_1$ parameters and the manifold has an intrinsic dimension of $\mathcal{O}(\log n_2 / \log d)$ (following the result in Thm 5.5), then the network would have $n_1+n_2$ parameters which could be less than the exponential number of parameters predicted by Thm. 4.3.  

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

limitations: The theoretical results are not empirically verified.
review_title: null

Meta-review: metareview: This paper gives new lower bounds and upper bounds on the size of a feedforward ReLU network needed for robust generalization (and not just robust training error. In particular, they give an exponential lower bound on the size of the network, even for separable data. The reviewers were in agreement about the strengths the paper. This points one of the challenges in obtaining neural networks with robust test error. 
confidence: Certain
Decision: Accept