Mildly Overparametrized Neural Nets can Memorize Training Data Efficiently
Authors: Rong Ge
Runzhe Wang
Haoyu Zhao
Venue:  (2020)
Keywords: nonconvex optimization
optimization landscape
overparametrization

Abstract: It has been observed \citep{zhang2016understanding} that deep neural networks can memorize: they achieve 100\% accuracy on training data. Recent theoretical results explained such behavior in highly overparametrized regimes, where the number of neurons in each layer is larger than the number of training samples. In this paper, we show that neural networks can be trained to memorize training data perfectly in a mildly overparametrized regime, where the number of parameters is just a constant factor more than the number of training samples, and the number of neurons is much smaller.

Under review as a conference paper at ICLR 2020
MILDLY OVERPARAMETRIZED NEURAL NETS CAN MEMORIZE TRAINING DATA EFFICIENTLY - REVI- SION
Anonymous authors Paper under double-bling blind review
ABSTRACT
It has been observed (Zhang et al., 2017) that deep neural networks can memorize: they achieve 100% accuracy on training data. Recent theoretical results explained such behavior in highly overparametrized regimes, where the number of neurons in each layer is larger than the number of training samples. this paper, we show that neural networks can be trained to memorize training data perfectly in mildly overparametrized regime, where the number of parameters is just constant factor more than the number of training samples, and the number of neurons is much smaller.
INTRODUCTION
In deep learning, highly non-convex objectives are optimized by simple algorithms such as stochastic gradient descent. There has been many theoretical analysis for the optimization landscape of neural networks(e.g.. Brutzkus et al. (2017); Brutzkus & Globerson (2017); Ge et al. (2017b); Wang et al. (2018)), but 2018). In practice, it was observed that neural networks are able to fit the training data perfectly, even when the data/labels are randomly corrupted(Zhang et al., 2017). Recently, a series of work (Du et al. (2019); Allen-Zhu et al. (2019c); Chizat & Bach (2018); Jacot et al. (2018), see more references in Section 1.2) developed a theory of neural tangent kernels (NTK) that explains the success of training neural networks through overparametrizztion. Several results showed that if the number of neurons at each layer is much larger than the number of training samples, networks of different architectures (multilayer/recurren)) can all fit the training data perfectly.
very simple two-layer networks have spurious local optima(Safran & Shamir,
However, if one considers the number of parameters required for the current theoretical analysis, these networks are highly overparametrized. Consider fully connected networks for example. If two-layer network has a hidden layer with neurons, the number parameters is at least rd where d is the dimension of the input. For deeper networks, if it has two consecutive hidden layers of size r, then the number of parameters is at least r². All of the existing works require the number of neurons per-layer to be at least the number of training samples (in fact, most of them require r to be polynomial of n). In these cases, the number of parameters can be at least nid or even n² for deeper networks -much larger than the number of training samples Therefore, natural question is whether neural networks can fit the training data in the mildly overparametrized regime- where the number of parameters is only a constant factor larger than the number of training data. To achieve this, one would want to use small number of neurons in each layer n/d for two-layer network and vn for a three-layer network. Yun al. (2018) showed such networks have enough capacity to memorize any training data. In this paper we show with polynomial activation functions, simple optimization algorithms are guaranteed find a solution that memorizes training data.
1.1 OUR RESULTS
In this paper, we give network architectures (with polynomial activations) such that every layer has width much smaller than the number of training samples n, the total number of parameters is linear in n, and simple optimization algorithms such neural networks can fit any training data. We first give a warm-up result that works when the number of training samples is roughly d? (where d is the input dimension).

---

Under review as a conference paper at ICLR 2020
Theorem 1 (Informal). Suppose there are n (2+1) training samples in general position, there exists a two-layer neural network with quadratic activations, such that the number of neurons in the hidden layer is 2d 22, the total number of parameters is O(d?), and perturbed gradient descent can fit the network to any output.
Here "in general position" will be formalized later as a deterministic condition that is true with probability for random inputs, see Theorem 4 for details.
In this case, the number of hidden neurons is only roughly the square root the number of training samples, so the weights for these neurons need to be trained carefully in order to fit the data. Our analysis relies on an analysis of optimization landscape we show that every local minimum for such neural network must also be globally optimal (and has O training error). As result, the algorithm can converge from an arbitrary initialization.
Of course, the result above is limited the number of training samples cannot be larger than O(d)). We can extend the result to handle a larger number of training samples:
Theorem 2 (Informal). Suppose number of training samples n S d for some constant p. if the training samples are in general position there exists three-layer neural network with polynomial activations, such that the number of neurons v in each layer is Oplyn) and perturbed gradient descent on the weights of the middle layer can fit the network any outpul.
Here Op considers
constants and hides constant factors that only depend on p. We consider "in general position" in the smoothed analysis Tramework(Spielman inputs ,2; Jn. E IRd fix a perturbation radius vv, the actual inputs is 2 t where ü, NO, v/). The guarantee of training algorithm will depend inverse polynomially on the perturbation (note that the architecture- in particular the number of neurons independent of v). The formal result is given in Theorem 5 in Section 4. Later we also give a deterministic condition for the inputs, and prove a slightly weaker result (see Theorem 6).
Teng, 2004) given arbitrary
1.2 RELATED WORKS
Optimization Landscape for Networks without Overparametrrizttoon Many works (Brutzkus & Globerson, 2017; Tian, 2017; Li & Yuan, 2017; Soltanolkotabi, 2017; Zhong et al., 2017; Ge et al., 2017b) analyzed the optimization landscape of 2-layer neural networks. However, these works either work on single neuron or have very strong assumptions also known that even with strong assumptions on input x gradient descent on the standard objective can get stuck in spurious local minima when the network has more than constant number of neurons (Safran & Shamir, 2018).
the input (such as is Gaussian). It is
Neural Tangent Kernel Many results in the framework of neural tangent kernel show that net- works with different architecture can all memorize the training data, including two-layer (Du et al., 2019), multi-layerrDuu et al., 2018; Allen-Zhu al., 2019e; Zou & Gu, 2019), recurrent neural net- work(Allen-Zhuu et al., 2019b). However, all of these works require the number of neurons in each layer to be at least quadratic in the number of training samples. Oymak & Soltanolkotabi (2019) improved the number of neurons required for two-layer networks, but their bound is still larger than the number training samples. There are also more works for NTK on generalization guarantees (e.g.. Allen-Zhu et al. (2019a)), fine-grained analysis for specific inputs( Arora et al., 2019b) and empirical performances(AAe) Arora et al., 2019c), but they are not directly related to our results.
Representation Power of Neural Networks For standard neural networks with ReLU activations, Yun et al. (2018) showed that networks of similar size as Theorem 2 can memorize any training data. Their construction is delicate and it is not clear whether gradient descent can find such a solution.
Matrix Factorizations and Quadratic Activations Since the activation function for our two- layer net is quadratic, training of the network is very similar to matrix factorization problem. Many existing works analyzed the optimization landscape and implicit bias for problems related to matrix factorization in various
et al., 2016; Ge et al., 2016; 201 7a; Park et al., 2016; Gunasckar et al., 2017: Li al., 2018; 8; Arora et al., 10)9).. In this line of work, Du & Lee (2018) and Soltanolkotabi al. (2018) are the most similar to two-layer result. Du & Lee (2018) showed
2

---

Under review as a conference paper at ICLR 2020
how gradient descent can learn two-layer neural network that represents any positive semidefintte matrix. However positive definite matrices cannot used to memorize arbitrary data, and our two-layer network represent arbitrary matrix. Soltanolkotabi et al. (2018) is very similar to our two-layer result except they require the input to be Gaussian. Extending this condition to our deterministic condition is crucial to our main (3-layer) result.
Existing works mildly overparametrrzaaioon There are several works on overparametrization that does not fall exactly into the NTK regime. Brutzkus et al. (2017); Wang et al. (2018) works for linear separable setting. However in this setting gradient descent also works even if the network has only a single neuron (no overparametrization), so the results only show that overparametrization does not hurt. Li & Liang (2018) requires interesting but strong assumption on the input data. Our work is different as we make mild assumptions on the data distribution and the network size is necessary (up to constant factors) achieve 0 training error without further assumptions.
Interpolating Methods Of course, simply memorizing the data may not be useful in machine learning. However, recently several works(Belkin et al., 2018; 2019; Liang al., 2019; Mei & Montanari, 2019) showed that learning regimes that interpolate/memorizze data also have gener- alization guarantees. Proving generalization for our architectures is an interesting open problem.
PRELIMINARIES
In this section, we introduce notations, the two neural network architectures used for Theorem 1 and and the perturbed gradient descent algorithm.
2.1 NOTATIONS
We use [n] to denote the set 21., n). For vector æ, use ||ا|| denote its & norm, and sometimes ||=|| as a shorthand. For matrix M, we use || ||] fr to denote its Frobenius norm, M| denote its spectral norm. We will also use (MM and os (M) to denote the i-th largest eigenvalue and singular value of matrix M, and Amin (M), minn (M) to denote the smallest eigenvalue/singula value.
For the results of three-layer networks, our activation is going to be x", where is considered as small constant. We use O,(). (,p() to hide factors that only depend on p.
For vectors x; y E Rd, the tensor product is denoted by (a @ x) E Rdd We use & E dd as a shorthand for p-th power of in terms of tensor product. For two matrices M, N Rdd xd2, use M s E mddxxd denote the Kronecker product of matrices.
2.2 NETWORK ARCHITECTURES
In this section, we introduce the neural net architectures we use. As we discussed, Theorem I uses a two-layer network (see Figure (a)) and Theorem 2 uses a three-layer network (see Figure (b)).
Two-layer Neural Network For the two-layer neural network, suppose the input samples are in Rd the hidden layer has r hidden neurons (for simplicity, we assume is even, in Theorem 4 we will show that r 2d is enough). The activation function of the hidden layer is (zz) z
We use E Rdd to denote the input weight of hidden neuron i. These weight vectors are collected as a weight matrix W [w1, 12..... wor] Rdxr, The output layer has only neuron, and we use a, E R to denote the its input weight from hidden neuron i. There is no nonlinearity for the output layer. For simplicity, we fix the parameters a,, i E [r] in the way that a, for all 1 < < 5 Given as the input, the output of the neural network
and -1 for all _ + < i
y El ow)

---

