Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization
Authors: Simone Bombari
Mohammad Hossein Amani
Marco Mondelli
Venue: NeurIPS 2022 Accept (2022)
Keywords: deep neural networks
Neural Tangent Kernel
minimum over-parameterization
memorization capacity
gradient descent training

Abstract: The Neural Tangent Kernel (NTK) has emerged as a powerful tool to provide memorization, optimization and generalization guarantees in deep neural networks. A line of work has studied the NTK spectrum for two-layer and deep networks with at least a layer with $\Omega(N)$ neurons, $N$ being the number of training samples. Furthermore, there is increasing evidence suggesting that deep networks with sub-linear layer widths are powerful memorizers and optimizers, as long as the number of parameters exceeds the number of samples. Thus, a natural open question is whether the NTK is well conditioned in such a challenging sub-linear setup. In this paper, we answer this question in the affirmative. Our key technical contribution is a lower bound on the smallest NTK eigenvalue for deep networks with the minimum possible over-parameterization: up to logarithmic factors, the number of parameters is $\Omega(N)$ and, hence, the number of neurons is as little as $\Omega(\sqrt{N})$. To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training.

Memorization and Optimization in Deep Neural
Networks with Minimum Over-parameteriiation
Simone Bombari', Mohammad Hossein Amani", Marco Mondelli.
Abstract
The Neural Tangent Kernel (NTK) has emerged as powerful tool to provide memorization, optimization and generalization guarantees deep neural networks. A line of work has studied the NTK spectrum for two-layer and deep networks with at least a layer with (2N neurons, N being the number of training samples. Furthermore, there is increasing evidence suggesting that deep networks with sub- linear layer widths are powerful memorizers and optimizers, as long as the number of parameters exceeds the number of samples. Thus, natural open question is whether the NTK is well conditioned in such a challenging sub-linear setup. In this paper, answer this question in the affirmative. Our key technical contribution is a lower bound on the smallest NTK eigenvalue for deep networks with the minimum possible over-parameterizaaion::: up logarithmic factors, the number of parameters is (2NN) and, hence, the number of neurons is little as S!( D(VN). To showcase the applicability of our NTK bounds, we provide two results concerning memorization capacity and optimization guarantees for gradient descent training.
Introduction
Training neural network is a non-convex problem that exhibits disconnected local minima g 57
70
Yet, in practice gradient descent (GD) and variants routinely find solutions with zero training loss [72). A framework to understand this phenomenon comes from the Neural Tangent Kernel (NTK). This quantity was introduced in [33]. where it was proved that, during GD training, the network follows the kernel gradient of the functional cost with respect to the NTK. Furthermore, as the layer widths go large, the NTK converges to a deterministic limit which stays constant during training. Hence, in this infinite-width limit, it suffices that the smallest eigenvalue of the NTK is bounded away from 0 for gradient descent to reach zero loss. Going to finite widths, a recipe to prove GD convergence can be summarized as follows: show that (i) the NTK is well conditioned at initialization. and (ii) the NTK has not changed significantly by the time GD has reached zero loss (see e.g. 49 17 11). A number of papers have exploited this recipe for networks with progressively smaller over- :rarreertmtriiiii two-layer networks 22 550 63 69 62), deep networks with polynomially wide layers (5) 21 (74), and deep networks with a single wide layer 47 43). Besides optimization, showing that the NTK is well conditioned directly implies a result on memorization capacity [4] 48)
and the smallest eigenvalue of the NTK has also been related to generalization [6]
In [8 it is shown that, given N training samples, single layer with ((N) neurons suffices for the NTK be well conditioned in networks of arbitrary depth. However, there increasing evidence that, in the challenging setup in which the layer widths are sub-linear in N, neural networks still memorize the training data 14 7I 66). reach zero loss under GD training the two-layer setting
66 50 42, and in the deep case, GD explores nicely behaved region of the loss landscape [4]].
This is agreement with simple back-of-the the-envelope calculations on CIFAR-10 and ImageNet: CIFAR-10 has N 50000 images and roughly 106 parameters suffice to fit random labels [2]];
"Institute of Science and Technology marco. sorroo.ondeelleeist.. ac.
Austria
(ISTA).
Emails:
{simone bombari,
TEPFL, Switzerland. Email: mh. amani 19988gma11.com
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

furthermore, in order to fit random labels to subset of 1.2 10 ImageNet data points, 2.4- 10? parameters are enough [72]. These numbers suggest that having number of parameters of the same order as the dataset size is much closer to practice than having a number of neurons of that order. We also note that, by counting degrees of freedom or bounding the VC dimension [10], (2(N) parameters (and, therefore, ()(NN) neurons) are in general necessary to fit N data points. This naturally brings forward the following open question:
Is the NTK well conditioned for deep networks with the minimum possible over-parameterization (i.e., containing S2(N) parameters corresponding to N) neurons)?
Main contributions. In this paper, settle this open question for large class of deep networks. We consider (i) a smooth activation function, (ii) i.i.d. data satisfying Lipschitz concentration (e.g.. data with Gaussian distribution, uniform the sphere/hypercube, Adversarial Network), (iii) a standard initialization of the weights (e.g., He's ' or LeCun's 's initialization), and (iv) loose pyramidal topology in which the layer widths can increase by at most multiplicative constant as the network gets deep. Then, in Theorem [3.] we show that the NTK is well conditioned under the mininum possible wver-parameterization requirement: the number of parameters between the last two layers has to be (2()) or, equivalently, the number of neurons has be (( where i includes extra logarithmic factors. We achieve this goal by giving lower bound on the smallest eigenvalue of the NTK. This lower bound is tight when all the layer widths are of the same order.
obtained via Generative
Our NTK bounds open the way towards understanding the behavior of deep networks with minimum over- weer-parameterization. In particular, an immediate consequence of the fact that the NTK is well conditioned is a result on the memorization capacity (Corollary 4.1). Furthermore, by suitably choosing the initialization, 4.2). Finally, we highlight that, in order to obtain our bounds on the smallest NTK eigenvalue, we give number of tight estimates on the & norms of feature vectors and of their centered counterparts, which may be of independent interest.
provide convergence guarantees for gradient descent training (Theorem
Proof ideas. To prove Theorem 3.1 restrict to the kernel K1-2= where J is the Jacobian of the output w.r.t. the parameters between the last two hidden layers. This suffices as Kz-2 2 is lower bound on the NTK in the positive semi-definite (PSD) sense. We note that the i-th row (i E
of JL-2 is given by the Kronecker product @ between the feature vector at layer L 2 and the backpropagation term from the same layer. One key technical hurdle is to center Jr so that its rows have the form u & V - E [u 3 vj. where E[u] = B[c] = O, and all expectations are taken with respect to the (random) training data. To do so, we perform three steps of centering: (i) we center the feature vectors (corresponding to u). (ūi) we center the backpropagation terms (corresponding to v), and (iii) we center again the whole row (corresponding centering steps are approximate in the sense that the centered matrix is not necessarily a lower bound (in the PSD sense) on the original one. However, we are able to control the operator norm of the difference, and show that it scales slower than the smallest eigenvalue of the centered kernel. At this point, we leverage the structure of the rows of the centered Jacobian to bound their sub-exponential norm via a version of the Hanson- Hanson-Wright inequality for (weakly) correlated random vectors [[]. Finally, after providing also tight estimate on the E2 norms of such rows, we can exploit a result from (2 to lower bound the smallest singular value of a matrix whose rows are independent random vectors with well controlled sub-exponential and & norms.
@ v). These
Existing work bounds the smallest NTK eigenvalue for networks with two layers 61 42 or deep networks with a layer containing ( neurons [48). In particular, [61] also exploits the results 1 However, the centering of the Jacobian is achieved via a combination of whitening and dropping rows, which appears to be difficult to generalize to deep networks. In contrast, the 3-step centering we described above applies in 42), and it is based on a decomposition of the kernel via spherical harmonics. This technique allows to obtain the exact limit of the smallest NTK eigenvalue, it has been used to analyze random feature models [26 41 25 40 and to obtain generalization bounds for two-layer networks (see again (42). However, understanding how to carry out such a decomposition in the multi-layer setup is an open problem. Finally, (48 considers the deep case, and it relates the smallest eigenvalue of the NTK to the smallest singular value of a feature matrix. As feature matrices are full rank only when the number of neurons is ((N), this approach is inherently limited to networks with lincar- layer.
networks of arbitrary depth L. A different approach is put forward
2

---

The rest of the paper is organized as follows: Section D discusses the problem setup and our model assumptions; Section pressnts our main result on the smallest NTK eigenvalue and gives a roadmap of the argument; Section provides two applications of our NTK bounds: memorization capacity and gradient descent training: Section [ discusses additional related work, and Section 6 provides some concluding remarks. The details of the proofs are deferred to the appendices.
2 Preliminaries
Neural network setup. We consider I--layer neural network with feature maps fi TRd R defined for every z E Ra as
I; o(W, ft-1),
[ = 0, I EE [L 1}, =
[(xx)
WI fL-1,
Here, Wi E - is the weight matrix at layer I, á is the activation function and, given an integer n, we use the shorthand [n] = {l....,,7] n.. We assume that the network has a sin- gle output, Lec. n,
and Wy p and for consistency we have no d. Let gi R + R be the pre-activation feature map so that fi(z) = ((g(())) for / E [4]. We de- fine 90(x) fo())
Nxd be the data matrix containing N samples in Fd 0 = [vec(W1), ..... (WL] be the vector of the parameters of the network, and (0) [fz (..)..... f2 (xx) ] be the network output. We denote by J the Jacobian of Fz with respect to all the parameters of the network:
x. Let X
[rI.....,TN"
OF,, J @vec(W,))
OF, ① vec (L))
E
76-17
(2)
Our key object of interest the empirical Neural Tangent Kernel (NTK) Gram matrix, denoted by K RVVx & and defined as:
OFL O vec( 1=1
OFL i vec (Wi)
K= == =
(3)
In 333, it shown that, 74 do for all / E 1L-11, 1]. K converges to deterministic limit, which stays constant during gradient descent training. The focus of this paper is on the finite-width behavior of the empirical NTK (3). Quantitative bounds for the NTK convergence rate can be obtained from 17 [5). However, these bounds lead to a significant overpparamtterization requirement, see the discussion at the end of Section in [48. Here, our main result consists in showing that the NTK is well conditioned for class of neural networks with the minimum possible nheepparamttrrizatinn ie., ((N) parameter or, equivalently, ((VN) neurons.
Weight and data distribution. We consider the following initialization of the weight matrices: (Wi)a,) Mi.d (0, B8 /m)-1) for I E [T. - 1]. E [n--1]; J E [mi]. where 3r is numerical constant independent of the layer widths. This covers the popular cases of He's and LeCun's initialization 27 30 36). For the last layer, we assume that (WL); -iid N/O0, 88) for i E [RL--]] Throughout the paper, we let (II,...,,NN) be i.idd samples from the data distribution Px, which satisfies the conditions below.
Assumption 2.1 (Data scaling). The data distribution Px satisfies the following properties:
1. / ||||| dx)(x) @(va).
2. f || dPx Odd)
3. f f x'''f''p (P) (Px())
Assumption 2.2 (Lipschitz concentration). The data distribution Px satisfies the Lipschitz con- centration property. Namely, there exists an absolute constant e >> 0 such that, for every Lipschitz continuous function vp Rdd R. we have [X)) < +00, and for all >
IP p(x)) - (l(x ((x'))x)()')) 2t) 2e -d- -d2/111
3

---

Assumption 2.1 is simply a scaling of the training data points and their centered counterparts. Assumption 2.2 covers number of important cases, e-g., standard Gaussian distribution [65]. uniform distributions on the sphere and on the unit (binary or continuous) hypercube (65 data produced via a Generative Adversarial Network (GAN [5], and more generally any distribution satisfying the log-Sobolev inequality with Assumption 2.2 is rather common in the related literature [48), or it even replaced by a stronger requirement (e.g., Gaussian distribution or uniform on the sphere) (4).
constant. We also remark that
Assumption 2.3 (Activation function). The activation function & satisfies the following properties:
1. o is a non-linear (and therefore also non-conee con-constant) M LLisscchta,auccitiin
2. its derivative ø' is M' -Luxschittffuncion;
These requirements satisfied by common activations, e.g. smoothed ReLUU, sigmoid, or tanh.
Assumption 2.4 (Network topology). The network satisfies a loose pyramidal topology condition,
i.e. Rı O (m-1). for all [L- 1].
strict pyramidal topology (namely, innreeeresinn layer widths) has been considered in prior work concerning the loss landscape [45] [6] and gradient descent training [4]]. Our Assumption 2.4 requires loose pyramidal topology the sense that, as we go deep. the layer widths are allowed to
increase by constant multiplicative factor. We also note that the widths of neural networks used in
practice are often large in the first layers and then start decreasing 28 60
Assumption 2.5 ovverpprrameterization) We have that
N llog' N = ((11.2271111)
(4)
Furthermore, there exists > such that
N O (ML-1))
(5)
Condition 4 requires the number of parameters between the last two hidden layers to be linear in the number of samples, up to logarithmic factors. This represents our key over-parameteriation condition. When all the widths have the same scaling, 44) reduces to N ö( d(d²). This is satisfied by several "standard" datasets, such as MNIST (N = 60000, d = 784), CIFAR- 10 (N = 5 10 d == 3- 3-3?), and ImageNet (N 1.4 10", d d= 2 10"). We also note that, if N > d, the NTK low-rank and Amin (K) = O. Furthermore, Corollary 4.1 and Theorem 4.2 cannot generally hold when N >> d², as there
data points to fit than parameters to help with the fitting. A milder requirement is possible for classification tasks, see the discussion at the end of Section 5 The second condition (5) is rather mild, as y can be taken be arbitrarily small, and it avoids exponential bottleneck in the last hidden layer.
E R-Nx and Ex(x) diag(Iø' (ي)(()))) for 1 E [L- 1]. where (1,(()) is the pre-activation neuron. Given two matrices F,B Rmxn, we denote by Fo B their Hadamard product, and by F ()),, )r E mm=xn their row-wise Kronecker product (also known as Khatri-Rao product). Given a random vector let [|elly and ||ا|| denote its lub-Gaussian and sub- sub-exponential norm, respectively (see also Appendix Afr a detailed definition). Given a matrix A, let ||All.op be its operator norm, || its Frobenius norm, Amin (A) its smallest eigenvalue, and miin (A) its smallest singular value. We denote by l1ll the Lipschitz constant of the function s. All the complexity notations 9(-), O(-), of-) and (-)) are understood for sufficiently large N, d, d,,, 712, n1,71, symbols are meant to neglect logarithmic factors.
Notation.
The feature matrix at layer I F. =
-1- Tildes such
3 NTK Bounds with Minimum Over-parameterization
Our main technical contribution on the smallest eigenvalue of the empirical NTK 3 is stated below.
Theorem 3.1 (Smallest NTK eigenvalue under minimum over peeepaarameterization), Consider an L- layer nearal network (T) where the activation funnction satisfies Assumption [2.3and the layer widths
satissy Assumptions 2.4 and 2.5 Let { "Lidd. Px, where Px satisfies the Assumptions 2.1 2.2
By applying Lipschitz map to standard Gaussian distribution, the map output satisfies Assumption 2.2

---

and let K be the empirical NTK Gram matrix (3. Assume that the weights of the network are
initialized as (Wi)as Lidd (0, Si mm) for L 11, i [nt-1] [nd] and (W1). M.add
NO (8) for E [nL-1]. Then, we have
Amin (K) ((15--21-11),
(6)
with probability least CNe-llos and C are numerical constants. Moreover, we have that
Ce-elon² N over (at)) and (W&)k= where c
Amin (K) = O (dnL-1)) with probability at least 1 1---Cee---- over (zi) and (Wi)kmr
(7)
This result implies that the NTK is well conditioned for class of networks in which the number of parameters R--2"L-1 between the last two hidden layers is linear in the number of data samples N, up to logarithmic factors. This means that the total number of neurons of the network be little as Q2( (VN), which meets the minimum pos- sible amount of pverpparameterizzaionn The lower bound (6) and the upper bound 7 match when all the widths (up to layer L - 2) have the same scaling, i.e., d = (m,-2)). Throughout the paper, we do not explicitly track the depen- dence of our bounds on L, in the sense that the numerical constants c, C may depend on
N
1000
100
2000
3000
75
25
0.0
0.2
0.4
0.6
0.8
1.0
d2
1e6
Figure Amin (K) as function of d2 in a 3-layer neural network, with sigmoid activation and d m n2-
In Figure | we consider a 3-layer neural network with function of d², for three different values of N. The inputs are sampled from standard Gaussian distribution, the tivation function is the sigmoid (xx) = (1 + e-*)-1, and we set 3 = for all E [Z]. We repeat the experiment 10 times, and report average and confidence interval I standard deviation. The linear scaling of Amin (K) in d² is in agreement with the result of Theorem (and Figure as well) is available bombari/smallstt... htsss/maallllaaaeeeeeeeeeeeaaesm eigenvaleeenveeeeeeeeeee NTK/
d 72 12.. and plot Amin (K')
3.1 The code used to obtain the results of Figure [
https://gi thub. com/ hom/simma simone- bombari/
3.1 Roadmap of the proof of Theorem 3.1
After an application of the chain rule and some standard manipulations, we have
JJ
Kk
with K₁ = F&FT BR+1 E ERNN
(8)
k==
where B3 E RN Xnm is matrix whose i-th row is given by
(x)) (IT wiEr(z)) WT,
k E [. 2], k L - 1,
(Bx);: (2:
(9)
L.
one readily obtains that K > KL-2, since K₃ is PSD for all h L - 1}. Hence, it suffices to prove a lower bound on Amin (). We denote by Jr,-2 the Jacobian obtained by computing the gradient only over the parameters between layer L L-3 2 and layer L-1. 1. Then, Kr.-2 = Jr Jr.-2J ___, and, by using
From the decomposition (8)
(8) and (9), the i-th row of Jr.22 can be expressed as
(Jr-2)s: (x:)) (Di.'' (WI-1f1-2(1))
(10)
where Dr, is a diagonal matrix with the entries of Wz its diagonal. Note that, if we fix the weight matrices (Wi) the rows ((Jr-2) are i.i.d., as the training data (x:) are i.i.d. too.
The proof consists of two main parts. First, we construct centered Jacobian Jr.-2, which obtained from Jr.-2 by iteratively removing expectations with respect to X to its parts, and we show that smallest singular value close to the smallest singular value of Jr-22 2- The details of this part contained in Appendix D Second, we bound the smallest eigenvalue of the kernel obtained from
5

---

the centered Jacobian J2- by providing an accurate estimate of the lz and sub-suuouneeee eabb-expoentill norms of its rows. The details of this part are contained in Appendix E In order to earry out this program, we ex- ploit number of concentration results on the l2 norms of feature and backpropagation vectors, and on the lg norms of their centered counterparts. These results are contained Appendix and they could be of independent interest. In particular, we provide tight tigh-probabilityy estimates on (i) (z))l=-
(ii) E. (z))) 21. (iit) E (1))(())))l2 (tv) (z)) E [f(())]1 E. [l..f())) E. [fi (z)]]l 2). and (z) - E. [z)(2 and (v) [| D' (g)-1(z)) - E [ (x)]l2) Some preliminary calcu-
lations are also contained in Appendix B
Part 1: Centering,
We consider the centered Jacobian Jr.-2, whose i-th row is defined as
(JL-2):: = - @ (D):()1-11:)))) - Ezz [ (xx) @ Dr
i E [M]
(11)
where fL-2(1;) م(و6-2 (2:)), with ((9)-2(x;))
((1L-2(2;)) Ex, (x;1__2(xx) and
ő (y(rr-1 (2:)) = d'((n-1(xx)) Ez, 1d' (gr. (x))) being the centered versions of the activation func- tion and of its derivative, respectively. Our strategy is to relate Amin ( (J 2 to Amin (J2-2 2) via the following two steps.
Step (a): Centering Fr. and B We show that Amin 2m > Amin (Jrn(FF
o(LL-27L-1), where JFBJFB = FL FT o BL-1BT_ 1_1 and FL-2 = Ex and BL-1
Ex[BB_ (Lemma D.1 in Appendix D.I.. Our strategy differs from existing work (e.g.. 48). where either only the backpropagation term is centered (cf. Proposition 7.1 of [6]) or only the features are centered (cf. Lemma 5.4 of (88) ). We remark that, in order to handle deep networks with minimum overparameterizatiorff the centering of Fi.-2 and B is crucially performed the same time, In fact, by doing so, certain terms containing an eigenvalue which is negative and large in modulus suitably cancel. As result, the difference between the original kernel Jr. J and the centered one JFBJEB is o(nL-2nL-1))
FB can be bounded by a matrix whose operator norm
Step (b): Centering everything, We show that Amin (JFBJFE) 2 Amin
where the rows of Jr are given by (11) (Lemma D.2 in Appendix D.2p. The idea is to decompose the difference JFB J1-2 L-2 into rank-1 matrix plus a PSD matrix. Then, in order to bound the operator norm of the rank-1 I term, we leverage the general version of the Hanson- Hanson-Wright inequality given by Theorem 2.3 in [ (see the tail bound on quadratic forms that we provide in Lemma B.5). This strategy avoids whitening and dropping rows (as done in 61) and, hence, appears to be better suited the deep case.
The main result of this part is stated below, and it is proved by combining Lemmas D. and D.2
Theorem 3.2 (Jacobian centering). Consider the setting of Theorem 3.7 and let the rows of Jr.-2 and J 2 be given by (10) and [II, respectively. Then, we have
Amin (Jr.-2J1-22 2 Amin (J o(11.2271-11)
(12)
with probability at least 1 - C Cexp(-clog' nL-1) - Cexp(-clog' N) over (ax) and (Wx) k where c, C are numerical constants.
we fix the weight matrices (Wi) the rows of Jr.-2 are i.i.d. vectors of the form u & v E lu @ v). where both u and e are centered. By exploiting this structure, in Appendix E. we bound the l22 and sub-exponential norms of these rows. The l2 norm is bounded in Lemma E.2 and this result relies on the tight estimates on the & norms of centered features and centered backpropagttion terms given by Lemma C.4 and C.5 respectively. The sub-exponential norm is bounded in Lemma E.33 and we use again the tail bound of Lemma B.5 which exploits the version of the Hanson- Manson-Wrightt Wright inequality in [I]. At this point, the problem is reduced to bounding the smallest eigenvalue of a matrix such that its rows are i.i.d. and we have a good control on their lg and sub-exponential norms. This goal can be achieved via the following
Part 2: Bounding the centered Jacobian.
'In contrast,
61 considers shallow networks, and 48 requires the existence of a layer with roughly (((N))
neurons.

---

result, whose proof follows from Theorem 3.2 in (2 and it is presented for completeness in Appendix
Proposition 3.3. Let J be a matrix with rows Jr: E -R= for E [N]. Assume that {Jx: [EGNN independent expoonxpoettaal random vectors with vb max; || 21 Let Mmii min; || and Mmax max; [|:1l12 Set { K/KK K', and A = (1L-10222)))))) Then, we have that
Amin (JJT)
2 M
(13)
holds with probability at least
1 1-exp (-cKVN
log log 2n 2
)) (Amar 2 K' (V..-111-2))
(14)
N
where с and C are numerical constants.
The main result of this part is stated below, and it is proved in Appendix E.3
Theorem 3.4 (Bounding the centered Jacobian). Consider the setting of Theorem 3.1 and let the rows of JL-2 be given by Then, we have
Amin (Ja-2J[-2) 11(11-271111
(15)
with probability at least 1 - Ce evN CNe-ollo' RI--1 over (z:)i=m and (W&)k= where and C' are numerical constants.
Amin (KL-2) Amin (JL-2J bound (6) follows by combining the results from Theorem 3.2 and Theorem 3.4
Recall that K > KL-2, hence Amin (K) 2
Thus, the lower
Finally, the upper bound 7 is rather straightforward. First, we write
Ami (K) Amin (JJT) S (JJ
11
(16)
Then, by combining the bound on [( of Lemma C.1 with direct calculation for |1(B++1)::13
the desired result follows. The details are contained Appendix F
Two Applications: Memorization and Optimization
Memorization capacity. The fact that the NTK Gram matrix (3) is well conditioned readily implies result on memorization capacity. This was already observed in 42 for two-layer networks and in [48] for deep networks with a layer containing S2(NV neurons. Here, by using Theorem 3.1 we show that Q(N) parameters between the last pair of hidden layers enough for the network to fit N real-valued labels up to an arbitrarily small error. The result is stated below and, for completeness, we give the proof in Appendix G
Corollary 4.1 (Memorization). Consider an L-layer neural network I where the activation
satisfies Assumption 2.3 and the layer widths satisfy Assumptions 2.4 2.4and22. 2.5 Let {xr) Ws..d. Px. where Px satisfies the Assumptions 2.1 2.2 Then, it holds that for every Y E IRN, and for every e > 0, there exists set of parameters 0 such that
[[))(0) V112 Se,
(17)
with probability at least 1 - C Ne Ne-oloo" ny Ce-clog n over (xx) where and C are numerical constants.
Gradient descent training. Theorem 3.1 has implications the convergence of gradient descent algorithms. In particular, by choosing carefully the initialization, we show that gradient descent trained the N samples { with labels Y (Yi...., YN) converges to loss. This at the best of our knowledge the first result of this kind for deep networks with minimum over-parameeeriizatio..
To define our initialization, let us assume that the (T. 1)-th layer has an even number of neurons. With slight abuse of notation, we indicate its width 2nt-1. Thus, Wi-1 can be written in the
7

---

form
wh 1-1 [-1
w
where W W E - Similarly, WL - is the concate-
nation of WL W(
E ERLL1 Then, define the initialization 8g voc. (..o))
as follows:
(Wiolay Midd (0, l [L -0--), 2], E [m--1], j e [ma], (W MLLd. (N0, /100 e [nt-2], j E [mz-i]. and W L-1,0 --1100 (18)
(W2,)) Miid. ((0,82n), i [mz-1], and w ( L,
As usual, (1 are numerical constants independent of the layer widths. In contrast, the quantity
will be set to a suitably large value depending on the number of training samples and on the layer
widths. In words, the initialization is standard for Wi,0.... WL-200 and w((l) L-1,0: the variance of
W is boosted up by factor y and we duplicate the neurons of layer L, 1 so that W(2)
L-1,0
w 1-110 and ( 1.0 - F,0 At this point, we are ready to state optimization result.
Theorem 4.2 (Optimization via gradient descent), Consider an L-layer neural network the uctivation function satisfies Assumption 3,3d the layer widths satisfy Assumptions 2.4 2.4and 2.5
(1) where
Consider training data (= "ii.d. Px, where Px satisfies the Assumptions 2. 2.2 with labels
Y E RN such that || (VVN). We consider solving the
optimization problem
1
ming ((0) mino [[F -Y112
(19)
by running gradient descent updates of the form d 0, 17 ((.)). where the initialization 0g is defined in (18) with 7 = di and 1 S Cn
Then, for all
((,,) S - [(00),
(20)
with probability at least 1 - C Ne-clog where e and C are numerical constants.
elog nc-1 Ce-clog" n over (I:) and the initialization Pg.
In words, (00 guarantees that gradient descent linearly converges a point with zero loss. We also note that (our upper bound on) the convergence rate can be expressed as a simple function of the learning rate 7,, the number of training samples N, and the layer widths (m))
8800
4
-6
we give an illustrative example that 4-layer networks achieve loss when the number of parameters at least linear in the number of training samples, i.e., under minimum over-parannn wverparameeerizztionn To ease the experimental setup, we use ReLU activation, with Adam optimizer. We initialize the network as in the setting of Theorem 3.1 picking 3 = for all E [L]. The inputs, as well as the targets, are sampled from standard Gaussian distribu- tion. The plot is averaged over 10 independent trials. As predicted by Theorem 4.2 the loss experiences a phase transition and it goes from to when the layer widths are of order VN.
In Figure 2
4800
10
400
400
5400
10400
d²
Figure 2: Value of the loss L(0y) once gradient descent has converged for a 4- layer ReLU network with d n2 = ng.
We now provide a sketch of the argument of Theorem 4.2 deferring the detailed proof to Appendix H As the NTK is well conditioned at the initialization dg. which implies that gradient descent makes progress at the beginning. The idea is that the NTK remains sufficiently well conditioned also during training and, hence, the loss vanishes with the linear rate in (20). since the trained weights remain confined in ball of sufficiently small radius centered at 0g. More specifically, we exploit the optimization framework developed in 44).. There, convergence result proved if the following condition holds: there exists a, 3 such that
consequence of Theorem 3.1
a
S Jmin (J(0)) < (0) - B, and [|](0,) (02)ll - 2.3'
(21)

---

for all 0, 01. 02.00 E = -B R), where D denotes a ball centered at d of radius : ;- (l.))
Y|12/a (cf. Proposition H.I. In order control the radius R, we take advantage of the form (18) of the initialization dn- in particular, the spectrum of the Jacobian J (and, hence, a) scales linearly in v7. and the network output at initialization (2(()) equal to (cf. Lemma H.2). Thus, as ||Y|| = N(vN), we have that R = D(VN/a)) which can be controlled by choosing suitably y: At this point, the argument consists in providing number of estimates on feature vectors, backpropagation terms, and finally the Jacobian J()) for all o E 'D (cf. Lemmas H.3H. This allows us to find a, 8 such that (2T) holds and conclude.
5 Related Work and Discussion
Random matrices in deep learning. The limiting spectra of several random matrices related to neural networks have been the subject of a recent line of work. In particular, the Conjugate Kernel (CK) - namely, the Gram matrix of the features from the last hidden layer has been studied for models with two layers [54] 37 39, [1], with a bias term
3 56], and with multiple layers [3]. The
Hessian matrix has been considered in [52], and the closely related Fisher information matrix in (55)
Using tools from free probability, the input-output Jacobian (as opposed to the parameter-output
Jacobian considered in this work) of deep networks is studied in [53] and the NTK of two-layer model in [4. In (23) the spectrum of NTK and CK for deep networks is characterized via an iterated Murchenko-Pasture map. The generalization error has also been studied via the spectrum of suitable random matrices, see [29] 38 (42) and Section 6 of the review [II]. Most of the existing results focus on the linear-wide asymptotic regime, where the widths of the various layers are linearly proportional. An exception is 688 which focuses on the ultra- wide two-layer case (n1 > N).
Smallest eigenvalue of empirical kernels. In the line of work mentioned above, the limiting spectrum of the random matrix is characterized in terms of weak convergence, which does not lead to a direct implication on the behavior of its smallest eigenvalue. In fact, lower bounding the smallest eigenvalue often requires understanding the speed of convergence to the limit spectrum. Quantitative bounds for random Fourier features are obtained in (9]. In the two-layer setting, the smallest NTK and concentration bounds can also be obtained from 163 31 In particular, 42) establishes a tight bound for two-layer networks with roughly as many parameters as training samples (hence, under minimum over-oaramnn puee-prrameterizztionn and for a wide class of activations. However, this result still requires that n1 = (dd). For deep networks. a convergence rate on the NTK can be obtained from 7 and potentially from (15), however these results require all the layers to be wide. In [48). it is proved that a single layer of linear width suffices for the NTK to be well conditioned. Here, Theorem 3.1 provides the first result for deep networks under minimum over- parreeeerrattiiinnn therefore allowing for sub-linear layer widths.
eigenvalue is lower bounded in 61 42 68
Memorization capacity and gradient descent training. For binary classification, the memo- rization capacity of neural networks was first studied by Cover [18], who solved the single-neuron case. Later, Baum [22 proved that, for two-layer networks, the memorization capacity is lower bounded by the number of parameters, and upper bounds of the same order were given in 35
58
Recently, tight results for two-layer networks in the regression setting have been provided 14
In particular, [14] generalizes the construction of [12), while the memorization result of 42 comes
from bound on the smallest NTK eigenvalue. This same route is also followed to analyze deep
networks in [48) and in this work. Results for multiple layers have been provided in [10 71 66 24
As concerns efficient algorithms achieving memorization. 19 20 study classification with two-layer networks. popular line of research has exploited the NTK view give optimization guarantees
on gradient descent. Existing work has focused on the two-layer case [6
22
50
63
69 62]. and
optimal results in terms of over over- parammmttttrinnnoonnnn have been obtained 442 For deep networks, [2]
assumes lower bound on the smallest NTK eigenvalue, [5] 73. 74 require all the layer widths to be
reduce the over-parameterization to single layer of linear width. In particular, in these last two papers, the analysis of the NTK is
(rather large) polynomials in the number of samples, and [7
reduced to that of a certain feature matrix (the first one 47 and the last one 43 ). Hence, these approaches do not seem suitable to tackle networks with sub-linear layer width Finally, we remark that milder over poer-paamerization requirements are sufficient for classification problems. More specifically, it has been proved that polylogarithmic width suffices for two-layer 33 and deep [16]
'If' the width is linear, then the feature matrix is low-rank and, hence, its smallest eigenvalue is 0.

---

ReLU networks to converge and generalize. In fact, achieving memorization for regression is harder than for classification, where suffices to satisfy inequality constraints 42
Concluding Remarks
In this paper, we show that the NTK is well conditioned for deep networks with sub-linear layer widths. As consequences of our NTK bounds, we also prove results on memorization and optimization for such a class of networks. Our approach requires smooth activations and layer widths which do not significantly grow in size with the depth. We believe such assumptions to be purely technical, and we leave as an open question their removal. Our novel NTK analysis could potentially be applied beyond standard gradient descent, e.g., for optimization with momentum [67]. or federated learning (32).
Acknowledgements
The authors were partially supported by the 2019 Lopez-Loreta prize, and they would like to thank Quynh Nguyen, Mahdi Soltanolkotabi and Adel Javanmard for helpful discussions.
References
[1] Radoslaw Adamczak. A note on the Hanson Wright inequality for random vectors with dependencies. Electronic Communications in Probability, 20:1-13, 2015.
[2] Radoslaw Adamczak, Alexander E Litvak, Alain Pajor, and Nicole Tomezak- Janezaa-Jaegermann. Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling. Constructive Approximation, 34(1):61-88) 1888, 2011.
[3] Ben Adlam, Jake Levinson, and Jeffrey Pennington. random matrix perspective on mixtures of nonlincarities for deep learning, 2019. arXiv: 191..
[4] Ben Adlam and Jeffrey Pennington. The neural langent kernel in high dimensions: Triple descent and a multi-scale theory of generalization. In International Conference on Machine Learning (ICML), 2020.
Zeyuan Allen -hu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning (ICML), 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning (ICML), 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Rousong Wang. On exact computation with an infinitely wide neural net. Neural Information Processing Systems (NeurIPS). 2019.
[8] P. Auer, Herbster, and M. Warmuth. Exponentially many local minima for single neurons. Neural Information Processing Systems (NIPS), 1996.
Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In International Conference on Machine Learning (ICML), 2017.
[10] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension and pscudodimension bounds for piecewise lincar neural networks. Journal of Machine Learning Research (JMLR), 20(63):1-17, 2019.
[11] Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta munerica, 30:87-201, 2021.
[12] Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity, 4, 1988.
[13] Lucas Benigni and Sandrine Péché. Eigenvalue distribution of some nonlinear models of random matrices. Electronic Journal of Probability, 26:1 37, 2021.
[14] Sébastien Buheck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
[15] Sam Buchanan, Dar Gilboa, and John Wright. Deep networks and the multiple manifold problem. In International Conference Learning Representations (ICLR), 2021.
10

---

[16] Zixiang Chen, Yuan Cao. Difan Zou, and Quanquan Gu. How much over-paramelerizzaionn is sufficient to learn deep relu networks? In International Conference Learning Representations (ICLR), 2020.
[17] Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In Neural Information Processing Systems (NeurIPS), volume 32, 2019.
[18] Thomas M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, (3):326-334, 1965.
[19] Amit Daniely, Memorizing gaussians with no over- paraaattettiiiionn via gradient decent on neural networks, 2020. arXiv:2003 12895.
[20] Amit Daniely. Neural networks learning and memorization with (almost) no over-paramettriizaion. In Neurul Information Processing Systems (NeurlPS), 2020.
[21] Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning (ICML), 2019.
[22] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- weerpparamterized neural networks. International Conference on Learning Reprexentations (ICLR), 2019.
[23] Zhou Fan and Zhichao Wang. Spectra of the conjugate kernel and neural tangent kernel for linear-widre neural networks. In Neural information processing systems (NeurlPS), 2020.
[24] Rong Ge, Runzhe Wang, and Haoyu Zhao. Mildly overparametrized neural nets can memorize training data efficiently, 2019. arXiv: 1909. 11837.
[25] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. When do neural networks outperform kernel methods? In Neural Information Processing Systems (NeurlPS), 2020.
[26] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. The Annals of Statistics, 49(2):1029-105:: 2021.
[27] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Machine Learning (ICML), 2010.
[28] Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5927-5933 2017.
[29] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986, 2022.
[30] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2015.
[31] Wei Hu, Lechao Xiao, Ben Adlam, and Jeffrey Pennington. The surprising simplicity of the early-time learning dynamics of neural networks. In Neural Information Processing Systems (NeurIPS), 2020.
[32] Baihe Huang, Xiaoxiao Li, Zhao Song, and Xin Yang. Fl-ntk: A neural tangent kernel-based framework for federated learning analysis. In International Conference on Machine Learning (ICML), 2021.
[33] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kemel: Convergence and generalization in neural networks. In Neural Information Processing Systems (NeurIPS), 2018.
[34] Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. In International Conference Learning Representations (ICLR), 2019.
[35] Adam Kowalczyk. Counting function theorem for multi-layer networks. In Neural Information Processing Systems (NIPS), 1994.
[36] Yann LeCun, Léon Bottou, Genevieve Orr, and Klaus-Robert Müller. Efficient backprop. In Neurul networks: Tricks of the trade, pages 9-48. Springer, 2012.
[37] Zhenyu Liao and Romain Couillet. On the spectrum of random features maps of high dimensional data. In International Conference Machine Learning (ICML), 2018
11

---

[38] Zhenyu Liao, Romain Couillet, and Michael W. Mahoney. A random matrix analysis of random Fourier features: beyond the Gaussian kernel, precise phase transition, and the corresooninng double descent. In Neural Information Processing Systems (NeurIPS), 2020.
[39] Cosme Louart, Zhenyu Liao, and Romain Couillet. A random matrix approach to neural networks. The Annals of Applied Probability, (8(2):1190-1222 2018.
[40] Song Mci, Theodor Misiakiewicz, and Andrea Montanari. Generalization error of random feature and kernel methods: hypercontractivity and kemel matrix concentration. Applied and Computational Harmonic Analysis, 2021.
[41] Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 75(4):667- 766, 2022.
[42] Andrea Montanari and Yigiao Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training, 2020. arXiv:2007... 12826.
[43] Quynh Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. International Conference on Machine Learning (ICML), 2021.
[44] Quynh Nguyen, Pierre Bréchet, and Marco Mondelli. When are solutions connected in deep networks? In Neural Information Processing Systems (NeurIPS), 2021.
[45] Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In International Conference on Machine Learning (ICML), 2017.
[46] Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity deep CNNs. International Conference on Machine Learning (ICML., 2018.
[47] Quyah Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Neural Information P Processing Systems (NeurlPS), 2020.
[48] Quynh Nguyen, Marco Mondelli, and Guido Montufar. Tight bounds on the smallest eigenvalue of the neural langent kernel for deep ReLU networks. In International Conference Machine Learning (ICML), 2021.
[49] Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning (ICML), 2019.
[50] Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameetrrizatio:: Global convergence guarantces for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, I(1):84 105, 2020.
[51] Sandrine Péché. note on the Pennington- -onrh Worah distribution. Electronic Communications in Prohability, 24:1-7, 2019.
[52] Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference Machine Learning (ICML), 2017.
[53] Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. The emergence of spectral universality in deep networks. International Conference on Artificial Intelligence and Statistics (AISTATS), 2018.
[54] Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Neural Information Processing Systems (NewrIPS), 2017.
[55] Jeffrey Pennington and Pratik Worah. The spectrum of the fisher information matrix of a hingl-hhideen-aye layer neural network. In Neural Information Processing Systems (NeurIPS), 2018.
[56] Vanessa Piccolo and Dominik Schröder. Analysis of one-hidden--ar layer neural networks via the resolvent method. Neural Information Processing Systems (NeurIPS). 2021.
[57] Itay Safran and Ohad Shamir. Spurious local minima are common two-layer ReLU neural networks. In International Conference on Machine Learning (ICML), 2018.
[58] Akito Sakurai. nh-1 networks store no less n h+ 1 examples, but sometimes no more. In IJCNN International Joint Conference Neural Networks, 1992.
12

---

[59] Mohamed EI Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of GAN-data behave gaussian mixtures. In International Conference on Machine Learning (ICML), 2020.
[60] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. International Conference on Learning Representations (ICLR), 2015.
[61] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over parammmeeteri shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-76) 769, 2018.
[62] Chaehwan Song, Ali Ramezani Kebryya, Thomas Pethick, Armia Eftekhari, and Volkan Cevher. Sub- quadratic overparamelerization for shallow neural networks. In Neural Information Processing Systems (NeurIPS), 2021.
[63] Zhao Song and Xin Yang. Quadratic suffices for over parameetttiinnnoonnn via matrix chernoff bound, 2020. arXiv: 1906. 03593.
[64] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, page 210-268. Cambridge University Press, 2012.
[65] Roman Vershynin. High-dimensional probability: An introduction with applications in data science.
Cambridge university press, 2018
[66]
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2(4):1004-1055 2020.
[67] Jun-Kun Wang, Chi-Heng Lin, and Jacob D Abernethy. A modular analysis of provable acceleration via Polyak's s momentum: Training wide ReLU network and a deep linear network. In International Conference on Machine Learning (ICML), 2021.
[68] Zhichao Wang and Yizhe Zhu. Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks, 2021. arXiv: 21009.9904..
[69] Xiaoxia Wu, Simon S. Du, and Rachel Ward. Global convergence of adaptive gradient methods for an weer-parameterized neural network, 2019, arXiv:1902.07111.
[70] Chulhee Yun. Suvrit Sra, and Ali Jadbabaie. Small nonlinearities in activation functions create bad local minima in neural networks. In International Conference on Learning Representations (ICLR), 2019.
[71] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks powerful memorizers: tight analysis of memorization capacity. In Neural Information Processing Systems (NeurIPS), 2019.
[72] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires re-thinking generalization. In International Conference Learning Representations (ICLR), 2017.
[73] Difan Zou, Yuan Cao. Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterriee deep relu networks. Machine Learning, 109(3):467 2020.
[74] Difan Zou and Quanquan Gu. An improved analysis of training over-parameterrized deep neural networks. In Neural Information Processing Systems (NeurIPS), 2019.
13


Reviews:
[{"review_id": "rsjnTR1m-px", "reviewer": "Reviewer_UvzJ", "summary": "This submission studies the problem of minimum over-parameterization in deep neural networks. More specifically, the authors investigated the settings with sublinear layer width and provides the lower bound in terms of the smallest NTK eigenvalue.", "questions": "See above", "limitations": "Yes", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I must first say that this paper is much beyond my expertise, and the evaluation of this submission should depend on other reviewers with necessary background.\n\nStrength:\nAs the authors claimed, this paper gives an affirmative answer regarding whether NTK is well-conditioned in the sublinear setting. The theoretical results from Theorem 3.1 match the claim. The authors also provide details proof to cover the main steps.\n\nWeakness:\nSome clarification regarding the assumptions would be helpful to understand the major conclusion. For example, if \\alpha >= 1 in Eq. (4), does it mean that the number of neurons would exceed the sublinear case? \n\nAnother case is regarding the proof for the smallest NTK eigenvalue: how does it depend on the optimizer? Since NTK changes with updated parameters (which may explode if optimization failed), does the proof depend on any hidden assumptions for the optimizer?  ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "nGiVEgz1q_E", "reviewer": "Reviewer_mvcT", "summary": "This paper shows that NTK can be well-conditioned in a sub-linear setup. In particular, they proved that roughly  $\\Omega (N)$ parameters are needed to get a good NTK matrix, and also $O(N)$ parameters are enough to memorize the training data. Based on those NTK bounds, they further provide results on the memorization capacity and the optimization via gradient descent and square loss.  ", "questions": "1. Requirement 4 in Assumption 2.5 implies that the total number of neurons should be larger than $\\Omega(N^{(1+\\alpha)/2})$. This violates the statement after Theorem 3.1 in line 175. \n\n2. The authors argue that when all the widths have the same scaling, the upper bound matches the lower bound. In this case, the training data size $N$ should be smaller than $d^{2/(1+\\alpha)}$ according to Assumption 2.5, where d is the dimension of the input. This is a fairly strong condition for the training data set, which may limit the significance of the results.  \n\n3. Under certain margin assumptions on the training data, [1] showed that a polylogarithmic width condition suffices for two-layer ReLU networks to converge and generalize. Later [2] studied how much over-parameterization is sufficient to learn deep ReLU networks and showed that under certain assumptions on the training data, polylogarithmic width is sufficient. Since these papers have milder overparameterization conditions of the NNs, the authors may want to make a comparison with those results. \n\n[1] Ji, Ziwei, and Matus Telgarsky. \"Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks.\" International Conference on Learning Representations. 2019.\n\n[2] Chen, Zixiang, et al. \"How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?.\" International Conference on Learning Representations. 2020.", "limitations": "The authors have addressed their work's limitations and potential negative social impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "It is interesting to study the neural network in a sub-linear setup. For square loss, the authors provided valuable sight for the training data memorization as well as the optimization. This paper is well-written and clear for the technique part. However, I have several concerns about the significance and the limitation of the results. Besides,  I think this paper can improve the clarity of their results by making a comparison with the setting for the classification. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WKUsCo819J4", "reviewer": "Reviewer_5UpM", "summary": "This manuscript analyses the neural tangent kernel in the regime of minimum over-parameterization. In detail, the authors prove the lower bound about the NTK eigenvalue for deep nets with minimum over-parameterization. Then, they apply the theorems to the aspects of networks' memorization and training.", "questions": "1. The modern deep learning foucses on \"super\" over-parameterization, why do the paper research the minimum over-parameterization? For completing the NTK theorem? How the research on the minimum over-parameterization help understand the success of deep nets?\n\n2. What is the mean of \"to be conditioned\"?\n\n3. About the experiments of Figure 2, are the used labels random? If yes, Can we get the similar results with normal label (or normal dataset with low complexity, compared to the complex random datasets)? \n", "limitations": "Please the Questions.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThis manuscript deeply investigate the question of minimum over-parameterization;\n\nThe proofs are solid;\n\nTwo application are proposed based on theorems.\n\nCons:\n\nThis paper is very theoretical and focuses on the minimum over-parameterization in deep learning. I am not an expert about the NTK research, so I mainly give some comments and suggestion on writting. For me, it is neccesary to clearly and comprehensively illustrate the backgroud and significance on investigating the problem of minium over-parameterizatio, please see Questions below.\n\nSome minor writing suggestions:\n\n1. Line 60: the full name of PSD should be proposed;", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PRS1t0Gr8t", "reviewer": "Reviewer_mnfH", "summary": "For an $L$-layer (loosely) pyramidal network, this paper gives a probabilistic lower bound on the smallest eigenvalue of the empirical neural tangent kernel Gram matrix, which is proportional to the product of the width of the last two hidden layers. When combined with known results on NTK, this lower bound implies that $\\sim \\sqrt{N}$ neurons are enough to learn a solution (via GD) that memorizes $N$ copies of data. ", "questions": "My questions are basically the same as the weaknesses described above:\n\n- Could you describe what the hidden terms of Theorem 3.1. are?\n\n- Please explain when and why $CN\\exp(-c\\log^2 n_{L-1})$ would be small enough for event in Theorem 3.1 would happen with a sufficiently large probability.", "limitations": "Limitations are well-addressed.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I do not have anything major against the acceptance of this paper. The paper is well written and the theoretical contributions are clear (up to my knowledge). I especially appreciate the proof-technical innovation in the paper---the three-stage centering argument may be quite useful for the future works in this direction.\n\nNevertheless, I do have some minor concerns:\n\n- Assumption 2.4 restricts the setup to neural networks with \"loose pyramidal topology,\" which seems to be much weaker than the strict pyramidal topology in the sense that the layer width need only be smaller than a constant times the preceding layer's width. While this looks very easy to satisfy, this also suggests that actually many \"constants\" are being hidden inside the big-O notation of Theorem 3.1. Could you briefly describe the what the hidden terms of Theorem 3.1 are, and how they behave with respect to the assumption?\n\n- The probability of event at Theorem 3.1. is $1 - C \\exp(-c\\sqrt{N}) - CN\\exp(-c\\log^2 n_{L-1})$. I am particularly worried about the last term, which is proportional to the sample size $N$. Could you explain in more detail, why, and under what condition such $N$-proportionality does not really make the probabilistic bound meaningless?\n\n- I do not find Figure 1 to be very meaningful---any curve can look linear when we select a nice interval.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept