Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
Authors: Atsushi Nitanda
Taiji Suzuki
Venue: ICLR 2021 Oral (2021)
Keywords: stochastic gradient descent
two-layer neural network
over-parameterization
neural tangent kernel

Abstract: We analyze the convergence of the averaged stochastic gradient descent for overparameterized two-layer neural networks for regression problems. It was recently found that a neural tangent kernel (NTK) plays an important role in showing the global convergence of gradient-based methods under the NTK regime, where the learning dynamics for overparameterized neural networks can be almost characterized by that for the associated reproducing kernel Hilbert space (RKHS). However, there is still room for a convergence rate analysis in the NTK regime. In this study, we show that the averaged stochastic gradient descent can achieve the minimax optimal convergence rate, with the global convergence guarantee, by exploiting the complexities of the target function and the RKHS associated with the NTK. Moreover, we show that the target function specified by the NTK of a ReLU network can be learned at the optimal convergence rate through a smooth approximation of a ReLU network under certain conditions.

Published as a conference paper at ICLR 2021
OPTIMAL RATES FOR AVERAGED STOCHASTIC GRA- DIENT DESCENT UNDER NEURAL TANGENT KERNEL REGIME
Atsushi Nitanda Taiji Suzuki
1 Graduate School of Information Science and Technology. The University of Tokyo
2 Center for Advanced Intelligence Project, RIKEN
3 PRESTO, Japan Science and Technology Agency Email: nitannda @ niik.i..tooky..a..jpp "taiji oos....-
ABSTRACT
We analyze the convergence of the averaged stochastic gradient descent for over- parameterized two-layer neural networks for regression problems. It was recently found that a neural tangent kernel (NTK) plays an important role in showing the global convergence of gradient- based methods under the NTK regime, where the learning dynamics for overparameterized neural networks can be almost character- ized by that for the associated reproducing kernel Hilbert space (RKHS). However, there is still room for a convergence rate analysis in the NTK regime. In this study, we show that the averaged stochastic gradient descent can achieve the minimax optimal convergence rate, with the global convergence guarantee, by exploiting the complexities the target function and the RKHS associated with the NTK. More- over, we show that the target function specified by the NTK of a ReLU network can be learned at the optimal convergence rate through a smooth approximation of a ReL.U network under certain conditions.
INTRODUCTION
Recent studies have revealed why a stochastic gradient descent for neural networks converges to global minimum and why it generalizes well under the overparameterized setting in which the number of parameters is larger than the number of given training examples. One prominent approach to map the learning dynamics for neural networks into function spaces and exploit the convexity of the loss functions with respect to the function. The neural tangent kernel (NTK) (Jacot et al.) (2018) has provided such connection between the learning process of a neural network and a kernel method in reproducing kernel Hilbert space (RKHS) associated with NTK.
The global convergence of the gradient descent was demonstrated Du et al. (2019b;; Allen-Zhu et al. (2019a); Du et al. (2019a); Allen-Zhu et al. (2019b) through the development of a theory of In these theories, the positivity of the NTK on the given training
NTK with the overparameterization examples plays crucial role in exploiting the property of the NTK. Specifically, the positivity of the Gram-matrix of the NTK leads to a rapid decay of the training loss, and thus the learning dynamics be localized around the initial point of neural network with the overparameterization. resulting in the equivalence between two learning dynamics for neural networks and kernel methods with the NTK through linear approximation of neural networks. Moreover, Arora al. (2019a) provided generalization bound of 1/22) where T is the number of training examples, gradient descent under the positivity assumption of the NTK. These studies provided the first steps in understanding the role of the NTK.
However, the eigenvalues the NTK converge to zero as the number of examples increases, as shown Su & Yang (2019) (also see Figure T). resulting in the degeneration of the NTK. This phenomenon indicates that the convergence rates in previous studies in terms of generalization are generally slower than 11/2 owing to the dependence on the minimum eigenvalue. Moreover, Bietti Mairal (2019): Ronen et al. 2019: Cao et al. (2019) also supported this observation by providing precise

---

Published as a conference paper at ICLR 2021
estimation of the decay of the eigenvalues, and Ronen et al. (2019); Cao al. (2019) proved the spectral bias (Rahaman et al.; (2019) for a neural network, where lower frequencies are learned first using a gradient descent.
By contrast, several studies showed faster convergence rates of the (averaged) stochastic gradient descent in the RKHS in terms of the generalization (Cesa-Bianch) al. 2004 Smale & Yao [006)
Ying & Zhou 2006 Neu & Rosasco 2018: Lin et al. (022)) In particul ar. by extending the results
in fintt-dimmeniional case (Bach & Moulines 2013). Dieuleveut & Bach (0016); Dieuleveut et al.
(017) showed convergence rates of ((T 2 depending on the complexity r E [1/2, 1] of the
target functions and the decay rate B > 1 of the eigenvalues of the kernel (a.k.a. the complexity of the hypothesis space), In addition, extensions to the random feature settings (Rahimi & Recht 2007
Rudi & Rosasco 2017 Carratino al. 2018), to the multi-pass variant (Pillaud- Vivien al. 2018b).
and to the -verrging and mini batching variant (Mücke et al. 2019) have been developed.
is always faster than 0(221/2) and is known as the minimax optimal rate (Caponnetto & De Vito 2007 Blanchard & Mücke, 2018). Hence, a gap exists between the theories regarding NTK and kernel methods. In other words, there is still room for an investigation into a stochastic gradient descent due to a lack of specification of the complexities of the target function and the hypothesis space. That is, to obtain faster convergence rates, we should specify the eigenspaces of the NTK that mainly contain the target function (i.e., the complexity of the target function), and specify the decay rates of the eigenvalues of the NTK (i.e., the complexity of the hypothesis space), as studied in kernel methods (Caponnetto & De Vito 2007, (teinwarr et al. 2009 Dieuleveut Bach 2016). In summary, the fundamental question this study is
Motivation. The convergence rate of (TT Zvpei
-Zei
Can stochastic gradient descent for overparameterized neural networks achieve the optimal rate in terms of the generalization by exploiting the complexities of the target function and hypothesis space?
In this study, we answer this question in the affirmative, thereby bridging the gap between the theories of overparameterized neural networks and kernel methods.
10
dm5
d-10
d=100
k-th eigervalue
10
20
10
1014
10-1
5000
100000
5000
10000
5000
10000
Figure 1: An estimation of the eigenvalues of Ex using two-layer ReLU networks with a width of M = 2 x 10 The number of uniformly randomly generated samples the unit sphere is 10* and the dimensionality of the input space is d E {5, 10, 100].
1.1 CONTRIBUTIONS
The connection between neural networks and kernel methods is being understood via the NTK, but it is still unknown whether the optimal convergence rate faster than 1/2) is achievable by certain algorithm for neural networks. This the first paper to overcome technical challenges of achieving the optimal convergence rate under the NTK regime. We obtain the minimax optimal convergence rates (Corollary[) D. inherited from the learning dynamics in an RKHS, for an averaged stochastic gradient descent for neural networks. That is, we show that smooth target functions efficiently specified by the NTK are learned rapidly at faster convergence rates than O(IvTT). Moreover, we for a smooth approximation of the obtain an explicit optimal convergence rate of O (Tawia
-2nd
ReLU network (Corollary 2), where d is the dimensionality of the data space and r is the complexity of the target function specified by the NTK of the ReLU network.
1.2 TECHNICAL CHALLENGE
The key showing global convergence (Theorem I is making the connection between kernel methods and neural networks in some sense. Although this sort of analysis has been developed
in several studies (Du al. 2019h Arora et al. 2019a Weinan al. 2019: Arora al. 2019b
2

---

Published as a conference paper at ICLR 2021
would like to emphasize that our results cannot be obtained by direct application of their results. A naive idea is to simply combine their results with the convergence analysis of the stochastic gradient descent for kereel methods, but it does not work. The main reason is that we need the I--bbound weighted by a true data distribution on the gap between dynamics of stochastic gradient descent for neural networks and kernel methods if try derive a convergence rate of population risks for neural networks from that for kernel methods, However, such a bound is not provided in related studies. Indeed, to the best of our knowledge, all related studies make this kind of connection regarding the gap on training dataset or sample-wist high probability bound (Lee) al. [019 Arora et al.) (2019)). That is, statement "for every input data x with high probability 1 (x) Pntk (
Lee al. 2019; 2020),
(t) (z)1 < E" cannot yield a desired statement "Il.gmm Inck La(px) < E" where Grai and
Intk are t-th iterate of gradient descent for a neural network and corresponding iterate described by NTK, and Il La(ex) is the Iz-norm weighted by a marginal data distribution px over the input space. Moreover, we note that we cannot utilize the positivity of the Gram-matrix of NTK which plays a crucial role in related studies because we consider the population risk with respect to || [l22(ex) rather than the empirical risk.
To overcome these difficulties we develop different strategy of the proof. First, make bound on the gap between two dynamics of the averaged stochastic gradient descent for a two-layer neural network and its NTK with width M (Proposition A), and obtain a generalization bound for this intermediate NTK (Theorem Alin Appendix). Second, we remove the dependence on the width of M from the intermediate bound. These steps are not obvious because we need a detailed investigation to handle the misseecification of the target function by an intermediate NTK. Based on detailed analyses, we obtain a faster and precise bound than those in previous results (Arora et al. 2019a)
The following is an informal version of Proposition A providing new connection between a two-layer neural networks and corresponding NTK with width M.
Proposition 1 (Informal). Under appropriate conditions we simultaneously run averaged stochastic gradient descent for a nearal network with width of M and for its NTK. Assume they share the same hyper-parameter and examples to compute stochastic gradients. Then, for arbitrary number of iterations T E Z+ and >> O, there exists M E Zz4 depending only on T and e such that Vt S T,
ll 9 (t) (ixlll..(ex)) (px) S,
(t) where Tau and Fatk are iterates obtained by averaged stochastic gradient descent.
(t)
This proposition is the key because it connects two learning dynamics for a neural network and its NTK through overparameterization without the positivity of the NTK. Instead of the positivity, this proposition says that overparameterization increases the time stayed in the NTK regime where the learning dynamies for neural networks can be characterized by the NTK. As result, the averaged stochastic gradient descent for the overparameterized two-layer neural networks can fully inherit preferable properties from learning dynamics in the NTK long as the network width is sufficiently large. See Appendix A for detail.
1.3 ADDITIONAL RELATED WORK
Besides the abovementioned studies, there are several works (Chizat Bach, 2018b, Wu et al. 2019 Zou & Gu 2019) that have shown the global convergence of (stochastic) gradient descent for overparameterized neural networks essentially relying on the positivity condition of NTK. Moreover, faster convergence rates of the second-order methods such as the natural gradient descent and Gauss- Newton method have been demonstrated (Zhang et al. 2019) Cai et al. 2019) in the similar setting, and the further improvement of Gauss-Newton method with respect the cost per iteration has been conducted in Brand et al. 2020).
There have been several attempts to improve the overparameterization size in the NTK theory. For the regression problem. Song & Yangl (2099) has succeeded in reducing the network width required in Du et al. (2019b) by utilizing matrix Chernoff bound. For the classification problem, the positivity condition can be relaxed to a separability condition using another reference model (Cao & Gu 2019a by Nitanda al.) 2019 Ji & Telgarsky 2019). resulting in mild overparameterriztton and generalization bounds of O(T 172) or O(T 174) classification errors.
For an averaged stochastic gradient descent on classification problems in RKHSs, linear convergence rates of the expected classification errors have been demonstrated in Pillaud- Vivien al. (2018));
3

---

Published as a conference paper at ICLR 2021
Nitanda & Suzuki (2019). Although our study focuses regression problems, describe how to combine their results with our theory in the Appendix.
The mean field regime (Nitanda & Suzuki 2017; Mei et al. 2018 Chizat & Bach 201 8a) that is different limit of neural networks from the NTK is also important for the global convergence analysis of the gradient descent. In the mean field regime, the learning dynamics follows the Wasserstein gradient flow which enables us to establish convergence analysis in the probability space.
Moreover, several studies (Allen-Zhu & Li 2019 Bai & Lee 2019 Ghorbani et al. 2019 Allen-Zhu
& Li 2020 Li et al., 2020 Suzuki 2020) attempt to show the superiority of neural networks over kernel methods including the NTK. Although it is also very important to study the conditions beyond the NTK regime, they do not affect our contribution and vice versa. Indeed, which method is better depends on the assumption on the target function and data distribution, so is important to investigate the optimal convergence rate and optimal method in each regime. As shown in our study, the averaged stochastic gradient descent for learning neural network achieves the optimal convergence rate if the target function is included in RKHS associated with the NTK with the small norm. It means there are no methods that outperform the averaged stochastic gradient descent under this setting.
2 PRELIMINARY
Let X' C Rd and y C R be the measurable feature and label spaces, respectively, We denote by data distribution
X' V by px the marginal distribution on X, and by p(-|X) the conditional distribution on Y. where (X, (2 2) and let g : R be hypothesis. The expected risk function is defined follows:
p. Let f(z, y) (z R. y E )) be the squared loss function
((g) def 1(xx))((((X)))))))))
(1)
The Bayes rule 9p : X R is a global minimizer of L over all measurable functions.
For the least squares regression, the Bayes rule is known to be 9p (X) Ey [Y]X] and the excess risk of hypothesis (which is the difference between the expected risk of and the expected risk of the Bayes rule go) expressed squared L2(px) (a(px)-distance between y and go (for details, see
Cucker & Smale 2002) up to constant:
- 1
((g) -(gp)-
where ||- (1xafxx) is L2-norm weighted by px defined as IIgl del (X)x(x))xxxx)) (g L2(p))). Hence, the goal of the regression problem is to approximate Ip in terms of the ddistacee in a given hypothesis class.
Two-layer neural networks. The hypothesis class considered in this study is the set of two-layer neural networks, which is formalized as follows. Let M E E, be the network width (number of hidden nodes). Let (01..... aM) E R (a, I) be the parameters (bi..... bM) E I M (b, E ( be the parameters of the input layer, and (CI..... E RM (c,- E R) be the bias parameters. We denote by @ the collection of all parameters (a, B,c), and consider two-layer neural networks:
the output layer, B
ge (x)
Σ
(0, 700,)
VM
where Ø R R is activation function and 7 0 is scale of the bias terms.
Symmetric initialization. We adopt symmetric initialization for the parameters O. Let ( (o ...... (0)) TT B(0) for a, B. and c, respectively. Assume that the number of hidden units M E Z+ is even. The
(0), ). and ( (c( ..... C.M ( T denote the initial values (b(0) ..... bbg
(0)
R for r E ( + 1,..., M). where R > 0 a positive constant. Let μio be uniform distribution on the sphere gd-1 {b E Rd [|b|2 = 1) C Rd used to initialize the parameters for the input layer. The parameters for the input layer are initialized as b (0) 4 for E {1..... }. where (b( )
parameters for the output layer are initialized as (0)) R for (l,..., //2 } and (
4

---

Published as a conference paper at ICLR 2021
independently drawn from the distribution 140. The bias parameters initialized as (0) 0 for r E (l..... M. The aim of the symmetric initialization is to make an initial function fe = 0, where O = (a!o) B(O,, c(O)). This is just for theoretical simplicity. Indeed, we can relax the symmetric initialization by considering an additional error stemming from the nonzero initialization in the function space.
Regularized expected risk minimization. Instead of minimizing the expected risk ① itself, we consider the minimization problem of the regularized expected risk around the initial values:
min ((ge) + 2 (Ia- (0 1 + B - 11 + ||c I|c- c000
(3)
where the last term is the Lg-reuularization at an initial point with regularization parameter À > 0. This regularization forces iterations obtained by optimization algorithms to stay close to the initial value, which enables us to utilize the better convergence property of regularized kernel methods.
Averaged stochastic gradient descent. Stochastic gradient descent is the most popular method for solving large-scale machine learning problems, and its averaged variant is also frequently used to stabilize and accelerate the convergence. In this study, we analyze the generalization ability of an averaged stochastic gradient descent. The update rule is presented in Algorithm T Let (0)) = (a ((),, , denote the collection of (-th iterates of parameters a E RR,,, B E RRXM and c E R.M, At 1-th íterate, stochastic gradient descent using a learning rate ' for the problem (3) with respect to a, B, c is performed on lines 4-6 for a randomly sampled example (z,, 3c) ~ p. These updates can be rewritten in an element-wise fashion follows. For r E {I,...,M} M),
a(t+)) (0) = (1 (a)) - a T.M 1/2 (g (z1) - (i)o(b(0) It + 7c("),
8 ((++1) ((0) =(1 (1- ())(((()) (10) M 1/2 (g (1z) y1)a d'(b 2s ycc nccf9) )art.
of (1+1) ET = (1 - (C)) (1) - - )- - - 1/2 (ge (xx) - ve)a (1) yo (b(O) It + 707 (t)),
where (1) = (a) (al")...,.!!)) J, B(O = (1
((0) M and e()) = (c(t) (4) CM T. Finally, a
weighted average using weights a of the history of parameters is computed on line 9. In our theory,
we consider the constant learning rate 77 17 and uniform averaging a = 1/(T + 1).
Algorithm 1 Averaged Stochastic Gradient Descent
1: Input: number of iterations T. regularization parameter X, learning rates (n))T1 averaging weights (at)T initial values ( = (a))),B()) c(0))
B(0),
2: for tort=00
= 0 to T 1 do
3: Randomly draw a sample (Iz; V1) ~ p
4:
((++1) + (t)) - n7, m0da( (21). y0) - -7 m(a((()) (0)))
5:
B(++1) + B(t) - n. (xz),
Th MN(((1)) - B(o))
6:
c(l+1) + (t) m.de(gem (2),,11) v1) - Th M((((())) (())
7:
((++)) + (1(++1), B(t+l), (l(t))))
8: end for
9: θ
T' 1 (1) It a, B(), Ein a,t(t)
10: Return I
Integral and Covariance Operators. The integral and covariance operators associated with the kernels, which are the limit of the Gram-matrix as the number of examples goes to infinity, play crucial role in determining the learning speed. For given Hilbert space H. we denote by @H the tensor product on H. that is, v(f.g) E H2, f @x defines a linear operator; E H H> (f @H h (f, h) g E H. Note that f 0h g naturally induces bilinear function: (h, h²)
H x - (Lf SH h,, h'yx = (f. fi) (g. h²))))
30- When H. is reproducing kernel Hilbert space
(RKHS) associated with a bounded kernel k X X R. the covariance operator Σ H + H is
defined as follows: Set Kx def k(X,,) and
Σ Exxpx [Kx ΦH Kx).
5

---

Published as a conference paper at ICLR 2021
Note that the covariance operator is restriction of the integral operator L2(px):
f I2(px) (()) E L2(px).
We the symbol above for convenience with slight abuse of notation. Be- cause Σ is a compact self-adjoint operator on L2(px). E has the following eigendecomposi- pair of eigen-
tion: Σf Ei=1 A (1) Lx(ex) oi for f L2(px), where {(),, values and orthogonal eigenfunctions in L2(px). For s E R, the power E is defined as E Ei X, (f, 6.) La(px) 9:-
MAIN RESULTS: MINIMAX OPTIMAL CONVERGENCE RATES
In this section, present the main results regarding the fast convergence rates of the averaged stochastic gradient descent under a certain condition on the NTK and target function 9p-
Neural tangent kernel. The NTK is recently developed kernel function and has been shown to be extremely useful in demonstrating the global convergence of the gradient descent method for neural networks (cf., Jacot et al. (2018); Chizat & Bach| (2018b); Du al. (2019b); Allen-Zhu et al.
22019a by: Arora et al. 2019a)). The NTK in setting is defined follows: Vz, Vz X,
Roc (z, ) def Egco (b) (b z')] (x
x' )) |a (b) 2))0 (b 2'),, (4)
where the expectation taken with respect ((0) ~ 14g- The NTK the key to the global convergence of neural network because it makes connection between the (averaged) stochastic gradient descent for a neural network and the RKHS associated with ko (see Proposition AA). Although this type of connection has been shown in previous studics AArra al. 2019b] Weinan et al. 2019 Lec et al.) 2019 2020), note that their results are inapplicable to our theory because we consider the population risk. Indeed, our study is the first to establish this connection for an (averaged) stochastic gradient descent in terms of the uniform distance on the support of the data distribution, enabling us to obtain faster convergence rates. We note that NTK kic is the sum of two NTKs, that is, the first and second terms in are NTKs for the output and input layers with bias, respectively.
3.1 GLOBAL CONVERGENCE ANALYSIS
Let Hoo be an RKHS associated with NTK koo and Eoc. be the corresponding integral operator. Let {X: denote the eigenvalues of Exo sorted in decreasing order: A1 2 X2
Assumption 1.
(A1) There exists > such that ||o"|loo S C. ||o' S 2, and [o()) S 1 + lu for Vu E
(A2) supp(px) C. {Ø E Rd || I 13, y c [-1, 1], R 1, and y E [0,
(A3) There exists r E [1/2,1] such that go E Ex (L2(px)) ie.. | <0.
(A4) There exists 3 > such that ); ()-
Remark.
(A1): Typical smooth activation functions, such as sigmoid and tanh functions, and smooth approximations of the ReLU, such as swish (Ramachandran et al. 2017), which performs as well as even better than the ReLU, satisfy Assumption (A1). This condition is used to relate two learning dynamics between neural networks and kernel methods (see Proposition A).
(A2): The boundedness (A2) of the feature space and label are often assumed for stochastic optimization and least squares regression for theoretical guarantees (see Steinwart et al. (2009)). Note that these constants (A2) can be relaxed to arbitrary constants.
(A3): Assumption (A3) measures the complexity of 9o because E.o can be considered smoothing operator using a kernel h A larger r indicates faster decay of the coefficients of expansion of 9p based on the eigenfunctions of Eno and smoothens 9p. In addition, Er, (T<(p)))

---

Published as a conference paper at ICLR 2021
(px())) Hos resulting in 9p E Hoo This condition is used to control the bias of the estimators through In-regularriztion. The notation Ex Dp represents any function G E L2(xx) such that 9p = G.
shrinks with respect to and E 2
(A4); Assumption (A4) controls the complexity of the hypothesis class Ho. A larger indicates a faster decay of the eigenvalues and makes His smaller. This assumption is essentially needed to bound the variance of the estimators efficiently and derive fast convergence rate. Theorem 1 and Corollary 1, 2 hold even though the condition in (A4) is relaxed to X; O(i- and the lower bound X = D P) is necessary only for making obtained rates minimax optimal.
Under these assumptions, we derive the convergence rate of the averaged stochastic gradient descent for overparameterizee two-layer neural network, the proof is provided in the Appendix.
Theorem 1. Suppose Assumptions (A1)-(A3) hold. Run Algorithm 2 with a constant learning rate satisfying 4(6 + A)n S 1. Then, for any e > 0, |E 2 À > 0, E 1), and T E Z,,, there exists Ma E 2+ such that for any M 2 Mo. the following holds with high probability at least 1 6 over the random choice of features (
E Bllggm gpllix(ex) Seta (x2r1230 9o gollizeex)
+ T +1 I1sollin. + (T 1)2
1
1
T+1 [111l91liz I1
(1liaoo)))) Tr (Neo (Eoo 11)
where a > 0 is a universal constant and geg(T) is an iterate obtained through Algorithm 7
Remark. The first term and second term X 22r|E 1 (plliz(xx)) are the approximation error and bias, which can be chosen to arbitrarily small. The first term comes from the approximation of the NTK using finite-sized neural networks, and the second term comes from the I-gregularizztion, which coincides with a bias term in the theory of least squares regression (Caponnetto & De Vito 2007). The third and fourth terms come from the convergence of the averaged semi-stochastic gradient descent (which is considered in the proof) in terms of the optimization. The appearance of an inverse dependence strong convexity, which slows down the convergence speed of the optimization methods (Rakhlin et al. 2012). The term Tr (Eeo (E.g + x1)-1) is the variance from the stochastic approximation of The gradrent, and it is referred to as the degree of freedom or the effective dimension, which is known to be unavoidable in kernel regression problems (Caponnetto & De Vito 2007 Dieuleveut & Bach
À in the fourth term is common because smaller À indicates weaker
2016 Rudi& & Rosasco 2017).
Global convergence in NTK regime. This theorem shows the global convergence to the Bayes rule 9p. which is a minimizer over all measurable maps because the approximation term e can be arbitrarily small by taking sufficiently large network width M. The required value of M has an exponential dependence on T; note, however, that reducing Af is not the main focus of the present study. The key technique is to relate two learning dynamics for two-layer neural networks and kernel methods in an RKHS approximating Hox up to a small error. Unlike existing studies (Du et al.. 2019b Arora al. 2019a b Weinan et al. 2019 Lee al.. 2019 2020) showing such connections, we establish this connection in term of the Loxe (px) -norm, which is more useful in a generalization analysis. Moreover, existing studies essentially rely on the striet positivity of the Gram-matrix to localize all iterates around an initial value, which can slow down the convergence rate in terms of the generalization because the convergence of the eigenvalues of the NTK to zero affects the Rademacher complexity. By contrast, our theory succeeds in demonstrating the global convergence in the NTK regime without the positivity of the NTK.
3.2 OPTIMAL CONVERGENCE RATE
We derive the fast convergence rate from Theorem I by utilizing Assumption (A4), which defines the complexity of the NTK. The regularization parameter À mainly controls the trade-off within the generalization bound, that is, a smaller value decreases the bias term but increases the variance term including the degree of freedom. The degree of freedom Tr (Eoe (Exe + AI)-1) can be specified by imposing Assumption (A4) because it determines the decay rate of the eigenvalues of E As a result, this tfade-off between bias and variance depending on the choice of X becomes clear, and
7

---

Published as a conference paper at ICLR 2021
can determine the optimal value. Concretely, by setting À = T- the sum of the bias and variance terms is minimized, and these terms become asymptotically equivalent.
Corollary 1. Suppose Assumptions (A1)-(A4) hold. Run Algorithm ! with the constant learning rate 17 ((1) satisfying 4(6 + Am I 1 and X = T-8/1228+1)) Then, for any e >> 0, 8 E (0.1) 1) and E 24 satisfying [| llop 2 X, there existy Mo & 244 such that for any M 2 Mo, the following holds with high probability at least 1 - over the random choice of random features (
Blllgre spllia(ex) c o.T oTTI5-11 I-FFI
-2nd
11+11159plli.. splliatpx))
where a > O is universal constant and (g is an iterate obtained by Algorithm 7
The resulting convergence rate is O(T229411 with respect T by considering a sufficiently large network width of M such that the error stemming from the approximation of NTK can be ignored. Because T corresponds to the number of examples used to learn a predictor 9g(7), this convergence rate is simply the generalization error bound for the averaged stochastic gradient descent. In general, this rate is always faster than 7-11/2 and is known to be the minimax optimal rate of estimation (Caponnetto & De Vito 2007 Blanchard & Mücke, 2018) in Ho in the following sense. Let ((3,r) be a data distribution class satisfying Assumptions (A2))-A4). Then,
lim lim inf inf sup P [| -9p-- (x(x)) > 21211 2 - T-400 A(T)
1,
where p is taken in r(B,r) and 1T taken over all mappings (Ie, 1= + h(T) E Hoo-
3.3 EXPLICIT OPTIMAL CONVERGENCE RATE FOR SMOOTH APPROXIMATION OF RELU
For smooth activation functions that sufficiently approximate the ReLU, an optimal explicit conver- gence rate can be derived under the setting in which the target function is specified by NTK with the ReLU, and the data are distributed uniformly on sphere. We denote the ReLU activation by (u) max(0, u} and a smooth approximation of ReLU by o(*), which converges to ReLU, as 8 + do in the following sense. We make alternative assumptions to (A1), (A2), and (A3):
Assumption 2.
(A1') (()) satisfies (A1). g()) and o(ا)' converge pointwise almost surely to a and o' as s - cc.
(A2') Px is a uniform distribution on {a E Rd || =
1-1, (1,1,, R= 1, and y E (0, 1].
(A3') The condition (A3) is satisfied by the NTK associated with the ReLU activation o.
(A1') and (A2') are special cases of (A1) and (A2). There are several activation functions that satisfy this condition, including swish (Ramachandran et al. 2017): a (u) [+exp(-su]) Under these
conditions, we can estimate the decay rate of the eigenvalues for the ReLU as 3 = 1 + उーं yielding the explicit optimal convergence rate by adapting the proof of Theorem I to the current setting. Note that Algorithm| is run for a neural network with a smooth approximation (()) of the ReLU..
Corollary 2. Suppose Assumptions (A1'), (A2'), and (A3') hold. Run Algorithm 7 with the constant learning rate 1) O(1) satisfying 4(6 + A)n & 1, and X = (2d/
Given any >> O. E 1) and T E Z4 satisfying [|E 2 2X, let s be an arbitrary and sufficiently large positive value. Then, there exists Mo E Et such that for any M 2 Mo. the following holds with high probability at least -8 8 over the random choice of random feutures (());
E [llggm - go [ox)) S e of
2nd
(1 (1+ Ip (
where a > is universal constant and gotty is an iterate obtained by Algorithm
7
4 EXPERIMENTS
We verify the importance of the specification of target functions by showing the misspecificationn significantly slows down the convergence speed. To evaluate the misspecification, consider
8

---

Published as a conference paper at ICLR 2021
single-layer learning well as the two-layer learning, and see the advantage of two-layer learning. Here, note that, with evident modification of the proofs, the counterparts of Corollaries for learning single layer also hold by replacing Eo with the covariance operator Ea associated with ka,s0 oo), where
[ and
( 2booo
ka (2, x') Eggon (b
x)0((()))=')) (
ko (x, x²) = 112 Ju + (b'(6 ( x')],
which components of o ka, bi corresponding to the output and input layers, respectively. Then, from Corollaries and 2 a Bayes rule 9p is learned efficiently by optimizing the layer which
has small norm Σ Jo L2(ex) for Σ (Ea,00, Eb,0o 8oo
1011
1044
10th
L2-horm
207
Z+
101
10a
109
3.5
0.6
0.7
0.8
0.9
1,0
0.5
0.6
0.7
0.8
0.9
1.3
0.5
0.6
0.7
0.8
0.9
1.0
0.1
0.23
037
0.30
0.10
0:55
008
0.54
0:31
1003 2000
1000
2000
1000 2000
Top: Estimation of "E""9olleztrr (r E [0.5, 1]) for integral operators Σ E (En,so, Et,oe, }x²} of two-layer ReLU networks. Bayes rules Ip are set to the average eigen- functions of 00 (left), D0 (middle), and Eo (right), Bottom: Learning curves of test errors for Algorithm with two-layer swish networks.
Figure 2:
Experimental settings. Figure 2 (Top) depicts norms 12>l for V E (Di, Lo 2oo Bayes rules 9p are averages eigenfunctions of Ma,>c (left). 29.00 (middle), and E (right) corre- sponding to the 10-largest eigenvalues excluding the first and second, with the setting: = 1/22//)) = 10,2, and px is the uniform distribution on the unit sphere in IR?, To estimate eigenvalues and eigenfunctions, draw -0mmsaeses from px and M x 10 -hiddenenn nodes of two-layer ReLU.
Empirical observations. We observe 9 has the smallest which specifies 9p and has comparably small norm with respect to Exe even for the cases where gp specified by Ea or Eo. This observation suggests the efficiency of learning corresponding layer to 9p and learning both layers, and it is empirically verified. We run Algorithm [ 10-times with respect to output (blue), input (purple), and both layers (orange) of two-layer swish networks with 10. Figure (Bottom) depicts the average and standard deviation of test errors. From the figure, we see that learning corresponding layer to Ip and both layers exhibit faster convergence, and that misspecification significantly slows down the convergence speed in all cases.
with respect to the integral operator
CONCLUSION
We analyzed the convergence of the averaged stochastic gradient descent for overparameterized two- layer neural networks for regression problem. Through the development of a new proof strategy that does not rely on the positivity of the NTK, we proved that the global convergence (Theorem) [] relies only on the overparameterizaaton. Moreover, we demonstrated the minimax optimal convergence rates (Corollary in terms of the generalization error depending the complexities of the target function and the hypothesis class and showed the explicit optimal rate for the smooth approximation of the ReLUU.

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
AN was partially supported by JSPS Kakenhi (19K20337) and JST-PRESTO. TS was partially supported by JSPS KAKENHI (18K19793, 18H03201, and 20H00576), Japan Digital Design, and IST CREST.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems 32, pp. 9017-9028, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning, arXiv preprint wwxiv:2001.044111 2020.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Proceedings of International Conference on Machine Learning 36, pp. 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate training recurrent neural networks. In Advances in neural information processing systems, pp. 6676-6685 2019b.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterrzed two-layer neural networks. Proceedings of International Conference on Machine Learning 36, pp. 322-332, 2019a.
Sanjeev Arora, Simon $ Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, pp. 8139-8148, 2019b.
Kendall Atkinson and Weimin Han. Spherical harmonics and approximations on the unit sphere: an introduction. Springer, 2012.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-60 1,12, 2017a.
Francis Bach. On the equivalence between kernel quadrature rules and random feature expansions. The Journal of Machine Learning Research, 18(1):714-751, 201
Francis Bach and Eric Moulines. Non-strongly-cconee smooth stochastic approximation with convergence rate O()/n). In Advances in Neural Information Processing Systems 26, pp. 773-781, 2013.
Yu Bai and Jason D Lee, Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference Learning Representations, 2019.
Peter L Bartleu, Michael I Jordan, and Jon D McAuliffe, Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101 :4134)):: 2006.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernlss. In Advances in
Neural Information Processing Systems, pp. 12873-12884, 2019.
Gilles Blanchard and Nicole Mücke, Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18(4):971-1013 2018.
Jan van den Brand, Binghui Peng, Zhao Song, and Omri Weinstein. Training (overparametrized) neural networks in near-linear time. arXiv preprint arXiv:2006. 100.200008.184..... 11648, 2020.
Tianle Cai, Ruiqi Gao, Jikai Hou, Siyu Chen, Dong Wang, Di He, Zhihua Zhang, and Liwei Wang. gauss-newton newton method: Learning overparameterized neural networks for regression problems. arXiv preprint arXiv: /905. 1675, 2019.
Gram- gauss-
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint 1902 2019a.
10

---

Published as a conference paper at ICLR 2021
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint 1rXiv:1905.13220, 2019b.
Yuan Cao, Zhiying Fang, Yue Wu, Ding- Bung-uun Zhou, and Quanquan Gu. Towards understanding the spectral bias of deep learning. arXiv preprint arXiv: 191.00 2019.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Luigi Carratino, Alessandro Rudi, and Lorenzo Rosasco. Learning with sgd and random features. In Advances in Neural Information Processing Systems 31, pp. 10192-10203, 2018.
Nicolo Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line learning algorithms. IEEE Transactions on Information Theory, 50(9):205022577, 2004.
Lenaic Chizat and Francis Bach. the global convergence of gradient descent for over-parameterized models using optimal transport. In Advances in Neural Information Processing Systems 31, pp. 3040-3050, 2018a
Lenaic Chizat and Francis Bach, A note on lazy training supervised differentiable programming. arXiv preprint arXhv:1812.07955 2018b.
Felipe Cucker and Steve Smale. On the mathematical foundations of learning. Bulletin of the American mathematical society, 39(1):1-49, 2002.
Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. The Annals of Statistics, 46(4):1333-139,, 2016.
Aymeric Dieuleveut, Nicolas Flammarion, and Francis Bach. Harder, better, faster, stronger con- vergence rates for least-squares regression. The Journal of Machine Learning Research, 18(1): 3520-3570,201
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In Proceedings of International Conference on Machine Learning 36, pp. 1675-1685, 2019a.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. International Conference on Learning Representations 2019b.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Limitations of lazy training of two-layers neural network. In Advances in Neural Information Processing Systems 32, pp. 9111 9121, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31, pp. 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. arXiv preprint arXiv:1909. 12292, 2019.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in neural information processing systems, pp. $570-8581, 2019.
Jason D Lee, Ruoqi Shen, Zhao Song, and Mengdi Wang. Generalized leverage score sampling for neural networks. In Advances in Neural Information Processing Systems, 2020.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural 2020.
networks beyond ntk. In Proceedings of Conference on Learning Theory 33, pp.
Junhong Lin, Alessandro Rudi, Lorenzo Rosasco, and Volkan Cevher. Optimal rates for spectral algorithms with least-squares regression over hilbert spaces. Applied and Computational Harmonic Analysis, 48(3):868-88) 890, 2020.
11

---

Published as a conference paper at ICLR 2021
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E7665-E776 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
Nicole Mücke, Gergely Neu, and Lorenzo Rosasco. Beating sgd saturation with tail-averaging and minibatching. In Advances in Neural Information Processing Systems, pp- 12568-12577 12577, 2019.
Gergely Neu and Lorenzo Rosasco. Iterate averaging regularization for stochastic gradient descent. In Proceedings of Conference On Learning Theory 32, pp.
2018.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint arXiv: 1712.0542.... 2017.
Atsushi Nitanda and Taiji Suzuki. Stochastic gradient descent with exponential convergence rates of expected classification errors. In Proceedings of International Conference on Artificial Intelligence and Statistics 22, pp. 1417-1426, 2019.
Atsushi Nitanda, Geoffrey Chinot, and Taiji Suzuki. Gradient descent learn less over-parameterized two-layer neural networks on classification problems. arXiv preprint arXiv:1905.008870, 2019.
Loucas Pillaud- Viviee, Alessandro Rudi, and Francis Bach. Exponential convergence of testing for stochastic gradient methods. In Proceedings of Conference on Learning Theory 31, pp. 1-47, 2018a
Loucas Pillaud- Vivien, Alessandro Rudi, and Francis Bach. Statistical optimality of stochastic gradient descent on hard learning problems through multiple passes. In Advances in Neural Information Processing Systems, pp. 8114-8124, 2018b.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In Proceedings of International Conference Machine Learning 36, pp. 5301-5310, 2019.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems 20, pp. 1177-1 2007.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of International Conference on Machine Learning 29, pp. 1571-1578, 2012.
Prajit Ramachandran, Barret Zoph, and Quoc V. Le. Searching for activation functions. arXiv preprint arXiv:1710.05941 2017.
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems, pp. 4763-4772, 2019.
Alessandro Rudi and Lorenzo Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems, pp. 3215-3225, 2017.
Steve Smale and Yuan Yao. Online learning algorithms. Foundations of computational mathematics, 6(2):145-170, 2006.
Zhao Song and Xin Yang. Quadratic suffices for over-parametrrizatoon via matrix chernoff bound. arXiv preprint /0t6.:990000360 2019.
Ingo Steinwart, Don R Hush, and Clint Scovel. Optimal rates for regularized least squares regression. In Proceedings of Conference Learning Theory 22, pp. 79-93, 2009.
Lili Su and Pengkun Yang. On learning over- parameterized neural networks: A functional approx- imation perspective. In Advances in Neural Information Processing Systems, pp. 2637-2646. 2019.
12

---

Published as a conference paper at ICLR 2021
Taiji Suzuki. Generalization bound of globally optimal non-convex neural network training: Trans- portation map estimation by infinite dimensional langevin dynamics. Advances in Neural Information Processing Systems, 2020.
Weinan, Chao Ma, and Lei Wu. A comparative analysis of optimization and generalization properties of two-layer neural network and random feature models under gradient descent dynamics. Science China Mathematics, pp. 1-24, 2019.
Xiaoxia Wu, Simon S Du, and Rachel Ward. Global convergence of adaptive gradient methods for an over-parameterized neural network. arXiv preprint arXiv: 2019.
Yiming Ying and D-X Zhou. Online regularized classification algorithms. IEEE Transactions Information Theory, 52(1 ()477757744888 2006.
Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natural gradient descent for over-parameteriied neural networks, In Advances in Neural Information Processing Systems, pp. 8082-8093, 2019.
Tong Zhang. Statistical behavior and consistency of classification methods based on convex ris minimization. The Annals of Statistics, 32(1):56-134, 2004.
Difan Zou and Quanquan Gu. An improved analysis of training over weerpparameterized deep neural networks. In Advances in Neural Information Processing Systems, pp. 2053-2066 2019.
13

---

Published as a conference paper at ICLR 2021
Appendix
A PROOF SKETCH OF THE MAIN RESULTS
provide several key results and proof sketch Theorem] 1 and Corollary [ We first recall definition of stochastic gradients of L in general RKHS (H. (1)x) associated with uniformly
bounded real-valued kernel function X x X - R. We set Kx = k(X,,), -). Then, it follows that for Vgg vh H.
Lig + h) L(g) +
N/ ((11)l)))
which is confirmed by the following equations:
ElI(( + h)) = (X)(((),, Y) + 0x(( ())()) ( (()(x)))
M(X)= = (X, )) 2) and [I(X)] S || k(X,X) x). This means that the stochastic gradient of L in H is given by (X)) ()k(X.)) for (X, (X.Y) p. In addition, the stochastic gradient of the Lg-regularized risk is given by (gL(g(X), ()(XX + >g.
A. REFERENCE AVERAGED STOCHASTIC GRADIENT DESCENT
We consider random feature approximation of NTK hioo: for an initial value B(O) Vx, Ve' E xx
(0) ) )r=l
M
To ae + +22 ob (B) (b x'), (5)
M
Ras (as x²) def
M ())(//) x')
Σ
M
We can confirm that kMs is an approximation of NTK, that is, kM converges k uniformly over supp(px) X supp(px) almost surely by the uniform law of large numbers. We denote by (Har: ()) an RKHS associated with kM- By the assumptions, we see kM (x, 12 for
v(I,,') E supp(px) x supp(px).
We introduce averaged stochastic gradient descent in Has (see Algorithm 2 as reference for Algorithm The notation (t) represents a stochastic gradient at the t-th iterate:
((t) del (x))) (e)kM(
Algorithm 2 Reference ASGD HM
1: Input: number of iterations T, regularization parameter X, learning rates (11 Y=)) averaging weights (a:)T=--
2: ()) 00
3: for ( 0 to T
4: Randomly draw sample (Ii, V1)
5: ((t+1) (1 (f) 17, (t)
6: end for
7: Return ( (=) Σ. (t
The following proposition shows the equivalence between the averaged stochastic gradient descent for two-layer neural networks and that in H. up to a small constant depending on M.
Proposition A. Suppose Assumptions (A1) and (A2) hold. Run Aggorithmssaad2 learning rate т satisfying ye < 1 and r S 1. Moreover, assume that they share the same hyper-parameter settings and the same examples (æt, vo)T- to compute stochastic gradient. Then, for arbitrary T E4 and O, there exists M E E4 depending only on T and such that Vt S T,
the constant
19
(1) (1Lx((ex S..
(6)
where gugtes and (t) are iterates obtained by Algorithm 7 and respectively.
14

---

Published as a conference paper at ICLR 2021
Remark. Note that this proposition holds for non-averaged SGD too because it is special case of averaged SGD by setting only one a to 1.
Key idea. This proposition is the key because it connects two learning dynamics for neural networks and RKHS HM by utilizing overparameterization without the positivity of NTK unlike existing studies (Weinan et al., 2019 Arora al. 2019b) that provide such a connection for continuous gradient flow with the positive NTK. Instead of the positivity of NTK, Proposition [ says that overparameterization increases the time stayed in the NTK regime where the learning dynamics for neural networks can be characterized by the NTK. As result, because M is free from the other hyper--arameters, the averaged stochastic gradient descent for the overparameterrzeed two-layer neural networks can fully inherit preferable properties from learning dynamics in HM with appropriate choice of learning rates and regularization parameters as long as the network width is sufficiently large depending only on the number of iterations and the required accuracy.
A. CONVERGENCE RATE OF THE REFERENCE ASGD
We give the convergence analysis of Algorithm 2 in Hys which will be a part of bound in Theorem 1 Proofs essentially rely on several techniques developed in serial studies (Bach Moulines 2013
Dieuleveut & Bach 2016 Dieuleveut et al. [201]] Pillaudd Vivien et al., 201 Sa Rudi & Rosasco
2017 Carratino al., 2018) with several adaptations to our settings.
def kw (X,-) and denote by Ex the
Let M E - U {oo} be positive number oc. We set KM,x covariance operator defined by kas
EM def Ex-px [KM,x WH KM,,)..
We denote by JM, the minimizer of the regularized risk over Has:
def arg min 9EHM
X { [(g)+
+ 1191 HM
9M.A
2
We remark that EM [2(xx) - Hm is isometric (Cucker & Smale 2002), that is, v(f.g) [2(xx) x L2(xx),
1/2 .13 9) Has (2 f.
and we use this fact frequently. It known that JM.A is represented as follows (Caponnetto & De Vito 2007):
gM. (EM + XI) - Ex,, (YX,))
=EE + A
The following theorem provides convergence rate of Algorithm tto the minimizer 9M,A-
Theorem A. Suppose Assumptions (A1), (A2) and (A3) hold. Run Algorithm 2 with the constant learning rate T) 17 satisfying 4 A)m 1. Then, fhr VA > 0 and V8 (0, there exists Mo such that for vM 2 Mo the following holds with high probability at least 1 8:
4
E 5 T
9M.A L2(ex)
-
17 + 1)22
11 + 11) 9MM.xllA(ex)
242
+ T +
|1(EMr + AT) 1/2 9M..MMlll 1/2gMM.llE.
8
+ T ++1 1
(1+1oell2atoxx) + 24 gp sall)) Tr (EM + +T)-
where (T is an iterate obtained by Algorithm 2
Remark. The first and second terms stem from the optimization speed of a semi-stochastic part of averaged stochastic gradient descent. The first term has better dependency on T, but it has a worse dependency on À than the second one. This kind of deterioration due to the weak strong convexity is common in first-order optimization methods. However, as confirmed later, these two
15

---

Published as a conference paper at ICLR 2021
terms are dominated by the variance term corresponding the third term by setting aper--prameters appropriately.
To make the bound in Theorem free from the size of M, introduce the following proposition. Proposition B. Suppose 9p E Ho holds. Under Assumption (A1) and (A2), for any E (0, 1), there exists Mo E Ra., such that for any M 2 Mo. the following holds with high probability at least 1 6:
|[EM + A1) 9M..llizzoxx ((xx)) S 2A 211-'190p
ll(EM + aM)-1/2gM.AAlie I 211
and if X 1 Expllop then
Tr (EM( + 11) S 3Tr (2xo + 1)
Remark. The last inequality on the degree of freedom was shown in Rudi & Rosasco (2017)
To show the convergence to Ip. we utilize the following decomposition:
( gpxl $ (l gMr (MAllLz((x)) IIgar, Ix0, 0xx,Allix(xx) + 119,0,0 9 9oll22(px);
where IoodA def
arg mingeH. (C(g) + + 11lll
The first term is the optimization speed evaluated in Theorem and the second and third terms are approximation errors from a random feature approximation of NTK and imposing Lzzregularization respectively. These approximation terms can be evaluated by the following existing results. The next proposition is simplified version of Lemma 8 in Carratino et al. (2018)
Proposition C (Carratino et al. (2018)). Under Assumption (A1), (A2), and (A3). any c, and 8 (0, 1), there exists Mo E depending on e, X, 8 such that for any M 2 Mo, the following holds with high probability at least 1 ò::
11 9 (01,212 S..
Proposition
Caponnettto & De Vito 2007 ). Under Assumption (A3), it follows that
19
9pll2 S 2r E p5rgppll Lx(xx)-
establish the convergence rate of reference ASGD to reach 9r- which is simply the generalization error bound.
By combining Theorem A Proposition B C and D with the decomposition 8
Theorem B. Assume the same conditions as in Theorem A Then, for Ve > O, || 2 AX >
and v5 E (0, 1), there exists Mo E Z- such that for vM 2 Mo. the following holds with high probability at least - 8 over the random choice of random features (())
E ( 9o ((x)) S
3x
12
9o gplli.
24
+ T +
288
\T + +1)
11gm112....
24
(1+ 11111111 (xxpl)) 24 9p 11 (alox)) TI (Eoc (Eoo +
T+1
where g(T) is an iterate obtained by Algorithum
A. CONVERGENCE RATES OF ASGD FOR NEURAL NETWORKS
As explained earlier, the generalization bound for the reference ASGD is inherited by that for two- layer neural networks through Proposition A with the following decomposition: for iterate Gy: obtained by Algorithm !
( - 90 solleslox) S I1 (()) [xs((x) + ( gpllez(ex)
16

---

Published as a conference paper at ICLR 2021
That is, these two terms are bounded by Proposition and Theorem B under Assumption (A1)-(A3),
resulting in Theorem [ which exhibits comparable generalization error to Theorem as long as the network width M is sufficiently large.
Theorem
limeedittely leads to the fast convergence rate in Corollary | by setting 1) = 1j = ((1)
satisfying 4 + A)n S and À = T-2/((2-3+1) 1) with the bounds on 1 12 [l ) and the degree of freedom. Because B in Assumption (A4) controls the complexity of the hypothesis space
Hos derives a bound on the degree of freedom, as shown in Caponnetto & De Vito (2007):
Tr (Eoc (E + +) 0(A-1/9)
In addition, the boundedness of | llop - (1) gives
| - ||0000 "x goll<iop)) (1
11gpll I | E gpllaz(ox) S {0 (plloa(ox))
This finishes the proof of Corollary 1
B PROOF OF PROPOSITION A
We first show the Proposition A that says the equivalence between averaged stochastic gradient descent for two-layer neural networks and that in an RKHS associated with kas.
Proof. Proof of Proposition A
Bound the growth of Iseco (xxx) We first show that there exist increasing functions d(t) and (1) depending only on & uniformly over the choice of the history of examples (I,, yt) used in Algorithms such that Ilgew [1 (ex) d(t) for Vs I when M 2 Mt). We show this statement
by the induction.
Without loss of generality, we assume that there is no bias term, ||b, 1|2 = 1, and supp(px) C {a e Rd+1 ||æ||| S 2) by setting x < 71) (where 7 E (0. 1)). Hence, we consider the update only for parameters a and B. The above statement clearly holds for /. = O. Thus, we assume it holds for I. We recall the specific update rules of the stochastic gradient descent:
(+11) -a aa (1 (a) a.0))
"
(g (xx) ye (:) xx),
(9)
VM
((+1 b(o) =(1 ()) ((0))
(Jere (1x))
(10)
VM
Here, let us consider VM 2 M(). Set d:d (1) = max 11, ||2. Then, by expanding equation 9 we get
la (1+1) - a < la!) a 1 + 7.
(d(t) + 1) 2d (t))
VM
(d(s) + 1)(1 + 2dh (t))
VM ==0
( + 1)
(d(t) + 1)(1 + 24 (1)),
(11)
VM
where we used [w)] S + and lyal S 1. As for the term |a! (s S + 1), from the similar
augment for and the monotonicity, we have for st+1, 1,
|a,51| < 1 + la.5) o.0)
1 + ntt 1)
(d(() + 1))(1 + 24 (1)
VM
ntt 1)(d(t) 1)(1 (())
(t)).
17

---

Published as a conference paper at ICLR 2021
We next give bound on [|b,++1) -b,0)
2|.. By expanding equation (00
we get
4n
[|6,-11
11
(6(00
6,00
1
a (d(t) + 1)
VM
4n
(d((s) + 11
M
4n(t + 1)
(d(t) +1) (1+ nit n((+ + 1)
(d(t) + 1)(1 2d. (())
(12)
VM
VM
where we used |oo' s 2 and |2eel22 5 2. Here, we evaluate df (t). From the similar augment for S t, the monotonicity, and [16." 112 S 1+ + [16,") -1. we get
4n(t v[(++1] (d(t) + 1) (1+
nit nt + 1) (d(t) + 1)(1 + 2d, 24((())) (8))
(t)++
VM
VM
Let (t + 1) be a positive integer depending t and d(t) such that +1 (d(t) + 1) S 1.- Let us
reconsider VM 2 M'(t + 1). Then, since 17 S 1, we have
dg (t) = 2
|a S (Vs st+
From the derivation of 11 and 12 and since
S 1, we have for 0 448 S 1 1,
(0) di dt + 1)
l16/0) 1 S d2(t +1
|0
(13)
VM
VM
where di (t + 1) and d2(t + 1) are set to
di(t + 1) del 6(t + 1)(d(t) + 1), dz 1) del 10(t + 1)(d(t) + 1).
We next bound [gen+ (x) for x E Vsupp(ex) as follows. Since Jo = 0, [g (x) = [9e (x) - gero: (x)
M
(1at (++1) (0)
(6((0)) + ((+t)) (o((tt)) x)) =0, x)}
M
M
(++1) a,00 +4 a 1 ( 6,00
2 ar
V M
< 2dg (t + 1) - 1tdg(t+) + 1).
In summary, by setting (t + 1) = max (t), 16(t 1)²(((())) 1)2} and d(t 2t 1) + 10dz(t + 1), we get [| (1 S d(t + 1) when M > + 1). We note that from
the above construction, d((), di (4), d2( depend only on l and inequalities (1) are always hold for VI 24 when M 2 M(L + 1).
Linear approximation of the model. For given T' E E4, we consider VM 2 (T) and define the neighborhood of (0) (a. (0) (10))
)M
()) def b.)) M E (R x Rd+1IM |a,| < 5
5
aa - a00 <
di
||, - 8,00 10,-6,011 - dz(1)
VM
VM
From Taylor's formula lo(b, x) - o (bb))) ()) 2) d' d' (O)T x),
6 ) x| < 2 2| 100 16, 6/50 1/
[0)T
and the smoothness of a, we get for O E (0 and x E supp (px),
(b, xx) - (a (b x) (ar - a 00) )o (b(0)) 2) a ()) d'1 (T))) z), b(00) x))
< 4/a, - a0 I||,, 110122 + 2C|a,111,, 60013
2d (T))2 SCd((T)
(14)
M M
18

---

Published as a conference paper at ICLR 2021
We here define a linear model:
M
he (x)
def
Σ
(ar,
x) + a (1 xx)(b, - Tz)
VM ==1
By taking the sum of 14h over E {l,...,Mp, M and by gero) = 0,
M
2d1 (T)d2( 5CdB(T)
[ge(x) - he(x)) S
VM
M
M
s VM
(2d) (T) + (T)
We denote dz(") del 2d, (T) + (T). Since iterates (o obtained by Algorithm
!
are contained in By (+(()),, weighted averages (6 yTo are also contained in Br(O())). Thus, we get for v4 (1..... T),
dT( VM
dz(T)) VM
I9ace (x) hate (2) $
(x) hggh(())
(15)
Recursion of ha@ using the random feature approximation of NTK. sion of ha using kMs From the updates and IOP, we have
We here derive recur-
M
ho (x) =
1
(aft
a (0) (b 2) + a o' (b(0) T)) ((0))T²)
VM
M
(1 mA)hom (x)
> M
(gern - 100066600)00066000171
M Σ 6 d'(bi)) x) (x))) 21)x, x.
(16)
Note that fort E 10, (O.....T). T),
(gew (are) - (1)0o((( xx)) (her (1x) - (1) x.)]
- (9gen) (xx) )- haw (Iz)) 21)1 + ((gen (o xx) =6610)22))
- 2dg (T)
+ 4(d((T) + 1))(((() - 6.00
VM
2
<
(dg(T) + 2(d(1)++++)))))))))))))))))))))) + (T)2
M
and
(x) - (2x)
o'( (b(oT xx) - (hero v.)a v,) ('(()) xx)]
1(gern (2,) h (x, (") (bb()) x1)1 (g (2,)
xx) o TT,)))
2d (T) + (d((T 1) (6(0) x2) (b(()) xx))
VM
2dx(T) + (d(T) + 1) { (0((1(() xx) o (b )) + (a a('''''(((') x.)1
VM
(T)
+ 2(d(T) 1) (C11000) - ((0) 122 + +laS) - -000 {1}
VM
(T) 2(d(T) +1) (di + Cd2(T))
VM
VM
2
(da(T) (d(T) + ()) + Cdz(T))
VM
19

---

Published as a conference paper at ICLR 2021
Plugging these two inequalities into (16). we have Vt T- 1}.
hou 12) (x) (1 77) (x)
M- hew (x4) (00 (0) (0
(1)
" Σ o (((b (h)rg (24) (1)) v1)00(1, Nt xx)xx
2n (2dz(T) (d(T) 1) + (C 2Td)(T)))
VM
(1 (x) ( y/ M (1(1 te)orbby) o'(bpo=2)) x) (o'(U,TTx))) x))
+ 2n
+ (d))) (C + 2)d2(T)))
VM
" d4(
= (1 (c) (t) +
VM
where d4(T) = + 2)d2 Clearly, the inverse inequality also
holds:
hgret1> (x) 2 (1 (1 (x) (her (xx) ye (M,
7 dT))).
VM
Thus, we get
hhget)(a) - (1-n)))/gcoo n(how (xx) (2,,
_d)())
(17)
VM
andd We provide a bound between recursions of Algorithm 2 and Noting that ha( = -0 O, we have for vt {o..... T
Equivalence between Algorithm I
1},
[hareen (tt1)) (x)) & (1 - ma (x) (x)) + my (xx) - gd (x)) (2, + (T))..
7
VM
Noting || [1 S 12 and taking a supremum over x, 24 supp(px) in both sides, we have
[ - (t+ (xx
([ S (1 - +)))llbar) - gd [[ + allhorn - e
+
7 (T)
VM
< (1 yn 12n)llhero - (( + (T)
VM
+ 12m) 1- " (T)
VM
T
<
(1+ + 12m) dd,
VM
Since he is a linear model, we have hgm = ET atho and
T
(ighT - (TTT)
((xx) callhogo - 900
(1 dd
VM
Combining this inequality with 15 we finally have
1lgm. -T( (1 (xx) Il -hgo + I1 (igmr ((T))1))()
1
(da(T) + 13
Because (dy(T) TddTd,(T) depends only T and C from the construction, l|gam (() (xx(px) + a as M so. This finishes the proof of Proposition A
20

---

Published as a conference paper at ICLR 2021
C PROOF OF THEOREM A
In this section, we give the proof of the convergence theory for the reference ASGD (Algorithm We introduce auxiliary result for proving Theorem A
Lemma A. Suppose Assumption (A1), (A2), and (A3) hold. Set & def YKMX MMM.X &H M. x + > Then, for vX VX and vō (0, there exists Mo such that for VM 2 Mo
the following holds with high probability at least 1 6:
Ex SHy 5 5 2(1 + 119 (la 2 sollstex)))
Proof. Since & = (Y 9M (M) M.X - AgM,A we get
El[ 8HM 4 = =B[(Y -
KM, 8HH Kaxx ABE(Y IMA (X)) BHH IMA
AgMA BHH BI(Y - KMM(
+ A9MM. EyH 9M.A
We evaluate expectation in the second and third terms in the right hand side of the above equation as follows:
Ei(Y (M) K
E[YKM,X (KM, OHM KM,x)9M.N.
EEYKKM KM,X
EM9MA B[Y K MM EM(EM + BY
EEYKK,, (EM + + -D) BY
-AEE + AN)-'B[YKM..
AgMsA.
Hence, we get
BiE ONM E & E((Y - (X)) (X)X) Orss KM.x].
For E HMs
(BI(Y- (X)) KM, 8HH K KM,xhh, h) HM
-E[[YY -MMA(X)) ((KMi BHa KMxx) 11) peal
||Y 9M)((X)l (ox) BR(KKMX OHs KM,x ), 11) Hadd
S 2(1 + 119., (ex) (e))) EEK(M, BMs KM,x)h h) moch
(18)
where we used Assumption (A2) for the last inequality.
Finally, provide upper-bound on ||gM, l (ox)- Since S - T --1==-- -S- for arbitrary operators S and T, we get
|| ((Ex \T) (EM AT) gellealoxx
15 AT)-1(EE.s Ear)(E + AT)-'/ppllzz0e
= 11 + >T) "0-11lop11Sos EmIlopp((SD) + 2T) "loplllllg (loppllpll<xx(x))
< [ox EMx l'rlloplloppl <z(
(19)
We denote Ps: = (E.o + >1) go and F'r = (EM + A Noting goo.A = Foc and IM.A = Exs FM, we get for Vor E supp(px),
( - (M))(())= = (xoFFo(()) (M)FN(())
/ (X)P - 1 (M.o())PM(()ddx
[ (Koo, - (X) - KMM - Foo Foo (x))
x Kooor KM (x Foollssoxx + || Fas Foeliza(ox)
12
koo (
+ x2
Dox -E- E'Mllollsollleseoo
21

---

Published as a conference paper at ICLR 2021
where we used kyr(2, (2, x²) 12 for v(z,x') supp(px) supp(px) and inequality 19 Moreover, we get
[z)) Woo.d Ka)Ha
$ K Hwx 11 100 11
2/3 Do EE X1) 1100gppplle 2
S 2v3
E (Exe + +11 - -2000 gol H:.
S 22 E
(Ex + \1) gp 10plggpllass (((l))((x))
< 23 E&e 50 + A1) 'lopp Ex 9epllllla ((2(x)
2233 g
(20)
where we used Assumption (A3) and the isometric map En! L2(px) + Hoo Hence, we get
[lMm, I GlIRso-Ravllnn kxrlles
12 X Ex Em |lap [19ell2(ex)) 2 2/ Ip 9pllex(ex)-
By the uniform law of large numbers (Theorem 3.1 in Mohri et al. (2012) and the Bernstein's inequality (Proposition 3 in Rudi & Rosasco (217)) to random operators, Mix kaslle= (px x and || - lop converge to zero as . + 0C in probability. That is, for given À > and 5 E (0, 1), there exists My such that for any M > My the following holds with high probability at
least 1 8:
IgM.alle (ex) S ?1lopllestex) + (/311=59pllllteee
Combining with (18), we get
(B[(YY (M)) KM,) SHHr K KM.x X,,)],, Has $ 21 + 11ppliisexx + 24| go (xll2 )B( OHar KM,xx th, 1) Hacl
Proof of Theorem
Since, stochastic gradient in Har is described as
( = 0. (w)) ((KK))-(((K))))))
uas 11 K KM
the update rule of Algorithm 2
(1+1) (1 ())) ((KMA))))))) uM -Br) KM.
wi)
= (I - M., OHH Kas,an - 11A1) 10) + MyN.M...
Hence, we get
(1+1) 9M,A (1 M.KM &H KM... ndl) (t) 9M.N)
=0.
=
-MKMa. OHa KM.z. + Al)MMA + MyLKM...
(21)
=8.
This leads to the following stochastic recursion: E -O.
t Σ
A41 a +
II Ag
II a.B,.
0=0/=st1
22

---

Published as a conference paper at ICLR 2021
By taking the average, we get
Ar 1
A
T+1
T
1 EE ag3 t= 8=0 I=s+1
EII Ao +
(22)
T+1
T+1
Noise torm
Thus, the average Ar is composed of bias and noise terms. We next bound these two terms, separately,
Bound the bias term. Note that the bias term exactly corresponds to the recursion 21 with 3t O. Hence, we consider the case of 3r = 0 and consider the following stochastic recursion in
HMr Ao = -MM
A41 (I nH, m
K M, In addition, we consider the deterministic recursion of where we define H, M, OHy this recursion: Al = Ao.
A/41 = (I T/ nAT))
We set
1
Ar
Ar
A'T T+1 Σ A/
T+1 1=0
Then, the bias term we want to evaluate decomposed as follows: by Minkowski's inequality,
E| (T1
$11A'illaaox) + (BllAA A'r 11xx(x)))))
(23)
We here bound the first term in the right hand side of 23 Note that from 4(6 + a)n < and | (px)) S 12, we see (Ex & 7112+A)
Since A (I Ln ndI) gM.A.
its average is
A'T T+1
A/ (T 1)
EEr + -I -1 (A)T+1)gMM.
t=0
Therefore.
| |A'T|lLs(px)
1 + A1) (1- (1 1/E 19) )gM.Allas(xx)
1(T 1)
5 (T +1)
|1Ess + "M..Alllaa))
(24)
We bound the second term in 23 which measures the gap between Ar and A'.. To do so, we consider the following recursion:
A411
A/+1 A. N 1--n(H+++ + AA) n H.)
Hence, we have
|A41 1/t1
1|A, ALl
17 -A, Ai, (H, + XI) -1) (EM HH)
11 ((H, AD)(AA - A1) - -(EM H.)A', A. - AlH
+ + + AL)(A, AD - -EEM A1
In general, for operator F; L2(px) + L2(xx) that commutes with D' and has a common eigen- bases with EM.. it follows that F(HM) Har and inequality F > 0 in (2(xx) is equivalent with F. | O. Hence, we do not specify Hilhert space consider in such case for the simplicity.
23

---

Published as a conference paper at ICLR 2021
Let (Fi) be filtration. We take conditional expectation given Fi:
B[IIA41 A4+1llia 1l
1 < A| - A'll PM. 2n (EEM + \T) - Ab),, A. A2)
+ B He + X1)(A, -40 2a [F]
(25)
+ 2nj BII(EM - H;) Fel;
(26)
where we used lg hillee. For E Had we have
s 2(1lg11/A [1bl1/4x))-
aM &ra KM,,))99 ( Har
< (KM.s Oyy K KM )a.)))9. (9.9) Har
(KM.z D (KM.r Bye KM Kas 9)
Has
( D. kad (2e, 2z) K KMac Har
(K 9) Hm
x0)
S 12E (Kas 9) nM
= 12 (E [K, SHM KM,x.9992 g.
(27)
where we used has (I+e r.,) < 12 which is confirmed from the definition of kas and Assumption (A2).
This means that [R| H??] E[(K M. SHar
K M,,,)² )2] & 12 on HM x HM- Hence, we get
bound on (25) as follows:
ElI[(H, + (A: ADl
[F] = (A A,), A1) HM Fi]
HM
= ((AFI+2XE)) 22EM + B[(KM 0HH KM,;;) )²1) (A, (A,-A)), A. Al) HM
< ((APT+ +))Ea) (A. A,), A, Al) Has
Next, we bound term (6)
E (2 A,) Pe
Fi| E(((MM H,) Al) H,s [F.]
EK( - EMH, - H,EM + H2 ( A1) H HM FF1
= ((E[H)) - -21) Ab) 1m
S (I) HAr
< 12 EENAA Al
Combining these inequalities, we get
B|||A++1 - A1441112asr
Fi] S ||A, Abll 2n ((EM + AT)(A, -A), A. -Ai) Has
+ 2n7 ((X²I + 2(6 + A)Eas)) - A,),, - -A1) Al)m
am
+ 24n² A4,
= -11 - 2\n + A1 - A/1 - 2n (E (Ae - -.), - Al)
+ (6 + 2) (Er(Ac- - Ar, -Ai)
+ 24n (E Ar)
< A - Alll2 11 (EM(AA - Ab), A. A1) HM
+ 24n (L A.)
(28)
where for the last inequality we used 4n(6 + A) S 1.
By taking the expectation and the average of (28) over t E .o..... T - 1}, we get
1 T
24n
T
Σ T=
(A - A.), AlMn T
Ess Ale Ald "0
T
1=U
24

---

Published as a conference paper at ICLR 2021
Since EM/ (2(xx) + Has is isometric, see
| (A+ A)) 11A Aillealox)> Thus,
the second term in 23 can be bounded as follows:
A A' (alex)
B||EM (Ar
1/2
A'r 1l
T
[BI E
1// (Ae
A:)1 M
T+1 t=
24n
T
|EM A,l HM
T +
1
24n
L (I 7 m/T)) 9M.
T+1
241
Σ (I M/E m/21) IM.A: E1/2 9M.2
T + 1
Har
24
(NMM + 11) '122/2 gM.Ai 2MM gM.A)
T + 1
Has
24
T + [Ie + AT) A7)-1/2
112 gM.lliiz
(29)
where we used the convexity for the first inequality and we used the following inequality for the last inequality: since | (px)) 12 and 1)(MM + AI) x n12 X) 41.
T
Σ
(I - M - 7 $ (Em + A
By plugging (24) and 29 into 23 we get the bound the bias term:
B| Ar 112
s A 1 ((x(ex)
+ 2E[||r A'r 1111)o1
(ex))
2
24
(T + 1)2 llEM 9M)
T + 11EEs + A1)-1/2
.MM.Al (1
(30)
Bound the noise term. Note that the noise term in (22 exactly corresponds to the recussion 21
with Ag = 0. Hence, is enough to consider the case of Ao evaluate the noise term. this case, the average Ar can be rewritten as follows:
A
II
an
II
II
ai 3
T+1
T+1
1=0 ==0
Imstl
==0
Z.
We here evaluate the noise term. We set 2, (Ies Us). Note that since Ez, [.o]]
O, we have for
8 < s',
E ((
(Z.. Zz) (
1x B(zon..Ze))
[II at
T
3n
()
[
T
II
at
Bdr
]
dox
1=s
t=ss I=s'+1 "
Ez, B
Ba
dpx
t=s "
Ims' 1=6'+1
0.
25

---

Published as a conference paper at ICLR 2021
Therefore, have
1)2
E Al [xx(xx) )1
E8
Σ Z
(T' + +)2
(2(px)
1/²
(I 1)² E
(Zer Zo) Le(px)
8,0'=0
172
E
(Zer Zeo Lx(ox)
(T' + 1)²
172
T
1/2
Ze 1l
(31)
(T' + 1)
8=0
Here, we apply Lemma 21 in Pillaud- Vivien et al. (201 8a) with A Em H = EM + XI, C 2(1 + 19 La(ex)
+ 24 gplli Lx(xx)))) M One of required conditions in this lemma is verified by
Lemma A
We verify the other required condition described below:
E [[,M,x 8H KM. + (KM. 8H KM, + XD] x c.
(32)
Indeed, we have
E [KM, ON KM,X + AT)CH (KM, OH KM, + AT)]
E [M.X SH KM KM.X SH KM.X 2HE X2HH-
& E KM,X OH KM,XCH- 8H KM,x] 6A(1 + l19pllizz(ex) + 24 9p gp (
where we used (M + A1) & I and A(EM + A1) * L. Moreover, we see
[KM,X Ey KM,CCH M, 87 KM.x]
=2(1 + 11pp1l2 + 24 Σx 9o 112 (px) E [MM @H EM
EM + - 8n KM,x]
< 2(1 + 119, 11a.112z + 24| 24 9p ( IE [KKM, &H x=
< 24111 + || L2(px) + 24 1pl (2))(())) E.M
where we used
(27) for the last inequality. Hence, we get
E [KM, 0H KM.x + AT)C (K On KM,X + XT) (24 6A)(1 + ( + 24 (pll22((x)) )
Since, 4n(6 + A) < 1, the condition (32 is verified. We apply Lemma 21 in Pillaud- Vivien et al.
80 31.. yielding the following inequality:
E||| E1 - T (1+ (1p1122(oxx) + +24
211 Tr (E (EM + A1) -2
< T (1+ 11pll + 24 24 Tr (EM (EM + xI) -1) (33)
Convergence rate in terms of the optimization. Finally, by combining 30 and (33 with (22) we get the convergence rate of averaged stochastic gradient descent to 9M.x:
4
(T) 9MM. Lx(ex)
<
|1(EAs + --) "9M.)lli2(ox)
(T + 1)2
2. 242
+
[1(EM + (T) 1122
T +
8
(1 + 11 ( + 24 24 sollzatox)) Tr (EM(EM + x))-
+ T + 1
where (T) def
T=I Ei=0g (9) This finishes the proof.
26

---

Published as a conference paper at ICLR 2021
D PROOF OF PROPOSITION B
We provide Proposition which provides the bound on Theorem
A
Proof of Proposition B From the Bernstein's inequality (Proposition 3 in Rudi & Rosasco (2017)
to random operators, the covariance operator Σm converges to Eoo as M - oo in probability.
Especially; there exits Mo E Z44 such that for any M 2 Mo, it follows that with high probability
least 6, Exx ΣM < 2 (E + AT) in (2(xx) Thus, for vf E (2(xx), we see
(Exo A1) A1) 1/2 EM + A1)-1/2f,5 L2(ex)
= <EEs - EM + AT) 1/2 (Ex + +11) x11-1123) La(ex)
1 (Eio + 11) + 1/2 (Exx + +11-11/1) 12(px)
2
2 [1
Hence, we have
[Ex + A1) 1 (/ EM + A1) 112 $ 2
LT.
Following the argument in Bach 2017b), have for Vf E L2(px),
((EM + {1) L2(ex)
((E00 AT Eas Fxxx)- lz(ex)
((I+ (Exo + A1)- - Exx) + +11- (Exo + A1)-1/// (E + +1)-1122)
Lx(ex)
2 (EEco + -/2)-1/3,, (Ex + 111)-1131) Le(ex)
= 2 + + (
ta(ox)
Thus, we confirm that with high probability least 1- 8, (EM + AT) & 2(E + AT)-
(34)
Utilizing this inequality, we show the first and second inequalities in Proposition as follows. is sufficient prove the second inequality because of
[IEM + AT) A 9M.all2 I X |1EEM + +TT 1/2
Noting that 9p E Hox and DM. = (EM + A1)- Mp we get
[[[ AT) 1/2 - 1112
11EM \π) 11/11/EEEM + - -M09
11Er \1)-1/2
go --1/2//0llxxxxx)
S 2xx + AT) 112 gp 12z(px)
< 2|| 1/2 1/2
21|gp11 1
The third inequality on the degree of freedom is result obtained by Rudi & Rosasco (2017).
E EIGENVALUE ANALYSIS OF NEURAL TANGENT KERNEL
E. REVIEW OF SPHERICAL HARMONICS
We briefly review the spherical harmonics which is useful in analyzing the eigenvalues of dot-product kernels. For references, see Atkinson Han (2012): Bach (2017)); Bietti Mairal (2019): Cao et al.) (2019).
27

---

Published as a conference paper at ICLR 2021
Here, denote by 7d-1 is the uniform distribution the sphere S R.. The surface area of where is the Gamma function. L2( 1), there is an orthonomal basis consisting of a constant 1 and the spherical harmonics YE)( & E 221, = ,,...,,, (dd, k), where [d,, k) = 2k-d-2 h: + 3 That is, (Yki, Yej) Ia( = du. and (Yks, 1) La(ra-1) = 0. 2
gd-1 is w = 2-4/2
T[d/2]
The spherical harmonics Yuy are homogeneous functions of degree k; and clearly Ykj have the same parity as k.
Legendre polynomial (t) of degree and dimension (a.k.a. Gegenbauer polynomial) is defined as (Rodrigues' formula):
T( ( + 2-1) (1
(d) dt (a) (1 12)tt(d-3)/2
Pa(() = (-1/2)
83/3-10/22
Legendre polynomials have the same parity k. This polynomial is very useful in describing several formulas regarding the spherical harmonics.
Addition formula.
We have the following addition formula:
((d.))
Σ =(d))))(()==((()]])) =
Vy
(35)
Hence, we see that (2 is spherical harmonics of degree k. Using the addition formula and the orthogonality of spherical harmonics, we have
8jh N(d, k)
Pa(xTT)
(36)
Combining the following equation: for x ted + v1 tt'' (xr sd-1 , E -g-2,tt [-,,
Wi- (x))= = (1 - - ()) dtdrt/dddrdd
Wd-2
we see the orthogonality of Legendre polynomials in T2([-1, 111 (2)dd3))2d)) and since
Ps (1) we see
[ - (2) W (d.
Wd-1 1
Recurrence relation.
We have the following relation:
+ d d- tPa(t) + 2 Pt)
k
2k + d Pt))(t),
(37)
for & 2 1, and for 1: = 0 we have (Pt(t)= = Pt))).
Funk-Hecke formula. The following formula is useful in computing Fourier coefficients with respect to spherical harmonics via Legendre polynomials. For any linear combination Y, of Ykj. (j E (1, (1,..., Ndd, k)}) and any f (2[[-1 1), (1 (2)d-33//2d)) we have for Va.
JS f(x gTTT)) ()) wd-2Yu(x)) S -P)
(38)
wa-1
This formula say that spherical harmonics eigenfunctions of the integral operator defined by f( y) and each eigen-space is spanned by spherical harmonics of the same degree. Moreover, also provides a way of computing corresponding eigenvalues.
28

---

Published as a conference paper at ICLR 2021
E. 2 EIGENVALUES OF DOT-PRODUCT KERNELS
Let d4n be the uniform distribution on Sd-1 Note that although TX-1 and pe are the same distribution, we use distributions Td-1 and 140 depending on random variables. First, consider any activation function ø : IR + IR and a kernel function k(z,x') = Eo (o((()) x))(b(0)) x')l on the sphere gd-1 We show this kernel function is a type of dot- dot-product kemnels that is, there k(z z²). In fact, it can be confirmed as follows. For any I, E 1d-1, we take E [0, π. so that x Tx' cos 8, and an orthogonal matrix E Rdxd so that Ax (1,0,... ...,, 0)T and Az' = (cos 0, sin 0, ..., because A preserves the value of x: x'. Then, since Ho is rotationally invariant we see
is k R + I such that k(ar,²')
x(x,x')
abbO))
Ab) Ax' (r)d))(((())
gd-1
o(b)
(0) (b()
(0) cos(0) + b sin sin()))d
84-1
where 6(0) = (69, 22
( ). In other words, we see l is a function of 0 = arceos (x T x²), and is
dot-product kernel k(x,, x²) hxx Tx'). Hence, can apply Funk-Hecke formula (38) k(,, +).
The derivation of eigenvalues of the integral operator follows a way developed by Bach (2017a);
Bietti & Mairal (2019): Cao et al. (019). In general, g E (2((Ta-)) can be decomposed by spherical harmonics as follows.
00 (d.k)
9 - J ga-1
g(Z))da-
Σ
(g.
Ykj
j=1
((dk)
1=1
N(d,k) / jea_ 9()))(( ()dr))(())))ra-1(())
(39)
where we used addition formula to the last equality.
Here, we apply this decomposition 39 to k(2,,) = Tx Since (zT.)) is linear combination of spherical harmonics of degree ki (see addition formula), we get
k(x,,) - / { k(x T 2)dra-1
/ Sa-1
=
N(d, k.)
h(x T 2)P 2))P((T.)dda--122
.)dra-1(2)
Iga-1
k=1
Σ (dN(d
(40)
where we used Funk- Hecke formula 38 and we set d₁- 2 -
We
wa-1
note that d is eigenvalue with multiplicity N k) of the integral operator defined by
Next, we derive another expression of k. In similar way, we obtain the following equation: Tbb(0)Tx)) - { 3a-1
oZ oZTTz)drr x:))rarr Σ
where A 3ad2 1L (1)))(() (2)(d-3)/2dl By the definition of & and the orthogonality of spherical harmonics, we get
wy
k(x, = E,so
/ -
x)TJ)) (2) / 1
1 Σ (d, k)),,))) [Pa(bIO)) x.) (bOO)T
=/ 3a-1
T(TTz)dras x))dd-11122) /
(2)+ Σ (NN(C 2'), (41)
3d-1
29

---

Published as a conference paper at ICLR 2021
where we used equation (36). By the rotationally invariance, show
JSu R( Z)dra- Js+ olZ olZTx)dra x))dra ( olZ (dd=a)ddr--1(2)
Thus, comparing (40) with 41 we get d -
E. 3 EIGENVALUES OF NEURAL TANGENT KERNELS
Utilizing relation Åe م we derive way of computing eigenvalues of the integral operator defined by the integral operators Ex associated with the activation a. Recall the definition of the neural tangent kernel:
1io (xr, x.) def mHo lo (b ( (bo()) (x (xJx' + 7 (o (b x:)o (b(O) x')]-
neural tangent kernel consists of three kernels:
h1 x.)
Egcor~ mum
((b(TT))(((0)))
Na(xxx²)) Repe0) ('((10))))
x) (b x')]
ha(x,x')= = ( IJ'LEpoo> 2) =)0(((()2'')
By the argument in the previous subsection, h1 and h2 dot dot-product kernel, that is, there exist h and ha such that in (z,,²') hn (x (TTT)) x') and h2(x, x²) ha(x x²). Moreover, ha is dot-product kernel as well because we get h3(x,, explained earlier is applicable to these kernels.
ha(a x') by setting hs(t) thz(t). Hence, theory
Eigenvalues ün for kernels h2 and hy are described follows:
Wa-2
[" (t))))(t)( - 2)
(42)
Wd-1
A4
(2)
Wd-2
(1))))(t((11- - -t)(d-3)/22
(43)
Wd-1
yielding eigenvalues ((1) = 12 and ues x(3) for h3, we have
(2 for hi and 122 respectively. As for eigenval-
33)
Wa-2
[" th2 -t2)(d-33/22)
k
WA-1
k
Wa-2
2k + d - 2 W
k: + - wa-2
["] h=((t) (d-(2-3)/2
2k + - 2 wa-1
k
(2)
+ d - 2 (2) 2k + d - k+11
2k + d 2 k-1
where used the recurrence relation (37 Since, h1, h2, and hy have the same eigenfunctions, eigenvalues No of oo is
doc,R ((1) +221(0
(2)
k
122)
k d - 2 (2)
(44)
2k +
2h + 2 k+1
Hence, calculation of (ioc, 100 results in computing ji()) and j for given activation
30

---

Published as a conference paper at ICLR 2021
Eigenvalues for ReLU and smooth approximations of ReLU. As for ReLU activation, its eigen- values were derived in Bach (017a). Let a be ReLU. Then, p and p. k-d/2 when is odd and Pi (1) k 4/2-11 and A 0 when k is even. Consequently, we see A O(K")).
We note that the multiplicity of S is .N (d, so that we should take into account the multiplicity to derive decay order of eigenvalues Xoo of E Since 1 + Σ}= N(d-1,) N(d, k) (for details
see Atkinson & Han ). we see N(d+1.)) = O(k Moreover, NN + 1, k) = ((x--1)
yields N(d+L.8)
N(d+1,N) (1-)))1--11 1-) As a result, Assumption (A4) is verified with
for ReLU.
For the smooth approximation (+)) of ReLU satisfying Assumption (A1'), we can show that every eigenvalue of Σ derived from (*) converges to that for ReLU as 8 -> oc because of (2) and (43)
with Lebesgue's ' convergence theorem.
F EXPLICIT CONVERGENCE RATES FOR SMOOTH APPROXIMATION OF RELU
For convenience, we here list notations used in this section. In this section, let a and ((*) be ReLU activation and its smooth approximation satisfying (A1"), respectively, and for M E 24 U {xo let
kM. EM, 9M... (()) <>x)) MMA be corresponding kernll, integral operators, and minimizers of the regularized expected risk functions. Let (T() be iterates obtained by the reference ASGD (Algorithm
in the RKHS associated with 1/6)-
We consider the following decomposition:
デ ( - goll2o(ox) S |g
(e) gMr all ((x)(xx)
(45)
(s)
11
(46)
(e)
930,1 (lxx)1(1((x))
(47)
+ 11 9o 10
(48)
These terms can be made arbitrarily small by taking large M and s. As for (48) this property is direct consequence of Proposition D Note that Proposition[[] is not applicable to (46) because this
C
proposition require the specification of the target function by 1<(6) which does not hold in general.
In the following, we treat the remaining terms.
Proposition E. Suppose (A1') and (A2') hold. Then, we have
1. plim M
1k: k!2o Il (px)3 0, limg-soo |1kle] kioo kooll [xx =
2. p Tr (x(()) (s) I 0, limg-toc Tr I Ez0o 0.
3. plim (9g - allxlllsss O, lim (1o - goo. = O.
where plim denotes the convergence in probability.
Proof. We show the first statement. By the uniform law of large numbers (Theorem 3.1 in Mohri ct al. (2012)), we see the convergence in probability:
M
1(0) (xx)) < sup
(s) (1(0)(())))))) ())0)) x') Eg,0) (b00)((()) x0]]
M
M P=1
M Σ (ss) (1,9) x (b(0) x') EB,Or (1000)0) (b:O)) mz)] 20.
+(1 72)
sup
31

---

Published as a conference paper at ICLR 2021
where the limit is taken with respect to M + and the notation 2 denotes the convergence in probability. Next, we have the following convergence:
[
sup E8
Egm
| (b x))00)((0 (b10)) (x) x0)]
+ (1 (1+ 2,0' ES
| (b(o)) (b(o)=x) x))oo))oo))) (b(o)Tz') x') - o' d'(b(o)T ( 2))
(b(0) 2
sup
[ - o(blo) 2) + +4(1 + +2)
sup B 0 (5) (b(0)( x) -))0T))(60001
d(((())z))
I sup
#ESU-
xE
= = (()T)) abboo ex)
اااا) (b a)) d' d((o)) e1) - 0, + 4(11 + + B
where for the first inequality we used the boundedness of a, o', o(5), and (())' on [-1, for the equality we used the rotationally invariance of the measure Moo and the limit is taken with respect to s + co. For the final convergence the above expression we used Assumption (A1') and boundedness with Lebesgue's 's convergence theorem.
In general, for a kernel k and associated integral operator Σ with px, we have Tr (2) x S || A (ox)) and Tr (>(e) Ex S
fg-- k(X, X)dpx- Hence, Tr (
|| 1: ll I. (2 and the second statement holds immediately.
Finally, we show the third statement. In the same manner as the derivation of inequality (9). we get
II(E=// + + - (5()) + \Π) ())~')9,pl) ()pll(x(ex) S |
1
x2
We denote MMM ( + \1) 9r and F(e) (E6e) -1)- Noting IMr.A
(s)
Ex// MM
and
go. -1/e) pla) we get for gd-1
(1)) (1) (z)
| FM (x) FLe (x)
1 Khila (X) (X)dpx /
K(())
00.2 FX')
S (K<l)) M, - k(() co (X) (X)dpx - / Kiollo (X) -X())
S (K K6 llxxllxxxxlol F (1xx(x)) + || ((( ll F1 Fizl)(
x 11:00 1:22) (ex plopp 12 ( >لا' llppllopl)
12
(49)
The both terms in the last expression 49 converge to O in probability because of the first statement of this proposition and the Bernstein's 's inequality (Proposition 3 in Rudi & Rosasco (2017)) to random operators. This finishes the proof of the former of the third statement.
In the same manner, we have
| Ixc.Alles(px)) S 1 Ilkes k66 (xx +
12 x Dox loolllp lex((x))
(50)
The first term in the right hand side converges to because of the first statement of this proposition. We next show the convergence ||
( llop + 0 as
As seen in the previous section,
Ege and Σ(O share the same eigenfunctions and every eigenvalue of E(e) converges to that of Ex
1 and 1 be eigenvalues of x(*) and Eoc. respectively. For an as Let (A jos,
arbitrary > O, we can take i, such that Eis doo,t From the convergence X()) + Aooi and
Tr {
(Eoo) as s + co, we see that for arbitrarily sufficiently large s, [x) -xoosl <
< i.) and Eee, (() 2c. Clearly, for ic, (1()) Aoc,il S Eie,, (1 + \oooe) < 3c.
32

---

Published as a conference paper at ICLR 2021
Therefore, we conclude the uniform convergence sup (e. 1200, Aoooil + 0 as s - co. This
implies ||x
D6e lpp as 00.
So far, we have shown that (46) 447 and (48) can be made arbitrarily small by taking large 8 and M
depending on X. The remaining problem is to show the convergence of 455 To do so, we establish
the counterpart of Theorem by adapting Theorem A and Proposition B to the current setting.
The counterpart of Theorem In Theorem A the condition (A3) is required for NTK associated with the smooth activation g(*) and is not satisfied in general. Note that (A.3) is used for bounding | (xxx) uniformly as seen in the proof of Lemma
Let us consider the decomposition:
119 A (xx)) - (loxoxlleewxxx)
11 soxilllw (px) 119b5)> 900.Allen
(8)
$ 2v 3 9pllaaaa + /19 -el llxxlll 119 (0c,All1:oo(xx)
2 2 (2((x)
Here, for the second inequality we used 20) Note that the inequality 20 holds for Exe because the condition (A3) is supposed for ReLU. For the last inequality we used Proposition E Hence, Theorem can can be applicable and the same convergence in Theorem A holds for g(*), For arbitrarily sufficiently large and M with high probability, we have
E |10TT 9M1. Lo(ex)
1
4
11
IM. AT) + (l22())
(T + 1)2
M
+ 2. 24
T |1(=)0)
+ -11)-1/29//)) (s)
92s.1 112
8
(1+ +111al11zacox) + 24|22 spll II 2MM (2/(0) + 21)-1)
+ T ++1
(51)
Next, we adapt Proposition B to the current setting, By inequality (34). there exists Mo Et such that VM 2 Mo. with high probability,
|< M
+ AT) 1/2 A I 2 + AT)
1/2 2
9p 1
If (E AZ) < 2(E A1) holds, then have the counterpart of the second inequality in Proposition because
S |= 11g.
(52)
where we used the fact that g, is contained in Hos because of (A3'). Note that the first inequality in Proposition B is direct consequence of the second one. We consider eigenvalues ( 1
and {A ) of Σ{ and Ex., respectively. Let i be an index such that for Vi > ix. Aoc,t A
Since, every eigenvalue of [X(e) 100 converges to that of (A ) as s + co, for an arbitrarily
sufficiently large we have [> oo, Aoo,il S
À for Vi < éx, leading to 1/(A (2) - 2/(A Aso.)).
2n2
As for the case i 2 ix. since X 2 X + \oc we have 1/(A + X ( - 1/1 < 3/ + Aoo,;)).
Combining these, we obtain (Σ()) + A7) & 2 AT) and
lim plim || -T)
(s)
IM. l (px) S 4X 1191119
(8)
(53)
80000
lim plim $0000
(E(+ + A/) - 1/2 (s) 1/2 11....ll..a 11 S 411ga 11
JM.
(54)
These are the counterpart of the first and second inequalities in Proposition B
Next, we consider the bound on the degree of freedom in this proposition. Assume X S 1 1 llop-
As seen earlier, an operator (()) converge to Eng in terms of the operator norm. Hence, 5 |5(2 ||op
33

---

Published as a conference paper at ICLR 2021
for arbitrarily sufficiently large and the bound the degree of freedom in Proposition B applicable. We get
Tr E (E + + - 3Tr (2 + +11--1)
(55)
Let us consider upper bounding the right hand side:
20.5
Tr [6 (x + 11) 1
20011
X
+
oo.1
(4)
1
(s)
xc,1
+ b0,1
(8)
1 4-1
(6)
1 Tr (51(2)
+ )
(a)
00,1
On the other hand, by the definition of ix,
Aboii
Aooii
2Tr (Eoo EEx + +11)-1)= =2
+2
X Xoo,i
A Aoait
i=
81
Axait
2
+
Asoyi
A Xoo,t
X
immx
Aooii
i-1
1
2
Azati +
Tr (Eoo)
x Aoo,i
i=1
i=1
1
A
Aoo + x Ir (2oo).
Aooit
1=1
1=1
Therefore, by inequality (55
). the convergence of A + Aoo,t for E fI,..., - 1] as 8 - oo,
and the second statement in Proposition E. we have
plim,
lim Tr (+))
(E()) xn)-t) - 9Tr (Exo(Eno + A1)-1).
(56)
M
Combining 45
448 with 51
53 54h, and (6). we establish the counterpart of Theorem
B For
given e, and 6, there exist sufficintlyy large and M such that with high probability 1 8.
E (0m0) - Lz(px) S set a
90 T+I (1+
11p0112e..
Anp(TT + 1)
a T+1
(1+ 11 + || (x=0op1l(x(xx) Tr (Eo + -11--1)
(57)
where a >> 0 is universal constant.
Proof of Corollary
Since conditions (A1') and (A2') are special cases of (A1) and (A2), we can
apply Proposition A to Algorithm for the neural network with the smooth approximation (()) of
ReLU. Hence, by setting ") 1) O(1) satisfying 4(6 + Ain and À T-8/(2r3+) where
and - and by applying Tr (Eoe (E.g0 - O(A 1/9)
Capoonetto & De Vito 2007
< O (1 because of |E llop S O(), finish the proof of Corollary 2
34

---

Published as a conference paper at ICLR 2021
G APPLICATION TO BINARY CLASSIFICATION PROBLEMS
In this paper, we mainly focused on regression problems, but our idea can be applied to other applications. We briefly discuss its application to binary classification problems. A label space is set to y = 1} and loss function is set to be the squared loss: {(2, y) = 0.5(y z)². The ultimate goal of the binary classification problem obtain the Bayes classifier that minimizes the expected classification eπror,
R(g) def (ogny)) o Y],
over all measurable maps. is known that the Bayes classifier is expressed as sgm 9. (X)). where Op the Bayes rule of L(g) (x,(((((()) Y) (see Zhang (2004); Bartlett al. (2006). Therefore,
Io satisfies a margin condition, i.e., (x) 2 Jr > on supp( ), then this goal is achieved by obtaining an 7/ 7/2-accurate solution 9, in terms of the uniform norm on supp(px). That is, the required optimization accuracy on (l -ppl (px) to obtain the Bayes classifier depends only on the margin т unlike regression problems. Due to this property, averaged stochastic gradient descent in RKHSs achieve the linear convergence rate demonstrated in Pillaud- Vivien al. (2018a). To
leverage this theory to our problem setting, we consider the following decomposition:
ll 3pl (ox)
- ( g [1
(58)
+ (T(T) 9M.A i. (px)
(59)
+ 19MA - 900,2lL<x0(ex)
(60)
+ | 1 - 9pll
(61)
The last term 66 can made arbitrary small by -> as shown in Pillaud- Vivien et (2)
A term (60) can be bounded in the same manner the third statement of Proposition E yielding convergence to 0 as + oo with high probability. The convergence (59) was shown in
Hillaud-Viviees et al. (2018a) and the convergence of (58) guaranteed by Proposition A As result, we can show the following exponential convergence of the classification error R(g for two-layer
neural networks with sufficiently small À demonstrated in Pillaud- Vivien et al. (2018a).
[(R(ggm)) - R(gp)) s 2 2exp(-0(1270))
In Nitanda & Suzuki (219)) exponential convergence
shown for the logistic loss ((2,)) log(1 + exp(- as well. Proposition A also holds for the logistic loss with an easier proof than
the squared loss because of the boundedness of stochastic gradients of the loss. Hence, their theory is
also applicable to the reference ASGD in an RKHS. In summary, 588 (59). and [61] can be bounded
by the above argument. However, we note that bounding (60) not obvious and left for future work.
35


Reviews:
[{"review_id": "YUzOq4nycmF", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n \nThis paper considers the convergence property of averaged stochastic gradient descent on a overparameterized two-layer neural networks for a regression problem. This paper is the first to achieve the optimal convergence rate under the NTK regime. They show that smooth target functions efficiently specified by the NTK are learned rapidly at faster convergence rate.\n\n\n##########################################################################Pros: \n \n+ The paper is technically sound. It adapt the neural networks and the RKHSs theory into the NTK regime and the proof techniques are different from existing literatures.\n\n+ It achieves the minimax optimal convergence rate of $O(T^{-2r\\beta/2r\\beta + 1})$ which is always faster than $O(T^{-1/2})$.\n\n+ This work shows the connection between RKHS and NN in term of the $L_{\\infty}(\\rho_X)$ norm while the convergence result does not need the positivity of the NTK\n\n\n##########################################################################\nCons: \n \n- The writing of this paper is not clear enough, for example $L_2(\\rho(x))$ appeared without any explaination\n- The practical choice of M in their experiment is 2e4, which is impractical in NN tasks\n \n\n##########################################################################\nOverall, I vote for accepting. This paper combine the convergence analysis of averaged stochastic gradient descent on kernel methods with the connection of kernel method with neural network to derive an optimal convergence rate of NN in NTK regime while the proof technique is novel. My major concern is about the practical influence of this paper to the theory of deep learning training, as the width of the output layer is required to be large.\n\n#########################################################################\n\nQuestions:\n \nIn Assumption A3, why the parameter $r$ has to be in the range [1/2, 1]\nIs the averaging mechanism at the output of the algorithm beneficial to the rate in Theorem 1?", "extra_scores": {}, "extra_text": {}}, {"review_id": "TNq4397Wg3U", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Here is the review of the article: ``Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime''.\n\n**SUMMARY**\n\nThe authors show that under the Neural Tangent Kernel Regime investigated lately, averaged SGD achieves optimal rates in the attainable case.  Note that this result is not a *plug and play* based on the current kernelized-SGD litterature: the difficulty the authors achieve to overcome is the fact that they could bound the difference between the dynamics of SGD on the neural networks and on the neural tangent kernel. This is stated in Proposition A and it represents the novelty of the article\n\nMoreover, they give an explicit representation of the capacity condition (decrease rate of the eigenvalues of the covariance matrix) in the cases where they have a smooth approximation of the ReLu.\n\n**Clarity**\n\nThe paper is outstandly clear. Indeed, despite the fact that optimality in RKHS can be technical to introduce, I found the paper very clearly presented and well motivated. It was very pleasant and smooth to read. The references are also both precise and sufficient to understand well the problem.\n\nThe only default of the paper is that, in my opinion, the authors do not stress enough their contribution and their novelty. Indeed, despite Proposition A and the sketch of the proof, the article consists in a *plug and play* result on averaged SGD. The authors should then stress the outline of the proof (going to a M-approximation of the Neural Tangent RKHS) and comparing the dynamics on these.\n\n**Quality and Originality**\n\nThe paper is not super original, and as accustomed to this literature, there is no surprise seeing this result. However, the quality of the paper is undeniable and fills the gap between optimality of kernel methods and the NTK literature. I thank the authors to have done it very clearly.\n\n\n\n**Comments**\n\n-My main comment is about the fact that except from Proposition A, this article is a *plug and play* one. This proposition, and the full sketch of the proof should be emphasized as they consist on the true novelty of the work.\n\n-Three remarks concerning the plots :\n\n1-*Minor comment.* They should be bigger.\n2-*Minor comment.* Figure 1 should illustrate the fact that $\\beta = 1 + \\frac{1}{d-1}$. I suggest a log-log plot.\n3-*Intermediate comment.* I do not really see how exactly the discussion of the experimental part illustrates really the result. The discussion is fairly interesting, but I really would like to see a theoretical proposition showing that taking the two layers is better for learning.\n\n\n*** Conclusion***\n\nYet the fact remains that, I would really like this article to be published when the commentaries of the reviewers will be taken into accounts. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "SbgSUVBNoJ_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThe paper focuses on the understanding of neural tangent kernel (NTK), which has been a central topic in deep learning theory recently and plays an important role in characterizing the generalization ability of artificial neural networks. In Particular, the authors derive minimax-optimal learning rates of the averaged stochastic gradient descent method for over-parametrized two-layer neural networks with smooth activation functions. The results are novel and offer insights into the connections between deep learning methods and kernel methods. One difference of this paper from other studies is that the positivity of NTK is not required in the error analysis. Numerical experiments are also illustrated to confirm the theoretical results. The paper is well written and interesting to read. Overall, I vote for accepting.\n\n\nConcerns:\n1. Although the paper considers smooth approximations of the ReLU and also shows the explicit optimal rate, its analysis does not apply to ReLU networks which may be of greater interest to researchers. \n\n2. It looks a little bit strange to me that the regularization is conducted around the initial values. Will this lead to a big difference in the numerical experiments?\n\n3. Is there an explicit form for the lower bound of network width in Theorem 1, i.e., $M_0$?", "extra_scores": {}, "extra_text": {}}, {"review_id": "NLe1F2VU-Gs", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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 considers the optimization of a wide two layers neural network (for a regression task) using averaged SGD. The authors consider the Neural Tangent Kernel (NTK) regime. The NTK is a kernel defined using the activation function and the initial distribution of the parameters of the input layer. The RKHS H associated to this NTK is assumed to contain the Bayes predictor. Based on this, the authors derive a convergence rate for the predictor constructed from the T-th iterate of averaged SGD and the Bayes predictor in terms of the L2 distance wrt the distribution of the features. By specifying this bound in terms of the decay of the eigenvalues of the integral operator in H, they obtain an explicit generalization error bound, which is optimal for the class of problems considered in the paper.\n\nIt seems that the paper solves an important problem related to the training of neural nets. The paper is rather well written even if some paragraph are hard to understand for a non expert. \nFor example, several paragraphs of the paper are dedicated to compare the obtained results with those of concurrent work. The level of technicality of these discussions makes the reading experience difficult (e.g. last paragraph of Page 6), often because the discussion happens at a step where the reader is not familiar with the results (e.g. Section 1.2). These paragraphs seem like a discussion with the authors of these concurrent works. I would suggest to gather these discussions at the end of the paper, once the reader understands the results. Moreover, a better approach in my opinion would be to explicitly state the results (mathematically) of these concurrent work. This way, the comparison will be easier.\n\nAs a non expert, I believe that the results are new but I cannot be sure because I cannot compare with existing works (see my comment above). I recommend acceptation.\n\n\nOverall, the paper shows an important result: optimal rate for generalization bounds for 2 layers NN in the NTK regime. The result is well explained but some precision could make the paper even more insightful. For instance, why considering the NTK regime? What is the intuition behind that? How would you define mathematically \"the NTK regime\" ? I would also like to understand better the relaxation of the positivity of the NTK. Does it have to do with the assumption that the norm of the integral operator is greater than lambda?\n\n\nMoreover, Proposition A, which is fundamental in the approach, should be stated in the main paper for a better understanding. I think that the authors can move the numerical experiments to the appendix to win some space.\n\n\n\n\nMINOR:\n\nCheck the def of excess risk, last equation of Page 3\n\"negative dependence on\" should be \"inverse dependence on\"\n\", That is, \"\nWhy is Figure 1 in Section 1? Is it a mistake? It should not be placed here. Moreover it is not commented in the text.", "extra_scores": {}, "extra_text": {}}, {"review_id": "2XUuEqYTtnb", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzed the averaged SGD for overparameterized two-layer NNs for regression problems. Particularly, they show that the averaged SGD can achieve the minimax optimal convergence rate, with the global convergence guarantee. To achieve, they propose a new parameter which captures the ``complexities’’ of the target function and the RKHS associated with the NTK.\n\nThe paper is well-written, and the result looks very interesting. I am tending to accept the paper. This paper is a theory, so experiments are a plus. If the authors can address some of my comments, I am tending to increase the score of the paper.\n\n\n\nHere are some comments about writing.\n\nI believe Assumption 1 and 2 are reasonable. But each statement is just math, it is good to write a 2~4 words to summarize each A1, A2 .. Also several math statements highly replied on the definitions, and it is hard to find them in the paper.\n\nAfter Assumption 1, in the next page, page 5, there is a Remark that has 4 bullets, maybe write Ai at the beginning of each bullet.\n\nAlgorithm 1 requires more words and explanation, it is hard to understand this algorithm in the following sense : the size of each matrix/vector is not mentioned and hard to find them in the paper.\n\nIn page 6, is it possible to simplify the statement of Theorem 1 a bit? e.g. write a simplified version here, and put the full version in appendix.\n\nIn Theorem 1, what is M_0? Is that over-parameterization size? Is that polynomial in parameters or exponentially in parameters? (This is not major point of the paper, I am just curious about the bound) \n\nIn page 4, Eq. (2), is it possible to consider a simple model where gamma = 0? This is quite common in previous work.\n\nIn appendix, e.g. page 30, the last step of many equations use ->0. I don’t follow the meaning of this notation. Is that possible to avoid it?\n\nThis paper is focusing on average SGD, is there any intuition why non-average SGD won’t give the similar result?\n\nI felt the following paper is highly close to this work, and should be cited and discussed more deeply. Usually optimization has two parts, one is the number of iterations, and the other is cost per iteration. This paper focused on improving the number of iterations. The following paper improved the cost per iteration, in the NTK overparameterized regime. \nTraining (Overparametrized) Neural Networks in Near-Linear Time\nJan van den Brand, Binghui Peng, Zhao Song, Omri Weinstein\n\n\nMinor comments\n\nIn page 1, second paragraph, the place cited Du et al. 2019b, Allen-Zhu et al. 2019 and Du et al. 2019a.\n\nThe following two papers should also be cited\n\nZeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks.  [This paper shows the result for recurrent neural networks. Note that RNN is  a harder case, In deep neural networks the weight matrices in different layers are different. However in RNN, the weights matrix are the same over all the layers]\n\nZhao Song and Xin Yang. Quadratic suffices for over-parametrization via matrix chernoff bound.\n[This paper improved the over-parameterization bound from m >= n^6 (Du et al. 2019b) to m >= n^4, where m is the width of a neural network, and n is the number of input data points.]\n\nIn page 2, the first paragraph, the place cited Du et al. 2019b, Arora et al. 2019a, Weinan et al. 2019, Arora et al. 2019b, Lee et al,. 2019.\n\nThe following papers should also be cited\n\nJason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. [Arora et al. paper shows a connection between neural networks with neural tangent kernel regression. This paper generalizes the Arora et al result, and shows the connection between regularized neural networks with neural tangent kernel ridge regression.]\n\nSimilarly, in page 5, some citations should be added.\n\nSmall typos:\nThe last paragraph, Page 2 “the key to show” -> “the key to showing”\nThe third paragraph, Page 3 “which enable” -> “which enables”\nThe fifth paragraph, Page 4 “ A stochastic gradient descent” -> “Stochastic gradient descent”\nThe third paragraph Page 5 “a neural networks” -> “a neural network”\nThe third paragraph Page 6 “arbitrary small” -> “arbitrarily small”\nThe first paragraph Page 8 “the single-layer learning” -> “single-layer learning”\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents some exciting results on the convergence of averaged SGD for overparameterized two-layer neural networks. The AC and reviewers all agree that the contributions are significant and well presented, and appreciate the author feedback to the reviews. The corresponding revisions on assumptions and references, and the added simplified proposition in the introduction have nicely improved the manuscript. 
Decision: Accept (Oral)