Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
Authors: Yu Bai
Jason D. Lee
Venue:  (2020)
Keywords: Neural Tangent Kernels
over-parametrized neural networks
deep learning theory

Abstract: Recent theoretical work has established connections between over-parametrized neural networks and linearized models governed by the Neural Tangent Kernels (NTKs). NTK theory leads to concrete convergence and generalization results, yet the empirical performance of neural networks are observed to exceed their linearized models, suggesting insufficiency of this theory.
Towards closing this gap, we investigate the training of over-parametrized neural networks that are beyond the NTK regime yet still governed by the Taylor expansion of the network. We bring forward the idea of randomizing the neural networks, which allows them to escape their NTK and couple with quadratic models. We show that the optimization landscape of randomized two-layer networks are nice and amenable to escaping-saddle algorithms. We prove concrete generalization and expressivity results on these randomized networks, which lead to sample complexity bounds (of learning certain simple functions) that match the NTK and can in addition be better by a dimension factor when mild distributional assumptions are present. We demonstrate that our randomization technique can be generalized systematically beyond the quadratic case, by using it to find networks that are coupled with higher-order terms in their Taylor series.


Published as a conference paper at ICLR 2020
BEYOND LINEARIZATION: ON QUADRATIC AND HIGHER-ORDER APPROXIMATION OF WIDE NEURAL
NETWORKS
Yu Bai
Jason D. Lee
Salesforce Research wu.bai@ealeesforce.com
Princeton University
jasonlee@prinneeton.cdl
ABSTRACT
Recent theoretical work has established connections between over over-pavanee parametrized neural networks and linearized models governed by the Neural Tangent Kernels (NTKs). NTK theory leads to concrete convergence and generalization results, yet the empirical performance of neural networks are observed to exceed their linearized models, suggesting insufficiency of this theory.
Towards closing this gap, we investigate the training of peremaaraetti neu- ral networks that are beyond the NTK regime yet still governed by the Taylor expansion of the network. We bring forward the idea of randomizing the neu- ral networks, which allows them to escape their NTK and couple with quadratic models. We show that the optimization landscape of randomized two-layer net- works are nice and amenable to escaping- saddle algorithms. We prove concrete generalization and expressivity results on these randomized networks, which lead to sample complexity bounds (of learning certain simple functions) that match the NTK and can in addition be better by a dimension factor when mild distributional assumptions present. We demonstrate that our randomization technique can be generalized systematically beyond the quadratic case, by using it to find networks that are coupled with higher-order terms in their Taylor series.
INTRODUCTION
Deep Learning has made remarkable impact on variety of artificial intelligence applications such as computer vision, reinforcement learning, and natural language processing. Though immensely successful, theoretical understanding of deep learning lags behind. It is not understood how non- linear neural networks can be efficiently trained to approximate complex decision boundaries with a relatively few number of training samples.
There has been a recent surge of research on connecting neural networks trained via gradient descent with the neural tangent kernel (NTK) (Jacot et al., 2018; Du et al., 201 8a;b; Chizat & Bach, 201 8b; Allen-Zhu et al., 2018a; Arora et al., 2019a:b). This line of analysis proceeds by coupling the training dynamics of the nonlinear network with the training dynamies of its linearization in local neighborhood of the initialization, and then analyzing the expressiveness and generalization of the network via the corresponding properties of its linearized model.
Though powerful, NTK is not yet completely satisfying theory for explaining the success of deep learning in practice. In theory. the expressive power of the linearized model roughly the same as, and thus limited to, that of the corresponding random feature space (Allen-Zhu et al., 2018a; Wei al., 2019) or the Reproducing Kernel Hilbert Space (RKHS) (Bietti & Mairal, 2019). While these spaces can approximate any regular (e.g. bounded Lipschitz) function up to arbitrary accu- racy, the norm of the approximators can be exponentially large in the feature dimension for certain non-smooth but very simple functions such as single ReLU (Yehudai & Shamir, 2019). Using NTK analyses, the sample complexity bound for learning these functions can be poor whereas ex- perimental evidence suggests that the sample complexity is mild (Livni et al., 2014). In practice, kernel machines with the NTK have been experimentally demonstrated to yield competitive results on large-scale tasks such image classification on CIFAR-10; yet there is still non-neglible per-

---

Published as a conference paper at ICLR 2020
formance gap between NTK and full training on the same convolutional architecture (Arora et al., 2019a; Lee et al., 2019). It is an increasingly compelling question whether we can establish theories for training neural networks beyond the NTK regime.
In this paper, we study the optimization and generalization of over pre--paraettizeed two-layer neural networks via relating to their higher-order approximations, a principled generalization of the NTK. Our theory starts from the fact that a two-layer neural network /wo+w(x)) (with smooth activation) can be Taylor expanded with respect the weight matrix W as
m
g(k) (w)
fwo+w(x) = Σ a,o((wo.r + w.) wx))x)) = Σ a (w
(w x)*
Op
k!
fx)
Wa WW..w/ (x)
Above, fw. does not depend on W, and f()) corresponds to the NTK model, which is the dominant W-dependent term when { [w,} are small and leads to the coupling between the gradient dynamics for training neural net and its NTK f()).
Our key observation is that the dominance of f()) is deduced from comparing the upper bounds rather than the actual values-of JW.. (x). a priori possible that there exists subset of W's in which the dominating term is not f()) but some other ((),, k 2 2. If we were able to train in that set, the gradient dynamics would be coupled with the dynamics on f(k rather than f() and thus could be very different. That learning is coupled with f(()) could further offer possibilities for expressing certain functions with parameters of lower complexities, or generalizing better, as f()) no longer a linearized model. In this paper, we build this perspective and identify concrete regimes in which neural net learning is coupled with higher-order f(k)'s 's rather than its linearization.
The contribution of this paper can be summarized as follows.
We demonstrate that after randomization, the linear NTK f(l) is no longer the dominant term, and so the gradient dynamics of the neural net is no longer coupled with NTK. Through simple sign randomization, the training loss of an werrpparmeerrized two-layer neural network can be coupled with that of a quadratic model (Section 3). We prove that the randomized neural net loss exhibits nice optimization landscape in that every second-order stationary point has training loss not much higher than the best quadratic model, making amenable efficient minimization (Section 4).
We establish results on the generalization and expressive power of such randomized neural nets (Section 5). These results lead to sample complexity bounds for learning certain simple functions that matches the NTK without distributional assumptions and are advantageous when mild isotropic assumptions on the feature are present. In particular, using randomized networks, the sample com- plexity bound for learning polynomials (and their linear combination) on (relatively) uniform base distributions is (d) lower than using NTK.
We show that the randomization technique can be generalized to find neural nets that are domi- nated by the k-th order term in their Taylor series (k > 2) which term higher-order NTKs. These models also have expressive power similar as the linear NTK, and potentially even better generalization and sample complexity (Section 6 & Appendix D).
1.1
PRIOR WORK
We review prior work on the optimization, generalization, and expressivity of neural networks.
Neural Net and Kernel Methods Neal (1996) first proposed the connection between infinite- width networks and kernel methods. Later work (Daniely et al., 2016; Williams, 1997; Lee et al., 2018; Novak et al., 2019; Matthews et al., 2018) extended this connection to various settings includ- ing deep networks and deep convolutional networks. These works established that gradient descent on only the output layer weights is well-approximated by a kernel method for large width.
More recently, several groups discovered the connection between gradient descent on all the param- eters and the neural tangent kernel (Jacot et al., 2018). Li & Liang (2018); Du et al. (2018b) utilized the coupling of the gradient dynamics prove that gradient descent finds global minimizers of the
2

---

Published as a conference paper at ICLR 2020
training loss of two-layer networks, and Du et al. (2018a); Allen-Zhu et al. (2018b); Zou et al. (2018) generalized this to deep residual and convolutional networks. Using the NTK coupling, Arora et al. (2019b); Cao & Gu (2019a;b) proved generalization error bounds that match the kernel method.
Despite the close theoretical connection between NTK and training deep networks, Arora et al. (2019a); Lee et al. (2019); Chizat & Bach (2018b) empirically found a significant performance gap between NTK and actual training. This gap has been theoretically studied in Wei et al. (2019); Allen- Zhu & Li (2019); Yehudai & Shamir (2019); Ghorbani al. (2019a) which established that NTK has provably higher generalization error than training the neural net for specific data distributions and architectures.
The idea of randomization is initiated by Allen-Zhu et al. (2018a), who use randomization to prov- ably learn three-layer network; however is unclear how the sample complexity of their algorithm compares against the NTK. Inspired by their work, we study the potential gains of coupling with a non-linear approximation over the linear NTK - we compare the performance of quadratic approximation model with the linear NTK on two-layer networks and find that under mild data assumptions the quadratic approximation reduces sample complexity under mild data assumptions.
believed that the success of SGD is largely due to its algorithmic regularization effects. A large body of work Li et al. (2017); Nacson et al. (2019); Gunasekar et al. (2018b;a; 2017); Woodworth et al. (2019) shows that asymptotically gradient descent converges to a max-margin solution with strong regularization effect, unlike the NTK regularization'.
Outside the NTK Regime
For two-layer networks, series of works used the mean field method to establish the evolution of the network parameters via Wasserstein gradient flow (Mei et al., 201 8b; Chizat & Bach, 201 8a; Wei et al., 2018; Rotskoff & Vanden- Eijjnenn, 2018; Sirignano & Spiliopoulos. 20 2018). In the mean field regime, the parameters move significantly from their initialization, unlike NTK regime, however is unclear if the dynamics converge to solutions of low training loss.
Finally, Li et al. (2019) showed how a combination of large learning rate and injected noise amplifies the regularization from the noise and outperforms the NTK of the corresponding architecture.
Landscape Analysis Many prior works have tried to establish favorable landscape properties such as every local minimum is a global minimum (Ge et al., 2017: Du & Lee, 2018: Soltanolkotabi et al., 2018; Hardt & Ma, 2016; Freeman & Bruna, 2016; Nguyen & Hein, 2017a;b; Haeffele & Vidal, 2015; Venturi et al., 2018). Combining with existing advances in gradient descent avoiding saddle- points (Ge et al., 2015; Lee et al., 2016; Jin al., 2017). these show that gradient descent find the global minimum. Notably, Du & Lee (2018); Ge et al. (2017) show that gradient descent converges solutions also of low test error, with lower sample complexity than their corresponding NTKs.
Complexity Bounds Recently, researchers have studied norm-based generalization based (Bartlett et al., 2017; Neyshabur et al., 2015; Golowich et al., 2017), tighter compression-basee bounds (Arora al., 2018), and PAC-Bayes bounds (Dziugaite Roy, 2017; Neyshabur al., 2017) that identify properties of the parameter that allow for efficient generalization.
PRELIMINARIES
Problem setup
We consider the standard supervised learning task, in which we are given labeled dataset D = {x1, V1 ....... (x..,. }. where (æ,, yi) E X' x y are sampled i.i.d. from some distribution P. and we wish find a predictor f X y. Without loss of generality, we assume that X gd (Bx) C Rd for some B2 0 (so that the features are d-dimensional with norm Bz.)
Let : y x RR + R20 be a loss function such that Ely, 0) < 1, and = + E(y, =) convex, 1- Lipschitz, and three-times differentiable with the second and third derivatives bounded by one for
As concrete example, Woodworth et al. (2019) showed that for matrix completion the NTK solution estimates zero on all unobserved entries and the max-margin solution corresponds to the minimum nuclear solution.
3

