Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power
Authors: Binghui Li
Jikai Jin
Han Zhong
John E. Hopcroft
Liwei Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep learning theory
adversarial robustness
robust generalization gap
expressive power

Abstract: It is well-known that modern neural networks are vulnerable to adversarial examples. To mitigate this problem, a series of robust learning algorithms have been proposed. However, although the robust training error can be near zero via some methods, all existing algorithms lead to a high robust generalization error. In this paper, we provide a theoretical understanding of this puzzling phenomenon from the perspective of expressive power for deep neural networks. Specifically, for binary classification problems with well-separated data, we show that, for ReLU networks, while mild over-parameterization is sufficient for high robust training accuracy, there exists a constant robust generalization gap unless the size of the neural network is exponential in the data dimension $d$. This result holds even if the data is linear separable (which means achieving standard generalization is easy), and more generally for any parameterized function classes as long as their VC dimension is at most polynomial in the number of parameters. Moreover, we establish an improved upper bound of $\exp({\mathcal{O}}(k))$ for the network size to achieve low robust generalization error when the data lies on a manifold with intrinsic dimension $k$ ($k \ll d$). Nonetheless, we also have a lower bound that grows exponentially with respect to $k$ --- the curse of dimensionality is inevitable. By demonstrating an exponential separation between the network size for achieving low robust training and generalization error, our results reveal that the hardness of robust generalization may stem from the expressive power of practical models.

Why Robust Generalization in Deep Learning is Difficult: Perspective of Expressive Power
Binghui Li
Jikai Jin 2+ Han Zhong John E. Hopcroft'
Liwei Wang
School of EECS, Peking University
Sccooo of Mathematical Sciences, Peking University
Center for Data Science, Peking University 'Cornell University
National Key Laboratory of General Artificial Intelligence,
School of Intelligence Science and Technology. Peking University
* Cheng Laboratory PPazhou Laboratory (Huangpu) (libinghui, jkjiijj edu. en, hanzhong@stu, pku. edu. cn, jeh170cornell edu, wanglutcis pku. pku.edu. edu. cn
Abstract
It is well-known that modern neural networks are vulnerable to adversarial exam- ples. To mitigate this problem, series of robust learning algorithms have been proposed. However, although the robust training error can be near zero via some methods, all existing algorithms lead to high robust generalization error. In this paper, we provide a theoretical understanding of this puzzling phenomenon from the perspective of expressive power for deep neural networks. Specifically, for binary classification problems with well-separated data, we show that, for ReLU networks, while mild wver-parameterization is sufficient for high robust training accuracy, there exists constant robust generalization gap unless the size of the neural network is exponential in the data dimension d. This result holds even if the data is linear separable (which means achieving standard generalization is easy), and more generally for any parameterized function classes as long as their VC dimension is at most polynomial in the number of parameters. Moreover, we establish an improved upper bound of cxp(O for the network size to achieve low robust generalization error when the data lies dimension k (k < d). Nonetheless, we also have lower bound that grows ex- ponentially with respect A the curse of dimensionality is inevitable. By demonstrating an exponential separation between the network size for achieving low robust training and generalization error, our results reveal that the hardness of robust generalization may stem from the expressive power of practical models.
manifold with intrinsic
1
Introduction
Deep neural networks have achieved remarkable success in variety of disciplines including com- puter vision (Voulodimos et al., 2018), natural language processing (Devlin et al., 2018) as well as scientific and engineering applications (Jumper al., 2021). However, networks are often sensitive to small adversarial attacks (Biggio et al., 2013; Szegedy et al., 2013; Goodfellow et al., 2014), which potentially gives rise to reliability and security problems in real- world applications.
observed that neural
In light of this pitfall, is highly desirable to obtain classifiers that are robust to small but adversarial perturbations. A common approach is to design adversarial training algorithms by using adversarial
"Equal contribution. 'Corresponding author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

examples as training data (Madry et al., 2017; Tramèr et al.. 2018; Shafahi et al., 2019). Another line of works (Cohen et al., 2019; Zhang al., 2021a) proposes some provably robust models tackle this problem. However, while the state-of-the-art adversarial training methods can achieve high robust training aceuracy (e.g. nearly 100% on CIFAR-I0 (Raghunathan al., 2019)), all existing methods suffer from large robust test error. Therefore, it is natural to ask what is the cause for such a large generalization gap in the context of robust learning.
Previous works have studied the hardness of achieving adversarial robustness from different per- spectives. A well-known phenomenon called the robustness-and accurrryy tradeoff has been empirically observed (Raghunathan et al., 2019) and theoretically proven to occur in different settings (Tsipras al., 2019; Zhang et al., 2019). Dohmatob (2019) shows that adversarial robustness impossible to achieve under certain assumptions on the data distribution, while it is shown in Nakkiran (2019) that even when an adversarial robust classifier does exist, it can be exponentially more complex than its non-robust counterpart. Hassani and Javanmard (2022) studies the role of weerpparameterization on adversarial robustness by focusing on random features regression models.
At first glance, these works seem to provide convincing evidence that robustness is hard to achieve in general. However, this view is challenged by Yang et al. (2020), who observes that for real data sets, different classes tend to be well-separated (as defined below), while the perturbation radius is often much smaller than the separation distance. As pointed out by Yang et al. (2020), all aforementioned works fail to take this separability property of data into consideration.
Definition 1.1 (Separated data). Suppose that A,B
C R2d and e >
We say that A, B are 6-
separated under lp norm (1 S p S +00) if
. - xn 1 26, YaA E A, E B.
Indeed, this assumption is necessary ensure the existence of robust classifier. Without this separated condition, it is clear that there is no robust classifier even if non-robust classifier always exists, as discussed above.
Recently, Bubeck and Sellke (2021) shows that for regression problems, wer-paraamteerzation may be necessary for achieving robustness. However, they measure robustness of a model by its training error and Lipschitz constant, which has subtle difference with robust test error (Madry et al., 2017); see the discussions in (Bubeck and Sellke, 2021, Section 1.1).
To sum up the above, although existing robust training algorithms result in low robust test accuracy, previous works do not provide a satisfactory explanation of this phenomenon, since there exists a gap between their settings and practice. In particular, it is not known whether achieving robustness can be easier for data with additional structural properties such as separability (Yang et al., 2020) and low intrinsic dimensionality (Gong et al., 2019).
In this paper, we make an important step towards understanding robust generalization from the viewpoint of neural network expressivity. Focusing binary classification problems with separated data (cf. Definition 1.1) in Idd, we make the following contributions:
Given data set D of size N that satisfies a separability condition, we show in Section 2 that it is possible for ReLU network with Ö(Nd) weights to robustly classify D. In other words, an over-parameterized ReLU network with reasonable size can achieve 100% robust training accuracy.
We next consider the robust test error (cf. Definition 3.1). As a warm-up, we show in Section that, in contrast with the robust training error, mere separability of data does not imply that low robust test eтror can be attained by neural networks, unless their size is exponential in d. This motivates the subsequent sections where we consider data with additional structures.
In Section 4, we prove the main result of this paper, which states that for achieving low robust test error, an (xp))(d)) lower bound on the network size is inevitable, even when the underlying distributions of the two classes are linear separable. Moreover, this lower bound holds for arbitrarily small perturbation radius and more general models long as their VC dimension is at most polynomial in the number of parameters.
Finally, in Section we consider data that lies on a k-dimensional manifold (k < d), and prove an improved upper bound exp(O(A)) for the size of neural networks for achieving

