A Universal Law of Robustness via Isoperimetry
Authors: Sebastien Bubeck
Mark Sellke
Venue: NeurIPS 2021 Oral (2021)
Keywords: adversarial robustness
over-parametrization
isoperimetry

Abstract: Classically, data interpolation with a parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satisfied. A puzzling phenomenon in the current practice of deep learning is that models are trained with many more parameters than what this classical theory would suggest. We propose a theoretical explanation for this phenomenon. We prove that for a broad class of data distributions and model classes, overparametrization is {\em necessary} if one wants to interpolate the data {\em smoothly}. Namely we show that {\em smooth} interpolation requires $d$ times more parameters than mere interpolation, where $d$ is the ambient data dimension. We prove this universal law of robustness for any smoothly parametrized function class with polynomial size weights, and any covariate distribution verifying isoperimetry. In the case of two-layers neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj. We also give an interpretation of our result as an improved generalization bound for model classes consisting of smooth functions.

A Universal Law of Robustness via Isoperimetry
Sébastien Bubeck
Mark Sellke Stanford University
Microsoft Research sebubeckkmiccoosof..com
msel edu
Abstract
Classically, data interpolation with parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satis- fied. A puzzling phenomenon in deep learning is that models are trained with many more parameters than what this classical theory would suggest. We propose theoretical explanation for this phenomenon. We prove that for broad class of data distributions and model classes, overparametrization is necessary if one wants interpolate the data smoothly, Namely we show that smooth interpolation requires d times more parameters than mere interpolation, where d is the ambi- ent data dimension. We prove this universal law of robustness for any smoothly parametrized function class with polynomial size weights, and any covariate dis- tribution verifying isoperimetry (or a mixture thereof). In the case of two-layer neural networks and Gaussian covariates, this law was conjectured in prior work by Bubeck, Li and Nagaraj. We also give an interpretation of our result as an improved generalization bound for model classes consisting of smooth functions.
Introduction
Solving n equations generically requires only unknowns'. However, the revolutionary deep learn- ing methodology revolves around highly overparametrized models, with many more than n parame- ters to learn from n training data points. We propose an explanation for this enigmatic phenomenon, showing in great generality that finding a smooth function to d-dimensional data requires least nd parameters. In other words, overparametrization by factor of d is necessary for smooth inter- polation, suggesting that perhaps the large size of the models used in deep learning is a necessity rather than a weakness of the framework. Another way to phrase the result is as a tradeoff between the size of a model (as measured by the number of parameters) and "robustness" (as measured by its Lipschitz constant): either one has small model (with n parameters) which must then be non-robust, or one has robust model (constant Lipschitz) but then it must very large (with nd parameters). Such tradeoff was conjectured for the specific case of two-layer neural networks and Gaussian data [BLN21]. Our result shows that in fact it is universal phenomenon, which applies to essentially any parametrized function class (including in particular deep neural networks) as well as a much broader class of data distributions. As in [BLN21] we obtain an entire tradeoff curve between size and robustness: smoothly parametrized by parameters, and for any d-dimensional dataset satisfying mild regularity conditions, any function in this class that fits the data below the noise level must have its (Euclidean)
universal law of robustness states that, for any function class
Lipschitz constant larger than nd
Theorem 1 (Informal version of Theorem 3). Let F be class of functions from Rd R and let (I,, 81 p be i..dd input-output pairs in Rd x [-1, Assume that:
1. F admits a Lipschitz parametrization by p real parameters, each of size at most poly(n, m, d).
As in, for instance, the inverse function thcorem in analysis or Bézout's theorem algebraic geometry. See also [YSJ19, BELM20] for versions of this claim with neural networks.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

2. The distribution of the covariates z4 satisfies isoperimetry (or is mixture theoreof).
3. The expected conditional variance of the ouppu (i.e., the "noise level") is strictly positive, denoted o² == [V aaaarruu ar(y]æ=]] > 0.
Then, with high probability over the sampling of the data, one has simultaneously for all f E F:
nd < p
( so Lip(f) 2 52
Remark 1.1. For the distributions we have in mind, for instance uniform on the unit sphere, there exists with high probability some O11)-Lipschitz function f RR - IR satisfying f(;; y; for for all 1 S Si j n long
all i. Indeed, with probability 1 --- -0(( we have || - zyyl as n S poly(d). In this case we may apply the Kirszbraun extension theorem to find a suitable f
regardless of the labels yi- More explicitly we may fix smooth bump function g : I - R with
g(0) = 1 and g(x) 0 for 2 1, and then interpolate using the sum of radial basis functions
f(0)= -1=>on 9(11= =x:lly--
In fact this construction requires only p n2d + 1) parameters to specify the values (Ii, Mi) kejn) and thus determine the function f. Hence = n + parameters suffice for robust interpolation, iee. Theorem is essentially best possible for = O(1). A similar construction shows the same conclusion for any p E [92()), nd], essentially tracing the entire tradeoff curve. This is because one can first project onto a fixed subspace of dimension d = p/n, and the projected inputs x; (Vá
now have pairwise distances at least Ω on the projected points now requires only = dr parameters and has Lipschitz constant I. =0
(Vá/d) with high probability. The analogous construction
o (alaa) -
nd
1.1 Speculative implication for real data
To put Theorem in context, compare the empirical results presented in [MMS+ 18). In the latter work, they consider the MNIST dataset which consists of n = 6 x 10 images in dimension 28 784. They trained robustly different architectures, and reported architecture versus the obtained robust test accuracy (third plot from the left). One can see a sharp transition from roughly 10% accuracy to roughly 90% accuracy at around x 10 parameters (capacity scale 4 in their notation). Moreover the robust accuracy keeps climbing up with more parameters, to roughly 95% accuracy at roughly 3 x 10th parameters.
Figure 4 the size of the
How can we compare these numbers to the law of robustness? There are number of difficulties that we discuss below, and we emphasize that this discussion highly speculative nature, though we find that, with a few leaps of faith, our universal law of robustness sheds light on the potential parameter regimes of interest for robust deep learning.
The first difficulty is to evaluate the "correct" dimension of the problem. Certainly the number of pixels per image gives an upper bound, however one expects that the data lies on something like a lower dimensional sub-manifold. Optimistically, we hope that Theorem I will continue to apply for an appropriate effective dimension which may be rather smaller than the literal number of pixels. This hope is partially justified by the fact that isoperimetry holds in many mossthann-pccurrest situations, some which are stated the next subsection.
The next difficulty is to estimate/interpret the noise value 0². From theoretical point of view, this noise assumption necessary for otherwise there could exist a smooth classifier with perfect accuracy in F. defeating the point of any lower bound on the size of F. We tentatively would like to think of o² as capturing the contribution of the "difficult" part of the learning problem, that is o² could be thought of as the non-robust generalization error of reasonably good models, so a couple

---

of % of error in the case of MNIST. With that interpretation. one gets "below the noise level" in MNIST with a training enror of couple of %. We believe that versions of the law of robustness might hold without noise; these would need to go beyond representational power and consider the dynamies of learning algorithms.
Finally another subtlety to interpret the empirical results of [MMS+ 18] is that there is mismatch between what they measure and our quantities of interest. Namely the law of robustness talks about two things: the training enror, and the worst-case robustness (i.e., the Lipschitz constant). On the other hand [MMS* 18] measures the robust generalization error. Understanding the interplay between those three quantities is a fantastic open problem. Here we take the perspective that small robust generalization error should imply small training error and a small Lipschitz constant. Another important mismatch is that we stated our universal law of robustness for Lipschitzness in lg. while the experiments in [MMS+ 18] are for robustness in Lo.. We believe that a variant of the law of robustness remains true for loo belief again partially justified by how broad isoperimetry is (see next subsection).
With all the caveats described above, experiments, smooth models with accuracy below the noise level are attained with a number of parameters somewhere in the range 2 10y 3 x 10th parameters (possibly even larger depending the interpretation of the noise level), while the law of robustness would predict any such model must have at least nd parameters, and this latter quantity should be somewhere in the range 10 107 (corresponding to an effective dimension between 15 and 150). While far from perfect, the law of robustness prediction is far more accurate than the classical rule of thumb parameters # equations (which here would predict a number of parameters of the order 10").
now look at the numbers as follows: in the [MMS+ 18]
Perhaps more interestingly, one could apply a similar reasoning to the ImageNet dataset, which consists of 1.4 x 10 images of size roughly 2 x 10 Estimating that the effective dimension is a couple of order of magnitudes smaller than this size, the law of robustness predicts that to obtain good robust models on ImageNet one would need at least 10 - 10 parameters. This number is larger than the size of current neural networks trained robustly for this task, which sports between 10 - 10" parameters. Thus, we arrive at the tantalizing possibility that robust models for ImageNet do not exist yet simply because we couple orders of magnitude off in the current scale of neural networks trained for this task.
1.2 Related work
Theorem I is a direct follow-up to the conjectured law of robustness in [BLN2I] for (arbitrarily weighted) two-layer neural networks with Gaussian data. Our result does not actually prove their conjecture, because we assume here polynomially bounded weights. While this assumption is reasonable from a practical perspective, it remains mathematically interesting conjecture for the two-layer case. We prove however in Section A that the polynomial weights as- sumption is necessary as soon as one considers three-layer neural networks. Let us also mention the [GCL+ 19, Theorem 6.1] which showed a lower bound (((d) on the VC dimension of any function class which can robustly interpolate arbitrary labels on all well-separated input sets (æ1,..., Fn,) We also note that relation between high-dimensional phenomenon such as concentration and adversarial examples has been hypothesized before, such as in [GMF+18]
prove the full
In addition to [MMS+18] several recent works have experimentally studied the relationship between a neural network scale and its achieved robustness, see e.g., INBA+18, XY20, 2QJ+ It has been consistently reported that larger networks help tremendously for robustness, beyond what is typically seen for classical non-robust accuracy. We view our universal law of robustness as putting this empirical observation on a more solid footing: scale is actually necessary to achieve robustness.
The law of robustness setting is closely related to the interpolation setting: in the former case one considers models optimizing "beyond the noise level", while in the latter case one studies models with perfect fit on the training data. The study of generalization in this in-
3

---

terpolation regime has been a central focus of learning theory in the last few years (see e.g., [BHMM19, MM19, BLLT20, NKB [0]). as it seemingly contradicts classical theory about regu- larization. More broadly though, generalization remains mysterious phenomon in deep learning, and the exact interplay between the law of robustness' setting (interpolation regime/worrs-case robustness) and (robust) generalization error is fantastic open problem. Interestingly, we note that one could potentially avoid the conclusion of the law of robustness (that is, that large models are necessary for robustness). with early stopping methods that could stop the optimization once the noise level is reached. In fact, this theoretically motivated suggestion has already been empirically tested and confirmed in the recent work [RWK20], showing again close tie between the conclusions one can draw from the law of robustness and actual practical settings.
Classical lower bounds on the gradient of function include Poincaré type inequalities, but they are of a qualitately different nature compared to the law of robustness lower bound. We recall that measure μ Rd satisfies Poincaré inequality if for any function f. one has [=I V ff > C. Var(f) (for some constant C' > 0). In our context, such a lower bound for an interpolating function f has essentially no consequence since the variance f could be exponentially small. In fact this is tight, as one easily use similar constructions to those in [BLN21] to show that one can interpolate with
exponentially small expected norm squared of the gradient (in partieular it is crucial in the law of robustness to consider the Lipschitz constant, i.e., the supremum of the norm of the gradient). On the other hand, our isoperimetry assumption is related of the Poincaré inequality known as log-Sobolev inequality (see e.g., [Led01]). If the covariate measure satisfies only Poincaré inequality, then could prove a weaker law of robustness of the
certain strenghtening
form Lip Z avd (using for example the concentration result obtained in [BL97]). For the case of two-layer neural networks there is another natural notion of smoothness (different from lp norms of the gradient) that can be considered, known the Barron norm. In [BELM20] it is shown that for such a notion of smoothness there is no tradeoff à la the law of robustness, namely one can simultaneously be optimal both in terms of Barron norm and in terms of the network size. More generally, it is an interesting challenge to understand for which notions of smoothness there is a tradeoff with size.
P
1.3 Isoperimetry
Concentration of measure and isoperimetry are perhaps the most ubiquitous features of high- dimensional geometry. In short, they assert in many cases that Lipschitz functions on high- dimensional space concentrate tightly around their mean. Our result assumes that the distribution μ of the covariates z₁ satisfies such an inequality in the following sense.
Definition 1.1. A probability measure μ on Rd satisfies c-isoperimetry if for any bounded L- Lipschitz f Rd + R, and any t 2 0,
P(l(()) - E1AI 2 1) S 2e 20133
d12
(1.1)
In general, if scalar random variable X satisfies P[|]] 2 < 2C- then we say X is C-subgaussian. Hence isoperimetry states that the output of any Lipschitz function is O(1)- subgaussian under suitable rescaling. Distributions satisfying OLL)-isoperimetry include high di- mensional Gaussians μ N' (0, 4t) and uniform distributions spheres and hypercubes (normal- ized to have diameter 1). Isoperimetry also holds for mild perturbations of these idealized scenarios, including?:
The sum of a Gaussian and an independent random vector of small norm [CCNW21]. Strongly log-coneave measures in any normed space [BL00, Proposition 3.1].
Manifolds with positive Ricci curvature [Gro86, Theorem 2.2].
Due to the last condition above, we believe our results are realistic even under the manifold hypoth- esis that high-dimensional data tends to lie a lower-dimensional submanifold. This viewpoint on learning has been studied for decades, see e.g. [HS89, KL93, RS00, TDSL00, NM10, FMN16].
'The first two examples satisfy a logarithmic Sobolev inequality, which implies isoperimetry [Led99, Propo- sition 2.3].

---

We also note that our formal theorem (Theorem 3) actually applies to distributions that can be written as mixture of distributions satisfying isoperimetry. Let also point out that from technical perspective, our proof is not tied to the Fuclidean norm and applies essentially whenever Definition 1.1 holds. The main difficulty in extending the law of robustness to e-g. the earth-mover distance seems to be identifying realistic cases which satisfy isoperimetry.
Our proofs will repeatedly use the following simple fact:
Proposition 1.2. [Ver18, Proposition v.vHI,, Exercise 3.1] If Xi...., ,n are independent, C-subgaussian, with mean O, then 1 >i=1 X4 is 18C-subganssian.
2 A finite approach to the law of robustness
For the function class of two-layer neural networks, [BLN21] investigated several approaches to prove the law of robustness. At high level, the proof strategies there relied on various ways to measure how "large" the of two-layer neural networks can be (specifically, they tried a geometric approach based on relating to multi-inde models, statistical approach based on the Rademacher complexity, and an algebraic approach for the case of polynomial activations).
In this work we take here a different route: we shift the focus from the function class F. to an individ- ual function f E Namely, our proof starts by asking the following question: for a fixed function f. what is the probability that it would give good approximate fit on the (random) data? For simplicity, consider for a moment the case where we require actually interpolate the data (i.e., perfect fit), and say that are random =1 labels. The key insight is that isoperimetry implies that either the O-level set of f or the 1-level set of f must have probability smaller than exp (- (Tap(rr)))
nd Thus, the probability that f fits all the n points is at most exp (- so long as both labels
E 1-1,1) actually appear a constant fraction of the time. In particular, using union bound?, finite function class F of size N with T--Lipschitz functions, the probability that there exists function f E F fitting the data is at most
nd
exp [log(N) T,2
nd T,2
exp
nd Thus we see that, < V log(N)> then the probability of finding a fitting function in F very small. This basically concludes the proof, since via standard discretization argument, for smoothly parametrized family with (bounded) parameters expects log Ö(p).
We now give the formal proof, which applies in particular to approximate fit rather than exact fit in the argument above. The only difference is that will identify well-chosen subgaussian random variable in the problem. We start with the finite function class case:
Theorem 2. Let (xt, Mi) be i.i.d. input-output pairs in RR [-1, such that:
1. The distribution μ of the covariates can be written as μ Ei Ceflee where each pr satisfies c-isoperimetry and aq 2 0, Ei= at
2. The expected conditional variance of the output is strictly positive, denoted o² IE' ar [y]l > O.
Then one has:
P
3f E F: Σ
(y: - (f=))(=)))2--
522
1=1
nE²
endd
< 4k exp
exp
[og(([F)
83
g
'In this informal argument we ignore the possibility that the labels are not well-balanced. Note that the probability of this rare event is not amplified by union bound over E F.
5

---

We start with lemma showing that, to optimize beyond the noise level one must necessarily cor- relate with the noise part of the labels. In what follows we denote g(z) [/| for the target function, and target function g(x;) and the noise term 2;). Lemma 2.1. One has
g(z;) for the noise part of the observed labels (namely is the sum of the
1 Σ ( - f(x))) 50²- -c) S 2eep
nE² 83
- BfeF:
P Bfe
+PP
f(x))
Proof. The sequence (zf) is i...d. with mean o², and such that ity yields:
|2, < 4. Thus Hoeffding's 's inequal-
ne²
o5 2 0²
S exp
(2.1)
n
6
83
On the other hand the sequence (zig(z+)) i..dd, with mean (since E[2, [r:] 0), and such that [æ:g(z,) < 2. Thus Hoeffding's inequality yields:
e
nE²
P
(g((1:) S -0)
< exp
(2.2)
71
83
Let us write Z
--1 2n), G In
{(nn)), and F (f(
vn
We claim that if 2|
2
0²
and (Z, G) 2 - +. then for any f E F one has
G Z 2 s 0² (F,
This claim together with (2.1) and (2.2) conclude the proof. On the other hand the claim itself directly follows from:
0² -² - - -111--1---111--22----11 FI 02 -((2, F)
2
We can proceed to the proof of Theorem 2:
Proof. First note that without loss of generality we can assume that the range of any function in J is included in [-1,1] (indeed clipping the values improves both the fit to any E [-1,1] and the Lipschitz constant). We also assume wlog that all functions in are T-Lipsehitz.
For clarity let us start with the case k 1. By the isoperimetry assumption we have that V [aa)).)BBB1] is 1-subgaussian. Since [z
2, we also have that Va /d(())))33//De is 4- subgaussian. Moreover, the latter random variable has zero-mean since B[z[z] 0. Thus by Proposition 1.2 we have:
P(V
d Σ ((((.)) -(f)) 21) < 2exp (-(1/9)2).
P
We rewrite the above as:
n - (((x:))
2 ' < 2cxp (- 2nd
(2.3)
9+cL2
Since assumed that the range of the functions is in 1-1, 1] we have [[f] [-1, 1] and hence:
3 J 1
E e <P
24 2
(2.4)

---

(This step is the analog of requiring the labels y: to be well-balanced in the example of perfect interpolation.) By Hoeffding's inequality, the above quantity is smaller than 2 eexp(-ne" /8*) (recall that | < 2). Thus we obtain with an union bound:
FFEF: 1 Σ (1))) 1
S FP
(f(zi) B[f)) 2
+
21
12
8
1
(-end 94cl2
2nd
nE
2|F| exp
+ exep
83
Together with Lemma 2.1 this concludes the proof for k 1.
We now turn to the case k > 1. We first sample the mixture component & E [K] for each data point i E [n]. and we now reason conditioned on these mixture components. Let St c [n] be the set of data points sampled from mixture component e E [k), that is H; i E St, is i.i.d. from μig. We now
have that / / [(ala)=""+11 is i-subgaussian (notice that the only difference is that now need to center by IE [f]. which depends on the mixture component). In particular using the same reasoning as for (2.4) we obtain (crucially note that Proposition 1.2 does not require the random variables to be identically distributed):
IP
1
Σ (f(z.)
10 E0,,
-E% [f]]z
2exp
(-
ennd
(2.5)
8
94c62
Next we want to appropriately modify (2.4). To do so note that:
max E|
m.
1.1] 1=1
SE
so that we can rewrite (2.4) as:
1 Σ n
P
38 FFF
F:
[f]z
T1
i
Now note that >x
See
S Vikk and thus we have:
S k
n
2 S P
24
St
21
2
v
SS
8
k
k
FE
S
IES
Finally by Hoeffding's incquality, we have for any l E [k]. IP (Eiest
24
t
Sp
2 exp
and thus the last display is bounded from above by 2k exp now be concluded as in the case k = 1.
2
ne²
The proof can
8
Finally we can now state and prove the formal version of the informal Theorem from the introduc- tion.
Theorem 3. Let F. be class of functions from Rd R and let (si, yi) be i.i.d. input-output pairs in dd x 1.1, Fix e, 8 E (0, 1). Assume that:
1. The function class can be written as F = (Jm, w E W) with W c RR,, diam(W) S W and for any wi W2 W,
1| - swolloo S J1lu1 wzll-
2. The distribution μ of the covariates 2; can be written as μ Eis aepee where each μe satisfies c-isoperimetry, as 2 0, Σi= ar = 1, and is such that 9 k log(Sk/5) S ne?.
3. The expected conditional variance of the output is strictly positive, denoted o²
[Varlyll > 0.
7

---

Then, with probability at least 1- - 5 with respect to the sampling of the data, one has simultaneously for all f E F:
a Lip(s) 2 2 Ve p plog(60W: + log(4/))
nd
-i)
Proof. Define WL Wy WL = fw W: Lip(fw) S L)). Denote WL.e for an 6J net of Wy. We have in particular (Wdl = (c We apply Theorem 2 to FL,e = {fw, w E We,c7:
-et
IP Af E FL.e:
Σ
(vr ((x)) S - and Lip(f) 2T
2
i=1
(-
ne?
nnnd
I 4k exp
94k (-94k)
+ 2 eexp
(00ppppgp plog(60W JE
86
Observe that if || glooo= S and |/ so 119|/00 I then Ei= fx:))² S + Di (yi - g(x;)) ) (We may again assume without loss of generality that all functions F map to 1 Thus we obtain for any I, > O:
P
3f
Σ(u:
(v: f(xx))) =
-2- -c and Lip(f) S L
1
nc² 9*
end 86
s 4k exp
+ exx Delog(oWWJe-))
The first assumption ensures that for any ur E WT. there is w' E WL. with [| fw
8o S E. The second assumption shows the probability just above is at most ô when
nd
This concludes the proof.
L
2d 2VV
3 Deep neural networks
We now specialize the law of robustness (Theorem 3) to multi-layer neural networks. We consider rather general class of depth neural networks described as follows. First, we require that the neurons are partitioned into layers Li....,Cp Cp, and that all connections are from L: + C, for some < j. This includes the basic feed-forward case in which only connections L; - Li+1 are used as well as more general skip connections. We specify (in the natural way) neural network by matrices W, of shape |4,1 Eies [c,] for each 1 S j I D, as well as 1-Lipschitz non- non-linearities JeE and scalar biases by. for each (j,E) satisfying E |Cyl. We use fixed non- coneaiiissssies o,,e as well a fixed architecture, in the sense that each matrix entry Wy[k, is either always else it is variable (and similarly for the bias terms).
To match the notation of Theorem 3, identify the parametrization in terms of the matrices (W,) and bias terms (bg,c) to a single p-dimensional vector w as follows. A variable matrix entry W [k, E is set to Wa(j.k.) for some fixed index a(j, k. L) [p]. and a variable bias term bI.e is set Wa(j.) for some a(j, f) E [p]. Thus now have a parametrization w E RP + Sao where fur is the neural network represented by the parameter vector w. Importantly, note that our formulation allows for weight sharing (in the sense that a shared weight is counted only as single parameter). For
example, this is important to obtain an accurate count of the number parameters in convolutional architectures.
In order to apply Theorem 3 to this class of functions we need to estimate the Lipschitz constant of the parametrization w fw. To do this we introduce three more quantities. First, we shall assume that all the parameters are bounded magnitude by W. that is we consider the set of neural networks parametrized by E [-W, W]P. Next, for the architecture under consideration, denote Q for the maximum number of matrix entries/bias terms that are tied to a single parameter w, for some [p]. Finally we define
B(w)= = II max(1 1)-
JE(D]
8

---

Observe that ((w) is an upper bound on the Lipschitz constant of the network itself, i.., the map + fw (2). turns out that a uniform control on it also controls the Lipschitz constant of the parametrization w -> Sw. Namely we have the following lemma:
Lemma 3.1. Let x E Rd such that |||||| - R. and w1, w2 E IP such that B(w1), B(w2) S B. Then one has
1f (z) - fwz (x)) S B BRQ w2ll
Moreover for any [-W.W] with W 2 1. one has
B(w)= = ( vpQ)".
Proof. Fix an input x and define 9s by 9z = fw(zz) A standard gradient calculation for multi-layer neural networks directly shows that (w)ll> B(w)QR so that || Vg (w)) S
B(w)QR Since the matrix operator norm is convex (and nonnegative) it follows that ((w) S
B(w)) S B on the entire segment [wi w2] by multiplying over layers. Thus g/ [w)]] S
B² Q/R/ on that segment, which concludes the proof of the first claimed inequality. The second
claimed inequality follows directly from |[W I || S W VpQ.
Lemma 3.1 shows that when applying Theorem 3 to our class of neural networks one can always take J = RRW Qp) (assuming that the covariate measure μi is supported on the ball of radius R). Thus in this case the law of robustmess (under the assumptions of Theorem 3) directly states that with high probability, any neural network in our class that fits the training data well below the noise level must also have:
Lip(f) 2 â (v) nd
(3.1)
Dp
where Ω hides logarithmic factors in W,p, p, Rz Q, and the probability of error 5. Thus we see that the law of robustness, namely that the number of parameters should be least nd for smooth model with low training error, remains intact for constant depth neural networks. If taken at face value, the lower bound (3.1) suggests that is better in practice to distribute the parameters towards depth rather than width, since the lower bound is decreasing with D. On the other hand, we note that (3.1) can be strengthened to:
Lip(f) 2 á (V nd
log plgg(B))) (Vor)(())
(3.2)
for the class of neural networks such that B(ur)= S B. In other words the dependency on the depth all but disappears by simply assuming that the quantity B(r)) (a natural upper bound on the Lipschitz constant of the network) is polynomially controlled. Interestingly many works have suggested to keep B(w) under control, either for regularization purpose (for example [BFT17] relates B(w) to the Rademacher complexity of multi-layer neural networks) or to simply control gradient explosion during training, see e.g.. [ASB16, CBG 17, MHRB17, MKKY18, 18, JCC 19, YM17J. Moreover, in addition to being mell-motivated in practice, the assumption that B is polynomially controlled seems also somewhat unavoidable in theory, since B(w) is upper bound on the Lipschitz constant insttattzconstant L.p(Sw). Thus a theoretical construction showing that the lower bound (3.1) is tight (at some large depth D) would necessarily need to have exponential gap between Lip(fw) and ((w). We are not aware of any such example, and it would be interesting to fully elucidate the role of depth in the law of robustness (particularly if it could give recommendation on how to best distribute parameters in a neural network).
4 Generalization Perspective
The law of robustness be phrased in slightly stronger way. generalization bound for classes of Lipschitz functions based on data-dependent Rademacher complexity. In particular, this perspective applies to any Lipschitz loss function, whereas analysis in the main text was specific to the squared loss. We define the data-dependent Rademacher complexity Rad (F) by
Radn, (F) = - E
1
sup fEF
Σ i=1
(a((())
(4.1)
11.

---

where the values (or)iein) are ii.d. symmetric Rademacher variables in {-1,1} while the values (rz)ie(n) are ii.d. samples from
Lemma 4.1. Suppose Eiz Cuty is a mixture of c-isoperimetrie distributions. For finite F consisting of L-Lipschitz f with [f(x) & for all (f.x) E F x R we have
Rad (F) SO max (VE. L
(log((F)) nd
L
(4.2)
The proof is identical to that of Theorem 2. Note that Radm, (F) simply measures the ability of functions in J to correlate with random noise. Using standard machinery implies the following generalization bound:
Corollary 4.2. For any loss function E(t, y) which is bounded and 1- 1-Lipschitz in its first argument and any [0, 1), in the setting of Lemma I we have with probability at least 1 the uniform convergence bound:
((((s)) so s max (V L. clog((F)) E ((((()))))))
n
(lg((10) n
)
sup feP
nd
Proof. Using McDiarmid's concentration inequality it is enough to bound the left hand side in ex- pectation over (z). v.). Using the symmetrization trick, one reduces this task to upper bound
Σ a.((())))..
sup fEF
Fixing the pairs (I,, yi) and using the contraction lemma (see e.g., ISSBD14, Theorem 26.9]) the above quantity is upper bounded by Rad (F) which concludes the proof.
D
Of course, one can again use e-net to obtain analogous result for continuously parametrized function classes. The law of robustness, now for general loss function, follows as a corollary (the argument is similar to (Proposition [BELM20]]). Let point out that many papers have stud- ied the Rademacher complexity of function classes such as neural networks (see c.g. [BFT17], or [YKB 19] in the context of adversarial examples). The new feature of result is that isoperimetry of the covariates yields improved generalization guarantees.
Funding Acknowledgement
Funding in direct support of this work: NSF grant CCF-2006489, NSF graduate research fellowship. Stanford graduate fellowship. Additional revenues related to this work: internship employment by the second author at Microsoft Research.
References
[ASB16] Martin Arjovsky, Amar Shah, and Yoshua Bengio. Unitary evolution recurrent neu- ral networks. In International Conference on Machine Learning, pages 1120-1128 128. PMLR, 2016.
[ELM200] Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 4977-4986, 2020.
[BFT17] Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. Spectrally-normmaizze margin bounds for neural networks. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
10

---

[BHMM19] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, (16(32):1584--1588) 2019.
[B197] Sergey Bobkov and Michel Ledoux. Poincaré's inequalities and Talagrand's concen- tration phenomenon for the exponential distribution. Probability Theory and Related Fields, 107(3)383-400,, 1997.
[BL00] Sergey G Bobkov and Michel Ledoux. From Brunn-Minkowski to Brascamp-L Lieb and to logarithmic Sobolev inequalities. Geometric Functional Analysis GAFA, 10(5):1028-100 1102100088112,2222 2000.
[BLT200] Peter L. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):3003333007 2020.
[BLN21] Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. A law of robustness for two- layers neural networks. In Conference on Learning Theory, pages 804-820. PMLR, 2021.
[CBG + 17] Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In In- ternational Conference on Machine Learning, pages 854-863 PMLR, 2017.
[CCNW21] Hong-Bin Chen, Sinho Chewi, and Jonathan Niles-Weed. Dimension- free log-sobolev inequalities for mixture distributions. Journal of Functional Analysis, 281( 2021.
[FMN16] Charles Fefferman, Sanjoy Mitter, and Hariharan Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4):983-1449 2016.
19] Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsieh, Liwei Wang. and Jason D Lee. Convergence of adversarial training in overparametrrized neural networks. Advances in Neural Information Processing Systems, 32: 13029-13040, 2019.
[GMF+18) 18] Justin Gilmer, Luke Metz, Fartash Faghri, Samuel S Schoenholz, Maithra Raghu, Martin Wattenberg, and Ian Goodfellow. Adversarial spheres. arXiv preprint arXiv:1801.022 02774, 2018.
[GQU+20] Sven Gowal, Chongli Qin, Jonathan Uesato, Timothy Mann, and Pushmeet Kohli. Un- covering the limits of adversarial training against conn-bounded adversarial examples. arXiv preprint arXiv:2010.03593, 2020.
[Gro86] Mikhael Gromov. Isoperimetric inequalities in riemannian manifolds. In Asymptotic Theory of Finite Dimensional Spaces, volume 1200, pages 114-129. Springer Berlin, 1986.
[HS89] Trevor Hastie and Werner Stuetzle. Principal curves. Journal of the American Statisti- cal Association, 84(406):502-516, 1989.
JJCC 19] Haoming Jiang, Zhehui Chen, Minshuo Chen, Feng Liu, Dingding Wang, and Tuo Zhao. On computation and generalization of gans with spectrum control. Proc. of International Conference on Learning Representation (ICI.), 2019.
[KI99] Nanda Kambhatla and Todd K Leen. Fast nonlinear dimension reduction. In IEEE International Conference Neural Networks, pages 1213-1218. IEEE, 1993.
[Led99] Michel Ledoux. Concentration of measure and logarithmic Sobolev inequalities. In Seminaire de probabilites XXXIII, pages 120-216. Springer, 1999.
[Led01] M. Ledoux. The concentration of measure phenomenon. In Mathematical Surveys and Monographs, volume 89, American Mathematical Society, Providence, RI, 2001.
11

---

[MHRB17] Zakaria Mhammedi, Andrew Hellicar, Ashfaqur Rahman, and James Bailey. Efficient orthogonal parametrisation of recurrent neural networks using householder reflections. In International Conference on Machine Learning, pages 2401-2409. PMLR, 2017.
[MKKY18] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. Proc. of International Conference on Learning Representation (ICLR), 2018.
[MM19] Song Mei and Andrea Montanari. The generalization error of random features regres- Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
sion:
[MMS 18] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. Proc. of International Conference on Learning Representation (ICLR), 2018.
18B Roman Novak, Yasaman Bahri, Daniel A Abolañia, Jeffrey Pennington, and Jascha Sohl-Dickstein. Sensitivity and generalization in neural networks: empirical study. arXiv preprint arXiv: 2018.
[NKB 20] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In Inter- national Conference on Learning Representations, 2020.
[NM10] Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In Proceedings of the 23rd International Conference on Neural Informa- tion Processing Systems- Volume 2, pages 1786-1794, 2010.
[RS00] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2333-22222 2000.
[RWK20] Leslie Rice, Eric Wong, and Zico Kolter. Overfitting in adversarially robust deep learn- ing. In Proceedings of the 37th International Conference on Machine Learning, vol- ume 119 of Proceedings of Machine Learning Research, pages 8093-8100 8104. PMLR, 2020.
[SSBD14] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[TDSL00] Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric frame- work for nonlinear dimensionality reduction. science, 290(5500):3199 23223,33, 2000.
[Ver18] Roman Vershynin. High-dimensional probability: introduction with applications in data science, volume 47. Cambridge university press, 2018.
[vH14] Ramon van Handel. Probability in high dimension. Technical report, Princeton Uni- versity, 2014.
[XY20] Cihang Xie and Alan Yuille. Intriguing properties of adversarial training at scale. In International Conference Learning Representations, 2020.
[YKB19] Dong Yin, Ramchandran Kannan, and Peter Bartlett. Rademacher complexity for ad- versarially robust generalization. In International conference on machine learning, pages 7085-7094. PMLR, 2019.
[YM17] Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint 1rXiv:1705.10941,200
[YSJ19] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks powerful mem- orizers: a tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, pages 15532-15543, 2019.
12


Reviews:
[{"review_id": "zZ8gCQz5KJk", "reviewer": "Reviewer_Z64o", "summary": "It is generally possible to interpolate train data as long as the number of parameters of our model exceeds the number of training points. The present paper asks how many parameters do we need if we want to interpolate in a smooth manner. If the smoothness is measured by Lipschitzness, the paper proves that one needs at least n d parameters to do so, where d is the ambient dimension (Theorem 1). The main assumptions are i) Lipschitz parametrization of the model with bounded parameters, ii) isoperimetric distribution of the train data, iii) positive noise level. This result, in particular, settles a conjecture by Bubeck, Li, and Nagaraj modulo assumption iii). ", "questions": "", "limitations": "", "rating": 10, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "***Pros***\n\n - the proposed result is beautiful and truly interesting for the community. If indeed overparametrization (by a factor d) is necessary for smooth interpolation, this could have practical incidence on the type of model one tries to train on real datasets. This needs, of course, to be supported by other theoretical results and further experimental evidence. Note that such speculative discussion is extensively detailed in the paper (Section 1.1).\n - the theoretical framework is sound and simple enough so that one can imagine building upon it. \n - the exposition of the paper is very clear.\n\n***Cons***\n\n - there seems to be a slight inaccuracy in the proof of Lemma 2.1. At the end of p. 5, when lower bounding \\norm{Z}^2+2\\langle Z,G-F\\rangle + \\norm{G-F}^2, I find \\sigma^2 - \\epsilon/6 + 2(-\\epsilon/6)-2\\langle Z,F\\rangle + 0 (using l. 207 and \\norm{G-F}^2\\geq 0). Therefore the lower bound is \\sigma^2-\\epsilon/2-2\\langle Z,F\\rangle. The above display thus reads \\langle F,Z\\rangle \\geq \\epsilon /4, not \\epsilon /3 and same thing in the statement of the lemma. I did not echo further, but it seems to change the way \\epsilon has to be cut before using Lemma 2.1 in the subsequent derivations. To be clear: this is not a major mistake, the proof certainly still holds, but the numerical constants could change. I will increase my score if the rebuttal makes the changes to be made precise (or if I missed something here).\n \n***Minor comments and typos***\n\n - l. 149: missing 2 in the definition of sub-Gaussian. Also t is not defined in this definition.\n - l. 206: comma inside the parenthesis in the definition of G", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "kcs6OcQ-fwt", "reviewer": "Reviewer_pXqe", "summary": "This paper provides a lower bound on the *global* Lipschitz constant (with respect to the 2-norm) of any function within a parameterized function class that fits data below the noise level that scales inversely in the number of parameters p, showing that overparameterization is *necessary* to ensure a smooth fit of noisy training data. These lower bounds hold under the following assumptions/caveats:\n\n- the d-dimensional input data satisfies the assumption of c-isoperimetry, which includes the Gaussian measure, strongly log-concave measures and distributions over d-dimensional manifolds with a positive Ricci curvature.\n\n-- the parameters (\"weights\") of the function class are polynomially bounded in (n,d).\n\n-- the training data has positive label noise, and the function is constrained to fit below the noise level (which includes the case of interpolation of training data).\n\n-- the smoothness (Lipschitz) constant is evaluated with respect to the 2-norm.\n\nThe paper contextualizes these results in the context of deep neural networks and provides two lower bounds on the Lipschitz constant that (in addition to the scaling given in n, d, and p) scale inversely either in the depth or the product of spectral norms of layers. The latter is a well-known upper bound on the Rademacher complexity of deep neural networks. Both results show an additional dependence on the number of parameters p that is required to ensure small Lipschitz constant --- such a dependence is not present in typical Rademacher complexity bounds used to upper bound clean generalization error.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Strengths of submission:\n\n-- Establishing fundamental limits on adversarial robustness of function classes is an important open problem. This paper makes progress towards this mathematically challenging goal (albeit by lower bounding the global Lipschitz constant, whose precise relationship to the adversarial error remains unclear).\n\n-- The proof technique is relatively elementary, but innovative. In particular it makes elegant use of the isoperimetry property (which by definition is connected to Lipschitz-ness). Because of the ultimate application of parameter counting, it is also very generally applicable to arbitrary parametric function classes and shows insightfully that the number of parameters fundamentally bottlenecks a smoothness guarantee subject to fitting a non-zero amount of noise.\n\n-- This proof technique could be useful to study the generalization error of interpolating solutions for generic function classes beyond the adversarial examples problem.\n\nWeaknesses of submission:\n\n-- As discussed in Section 1.1 of the paper, it is very unclear whether the global Lipschitz constant is fundamentally related to the adversarial generalization error: intuitively, their relationship would depend on more fine-grained quantities such as the *distribution* of the Lipschitz constant over the data domain. In fact one can construct toy scenarios using 1-D data and polynomial features for which the global Lipschitz constant could worsen with overparameterization, but generalization error (clean or adversarial) might improve depending on the overall distribution of the local Lipschitz constants. Question for authors: do you think there is any possibility of studying these more fine-grained properties in the future, that might be more reflective of adversarial error, as a consequence of this approach?\n\n-- The results would also be stronger if matching, or at least close upper bounds could be provided, i.e. *there exists* a function within the function class that has sufficiently small Lipschitz constant that decays with overparameterization. This would be required to make the definitive case that overparameterization actually allows us to find functions with a small global Lipschitz constant (which is in fact sufficient for low adversarial error). Alternatively, this would shed light on whether a low Lipschitz constant is reasonable to expect and *necessary* for adversarial robustness; either way, it would be of interest. Perhaps this is possible via an anti-concentration approach, but it would also require characterizing the size of the set of globally L-smooth functions in the function class (which is not needed for the lower bound as one can simply upper bound this by the size of the function class itself). Do the authors think their techniques could be used for an upper bound in the future for the same problem; if so, how?\n\n-- The techniques are currently presented for Lipschitz constant with respect to l2-norm: the more standard quantity in the adversarial robustness literature is the infinity-norm. The authors mention in Section 1.1 that they believe that a variant of the law of robustness would also hold for the infinity-norm, but they do not provide details on this (in particular I am not sure if the techniques will be similar for the case of distributions over manifolds).\n\nMinor caveats/additional context that could be added in the paper:\n-- Because of the centrality of the union bounding approach to the proof, the techniques appear unlikely to shed light on the smoothness of specific functions that interpolate training data and arise in practice (e.g. variously regularized neural nets such as minimum-norm, minimum-path-norm, etc). \n\n-- The results critically constrain the function class to be fitting a non-zero amount of noise, which may not always be the case in practice. A short discussion on whether these results might imply a small Lipschitz constant on regularized function classes and/or noiseless data might be a good addition to the paper.\n\n---- after response ---- \nthanks to the authors for their detailed and well-thought-out response. I've increased my score accordingly. Please see comments below for details.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work. One suggestion: the authors are encouraged to provide a contextualization of their results with the following work, e.g. in the broader discussion in Section 1.1:\n\n\"Rademacher complexity for adversarially robust generalization\", by Dong Yin, Kannan Ramchandran and Peter L Bartlett. \n\nThis paper takes a different approach and upper bounds the Rademacher complexity of adversarially robust generalization error for specific functions (and also uncovers extra dimension dependencies).\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "gJQbFBdCN0p", "reviewer": "Reviewer_Xj7d", "summary": "This paper shows that if one wants to interpolate the data smoothly, the number of parameters required is $d$ times more than mere interpolation. More precisely, they show that for any function class smoothly parametrized by $p$ parameters, and for any $d$-dimensional dataset satisfying mild regularity conditions, any function in this class that fits the data below the noise level must have its (Euclidean) Lipschitz constant larger than $\\sqrt{nd/p}$. \n\nTo demonstrate this, the authors show that for random labels, if the distribution satisfies isoperimetry then either the 0 level or 1 level set has probability upper bounded by $\\exp(-d/C^2)$ where $C$ is the Lipschitz constant of $f$. A union bound then gives an upper bound on the probability of a function fitting the data. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "I think this is a good paper and vote to accept it. I find the result interesting and the paper proves a prior conjecture in the case of polynomially bounded weights. I think the proof is intuitive and clearly presented. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper and of limited social impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "20PNSice_9D", "reviewer": "Reviewer_gUHM", "summary": "The paper describes a universal law of robustness via isopemitry, which states that smooth interpolation requires d times more parameters than usual interpolation. The authors then include a discussion of their results for the MNIST and ImageNet datasets, and go through the proof of the main results. The authors conclude with a discussion of their results for deep learning.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "1. Originality\n\nThe tasks and/or methods are not new. The work is a direct follow-up of [BLN21] and the proof techniques regarding isometry and concentration are not new. Nevertheless, the main result is new and fairly interesting.\n\n2. Quality\n\nThe submission is technically sound and the main theorems make sense. A part that may need more explanation or refinement is the speculative discussion with MNIST and ImageNet. The main results are stated with constants, and even though the law of robustness \"predicts any such model must have at least nd parameters\", it is not clear if it is 100nd or 0.1nd; perhaps some additional clarification on the constant would be helpful. Another part that I feel can be beneficial to add in the paper is a discussion on cases where the main results are tight; i.e., conditions where an if and only if result holds. Additional discussion on the weaknesses of the work would also be helpful. \n\n3. Clarity\n\nThe paper is nicely written and organized. I would think it would be more beneficial to use more of the pages to discuss the implications/significance of the results and put the proof in the supplementary (since the proof takes up almost half of the main text). Some additional comments regarding typos are included in the Section 5 of this main review. Two minor comments on clarity:\n\na. In Theorem 1, where perhaps it would be nice to add the dependence of epsilon in the equation.\n\nb. In the abstract, particularly the last two sentences, \"We prove this universal law of robustness... this law was conjectured in prior work by Bubeck, Li and Nagaraj\" gave me the impression that the work confirmed this conjecture for 2-layer NNs and Gaussian covariates, however, in Section 1.2 the authors clarify that \"Our results does not actually prove their conjecture,...\". I think it may be a good idea to change the text in the abstract to prevent this kind of subtle misinterpretation.\n\n4. Significance\n\nThe results continues work on conjectures from prior work due to Bubeck, Li and Nagaraj, and from this theoretical perspective the results are important. However, due to the pure theoretical nature of this work and plenty of the main text occupied by the proof, practical significance is a bit lacking, and perhaps this may be addressed in further revisions.\n\n5. Typos\n\nA minor typo is in Line 36, \"theoreof\" perhaps should be \"thereof\".\n\nUpdate after reviewing comments: Increasing score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No discussions on societal impact is available.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper adds an interesting ingredient to the substantial literature on interpolating / memorizing data using neural networks by asking how things change if the neural network is required to be smooth (Lipschitz). The results essentially show that there is a cost to smoothness, appearing as a multiplicative factor of d in the number of parameters of the model. Smoothness of the model loosely corresponds to robustness against adversarial examples, and thus, the results shed light on the empirically observed phenomenon that sufficiently large models can be made more robust. Significantly, they give fairly precise numerical predictions that may help to guide the practice of deep learning. 
Decision: Accept (Oral)