Under review as a conference paper at ICLR 2020
Input layer
Hidden layer
Output layer
Input layer
Hidden layer
Hidden layer 2
Output layer
(a) 2-layer neural net structure
(b) 3-layer neural net structure
Figure 1: Neural Network Architectures. The trained layer is in bold face. The activation function after the trained parameters is (blue neurons). The activation function before the trained parame- ters is x (purple neurons).
If the training samples are (Zz) define the empirical risk of the neural network with parameters W to
S(W) = 4n
auww xz)2 yj
Three-layer neural network For Theorem 2, work. In this network, the first layer has a polynomial activation r(I) = x", and the next two layers the same the two-layer network.
complicated, three-layer neural net-
We use R = [ri,.... ]T] E R to denote the weight parameter of the first layer. The first hidden layer has i neurons with activation r(x) x² where p the parameter in Theorem 2. Given input x, the output of the first hidden layer is denoted as 2, and satisfy 2; = (r (x,)).TT P.The second hidden layer has neurons (again we will later show
2k is enough). The weight matrix for second layer is denoted as W [wi...., wr] E *** where each w, E R is the weight for neuron in the second hidden layer. The activation for the second hidden layer is (z) x². The third layer has weight and is initialized the same way as before, where = a2
0r/2 1, and ar 1. The final output y can be computed as y Ei= a,("f²)) 2)2
ar/2+1
Given inputs v1), (In, Va). suppose is the output of the first hidden layer for 24. the empirical loss is defined as:
S(W) 4n Σ
Σ a:(wT 2j)² U1
Note that only the second-layer weight W is trainable. The first layer with weights R acts like random feature layer that maps xy's into a new representation 2, 's...
2.3 SECOND ORDER STATIONARY POINTS AND PERTURBED GRADIENT DESCENT
Gradient descent converges to a global optimum of a convex function. However, for non-convex objectives, gradient descent is only guaranteed to converge into a first-order stationary point point with gradient, which can be a local/global optimum or a saddle point. Our result requires any algorithm that can find a second-order stationary point point with 0 gradient and positive definite Hessian. Many algorithms were known to achieve such guarantee Ge et al., 2015: Sun et al., 2015; Carmon et al., 2018; Agarwal et al., 2017; Jin et al., 2017a;b). As require some additional

---

Under review as a conference paper at ICLR 2020
properties of the algorithm (see Section 3), we will adapt the Perturbed Gradient Des, (Jin et al., 20177)) See Section B for a detailed description the algorithm. Here we give the guarantee of PGD that need. The PGD algorithm requires the function and its gradient to be Lipschitz:
Definition (Smoothness and Hessian Lipschitz). differentiable function f(-) is E-smooth if:
Vx 22, [V[((z)) v f||a - #2ll-
tvice-differenticble function f()) is p-Hessian Lipschitz if: Vz 22.
S plaa xz2l. \\>>\\l
Under these assumptions, we will consider an approximation for exact second-order stationary point as follows:
Definition (e-second-order stationary point). For a p-Hessian Lipschitz function f(),, we say that is e-second-order stationary point if: ||V f [())]l & e, and Xmin (V2 f(x)) -VPE.
Jin et al. (2017a) showed that PGD converges to an e-second-order stationary point efficiently: Theorem 3 (Convergence of PGD (Jin et al. (2017a))), Assume that f(-) is E-smooth and p- p-Hessian Lipschitz. Then there exists an absolute constant Cmax such that, for any 8 0, S - L Z f(xo) - ff, and constant с S. Cmaro PGD(xo, l, P,E, c, 6, A will output an e-second-order sta- tionary point with probability 1 - 6, and terminate in the following number of iterations:
((T(50)) f²) log
/dLAs
))
E28
WARM-UP: TWO-LAYER NET FOR FITTING SMALL TRAINING SET
In this section, we show how the two-layer neural net in Section 2.2 trained with perturbed gradient descent can fit any small training set (Theorem 1). Our result is based a characterization of optimization landscape: for small enough e, every g-second-order stationary point achieves near- zero training eπror. We then combine such result with PGD to show that simple algorithms can always memorize the training data. Detailed proofs are deferred to Section the Appendix.
3.1 OPTIMIZATION LANDSCAPE OF TWO-LAYER NEURAL NETWORK
Recall that the two-layer network we consider has r-hidden units with bottom layer weights W1, W2, Wr, and the weight for the top layer is set to a; 1 for S i S r/2, and a; -1 for r/2 + Sisn r. For set of input data {21 (().,))). (z2, y2). .... (Zn, yn }, the objective function defined as f(W)= = An Σ (E (n x2 yz)
With these definitions, we will that when point is approximate second-order stationary point (in fact, we just need it to have an almost positive semidefinite Hessian) it must also have low loss:
Lemma 1 (Optimization Landscape). Given training data {(11,31) (I2, V2)...., ..., (In Bn)}, Sup- pose the matrix X [ ..... 2022 xd has full column rank and the smallest singular value at least a. Also suppose that the number of hidden neurons satisfies r 2 2d + Then if Aunn 2 (W) 2 c, the function value is bounded by f(W)= < nds?
472
Soltanolkotabi et al. (2018) gave a similar characterization of the landscape, except their theorem requires 2,'s 's to be Gaussians.
3.2 OPTIMIZING THE TWO-LAYER NEURAL NET
Given the property of the optimization landscape for fW), ), it is natural to try to use PGD to find second-order stationary point. However, this is not enough since the function f does not have bounded smoothness constant and Hessian Lipschitz constant, and without improved analysis PGD not guaranteed to converge in polynomial time. In order control the Lipschitz parameters,
5

---

Under review as a conference paper at ICLR 2020
note that these parameters are bounded when the norm of W is bounded (see Lemma 5 in appendix). Therefore we add a small regularizer term to control the norm of W. More concretely, we optimize:
g(W) = ((W) + 2 II
We want to use this regularizer term to show that: 1. the optimization landscape is preserved: for appropriate ?, any e-second-order stationary point of g(W) will still give a small f(W); and 2. During the training process of the 2-layer neural network, the norm of W is bounded, therefore the smoothness and Hessian Lipschitz parameters are bounded. Then, the proof of Theorem I just follows from the combination of Theorem 3 of PGD and the result of the geometric property.
The first step is simple as the regularizer only introduces term 7/ to the Hessian, which increases all the eigenvalues by y. Therefore any E-second-ord -oderr stationary point of g(W) will also lead to the fact that Iminn V [(W) is small, and hence S(W) is small by Lemma 1.
For the second step, note that in order to show the training process using PGD will not escape from the area {W : [| < [] with some r, it suffices bound the function value g(W) by ///2, which implies [[I]]
properties of PGD: for gradient descent step, since the function is smooth in this region, the function value always decreases; for a perturbation step, the function value can increase, but cannot increase by too much. Using mathematical induction, we can show that the function value of g is smaller than some fixed value(related to the random initialization but not related to time t) and will not escape the set {W : |[W]|| S }} for appropriate r. Combining these analysis we have the following theorem:
(W) I r. To bound the function value
x E R x has full column rank and the smallest singular value is at least a. Also assumme that we have ||رر|| S B and 1yy| S. Y for all j Σ n.. We choose our width of neural network r 2 2d + 2 and we choose = (6B+ /((((0) + 1)) (nd/(o²=)) 1/4
Theorem (Main theorem for 2- NN). Suppose the matrix X = [x]²
(o"=/nd) 1/2 and = max 1))++)++ + B + 13. Then there exists absolute constant Cmax such that, for any ō > 0, A f(0) + 1, and constant с S Gmax. PGD(O, l, p. E, c, 6, ) on W will output an parameter W* such that with probability 1- - 8, f(W*) I when the algorithm terminates in the following number of iterations:
o B (Snd)
+ 1)2 log*
(BrrdeA(f(O) + 1),
0555/2
8²0g
4 THREE-LAYER NET FOR FITTING LARGER TRAINING SET
In this section, we show how a three-layer neural net can fit a larger training set (Theorem 2). The main limitation of the two-layer architecture in the previous section is that the activation functions are quadratic. Therefore, no matter the number neurons in the hidden layer, the whole network only captures a quadratic function over the input, and cannot fit an arbitrary training set of size much larger than d², On the other hand, if one replaces the quadratic activation with other functions, it is known that even two-layer neural networks can have bad local minima(Saffan & Shamir, 2018).
To address this problem, the three-layer neural net in this section uses the first-layer as a random mapping of the input. The first layer is going to map inputs x 's into 2;'s of dimension (where k = @(vn)) If 2,'s s satisfy the requirements of Theorem 4, then we can use the same arguments as the previous section to show perturbed gradient descent can fit the training data.
We prove our main result in the smoothed analysis setting, which is a popular approach for going beyond worst-case, Given any worst-case input {#1, X2, Fn J. in the smoothed analysis frame- work, these inputs will first be slightly perturbed before given to the algorithm. More specifically, let E = zy + z. where žÿ E Rd is a random Gaussian vector following the distribution of AO wI). Here the amount of perturbation is controlled by the variance The final running time for our algo- rithm will depend inverse polynomially on v. Note that on the other hand, the network architecture and the number of neurons/parameters in each layer does not depend U.
Let {21, 22, ..., 2n} denote the output of the first layer with (2z)s = (rTT,)( = 1,2,..., we first show that {21}'s 's satisfy the requirement of Theorem 4:
Lemma 2. Suppose le S Op(d)) and (k+1) > n, let T, = Zj + 3, be the perturbed input in the smoothed analysis setting, where 3. N(O, vI), let { (21, 2., bn) be the output of the first

---

Under review as a conference paper at ICLR 2020
layer the perturbed input ((zy): = ())))))) Let Z E R& be the matrix whose j-th column is equal to = then with probability least 1 6, the smallest singular value of Z is at least Qp /n /1(("680///2++//4444) )22
This lemma shows that the output of the first layer (2₁ 's satisfies the requirements of Theorem 4. With this lemma, we can prove the main theorem of this section:
Theorem 5 (Main theorem for 3-layer NN), Suppose the original inputs satisfy | S 1, I 1, imputs Σj 2j 3j are perturbed by š, NNO,, vf), with probability 1 8 over the random initialization, for = 2[ Vnl, perturbed gradient descent on the second layer weights achieves loss f(W*) I e in O₂ (n/a))(e))
2//2 log (n/c) iterations.
Using different tools, we can also prove a similar result without the smoothed analysis setting:
x has full column rank, and smallest singular value at least a. Choose k O, with high probability perturbed gradient descent on the second layer weights achieves loss f(W)) in (1))
Theorem 6. Suppose the matrix X = [x] ...., x2 E T
(1))
a log' (n/cc iterations.
When the number of samples is smaller than d /(p)). one choose k Op(d"). in this regime the result of Theorem 6 is close to Theorem 5. However, if n is just larger, say ddv one may need to choose (d"+)) which gives sub-optimal number of neurons and parameters.
Proof techniques Theorem 5 relies on Theorem 4 - it suffices to prove the two requirements in in Theorem 4: (a) The norm of output from each input sample bounded with high probability; (b) The matrix formed by the tensor of each output (Matrix Z in Lemma 2) has high segg-rrbbbbilityy positive smallest singular value lower bound, The proof of (a) is relatively simple as one only needs standard concentration bounds. The condition (b) is stated in Lemma 2.
To prove Lemma 2, we need to show that the vectors s0 are linearly independent (and well- conditioned). We prove that by using a technique called leave-one-out distance, which widely used in random matrix theory (e.g., in Rudelson & Vershynin (2009)). Roughly speaking, leave- one-out distance requires us to prove that for any fixed j. the vector 2) is far from the span of all
the other z/²2(1 + j)). We in fact show something stronger: for any fixed linear subspace (that is independent of ūfy) of dimension at most n 1, the distance between @2 and this subspace is large. This is done using anti-concentration inequalities for polynomials. Of course, there are additional challenges in this approach, as the entries of 2 2 are not independent. We use decoupling techniques to handle the additional dependencies. See details in Appendix
EXPERIMENTS
In this section, we validate theory using experiments. Detailed parameters of the experiments as well as more result are deferred to Section A in Appendix.
Small Synthetic Example We first gradient descent synthetic data-set, which fits into the setting of Theorem 4. Our training set, including the samples and the labels, are generated from fixed normalized uniform distribution(random sample from a hypercube and then normalized to have norm 1). As shown in Figure 2, simple gradient descent can already memorize the training set.
MNIST Experiment We also show how our architectures (two-layer and three-layer) can be used to memorize MNIST. For MNIST, we use squared loss between the network's 's prediction and the true label (which is an integer in {0, 1, ..., 9}). For the two-layer experiment, we use the original MNIST dataset, with small Gaussian perturbation added to the data to make sure the condition in Theorem 4 is satisfied. For the three-layer experiment, we use PCA to project MNIST images to 100 dimensions (so the two-layer architecture will no longer be able to memorize the training set). See Figure 3 for the results. In this part, we use ADAM as the optimizer to improve convergence speed, but given the main result optimization landscape the algorithm is flexible.

---

Under review as a conference paper at ICLR 2020
Training loss
6
4-
2-
5000
10000 15000 20000 25000
Iter
Figure 2: Training loss for random sample experiment
Training loss
Training loss
8-
8
Lo58
4-
2-
2
0
0
20000
40000
10000
20000
30000
Iter
Iter
(a) Two-layer network with perturbation input (b) Three-layer network top 100 PCA direc- tions
Figure 3: MNIST with original label
MNIST with random label We further test our results on MNIST with random labels to verify that our result does not any potential structure in the MNIST datasets. The setting is exactly the same as before. As shown in Figure 4, the training loss can also converge.
Training loss
Training loss
7.5
10
Loss
5.0
Loss
5
2.5
0.0
10000
20000
30000
10000 20000 30000 40000 50000 Iter
Iter
(a) Two-layer network with perturbation input (b) Three-layer network top 100 PCA direc- tions
Figure 4: MNIST with random label
6 CONCLUSION
In this paper, we showed that even a mildly overparametrized neural network can he trained to memorize the training efficiently. The number of neurons and parameters in our results are tight (up to constant factors) and matches the bounds in Yun et al. (2018). There are several immediate open problems, including generalizing our result to more standard activation functions and providing generalization guarantees. More importantly, we believe that the mildly overparametrized regime is more realistic and interesting compared to the highly overparametrized regime. We hope this work would be a first step towards understanding the mildly overparametrized regime for deep learning.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approxi- mate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195-1199. ACM, 2017.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In Advances neural information processing systems, 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In Advances in neural information processing systems, 2019b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252, 2019c.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint arXiv:1905. 13655, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning. pp. 322-332, 2019b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 1ete::994.19990 2019c.
Mikhail Belkin, Daniel J Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. In Advances Neural Information Processing Systems, pp. 2300 2311, 1, 2018.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B Tsybakov. Does data interpolation contra- dict statistical optimality? In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1611-1619, 2019.
Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. Advances Neural Information Processing Systems, pp. 3873-3881, 2016.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for convnet with gaussian inputs. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 605-614. JMLR. org, 2017.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint arXiv:1710.10174 2017.
Anthony Carbery and James Wright. Distributional and 19 norm inequalities for polynomials over convex bodies in r", Mathematical research letters, 8(3):233-248, 2001.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Accelerated methods for nonconvex optimization. SIAM Journal Optimization, 175-)775 2018.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems, pp. 3036-3046 2018.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 2019.
2019.
Simon S Du and Jason D Lee. On the power of over-parametrizzaioo in neural networks with quadratic activation. In International Conference on Machine Learning, pp. 1328-1337, 2018.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint 1800021810 2018

---

Under review as a conference paper at ICLR 2020
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle pointsonline stochastic gradient for tensor decomposition. In Conference on Learning Theory. pp. 797-842, 2015.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems, pp. 2973-2981, 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, 2017a.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one- see-hidden-layee -aaeer neural networks with landscape
design. arXiv preprint arXiv: 1,00500, 201
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems, pp. 6151-6159, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. Advances in neural information processing systems, pp. 8571- 8580, 2018.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael I Jordan. How to escape saddle points efficiently. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1724-1732. JMLR. org, 2017a.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. arXiv preprint 1rXiv:1711.10455 2017b.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 0rXiv:1412.69880 2014.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Advances in Neural Information Processing Systems, pp. 8157- 8166, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pp. 597-607, 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations. In Conference On Learning The- ory, pp. 2-47, 2018.
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai. On the risk of minimum-norm interpolants and restricted lower isometry kernels. arXiv preprint arXiv: 1908. 10292, 2019.
Tengyu Ma, Jonathan Shi, and David Steurer. Polynomial-tinn citommill-tmeeeeee tensor decompositions with sum-of- squares. In 2016 IEEE 57th Annual Symposium Foundations of Computer Science (FOCS), pp. 438-446. IEEE, 2016.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and double descent curve. arXiv preprint arXiv: 190800555, 2019.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparametetiizaton:: global conver- gence guarantees for training shallow neural networks. arXiv preprint 1xXiv:1902.04677 2019.
Dohyung Park, Anastasios Kyrillidis, Constantine Caramanis, and Sujay Sanghavi. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. arXiv preprint 16X1v:1609.032400 2016.
Mark Rudelson and Roman Vershynin. Smallest singular value of random rectangular matrix. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 62(12):1707-1739, 2009.
Itay Safran and Ohad Shamir. Spurious local minima are common in two-layer relu neural networks. In International Conference on Machine Learning, pp. 4430-4434 2018.
10

---

Under review as a conference paper at ICLR 2020
Mahdi Soltanolkotabi. Learning relus via gradient descent. In Advances in Neural Information Processing Systems, pp. 2007-2017, 2017.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
Daniel A Spielman and Shang- Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM), 51(3):885 2004.
Ju Sun, Qing Qu, and John Wright. When are nonconvex problems not scary? arXiv preprint vrXiv:1510.06096, 2015.
Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications in convergence and critical point analysis. arXiv preprint arXiv:1703.000 2017.
Roman Vershynin. High- High-ddmensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018.
Gang Wang, Georgios В Giannakis, and Jie Chen. Learning relu networks on linearly separable data: Algorithm, optimality, and generalization. arXiv preprint 1808 04685, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: tight analysis of memorization capacity. arXiv, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt. Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017.
Kai Zhong, Zhao Song, Prateck Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guarantees for haeehidden-layer neural networks. arXiv preprint arXiv: 100.:0/70660375. 2017.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. arXiv preprini arXiv: I 1906.990000 04688, 2019.

---

Under review as a conference paper at ICLR 2020
A MORE EXPERIMENTS AND DETAILED EXPERIMENT SETUP
A.1 1 EXPERIMENTS SETUP
In this section, we introduce the experiment setup in detail.
Small Synthetic Example We generate the dataset in the following way: We first set up a random matrices X E I (samples,, where N is the number of samples, d is the imput dimension and Y E IR (labels). Each entry in X or Y follows a uniform distribution with support [-1,1] Each entry is independent from others. Then we normalize the dataset X such that each row in X has norm 1, denote the normalized dataset X [.1,...,,IN. _xx]" Then we compute the smallest singular value for the matrix [&]² ..... #021T and we feed the normalized dataset X into the two-
layer network(Section 2.2) with r hidden neurons. We select all the parameters as shown in Theorem 4, and plot the function value for f(.).
In our experiment for the small artificial random dataset, we choose N 300, d 100, and r 300.
MNIST experiments For MNIST, we use a squared loss between the network's prediction and the true label (which is an integer in {0, 1, 9)).
For the first two-layer network structure, we first normalize the samples in MNIST dataset to have norm 1. Then we set up two-layer network with quadratic activation with 3000 hidden neurons (note that although our theory suggests to choose r 2d 2, having larger r increases the number of decreasing directions and helps optimization algorithms in practice). For these experiments, we use Adam optimizer(Kingg Kingma & Ba, 2014) with batch size 128, initial learning rate 0.003, and decay the learning rate by factor of 0.3 every 15 epochs (we find that the learning rate-decay is crucial for getting high accuracy).
We run the two-layer network in two settings, one for the original MNIST data, and one for the MNIST data with a small Gaussian noise (0.01 standard deviation per coordinate). The perturbation added in order for the conditions in Theorem 4 to hold.
For the three-layer network structure, we first normalize the samples in MNIST dataset with norm 1. Then we do the PCA to project it into 100-dimension subspace. We D ( to denote this dataset after PCA. Note that the original 2-layer network may not apply to this setting, since now the matrix X 82
In does not have full column rank(60000 1002). We then add small Gaussian perturbation D N(O of) to the sample matrix D and denote the perturbed matrix D [ ................................ Jn We then randomly select a matrix Q (O, Aed and compute the random feature 2 = (Qr,)², where (.)² denote the element-wise square. Then we feed this sample into the 2-layer neural network with hidden neuron d. Note that this is equivalent to three-layer network structure in Section 2.2. In our experiments, l = 750, r = 3000, 01 = 0.05, 02 = 0.15.
MNIST with random labels These experiments have exactly the same set-up as the original MNIST experiments, except that the labels are replaced by random number in (0.1,2.....))
A.2 EXPERIMENT RESULTS
In this section, we give detailed experiment results with bigger plots. For all the training loss graphs, we record the training loss for every iterations. Then for the ith recorded loss, we average the recorded loss from i 19th ith and set it the average loss at (5i)th iteration. Then take the logarithm on the loss and generated the training loss graphs.
Small Synthetic Example As we can see in Figure the loss converges to quickly.
MNIST experiments with original labels First we compare Figure 6 and Figure 7. In Figure 6, optimize the two-layer architecture with original input/labels. Here the loss decreases to small value (~ 0.1), but the decrease becomes slower afterwards. This is likely because for the matrix X defined in Theorem 4, some of the directions have very small singular values, which makes it
12

---

Under review as a conference paper at ICLR 2020
Training loss
2
0
Log(Loss)
-2
-4
-6
0
5000
10000
15000
20000
25000
Iter
Figure 5: Synthetic Example
Training loss
2
1
Log(Loss)
-1
10000
20000
30000
40000
50000
Iter
Figure 6: Two-layer network original MNIST
much harder to correctly optimize for those directions. In Figure 7, after adding the perturbation the smallest singular value of the matrix X becomes better, and as we can see the loss decreases geometrically to very small value (< 1e -). 5).
A surprising phenomenon that even though we offer no generalization guarantees, the network trained in Figure 6 has MSE error of 1.21 when tested test set, which is much better than random guess (recall the range of labels to 9). This is likely due to some implicit regularization effect (Gunasekar al., 2017: 7: Li et al., 2018).
For three-layer networks, Figure 8 we can see even though we are using only the top 100 PCA directions, the three-layer architecture still drive the training emror very low level.
13

---

Under review as a conference paper at ICLR 2020
Training loss
2
0
Log(Loss)
-2
-4
-6
wmm
-8
0
5000
10000
15000
20000
25000
Iter
Figure 7: Two-layer network on MNIST, with noise std 0.01
Training loss
2
0
Log(Loss)
-2
-4
-8
0
10000
20000
30000 Iter
40000
50000
Figure 8: Three-layer network with top 100 PCA directions of MNIST, 0.05 noise per direction
MNIST with random label When we try to fit random labels, the original MNIST input does not work well. We believe this is again because there many small singular values for the matrix X in Theorem 4, so the data does not have enough effective dimensions fit random labels. The reason that it still able to fit the original labels some extent (as in Figure 6) is likely because the original label is correlated with some features of the input, so the original label is less likely to fall into the subspace with smaller singular values. Similar phenomenon was found in Arora et al. (2019b).
Once we add perturbation, for two-layer networks we can fit the random label to very high accuracy, in Figure The performance for three-layer network in Figure 10 is also similar to Figure 8.
14

---

Under review as a conference paper at ICLR 2020
Training loss
2
0
Log(Loss)
-2
-4
-6
8
-10
0
5000
10000 15000 20000 25000 30000 35000
Iter
Figure 9: Two-layer network on MNIST, with noise std 0.01, random labels
Training loss
2
0
Log(Loss)
-2
-4
0
10000
20000
30000
40000
50000
Iter
Figure 10: Three-layer network with top 100 PCA directions of MNIST, 0.05 noise per direction, random labels
B DETAILED DESCRIPTION OF PERTURBED GRADIENT DESCENT
In this section we give the pseudo-code of the Perturbed Gradient Descent algorithm as in Jin et al. (2017a), see Algorithm I. The algorithm quite simple: it just runs the standard gradient descent, except if the loss has not decreased for long enough time, it adds perturbation. The perturba- tion allows the algorithm to escape saddle points. Note that we only use PGD algorithm to find second-order stationary point. Many other algorithms, including stochastic gradient descent and accelerated gradient descent, are also known to find a second-orde -odder stationary point efficiently. All these algorithms can be used for our analysis.
15

---

Under review as a conference paper at ICLR 2020
Algorithm Perturbed Gradient Descent
Input: To, P. 8, Ay.
1: X - 3 max log
d'd,
A4 t 2. +
Ver X2F : Itures &
Vce x²
fines t CVE3
x² 2/v0 timees t
xe @ Vpc
2: moise thhres
3: for t 0,1,... do
4:
if [
S Iitres and Enoise >
Ethres then
5:
It f- It,, Inoise
6:
24 + Tz Le, where & drawn uniformly from (r
7:
end if
Enoise = thres and f(x))= - 10000-(ftt (( -fures then 9: return I Txan
8: if t
10: end
11: T2+11
12:
end for
C GRADIENT AND HESSIAN OF THE COST FUNCTION
Before we prove any of our main theorems, we first compute the gradient and Hessian of the func- tions ((W) and gW)) our training process, we need to compute the gradient of function g(W). and in the analysis for the smoothness and Hessian Lipschitz constants, we need both the gradient and Hessian.
Recall that given the samples and their corresponding labels {(z M;))isn, we define the cost func- tion of the neural network with parameters W [Wi,..., ".....,,,,,, E Rdxx.
f(W) = 4n
Σ
Σ (w 2,)² Vj
Given the above form of the cost function, we can write out the gradient and the hessian with respect to W. We have the following gradient,
0f(W)
2
2
2ax (ow( xz 2z)
Owp
ak
as u x2,} - V1
255 Wk.
n
/=1
0² f(W)
and
dwk, Owik
aki
Σ mmi
a: (w) xT)) ) - VU
2, +
20k, aka
T Wk, |2 Wk. ) if k2 K2
20 ak
(a. Wky (2) Wh, Dajzf if ki + k2
Danky Ohika is square matrix whose differ- ent rows means the derivative to elements in Wk, and different columns represent the derivative to elements in Why Then, given the above formula, we can write out the quadratic form of the hessian with respect to the parameters Z
In the above computation, Sws. is column vector and (WW(W)
as(W)
[21, :2, 2r, E Rdxr.
2 f(W)(( 2)
T
4k
Σ (w x2 - 81 I5Σ
23
1=1
1=1
16

---

Under review as a conference paper at ICLR 2020
T Wk2
20k, akk
Σ
n
(az Wky (aj (ky )ayze
wkz
n
1SA1 St
72
2 n
Okk
am('z xzz)²
Vi IzJ T
2h
Σ a
ورير 24
Tt
n j=1
In order to train this neural network in polynomial time, we need to add small regularizer to the original ocst function f(W). Let
gW) = f(W) + [Wil
where 7 is constant. Then we can directly get the gradient and the hessian of (WW) from those of S(W). We have
OKk 72
a. (uf Ys 2,155 wx + +wk
n
j=1
(2)
ai (w) xzz) 2- -Yi 2zμe
k=
+
Σ
+ + a aw ma 2s
For simplicity. we can use 2 W WAWT,, z, yy to denote diagonal matrix with Aa = Then we have
(E=r x2)² yy. where A is
Vwg(W) = Σ
(o
WWTT uz) 25 W A +W
(Z,
Σ
a
W WWWT xj - vs) 2ويo 2x
k=1
-=1
2 ando 2,5 21
2
+ +711Z112.
n
D OMITTED PROOFS FOR SECTION
In this section, we will give a formal proof of Theorem 4. We will follow the proof sketch in Section 3. First in Section D.1 we prove Lemma which gives the optimization landscape for the two-layer neural network with large enough width;then in Section D.2 we will show that the training process on the function with regularization will end in polynomial time.
D.1 OPTIMIZATION LANDSCAPE OF TWO-LAYER NEURAL NET
In this part we will prove the optimization landscape(I_emma, 1) of 2-layer neural network. First we recall Lemmal 1.
Lemma 1 (Optimization Landscape). Given training data {(x1, 21), (I2, V2). ..., (I Bn)}, Sup- pose the matrix X [ ....., 2.221 d has full column rank and the smallest singular value at least a. Also suppose that the number of hidden neurons satisfies r 2 2d + 2. Then if Aunin F(W 2 -,, the function value is bounded by f(W) < nds²
472
For simplicity, we will use 6,) = Ei a.(wTay)) y, denote the error of the output of the neural network and the label yj- Consider the matrix M 1/ Σÿ= djzzol.. To show that every
xz)²
17

---

Under review as a conference paper at ICLR 2020
e-second-order stationary point W of f will have small function value f(W), we need the following 2 lemmas.
Generally speaking, the first lemma shows that, when the network is large enough, any point with almost Semi-definite Hessian will lead to a small spectral norm of matrix M.
Lemma 3. When the number of the hidden neurons 2 2d + 2, we have
Amin ? f(W) max (A((M))
where Xmii V2 ((W denotes the smallest eigenvalue of the matrix V f(W) and Xx( denotes the i-th eigenvalue of the matrix M.
Proof. First note that the equation
Ami V(S(W) max (Mx
equivalent
max || min V (Z)) ||2| p=1 and we will give a proof of the equivalent form.
12 M=|,
First, we show that
min V (2) || 1=1
max 1= M=M. ||
Intuitively, this is because 2 f(W) is the sum of two terms, one of them is always positive semidef- inite, and the other term equivalent a weighted combination of the matrix M applied different columns of Z.
V2,(W(ZZ22)
T
Σ
(w) (u(Wxxz)²² - Yi
2k +
a 25z} 2i
k=1
1=1
j=1
1=1
2 n
2 Ma 2k
Σ amw 2,
n2 j=1
a&2E M
2 max (MM) 1|2.11
max (MM 1
=
Then we have
min V VZ,(W)
min (- max (M(M))) = max | =- max M2]
[|]|==1
||
||=||==1
For the other side, we show that
min F=
2 ((W)))))))
max ||=||==1
T M
by showing that there exists Z, || FF = 1 such that V²f(W) 2) = max||=|aa 12T M z/.
First, let 20 arg | 2 Recall that for simplicity, we assume that r is an even number and a, for all < and a, -1 for all i > r+2 If zf M < 0, there exists R such that
1. |u//2
18

---

Under review as a conference paper at ICLR 2020
2. u, for all i 2
3. > W = 0,
since for constraints 2 and 3, they form a homogeneous linear system, and constraint has equa- tions and constraint 3 has equations. The total number of the variables is and we have > 2 + since we assume that r 2 2d + 2. Then there must exists r + 0 that satisfies constraints and 3. Then we normalize that have norm |||]|2
Then, let Z = znu² we have 1 =
| 12
||ull =
and
(2,(
Σ
a M +
a, 2j 2i
k=
5=1
2
0 aRUE Mo +
2 Σ
Σ
m 2nbЯ
j=1
1=1
=20 Mz0 + Σ
Σ
o
j=1
1=1
max 12S M22.
|| 2=
where the third equality comes from the fact that ||u1|2 = Ei= u² = 1, 0 for all i > 2.
and Ei= apu,; 0. The proof for the case when 2/ Me0 > 0 is symmetric, except the second half of the coordinates (where a; = -1).
The next step needs to connect the matrix M and the loss function. particular, we will show that if the spectral norm of M is small, the loss is also small.
221 E g xn has full column rank and the smallest singular value is at least o. Then if the spectral norm of the matrix = -,= 8,0,2z is upper bounded by the function value is bounded by
Lemma 4, Suppose the matrix X =
[x1
nd)2
f(W) <
402
Proof. We know that the function value f(W) = Ej= 63 = 11111 where E R" is the vector
whose j-th element is 5,. Because X = [ 02 ..... 2 E _dxxx has full column rank and the smallest singular value is at least a,, we know that for any R",
||oll22 2 (Xin(X) ||o|12 2 σ 0//1//2.
Since M = 1/2 1 is symmetric matrix, M has d real eigenvalues, and we use Å1. Xa to denote these eigenvalues. Because we assume that the spectral norm of the matrix M E 55 upper bounded by X, which means that | < X for all < i S d, and we have
|
= Σ
x
x2
dx2.
i=1
Then can conclude that
n
M |
Σ
رررر 11
1
|811.
n
where the second equation comes from the fact that reordering a matrix to a vector preserves the Frohenius norm.
19

---

Under review as a conference paper at ICLR 2020
Then combining the previous argument, we have
f(W) = 4n 4
1 1 S
n
||
-
nd)a
4
Lemma 1 follows immediately from Lemma 3 and Lemma 4.
D.2 TRAINING GUARANTEE OF THE TWO-LAYER NEURAL NET
Recall that in order to derive the time complexity for the training procedure, we add regularizer to the function f. More concretely,
2 [W]] sW) = s(W)+ + 2
where 7 is constant that we choose in Theorem 4.
To analyze the running time of the PGD algorithm, we first bound the smoothness and Hessian Lipschitz parameters when the Frobenius norm of W is bounded.
Lemma 5. In the set {W : [[W1| ST), if we have |zyl|2 S B and luyl S Y for all j S n, then
1. Vg(W) is (3 + B + -smoothh
2. V'g(W) has
Hessian.
Proof. We first figure out the smoothness constant. We have
[[) - Vo(V)lle
(nTUAUT x3 -3- - U1) UT + - 1 n
Σ
(x (N xy - - VV - ~VI16
n j=1
X n Σ (c) - v1) -))) 2,,5 UA
(1) x3 (,) 2, + - Vlle.
Then we bound the first term, we have
U xj - v;) 23 UA-
1
(x V x. u5) V All
j=1
2,)
(u] -1)
n
j=1
(cTUAU" x, 2,) 1
(uTUAV" -, v.) =,)
n
(FUVV 2,) 20)
1
- Alls
n
- uD) -
Σ (.)
n j=1
(L SU ,,
VA
1 Σ
(4TUAV x.
-,--,,, 1 v,) 2 AllF
n j=l
(UUUAV=2)-
VA
1
VA x, 2 AlLE.
20

---

Under review as a conference paper at ICLR 2020
The first term can be bounded by
1 (TTAAT" 23 - v1) 252 A
<||
1
Σ ()) Alle
! Σ
<| Σ
AU
+ V)Alle
1=1
<B'MIIU Vlr + YB Vllr.
Similarly, we can show that
a x TUAAA - v1) 20)) VA- Σ
(uJUAVT 2, -,) =)) S BBTIUU-VI
j=1
j=1
and
Σ UUTUATTZ x3 v1) 2z] V A
Σ
(x) VAVVVVT x2 -5) V S B'TIUU-VI1
Then, we have
[V) Vg(())le S 53BBT+ YB + 7)1l VllF.
Then we bound the Hessian Lipschitz constant. We have
V
((,))
V²g(V)(2, Z)
2
T
0k
a
(1 UUUAUTT 33 -3)) 1z T
2k +
2
Σ
and 3z
T
T
24
+ 111
n
n
k=1
j=1
y=1
2
2k
0
(1) V. x2 -1,)
2/
2
0,0% 25 21
T
-71
n
k=1
j=1
1=1
0k
(1,TUAUT - VAV (
252z
2xl
n2
k=1
- aul o05 )
2
Σ
anf azæ 21 - Σ
n
1=1
First we have
ag n n
zxl
j=1
CQUAAU-VAVVI (G]CAAU-VVVV)) 21
Σ (2][UUAUTT - -UVV +UAVT- - VAVT)2,) )a,) 2ب23 I| 1|
<2B'T& |IU VIIelleu11.
21

---

Under review as a conference paper at ICLR 2020
So bound the first term by
ak
(1) (UAU - )A 2z45
2xc
n j=l
2BT
||U V||=||=112 -1 VI1=/1211.
Then for the second term, note that
Σ
=
1=1
and we have
2
2 n
Σ a 2 )
Σ
aa 2a0t2
71 j=l
2 n
AUA -VA,22(V
11
==
I((U - V)A, + ()A,
2
II(U V) 211= + +VAl|=|1> Z
<4BTH -1|>>1
where the first inequality comes from the Cauchy-Schwatz inequality. Combining with the previous computation, we have
-
-|
We also have the theorem showing the convergence result of Perturbed Gradient Descent( (Algort(A 1).
Theorem 3 (Convergence of PGD (Jin et al. (2017a))). Assume that f(-) is l-smooth and p-Hessian Lipschitz. Then there exists an absolute constant Cmax such that, for any 8 0. L
p L. 2
f(oo) f", and constant e S Cmaso PGD(xo, l, p, c, 8, As) will output an E-second-order sta- tionary point with probability 1 - 6, and terminate in the following number of iterations:
(((((1)) - 1*)
/dess
2² log"
E28
Then based on the convergence result in Jin al. (2017a) and the previous lemmas, have the following main theorem for 2-layer neural network with quadratic activation.
Theorem 4 (Main theorem for 2-layer NN). Suppose the matrix X [x ...., x82 e x has full column rank and the smallest singular value is at least a. Also assume that we have ||اد < B and 1yy| Y for all I We choose width of neural network > 2d + 2 and choose
(6B²) (0) + 1)) (nd/(o"s)) 1/1 7 (o²=/nd) 1/2 and & = max 2(1())+1) + YB2 + 13. Then there exists an absolute constant Cmax such that, for any 5 0, 2 / +1, and constant < Cmar, PGD(O, l, s, c, 8, A) on W will output parameter W* such that with probability 8, f(W*) & when the algorithm terminates in the following number of iterations:
0 / + 1)² log"
Bn(d)A(f(0) + +1)
0555/2
E250
22

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 4. We first show that during the training process, if the constant S 1, the objec- tive function value satisfies
3CE
g(w) S g(Winn)) ins) +
2x
where we choose the smoothness constant 2 to be the smoothness for the region g(W) s g( ((Win) (ims)) +
3ce2 2x
In the PGD algorithm (Algorithm 1), we say point is in perturbation phase, if t noise lthres- A point F2 the beginning perturbation phase if reaches line of Algorithm and perturbation is added to it.
We use induction to show that the following properties hold.
1. If time t is not in the perturbation phase, then g(W;) S g(Wns).
2. If time is in perturbation phase, then g(W)) S g(Wins) +
3es 2x
Moreover, if t is the
beginning of a perturbation phase, then g (W,) S im...
First we show that at time = O, the property holds. If t 0 is not the beginning of a perturbation phase, then the inequality holds trivially by initialization. If = 0 is the beginning of a perturbation phase, then we know that g(W)) = (ins) from the definition of the algorithm, then
g(W)) -WW - Eo)
(1)
(WWW) + |lEoll | + [
Sg(Wo) Jtnes + 6,2
Sg(Wo) + Ves Vee
Ves Ves
+
x²e x²
2 x22 x2l
3cE
[Iii) + 2x
Now we do the induction: assuming the two properties hold for time i, we will show that they also hold at time + 1. We break the proof into cases:
Case 1: t + is not in perturbation phase. In this case, the algorithm does not add a perturbation on 1,+1, and we have
g(++1) =g(W, vo(W))
(2)
L Sw(W)) (WV)(, (W()) 1nV
So(W)) 7 (IV
(W(W))
If t is not in perturbation phase, then from the induction hypothesis, we have
g(W+1) S 9(W,) S gWWis)
otherwise if is in a perturbation phase, since + 1 is not in perturbation phase, must be at the end of the phase. By design the algorithm we have:
g( (W++1) & g(W) S - S (WWns)
Case 2: t + is in perturbation phase, but not at the beginning. Using the same reasoning as equation we know
g(W+11) 9(W)) & 9(Wim))
23

---

Under review as a conference paper at ICLR 2020
Case 3: + 1 is at the beginning of perturbation phase. First we know that g(W,) S (Wins)
since t. either not in a perturbation phase of at the end of perturbation phase, then we have g(W++1) S (.W.). Same as the computation in equation 1, we have
3es
g(W++1) - (Wins) 2x4e
This finishes the induction.
Since we choose É 2 I, we can choose the other parameters such that g(W+11) S (.9WWi) ins)
300
S
2x
g(Wins) ims) Then since
s(W) = S(W) + ? [W
we know that during the training process, we have | z 2()(W)))
Since we train from
Wins O, we have ||W]| 2(1(0++1) From Lemma 5, we know that
1. Vg(W) is (3 + B + 7)-smooth.
2. V'g(W) has 6B* 1(1(0)+1) Lipschitz Hessian.
As we choose y (6B²* (() + 1 2/5 know that p (6B* 1)) is an upper bound on the Lipschitz Hessian constant.
When PGD stops, we know that
Amin (v ((g(W)) - 1
and we have
Amin (22((W)
- /2(()) 1))2/5 2/5 Amin - 7
From Lemma 3, we know that the spectral norm of matrix M is bounded by 2(6B* / (0) + 1))2/5 225 and from Lemma 4, we know that
f(W) $ nd. 4(6B* / 2(f(0) 1))4/5, g4/5 nd (6B*
(GB+)2(((()) 2(f(() 1)) g/6
402
σ²
The running time follows directly from the convergence theorem of Perturbed Gradient De- scent(The 3) and the previous argument that the training trajectory will not escape from the set (W: ||W|| < 211)
Then, in order to get the error to be smaller than E, we choose
0=
5/4
nd
6B* 6B4 2(((0)++
and the total running time should be
( (nd 1)2
(Bnrd(A(S(O)) +1)
log*
55/5/2
8280
Besides, our parameter / and 7 chosen to be
nd
- (6B* /2(f(0) 1))
and
02g
= (6B (
2/5
nd
24

---

Under review as a conference paper at ICLR 2020
E OMITTED PROOFS IN SECTION 4
In this section, we give the proof of the main results of our three-layer neural network((heeorm and 6). Our proof mostly uses leave-one-out distance bound the smallest singular value of the relevant matrices, which is a common approach in random matrix theory (e.g., in ). However, the matrices we interested in involves high order tensor powers that have many correlated entries, so we need to rely on tools such as anti-concentration for polynomials in order to bound the leave-one- distance.
First in Section E.I. we introduce some more notations and definitions, and present some well- known results that will help us present the proofs, In Section E.2, we proof Theorem 5 which focus on the smoothed analysis setting. Finally in Section E.3 we prove Theorem 6 where we can give deterministic condition for the input.
E. PRELIMINARIES
Representations of symmetric tensors Throughout this section, use T3 denote the space of p-th order tensors on dimensions. That is, To (Rd)& A tensor T Th is symmetric if T(1,, 12, .... ip) = (1)x (m(2): (x()) for every permutation x from [p] + [p]. We use X to denote the space of all symmetric tensors in To- The dimension of X2 is DJ p
(
Let Xg- = x E x |لا|| = } be the set of unit tensors in X (as sub-metric space of T For Rd, let {eiii = 1, 1,2...d) d} be its standard orthonormal basis. For simplicity of notation we use Sp to denote the group of bijections (permutations) [p] + [p]. and La to denote the set of integer indices
d
1 = ((1,,22 (2....)))) E N
Σ i = p}. We can make X2 isomorphic (as a vector space over R) to 1=1
Euclidean space R (12)) D by choosing a basis (s
Σ Boo &ej.ca) &
... Goom (h 0222 opp) = (éx) 2((2) o... ....)))()))))) } where (1 2(12) o... d(te)) means length p string with 1 1's, i2 2's and so on, and let the isomorphism be of. We call the image of a symmetric tensor through o its reduced vectorized form, and we can define a new norm on X with ||a/||wv~ (x)]l2,
Given the definition of reduced vectorized form and the norm || Il.. we have the following lemma that bridges between the norm ll and the original 2-norm.
Lemma 6. For any Xę.
| 2 Vp!
||0||2-
Proof. We can expand as x Σ 3,8t. Then ||
/ Σ x2 and ||x||| =
Σ
x 11
as
V vi
V
{s:} are orthogonal. Notice that for i (d1, b2 .......n):: ||sell3 p! pl, and therefore
π es!
| < V
atpp Edppl EEIR
Vp!l2///
E-net Part of our proof uses e-nets to do a covering argument. Here we give its definition.
Definition 3 (s-Net). Given a metric space (X, d). A finite set N C P is called e-net for P C X for every x P, there exists n (x: E N such that d(xr, π (x)) ) S E. The smallest cardinality of an for P is called the covering number: (P,,)) inf N is e-net of P).
Then we introduce give an upper bound on the size of nenet of set K C Rd. First, we need the definition of Minkowski sum
25

---

Under review as a conference paper at ICLR 2020
Definition 4 (Minkowski sum). Ler A, B S Rdd be 2 subsets of R then the Minkowski sum is defined as
A := = a
Then the covering number can bounded by a volume argument. This is well-known, and the proof can be found in Vershynin (2018)(Pooosition 4.2.12 in Vershynin (2018)).
Proposition 1 (Covering number). Given set K S Rd and the corresponding metric d(æ, y) || - y/l2. Suppose that > O, and then we have
K + (B(EE22)) N(K,
(B5((/2)
where denote the volume the set.
Then with the help of the previous proposition, can bound the covering number of symmetric tensors with unit length.
Lemma 7 (Covering number of X%). There exists an E-net of X with size O ((1+22 (1+2222 D2
i.c.
e) 50 ((1 2/p!
(1+2 c
D
Proof. Recall that (.()) Rd + P
f is an bijection between the symmetric tensors in R and net for the image (Xx) implies an E-net for the unit vector in R.D, We first show that an -nt
symmetric tensor X.P
Suppose that the - for the image (x())) is denoted as N 2x())) and for any x
(X)), there exists K (x) E N such that [|)(() - æ||2 S Vpr Then we know that (o -1 (N) is an c-net for the unit symmetric tensors XT. because for any x' E XP, we have
|| (0 (T( 12 SV (0110((()))) ग (o
Svpl =E,
pp
where the first inequality comes from Lemma 6.
Next, bound the covering number for the set d (2). First note that the set satisfies o7(X)) C I P2, and from Proposition we have
(x
+
BB
DP
d
Dvp!
N
(2
Vp!
DV
B
2Vp
D
B DE
B2
(1)
2vpl
B2
(2
2/p! D
where the first inequality comes from Proposition and the second inequality comes from the fact that (x=)l) & |||||
26

---

Under review as a conference paper at ICLR 2020
Leave-one-out Distance Another main ingredient in our proof is Leave-one-ore distance. This is a notion that is closely related to the smallest singular value, but usually much easier to compute and bound. It has been widely used in random matrix theory, for example in Rudelson & Vershynin (2009).
Definition (Leave-one-our distance). For set of vectors V {ri, u2.... un.... distance is defined as
their leave-one-oul
(V)
min Isisn an
inf
||u;
Σ ajuyll2-
For matrix M, its leave-one-out distance ((M) is the leave-one-out distance of its columns.
The leave-one-out distance is connected with the smallest singular value by the following lemma: Lemma 8 (Leave-one-out distance and smallest singular value). For matrix M Ruxx with m 2 n. let LM) denote the leave-one-out distance for the columns of M, and J (innM) denote the smallest singular value of M, then
I(M) S Jwin (M) S ((M).
12
We give the proof for completeness.
Proof. For any R (0). let rax) = argmax |zs]. then (xr())) > O for x + 0.
vE(x]
Because 1(M) = min inf
| we have
iE[n] WER" ====1
|a
inf min (M)
1o
||a||2
|| 2 1|
inf vE[n we (0,()))))))
min
2,
|| 1 ll2
|| || ||2
min keln
inf (E
Because of the equations
||~1||2
|
and
||>' ll2
Σ
x
S V
Vū, we have
JE[n]
(MM) v <
mmin (M) ((M).
To make use of the random Gaussian noise added in the smoothed analysis setting, we rely on the following anti-concentration result by Carbery & Wright (2001):
Anti-concentration
Proposition 2 (Anti-concentration (Carbery & Wright (2001))). For multivariate polynomial f(z) f(x1, T211,-2-- ... zn) of degree p. let No, 1)" follows the standard normal distribution, and Var 2 1, then for any E IR and ε > 0,
Pr(lf(x) - 1| S e] s 2/p)
Gaussian moments To apply the anti-concentration result, we need to give lower bound of the variance of polynomial when the variables follow standard Gaussian distribution (N00, 1). Next, we will show some definitions, propositions, and lemmas that will help us to give lower bound for variance polynomials.
Proposition (Gaussian moments). if x ~ 1) is a Gaussian variable, then for p E N, (2p)
[x22]] [p!) 2Pp [g 0.
Definition 6 (Hermite polynomials). In this paper, we use the normalized Hermite polynomials, which are univariate polynomials which form orthogonal polynomial basis under the normal distribution. Specifically, they are defined by the following equality
(
d"
Hn(x)
Vn!
dl."
27

---

Under review as a conference paper at ICLR 2020
The Hermite polynomials in the above definition forms set of orthonormal basis of polynomials in the standard Normal distribution. For polynomial f IR R. f(x)
n1
J 1
Σ
and
iET
1 f(x) S 1I (1y) be its expansions the basis of monomials and Hermite polynomials iEI
respectively (H2 is the Hermite polynomial order k). Let the index set 1:50
Ü
12
We have
j=0
the following propositions. The propositions are well-known and easy to prove. We include the proofs here for completeness.
Proposition 4. for E Th I.M
Proof. Consider i = (i1, b2 1.g..... in) E Is in the monomial expansion, the coefficient for the mono- n
mial M, II z/ is f.M. In the Hermite expansion, since H, (2) an order-n polynomial, if the j=1
term II He (zz) contain the monomial M,, there must be inj 2 ig. and therefore for E I the only 1=1
term in the Hermite expansion that contains M; is f1 11 H, (zz) (with M; as its highest order j=1
monomial). The coefficient for 2² in Hi, (Ix) is Viz. and therefore J.M
1
Proposition 5. For x ~ N),, Ex = S Fu1s9 = E
(2 (0r refers to the index
VEI
00.0,0.--000 0) E 1
Proof. Firstly, let w<x)
1e =2 be the PDF of N(0 1). then
/2T
(-1)"
d" 2²/2
(n(z)
dr
22nn!
da
[0 2
1 n
result of d"a--3pp dza
0 when t:00 for 0. Besides,
J (z))))) 8am
for its well-known orthogonality in Guassian distribution (with 8mm I/n mm] as the Kronecker function). Therefore.
Σ " II /
Exfl
Hi (2,)w(z;)ddz
]E(n)
Σ
11
T(i
=
S
/E(n)
cH
E. =
Σ
1 II
H,,
jE(m)-
28

---

Under review as a conference paper at ICLR 2020
E
II 5c(m]
-
&EEIS
Σ
Then, we have the following lemma that lower bounds the variance of a polynomial with some structure. Given the following lemma, we can apply the anti-concentrrttio results the proof of Theorem 5 and 6.
....)))) Lemma 9 (Variance). Let f(x) f(11, T2- ... Ia) be a homogeneous multivariate polynomial of degree p. then there is symmetric tensor M E X2 that fx) x For all Ny E Rd, when (0,
|f + x)] MM
Proof. We can view f(ro + x) as polynomial with respect to and let f:M and f. be the co- efficients of its expansion in the monomial basis and Hermite polynomial basis respectively (with variable x). It's clear to see that (f E IR) is the reduced vectorized form of M. From the Proposition 4 and 5, we have
Varls + x]] =00 + +z) -[ + x)]
Σ
(
1 \0n
Σ
Σ (
iE
M| 1
LI
We also need a variance bound for two sets of random variables
Lemma 10. Let fxx = f(11,12 ... Ea) be homogeneous multivariate polynomial of degree 2p, then there is a symmetric tensor M Xg that f(x)) (M,x For all wo, vo Rd, when u. U N (0, Ia), we have
1 (2p)) M
Var [M, M (wp + u) @ (vo 8)88]]
Proof. The proof similar Lemma 9. We can view (M, (wp + u @ (w++ + +)) as a degree-2) polynomial g over 2d variables (u,v). v). Therefore by Lemma 9 the variance would be at least the rv-norm of g. Note that every element (monomial the expansion) M corresponds to at least one element in y, and the ratio of coefficient in the correspnding rv-basis is bounded by (2p)!, therefore
lialire 2 (2p) M [re. and the lemma follows from Lemma
E.2 PROOF THEOREM
In this section, we give the formal proof of Theorem 5. First recall the setting of Theorem 5: we add a small independent Gaussian perturbation ă ~ (0, vdd on each sample æ, and denote = x + f. The output of the first layer is {zj} where 2₁ (i) (r J.
Our goal to prove that {2₂} satisfy the conditions required by Theorem 4, in particular, the .821 has full column rank and bound on smallest singular value. To do that,
matrix Z = [2 note that if we let X = [ 82p . @2p ... oú, S2p) be the order-2p perturbed data matrix, and Q be Sp then matrix whose i-th row is equal to r
write Z (Q Q)
We first show an auxiliary lemma which helps us to bound the smallest singular value of the output matrix (Q Q) and then present proof for Lemma 2.
29

---

Under review as a conference paper at ICLR 2020
Generally speaking, the proof of Lemma 2 consists of the lower bound of the Leave-one-one distance by the cati-concentration property of polynomials and the use of Lemma 8 to bridge the Leave-one out distance and the smallest singular value.
Lemma 11. Let M be k-dimensional subspace of the symmetric subspace of Xa. and let Proj be the projection into M. For any R with pertubation I (0, =
k
1/4
Pr
Proj M 1
uhe
<(())
(2p)
Proof. Let my, M2 .2........ my X be set of orthonormal (in Ty as Euclidean space) ba-
sis that spans M, and each m, is symmetric. Then Proj x 3p =
(ms, #8p)2, Let
&
g(x) Σ (m,
m a 222), then g(x) is a homogeneous polynomial with order [
==1
2p. For any initial value v. if = x + 3. then Je
+ Jo T is a vector where the random
part Ve J
i NNO,,)) 1)". Therefore by Lemma
Var
m
32
(2p)
(2p)
2=1
1=1
Hence from Proposition 2 we know that, when 3 ~ uT),
Pr
Proj
2 101122 M
k
u E
Pr
(2p)
9(
I
<
2
< O(p):1/p
(2p))
k
Lemma 12. Let M be a k-dimensional subspace of the symmetric subspace of X2" and let Proj at be the projection into M. For any x, E Rd with pertubation i. ÿ ~ N(, v) I x - H, and ÿ y + y. there is
1/4
Pr Proj & 88)1112
uPe JeE]
1pp)
((4p)!)²
Proof. The proof here is similar to that of Lemma 11. Let m1, m2 my E X² be a set of orthonormal (in T2p Euclidean space) basis that spans M, and each my is symmetric. Then
Proj
@r SP)
(mi, (ror @ jzr))2. Let g( Σ (ms, (r 00))
m
or )P))
( m sr y )2p) for some tensor m (2)
,thnn
((x) is a homogeneous polynomial with order 4p. Notice that || (2) ||2 ||m, || by a change of
coordinate. For any initial value v and y. if I = x - and y = y 7. then J v and y. iJ are vectors
where the random part Vo R. J ~ NO, 1)a Therefore by Lemma 10,
Varz,v [0 ( 9
m
(4p)
i=1
m (2)
((4p)))²
((4p)))²
m
30

---