---

Published as a conference paper at ICLR 2020
all y y. This includes for example the logistic and soft hinge loss for classification. We let
L(f) = EDle(,, f(x)) Σ Cyv. f(x,)) and Lp(f) == ((xx))-r(((( f(x))
denote respectively the empirical risk and population risk for any predictor x y.
Over Over-parametrized two-layer neural network layer neural network of the form
We consider learning an over-parametrized two-
TaTooWTx fw(x) (x) m
a (w, (w,x),
V
where W = -[ wr] E Rdx is the first layer and a = [A1..... am. E Rm is the second layer. The 1/ym m factor is chosen to account for the effect of over-voeraaat wver-parametrization and consistent with the -TK-type scaling of (Du et al., 2018b; Arora et al., 2019b). In this paper we fix and only train W (and thus use fw to denote the network.)
Throughout this paper we assume that the activation is second-order smooth in the following sense. Assumption A (Smooth activation). The activation function (R)), and there exists some absolute constant C such that |o' (t)) v Ct |o" [t) S Cl and o") is C-Lipschitz.
An example is the cubic ReLU (t) relu (t) max ft, 0} The reason for requiring o to be higher-order smooth (and thus excluding ReLU) will be made clear in the subsequent text².
2.1 NOTATION
typically reserve lowercases a, b, at B,... for scalars, bold lowercases a, b, ar B,... for vec- tors, and bold uppercases A, B, for matrices. For matrix A [a...... am E Rdxm its 12))// 1/P for all E [o]. In particular we have 11-112.2 |1-1lF. We let B,,, (R) == ( [W Wl2.,pp I R} denote 2, p-nrm ball of radius R. We use standard Big-Oh notation:
2, norm defined as || = (E ||a, (12)
O(b) for stating a S Cb for some absolute constant C > 0, and (b)) for S Ch where C depends most logarithmically in b and all other problem parameters. For a twice-difierentiable function f IRd - RR x, is called a second-order stationary point if if (x..) and 2 fxx)) ž O.
ESCAPING NTK VIA RANDOMIZATION
To motivate our study, we now briefly review the NTK theory for over over- wer-parametrized neural nets and provide insights how to go beyond the NTK regime.
Let Wo denote the weights in a two-layer neural network at initialization and W denote its move- ment from W, (so that the current weight matrix is Wo + W.) The observation in NTK theory, or the theory of lazy training (Chizat & Bach, 2018b), is that for small W the neural network fwotW can be Taylor expanded as
fwo+w(x) Vm
Σ a,o((Wo.r + w,) x))
rsm
Σ rSm
a (wo
Σ a ( rsm
1 Vm
E (w, x)2 rSm
mm
Vm
fx)
We note that the only restrictive requirement in Assumption A is the Lipschitzness of o" which guarantees second-order smoothness of the objectives. The hounds on derivatives (and specifically their bound near zer) merely for technical convenience and he weakened without hurting the results.
4

---

Published as a conference paper at ICLR 2020
so that the network can be decomposed the sum of the initial network fwo, the linearized model Jw and higher order terms. Specifically (ignoring fw. for the moment), when m is large and ||wll22 = (m22//2, we expect fW = (1) and higher order terms to be Om (1), which in- deed the regime when train fWo+W via gradient descent. Therefore, the trajectory of training fwo+w is coupled with the trajectory of training fw, + Ww. which is a convex problem and enjoys convergence guarantees (Du et al., 2018b).
Our goal is to find subsets of W so that the dominating term is not p but something else in the higher order part. The above expansion makes clear that this cannot be achieved through simple fixes such as tuning the leading scale 1/ ym or the learning rate - the domination of ft. appears to hold so long as the movements w, are small.
Randomized coupling with quadratic model We now explain how the idea of randomization, initiated in (Allen-Zhu et al., 2018a), can help get rid of the domination of f". Let W be a fixed weight matrix. Suppose for each weight vector wy, sample random variable Eyr E R and consider instead the random weight matrix
WE == ('diaa((EEr),")))) [Σ, W w.... E., w,l
then the second-order Taylor expansion of /Wo+WS be written
fwo+ws(x)) = 1
aro( + Errrr xx)
m
m Σ r=1
(x)
Σ
a o x) XE,, + 2/m
a,o
x)² +....
mm
= (x)
(x)
where we have defined in addition the quadratic part SWE- Due to the existence of {E,r), each original weight w, now has an additional scalar that is different in ft and fl, Specifically, if choose
Sid Uni
Enp
(2)
to be random signs, then we have D = and thus ( = (x), whereas E[Σ,,, so that W (x)] = O. Consequently, / is not affected by such randomization whereas wW is now mean zero and thus can have substantially lower magnitude than fW
More precisely, when ||w,ll2 x mmmmm11m 1/4 the scalings of ft and fc compare as follows:
We have [x(
(x)] = and
Ex ((WW(())² 1 a3 (w),)))((w x)² =0 0
1 = =0(m -1/2),
so we expect (wx((x) 00 11/1) over random draw of Σ.
The quadratic part scales
(x) = 12 (x) 2/m
Σ a,0" (w x)(, x)2 x)===x===00
W wr 0(1).
Therefore, the random weight matrix WE, 1 dominates fz and thus the network is coupled with its quadratic part rather than the linear NTK.
3.1 LEARNING RANDOMIZED NEURAL NETS
The randomization technique leads to the following recipe for learning W: train W so that ||w,ll2 = O( -1/4) and WE has in expectation low loss. We make this precise by formulating the problem minimizing randomized neural net risk.
5

---

Published as a conference paper at ICLR 2020
Randomized risk
Let L Rdxm - R denote the vanilla empirical risk for learning fw:
L(w) Ep [f(y, fwo+ (x)),,
where we have reparametrized the weight matrix into Wo + W so that learning starts at W = 0.
Following our randomization recipe, we now formulate our problem as minimizing the expected risk
L(W) == Ex([(WE)) Ey,D [e(y, fwo+we(x))],
where Σ E Rmxm is a diagonal matrix with Err üd Uni To encourage || wrll2 = ((m and improve generalization, consider regularized version of L and L with 22 regularization:
Lx(W) L(W) | and (w( L(W) + A || 2,1 Eg|Lx (WE).
Our regularizer penalizes W, ie. the distance from initialization, similar in (Hu al., 2019).
Symmetric initialization
We initialize the parameters (a, Wo) randomly in the following way: am
a1
0m/2 +1, 0m/2+1 1a), lid N(0, B_ Ia), Vr [m/2].
(3)
Wü,r Wo.++m/2 Above, we set half of the a, 's as +1 and half as -1, and the weights wo,r are i.i.d. in the +1 half and copied exactly into the half. Such an initialization almost equivalent to i.i.d. random Wo. but has the additional benefit that fw, (x) = O and also leads to simple expressivity arguments. Our initialization scale B_² chosen so that for random draw of wo, we have w, x N(O, 1), which is on average (11)*, For technical convenience, we also assume henceforth that the realized {worr) satisfies the bound
max (B [Wo,r =0 rE(m]
0 =o(vd- log(m/)) Ō(Va).
(4)
This happens with probability least 1 ô under random initialization (see proof Appendix A.3), and ensures that e[mm / s Ö(Vd) simultancously for all x.
OPTIMIZATION
In this section, we show that LA enjoys nice optimization landscape.
4.1 NICE LANDSCAPE OF CLEAN RISK
As the randomized loss L induces coupling of the neural net Jw,+ws wE with the quadratic model 1 expect its behavior to resemble the behavior of gradient descent the following clean risk:
n Σ
(xxx] WD.WT)).
L
ely,, f (x:)
y/s
n2
2/m
Above, have defined diagonal matrices D; diag( (a,0" (wo,, (wo, re(m) E mm which not trained.
We now show that the clean risk L albeit non-convex, possesses nice optimization landscape.
Lemma (Landscape of clean risk). Suppose there exists W, E Rdxm such that L ( x OPT.
Let Σ' E Rmxx be diagonal matrix with E,,, ädd Unif(+1), then we have
Ex (' E', w.E'|
(5)
< <VL* W) - ((L OPT) + Ō dB W | I1- m-1)
Our specific choice of |1-1l norm is needed for measuring the average magnitude of 2 whereas the high (8-th) power not essential and can be replaced by any (4 e)-th power without affecting the result. *Our choice covers commonly used scales in neural analyses: BN Wa.r N(O, Ia) in e.g. (Arora al., 2019b; Allen-Zhu et al., 2018a); B₂ Vd, wo,r N(0, (d/) in e.g. (Ghorbani et al., 2019h).

---

Published as a conference paper at ICLR 2020
This result implies that, for W in certain ball and large m, every point of higher loss than W. will have either a first-order or a second-order descent direction. In other words, every approximate second-order stationary point of _ is also approximate global minimum. Our proof utilizes the fact that T similar to the loss function in matrix sensing / learning quadratic neural networks, and builds recent understandings that the landscapes of these problems often nice (Soltanolkotabi et al., 2018; Du & Lee, 2018 8; Allen-Zhu et al., 2018a). The proof is deferred to Appendix B.I.
4.2 NICE LANDSCAPE OF RANDOMIZED NEURAL NET RISK
With the coupling between fwo+wE(X) and F in hand, we expect the risk L(W)
E[L(WE)) to enjoy similar guarantees as the clean risk does (?(W) in Lemma We make this precise in the following result.
Theorem (Landscape of L). Suppose there exists W. E B2,1( (Bu,,) such that L (W.))) & OPT, and that
m 2 O[[[[] B + d BB + d B2 B=l -4 + d BB, 3). for some fixed (0, 1] and B Bu, then for all W B2, B2,a(Bu).. we have
(6)
Ey V W.E ,.E, S (VL(W), W) 2(L( OPT) +
As an immediate corollary, we have a similar characterization of the regularized loss L2- Corollary (Landscape of Lx). For any B 2 Bu,,, under the conditions of Theorem we have for all X > 0 and all W (B.) that
Ex
E', W.
(8)
S (VLx(W). W) - ((L)(W)) OPT) [ + CA 1. +
where C = 0(1 is an absolute constant.
Theorem 2 follows directly from Lemma 1 through the coupling between L and L (as well as their gradients and Hessians). Corollary then follows by controlling in addition the effect of the regularizer. The full proof of Theorem and Corollary are deferred Appendices B.4 and B.5.
We now present our main optimization result, which follows directly from Corollary 3. Theorem 4 (Optimization of Lx). Suppose there exists W, such that
( < OPT and |W+ll2,4 S Bu.+
for some OPT O. For any γ (11) and > O, we can choose X suitably and m 2 (poly(d, Bg Bu,,, 1)) such that the regularized loss Lx satisfies the following: any second order stationary point W has low loss and bounded norm:
Lx( s (1 + 7)PPT + aand
W
< O(ww,))).
(10)
2,4
Proof sketch. The proof of Theorem 4 consists of two stages: first "localize" any second-order sta- tionary point into a (potentially very big) norm ball using the 11-11,, regularizer, then use Corollary in this ball to further deduce that T, is low and to Appendix B.6.
W
2,4 < O(1[W+ll2.)) The full proof is deferred
Efficient optimization & allowing large learning rate Theorem 4 states that when the over- parametrization is enough, any second-order stationary point (SOSP) W of LA has loss competitive with OPT, the performance of best quadratic model. Consequently, algorithms that are able to find SOSPs (escape saddles) such as noisy SGD (Jin et al., 2019) can efficiently minimize Lx to up to a multiplicative / additive factor of OPT. Further, by sampling a fresh Σ at each iteration and using the stochastic gradient Lx (WE) (rather than computing the full (L))W)). the noisy SGD iterates can be computed efficiently. We note in passing that our coupling results work in any 22,4 ball of (11) size further allows the use of a large learning rate: as soon as the learning rate is bounded by 0/4) we would have ||Wella, S O(1) in a constant number of iterations, and thus our coupling and landscape results would hold. This is in contrast with the NTK regime which requires the learning rate be bounded by (11) (Du et al., 2018b).
7

---

Published as a conference paper at ICLR 2020
5 GENERALIZATION AND EXPRESSIVITY
We now shift attention to studying the generalization and expressivity of the (randomized) neural net W learned in Theorem 4.
5.1
GENERALIZATION
As W always coupled (through randomization) with the quadratic model 1 w ing the generalization the quadratic model.
we begin by study-
Generalization of quadratic models
Let
(Bx) = ( (x)x): [ 2,1 S B
denote the class of quadratic models for W in a 62,4 ball. We first present a lemma that relates the Rademacher complexity of F (B.) to the expected operator norm certain feature maps. Lemma 5 (Bounding generalization of f via feature operator norm). For any non-negative loss such that z + E(y, I-Lipschitz and E(y, 0) S 1 for all y Y, we have the Rademacher complexity bound
n Σ nt
Exxx
sup
Σ o, (W()))
BaE
max remm
o, (wo,
(wi,)x;
+
IIW|
S.,
n
Vn
op
where 0g iid
Unif(=1) are Rademacher variables.
Operator norm based generalization Lemma 5 suggests possibility for the quadratic model to generalize better than the NTK model: the Rademacher complexity of j (B..) depends on "feature maps" 1 E o.o"(w,) (wo,-x,)xxxx through their matrix operator norm. Compared with the (naive) Frobenius norm based generalization bounds, the operator norm is never worse and can be better when additional structure x is present. The proof of Lemma is deferred to Appendix C.I.
We now state our main generalization bound on the (randomized) neural net loss L, which con- cretizes the above insight.
Theorem (Generalization of randomized neural net loss). For any data-dependen such that
W
Bur have
2,4
Ew, ((W) Lr(W) & sō
B2 B2B² B2 Ma.op
1
+ BBB
111 B -1/2)
+
Vn
where Ms == B [ E x l1 lloo)) 1 is the (rescaled) operator norm of the empiri-
1/2
cal covariance matrix. In particular, Mr always holds; in addition v x is K Var(v x) sub-Gaussian for all v E gd-1(1) and =(Cov(x)) S K, then Mz,op S x/V2 whenever O(K4)).
The generalization bound in Theorem 6 features two desirable properties:
(1) For large m (e.g. m 2, n²4), the bound scales at most logarithmically with the width m, therefore allowing learning with small samples and extreme parametrization:
(2) The main term Õ B bution and can lower the generalization error than the naive bound by at most O(1/Vd) without requiring us to tune any hyperparameter. Concretely, we have Mz,op < O(L/Vd) when x has an isotropic distribution such as (nd"(s" Unif(=B./Val
Vn)) automatically adapts to properties of the feature distri-
Theorem follows directly from Lemma 5 and matrix concentration Lemma. The proof is deferred to Appendix C.2.
8

---

Published as a conference paper at ICLR 2020
5.2 EXPRESSIVITY AND SAMPLE COMPLEXITY THROUGH QUADRATIC MODELS
In order to concretize our generalization result, we now study the expressive power of quadratic models through the concrete example of learning functions of the form Σjςt aj (5} x) ie. sum of "one-directional" polynomials (for consistency and comparability with (Arora al., 2019b).) generated according the symmetric initialization (3) and we use (t) =rell" (so that o" relu(().)
Theorem 7 (Expressing sum of polynomials through fQ). Suppose ((ar, Wo,r))
0z (3) x)"; achieves training loss L(f+) x) I co. where pj 2 E {1} U (20 Then so long as the width is sufficiently large:
If fx) = وز=
k m 2 ndl Σ (133,111
223
we have with probability at least 1 (over Wo) that there exists W. E Rdxm such that
L S OPT = co co+ te and | S By, =0
p p a
B
220, || 2p, 8-1
The proof of Theorem 7 is based on a reduction from expressing degree p polynomials using quadratic models to expressing degree 2 polynomials using random feature models. The proof can be found in Appendix C.4.
Comparison between quadratic and linearized (NTK) models We now illustrate results in Theorem 6 and 7 in three concrete examples, in which we compare the sample complexity bounds of the randomized (quadratic) network and the linear NTK when m is sufficiently large.
Learning a single polynomial. Suppose (x) a(B x)P satisfies L(fa) S e, and we wish to find W with OEe) test loss. By Theorem 7
choose W. such that (?(WW) < OPT 2e, and by Theorem 4 we can find W such that L(W)= S Lx (W) S 3e and [ ||2.4 = (B,,,). Take B, 1, and assume is sufficiently isotropic so that Mz,op O (2))))))) the sample complexity from Theorem 6 is
B B
M2
= =0(=0²
131
n 2 σ
: nq-
dea
In contrast, the sample complexity for linear NTK (Arora et al., 2019b; Cao & Gu, 2019a) to reach c test loss is
ō Saaaaaa111 2p
We have no/mn. = (pp/d), a reduction by dimension factor unless p = d. We note that the above comparison is simply comparing upper bounds, since in general the lower bound the sample complexity of linear NTK is unknown.
Learning noisy 2-XOR. Wei et al. (2019) established a sample complexity lower bound of linear NTK of n 2 ny = Q(d)) to achieve constant generalization error on the noisy 2-XOR problem, which allows for rigorous comparison against the quadratic model.
The ground truth function in 2-XOR is (x) = xi = ([(e) + Tx|² - [(e: - Tx|²) /4, where {+1) and f. attains constant margin the training distribution constructed in Wei (2019). By Theorem 7, f. can be e-approximated by f& with B < 0(1). Thus by
Theorem 6 the sample complexity for learning noisy 2-XOR through the randomized net W is
Ba
M w.
n no nn= Ō
2,0p
=ō
This is Ö(d) better than the sample complexity lower bound of linear NTK and thus provably better.

---

Published as a conference paper at ICLR 2020
Low-rank matrix sensing. Suppose wish to lear symmetric low-rank matrix A, E Rdxd with ||A,.lop I and rank(A.) Σ through n rank-one observations of the form y: = f fx,) = (A,, where x Unif(Su-1( Ej=1 az (vj x2 where |ayl I 1 are the eigenvalues A and V, R are the corresponding eigenveetors. For any 1-Lipschitz loss such as the absolute loss, by Theorem 7, there exists W, such that (W.) S OPT = and B & Orr Σÿ= (|v) = (r²)) Thus by Theorem 6, the sample complexity of reaching test loss
This ground truth function can be written as fx,)
Ex xx, fw(x)]] S 2e
through the randomized net W is
n = Ō
B B4 M2 uz 2²
s.op
=
dr
2
This compares favorably against the sample complexity upper bound for linear NTK, which needs
B1
Ō d (
mz
samples.
HIGHER-ORDER NTKS
We demonstrate that our idea of randomization for changing the dynamics learning neural net- works can be generalized systematically through randomization parametrized neural networks in which the k-th order term dominates the Taylor series. Due to space constraints, we provide our concrete results on the coupling, generalization, and expressivity of higher-ordes models in Appendix D.
able obtain over-
7 CONCLUSION
In this paper we proposed and studied the optimization and generalization of paramearreet neu- ral networks through coupling with higher-order terms in their Taylor series. Through coupling with the quadratic model, we showed that the randomized two-layer neural net has a nice optimization landscape (every second-order stationary point has low loss) and is thus amenable to efficient min- imization through escape-sauee saddle style algorithms. These networks enjoy the same expressivity and generalization guarantees as linearized models but in addition can generalize better by dimension factor when distributional assumptions are present. We extended idea of randomization to show the existence of neural networks whose Taylor series is dominated by the k-th order term.
We believe our work brings number of open questions, such as how to better utilize the ex- pressivity of quadratic models, whether the study of higher-order expansions can lead to more satisfying theory for explaining the success full training. We also note that the Taylor series is only avenue obtaining accurate approximations of nonlinear neural networks. It would be of interest to design other approximation schemes for neural networks that are coupled with the network in larger regions of the parameter space.
ACKNOWLEDGMENT
The authors would like to thank Wei Hu, Tengyu Ma, Song Mei, and Andrea Montanari for their insightful comments. JDL acknowledges support of the ARO under MURI Award 19--N--11-1- 0303, the Sloan Research Fellowship. and NSF CCF #1900145. The authors also thank the Simons Institute Summer 2019 program the Foundations of Deep Learning, and the Institute of Advanced Studies Special Year on Optimization. Statistics, and Theoretical Machine Learning for hosting the authors.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:/905. 10337, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li. and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. arXiv preprint arXiv: 1.0091998 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv:1811.0 1.3962, 2018b.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv:1802.05226. 2018.
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 arXiv: /904. 1955, 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprini /901v: 2019b.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaaizee normalized margin bounds for neural networks. In Advances in Newral Information Processing Systems, pp. 6241-6250, 2017.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint arXiv:190..1217, 2019.
Yuan Cao and Quanquan Gu. Generalization error bounds of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1rXiv:192..01384. 2019a.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint arXiv: 13210, 2019b.
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. 3040-3050, 2018a.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv: ///2.////7778 2018b.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2261, 2016.
Simon S Du and Jason D Lee. On the power of over parametrization in neural networks with quadratic activation. arXiv preprint arXiv:1803.0 10t..00030.006,,.. 2018
Simon Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. arXiv preprint 181iv:1811.0 1.08804 2018a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes 2018b.
over-parameterized neural networks. arXiv preprinl
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: I 1008, 2017.
Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimization. arXiv preprint arXiv: 16/ 1.05500, 2016.
Rong Ge. Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. In Proceedings of The 28th Conference on Learning Theory, pp. 797-842, 2015.
11

---

Published as a conference paper at ICLR 2020
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hideen-laee neural networks with landscape design. arXiv preprint arXiv:1711.00501, 2017.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural networks. arXiv preprint arXiv: 00Xiv::900.00 006608899, 2019a.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv: /2/91, 2019b.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXiv: 2017.
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.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. arXiv preprint arXiv:1802.08246, 2018a.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018b.
Benjamin D Haeffele and René Vidal. Global optimality in tensor factorization, deep learning, and beyond. arXiv preprint 1rXiv:1506.07544 2015.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. arXiv preprint arXiv:1611.0422 2016.
Wei Hu, Zhiyuan Li, and Dingli Yu. Understanding generalization of deep neural networks trained with noisy labels. arXiv preprint arXiv: 1et.19905.13368 1666, 2019.
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 escape sad- dle points efficiently. In Proceedings of the 34th International Conference on Machine Learning, pp. 1724-1732, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. Stochastic gradient descent escapes saddle points efficiently. arXiv preprint arXiv:1902.080 1et::0002211111 2019.
Jachoon Lee, Jascha Sohl-dickstein, Jeffrey Pennington, Roman Novak, Sam Schoenholz, and Yasaman Bahri. Deep neural networks as gaussian processes. In International Confer- Learning Representations, 2018. URL htttps://opeereviiee wwwp:arwwwewee.eeeeeeeeeeeeeeeee wwwp:/eee/oooimioooooooo
SIEA-M-OZ.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. arXiv preprint 1rXiv:1902.067200 2019.
Jason D Lee, Max Simchowitz, Michael Jordan, and Benjamin Recht. Gradient descent only converges to minimizers. In Conference on Learning Theory, pp. 1246-1257, 2016.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. arXiv preprint 1808v:1808.011 01204, 2018
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over-parameterrized matrix sensing and neural networks with quadratic activations. arXiv preprint arXiv: 17 2017.
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. arXiv preprint arXiv: 1907099977595.. 2019.
12

---

Published as a conference paper at ICLR 2020
Roi Livni, Shai Shalev-Shwarde and Ohad Shamir. On the computational efficiency of training neural networks. In Advances in neural information processing systems, pp. 855-863, 2014.
Alexander G de G Matthews, Mark Rowland, Jiri Hron, Richard Turner, and Zoubin Ghahramani. Gaussian process behaviour in wide deep neural networks. arXiv preprint arXiv: 11271, 2018.
Song Mei, Yu Bai, Andrea Montanari, et al. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A):2747-2774, 2018a.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layers neural networks. In Proceedings of the National Academy of Sciences, volume 115, pp- E7665-E7671, 2018bb 2018b.
Ha Quang Minh, Partha Niyogi, and Yuan Yao. Mercer's theorem, feature maps, and smoothing, In International Conference on Computational Learning Theory, pp. 154-168. Springer, 2006.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. arXiv preprint Xrviv: /9055093555 2019.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Networks, pp. 29-53. Springer, 1996.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli,, David McAllester, and Nathan Srebro. A PAC- Bayesian approach to spectrally-normaizzed margin bounds for neural networks. arXiv preprint 1eXiv:1707.0955 2017.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. arXiv preprint arXiv:/704.0810 08045, 2017a
Quynh Nguyen and Matthias Hein. The loss surface and expressivity of deep convolutional neural networks. arXiv preprint 1rXiv:1710.10928 10928, 2017b.
Roman Novak, Lechao Xiao, Yasaman Bahri, Jaehoon Lee, Greg Yang, Daniel A. Abolafia, Jeffrey Pennington, and Jascha Sohl-dickstein. Bayesian deep convolutional networks with many chan- nels are gaussian processes. In International Conference on Learning Representations, 2019. URL /ttt:::://ppereeeeee net///ewweeeeeeeeeeeeeeeeeeeeeee formtt//oummmmm B1gg0
Grant Rotskoff and Eric Vanden-Fijnden. Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. arXiv preprint arXiv:1805.00911 2018.
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks. arXiv preprint arXiv: (00.:/0005.0033 2018
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of pvrrtparameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-766, 2018.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2):1-230 2015.
Luca Venturi, Alonso Bandeira, and Joan Bruna. Neural networks with finite intrinsic dimension have no spurious valleys. arXiv preprint arXiv: 1802:0088833 2018.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge University Press, 2018
Martin Wainwright. High- digensiamenioonll statistics: A non-asymptotic viewpoint, volume 48, Cam- bridge University Press, 2019.
13

---

Published as a conference paper at ICLR 2020
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. arXiv preprint arXiv:1810.05366 2018.
Colin Wei, D Lee Jason, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and
optimization of neural nets vs their induced kernel. arXiv preprint 18X.v:1810.05369, 2019.
Christopher KI Williams. Computing with infinite networks. In Advances in neural information processing systems, pp. 295-301, 1997.
Blake Woodworth, Suriya Gunasekar, Jason Lee. Daniel Soudry, and Nathan Srebro. Kernel and deep regimes in overparametrized models. arXiv preprint (9Xiv:/906.05500 2019.
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv:1904.0
2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep ReLU networks. arXiv preprint arXiv:1811.08888 2018.
A TECHNICAL TOOLS
A.1 A MATRIX OPERATOR NORM CONCENTRATION BOUND
Lemma 8 (Variant of Theroem 4.6.1, (Tropp et al., 2015)). Suppose
are fuxed
symmetric x d matrices, and [ax)
iid Unif(#1} are Rademacher variables. Letting
Y, Σ i=1
o;Ar,i.
then we have
Eg max rEmm]
llop
<4
max D( o(Y,) l( log@md), rE(m)
where
YY)
F Y
op
Proof. Applying the high-probability bound in (Tropp et al., 2015, Theorem 4.6.1) and the union bound, we get
Y Yrllop 2t < 2d Σ
max rE[m]
rE(m
12
log(2dm) ).
< 2dm exp(-t² -t2 max ua (Y,
exp
rE|m]
2 max v ((,))
Let V max,e[m] u (Y,). ,) we have by integrating the above bound over that
f2
E
max
Y
llop
min
exp
+ log(2dm)
rElm
2V
/ AV log (2dm)
+
sxp(-t//20 log(2dm))
AV (2g(2dm)
/ 4V log(2dm) +
exp(-t8/4V))
4V log (2dm)
/4V log(2dm)) +
< 4 Vlo(2dm))
2dm
14

---

Published as a conference paper at ICLR 2020
A.2 EXPRESSING POLYNOMIALS WITH RANDOM FEATURES
Lemma 9. Let o()) = relu(!) and wo ~ N(O, B la) be Gaussian random features. For any p E {1) U (20) and 3 Rd, there exists a random variable a al (Wo) such that
Ew Ewolo(wo x)a] = 22(3xx)p
and a satisfies the la norm bound
Ewo Swola?] - 2n V 1) B2 1) d113
Proof. Consider the ReLU random feature kernel
(x,xx') Boo-NO0.B (rellllllwwwwee x)rell(w)
and let Hx denote the RKHS associated with this kernel. By the equivalence of feature maps (Minh
al., 2006, Proposition 1), for any feature map Φ (B,) + H (where Hilbert space) that generates K in the sense that
K(xxx) (p(x),
we have for any function f that
| inf nEH
[all f+(x)= = (a, )(x))
(11)
and the infimum over is attainable whenever it is finite.
For the ReLU random feature kernel K, let u == x x' 13/B3 and N2(p) denote a bivariate normal distribution with marginals N(O, 1) and correlation P E [-1,1]. We have that
K(x, x') E wo N(o.B, 21a) [relu(w, x)rclu) []]]
E (2),, (rclu ) (zcuuu
(u(T u)rccosu) + / u²
2n
1
1
π
22 2) (2 " 20
(2f - 3)!!
2m
2
1=1
Σ
Cp(x x2pB
pEfO.1)u(2ftea)
Σ
B (c
pE/0.11(230
where the constants
{cp} satisfy
cu 1/(2m); = 1/4, C2t 2 2n 1)2
for f 2 1,
(and thus Cp 2 (2 1)3) for all p), and 3k Rd* denote the k-wise tensor product x. Therefore, if we define feature map
<(x) [Vcp Sp pe (0.1)
we have K(x, x') = (0(x), o(x'). represented
With this feature map, the function f.(x) al3T x)" can be
fx(x) = (c., ((x)) where c. c=
= [o.............. :=,0....,0.. 00, Sp 1/2 1/2 o.....
Thus by the feature map equivalence (11), we have f. E HK and || < || = a² 2²=²² B²r || < 2 V 1)3 B ||81 Now apply the feature map equivalence (11) again with the random feature map x x {relu(w] x)} wo
(which maps into the inner product space of wo N(O, B.)1a), we conclude that there exists (W)) such that f. = Ew. [rclu(w, x)a] and
Ew, < 11 2n V 1)3 B²d |
15

---

Published as a conference paper at ICLR 2020
A.3 PROOF OF EQUATION (4)
Let M be an 1/2-covering of (1). We have [M] S 54 and for any vector w E IRd that ||w||2 S 2 (u w) (see e.g. (Mei et al., 2018a, Section A).) We thus have
P max BN Wo.r 2t)
relm]
max (v T Wo.r) 2 1/2 S exp(-12/88 log [V + log S exp(-12/8 dllo 5 + log m)) VEN
Setting V 88d log(m/0)) {0) Olvd+ log(m/5)) ensures that the above probability does not exceed as desired.
B PROOFS FOR SECTION 4
B. PROOF OF LEMMA
Computing the gradient of L we obtain
2
2 C (w(i)) (x)) x x/xx)) WD..
VL
71
Further computing the Hessian gives
VLL(W)).EE
2 Σ
(xxx, W.E'D.'W.,)
2/m
sw, (xi)
4
(xix] WD. E¹)
n
2/m
2
(y., P (x.)) (x.)
(u. S (x.))
Taking expectation over E', and using that < 1, term can be bounded as
Ey [I] I Exy
2 Σ o" d((wo, x) (w. (x)xx)(((0))) (Ex w x)²
=By,D
< C Ep
( o x)2 (w [x)] x w x,, x)²
(
1
< CB
(w x2)
Σ ||wr|12 1
max
re(m],eE[m)
m
rmm
< O
W. 22, m m-
where the last step used CauchhySchwarc on {I ||wwl 112) and [1]
16

---

Published as a conference paper at ICLR 2020
Term does not involve E' and can be deterministically bounded
I 2=EEE( (v. ( (x)) (x)
2E (x)) (x)] + 2ED(e (W)) (x)
( (VL W + 2E Nw. (x)) ((
(1
(V))(W), W) - 2(1.2(W)) - OPT).
where (i) follows directly by computing (VL (W), W) and the convexity of 2 + E(y, 2), and (ii) follows from the assumption that (W.)) - OPT. Combining the bounds for terms I and II gives the desired result.
B.2 COUPLING LEMMAS
Lemma 10 (Bound on (Q) For any W E Rdxm, the quadratic model Jw satisfies the bound
(x(x) & @0VvB% wl
for all x E (B,).
Proof. We have
[x(x))
1 Car (won) (,,
=
vmm
rsm
Σ C/wo,rx (w, x)² S CVmB3
max rE(m)
Wo.
|| 1l.1
rsm
1/2
< CVMBBÖ(Va)
1 Σ wrrl2 m rsm
=
=Ö(VaB3 Ruc. [W112a).
Lemma 11 (Coupling between f and fo). We have for all x E gdt that
(a) Esif (x)) = and Ex((fWr e B W 12, m 1/2).
(b) A (ww(()) (x) < O ( [ 2,,4 m 1/4) (almost surely for all E.)
Proof.
(a) Recall that
S (x)
Σ
q a,o'
x x).
mm
As Eyr has mean zero, we have Ex 0 and
EE( m
(w, Σ (wo ( x)2
TS
(
Σ x)
(8))
C max (w T x) rE(m)
1
Σ
B ||
/wrl12
m
1/2
(00)
1 Σ m
(dv) < CE
1 <
|wrlll
( || 2, m 1/2))
Above, (i) follows from the assumption that (o((t) < Ct², (ii) is Cauchy-Schward (iii) uses the bound (4), and (iv) uses the power mean inequality on |wrllg-
17

---

Published as a conference paper at ICLR 2020
(b) We have by the Lipschitzness of o" that
I (x)l - mm
1
Σ or (a((wo.r + Eyr w,) [x) - (wo,,.))
r-mm
o' x' w x) -wo x))²
w, CV CvmB 1 Σ |w, 112
rsm
rsm
3/4
CCmBB
Σ
|wrll2
0
B
W
2.4
1/4
where again (i) uses the power mean inequality on ||w,ll2- 112-
B.3 CLOSENESS OF LANDSCAPES
Lemma 12 (L close to L). We have for all W dd that
IL(W) 1 (W) s 6 B W W12.a
m-
1/4 + d² [ 2,4 m 1/22)
Proof. Recall that
L(W) Bx,D|e fwo+ and ( ED(((y [W
By the I-Lipschitzness of z + Ely, 2) we have
[L( - La (w)l s EIDD (Wx-) -
s (EE.D (flvx()) (x) + (x)( 1/2
(2Ex. (C (x)) + 2E (A WE (x))²1) 1/2
(WWr(x))?
5 B |
3 2,4 m 1/1 + BB W 2,4 1/2 m1/2)
where the last step uses Lemma 11.
Lemma 13 (Closeness of directional gradients). We have
(VL(W), w) - (VL w)
I <0(( | + vdB. W 1. + B |
+ d2. -1/4
1/4
W1 m -1/2)
Proof. Differentiating L and 6 and taking the inner product with W, get
(VL(W), w) -E,D ('C, mm
Σ
a. (,o'((Wo,r + Er, wr) (x) x) w, x)
rsm
and
(VL)(W), w) EE
ely, (x))
Σ
(wo,)) (w, x)²
18

---

Published as a conference paper at ICLR 2020
Therefore, by expanding o' d((Wo,r + Err wr) Tx) x) and noticing that Σ2, 1, we have
(VL(W)-VL(WW) w)|= BI,D (y, (..f:owwx))
Σ
a
x)
m
rsm
+ EEDD
(w.,(x)-- ((v))((x))))
Ea.o" (wo,xx) (w
Vm
rsm
+ Ex,D f(v.fwotwz(x))
Σ ar (o'or + w,, x) o' (w - x)" x)) (Enr w xx) P.M
III
We now bound the three terms separately. Recall that |&'| s and (1,,, 2) is 1-Lipschitz in For term we have by Sauchy-Schware that
(wo x) xx)) x)² ))
1/2
[
ED
Σ
m
rSm
1/2
1
C
max re(m rE(m)
(w x;)
Σ 1|wr112 B²
m
rsm
1/4
OdBx))
wwrll2
- ||
11,,4 m ml200
m
For term II, we have
| EEDD (/wo+ -xx()))))) 1/2
(1)
(1 (B 1/2
(6)) <
0
B
W
3
2,1 m. 1/4 + BBB W12 2,1 1112 Ö(VdB3 (W1l.))
= =ō(vaBB
_ m
114 + 2 BA W 11 mn-122)
where (i) uses Cauchy-Schward and (ii) uses the bounds in Lemma 10 and 11. For term III we first note by the smoothness of o' that
(a- (o'(( + E,,,, x) - o'(wo,,x) o² o'(wo, ()),, w, x)) (Ear w. xx]
<C CB wrll
Substituting this bound into term III yields
I
C
wr 12 < CVmB
1
Σ 11
3/4
CVmB
1 m rsm
1wrll2
=
B
3 W 2.4
m 2/1)
Putting together the bounds for term I, II, III gives the desired result.
19

---

Published as a conference paper at ICLR 2020
Lemma 14 (Closeness of Hessians). Let E' denote diagonal matrix with diagonal entries drawn i.dd from ( =1). We have for all W, W. E Rdxm that
E -
v2
W >' W.
B [
21,, + vdB
w 3 2.44 [W 2,,1 m 1/4
(
W
2 2,4
| W. + (d + W B W. 112 )mmmmmmmm 1/2
" W 2,4
W. 12, m
Proof. Differentiating L and 1 twice on the direction W, E', we get (2L(W) W.E
= E
f'(v.fw+wwx(x)
1
Σ
Caro((Worr + (T, Ey, w xT
vm rS
I(L)
+ E
('), f(w,swoowz(x))
Σ
a, a, ((Wo.r + Err x) Tx)) E', x.yxx/
mm
IT(L)
and
W. (x))
1
Σ a, _ajo"(wT,,x(m x) w wT,
m
T(1
E EED
((y,
Σ (W) w.. xx)
vm
rsm
II(29)
We first bound the terms T(T.) and I(I.0). We have
I(L) DE,,''
d.o'((Worr + Err w.) xx) (w.T,
m
rsm
C. sup
Σ ((worr + E,, [x) xx)
||x|| =
1 Σ (Õ(P) ||,,, ||w B |
CBB 171 rSm
dl + W 0, B¹) | |. 1 m m112) 0 O0 B2
Using similar arguments on I(L gives the bound
I(I s δ dB || 12,, W 112, m m-1)
(12)
We now shift attention to bounding IT(L.) - II(T)). First note that
A (x) = (ar ((Wo,r Er, w.) x) o" < C E w. (w. (w < CB3 |rlll ||w.,ll..
20

---

Published as a conference paper at ICLR 2020
Then have, by applying the bounds in Lemma 10 and 11, [L) [I((T)]
E (yy. f(wx(x)+
1
Σ
A (xx)
+ +E,, (elv. (VV 2f (x)
vm
Smm
CV R (wwx(x) + A AWx(())) /
[R. J.. (xx)²) 1/2
C. Vm
B (/-l [ w
rSm
s <Ö B3 ||]] 2,4 W
11,,1 m m//14)
B |W 2,1 1/4 dl B
W 2,1 1/2) -0 (VVdB3 |w. W.1...).
=Ō((B²
| 11,, vdB. w1
W 11112, m 1/4 2 W
2,4
W 11 1/2
W
Combining all the bounds gives the desired result.
B.4 PROOF OF THEOREM 2
We apply Lemma 12, 13, and 14 to connect the neural net loss L to the "clean risk" L First, by Lemma 12, we have for all the assumed W that
L(W) ( - 5 B W 3 m 1/1 + d d Wl2,, m -1/2)))
Therefore have [[W) I [Q(W) & c/6 so long
m OBBB B -4 d B.B
(13)
Applying Lemma 1, we obtain that
Ex (3L W. E' - (VL) w) 2 (W) OPT) c/3 s 2(L(W) OPT) + 2c/3
(14)
provided that the enror term in Lemma is bounded by e/3, which happens when
m N OdB
(15)
Finally, choose sufficiently large that
Ex -"2 W. W. s//6
and
(VL(W)- - (L)(W), W) S c/6,
which combined with (14) yields the desired result. By Lemma 13 and 14, suffices choose m such that, to satisfy the closeness of directional gradients,
m Õ(d B + d B + B. o12 + B
(16)
and to satisfy the closeness of Hessian quadratic forms,
2 o ( B B$ + dl B20 B B B -4
(17)
[dS Bd Ba + dt B + B12B$ Bd BL ( Bd B² B
Collecting the requirements on m in (13), (15), (16), (17) and merging terms using S and B < Ban the desired result holds whenever
m 2 O(BLB B + d' B d 2 B - + BB,
This completes the proof.
21

---

Published as a conference paper at ICLR 2020
B.5 PROOF OF COROLLARY 3
Proof. For all À Z 0 define
Ax := Ex LW) W. (V),(W), W) + -W) By Lemma 2, it suffices to show that
A Ao S SC 11, 2/
for some absolute constant C.
Recall that (WW L(W) + A W. 112. By differentiating A ||A we get
(V(L) (W), w) = 2 |
Σ
(4>11wrll w. 82 W
and
VL - ())) W.E"
8A W
Σ
wr 112 W., E +2 (Wr, Enr +23 |W
Σ
wr
l2 (wr, Wer
rsm
rsm
(4) ||,, 1
(1) S 14Aa [ +
3781
$ 56X W
11 S 56A W 11 |..
[W 1,.4
a
mm
and (ii) used the AM-GM inequality r²q S ap"/4 + 27 1/4a²²))) for all p. q and a > 0. Substituting the above expressions into A Ao yields
where (i) used
A Ao
378A
< 14Aa W
2,1
+
|W
8A W + 2A W 2,1
378A
= (14Aa - 6Λ) |
2,4
+
a
W.
Choosing 5/14 gives the desired result.
B.6 PROOF OF THEOREM 4
We begin by choosing the regularization strength as
X = B.
w,
where A is a constant to be determined. Let e be an accuracy parameter also to be determined.
Localizing second-order stationary points We first argue that any second order stationary point W has to satisfy || S Buno for some large but controlled B We first note that for the clean risk L,, we have for any W mddx that
(VI.(W), W ED (V.. R2 (x)) 2)(())
(1)
2E (y, 2 (x)) (f (x) - 1o (x))
2 -2
where (i) uses convexity of & and (ii) uses the assumption that f(y. 0) < 1 for all y E V.
Now, applying the coupling Lemma 13, and combining with the fact that (Vw(>) 12) w)
8A || 1 we have simultaneously for all W that
V (W)) W)
Vw ( (. w) +(VL W) - w)
8A W 2.4 - 2- 2-66( ((dBB | 2,4 + VaB.
W|
5
B
W
2.4 m
1/4
2 B
[ 1
2.4 m -1/2)
22

---

Published as a conference paper at ICLR 2020
Therefore that any stationary point W has to satisfy
| I w, = Ō 1/8 + +AA -1///// + (A + VdB 1/1///// -14.m1 + BAA + (A-1
B 1//3/3/)
By Corollary 3, choosing m 2 poly(Añ' d. Bu., c), the coupling enror is bounded by e in (2,,(Bu,o)) i.e. for all W E (Pw.)) have that
Bx [L W.E'] (VLx(W), W) 2 (W) - OPT) X 1 CA C.122 +c
(18)
where C = (11) is absolute constant.
Bounding loss and norm
Choosing
Ao
C (2,OPT +c),
we get that CAB$ i0 = 2yOPT + e, and thus the bound (18) reads
Ex (VW. [W.
< (V)(WW), w) - 2(Lx((())) - OPT) - A + 2yOPT + 2e.
For the second-order stationary point W, the gradient term vanishes and the Hessian term is non- negative, so we get
2(L (W) OPT) S 2(TOPT +c) - -
W S 2((0OP
2,4
and thus
LA (w( S (1+ (L+2)) 7PP +
Further, by re-writing (18), we obtain
X
W S CABS + 2(OPP- Lx((W) +E CAB + 20PT +e
24
(1+
20PT +e
< CXB
= 0(1) ABB.
2-OPT +
for any 7 (1). This is the desired result.
23

---

Published as a conference paper at ICLR 2020
C PROOFS FOR SECTION 5
C.1 PROOF OF LEMMA 5
As the loss { 2) is 1-Lipschitz in for all y, by the Rademacher contraction theorem (Wainwright, 2019, Chapter 5) we have that
2
Σ
oy Iw Ru(x)))
sup
|| 2,,4 x Bi.
i=1
< x
sup
F
w (x::
Bo,
1
Σ
oll(yr 0)
2, S. B, n1
n
J,a,0" (wo, w. )
1
< F
sup
|
m
n2
vz
rsm
1
< F
sup
max
a, Wi,xxiiXxxx
Wr w _
|l.
SB rE[m]
Th
mm
vn
op
rsm
1 Σ 0,o"
1
< Ex,x
max
(wo, (wo
X,),xx
sup |
l|,, 12
+
rE mi
n
SB B
V m
vn
SB
where the last step used the power mean (or Cauchy-Schwand inequality on {||wrl22)
C.2 PROOF OF THEOREM 6
We first relate the generalization to that of L through
Lp W) - L(W)= & (w 1 W) + L)( - L (Q L - L(W).
By Lemma 12, have simultaneously for all W (B,) that
[(W) (w) s 2ō B m 1/4 BB
(19)
Further, from the proof we see that the argument does depend on the distribution of x (it holds uniformly for all x E gd-1(B... therefore for the population version we also have the bound
[P)W) (2(W)) &
Ō BB 1/4 + d B2 -11/2)
(20)
These bounds hold for all W (B..) apply to W. Therefore it remains to bound L (W) 2 (W), i.e. the generalization of the quadratic model.
Generalization of quadratic model
By symmetrization and applying Lemma 5, we have
Ew. Lg(W) (W)
< EW..D
sup || Sl
- L9
< 2.
sup 1wll2.BB.
Σ iml
oillyss (W (x:))
(21)
2
< 4B2 E.w.oxx
max rE(m]
Σ 1=1
0,0" (w)) X
Vni
1p
24

---

Published as a conference paper at ICLR 2020
We now focus bounding the expected max operator norm above. First, apply the matrix concentration Lemma 8 to deduce that
B
max relm]
o (wo,r
1=1
op
I 4 (log(2dm) Ewa.
max re(m]
n12 i=1
1
Σ
o"
(w. (.,, x2 |x: X
op.
log (2(2m))
S 4B,
Ewo.
max
anaxo"(Wor-aa (w),
x
op
1/2
log( log(2 (ddm)
n
$ xB2
Ewo. max o" (ww,, x;)²
Ex
x
n
As lt"(t) < Ct and w exponential variables we have
1) for all (r, 1), by standard expected max bound on sub-
E E max (wo,,
< (llo(mmn) = Ō(1).
Therefore defining
x )
1/2
My Ma
B=². Ex
im1
and substituting the above bound into (21) yields that
Ba B²B² Mr.op
E Ew., - - L
Vn
Vn
Combining the bound with the coupling error (19) and (20), we arrive the desired result. For Mz,op we have two versions of bounds:
(a) We always have Eiig x /nl S B2, and thus Mg.op S 1.
up
(b) If, in addition, x is uniformly distributed on the sphere (d-1(B,) or the hypereube (BB//VV) then we have by standard covariance concentration (Vershynin, 2018, The- orem 4.7.1) that Exx E x
/n lop
BB/d O(1 + Vd/n d/n) O(B2/d)
when 2 d. More generally, if for all E (1) have
| | SK (or(xx)),,
and that ((Cov(x)) & K, then we have [|Cov(x))llon I <xB2/d. Applying (Vershynin, 2018, Theorem 4.7.1), we get Mz.op S x//V whenever n 2 O(K*d).
C.3 EXPRESSIVE POWER OF INFINITELY WIDE QUADRATIC MODELS
((3xx)) Lemma 15 (Expressivity of fo with infinitely many neurons), Suppose fx(x) aaBT x) for some a E R, B E Rdd, and 2 2 and such that p - 2 E {1} U {20 Suppose further that we use (t) trelu (t) (so that o" (t) = relu(t)), then there exists choices of (W+, w_) that depends on such that
Ewo [ow(w] ()TT()(([[[) (w (wIx))) fx(x)
and further satisfies the norm bound
Ewp
[w+
+ ||w
||w-12 11
< 2m 2) v1) 22 ||31122
25

---

Published as a conference paper at ICLR 2020
Proof. Our proof builds reducing the problem from representing (3 x)" via quadratic networks to representing (3 x))=² through random feature model. More precisely, we consider choosing
(w++
(Vla)+ -B vial-
(22)
where a is real-valued random scalar that can depend on Wo. and ,3 is the fixed coefficient vector in fw. With this choice, the quadratic network reduces to
Ew [o" (wo x ( x)) (wIx)²)]
= Ew oo ( x a+ (3 x)² - - a_ x} = (8 2w [o"(w]
Therefore, to let the above express fa [x(x) = a(3 x)P. it suffices to choose such that Blo" (wo) x)a} =
(23)
for all x. By Lemma 9, there exists a = a(wo) satisfying (23) and such that
Ewo [a") < 2n ((p 2) v 1) B2(=2) || ((p22)
Using this in (22), the quadratic network induced by (w+, w-) has the desired expressivity, and further satisfies the expected 4th power norm bound
Ew w 11 + [|w- [1 Ew. [a] + [ || = Ew [a") [11111112 - 2T((p- - 2) v V 1131 This is the desired result.
C.4 PROOF THEOREM 7
We begin by stating and proving the result for k in Appendix C.4.1, i.e. when f== xx is a single "one-directional" polynomial. The main theorem then follows as a straightforward extension of the h: = case, which we prove in Appendix C.4.2.
C.4.1 EXPRESSING A SINGLE "ONE-DIRECTIONAL" POLYNOMIAL
Theorem 16 (Expressivity of fQ). Suppose {(rr wo,r) are generated according to the symmetric initialization (3), and (x(x) = a(BT x)? where E [1} U {20) Suppose further that we use (t)) relll (t) (so that ot()) relu(t)), then long the width sufficiently large:
m N Ö(dpp² a² aB2, 113111)
--)-)) 2),
we have with probability at least 1 (over Wo) that there exists W. E Rdx such that
LWWW)) -WW.)-((J)) Se and |. S Bd, = 0 B2 2) || || 8 5-1).
We build on the infinite-neuron construction in Lemma 15. Given the symmetric initialization {wo.r) for all r E [m/2]. we consider W. E [d defined through
Proof of Theorem 16
(Werr) w.r++m/2) 2m 10m-1/4 1/4
w. (Wo.)) 2m 1//--//wwww))
where we recall (w4(wo), w-(w))) (Wo) (wo)3)) We then have
W (x)
Σ
o" d"(w x2) (w [w., .r
m
rsm/2
2
Σ o" [((wJ,,)) Tx)2 - (w- (wo.r) [x)
rSm/2
Σ
d"(wo,xxaaWwon
x))
m/2
r5m/2
26

---

Published as a conference paper at ICLR 2020
Bound |1+112,1 As fx(x) a(3xx)) x))" Lemma 15 guarantees that the coefficient al ((wo)
involved above satisfies that
R² = Ew.la(wo) & (T ( v a) (1
By Markov inequality, we have with probability at least 6/2 that
Σ a(worr)² S (( - v)) 2) ||311 200 2) 8-1
m/2
which yields the bound
||
Σ
||
rsm
$ ||
Σ
16m 16m--aa a(worr) =8113112 m/2
Σ al a(wo,r)² rSm/2
rSm/2
S 32 (pp - 2) v 1]0 22(p-2) 113 8-1.
Concentration function Let (x(xx = 1 Ems//2 o" (ww x))(x))( We now show the con- centration of fm to fx := a(33 x)p-² over the dataset {x1,.... Xn We perform trunca- tion argument: let R be a large radius (to be chosen) satisfying
Pwo
|| RBB') re(m
sup
2 1
(24)
On this event we have
fm(()=
1 m
Σ
{ |/ S RB_ == (x)))..
rsm
Letting f 2(x) = Ew [o"(wo (xxxxaaooo) [1)) [w
{/ollll RB,". }}, we have
B | Ewo (ow (wo) [llwoll2 S <R}] S
11-12g
112 R2
Ew. (Jm(x) - (.i0))--pp2210 2x))= =
m
m
Applying Chebyshev inequality and union bound, get
nR R² mil2
P max (x;:) f- 2t) s c
For any >> O, by substituting in t = =eB=2 1/111 /2, we see that
m 2 Ontt R2 [ = 0nLl (n2 22 1131 E
(25)
ensures that
max fmx (xx)) S 2=B=3110111 11,011-/22
(26)
iE|m]
Next, for any x we have the bound
(x)p2(() - St, 2x = || (o]((v))))((w))) [[]]o]] > R}]
$ Ela( wo 2/1/2 Elo" (w, x1)"(//)))////4 xx)2//44P(((olll)) > R/2/4
Ra. C/Vd P( > 1//2/4
Choosing R such that
P([|woll2 R) S Vile 4
(27)
R, B& |,31|
ensures that
cB=2 ||,9112
max 2
1 2xxx) f..p- 2(xx) <
(28)
27

---

Published as a conference paper at ICLR 2020
Combining (35) and (37), see that with probability at least 6,
max sEin
Jw.
(x,) - fx = max If (x;) - f=,-2((x))) (3)x,)²
RE(m]
S 2 <B 1131 -2
2 |13111 =E
and thus
(w.) I(f-)] Sc.
(29)
To satisfy the requirements for m and R in (36) and (34), we first set R = Ö(Vd) (with sufficiently large log factor) satisfy (36) by standard Gaussian norm concentration (cf. Appendix A.3), and by (34) suffices to set m as
m 2 Ö(n((p aB 21
for (38) to hold.
C.4.2 PROOF OF MAIN THEOREM
We apply Theorem 16 k times: let
fx (3)x)) (3,
so that f+ = Ejech f-j- Associate each j with independent of initialization ()) ( Theorem 16, there exists w(J) gdxm;, where
w(().. By m, = Ö 1),, (13
such that with probability at least 1 - 8/k k we have
p W (xx) [x(xi) S sc/h
max sE|m]
and the norm bound
O o 3 113,1120 22: 8 8-1).
(Note we have slightly abused notation, so that now
{
{ w!o jE(K]
use disjoint of initial weights
(5) (1) ((()) ).) Concatenating all the (W(/) ag w()) and applying a union bound, we have the (ao
following: so long as the width
δ ndk? Σ pJ 1201)))200
m2
with probability at least 1 8 (over ag E Imm and Wo E RRdxm), there exists W. E Bdxm such that
fe (x.) - fx(x)) Se,
max <Ein]
which by the I-Lipschitzness of the loss implies that ( S L(f.)()))))))) +c= +c.
Further, as W, is the concatenation of (w!)) jE(N]
we have the norm bound
W. W.I1 1
W
k
p
3
B2 pps
2) |13
2p, 8-1
1=1
1=1
This is the desired result.
28

---

Published as a conference paper at ICLR 2020
D EXISTENCE, GENERALIZATION,, AND EXPRESSIVITY OF HIGHER-ORDER NTKS
In this section we formally study the generalization and expressivity of higher-order NTKs outlined in Section 6. Let 2 be an integer, and recall for any W [dx22m the definition of the k-th order
NTK
(ki) (w x) [( [(wT,,x)* - (w [w]])
1
Wo. (x)=
(30)
vm
k!
mm
D.1 COUPLING AND f(() VIA RANDOMZIATION
Recall that for analytic we have the expansion
fwo+w(x) = m
Σ PSm
o((wo,r + w+r) xx) - -o(Wo.r + w-
Tx)
Σ
W w((),
Rmn
For an arbitrary W such that || ||w2 Om (1), expect that (x) is the dominating term in the expansion.
Extracting the k-th order term We now describe approach to finding W that
(k) fw.+w(x) Jw.. w...(()) (x) + Om (1),
that is, the neural net is approximately the k-th order NTK plus an error term that goes to zero as bo, thereby "escaping" the NTK regime. Our approach builds the following randomization technique: let 24, =_ be two random variables (distributions) such that
E[2 =<<_] for 0, 1, ... and M[ E[s*]
Set (W+sr, w-))) (Z+. Z- W..)), and take | O(m -1/2k,, we have
(l) (x) vm rmm
1 (i) (Wo, (24,r - x_ (w (w] = Op(m 51/2k)
j!
O(m 5/2k)
for j = I..... and
(x.
(1) (wJ, (z (w. xT) Op()),
mm
Pmm
1ean=1
O(m 1/2)
and
(2k+1
(w I h+1 x Or(m--011000 11/2k).
(x) mm rsm
(k + 1)!
(1--(t-1)/22)
Therefore, with high probability, all f(),..., ..... f(k-1) as well as the remainder term - Eisch f(5) has order (m (mm-1/2k) and the k--th order NTK (() can express an O(1) function.
D.2 GENERALIZATION AND EXPRESSIVITY OF (k)
We now turn to studying the generalization and expressivity of the k-th order NTK (()), Throughout this subsection, we assume (for convenience) that
au(() = hd!
(1) relu(()
the ReLU activation.
As we have seen in Section 6, we have (()) = 0(1) by choosing w, ~ Omm-111mp therefore we restrict attention on such W's by considering the constraint set {W || B2* for some B.. Om (1).
29

---

Published as a conference paper at ICLR 2020
Overview of results
This subsection establishes the following results for the k-th order NTK.
We bound the generalization of (A) through the tensor operator norm certain k-tensor in- volving the features (Lemmaa 17). Consequently, the generalization of the k-th order NTK for | Bw, when the base distribution of x is uniform on the sphere, scales
1
B
+ Vn
Vndk-1
n
(Theorem 19). Compared with the distribution-fiee bound B B / Vn, the leading term is better by factor of /min {d--1,n) nz.. In particular, when dt-11 the generalization is better by factor of d than the distribution free bound.
For the polynomial f. (x) = a(B x)² with 2 k (and p k is even or onc), when m is sufficiently large, there exists W. expressing f. such that
W. 2,2k S o <0 O || 11
(Theorem 20). Substituting into the generalization bound yields the following generalization emror for learning f.:
δ 02 p'xa2(BB1111) (191)))))
+ #1
Vnd
In particular, the leading multiplicative factor is the same for all & (including the linear NTK with k 1), but the sample complexity is lower by a factor of d when 2 d This shows systematically the benefit of higher-order NTKs when distributional assumptions are present.
Tensor operator and nuclear norm Our result requires the definition of operator norm and nu- clear norm for k-tensors, which we briefly review here. The operator norm of symmetric k-tensor A E gd is defined as
| = sup (A, (Sk)
sup
l|vll==1
l|v
The nuclear norm ||-||, is defined as the dual norm of the operator norm:
||||. sup
(A,B)
=1
Specifically, for any rank-one tensor u we have
skk
(u B) = =
sup
[ op
ie. its nuclear norm equals its operator norm (and also the Frobenius norm).
D.2.1 GENERALIZATION
begin by stating a generalization bound for (k), which depends on the operator norm k-th order tensor feature, generalizing Lemma 5.
Lemma (Bounding generalization of ((k) via tensor operator norm). For any non-negative loss l such that z + E(y,z) is 1-Lipschitz and É(y, 0) I 1 for all y E Y, we have the Rademacher complexity bound
Eg
sup
Σ o.lly,, ((k) (W) (x))(x)))
2 E
max rE(m)
Σ n i=1
o W X
|| 2,24 S
op
where a; iid
Unif(= 11} are Rademacher variables.
30

---

Published as a conference paper at ICLR 2020
Proof. The proof is analogous to that of Lemma 5. As the loss E(y, 2) is 1-Lipschitz in for all y, by the Rademacher contraction theorem (Wainwright, 2019, Chapter 5) we have that
E Ex,x
sup
orl(yi I ((k) wo.w(
W 11 SBa
1=1
1
< 2B
sup
Σ
oi o..Wo.
+ Eox
Σ
osl(us. 0)
JIW 2,24 S Bu i=1
n i=1
woth 1/
1
< 2B,
sup
(Wo,
0K
| 2,24 BB
V
vn
rsm
S 2
sup
max rE(m]
a,0:0 xx
/ |l.
+
[ 1/2, 2, Bw.
nn
op
rsm
< 2
max rE[m]
Σ 1=1
( oo
x &k
sup I| & B..
|
122
+
1
Vm
vn'
B
where the last step used the power mean (or Cauchy-Schward inequality on [|wwll2)
Bound on tensor operator norm It is straightforward see that the expected tensor operator norm can be bounded
without any distributional assumptions x. We now provide bound on the expected tensor opera- tor norm appearing in Lemma in the special case uniform features, i.e. Unir((d--(Ba))
Lemma 18 (Tensor operator norm bound for uniform features). Suppose x; lid (af((gdd1(BB)) Then for any k 2 3 and l = O(1), we have (with high probability over Wu)
1
Eo. x
o. (w, 0K
<
B
(31)
rE/m]
ndt
Substituting the above bound into Lemma 17 directly leads to the following generalization bound for (k))
Theorem 19 (Generalization for f(k) with uniform features). Suppose x; Then for any k 3 and l = O()), we have (with high probability over Wu)
lid
(ni)())
(Lr(sW. L(FW) (.W..))
=O(
zō B Bk
1 2
+ 1
ED
sup |I
Vndk-I + n
Vn
B...
The proof Lemma 18 is deferred to Appendix D.3.
D.2.2 EXPRESSIVITY
Theorem 20 (Expressivity of (())), Suppose {(ar, Wo.r)] are according to the symmetric
initialization (3), and (x) = a(B x)" where p p- {1} (20) Suppose further that such that d% ox(() relu(t), then so long as the width is sufficiently large:
m Ō (ndpp a² (Bz [13112) (P 2))
we have with probability at least 1 - 5 (over Wo) that there exists W. E RRdxm such that
(W.) I(f+)| < and ||
2k 2.2k
B2R
00p a B2(=-k) ||3123 8-1) 5-1)
The proof of Theorem 20 is deferred to Appendix D.4.
31

---

Published as a conference paper at ICLR 2020
D.3 PROOF OF LEMMA 18
We begin by observing for any symmetric tensor A E Rd" that
|| - ke veN(e)
sup
v],
where (e) is e-covering of unit sphere (1). (The proof follows by bounding A Afu,..., .......2 u] by A v] + ke | through replacing u by v one at a time). Taking e = 1/(2k;,, we have
P Pa,x
max rE[m]
Σ 1=1
os0h W Xi)x
ok
21
op
P
max FE(m),VEN(1((22) n
(w,, (v x;) 2 1/2
We now perform truncation argument to upper bound the above probability. Let M > 0 be truncation level to be determined, we have by the Bernstein inequality that
Po x
max rE[m]
O x.)x
2t
1=1
op
< PP
Pxx
max
Oiak w x:)(v (.), xx,)*
( S SM} 2 1/2
rE|m)
1=1
+ Px
max Th (W, x,) 2 M
nt
nt
M 20((1)
< exp
-cmin
+ d log 6k + log
+ exp
+ log mn
Õ(1) B2kd
M B
where the Ö(1) B2kd d comes from computing the variance of
Z, = oi0k (w,, (v) x;
using that x; are uniform on the sphere (see, e.g. (Ghorbani et al., 2019b, Proof of Lemma 4)); M M is the bound on the variable Z; and the ((1) comes from the fact that ||Wo,rll2 S Ō(vdB=1) with high probability. Now, choosing
M = (nt (nt/B5)u2
the above bound reads
exp
min
n
Tát
1/2
+ Ö(d)) + exp
nt/B 20(1)
-pp-- + 5(1) = pr-
(Õ(1) B2
BE
remains bound 1 Pt to give an expectation bound on the desired tensor operator norm. This follows by adding up the following three bounds:
For the main branch "nt? /O((// d k"" have
l min
cxp (TÖ(BRaa-)) + +0(0) + dt s =o
nt²
B2k notk-1
This follows by integrating the "1" branch for < Ō O (k-6d(k-11/pp (which yields the right hand side) and integrating the other branch otherwise (the integral being upper bounded by Õ(v
dominated by right hand side).
(2) The branch "(nt/ / is taken only when
nt
1/2
nt²
ie. 1> (n-1331 2k/3))
B
O O
32

---

Published as a conference paper at ICLR 2020
On the other hand, the inequality (nt (nt/B²) ((d) happens when
t> /
which is implied by the preceding condition so long as k 2 3. Therefore, when this branch is taken, the (dd) already be absorbed into the main term, the contribution of this branch can be bounded as
1e B
-c
nt
1/2
B
exp
dt 2
exp
dt S 0
Ō(a noo-1/angaee (3
B
(3) We have
nt/B B
+ 5(0) I s /((B/n))
min
exp
20(1)
using similar argument as part (I).
Putting together the above three bounds, we obtain
Σ Ooox(W
$ $ p:at - 20 B 1
Vndk-1 + 1 ))
re[m]
the desired result.
D.4 PROOF OF THEBREE 20
Our proof is analogous to that of Theorem 16, in which we first look at the case of infinitely many neurons and then use concentration to carry the result onto finitely many neurons.
Expressivity with infinitely many neurons We first consider expressing f.(x) = a(3x)) infinite-neuron version of (()), that is, we wish to find random variables (W+.w-) such that
x)" with
E [rolu(wo x))x)))) ((WIx)))))))) (wI (wIx)*)] (x).
Choosing
(w+, w-) ((k)))) ([a]-))*
for some real-valued random scalar (that depends on Wo). we have
Tw [relu(w, w. x) x)((w] x)* (wIx)*)] = (0 x)* IE [relu(w] x)a],
therefore the task reduces to finding a = a(wo) such that Ew [relu(w] x)a] = a(3Tx) x)p
By
Lemma 9, there exists a(wo) satisfying the above and such that
Ewo [a2] (T((p k)) v 1) 2 B2(n-k) ||
(32)
Using this a, the k-th order NTK defined by (w+, w expresses f. and further satisfies the bound
Ewo || 112 +
||
12 24 = Ewo[a"] || 26 < 2T((p - k) V 1) 2 k) 1|
Finite neurons Given the symmetric initialization [wo,r) T for all r E [mm), we consider W. Rdxm defined through
(Werr, We.r-m) = 1122k w (Wo,r), m 1122k w- -woor))
where we recall (w+ (Wo), w- = (a+ (wo) 2/1 B, a (wo) 2/k3) We then have
W...W. (x)
(b)
1 Σ on (w (w,,,) Tw.
Vm
rsm
1 Σ
xx)* (Woor) TT x
m
rm
1
ox Ox xx)x
Smm
33

---

Published as a conference paper at ICLR 2020
Bound on above satisfies that
As fx(x aa33xxxx x)", (32) guarantees that the coefficient a o(wo) involved
R = Ew, (a(ww) - (p - k) V " ||
By Markov inequality, we have with probability at least - 6/2 that
Σ
a(wo,)) 4T((P 1)v1))a² ||3|| 2()-)))) 8-1
m rSm
which yields the bound
|| W ll
E ||W., 22
=
$ || 2
Σ m
a(wo,r) S 4 1))² V 1]a² B2(p-1 "]a222(0> k)
1
2p 8-1
r.Sm
Concentration of function Let fm = = E (w ()),o))(((oor)) We now show the con-
centration of fm to f+ (x) a(3 ( x)"=* over the dataset {xi, ( We perform trunca-
tion argument: let R be a large radius (to be chosen) satisfying
Pwo
sup ||worll22 2 RB=1) 2 1 1-5/2. rE(m]
(33)
On this event we have
1 Σ ox ()( (llworrll S RBB1) = [x)(x).
Jm (m)
m
rsm
Letting f. (x) = Ew [ox (Wo x))(Wo)) (llwoll2 I RB, ']1, we have
Ewo (Jm(x) S. (x)==(())] 1 Ewn (wo x)a? (llwoll2 S RR} S
LEw m
12t
R2
m
Applying Chebyshev inequality and union bound, we get
P Pmmax (m()))) Sx.p- (x:) 2112(1) S SC
nRR
mt2
For any é 0, by substituting in = =B, ||31 -k 12, we see that
m 2 O B2h |13112 x2) O nRR² - 1:)3-))8220 13302B² 1101260
(34)
ensures that
max fm((x)) - - (x:) S BBB=* ||3|| /2.
(35)
<E(m)
Next, for any x we have the bound
xx))=(x)= - fxp-x(x)) Eowolox (w (w) ())(wa)))))))) [ > RY]
< (Ha(ww)) (wo ( x)// P([lwoll2 2/22/2
< R. C/Vd P([lwoll2 > 1/4
Choosing R such that
Vdee
P(| P(|woll2 > R) s c
(36)
R2 B4kk ||,3112 1k
ensures that
cB 11,111 k
max ([Rp-((x)) S.. 2x;)) 5
(37)
34

---

Published as a conference paper at ICLR 2020
Combining (35) and (37), see that with probability at least 6,
max 12
Jw.
(x:)
(xx)
max (x fo fx (8 x,)* :c|n]
(3'x,)*
cB
||
$ 2
m
B
|131 =c
2
and thus
L(f-) c.
(38)
To satisfy the requirements for m and R in (36) and (34), we first set R = Ö(Va) (with sufficiently large log factor) to satisfy (36) by standard Gaussian norm concentration (cf. Appendix A.3), and by (34) suffices to set m as
Σ (nd((pp 4) v (
for (38) to hold.
35


Reviews:
[{"review_id": "SyePj4XCtH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 investigates higher order Taylor expansion of NTK (neural tangent kernel) beyond the linear term. The motivation of this study is to investigate the significant performance gap between NTK and deep neural network learning. The conventional NTK analysis only deals with the first order term of the Taylor expansion of the nonlinear activation, but this paper deals with higher order terms. In particular, it thoroughly investigates the second order expansion. It is theoretically shown that the expected risk can be approximated by the quadratic approximation, and show that the optimal solution under a quadratic approximation can achieve nice generalization error under some conditions.\n\nOverall, I think the analysis interesting. Actually, there are big gap between NTK and real deep learning. However, this gap is not well clarified from theoretical view points. This is one of such attempts.\nAs far as I understand the analysis is solid. The writing is clear. I could easily understand the motivation and the results. The quadratic expansion is clearly different from the recent series of NTK analyses. In that sense, this study has sufficient novelty.\n\nOn the other hand, I think the study has several limitations. My concerns are summarized as follows:\n- The proposed objective function is different from the normal objective function used for naive SGD because there is a \"random initialization\" term and some special regularization terms. Therefore, the analysis in this paper does not give precise understanding on what is going on for the naive SGD in deep learning.\n- As far as I checked, there is no definition of OPT. Is it the optimal value of \\tilde{L}(W)? Since OPT is an important quantity, this must be clarified.\n- L^Q(W) considers essentially a quadratic model, and is different from the original model. It is unclear how expressive the quadratic model is. Since the region where the quadratic model is meaningful is restricted (i.e., ||w_r|| = O(m^{-1/4}) is imposed), the expressive power of the model in this regime is not obvious. It is nice if there are comments on how large its expressive power is. In particular, it is informative if sufficient conditions for L^Q(W_*) <= OPT is clarified.\n- (This comment is related to the right above comment) There are two examples in which the linear NTK is outperformed by the quadratic model. However, they are rather simple. It would be better if there was more general (and practically useful) characterization so that there appears difference between the two regimes.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hylx2510tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 training of over-parameterized neural networks. Specifically, the authors propose a novel method to study the training beyond the neural tangent kernel regime by randomizing the network and eliminating the effect of the first order term in the network’s Taylor expansion. Both optimization guarantee and generalization error bounds are established for the proposed method. It is also shown that when learning polynomials, the proposed randomized networks outperforms NTK by a factor of d, where d is the input dimension. \n\nOverall, I enjoy reading this paper. The presentation is clear, the arguments are insightful, and the proofs seem to be solid. Moreover, this paper offers some interesting ideas to show that neural networks can outperform NTK, which might be impactful. However, this paper also has certain weak points, mainly due to the less common problem setting. \n\nAlthough it is believed that NTK cannot fully explain the success of deep learning, results in the NTK regime have the advantage that the problem setting (initialization method, training algorithm) is very close to what people do in practice. Therefore, ideally, a result beyond NTK should demonstrate the advantage of NN over NTK under similar, or at least practical settings. If the problem setting is changed in some strange way, then it might not be that meaningful even if the training behavior is different from the NTK setting. In my opinion, the following four points about the problem setting in this paper are less desired:\n\n(1) Assumption A is not satisfied by any commonly used activation functions. The authors only provided cubic ReLU as an example.\n\n(2) The randomization technique in this paper is not standard, and is pretty much an artifact to make the first order term in the Taylor expansion of neural networks small.\n\n(3) The $(\\| \\cdot \\|_{2,4})^8$ regularization term introduced on page 6 is highly unusual. Due to reparameterization, this regularization is on the distance towards initialization, indead of the norms of the weight parameters.\n\n(4) The training algorithm used in this paper is noisy SGD due to the need to escape from saddle points.\n\nDespite the issues mentioned above, I still think this paper is of good quality, and these limitations are understandable considering the difficulty to escape from the NTK regime. It would be interesting if the authors could provide some direct comparison between the generalization bound in this submission and existing generalization bounds in the NTK regime, for example the results in\n\nYuan Cao, Quanquan Gu, Generalization Error Bounds of Gradient Descent for Learning Over-parameterized Deep ReLU Networks\nYuan Cao, Quanquan Gu, Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks\n\nMoreover, since this paper studies optimization with regularization on the distance towards initialization, it would also be nice to compare with the following paper:\n\nWei Hu, Zhiyuan Li, Dingli Yu, Understanding Generalization of Deep Neural Networks Trained with Noisy Labels \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eYDESfcH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 presents an approach for going beyond NTK regime, namely the linear Taylor approximation for network function. By employing the idea of randomization this paper manages to reduce the magnitude of the linear part while the quadratic part is unaffected. This technique enables further analysis of both the optimization and generalization based on the nice property of quadratic approximation.\n\nI believe this paper should be accepted because of its novel approach to go beyond the linear part, which I view as a main contribution. Also, this paper is well written and presents its optimization result and proof in a clear manner. Although it is an innovation in the theoretical perspective, I still want to raise two questions about the object this paper trying to analyze:\n\n1. The activation function is designed so that it has really nice property: it has second-order derivative which is lipshitz. Actually I believe Assumption A is first motivated by cubic ReLU. Why is cubic ReLU so favorable in this paper? Is it possible to use quadratic ReLU in the proof? Also I wonder what is the key property of activation function which is allowed here.\n\n2. The network model considered here, is modified to a randomized neural network. So maybe this paper just circumvents the difficulty in going beyond NTK regime? I have this concern because in reality optimizing this network model seems intractable. To evaluate the loss $L(\\mathbf{W})$ or $L_{\\lambda}(\\mathbf{W})$ we take expectation over $\\Sigma$; when doing gradient descent, apparently the gradient also takes exponential time to compute.\n\nOverall, I believe this paper has high quality and I enjoyed reading it. However, I do expect response from authors which could address my concerns raised above. This can help me achieve a better understanding and a more precise evaluation on this paper.\n\n***\n\nI have read the author's response and decide to remain the rating as weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "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: This paper studies the training of over-parameterized two-layer neural networks by considering high-order Taylor approximation, and randomizing the network to remove the first order term in the network’s Taylor expansion. This enables the neural network training go beyond the recently so-called neural tangent kernel (NTK) regime. The authors also established the optimization landscape, generalization error and expressive power results under the proposed analysis framework. They showed that when learning polynomials, the proposed randomized networks with quadratic Taylor approximation outperform standard NTK by a factor of the input dimension. This is a very nice work, and provides a new perspective on NTK and beyond. All reviewers are in support of accepting this paper. 
Decision: Accept (Poster)