A law of robustness for two-layers neural networks
Authors: Sebastien Bubeck
Yuanzhi Li
Dheeraj Mysore Nagaraj
Venue:  (2021)
Keywords: neural networks
approximation theory
robust machine learning

Abstract: We initiate the study of the inherent tradeoffs between the size of a neural network and its robustness, as measured by its Lipschitz constant. We make a precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with $k$ neurons that perfectly fit the data must have its Lipschitz constant larger (up to a constant) than $\sqrt{n/k}$ where $n$ is the number of datapoints. In particular, this conjecture implies that overparametrization is necessary for robustness, since it means that one needs roughly one neuron per datapoint to ensure a $O(1)$-Lipschitz network, while mere data fitting of $d$-dimensional data requires only one neuron per $d$ datapoints. We prove a weaker version of this conjecture when the Lipschitz constant is replaced by an upper bound on it based on the spectral norm of the weight matrix. We also prove the conjecture in the high-dimensional regime $n \approx d$ (which we also refer to as the undercomplete case, since only $k \leq d$ is relevant here). Finally we prove the conjecture for polynomial activation functions of degree $p$ when $n \approx d^p$. We complement these findings with experimental evidence supporting the conjecture.

Under review as a conference paper at ICLR 2021
A LAW OF ROBUSTNESS FOR TWO-LAYERS NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
We initiate the study of the inherent tradeoffs between the size of a neural net- work and its robustness, as measured by its Lipschitz constant. We make precise conjecture that, for any Lipschitz activation function and for most datasets, any two-layers neural network with ic neurons that perfectly fit the data must have its Lipschitz constant larger (up constant) than / /n/k where is the number of datapoints. In particular, this conjecture implies that overparametrization is neces- sary for robustness, since means that one needs roughly one neuron per datapoint to ensure a (1)-Liischitz network, while mere data fitting of d-dimensional data requires only one neuron per datapoints. We prove weaker version of this con- jecture when the Lipschitz constant is replaced by an upper bound on it based on the spectral norm of the weight matrix. We also prove the conjecture in the high- dimensional regime n R d (which we also refer to as the undercomplete case, since only & S d is relevant here). Finally we prove the conjecture for polynomial activation functions of degree p when n d². We complement these findings with experimental evidence supporting the conjecture.
INTRODUCTION
We study two-layers neural networks with inputs in Rd, k neurons, and Lipschitz non-linearity vi: : + E. These are functions of the form:
k
arblwe- - x be),
(1)
with ag by E IR and W, Idd for any e E [k]. We denote by FV( the set of functions of the form (1). When & is large enough and v non-polynomial, this set of functions can be used fit any given data set (Cybenko, 1989; Leshno et al., 1993). That is, given a data set (z,, M))e(m) [ R)", one can find f E (eb)) such that
f(x,) = yr, Vi E [n].
(2)
In a variety of scenarios one is furthermore interested in fitting the data smoothly. For example, in machine learning, the data fitting model f is used to make predictions at unseen points & In J. It is reasonable to ask for these predictions to be stable, that is a small perturbation of x should result in a small perturbation of fxx)
A natural question is: how "costly" is this stability restriction compared to mere data fitting? In practice seems much harder to find robust models for large scale problems, as first evidenced in the seminal paper (Szegedy et al., 2013). In theory the "cost" of finding robust models has been investigated from a computational complexity perspective (Bubeck al., 2019), from a statistical perspective in (Schmidt et al., 2018), and more generally from model complexity perspective in (Degwekar et al., 2019; Raghunathan et al., 2019; Allen-Zhu and Li, 2020). We propose here a different angle of study within the broad model complexity perspective: does model have to be larger for to be robust? Empirical evidence (e.g., (Goodfellow et al., 2015; Madry et al., 2018)) suggests that bigger models (also known as "overparameetiization)) do indeed help for robustness.
complexity
Our main contribution is a conjecture (Conjecture and Conjecture 2) on the precise tradeoffs between size of the model (i.e., the number of neurons k) and robustness (i.e., the Lipschitz constant

---

Under review as a conference paper at ICLR 2021
35-
vd
Figure 1: Sce Section 5 for the details this experiment.
of the data fitting model Fx(()) for generic data sets. We say that a data set (æi,, yb sE|n is generic if it i.i.d. with 2; uniform (or approximately so, see below) on the sphere @d-1 {x R ||ق||| = 1} and y, uniform on {-1, We give the precise conjecture in Section 2. We prove several weaker versions of Conjecture and Conjecture 2 respectively in Section 4 and Section 3. We also give empirical evidence for the conjecture in Section 5,
A corollary of our conjecture. A key fact about generic data, established in Baum (1988); Yun et al. (2019); Bubeck et al. (2020), is that one memorize arbitrary labels with &: x n/d, that is merely one neuron per d datapoints. Our conjecture implies that for such optimal-size neural networks it is impossible to be robust, in the sense that the Lipschitz constant must be order vd. The conjecture also states that to be robust (i.e. attain Lipschitz constant O())) one must necessarily have k zs n, that is roughly each datapoint must have its own neuron. Therefore, we obtain a trade off between size and robustness, namely make the network robust it needs be d times larger than for mere data fitting. We illustrate these two cases in Figure 1. We train neural network to fit generic data, and plot the maximum gradient over several randomly drawn points (a proxy for the Lipschitz constant) for various values of vd, when either n (blue dots) or k d (red dots). As predicted, for the large neural network (k: = n) the Lipschitz constant remains roughly constant, while for the optimally-sizen one (k: 10m the Lipschitz constant increases roughly linearly in vd.
d
Notation. For Ω C Rdd we define Lipa(f) = suPa44reR
[(x)) (if = Rd we omit the [-=2'||
subscript and write Lip(f)) where denotes the Fuclidean norm. For matrices llop: || llop... || || and (5.)) for respectively the operator norm, the nuclear norm (sum of singular values), the Frobenius norm, and the Frobenius inner product. We also use these notations for tensors of higher order, see Appendix A for more details on tensors. We denote e > 0 and C' > for universal numerical constants, respectively small enough and large enough, whose values can change in different occurences. Similarly, by Cp > 0 and Cp > O we denote constants depending only on the parameter p. We also write ReLU(L) = max 0) for the rectified linear unit.
Generic data. We give some flexibility in our definition of "generic data" in order to focus on the essence of the problem, rather than technical details. Namely, in addition to the spherical model mentioned above, where is i.i.d. uniform the sphere gd-1 {u E Rd ||= = 1}. we also consider the very closely related model where 2; is i.i.d. from a centered Gaussian with covariance and in fact ||æ; is tightly concentrated around 1). In both cases
I (in particular B[||2, consider y; to i...d random signs. We say that a property holds with high probability for generic data, if holds with high probability either for the spherical model or for the Gaussian model.
2

---

Under review as a conference paper at ICLR 2021
2 A CONJECTURED LAW OF ROBUSTNESS
Our main contribution the following conjecture, which asserts that, on generic data sets, increasing the size of network is necessary obtain robustmess:
Conjecture For generic data sets, with high probability', any I Fe(()) fittin the data? (i.e., satisfying (2)) must also satisfy:
n Lipge-:(1) V k
Note that for generic data, with high probability (for n voly(d), there exists a smooth interpo- lation. Namely there exists g R² - with g(x;) yr. vi E [n] and Lip(g) O(1). This follows easily from the fact that with high probability (for large d) one has || 2, 2 1, + Conjecture puts restrictions on how smoothly one can interpolate data with small neural networks. A striking consequence of the conjecture is that for two-layers neural network f F& (v² to be as robust as this function g (i.e., (f) = ((1) and fit the data, one must have = ((n), i.c., roughly one neuron per data point. On the other hand with that many neurons it is quite trivial to smoothly interpolate the data, as we explain in Section 3.3. Thus the conjecture makes a strong statement that essentially the trivial smooth interpolation is the best thing can do. In addition making the prediction that one neuron per datapoint is necessary for optimal smoothness, the conjecture also gives a precise prediction the possible tradeoff between size of the network and its robustness. We also conjecture that this whole range of tradeoffs is actually achievable:
C n and S. d where C is an arbitrarily large constant the latter occurence. There exists such that, for generic data sets, with high probability, there exists f E Fi((t) fitting the data (i.e., satisfying (2)) and such that
Conjecture 2 Let nt, d, k be such that C-
S C.
n Lipga- CV
VV
The condition S C. n Conjecture necessary, for any interpolation of the data must have Lipschitz constant at least a constant. The other condition k namely k 2 C- d is also necessary, for that many neurons is needed to merely guarantee the existence of a data-fitting neural network with A neurons (see Baum (1988); Yun et al. (2019); Bubeck et al. (2020)). Finally the condition n S de is merely used to avoid explicitly stating a logarithmic term our conjecture (indeed, equivalently can replace this condition by adding multiplicative polylogarithmic term in d in the claimed inequality).
Our results around Conjecture 2 (Section 3). We prove Conjecture 2 for both the optimal smoothness regime (which is quite straightforward, see Section 3.3) and for the optimal size regime (here more work needed, and we use a certain censor-based construction, see Section 3.4). In the latter case we only prove approximate data fitting (mostly to simplify the proofs), and more im- portantly we need to assume that n of order d' for some even integer p. It would be interesting to generalize the proof to any n. While the conjecture remains open between these two extreme regimes, we do give a construction in Section 3.3 which has the correct qualitative behavior (namely increasing k improves the Lipschitz constant), albeit the scaling we obtain is n/k instead of /n/ke see Theorem 1.
Our results around Conjecture (Section 4). We prove a weaker version of Conjecture I where the Lipschitz constant on the sphere is replaced by a proxy involving the spectral norm of the weight matrix, see Theorem 3. We also prove the conjecture in the optimal size regime, specifically when n d for an integer p and one uses a polynomial activation function of degree p, see Theorem 6. For (i.e., ~ d) we in fact prove the conjecture for abritrary non- lineaanaai,see, see Theorem 4.
'We do not quantify the "with high probability" in our conjecture. We believe the conjecture to be true except for event of exponentially small probability with respect to the sampling a generic data set, hut even proving that the statement true with strictly positive probability would extremely interesting. We expect the same lower bound to hold even if one only asks f to approximately fit the data. In fact provable variants of Conjecture hased proofs that robust to only assuming approximately fitting f.
3

---

Under review as a conference paper at ICLR 2021
Further open problems. Our proposed law of robustness is first mathematical formalization of the broader phenomenon that "overparametrizztion in neural networks is necessary for robustness". Ideally one would like much more refined understanding of the phenomenon than the one given in Conjecture 1. For example, one could imagine that greater generality, the law would read (f) 2 F(k, (as; ())tt()) That is, would like understand how the achievable level of smoothness depends on the particular data set at hand, but also on the set where we expect to be making predictions. Another direction to generalize the law would be extend it to multi- layers neural networks. In particular one could imagine the most general law would replace the parameter (number of neurons) by the type of architecture being used and in turn predict the best architecture for given data set and prediction set. Finally note that our proposed law apply to all neural networks, but would also be interesting to understand how the law interacts with algorithmic considerations (for example in Section 5 we use Adam Kingma and Ba (2015) to find set of weights that qualitatively match Conjecture 2).
SMOOTH INTERPOLATION
We start with warm-up in Section 3.1 where discuss the simplest of interpolation with a linear model (k 1, I d) and in Section 3.2 for the optimal smoothness regime (k = n). We generalize the construction of Section 3.2 in Section 3.3 to obtain the whole range of tradeoffs between i and Lip(f), albeit with a suboptimal scaling, see Theorem We also generalize the linear model calculations of Section 3.1 in Section 3.4 obtain the optimal size regime for larger values of n via a certain tensor construction.
3.1 THE SIMPLEST CASE: OPTIMAL SIZE REGIME WHEN n. S c
Let consider A 1, w. I; = for all i E [n). or in other words Xw = Y with X the n x d matrix whose jth row is z;, and Y (y1,..., . 97)) The smoothest solution this system (i.e., the one minimizing ||w]]) is
c d and (t) t. Thus
trying find E Rd such that
w X (xx
Note that
Lip(# w w. = |||||| Vw YT(XXT)-LY.
Using [Theorem 5.58, Vershynin (2012)) has with probability at least 1 exp(C cdl (and using that n I c. d) that
xx 1 T.
and thus Lip(z + w x) < 22 |Y|| = 22n This concludes the proof sketch of Conjecture 2 for simplest case k = I and n S
3.2 ANOTHER SIMPLE CASE: OPTIMAL SMOOTHNESS REGIME
Next we consider the optimal smoothness regime in Conjecture 2, namely h: n. First note that, for generic data and = poly with high probability the caps C, := {ar E Sd-1 I; x x disjoint sets and moreover they each contain single data point (namely x;). With single ReLU unit is then easy to make smooth function (10-Lipschitz) which is outside C, and equal to +1 at I, (in other words the neuron activates for a single data point), namely + 10-ReLU (z, - 0.9). Thus one can fit the entire data set with the following ReLU network which is 10-Lipschitz on the sphere:
0.9) are
f(x)
10g; ReLU (a, x 0.9)
1=1
This concludes the proof of Conjecture for the optimal smoothness regime k = n.
3.3 INTERMEDIATE REGIMES VIA RELU NETWORKS
We now combine the two constructions above (the linear model of Section 3.1 and the "isolation"
strategy of Section 3.2) to give a construction that can trade off size for robustness (albeit not opti- mally according Conjecture 2), see Appendix C for the proof.
4

---

Under review as a conference paper at ICLR 2021
Theorem Let d, k be such that C. n m=log(n) S k S C. For generic data sets, with probability at least 1 1/n there exists E FRe.R)) fitting the data (i.e., satisfying (2)) and such that
ni (llo(d)
Lipge-1(f) SC
C.
k
3.4 OPTIMAL SIZE NETWORKS VIA TENSOR INTERPOLATION
In this section we essentially prove Conjecture 2 in the optimal size regime (namely k d se nt), with three caveats:
1. We allow slack of a log n factor by considering k - d= Cn (og(n) instead of the optimal k d = On as in Baum (1988); Bubeck et al. (2020).
2. We only prove approximate fit rather than exact fit. It is likely that with more work one can use the core of our argument to obtain exact fit. For that reason we did not make any attempt to optimize the dependency on Theorem obtain log(1/E) rather than (F) dependency by using an iterative scheme that fits the residuals, as in (Bresler and Nagaraj, 2020; Bubeck et al., 2020).
For instance one could probably
3. We assume that is of order d for some integer p. While it might be that apply the same proof for odd integers, the whole construction crucially relies on being an even integer we essentially do linear regression over the feature embedding A possible approach to extend the proof to other values of n would be use the scheme of Section 3.3 with the linear regression there replaced by the tensor regression used below.
Sp
Theorem Fix > O. P an even integer, and let vx() tº, Let n, d, k be such that log(n) g² dl and k = Cp dd- Then for generic data, with probability at least 1 - 1/n there exists E Fb(() such that
If(x;) - vil S Cp E
(3)
and
Lipgo-1 (f) S CoV n
Proof. We propose to approximately fit with the following neural network:
f(x) Σ (z - x)P.
Naively one might think that this neural network requires n neurons. However, it turns out that one can always decompose symmetric tensor of order p into k 2- rank-1 symmetric tensors of order p. so that in fact f (v)).. For p = 2 this simply follows from cigendecomposition and for general we give simple proof in [Appendix A, Lemma 2].
One also has by applying [Appendix B, Lemma 4] with r = Cp log(n) and doing an union bound, that with probability at least 1/n for any E [n].
log(n) dp
Vi x2)2 s CC.
< C,E.
(=1,4)
In particular this proves (3).
Thus it only remains to estimate the Lipschitz constant, which by [Appendix A, Lemma is reduced to estimating the operator norm of the tensor Σn yar, Sp. We do so in [Appendix B, Lemma 5]. D
4 PROVABLE WEAKER VERSIONS OF CONJECTURE
Conjecture can be made weaker along several directions. For example the quantity interest Tipga (f) be replaced by various upper bound proxies for the Lipschitz constant. A mild
5

---

Under review as a conference paper at ICLR 2021
weakening would be to replace it by the Lipschitz constant on the whole space (we shall in fact only consider this notion here). A much more severe weakening is to replace it by quantity that depends on the spectral norm of the weight matrix (essentially ignoring the pattern of activation functions). For the latter proxy we actually give a complete proof, see Theorem 3, which in particular formally proves that "overparametrizztionn is law of robustness for generic data sets". Other interesting directions to weaken the conjecture include specializing it to common activation functions, or simply having smaller lower bound on the Lipschitz constant. Section 4.2 prove the conjecture when is replaced by d in the lower bound. We say that this inequality is in the "very high-dimensional case", in the sense that matches the conjecture for n the "undercomplete case", in the sense that only k < d is relevant in this very high-dimensional scenario). In the moderately high-dimensional case (n >> d) the proof strategy we propose in Section 4.2 cannot work. In Section 4.3 we give another argument for the latter case, specifically in the optimal size regime (i.c., ss n) and for a power activation function, see Theorem 5. We generalize this to polynomial activation functions in Section D. In the specific case of quadratic activation function we also show a lower bound that applies for any l and which is in fact larger than the one given in Conjecture 1, see Theorem in Section D.2.
(alternatively we also refer as
4.1 SPECTRAL NORM PROXY FOR THE LIPSCHITZ CONSTANT
We can rewrite (1) as
f(x) a (W b).
(4)
where a = (ai,..., ..) E R (bi...., bx) E IR, W E Rxdd is the matrix whose gth row is wy. and s is extended from R to R + by applying it coordinate-wise, We prove here the following:
Theorem 3 Assume that vb is L-Lipschitz. For f Fe(()) one has
Lip(J) L. ||a]| l|W
For generic data set, if f(xx)) M/ Vi E [n]] and I has no bias terms (i.e., = 0 in (4)), then with positive probability one has:
n
L- G|ll || lop VVEE
(6)
Note that we prove the inequality (6) only with positive probability (i.e., there exists data set where the inequality is true), but in fact it is easy to derive the statement with high probability using classical concentration inequalities.
Proof. Since &b R R L-Lipschitz, we have:
f(x)-f(>') & ||||| (ollllll - +b)ll & I-I[a|l. Wx-WW'll s L-|||||-|[W llop ||0 ==11
which directly proves (5).
Next, following the proof of [Proposition 1, Bubeck et al. (2020)] one obtains that for a generic data set, with positive probability, one has (without bias terms):
k
Vn
Lrl
||we|
L
It only remains to observe that:
Vn
aal
||well =
laz12 2
||
||a||
|[W]|e s VT. VTel[|al
|||lopp
8=
which concludes the proof of (6).

---

Under review as a conference paper at ICLR 2021
4.2 UNDERCOMPLETE CASE
Next we prove the conjecture in the high dimensional case n R d. More precisely we replace n by d in the conjectured lower bound. Importantly note that the resulting lower bound then becomes non-trivial only in the regime k S d (the "undercomplete case").
We consider in fact a slightly more general scenario than interpolation with a neural network, namely we simply assume that one interpolates the data with function f(x) = g(Px) where / is linear projection on k-dimensional subspace (this clearly generalizes f E F& (v)), fact even allows for the non- non-linearity & to depend on the data', or to have a different non non-linearity for each neuron).
Theorem Let n 2 d. Let f R2 + R be a function such that f(x,) = yı, vi E [n] and moreover f(z) g( Px) for some differentiable function g : IR* + IR and matrix P E lgxxd, Then, for generic data, with probability at least exp(C - -cd) one must have
Lip(J) 2 VV K
Proof. Let us modify g so that P simply an orthogonal projection operator (i.e., PPT +g). Let us also assume for sake of notational simplicity that we have a balanced data set of size 2n, that is with: yi.... Dn = +1 and yn++,..... V/n sequence z is i.idd and satisfies E|rla, L..
1. Let us denote xy = 34 In+s for E [n]. The
Now observe that on the segment [ra, un+e] (whose length is less than 2), the function f changes value from +1 1, and thus there exists 2; [1,, [n+i such that:
1 1 (V(2)) (I; zn+t)l = V (=x) 241-
Moreover one has (using that ff(x) = PT V Vg(z). and thus //Vg(z)] [VV((=)] < Lip(f)
ff(22)) z/1 = Vg (Px() < Lip(f) ||
Combining the two above displays one has:
Lip(J)
n
PPlll
n |P
n
TT PT PT
n
dla PT P/Hs.
i=1
i=1
Using [Theorem 5.39, Vershynin (2012)] (specifically (5.23)) we know that with probability at least 1 exp(C - ed) we have |> daay llop I C (here we use n 2 d too). Moreover we have
||PTP|lope Tr(PT P) Tr(PPT) k. Thus we have " PT P) I C d' that
with the above display one obtains
n Lip(S)
I ny d
Ck which concludes the proof.
4.3 POWER ACTIVATION
We prove here the conjecture for the power activation function (0()) 12' with p an integer and with no bias terms (we deal with general polynomials, including with bias, in Appendix D). Without bias such a network can be written as:
f(x) Σ oe x>)0 (T, (p),
where T = =k- a.w? Sp As we already saw in the proof of Theorem 2 (see specifically [Appendix A, Lemma 21), without loss of generality we have k < C. We now prove that tensor net- works of the form (7) cannot obtain Lipschitz constant' better than v n/ TT in accordance with Conjecture for full rank tensors (where k x d111).
'It would be interesting to study whether allowing deta-dependent non- linearities could affect the conclusion of our conjectures. Such study would need to crucially rely on having only one hidden layer, as it is known from the Kolmoggorv-Armoll theorem that with two hidden layers and data-dependent non- -ineariisss obtain perfect approximation properties with & (albeit the non-lincarities
non-smooth).
"Note that without loss of generality one can assume 7 to be symmetric, since we only consider how it acts on 2. Sp, For symmetric tensors one has that the Lipschitz constant on the unit hall is lower bounded by the operator norm of T thanks to (9)
7

---

Under review as a conference paper at ICLR 2021
Amn
maxiumm random gradient
mIKK nandom
Figure 3: Scatter plot of maximum random gra- dient with respect to vd in optimal smoothness (blue) and optimal size (red) regimes (Experiment 2)
Figure 2: Scatter plot of maximum random gradi- ent with respect / with 906 data points (Ex- periment 1)
Theorem Assume that we have a tensor T of order such that (T, x; (P) = ye. Vi E [n]. Then, for generic data, with probability at least C exp( -cpd), one must have
|T 2 cp
n
d=-1
Proof. Denoting Ω Ei= y, have (using yi for the first equality and [Appendix A, Lemma 3] for the last inequality):
n (7, s || |/7 I d || ||
(8)
Thus we obtain ||||pp 2 .--ححح and it only remains to apply [Appendix B, Lemma 5] which states that with probability at least 1 C (cpp- one has [|O]|op & CpV -T.
EXPERIMENTS
We consider a generic dataset from the Gaussian model (i.e., ..,...,,, T, i.id. from N(0, aa) and labels yi...., yn. i..d from the uniform distribution over {-1, and independent of I1. Fn). For various values of (n, k) we train two-layers neural networks with & ReLU units and batch nor- malization (see loffe and Szegedy (2015)) between the linear layer and ReLU layer, using the Adam optimizer (Kingma and Ba, 2015) the least squares loss. We keep the values of (n, lt, d) where the network successfully memorizes the random labels (possibly after a rounding to [-1,+1), and such some small value
be specified later). Given IRd + R. We then generate 21..... 2r (where T = 1000) i.i.d from the distribution (0, La). independently of everything else and define the "maximum random gradient" to be max V (2))) (it is our proxy for follows:
that prior to rounding the least squares loss a triple (n, d, k), suppose the output of the trained network is fn. k
the true Lipschitz constant supaese-: [,, Our experimental results
Experiment 1: We ran experiments with n between 100 and 2000, d berween ~ 50 and ~ n, and k between 10 and (we also choose ε 0.02 for the thresholding). In Figure 2 give scatter plot of ( T m V. (f))) and as predicted we see linear trend, thus providing empirical evidence for Conjecture
Experiment 2: In this experiment, we investigate the two extreme cases k ~ and & ~ n/d. We n = 1 and sweep the value of dl between to 5000 (we also choose & 0.1 the thresholding). In the first case, we let A: = and in the second case we let & = 10n/d. In Figure plot Vd versus the maximum random gradient (as defined above) for both cases. We observe linear dependence between the maximum gradient value and vd when have k 10n/d, and roughly a constant maximum gradient value when = n, thus providing again evidence for Conjecture
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
James Alexander and André Hirschowitz. Polynomial interpolation in several variables. Journal of Algebraic Geometry, 4(2):201 -222, 1995.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint 200i::2000.00/99 2020.
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215, 1988.
Guy Bresler and Dheeraj Nagaraj. A corrective view of neural networks: Representation, memo- rization and learning. arXiv preprint arXiv:2002.00274, 2020.
Sébastien Bubeck, Yin Tat Lee, Eric Price, and lya Razenshteyn. Adversarial examples from com- putational constraints. In International Conference Machine Learning, pages 831-840) 2019.
Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint arXiv:2006.02855 2020.
Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain. Symmetric tensors and sym- metric tensor rank. SIAM Journal Matrix Analysis and Applications, (0(3):1254-1279 2008.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
Akshay Degwekar, Preetum Nakkiran, and Vinod Vaikuntanathan. Computational limitations ro- bust classification and win-win results. volume 99 of Proceedings of Machine Learning Research (COLT), pages 994-1028, 2019.
Shmuel Friedland and Lek-Heng Lim. Nuclear norm of higher-order tensors. Mathematics of Com- putation, 1):1:)):2552223 2018.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2015.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 448- 456, 2015.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
Zhening Li, Yuji Nakatsukasa, Tasuku Soma, and André Uschmajew. On orthogonal tensors and best rank-one approximation ratio. SIAM Journal on Matrix Analysis and Applications, 39(1): 400-425, 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Arkadi Nemirovski. Interior point polynomial time methods in convex programming. Lecture notes, 2004.
Grigoris Paouris, Petros Valettas, and Joel Zinn. Random version of dvoretzky's theorem in lpn. Stochastic Processes and their Applications, 127(10)3188-3222 2017.
Aditi Raghunathan, Sang Michael Xie, Fanny Yang, John C Duchi, and Percy Liang. Adversarial training hurt generalization. In International Conference on Learning Representations, 2019.

---

Under review as a conference paper at ICLR 2021
Bruce Arie Reznick. Sum of even powers of real linear forms, volume 463. American Mathematical Soc., 1992.
Ludwig Schmidt, Shibani Santurkar, Dimitris Tsipras, Kunal Talwar, and Aleksander Madry. Adver- sarially robust generalization requires more data. In Advances in Neural Information Processing Systems, 2018.
Christian Szegedy. Wojeiech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. In International Conference on Learning Representations, 2013.
Roman Vershynin. Introduction the non-asymptotie analysis of random matrices. In Compressed Sensing: Theory and Practice, pages 210-268. Cambridge University Prteess, 2012.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, pages 15532-15543, 2019.
A RESULTS ON TENSORS
tensor of order p is an array T = (T (Te i The Frobenius inner product for tensors is defined by:
(T,S)
Σ
T T St
with the corresponding norm || 11|F.. A tensor said to be of rank it can be written as:
T uh X ... @ up
for - Up RRd. The operator norm llop is defined by:
|| rank S1
sup (T
For symmetric tensors (i.e., such that the entries of the array are invariant under permutation of the p indices), Banach's Theorem (see e.g., [(232), Nemirovski (2004)]) states that in fact one has
|| = sup (T,
zE8
We refer to Friedland and Lim (2018) for more details and background tensors. We now list couple of useful results, with short proofs.
Lemma For a tensor T of order p. one has
Lipga-1(x (T,x Sp ||
Proof.
One has for any Z, y E S
OT) - (T, y bP)
x
(T x 0t-
8 y 04-1) - (T, 3p 2 say
< p | y|
sup z1 ZPE
(T, 80 1
p. || yl
[T]
opp
Lemma 2 For any tensor T of order p. there exists wi..... W2nddr1 Rdd and .I,..., E2r
{-1, +1) such that for all x E Rd
2-1-1
TT x 0pj
=
Σ t=1
&
fwe - x)P
10

---

Under review as a conference paper at ICLR 2021
Results like Lemma 2 go back least to Reznick (1992). In fact much more precise results min- imal decomposition in rank-1 1 tensors are known thanks to the work of Alexander and Hirschowizz (1995). We refer to (Comon al., 2008) for more discussion this topic.
Proof. First note that trivially T can be written as:
T
Σ
Ci1 .... 8 Ei & Ti f-1,, d.
(10)
113-11p1111
Thus one only needs prove that function of the form x = (Wg x) can be written the sum of 2D functions of the form (w' x)). To do so note that, with Eg i..d. random signs,
1
Eqg
Eggigg x
]
= E
Eq
Σ
II
gg Wgg I = p! II m x)
Lemma 3 For any tensor T of order p one has: |T S dp-1. 1op
The above result and its proof are directly taken from et (2018). We only repeat the argument here for sake of completeness.
Proof. Note that the decomposition (10) is orthogonal, and thus for any tensor S of order p has:
S)
x
de-1
(e .... @ c 8 TT .............. 1p-1, 1: dl, 8y2
dp- 11S
Σ
1 1, d][
d= ||S1 ||||.-
Thus one has |T op.. concludes the proof.
op..
I d -²
|| F. By duality one also has || 2 " |[T] which
B RESULTS ON RANDOM TENSORS
Lemma For any fixed x E gd-1 and generic data, with probability at least 1 C (xxp(-c,7) one has:
Σ val x) &Cp
nt
d
Proof. Using [Theorem 1, Paouris al. (2017)) one has, for any fixed gd-1 and 7 S
n
112
x x - nop Cpvnr s Cexp((ccpT)
where op denotes the th moment of the standard Gaussian. Let us denote n* = iii E [n] yi Sp and similarly for n n=,T" ,TT Now with probability e'exp(-cT)
+1} and T = Eiy x
(with respect to the randomness of the 8/8) we have
In
VnT.
11

---

Under review as a conference paper at ICLR 2021
Thus combining the two above displays obtain with probability at least 1 C cexp(-co7).
dp/2
Σ ++==11
looe . 20/"
Σ h==-1
x|"
S C.vnT + +opln* -n - ~n'IsCoVTT
Lemma 5 For generic data, with probability at least
C Cexp(-c,de one has:
m
Σ
yo
op
S sCp
n d=-1
Proof. W be an
2p -net of 8d-1 (in particular W S C.)).. By an union bound and Lemma 4 one
has:
P
Br B
Σ s.l x|? > CDp. dv-1
n = Cexp(-ccd)
(11)
Let = D yiet @ Note that T is symmetric, and thus thanks to (9) and Lemma 1, one has:
|Tllop I mmx x0 oEN
and in particular oT I 2 (T, which together with (11) concludes the proof.
C PROOF THEOREM
Let Ix (by assumption with the same label, say it is the points T1, . with label +1. As in Section 3.1 let E Rd be the minimal norm vector that satisfy w I; 1, and thus as we proved there with probability at least 1 exp(C C ed) one has ||l|| S /2m. Crucially for the end of the proof, also note that the distribution of w is rotationally invariant. Next observe that with probability at least 1 - 1/n (with
log(x) and assume it is integer. Let choose points
|w 2zy S C' C.- CC-1[wlly log(n) S }
respect the sampling of 2m+1....,.. xr) one has In particular the cap C := {ar gd-1, u 2 } contains .i,..., but does not contain any i m. Thus the neuron
+ 2- ReLU w
computes the value 1 at points Ti,... Fm and the value at the rest of the training set.
One can now repeat this process, and build the neurons Wi...., wy (all with norm S /2m), so that (with well-chosen signs & {-1,1) the data perfectly fitted by the function:
k 2 E ReLU (0p-x- (w
f(x) = -
only remains estimate the Lipschitz constant. Note that if point æ gd activates a certain subset A C f1....,ki k) of the neurons, then the gradient at this point is EtEA w/ with w/ w Using that the wyr are rotationally invariant, one also has with probability at least 1 On exp( cod) that |EEA w/ 1 C -AA m for all A can be. We show below that |A| C' log(d) with probability at least C exp((ce (d)) which will conclude the proof.
(l....,k) k). Thus it only remains control how large
12

---

Under review as a conference paper at ICLR 2021
If activates neuron & then we x 2/2 ||wel||
Now note that for any fixed gd-1 and fixed
1ym
A C [6], IP vE E A, We 2 [
I C exp (-c|Al
m
so that
dym
d m In particular conclude that with Cm log(d) the probability that fixed point the sphere activates more than a neuron exponentially small d log(d) (recall that m log(k) S ed by as- sumption). Thus we can conclude via an union bound on an e-net that the same holds for the entire sphere simultaneously. This concludes the proof.
||wx|] 4/m
P VE C [ ||| and v4 E we
S Sexp (Calog(k))
D FURTHER RESULTS AROUND CONJECTURE
D.1 POLYNOMIAL ACTIVATION
We now observe that one can generalize Theorem 5 to handle biases (the parameters by in 1), and in fact even general polynomial activation function. Indeed, observe that any polynomial of (w,,x) + must also be a polynomial in (w,x), albeit with different coefficients.
Theorem Let (t) = Eg a,t 9 and assume that we have f E Fxl such that f = yis Vi E [n]. Then, for generic data, with probability at least 1 C exp(-cpp) one must have
Lip la |al (f) 2 er dP-1
Proof. Note that for f Feb)) there exists tensors To: Tp. such that T, is tensor of order g. and f can be written
((x)
(T x 04).
Now let us define S2 = -im V.r, By and observe that
n Σ v.f(x:)) = (TT, R4)
9=0
and thus there exists 9 (1......p) p) such that (Zg) 2 cnn (we ignore the term q 0 by considering the largest balanced subset of the data, i.e. we assume Σ Yi = 0). Now one can repeat the proof of Theorem to obtain that with probability least C exp( (xpp) one has ||Tzllop 2 C -=-1. It only remains to observe that the Lipschitz constant of f on the unit ball is lower bounded by ||Tyllop-
As we mentioned in Section 4.3, without loss of generality we can assume T, is symmetric, and thus by (9) there exists E gd-1 such that [7g]lop = (Ig. S9). Now consider the univariate polynomial P(I) = f(xx). By Markov brothers' inequality one has max P(() 2 | (0) q! (T q. x 200) = g! [Tal thus concluding the proof.
D.2 QUADRATIC ACTIVATION
In Section 4.3 we obtained a lower bound for tensor networks that match Conjecture I only when the rank the corresponding tensor is maximal. Here we show that for quadratic networks (i.e., p 2) we can match Conjecture 1, and in fact even obtain a better bound, for any rank k:
Theorem Assume that we have a matrix T ddd with rank such that:
(T, = yr, Vi E [n]
Then, for generic data, with probability least 1 - C Cexp(-ccl
must have
Vnd
[ 2 c k (2 (2o/n/k).
13

---

Under review as a conference paper at ICLR 2021
Proof. The proof is exactly the same for Theorem 5, except that in (8), instead of using Lemma 3 we use the fact that for a matrix of rank one has:
|T lop,. S k. ||T|
14


Reviews:
[{"review_id": "rD1DfgezTxB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "SUMMARY\n#######\n\nThe present paper proposes a study of the tradeoff between the number of neurons $k$ and the Lipschitz constant $L$ of a 2-layers neural network $f$ that fits a training dataset, i.e. $f(x_i) = y_i$ for all $(x_i, y_i)$ in the training set.\n\nTo that end, authors consider \"generic datasets\" such that the marginal distributions of the input random vector $X \\in \\mathbb{R}^d$ and the random label $Y$ are the uniform distributions over the $\\mathbb{R}^d$ sphere with radius 1 and the set $\\{-1, +1\\}$ respectively.\n\nAuthors essentially formulate two conjectures (in the following constants are omitted for the sake of simplicity):\n\n(1) If $f$ is a 2-layers NN with $k$ neurons fitting the data, then its Lipschitz constant $L$ satisfies (w.h.p.): $L \\ge \\sqrt{n/k}$.\n\n(2) If $n/d \\le k \\le n$, then there exists an activation function such that w.h.p. there exists a 2-layers NN with this activation function that fits the data and satisfies $L \\le \\sqrt{n/k}$.\n\nThese two conjectures are not formally proved, but studied in restricted settings as follows.\n\nConjecture (2) is first proved in the case $k=1$, and $k=n$. For an intermediate value of $k$, only $L \\le n \\log(d) / k$ is proved. The proof technique builds upon the possibility to separate datapoints into different caps, and then uses the ReLU activation function to impose different values on the different parts of the space.\n\nIf one allows approximate fitting, i.e. $|f(x_i) - y_i| \\le \\epsilon$, then the activation function $t \\mapsto t^p$ allows to construct a 2-layers NN with Lipschitz constant lower than $\\sqrt{n/k}$.\n\nAs for conjecture (1), it is proved for the Lipschitz constant over $\\mathbb{R}^d$ (which is by definition bigger than that over the sphere) in two particular cases: (a) $n=d$, activation function = ReLU, and no biases, and (b) activation function = $t \\mapsto t^p$ and no biases.\n\nTwo synthetic experiments are finally provided.\n\n\n\nOPINION\n#######\n\nAs for positive aspects, I find that:\n- the paper is globally clear and well written\n- the mathematical aspects are thoroughly dealt with\n\n\nHowever, I find this contribution insufficient with respect to the following points:\n\n- my first main concern is about the assumption made on the architecture of the neural network. This 2-layers architecture seems very restrictive, all the more that the second layer is simply linear. Overparametrization is also thought in terms of number of layers, and I doubt that the analysis of shallow models (although they are universal approximators) could be extended to deeper ones in a straightforward fashion.\n\n- my second concern is about the generic dataset assumption. Again, recent understanding on the generalization capacity of neural networks rather consider that inputs are very structured, and actually concentrated on a lower dimensional manifold. Hence, the uniform distribution assumption seems quite far away from this realistic setting.\n\n- I perfectly understand that you have to start somewhere, but the above two limitations make me think that the proposed analysis is hardly transferable to real world interesting frameworks. This is all the more true that even with these assumptions on the architecture and the data distribution, conjectures are only partially validated.\n\n- although the constructions of the data fitting predictors are interesting, Sections 3.1 and 3.2 seem to me a bit superfluous. The constructions could have simply been mentioned in a sketch of proof of Thm 1, the central result of this Section, that incidentally does not match the conjecture. In contrast, the cases $k=1$ and $k=n$ rather appear as curiosities, insufficient to support a conjecture.\n\n- I am not convinced of the relevance of Thm 3. It basically proves nothing as it applies to an upper bound of the Lipschitz constant. This is not a positive contribution supporting conjecture (1), but rather a non-negative side result, from which it is (very) hard to gain intuition on whether the conjecture is true or not. Perhaps a discussion on how tight the first inequality is may help.\n\n- as for Thms 4 et 5, the fact that biases are are not allowed appear to me as another example (with the fact that ReLU is always chosen) to dismiss the non-linearities that might appear in the NN studied. Although I agree it makes the analysis much easier (feasible), this fundamentally breaks with all that is thought to be responsible for the good NN learning capacity, making the subsequent study less convincing.\n\n- this brings me to the next point, which is the comparison to kernel methods. Indeed, many elements in the paper suggest a tight connection with kernel functions, for which the Lipschitz constant is easily computable. Indeed, the reproducing property gives that it is essentially equal to the Lipschitz constant of the feature map multiplied by the RKHS norm of the function. For instance, eq. (1) may be viewed as the standard dual expansion of a kernel function, associated to the kernel $k\\colon (x, y) \\mapsto \\psi(<x, y>)$ (the latter is a valid p.s.d. kernel if $\\psi$ is polynomial, or the limit of polynomials for instance), with support vectors $[w_l, b_l]$, and applied to the point $[x, 1]$. Of course, eq. (1) differs from standard kernel methods in the sense that the support vectors are not the datapoints, but some weights to optimize, in addition to the coefficients $\\alpha_l$. Yet, a comparison might be insightful. I stress that the parallel is even more striking in the function proposed in the proof of Thm 2, where support vectors are datapoints as in standard kernel methods. More generally, considering a potentially very large shallow network reminds the structure of a kernel function, with infinite dimensional feature map. The idea of considering one neuron/support vector per datapoint, as suggested by authors to ensure a $O(1)$ Lipschitz constant is also a key feature of these nonparametric method. Removing biases only makes both models closer, as one does not need to resort to the artificial reparametrization $x' = [x, 1]$ to explicit the similarity. The overall comparison might not be significant for the precise goal pursued by the authors, but so many similarities deserve to be mentioned at least in my opinion. Notice that disjoint caps would be equivalent, with a rbf kernel, to diminish the bandwidth until $k(x,y)$ is globally null when $x \\ne y$.\n\n- the experimental validation is quite rudimentary, and yet duplicated. Fig. 1 is totally redundant with Fig. 3, authors could make better use of the space gained by the deletion of Fig. 1\n\n- a minor comment would be on the clarity of the vocabulary: sometimes authors speak about \"robustness\", sometimes it is \"smoothness\", but finally all is about the Lipschitz function. I feel that sticking with the latter would be less misleading, as very few is said about robustness, apart from that aspect.\n\n- here is a list of things that could be better exposed:\na) it was not clear for me from eq. (2) and the definition of generic samples given in the 1st paragraph of page 2 if the $y_i$ where reals or binary labels.\nb) about generic data, I had to assumed that authors were speaking about marginal distributions when referring to \"with $x_i$ uniform\", this should be better explicited.\nc) more generally, the presentation of the realizations (the $x_i$'s), the underlying random variable, and its distribution was not very neat (e.g. \"where $x_i$ is i.i.d. uniform\" suggests that $x_i$ is the r.v. and not the realization)\nd) in conjecture (2), are the $C$ constants the same for both inequalities? Despite the warning made in the notation paragraph, I found it confusing. The fact that $c$ and not $C$ is used in Sec. 3.1 also\ne) the $\\cdot$ is used for both scalar multiplication and dot product\nf) maybe some references about results on the caps could be helpful\n\n- here is a list of typos:\np.1 make prediction*s*\np.1 do*es* indeed help\np.2 the Euclidean *?*\np.2 whose value*s*\np.2 i*.*i*.*d*.*\np.4 \\sqrt{2}*..*\\|Y\\|\np.4 in other word*s*\np.5 would be *to* use\np.6 missing absolute value for Lipschitzness in the proof of Thm 3\n\n\n\nOVERALL EVALUATION\n################\n\n\nAlthough the subject is of interest, authors only propose partially validated conjectures, building upon assumptions that do not match the framework in which neural networks have been shown to perform well (deep architecture, structured data). Hence, I found the contribution (e.g. Sec. 3.1, 3.2, Thm 3) insufficient to warrant acceptance.\n\n\n\n--- EDIT POST REBUTTAL ---\n\nI thank the authors for their response. I have read other reviews and answers too. I have appreciated the revisions (especially the proof for ReLu with biases). I am still a bit concerned by the applicability due to the assumptions on the architecture/data generation process,  but will not fight acceptance if other reviewers feel strongly about it (I changed my score from 4 to 5 to reflect this position). I understand that authors do not want to present unfinished/ongoing work, but mentioning the parallel with kernel methods (at least as a research direction) would seem fair to me.", "extra_scores": {}, "extra_text": {}}, {"review_id": "X2-7JhX1Cqc", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**: \nIn this article, the authors investigated the fundamental trade-off between the size of a neural network and its robustness (measured by its Lipschitz constant), in the setting of a single-hidden-layer network with $k$ neurons and (approximately) Gaussian data, by proposing two conjectures, Conjecture 1 and 2, on the (lower and upper bound of the) network Lipschitz constant in perfectly fitting a given data set of size $n$ and data dimension $d$. Some weaker versions of the two proposed conjectures were proven, in Section 4 and 3, respectively. Empirical evidence for the proposed conjectures was shown in Section 5.\n\n**Strong points**: This paper proposed a clear and promising mathematical conjecture to investigate the robustness in neural network models, and provided many examples and explanations on why such conjecture is reasonable. The paper is in general well written: the simple examples in Sec 3.1 and 3.2 make a clear sense of the proposed theory, and solid technical contribution is provided in e.g., the proof of Theorem 2.\n\n**Weak points**: This paper is already in pretty good shape.\n\n**Recommendation**: This is a good paper that made solid contributions to the theoretical understanding of the fundamental trade-off between model size and robustness. I recommend it for publication at ICLR.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VweP8F-832k", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This submission studies the relationship between the hidden-layer size of a two-layer neural network and its robustness, that is measured by its Lipschitz constant here. This paper first makes a conjecture that any two-layer neural network with k-neurons and Lipschitz activation functions that perfectly fit the data must have its Lipschitz constant larger than \\sqrt(n/k) (with n being the number of data points and k the number of hidden neurons). An implication of this conjecture is that overparameterization can help improve the network robustness (namely, by making \\sqrt(n/k) with sufficiently large k). Furthermore, a weaker version of this conjecture was proved by replacing the Lipschitz constant with an upper bound on the spectral norm of the weight matrix. The conjecture was further proved for ReLU activation function and polynomial activation function in different data regimes. These theoretical findings were finally evidenced with numerical results. \n\nThis paper proposes interesting ideas and supported them with mathematical proofs, though lacking a bit rigor sometimes. The paper is also sufficiently well-written; at least the main technical ideas are easy to follow, but there are several grammatical errors, some of which are listed below along with several major comments.\n\ni) What kind of robustness of this paper is referring to? against random noise/perturbation in the input data or adversarial attacks? Link between this notion of neural network robustness and the neural network Lipschitz constant is not clear. From what I understand, the results are more like quantifying the stability of the neural network output to random noise (e.g., generated from Gaussian distributions or spherical distributions considered in this paper; rather than robustness against purposefully constructed attacks); see also [Arora et al'2018, Stronger generalization bounds for deep nets via a compression approach] for related study; and please discuss the difference and relationship between this paper and this [Arora et al'2018]. \n\nii) The probabilistic statements could be made more precise in the conjectures. What is deemed random here? What kind of data are generic data? See e.g., [Balan et al'2006, On signal reconstruction without phase] for “generic frame” in the context of phase reconstruction. But not always, generic data are random.  \n\niii) In the proof of Theorem 3, the ||is missing on the left. \n\niv) Both \"two-layers neural networks\" and \"two-layered neural networks\" are used in the paper. Please unify and keep consistent. It seems more grammatically reasonable to use 'two-layer neural network.'\n\nv) The major concern is some of the claims were made after relaxing a number of conditions; e.g., approximate fit rather than exact fit was proved for the two special cases, which is a bit different than the conjectures; as well as how to generalize to more \"generic\" data than the special ones studied. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "3RQ7AJDwCx-", "reviewer": "AnonReviewer3", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper concerns the Lipschitz constant of two-layer neural networks that fit \"generic data sets\" exactly.  A key contribution is the statement of two conjectures relating the number of hidden neurons in the network to the Lipschitz constant.  Roughly, to have $O(1)$ Lipschitz constant, the authors conjecture the number of hidden neurons should be on the order of the input dimension.  In a slogan, over-parameterization is needed for robustness.  Proofs are provided for various special cases, relying on results about real symmetric tensors and uniformly random points on the unit sphere.  Overall, this is a very interesting paper.  My main question surrounds the notion of generic data set that the authors use.  Itemized comments follow.\n\n----------------------------------------------------------------\n\nPage 2, definition of generic data set: Can the authors justify the relevance of fitting to such data sets?  Since the labels $y_i$ are iid uniform on $\\{+1, -1\\}$, one is fitting $f$ to a very unstructured data set in which nearby points x_i on the sphere (or from the Gaussian model) receive different labels.  For such data sets, it somehow does not surprise me so much the fitted function should have a high Lipschitz constant...  If possible, the authors could add intuition on why these data sets may have similar qualitative behavior to more structured data sets.\n\nPage 2, notation: Typo, “where $|| \\cdot ||$ denotes the Euclidean norm.\n\nPage 3, Conjecture 1: Do the authors expect the Lipschitz constant needs to be similarly high if $f$ is only required to approximately fit the data?\n\nPage 3, “Our results around Conjecture 2”: Can the authors comment on what role they imagine the activation $\\psi$ plays?  Suppose I edit Conjecture 2 by fixing nonlinear $\\psi$ satisfying some kind of reasonable conditions.  Should I believe the resulting conjecture?\n\nPage 4, typo: double dot just before “This concludes the proof sketch of Conjecture 2…”\n\nPages 10-11, Appendix A, Lemma 2: I believe the precise result is that for $d \\geq 5$ it suffices to take $k$ at least $\\frac{2}{d} \\binom{d+p-1}{p}$.  This is by Alexander-Hirschowitz and the result relating the maximum real rank in Blekherman, Grigoriy, and Zach Teitler. \"On maximum, typical and generic ranks.\" Mathematische Annalen 362.3-4 (2015): 1021-1031.\n\nPage 8, proxy for Lipschitz constant: Can the authors prove the “maximum random gradient” is close to the true Lipschitz with high probability for $T$ such as $1000$?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the Lipschitz properties of neural networks — in particular, two layer neural networks that interpolate generic datasets. It conjectures a “size robustness tradeoff”: in this setting, the number of neurons required to interpolate with an O(1)-Lipschitz function is proportional to the number of data points n, while the number of neurons required for interpolation alone is proportional to n/d, where d is the data dimension. More precisely, the conjecture is that the best achievable Lipschitz constant is proportional to $\sqrt{n/k}$, where $k$ is the number of neurons. The paper proves weaker versions of both sides of this conjecture: it proves that a spectral upper bound on the Lipschitz constant is lower bounded by $\sqrt{n/k}$ and that there exist networks achieving this Lipschitz constant when $k ~ n/d$ and $k ~n$. The paper also provides experiments supporting its claims, with the caveat that the actual Lipschitz constant is a worst-case quantity that cannot be directly observed. 

Pros and cons:

[+] The paper identifies a novel (conjectured) phenomenon involving the dependence of the Lipschitz constant of an interpolating network on the degree of overparameterization. In words, Lipschitz interpolation requires significantly more neurons than mere interpolation. This observation seems likely to stimulate future work. 

[+] The paper provides relatively simple and rigorous proofs of simplified versions of its conjectures (both upper and lower bounds on the achievable Lipschitz constant). 

[+] The exposition is technically clean, and the paper is clear on the limitations of its analyses. 

[-] The setting of the paper’s analysis seems somewhat mismatched with the practice of deep learning. The data are assumed to be generic, where neural networks excel in fitting structured data. Several reviewers noted this mismatch and raised concerns about whether this conjectured/proved tradeoff on generic data carries over to structured datasets. 

[-] A technical limitation is the shallowness of the network: controlling the Lipschitz properties of deep networks is much more challenging at a technical level, because one needs to argue that for the worst input, features propagate in a “generic” fashion. It is technically challenging to avoid exponential dependence on depth. 

[-] The paper obtains only partial progress towards proving its conjectures — for example, it shows that it is possible to interpolate with a Lipschitz constant of $n \log n / k$, where the conjectured bound is $\sqrt{n/k}$. 

[-] Comparing to kernel methods would help to better contextualize the results, since in a similar setting, kernel methods could also potentially be analyzed via localization arguments. 

Overall, the paper conjectures a novel phenomenon around size/robustness tradeoffs in interpolating neural networks. While the paper's conjectures have the potential to stimulate further empirical and theoretical work, the reviewers (in particular R1 and R2) note a number of significant limitations to the paper’s analysis. In light of these issues, the paper falls below the par for acceptance. 
Decision: Reject