Under review as a conference paper at ICLR 2020
k
((4p)!)²
Hence from Proposition 2 we know that, when & N(),,
k
1/1
Pr
PProj (: 1 <
uPE
((pp)!)²
(4p))
9 Vo" v0) < S Opp)el12
Pr
Then show Lemma 2 as follows.
Lemma 2. Suppose k S Op(dP) and ((++-1) > n. let F. = =z 33 be the perturbed input in the smoothed analysis setting, where ãj ~ NN, vI), let (2., 2n3 be the output of the first layer on the perturbed inpul ((zz); = (rf))))). Let Z E BB*xxx xn be the matrix whose j-th column equal to 282, then with probability least 1 8, the smallest singular value of Z is at least Op (u //2
Actually, we show a more formal version which also states the dependency on p.
Lemma 13 (Smallest singular value for (Q&²) X with pertubation). With Q being the xP matrix defined as Q = [ri @p 122 ...... T S (r; ~ (O, I)), with pertubed X [ 82p ,T, ,2p,,t S2........
......... ..,, [2p]
(E; I; + T.), and with Z (Q Q)X, when Es drawn from ii.d Gaussian Distribution D
N(0, vl). for 2/
S D)("))
(d(d)), with overall probability 2 O(p8), the smallest
singular value
DD kD (P)1() n) [4pp)!}
1/4
8
Tmin 2
2
(4)
n 1/2
Proof. First, we show that with high probability, the projection of rows of Q & Q in the space of
degree 2p symmetric polynomials (in this proof we abuse the notation Projx?- (Q Ø Q) to denote the matrix with rows being the projection of rows of Q X Q onto the space in question) has rank kg = 1R+1), and moreover give bound on kb2 (Proj x2 (Q Q)).
We do this by bounding the leave one out distance of the rows of Proj x (Q @ Q), note that we only
consider rows (i.j) x (r: & (P) where < i < < le (this is because the (i, and (j, i) row of Projx3" (Q 39 Q) are clearly equal).
The main difficulty here is that different rows of Proj (Q 2 Q) can be correlated. We solve this problem using technique similar Ma al. (2016).
For any isijjs S k. fix the randomness for Tı where / j.j. Consider the subspace S(,,)) span ( (Proj (r X x S))) x E Rd. + i.j). The dimension of this subspace is bounded by
k DJ- (2x) (as there are (29) ways to place p copies of ri and p copies of x). Note that any other row of P (Q Q) must be in this subspace.
Now by Lemma 12, we know that the projection of row (i.j) onto the orthogonal subspace of S(
D2" (??
1/4
has norm
with probability 1/p) Thus by union bound on all the rows,
((4p)))²
with probability at least Opp5), the leave-one-out distance is at least
-
D2 - kD2
1/4
2p
((Prox (Q 8 (Q&Q)) 2
((D))))2
(K+1)
31

---

Under review as a conference paper at ICLR 2020
Prroj (Proj (QSQ)
and by Lemma the minimal absolute singular value amin (Proix;
(Q
Next, let VQQ @ Q) be the rowspace of Proix3" (Q @ Q), which as we just showed has dimension (<2)). We wish to show that the projections of columns of X in V(Q@Q) have large leave-one-out distance, and thus (Q & Q) has a large minimal singular value.
of VQQ&Q) orthogonal to spant + i} has dimension ( 2 ( -n+11 almost surely, and therefore by Lemma
Actually for each i, the subspace (which for simplicity will be denoted as
1l and union bound, with probability 1 - O(p) 1/2p = - O(po). for all i,
1/1
(Qso) = E [1PV ( (1 lla (3 #01 2
2 n
UPT,
(4p)
thus with probability 1 Opp)), for any vector E R² with |c|| 1, let 1" argmaz; (cs).
and Je-1 2 vi
II( Q)xxe1
min (Projx
x Q 2 Q)(c, ||lla-I||Poooj Projv X Te
M w min (Proj x20 Q3Q)
Projy (Q@Q)) (x lll
vn
1/1
[1p)
2041//2
And therefore we will get Lemma 13.
A minor requirement of on zy's is that they all have bounded norm. This is much easier to prove: Lemma 14 (Norm upper bound for @x Suppose that ||æ, S for all j E [n] and Ty Iy + R where i. ~ (O, vf). Same as the previous notation, Q = 8p .....,,,, Then with probability at least 1
' T E R
2m In( (n((=+-njdB-122(k44a)a) 1/2)(k+4)dd for all i E [n], we have
5
1 S vie 2BB + 2 ud Inl + n)d8 n))d6-122)) / d'mn(1s + n)dō 112) P
Proof. First we have, for a standard normal random variable N ~ NN 1), we have
V2
Pr[[N] 2 2)
N
Then, apply the union bound, we have with probability at least
v 2m (n) 1/2 4/3)(k+m))d' for
all I E [k), d E [m], d. 5 < 1, we have
((r)) S v (k - m)d6 (F,))d S v wwnn(n++n000) + 11)d-1122)
Then for all j E [n]], we have
||ā||| S ||0||2 + ||11|2 S B + 2 vd In(( + n))6- 1/2).
If for all E [4,1 E [k], ((ry)al < 2 2/in((k m)dō-1/2), then for any E such that ||||| S B +
2 /vd In(( + m)d8-112) 1/2) and any 7 [k]. have
((m) 000"" _ = =I(r7
<(Irx]] -|=||)
2(B + 2 ad vd -))8-1122))) /dI(((k + n)dd m))d8-122) 1/2) P
32

---

Under review as a conference paper at ICLR 2020
Then we have
p
11000112 s vi 2 2 udla((k + =))d8-111)) d'ln(kk + n)d6-1/2) -12b)-1)))))
Then combined with the previous lemmas which lower bound the smallest singular value(Lemma 13) and upper bound the norm(Lemma 14) of the outputs of the random feature layer and Theorem have the following Theorem
Theorem 5 (Main theorem for 3-layer NN). Suppose the original inputs satisfy || I 1, 1, S 1, imputs 3; = z + Ij are perturbed by ē; ~ (N,,, vf), with probability 1 - 8 over the random initialization, for
2[ /n,, perturbed gradient descent on the second layer weights achieves loss J(W') S in (1) (n/f) (n/e) iterations.
Proof. From the above lemmas, we know that with respective probability 1-0(1)6, after the random featuring, the following happens:
( (+++)))))))
1/4
1. miin mi 2 2)X)
[4p]!]
2. [Qu [n].
la S v (2 (2 (n)d6-1/2)) 1/2))///ln((())) ddn((k ())d661))))))))) for all j E
Thereby considering the PGD algorithm on W, since the random featuring outputs (r?{,
Q[= has [r]] α, 2r] = (Q @ Q) from Theorem 4, given the singular value condition and norm condition above we obtain the result in the theorem.
E.3 PROOF OF THEOREM 6
In this section, we show the proof of Theorem 6. In the setting of Theorem 6, we not add perturbation onto the samples, and the only randomness is the randomness of parameters in the random feature layer.
SP ... T We show that: when r; sampled from i.i.d. Normal distribution (0, 1)d and lt is large enough, with high probability Q is robustly e-net and o-net of X with size Ze and Zo.
Recall that Q E Axdd" is defined as Q 1r
,
full column rank. Let N: and N, be respectively
The following lemmas(Lemma 15, 16 and 17) apply the standard e-net argument and lead to the smallest singular value of matrix Q(Lemma 18). Then we will derive the smallest singular value for the matrix (Q & (Lemma 19).
Note that unlike the Q matrix in the previous section, in this section the Q matrix is going have more rows than columns, so it has full column rank (restricted to the symmetry of Q). The Q matrix in the previous section has full row rank. This is why could not use the same approach to bound the smallest singular value for Q.
Lemma 15. For some constant C, with probability at least - Ze (Cpn)//)* & for all e E No. we have
n²² p!
11eel2 >
Proof. For any c E XT by Lemma 6, ||c|hr 2 Ap! degree with respect to r, and therefore by Lemma 9,
Let f(r) = &r then f is polynomial of
Var (o0,)0
[f(r]] 2 ||a|| >
p!
33

---

Under review as a conference paper at ICLR 2020
Thus by Proposition 2,
Pr
{156)
< --)
_1
x 1(p)))/P
(0,11)
vpl
K Therefore, as ||Qc12 = Σ f(ri)?
1122 p!
{ Yr. 1f(r:)) <
"
<
Pr -i..nn
vp!
S ((6))))))))
Therefore for some constant C, for each E X2 with probability at most (Cpn there pr. Thus by union bound this happens for all E No with probability at most fe) and thereby the proof is completed.
|1Qelè < oi Ze
Lemma 16. For > with probability 1 - (126 (vx)
-0 (vz) 1/D ke - =+))
for each E No.
||Qcl22 T.
Proof. For any E X2.
Pr [112c112 > 2/s Q
Pr
3i lc 1
vkl
<k
Pr
10 102rep1
mmN(0,.1)
V
Furthermore,
Pr 1)d
10
Pr
||c|al1111
Vkl
10.
Vkl 5
1/P
Pr
|1rl12> >
vk.
1/p
Vk
e -
(vx)
2/0
Therefore for the a-net No, with union bound know with probability at least 2/0 (+x)
1/P
o
Zoo
be
for all E No. 5
Lemma 17. For o < 1, 1> 0, with probability at least 1 - of ( Zo [Kk] (xK) ke )²00)))) we
>
have for each E X2. ||Qel12 - --
Proof. We first show that give No. for each e E X we can find c,,2, E No and a1, a2 ......... E E such that
and that aj = 1,0 S 00;-1 (12 2). Thus S 5 In fact, we can construct the sequence by induction. Let I X3 N₂ that
I (xx)
argmin |/l z2/12- vEN.
34

---

Under review as a conference paper at ICLR 2020
We take 01 I(c), a1 and recursively
ajc
=
I
2
ai
By definition, for any c E X |c - [(c]l2 S a, and therefore
2==1 CgCj
Cj
S o,
a3
2
which shows that 0 S di+i ||c Σ d,eil2 S oa; and by induction a; _0'-1
We know from Lemma 16 that with probability at least 1 1
00 %
vk
1/p
he
-
(7)) for all
C E No. ||Qc/ll2 I r, and therefore
110cl12 S Σ aal1Qeell2
S Σ 0--- 21
7
1-o
121
Lemma 18 (least singular value of Q). IfQ is the k x d matrix defined as Q = 1r with r; drawn i...d from Gaussian Distribution (0. I), then there exists constant Go > 0 that for
20 ... T
.2
k apD' (ax >> 1), with probability at least 1 - o{1),, the rows of Q will span X d. and for all
c E X2
5 (1 bog
110cl12 2 Ω
Sp
(DP (DPVD!) -- (k(GoplnDD)))) 2(--1)
k: 2
where Opp is the big-St notation that treats p as a constant.
Proof. We show that with high probability, for all c E X2 ||0c|l
k = Σ
(1r:0]7 2
is large. To do
1=1
this we will adopt an s-net argument over all possible c. First, we take the parameters
1 10
T=VK
T=
(2108
2 k
Zaki P
and
E = (TDP Vp!)
(a-inay
8
for small constant such that CD DPDDe DTa-Ijo << 1, and know that with probability least
20
eT / pl. From Lemma 15 and 17, we g
1/8
1 - 2x (cpn)(10)*
Vk
be $ + )20
2n
=1 0 (000
(a- (a-1)Da Di D6) -0
5
V/2 log Zukk
=1 o11),
the following holds true:
1. Vc, Ne. 11Qca12 3
35

---

Under review as a conference paper at ICLR 2020
2. Vc E X |1Qc|12 $ 1-a zevp!"
Therefore for any c E ty let argmin
||e 0: cal12, we know
E.
[|Qcl2 2 2|Qai|1 |1Q(c c;)ll2
7
||c cill2
Q
Vp!
||c C: 1
"
Vp!
2Ev/!!
2vp!'
and by definition we know that Amin (Q) 2
2Vp!' By lemma 7, with log Zo O(plnpD)) S
Gop Dn for some constant Go. this gives us the lemma.
Lemma 19 (Smallest singular value for (Q @ Q)X without pertubation). With Q being the k x d' matrix defined as Q [rio, Sp ... @PpT. X being the der x matrix defined as X ( ....,,222p xdd and Z = (Q Q)X, for k = apD" (a 1), when Ti are randomly drawn from i.i.d. Guassian distribution (0, I), there exists constant Go > 0 such that with probability 2 011), the smallest singular value of satisfies
(o-bbpy)
O miin (X)
Tmin 2
Up
O (X)
(5)
(DP [k(Gop In p))
(where 22p is the big-St notation that treats p as a constant). Furthermore, for 22p2 D2), with
high probability 1 5, omin (Z) 2 21 ((min(()) (if is not exponentially small).
Proof. From Lemma 18, with probability 2 o(1)8, for all E X2. ||Qc|2
A
5 (1-1)
Ω
Then, from linear algebra, we know for all E X & X
(peVP!) --1 (k(Goplu Ia (D))))) 13
II(Q @ Q)s|l2 AZ, As X
X2 & X
Omin (Q 2 X)
inf
I[Q @ Q)Xu||z
EE 1ulla=1
inf "ER" ||
([Q 8 Q) T ||all Xulla A
inf wER ||
|uul|2 = A a (X);
which gives us this lemma 19.
Besides the lower bound for the smallest singular value, we also need the following lemma show that with high probability, the norm is upper bounded.
Lemma 20 (Norm upper bound for @r Suppose that ||r:|l2 S for all i E [n]. and Q [r ...... @rT T Then with probability at least have
2n 1o(kd6-11=jjkdd for all [n], we
1 S Vic / dim(kad- (22 P
Proof.
First we have, for a standard normal random variable N ~ N(0, 1), we have
V2 e
Pr[[N| 2 x}
<
//T
Then, apply the union bound, we have
V2
Pr 3i E [d].j [s], 17y)a 2 2 1n/n(kkd66///
<kd /
exp (-21n(kd88- -1/2))
1/12/In(kd) in(kdö-112
36

---

Under review as a conference paper at ICLR 2020
2T In(kdō 1/2)
for all [4]. E (M)1(1))d have
2//n(kel), then for any x such that ||=||| S B and any ko E [k]]
((Tko) )o8)) z000 =1r x))
<(1 1| |201))
<2BB d d'In(kdō-177
Then we have
|| 10 S vi 2Bv din(kdd-1/22)
Then, combining the previous lemmas and Theorem 4, we have the following Theorem
Theorem 6. Suppose the matrix X = [x ..... 2:1 _ has full column rank, and smallest singular value at least a. Choose O, with high probability perturbed gradient descent on
x
(x)) 6 log a (n/e) iterations.
the second layer weights achieves loss f(W*) S in (p()
Proof. From the above lemmas, we know that with respective probability 1 o(16, after the random featuring, the following happens:
1. There exists constant Go that T ((Q Q)X) 2
Lo- 11
Gmin (X)
(n²)T) ((GoplpDD)))) (a-1)
2a
2. 10 I (ln(kod 1/2)) for all j E [n].
Thereby considering the PGD algorithm on W, since the random featuring outputs [(rF',)' @1= has [(r] 22) pp] = (Q& Q)X, from Theorem 4, given the singular value condition and norm condition above we obtain the result in the theorem.
37


Reviews:
[{"review_id": "HJgMadUAYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The paper studies the amount of over-parameterization needed for a quadratic two (three) layer neural network to memorize a separable training data set with arbitrary labels. The main result of this paper shows that as long as the number of data in dimension d is smaller than d^2/2 and the data is separable by a quadratic function, then a fully connected two-layer neural network with quadratic activation function and 2d hidden neurons can memorize the training data set efficiently. \n\n\nThe intuition behind this result is quite simple: Given data x_1, ..., x_N with a matrix A in R^{d x d} such that x_i^T A^T A x_i = y_i, given the current weight matrix W one can always try to construct an Hessian update direction A' = U A for a column orthonormal matrix U such that x_i^T W^T U A x_i = 0 for every i and (by the property of U) x_i^T A'^TA'x_i = y_i. Note that U has more than d^2/2 degree of flexibility, so having x_i^T W^T U A x_i = 0 is in principle always possible. \n\n\nThe paper studies a very important question: How can neural network memorize data in the mildly over-parameterized regime (number of parameters is linear in the number of data). There is experimental evidence that in this regime, the neural network does memorize much better than its counterpart neural tangent kernel (NTK).\n\n\n\nMy main concern about this paper is the assumption that the data is separable by a quadratic function, which seems to be very restricted (although this is indeed a progress from those who assume linear separability of the data, e.g.  Brutzkus et al. arxiv:1710.10174,  Wang et al. arXiv:1808.04685 and Oymak & Soltanolkotabi 2019 which has a sub-optimal dependency on the condition number of the training data set). However, in the result such as Allen-Zhu et all, the only requirement is that every data has distance at least \\delta, and the final dependency is poly(1/\\delta), the assumption is necessary to memorize arbitrary labels over the data set. However, quadratic separable seems to be too strong for a general data set.\n\nIndeed, the authors argued that if the data set is noisy with N < d^2/2, then w.h.p. it is quadratic separable. However, if the network is really using those noise in the data to fit the labels, then one should expect NO GENERALIZATION GUARANTEE of the learnt network at all -- a result that is meaningless for the theory of deep learning.\n\nMissing citation:\nLearning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data\n\n\n\nAfter Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement. I agree that the smoothed analysis makes more sense than my original understanding. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1loxGgTYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "\nThis paper proves that one can design a (shallow)neural network that with a mild amount of overparametrization (e.g. the number of datapoints n is roughly less than d^2 in Theorem 1), a second-order method can reach a global minimum. In general, I think this is an interesting direction. However, I have some doubts regarding the comparison to prior work (especially regarding the results on the two-layer network), as well as some technical details that need some clarification. Regarding the quality of the writing, it’s in general ok but there are lots of grammatical mistakes, the authors should pay more attention to this. I’m not giving a high score for now but I will reconsider my review once I hear back from the authors.\n\nComparison to Oymak & Soltanolkotabi 2019: my understanding is that this paper prove convergence to a global minimum for a neural network where the number of parameters is only twice the number of datapoints so aren’t your results “worse” in that sense? The text in the related work seem to say the opposite, so I’m rather confused by your statement, please clarify.\n\nLandscape: I think this discussion is largely missing in the paper but another way to prove the same result would be to focus on showing that the loss surface is “well-behaved”. In fact the paper by Soltanolkotabi et al (see reference below) proves this for a similar network with a quadratic activation function and arbitrary data. Essentially, they show that such network obeys the following two properties:\nThere are no spurious local minima, i.e. all local minima are global.\nAll saddle points have a direction of strictly negative curvature\nMy understanding is that they prove this for a parametrization regime where n=d^2, isn’t this the same regime as proved in your results?\nMahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.\n\nThree-layer neural net\n1) This network uses activation function of the form x^p. You wrote “for some constant p”, is there any specific lower bound on p? I’m also surprised that one would allow large values of p as such functions have a saddle at x=0 with a large region with low gradient magnitudes around it.\n2) Limitation quadratic activation function. You say “To address this problem, the three-layer neural net in this section uses the first-layer as a random mapping of the input“. How is this helping with changing the activation function?\n3) You have to fix part of the weights of the network, this seems to be a limitation of the analysis that should be more clearly highlighted and better contrasted to what has been done in prior work.\n4) I think it would be interesting for the reader to focus more on the three layer network (instead of the two-layer one whose analysis is rather simple) and provide a more detailed proof sketch.\n\nPaper organization\nThe most interesting result of the paper is the one about the three-layer network but the entire analysis is relegated to the appendix. I feel it would be worth trying to provide a rough proof sketch in the main paper to highlight the difficulty of the analysis.\n\nProof Lemma 2\nAlternatively to the current proof, couldn’t you differentiate the second term (2/n \\sum_j (\\sum …)^2 ) w.r.t. z and show it is zero at the argmax_z? Isn’t this what your result says?\n\nExperiments\nConsider repeating the experiments a few times and showing the average.\n\nMinor: Low loss vs perfect fitting: I couldn’t find any discussion about this but the authors seem to assume that a zero loss directly implies that the training data is fit perfectly. In the case n=d, there exists a function that yields a perfect fit of the data and therefore a larger network should be able to represent this function. Perhaps it would be worth writing this down.\n\nMore minor comments\n- Figure experiments: please use a log scale\n- Formula top of page 16: should be z_k on the left and right of the term inside the bracket\n- missing citation top of page 24: “e.g. in”\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1l8dPX2KB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 studies the mildly over-parameterized neural networks. In particular, it shows that when the width is at least O(sqrt{n}) where n is the number of samples, PDG fits the training data. The analysis is done for 2-layer or 3-layer networks with (mainly) quadratic activations, with only one-layer weights (the weights before the quadratic activation) trainable. For 2-layer network, that means the first layer weights are trainable. Except for O(sqrt{n}) width, the other settings of this paper are quite restricted and it is not clear how it reflects the training of the neural networks.\n    The quadratic activation is probably the main limitation of this paper, and fixing the last layer is the second major limitation. There are already a few papers studying quadratic activations, some of them cited in this paper. But the closest one is probably a missing one: Soltanolkotabi et al. https://arxiv.org/pdf/1707.04926.pdf. It also only requires O(sqrt{n}) neurons. It seems the data assumption of that paper is stronger (Gaussian input), but in terms of the major claim of this paper on mild overparameterization, that paper already made an attempt. In addition, that paper optimizes both v and W (first and second layer weights), which is more practical than this paper.  \n   The title on “mild over-parameterized network” is a bit misleading. The paper tries to compare with “a series of work (Du et al. (2019); Allen-Zhu et al. (2019c); Chizat & Bach (2018); Jacot et al. (2018)” which uses a large number of neurons, and thus claims “mild over-parameterization”. However, this comparison seems to be a bit  unfair, because for shallow networks there are many papers that do not require that large number of neurons, which seem to be ignored by this paper, including Brutzkus et al. arxiv:1710.10174,  Wang et al. arXiv:1808.04685, Liang et al. arXiv:1803.00909,Zhang arXiv:1806.07808 (I guess there are more). The settings of these papers are not the same as the setting of the current paper, but the differences will need to be clarified if the authors want to claim “the first step towards mild overparameterized networks”. \n\n   The result on 3-layer projection with smoothed analysis is theoretically interesting. However, the 3-layer result is mainly for technical purpose (“restore representation power”), and does not provide much extra insight on algorithm performance --- the two-layer convergence result and the 1st layer projection are treated independently. It is not sure how useful this result will be, and how can this be extendable.  \n\n=========After rebuttal period, I found [Ref1] studied the same setting======\nAfter the rebuttal period, I found the reference [Ref1] I mentioned earlier does not need Gaussian assumption. In fact, Theorem 2.1 applies to almost all data, thus is the SAME setting as the 2-layer part of this paper. Theorem 2.5 of [Ref1] assumed Gaussian data, but that is not the major result of [Ref1]. \nThe 3-layer proof may still be interesting. The authors can address the differences with [Ref1] in a future version, and focus more on the 3-layer proof. Finally, it is possible that the regularizers make the proof different from [Ref1], but that requires much effort to explain (I think even there is a difference, it is probably not a major innovation). \n\n[Ref1] Theoretical insights into the optimization landscape of\nover-parameterized shallow neural networks\n\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the amount of over-parameterization needed for a quadratic 2 /3 layer neural network to memorize a separable training data set with arbitrary labels. While the reviewers agree that this paper contains interesting results, the review process uncovered highly related prior work, which requires a major revision to put the current paper into perspective and generally various clarifications. The paper will benefit from a revision and resubmission to another venue, and is in its current form not ready for acceptance at ICLR-2020.
Decision: Reject