---

Table 1: Summary of our main results.
Setting
Params
Robust Generalization
Robust Training
General Case
Linear Separable
k dim Manifold
((Nd)
exp(O(d)
exp(O(())
Upper Bound
(Thm 2.2)
(Thm 3.3)
(Thm 5.5)
(2vNNd)
exp(O(d)) (Thm 3.4)
exp ((()
exp(S((k)
Lower Bound
(Thm 2.3)
(Thm 4.3)
(Thm 5.8)
low robust test error. Nonetheless, the curse of dimensionality is inescapable the lower bound is also exponential in k:
The upper and lower bounds on network size are summarized in Table Overall, our theoretical analysis suggests that the hardness of achieving robust generalization may stem from the expressive power of practical models.
1.1 Implications of our results
Before moving on to technical parts, we would like first discuss the implications of our results by comparing them to previous works.
Our main result is the exponential lower bound on the neural network size for generalization. First, different from previous hardness results, our result is established for data sets that have desirable structural properties, hence more closely related to practical settings. Note that the separabilityy condition implies that there exists a classifier that can perfectly and robustly classify the data i.e. achieve zero robust test error. However, show that such classifier is hard to approximate using neural networks with moderate size.
Second, it is popular belief that many real-world data sets intrinsically low dimensional, al- though they lie high dimensional space. Our results imply that low dimensional structure makes robust generalization possible with neural network with significantly smaller size (when & < d). However, the size must still be exponential in k.
Finally, we show that there exists an exponential separation between the required size of neural networks for achieving low robust training and test error. Based on our results, we conjecture that the widely observed drop of robust test accuracy is not due limitations of existing algorithms rather, is a more fundamental issue originating from the expressive power of neural networks.
1.2 Related works
Robust Generalization. One surprising behavior of deep learning that over over-parameterizer neural networks can generalize well despite their ability to fit random data (Zhang et al., 2017: Belkin et al., 2019). However, in contrast the standard (non-robust) generalization, for the robust setting, Rice et al. (2020) empirically investigates robust performance of models based adversarial training methods, which are designed to improve adversarial robustness (Szegedy et al., 2013; Madry et al., 2017), and shows that robust overfitting can be observed on multiple datasets. From the theoretical side, Madry et al. (2017) proposes the notion of robust test error to measure the performance of model under adversarial attacks, and the required sample complexity is studied in various settings (Schmidt et al., 2018: 8; Bhagoji et al., 2019; Dan et al., 2020; Bhattacharjee et al., 2021). this paper, mainly focus this robust generalization gap and provide theoretical understanding from the perspective of expressive power.
Robust interpolation. Bubeck et al. (2021) proposes conjecture that paramtterization is nec- essary for smooth interpolation. Then Bubeck and Sellke (2021) establishes a law of robustness for isoperimetric data. Specifically, they prove an ( /
..dp)) (/pp) Lipschitzness lower bound for smooth interpolation, where N, d, and denote the sample size, the inputs' dimension, and the number of parameters, respectively. This result indicates that over-parameteriizaton may necessary for ro- bust learning. Zhang et al. (2022) studies many data needed for robust interpolation. This line

---

of works focuses on the training error and the worst-case robustness (i.e. Lipschitz constant), while we measure robustness via the robust generalization error.
Memorization power of neural networks. Our work is related to another line of works (e.g., Baum, 1988; Yun et al., 2019; Bubeck al., 2020; Zhang al., 2021a; Rajput et al., 2021; Zhang et al., 2021b; Vardi et al., 2021) on the memorization power of neural networks. Among these works, Yun al. (2019) shows that neural network with ((V) parameters can memorize the data set with zero error, where N is the size of the data set. Under an additional separable assumption, Vardi et al. (2021) derives an improved upper bound of (VVN), which is shown to be optimal. In this work, we show that Ó (Nd) parameters is sufficient for achieving low robust training error. This is in contrast with our exponential lower bound for low robust test error.
Function approximation. Our work is related to a line of works on function approximation via neural networks (e.g.. Cybenko, 1989; Hornik, 1991; Lu et al., 2017; Yarotsky, 2017: Hanin, 2019). Yarotsky (2017) is the most related, which shows that the functions in Sobolev spaces can be uni- formly approximated by deep ReLU networks. Also related the studies of using deep ReLU networks to approximate functions supported on low dimensional manifolds (Chui and Mhaskar, 2018: Shaham et al., 2018: Chen et al., 2019). In particular, Chen et al. (2019) proves that any C" function in Hölder spaces be c-approximated by the neural network with size O(c-k/n, where k is the intrinsic dimension of the manifold embedded in F In the robust classification scenario, we can also achieve dimensionality reduction for low-dimensional data.
1.3 Notations
Throughout this paper, we use |1-1Ip P E [1, +oo] to denote the E norm in the vector space RRd For Fd and c. Rd. we can define the distance between and as dx(x,, A) = inf yllp y A). For r > O, Bp( { Rd || Ul1, S rr] is defined the E--ball with radius dvc(F) to denote its VC-dimension. A multilayer
centered æ. For function class F, neural network is function from input a E R.d to output y E IR"", recursively defined as follows:
h1 = a (W1 + b1), W1 E Rmixdd bj E R
h (W + bb).
W2 E R.mexm-) by RT ,2 L
y = Wrhh + br, Wr E Rmxmr by E ER"
where a is the activation function and L the depth of the neural network. In this paper, we mainly focus on ReLU networks i.e. (xx max(0, x). The size of neural network is defined as its number of weights/parameters i.e. the number of its non-zero connections between layers.
2 Mild Over-parameterizee ReLU Nets Achieve Zero Robust Training Error
With access to only finite amount of data, common practice for learning robust classifier is to minimize the robust training error(defined below). In this section, we show that neural networks with reasonable size achieve zero robust training error finite training set.
Definition 2.1 (Robust training error). Given a data set D = ((x, Ve) Bi)hsssn Yi E {f-,++1) and an adversarial perturbation radius 5 2 O, the robust training error of a classifier f is defined as Cp (f) A Σn' 13'x E (x,;; ; 6), sgn(f(x') + y:).
When 8 0, the definition coincides with the standard training error. In this paper, we mainly focus on the case p = 2 and p = 00, but our results can be extended to general p as well.
The following is our main result in this section, which states that for binary classification problems, neural network with (NNe) weights perfectly achieve robust classification data set of size N. The detailed proof is deferred to Appendix B.3.
Theorem 2.2. Suppose that D C (0,11) with p E +o0+ consists of N data, and the two classes in D are 2e-separated (cf. Definition 1.1), where (0, 1) is constant. Let robustness radius 8 < He, then there exists classifier I represented by a ReLU network with most
O (Ndlog (8-'d) +N+ - (N\)

---

parameters, such that L (f) 0.
Theorem 2.2 implies that neural networks is quite efficient for robust classification of finite training data. We also derive a lower bound in the same setting, which is stated below. It is an interesting future direction study whether this lower bound can be achieved.
Theorem 2.3. Let p E {2, } and Fn be the set of functions represented by ReLU networks with at most n. parameters. For arbitrury 2e-separated data set under lg norm, if there exists a classifier f E Fn such that L (f) 0, then it must hold that n. = S2(NNd).
The detailed proof of Theorem 2.3 is in Appendix B.4, We leave it as a future direction to study whether this lower bound can be attained. While optimal (non-robust) memorization of N data points only needs constant width (Vardi et al., 2021), our construction Theorem 2.2 has width O(Nd). Therefore, if our upper bound is tight, then Theorem 2.2 can probably explain why increas- ing the network width can benefit robust training (Madry et al., 2017).
3 Hardness of Robust Generalization A Warm-up
In the previous section, we give an upper bound on the size of ReLU networks to robustly classify finite training data. However, it says nothing about generalization, the robust test error, which is arguably a crucial aspect of evaluating the performance this section first consider the same setting as Section 2 where we only assume the data to be well-separated. We show that in this setting, even achieving high standard test accuracy requires exponentially large neural networks in the worst case, which is quite different from empirical obser- vations. This motivates to consider data with additional structures in subsequent sections.
a trained model. As a warm-up, in
Definition 3.1 (Robust test error). Given a probability measure P on IRd {-1,+1} and a robust radius 8 2 O, the robust test error of a classifier J : Rd + R w.r.t P and 6 under En norm is defined as CPp (f) (m)))
[max| x= =1, (f + y
In contrast with the training set which only consists of finite data points, when studying generaliza- tion, we must consider potentially infinite points in the classes that we need to classify. As a result, we consider two disjoint sets A, B E [0, 1]". where points in A have label +1 and points in B have label -. We are interested in the following questions:
Does there exists robust classifier of A and B?
If so, can we derive upper and lower bounds on the size of a neural network to robustly classify A and B??
turns out that, similar to the previous section, the e-separated condition (cf. Definition 1.1) ensures the existence of such classifier. Moreover, be realized by a Lipschitz function. This fact has been observed in Yang et al. (2020), and we provide a different version of their result below for completeness.
Proposition 3.2. For 2c-separated A, c [0, under lp norm with p E (2, +00). the clas- sifier (x) == 4.(a.B)-dull d,(w.A)
d,(m,,A)d,, (m, 6 - Liischhii continuous, and satisfies CP (f*) 0 for any probability distribution P on AUA B.
Based on this observation, Yang et al. (2020) concludes that adversarial training is not inherently hard. Rather, they argue that current pessimistic results on robust test error is due to the limits of existing algorithms. However, it remains unclear whether the Lipschitz function constructed in Proposition 3.2 can actually be efficiently approximated by neural networks. The following theorem shows that ReLU networks with exponential size is sufficient for as robust classification.
Theorem 3.3. For any two 2c-separated B, C [0, 1]d under & norm with {2, to0), distribu- tion P on the supporting set S = A U B and robust radius E (0. 1), there exists a ReLU network f with at most O (((1 c)e) parameters, such that CP (f) =
The detailed proof is deferred to Appendix C.I. Indeed, it is well known that without additional assumptions, an exponentially large number of parameters is also necessary for approximating a Lipschitz function Vore et al., 1989; Shen et al., 2022). This result motivates us consider the
5

---

second question listed above. The following result implies that even without requiring robustness, neural networks need to be exponentially large correctly classify A and B:
Theorem 3.4. Let Fn be the set of functions represented by ReLU networks with most param- elers. Suppose that for any 2e-separated sets A, B C [0, 10 under lp norm with E {2, +o0 there exists J E Fu. that can classify A, B with zero (standard) test error, then must hold that = S (2c) $ (dlog (1/2c))
Theorem 3.4 implies that mere separability of data sets is insufficient to guarantee that they can be classified by ReLU networks, unless the network size is exponentially large. The detailed proof is in Appendix C.2.
However, one should be careful when interpreting the conclusion of Theorem 3.4, since wealdworld data sets may possess additional structural properties. Theorem 3.4 does not take these properties into consideration, so it does not rule out the possibilityy that these additional properties make robust classification possible. Specifically, the joint distribution of data can be decomposed as
P(X,))= P(Y X P(X).
labeling mapping
input
where P(X,Y): P(Y
X). and P(X) denote the joint, conditional and marginal distributions, respectively. In subsequent sections, we consider two well-known properties of data sets that corre- spond to the labeling mapping structure (Section 4) and the input structure (Section 5), respectively, and study whether they can bring improvement to neural networks' efficiency for robust classifica- tion.
4 Robust Generalization for Linear Separable Data
We have seen that for separated data, if no other structural properties are taken into consideration, even standard generalization requires exponentially large neural networks. However, in practice it is often possible to train neural networks that can achieve fairly high standard test accuracy, indicating gap between the setting of Section 3 and practice.
This motivates us consider the following question: assuming that there exists a simple classifier that achieves zero standard test error on the data, is it guaranteed that neural networks with reason- able size can also achieve high robust test accuracy?
We give a negative answer to this question. Namely, we show that even in the arguably simplest set- ting where the given data linear separable and well-separated (cf. Definition 1.1), ReLU networks still need to be exponentially large to achieve high robust test accuracy.
4.1 Main results under the linear separable assumption
Clearly, the robust test error (ef. Definition 3.1) depends the underlying distribution P. We consider a class of data distributions which have bounded density ratio with the uniform distribution: Definition 4.1 (Balanced distribution). Let S R. such that there exists a uniform probability measure ma on S. A distribution P on S is called p-balanced if
P(E) (mo())
E is Lebesgue measurable and mo (E) > >0
inf
Remark 4.2. Definition 4.1 has also appeared in (Shafahi et al., 2018, Theorem 1), which gives an impossibility result robust classification, albeit in completely different setting. Intuitively, it rules out the possibility that data points certain regions are heavily represeepeessnted.
The following theorem is the main result of this paper, and the proof sketch is deferred to Section 4.3. Theorem 4.3. Let 6 E 10,1) be a small constant, p E {2, +o0 and F., be the set of func- tions represented by ReLU networks with most n parameters. There exists sequence Na Ω -=11 "'), 2 1 and universal constant C₁ > 0 such that the following holds: for any E (0. 1), there exists two linear separable sets A, B C [0, 1]d that are 26-separated under Ep norm,

---

such that for any po-balanced distribution P on the supporting set S = AUB B and robust radius ce we have
inf [CP $ 2 Cipo-
Theorem 4.3 states that the robust test error is lower-bounded by a positive constant a Po unless the ReLUU network has size larger than exp(S(d))) On the contrary, if we do not require robustness, then the data can be classified by a simple linear function. Moreover, this classifier can be learned with poly-time efficient algorithm (The detailed proof is in Appendix D.2):
Theorem 4.4. For any two linear-separable A, B C. [0, distribution P on the supporting set S AU B, ò and 3 > let H be the family of d-dimensional hyperplane classifiers. Then, there exists a poly-time efficient algorithm A 2 + H. for N = (2d/3²) training instances independently randomly sampled from P. with probability algorithm A learn a classifier f E F such that
over samples, we can use the
Cp(f) S.
where Cp(f) := P(( + f())} denotes the standard test ervor.
The practical implication of Theorem 4.3 is two-fold. First, by comparing with Theorem 4.4, one can conclude that robust classification may require exponentially more parameters than the non- robust case, which is consistent with the common practice that larger models are used for adversarial robust training. Second, together with our upper bound in Theorem 2.2, Theorem 4.3 implies an exponential separation of neural network size for achieving high robust training and test accuracy.
4.2 Exponential lower bound for more general models
In general, our lower bounds hold true for variety of neural network families and other function classes as well, as long as their VC dimension is at most polynomial in the number of parameters, which is formally stated Theorem 4.5 that can be derived by the proof of Theorem 4.3 directly.
Theorem 4.5. Let (0, 1) be small constant, p E {2, and Gn be the family of parameter- ized models with at most n. parameters, satisfying the VC-dimension of function family VC-dim is most (nly(n). Then, there exists a sequence Na (exp(S(d))) d 2 1 and a universal constant Ci > such that the following holds: for any c E (0,1), there exists two linear separable sets A, B C [0, 1]s that are 2e-separated under Ep norm, such that for any no Ho-balanced distribution P on the supporting set S A U B and robust radius ce we have
inf (CP (g) :9 E &NN. 2 C/P0--
In other words, the robust generalization error cannot be lower that constant Cipo unless the model, satisfying the property of their VC dimension polynomially bounded by the number of parameters, has exponential larger size. Indeed, this property satisfied for e-g. feedforward neural networks with sigmoid (Karpinski and Macintyre, 1995) and piecewise polynomial (Bartlett et al., 2019) activation functions. Therefore, our results reveal that the hardness of robust generalization may stem from the expressive power of generally practical models.
4.3 Proof sketch of Theorem 4.3
In this subsection, we present proof sketch for Theorem 4.3 in the Exo norm case. We only consider P to be the uniform distribution, extending to μo balanced distributions is not difficult, The case of fz-norm is similar and can be found in the Appendix.
Proof Sketch. Let K = [ and Φ {1,2, ... Kjd-1 + [-1,+1) be an arbitrary mapping, 1 S é1, 22, i S K
we define Sg {
f2 Sa-1 K. K.K...
K 2 + 0(1 b2, ... (d-1)) 1,,,,,,,,111))
where co is arbitrarily small constant. The hyperplane (d)) partitions Sp into two sub- sets, which we denote by Ag and BB. It is not difficult to check that Ag and B& satisfies all the required conditions.
Our goal is to show that there exists some choice of & such that robust classification hard. To begin with, suppose that robust classification with accuracy 1 can be achieved with at most M
7

---

...0.0
.0.
Figure 1: example of our construction for d = We choose A, B the set of blue points and red points, respectively.
parameters for all Φ, then these networks all be embedded into enveloping network Fo of size ((M)).
i 82. id- - k}. Robustness implies that for all possible label assignment to S, at least (1 - a points can be correctly classified by Fa-
Define 5 2 1-- -x :)
0 i.c. perfect classification is required, then we can see that the VC-dim(Fe) 2 Kdd1 which implies that its size must be exponential, by applying classical VC-dimension upper bounds of neural networks (Bartlett et al., 2019).
When a > 0, we cannot directly use the bound on VC-dimension. Instead, we use a double-counting argument to lower-bound the growth function of some subset of 5.
Let V _ Each choice of & corresponds to (1-a)/" labelled V-subset of 5 that are correctly classified. There are total of 2 choices of Φ, while each labelled V-subset can be obtained by at most -V different Φb. As a result, the total number of labelled V-subset correctly classified by Fg is at least 2 (1
On the other hand, the total number of V-subset of S is (Krt ') thus there must exists a V-subset Vo C S. such that at least
[ (Kd-)) (KV
2 (1 )
(2((1) Kd-1
(2((1 (111-))----
Kddz
different labellings of Vn are correctly classified by Fø. where C. = /2111 2a) > for a = 0.1. Since (1) provides lower bound for the growth function, together with the upper bound of growth
function in terms VC-dimension, we can deduce that VC-dim Fo) 2 0.05kd-1 Finally, the conclusion follows by applying the VC-dimension bounds in Bartlett al. (2019).
O
Remark 4.6. The connection between VC dimension and approximation error has been explored in a number of previous works (Yarotsky, 2017; Shen et al., 2022) to provide lower bounds on the network size for approximating given function class. Here we consider the problem of robust clas- sification which is of more practical interest then function approximation, and our main technical contribution is exponential lower bound the VC dimension. Our proof formalizes the folklore that adversarial training hard since it requires a more complicated decision boundary. We note that similar ideas have been used show benefits of depth neural networks (Telgarsky, 2016; Liang and Srikant, 2017) but their techniques are restricted to one-dimensional functions.
5 Robust Generalization for Low-Dimennsoona--anioll Data
In this section, we focus on refined structure of data's input distribution P(X). A common belief of real-life data such as images is that the data points lie on a low-dimensional manifold. It pro- motes series of methods that are invented to make the dimensionality reduction, including linear dimensionality reduction (e.g., PCA (Pearson, 1901)) and non-linear dimensionality reduction (e.g.. t-SNE (Hinton and van der Maaten, 2008)). Several works have also empirically verified the belief. Roweis and Saul (2000) and Tenenbaum et al. (2000) have demonstrated that image, speech and other variant form data can be modeled nearly on low-dimensional manifolds. In particular, Wang et al. (2016) studies auto-encoder based dimensionality reduction, and shows that the 28 28 784 dimensional image from MNIST can reduced to nearly 10 dimensional representations, which corresponds to the intrinsic dimension of the handwritten digital dataset.

---

Motivated by these findings, in this section, we assume that data lies on a low-dimensional manifold M embedded in [0, 1] i.. supp(X) EMC C [o, 1| We will show improved upper bound that is exponential in the intrinsic & of the manifold M instead of the ambient data dimension d for the size of networks achieving zero robust test error, which implies the efficiency of robust classification under the low-dimensional manifold assumption. Also, we point out that the exponential dependence of & not improvable by establishing a matching lower bound.
5.1 Preliminaries
Let M be & di-iennsional compact Riemannian manifold embedded in R where ls is the intrinsic dimension (k < d).
Definition 5.1 (Chart, atlas and smooth manifold), A chart for M is a pair (U, o) such that U F.C. M is open and Φ U + R., where homeomorphism; An atlas for M is a collec- tion {(Va, @all of pairwise C compatible charts such that Une Ua = M; And we call M a smooth manifold if and only if M has a C atlas.
Definition 5.2 (Partition of unity). C partition of unity on a manifold M is a collection of non-negative C functions Pa :M - R. a E A that satisfy (1) the collection of supports, (supp (a is locally finite; and (2) ELEA Pa =.
Definition 5.3 .olyy-Patitionabble.. We call that M is poly-partitionable if and only for a langent- space-induced atlas {(U Ta)baeA of M, there exists particular partition of unity {Pa JaEA that satisfies Pa o T- is a simple piecewise polynomial in R2 where simple piecewise polynomial is defined as the composite mapping between a polynomial and size-bounded ReLU network.
The concept, oolyypartitionable, defines a class of manifolds that have simple partition of unity, which is a generalization of some structures in the standard Euclidean space Rdd For example, an explicit construction for oowddimesioona manifold [0, 1] is {pm (2)} in Yarotsky (2017), where the coordinate system identity mapping.
5.2 Main results under the low-dimensional manifold assumption
Before giving our main results, we first extend robust classification to the version of manifold. Definition 5,4 (Robust classification on manifold). Given a probability measure P on M x {-1,+1) and a robust radius the robust test error of a classifier f . w.r. and under En norm is defined as CP.6 ( = E( EM.le'
[ssg((( v}}.
Now, we present our main result in this section, which establishes an improved upper bound for size that is mainly exponential in the intrinsic dimension & instead of the ambient data dimension d.
Theorem 5.5. Let M 1]d be k dimensional compact partitioabbee Riemannian ifold with the condition number т > 0. For any two 2 separated A, B C M under foo norm, distribution P the supporting 5 A and robust radius E (0, 1), there exists ReLU network f with at most
((1-))//V2) -R>
parameters, such that ( = O, where k O (k log d) is almost linear with respect to the intrinsic dimension k, only up to a logarithmic factor.
Proof sketch. The proof idea of Theorem 5.5 has two steps. First, we construct a Lipschitz robust classifier f in Proposition 3.2. Then, we regard f as the target function and use ReLU network If to approximate it on the manifold M. The following lemma is the key technique that shows we can approximate Lipschitz functions on a manifold by using ReLU networks efficiently.
Lemma 5.6. Let M C [0, 1]at be a k dimiennsio compact poly oolypaartitionable Riemannian mani- fold with the condition number >> O. For any small 5 > O and T. T.--ipschitzzfuncee function M - TR, there exists a function ğ implemented by ReLU network with at most Ô ((v (aL/)-885 parameters, such that lg < 8 for any M, where l is the same Theorem 5.5.

---

By applying the conclusion of Lemma 5.6, we can approximate the 1/c-Lipschitz function f in Proposition 3.2 via ReLU network f with at most Ö (exp(k)) parameters, such that the uniform approximation error |l. f (M)) at most 1 c.
Next, we prove the theorem by contradiction, Assume that there exists some perturbed input xf that is mis-classified and the original input x is in A. So we know f(x') < 0 and (x) < c'. This
impiles doo (1', A) doc (a', B)
doo (x', A). Combined with dxo A) do (x', B) > L+e I-
doo (A, 2 2e, have dao (x' A)
E')E ce, which is contradiction.
Remark 5.7. Chen al. (2019) studies network-based approximation on smooth manifolds, and also establishes an O(8-k) bound for the network's 's size. However, different from their setting where the approximation error 6 goes to zero, it is reusonable that the separated distance e and robust radius e are constants in our setting. If we simply follow their proofs, we can only obtain the bound (((8/CM))* where CM also grows exponentially with respect to k; which further implies that the final result will be roughly exp(O(1²)). This bound is too loose, especially when k: = vd. To this end, propose novel approximation framework so to improve the bound to exp(O(k)), which is presented as Lemmn 5.6. And the detailed proof of Lemma 5.6 is deferred to Appendix E.I.
Although we have shown that robust classification will be more efficient when data lies on low- dimensional manifold. there is also a curse of dimensionality, i.c., the upper bound for the network's 's size is almost exponential in the intrinsic dimension k. The following result shows that the curse of dimension is also inevitable under the low-dimensional manifold assumption.
Theorem 5.8. Let c E (0, be a small constant. There exists a sequence {Ne)x21 that satisfies and a universal constant C1 > O such that the following holds: let M C [0, be a complete and compact k-dimensional Riemannian manifold with non-negative Ricci curvature, then there exists two 2e-separated sets A, B M under too norm, such that for any - balanced distribution P on the supporting set S = AU AUDA B and robust radius E (0, 1). we (f)=
N& = -2 ((20/
have inf (Lp.ee (f): f FN.3 Cipo-
In other words, the robust test error is lower-bounded by a positive constant a = C No unless the neural network has size larger than exp()((k))) The detailed proof of Theorem 5.8 is presented in Appendix E.4.
6 Conclusion
This paper provides new theoretical understanding of the gap between the robust training and generalization error. We show that the ReLU networks with reasonable size can robustly classify the finite training data. On the contrary, even with the linear separable and well-separated assumptions, ReLU networks must be exponentially large to achieve low robust generalization error. Finally, consider the scenario where the data lies the low dimensional manifold and prove that the ReI.U network, with a size exponentially in the intrinsic dimension instead of the inputs' dimension, sufficient for obtaining low robust generalization error. We believe our work opens up many interesting directions for future work, such as the tight bounds for the robust classification problem, or the reasonable assumptions that permit the polynomial-size ReLU networks achieve low robust generalization error.
Acknowledgement
We thank all the anonymous reviewers for their constructive comments. This work supported by National Science Foundation of China (NSFC62276005)) The Major Key Project of PCL (PCL2021A) 12), Exploratory Research Project of Zhejiang Lab (No. 2022RC0AN02), and Project 2020BD006 supported by PKUBaidu Fund. Binghui Li is partially supported by National Innova- tion Training Program of China. Jikai Jin partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University.
10

---

References
Anthony, M., Bartlett, P. L., Bartlett, L. et al. (1999). Neural network learning: Theoretical foun- dations, vol. 9, cambridge university press Cambridge.
Baraniuk, R. G. and Wakin, M. B. (2009). Random projections of smooth manifolds. Foundations of computational mathematics, 9 51-77.
Bartlett, P. L., Harvey, N., Liaw, C. and Mehrabian, A. (2019). Nearly-tight vc-dimension and pseu- dodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20 2285-2301.
Baum, E. B. (1988). On the capabilities of multilayer perceptrons. Journal of complexity, 4 1933 215.
Belkin, M., Hsu, D., Ma, S. and Mandal, S. (2019). Reconciling modern machine-learning practice and the classical bias- trade-off. Proceedings of the National Academy of Sciences, 116 15849-15854.
Bhagoji, A. N., Cullina, D. and Mittal, P. (2019). Lower bounds on adversarial robustness from optimal transport. Advances in Neural Information Processing Systems, 32.
Bhattacharjee, R., Jha, S. and Chaudhuri, K. (2021). Sample complexity of robust linear classifica- tion on separated data. In International Conference on Machine Learning. PMLR.
Biggio, B., Corona, Maiorca, D., Nelson, B., Šrndié, N., Laskov, P., Giacinto, G. and Roli, F. (2013). Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery databases. Springer.
Bishop, L. (1964). A relation between volume, mean curvature and diameter. In Euclidean Quantum Graviry. World Scientific, 161-161.
Boser, B. E., Guyon, I. M. and Vapnik, N. (1992). A training algorithm for optimal margin clas- sifiers. Proceedings of the fifth annual workshop on Computational learning theory.
Bubeck, S., Eldan, R., Lee, Y. T. and Mikulincer, D. (2020). Network size and weights size for memorization with two-layers neural networks. arXiv preprint arXiv:2006.0288
Bubeck, S., Li, Y. and Nagaraj, D. M. (2021). A law of robustness for two-layers neural networks. In Conference on Learning Theory. PMLR.
Bubeck, S. and Sellke, M. (2021). A universal law of robustness via isoperimetry. Advances in Neural Information Processing Systems, 34.
Chen, M., Jiang, H., Liao, W. and Zhao. T. (2019). Efficient approximation of deep relu networks for functions on low dimensional manifolds. Advances in neural information processing systems, 32.
Chui, C. K. and Mhaskar, (2018). Deep nets for local manifold learning. Frontiers Applied Mathematics and Statistics, 4 12.
Cohen, J., Rosenfeld, E. and Kolter, Z. (2019). Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning. PMLR.
Cybenko, G. (1989). Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2 303-314.
Dan, C., Wei, Y. and Ravikumar, (2020). Sharp statistical guaratees for adversarially robust gaus- sian classification. In International Conference on Machine Learning. PMLR.
Devlin, J., Chang, M.-W., Lee, K. and Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04480 088..0000..0....
De Vore, R. A., Howard, and Micchelli, C. (1989).
Optimal nonlinear approximation.
Manuscripta mathematica, 63 469-

---

Dohmatob, E. (2019). Generalized no free lunch theorem for adversarial robustness. In International Conference on Machine Learning. PMLR.
Gao, R., Cai, T., Li, H., Wang, L., Hsieh, C. J. and Lee, J. D. (2019). Convergence of adversarial training in overparametrized neural networks. Advances in Neural Information Processing Sys- tems, 32.
Gong, S., Boddeti, V. N. and Jain, A. K. (2019). On the intrinsic dimensionality of image representa- tions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattenn Recognition.
Goodfellow, J., Shlens, J. and Szegedy, C. (2014). Explaining and harnessing adversarial exam- ples. arXiv preprint arXiv:1412.6572.
Hanin, B. (2019). Universal function approximation by deep neural nets with bounded width and relu activations. Mathematics, 992.
Hassani, H. and Javanmard, A. (2022). The curse of overparametrization in adversarial train- ing: Precise analysis of robust generalization for random features regression. arXiv preprint arXiv:2201.05149
Hinton, and van der Maaten, L. (2008). Visualizing data using t-sne journal of machine learning research.
Hornik, K. (1991). Approximation capabilities of multilayer feedforward networks. Neural net- works, 4 251-257.
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A. et al. (2021). Highly accurate protein structure prediction with alphafold. Nature, 596 583-589.
Karpinski, M. and Macintyre, A. (1995). Polynomial bounds for dimension of sigmoidal neural networks. Proceedings of the (wenty-seventh annual ACM symposium on Theory of computing.
Liang, S. and Srikant, R. (2017). Why deep neural networks for function approximation? In 5th International Conference on Learning Representations, ICLR 2017.
Lu, Z., Pu, H., Wang, F., Hu, Z. and Wang, L. (2017). The expressive power of neural networks: A view from the width. Advances in neural information processing systems, 30.
Madry, A., Makelov, A., Schmidt, L., Tsipras, D. and Vladu, A. (2017). Towards deep learning models resistant adversarial attacks. arXiv preprint 1iXiv:1706.0608.
Mohri, M., Rostamizadeh, A. and Talwalkar, A. (2018). Foundations of machine learning. MIT press.
Nakkiran, P. (2019). arXiv:1901.00532.
Adversarial robustness may be at odds with simplicity. arXiv preprint
Niyogi, P., Smale. S. and Weinberger, (2008). Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 39 441.
Pearson, K. (1901). Liii. on lines and planes of closest fit systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2 559-572.
Raghunathan, A., Xie, S. M., Yang, F., Duchi, J. C. and Liang, P. (2019). Adversarial training can hurt generalization. arXiv preprint 1906.00:906000000
Rajput, S., Sreenivasan, K.. Papailiopoulos, D. and Karbasi, A. (2021). An exponential improve- ment on the memorization capacity of deep threshold networks. Advances in Neural Information Processing Systems. 34.
Rice, I.., Wong, F. and Kolter, (2020). Overfitting adversarially robust deep learning. Inter- national Conference Machine Learning. PMLR.
12

---

Roweis, S. T. and Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embed- ding. science, 290 2323-2326.
Schmidt, L., Santurkar, S.. Tsipras, D., Talwar, K. and Madry, A. (2018). Adversarially robust gen- eralization requires more data. Advances in neural information processing systems, 31.
Shafahi, A., Huang, W. R., Studer, C., Feizi, S. and Goldstein, T. (2018). Are adversarial examples inevitable? arXiv preprint arXiv: 000188899004444
Shafahi, A., Najbb,, M., Ghiasi, M. A., Xu, Z., Dickerson, J., Studer, C., Davis, L. S., Taylor, G. and
Goldstein, T. (2019). Adversarial training for free! Advances in Neural Information Processing Systems, 32.
Shaham, U., Cloninger, A. and Coifman, R. R. (2018). Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis, 44 537-557.
Shen, Z., Yang, H. and Zhang, S. (2022). Optimal approximation rate of relu networks in terms of width and depth. Journal Mathématiques Pures el Appliquées, 157 101-135.
Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. and Fergus, R. (2013). Intriguing properties neural networks. arXiv preprint arXiv: 1312.619.
Telgarsky, M. (2016). Benefits of depth in neural networks. In Conference on learning theory. PMLR.
Telgarsky, M. (2017). Neural networks and rational functions. In International Conference on Machine Learning. PMLR.
Tenenbaum, J. B., Silva, V. and Langford, J. C. (2000). A global geometric framework for non- linear dimensionality reduction. science, 290 2319-2323.
Tramèr, F., Kurakin, A., Papernot, N., Goodfellow, I., Boneh, D. and McDaniel, P. (2018). Ensem- ble adversarial training: Attacks and defenses. In International Conference Learning Repre- sentations.
Tsipras, D., Santurkar, S., Engstrom, L., Turner, A. and Madry, A. (2019). Robustness may be at odds with accuracy. International Conference on Learning Representations. 2019.
Vardi, G., Yehudai, G. and Shamir, O. (2021). On the optimal memorization power of relu neural networks. arXiv preprint a7X0022110.03187.
Voulodimos, A., Doulamis, N., Doulamis, A. and Protopapadakis, E. (2018). Deep learning for com- puter vision: A brief review. Computational intelligence and neuroscience, 2018
Wang, Y., Yao, H. and Zhao, S. (2016). Auto-encoder based dimensionality reduction. Neurocom- puting, 184 232-242.
Yang, Y.-Y,, Rashtchian, C., Zhang, H., Salakhutdinov, R. R. and Chaudhuri, K. (2020). closer look accuracy vs. robustness. Advances in neural information processing systems, 33 8588- 8601.
Yarotsky, D. (2017). Error bounds for approximations with deep relu networks. Neural Networks, 94 103-114.
Yun, C., Sra, S. and Jadbabaic, A. (2019). Small relu networks powerful memorizers: tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 32.
Zhang, B., Cai, T., Lu, Z., He, D. and Wang. L. (2021a). Towards certifying l-infinity robustness using neural networks with l-inf-dist neurons. In International Conference on Machine Learning. PMLR.
Zhang, C., Bengio, S., Hardt, M., Recht, and Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. iclr. arXiv preprint arXiv:1611.03530.
13

---

Zhang, H., Wu, Y. and Huang, H. (2022). How many data are needed for robust learning? arXiv preprint arX1v:2202.1199.
Zhang, H., Yu, Y. Jiao, J., Xing, E., El Ghaoui, L. and Jordan, M. (2019). Theoretically principled trade-off between robustness and accuracy. In International conference machine learning. PMLR.
Zhang. J., Zhang, Y., Hong, M., Sun, R. and Luo, Z.-Q. (2021b). When expressivity meets trainabil- ity: Fewer than neurons work. Advances in Neural Information Processing Systems, 34 9167-9180.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Explain:
our work is seeking develop a theoretical understanding of the robust generalization in deep learning.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l re using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "HLtwdrKLdeL", "reviewer": "Reviewer_diHV", "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.", "questions": "In Def. 3.1, I assume you meant $\\mathrm{sgn}(f(x')) \\neq y$ instead of $f(x') \\neq y$?\n", "limitations": "This paper is theoretical in nature, hence it should not have any potential adverse social impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\nHowever, 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). ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5DtVI1Zy7Jf", "reviewer": "Reviewer_eEJn", "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.", "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", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper provides a novel view about the hardness of training robust models, by investigating approximation ability.\n- The lower bounds on the network size seem to be novel and provide evidences for why training robust models are hard.\n\n\nWeaknesses:\n- 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.\n- 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. \n- The depth of FNNs seems not to be important in their bounds.\n\nMinor: family F_{N_d} in Theorem 4.3 is not defined explicitly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-coAV1gzU4", "reviewer": "Reviewer_pcp1", "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. \n\nThe paper is well-written, the theoretical results are sound, interesting, and relevant. I vote for acceptance.", "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.\n- 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? \n- 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.  \n\n[1] Petzka, Henning, et al. \"Relative flatness and generalization.\" Advances in Neural Information Processing Systems 34 (2021): 18420-18432.\n", "limitations": "The theoretical results are not empirically verified.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- strong theoretical results\n- relevant analysis\n\nWeakness:\n- no empirical validation of the theoretical results", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept