Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods
Authors: Taiji Suzuki
Shunta Akiyama
Venue: ICLR 2021 Spotlight (2021)
Keywords: Excess risk
minimax optimal rate
local Rademacher complexity
fast learning rate
kernel method
linear estimator

Abstract: Establishing a theoretical analysis that explains why deep learning can outperform shallow learning such as kernel methods is one of the biggest issues in the deep learning literature. Towards answering this question, we evaluate excess risk of a deep learning estimator trained by a noisy gradient descent with ridge regularization on a mildly overparameterized neural network, 
and discuss its superiority to a class of linear estimators that includes neural tangent kernel approach, random feature model, other kernel methods, $k$-NN estimator and so on. We consider a teacher-student regression model, and eventually show that {\it any} linear estimator can be outperformed by deep learning in a sense of the minimax optimal rate especially for a high dimension setting. The obtained excess bounds are so-called fast learning rate which is faster than $O(1/\sqrt{n})$ that is obtained by usual Rademacher complexity analysis. This discrepancy is induced by the non-convex geometry of the model and the noisy gradient descent used for neural network training provably reaches a near global optimal solution even though the loss landscape is highly non-convex. Although the noisy gradient descent does not employ any explicit or implicit sparsity inducing regularization, it shows a preferable generalization performance that dominates linear estimators.

Published as a conference paper at ICLR 2021
BENEFIT OF DEEP LEARNING WITH NON-CONVEX NOISY GRADIENT DESCENT: PROVABLE EXCESS RISK BOUND AND SUPERIORITY TO KERNEL METHODS
Taiji Suzuki
Graduate School of Information Science and Technology, The University of Tokyo, Japan Center for Advanced Intelligence Project, RIKEN, Japan
E-mail: tai @mist. uuutokko.ac..3
Shunta Akiyama
Graduate School of Information Science and Technology, The University of Tokyo, Japan E-mail: akiyama@mist uu-ookyo.ac. ac.
ABSTRACT
Establishing theoretical analysis that explains why deep learning can outperform shallow learning such kernel methods is of the biggest issues in the deep learning literature. Towards answering this question, we evaluate excess risk of deep learning estimator trained by noisy gradient descent with ridge regular- ization on mildly overparameterized neural network, and discuss its superiority class of linear estimators that includes neural tangent kernel approach, ran- dom feature model, other kernel methods, k-NN estimator and so on. We consider teacher-student regression model, and eventually show that any linear estimator can be outperformed by deep learning in a sense of the minimax optimal rate espe- cially for high dimension setting. The obtained excess bounds are so-called fast learning rate which is faster than O(1/ (n) that is obtained by usual Rademacher complexity analysis. This discrepancy is induced by the non-convex geometry the model and the noisy gradient descent used for neural network training provably reaches a near global optimal solution even though the loss landscape is highly non-convex. Although the noisy gradient descent does not employ any explicit or implicit sparsity inducing regularization, it shows preferable generalization performance that dominates linear estimators.
INTRODUCTION
In the deep learning theory literature, clarifying the mechanism by which deep learning can out- perform shallow approaches has been gathering most attention for long time. In particular, it is quite important to show that a tractable algorithm for deep learning can provably achieve a better generalization performance than shallow methods. Towards that goal, we study the rate of conver- gence of excess risk of both deep and shallow methods in a setting of a nonparametric regression problem. One of the difficulties mization methods is that the solution is likely to be stacked in a bad local minimum, which prevents us show its preferable performances. Recent studies tackled this problem by considering opti- mization on overparameterized networks in neural tangent kernel (NTK) (Jacot et al., 2018; Du al., 2019 2019a) and mean field analysis (Nitanda Suzuki, 2017: Chizat & Bach, 2018; Rotskoff & Handen-Eijnden 2018; 2019; Mci al., 2018; 2019), analyzing the noisy gradient descent such as stochastic gradient Langevin dynamics (SGLD) (Welling & Tch, 2011; Raginsky et al., 2017; Erdogdu al., 2018).
show generalization ability of deep learning with certain opti-
The NTK analysis deals with a relatively large scale initialization so that the model is well approxi- mated by the tangent space at the initial solution, and eventually, all analyses can be reduced to those of kernel methods (Jacot et al., 2018; Du et al., 2019b; Allen Zhu et al., 2019; Du et al., 2019a; Arora al., 2019; Cao & Gu, 2019; Zou et al., 2020). Although this regime is useful show its global

---

Published as a conference paper at ICLR 2021
convergence, the obtained estimator looses large advantage of deep learning approaches because the estimation ability is reduced to the corresponding kernel methods. To overcome this issue, there are several "beyond-kernel" type analyses. For example, Allen-Zhu & Li (2019; 2020) showed benefit of depth by analyzing ResNet type networks. Li et al. (2020) showed global optimality of gradient descent by reducing the optimization problem to tensor decomposition problem for specific gression problem, and showed the "ideal" estimator on a linear model has worse dependency on the input dimensionality. Bai & Lee (2020) considered a second order Taylor expansion and showed that the sample complexity of deep approaches has better dependency on the input dimensionality than kernel methods. Chen et al. (2020) also derived similar conclusion by considering hierarchi- cal representation. The analyses mentioned above actually show some superiority of deep learning, but all of these bounds are essentially (11/v/)) where n is the sample size, which not optimal for regression problems with squared loss (Caponnetto & de Vito, 2007). The reason why only such a sub-optimal rate is considered is that the target of their analyses is mostly the Rademacher complexity of the set in which estimators exist for bounding the generalization gap. However, to derive a tight excess risk bound instead of the generalization gap, we need to evaluate so called local Rademacher complexity (Mendelson, 2002; Bartlett al., 2005; Koltchinskii, 2006) (see Eq. (2) for the definition of excess risk). Moreover, some of the existing analyses should change the target function class as the sample size n increases, for example, the input dimensionality is increased against the sample size, which makes it difficult to see how the rate of convergence is affected by the choice of estimators.
Another promising approach is the mean field analysis. There are also some work that showed superiority of deep learning against kernel methods. Ghorbani et al. (2019) showed that, when the dimensionality d of input is polynomially increasing with respect to the kernel methods is outperformed by neural network approaches. Although the situation of increasing explains well the modern high dimensional situations, this setting blurs the rate of convergence. Actually, we can show the superiority of deep learning even in a fixed dimension setting.
There are several studies about approximation abilities of deep and shallow models. Ghorbani et al. (2020) showed adaptivity of kernel methods to the intrinsic dimensionality in terms of approxi- mation error and discuss difference between deep and kernel methods. Ychudai & Shamir (2019) showed that the random feature method requires exponentially large number of nodes against the input dimension to obtain a good approximation for single neuron target function. These are only for approximation errors and estimation errors are not compared.
Recently, the superiority of deep learning against kernel methods has been discussed also in the nonparametric statistics literature where the minimax optimality of deep learning in terms of excess risk is shown. Especially, it is shown that deep learning achieves better rate of convergence than linear estimators in several settings -Sehmid--Hieber, 2020; Suzuki, 2019; Imaizumi & Fukumizu, 2019; Suzuki & Nitanda, 2019; Hayakawa & Suzuki, 2020). Here, the linear estimators are general class of estimators that includes kernel ridge regression, k-NN regression and Nadaraya-Wan Watson estimator. Although these analyses give clear statistical characterization on estimation ability of deep learning, they are not compatible with tractable optimization algorithms.
In this paper, we give a theoretical analysis that unifies these analyses and shows the superiority of a deep learning method trained by a tractable noisy gradient descent algorithm. We evaluate the excess risks of the deep learning approach and linear estimators in nonparametric regression setting, and show that the minimax optimal convergence rate of the linear estimators can be dominated by the noisy gradient descent on neural networks. In our analysis, the model is fixed and no explicit sparse regularization is employed. Our contributions can be summarized as follows:
A refined analysis of excess risks for a fixed model with a fixed input dimension is given to com- pare deep and shallow estimators. Although several studies pointed out the curse of dimensionality is a key factor that separates shallow and deep approaches, we point out that such a separation ap- pears in a rather low dimensional setting, and more importantly, the non-convexity of the model essentially makes the two regimes different.
A lower bound of the excess risk which is valid for any linear estimator is derived. The analysis is considerably general because the class of linear estimators includes kernel ridge regression with any kernel and thus it also includes estimators in the NTK regime.
All derived convergence rate is a fast learning rate that is faster than 0(1/ (n). We show that simple noisy gradient descent sufficiently wide two-layer neural network achieves fast
2

---

Published as a conference paper at ICLR 2021
learning rate by using fact that the solution converges to Bayes estimator with Gaussian process prior, and the derived convergence rate can be faster than that of linear estimators. This is much different from such existing work that compared only coefficients with the same rate of convergence with respect to the sample size n.
Other related work Bach (2017) analyzed the model capacity of neural networks and its corre- sponding reproducing kernel Hilbert space (RKHS), and showed that the RKHS is much larger than the neural network model. However, separation of the estimation abilities between shallow and deep not proven. Moreover, the analyzed algorithm basically the Frank- Wolffe type method which is not typically used in practical deep learning. The same technique is also employed by Barron (1993). The Frank- Wolfe algorithm is a kind of sparsity inducing algorithm that is effective for estimating function in model with an L1 Lo-norm constraint. It has been shown that explicit or implicit sparse regularization such as L reggulaariztton under certain situations (Chizat & Bach, 2020; Chizat, 2019; Gunasekar et al., 2018; Woodworth et al., 2020; Klusowski Barron, 2016). For example, E et al. (2019b;a) showed that the approxi- mation error of linear model suffers from the curse of dimensionality in setting where the target function is in the Barron class (Barron, 1993), and showed an Ly-type regularization avoids the curse of dimensionality. However, our analysis goes in a different direction where sparse regularization is not required.
beneficial to obtain better performances of deep learning
2 PROBLEM SETTING AND MODEL
In this section, we give the problem setting and notations that will be used in the theoretical analy- sis. We consider the standard nonparametric regression problem where data are generated from the following model for unknown true function fo IRd R:
y f + (i=1....,n))
(1)
where is independently identically distributed from Px whose support is included in Ω = [0. 1jd
and e, is an observation noise that independent of x; and satisfies Eles] = and e; E [-U, U] almost surely. The i.idd observations are denoted by Dn (z " We want to estimate the true function fo through the training data D,. To achieve this purpose, we employ the squared loss (y {x)))² and accordingly we define the expected and empirical risks as L(F) ==
[y,x[e(Y, (x))] and [(f) == 1
n Σ E(yr. fxx:)) respectively. Throughout this paper, we are interested in the excess (expected) risk of an estimator f defined by
(Excess risk)
<()-
inf f:ueasurable
C(F).
(2)
Since the loss function É is the squared loss, the infimum of inf memssrrable L(f) is achieved by fo: inf /=meusurable L(f) L(F)). The population Lz(Px) --norm denoted by [Iffll EEx-ix [Xx)]] and the sup-norm on the support of Px is denoted by || =
sup supresapp(Px) (x)). We can easily check that for an estimator f. the Ly-distance Il. f (1 between the estimator î and the true function fo is identical to the excess risk: L(Ū - L((9)= 1 Note that the excess risk is different from the generalization gap C(F) - L()) Indeed, the generalization gap typically converges with the rate of 0(1/V)) which is optimal in typical setting (Mohri et al., 2012). On the other hand, the excess risk can be faster than O which is known as a fast learning rate (Mendelson, 2002; Bartlett al., 2005; Koltchinskii, 2006; Giné & Koltchinskii, 2006).
2.1 MODEL OF TRUE FUNCTIONS
To analyze the excess risk, we need to specify function class (in other words, model) in which the true function f" is included. In this paper, we only consider a two layer neural network model, whereas the techniques adapted in this paper can be directly extended to deeper neural network models. We consider a teacher-student setting, that is, the true function f can be represented by neural network defined as follows. For w E R. let we be "clipping" of w defined w
3

---

Published as a conference paper at ICLR 2021
:=1x,, R x tanh(w/R) where R 2 1 is a fixed constant, and let [a;; 1] := [x_,1] ,1]"
for R Then, the
teacher network is given by
fw(()) = Em=1 am U2 I ( [x:; 1]),
where 1im E Rd+1 and 22,m E R (m E N) are the trainable parameters (where W (Wi,m, 32.m)m=1) am R (m E N) is fixed scaling parameter, and Fm I + IK is activation function for the m-th node. The reason why we applied the clipping operation to the parameter of the second layer is just for technical reason to ensure convergence of Langevin dynamics. The dy- namics is bounded in high probability in practical situations and the boundedness condition would be removed if further theoretical development of infinite dimensional Langevin dynamics would be achieved.
Let H. be set of parameters W such that its squared norm is bounded: H = W
(Wi,m, W2.m )
(I + w².m) < ooj. Define || || := IS m (1 W Wi,mll 1|2 +
w 11/2 for W E H. Let (pm)m= be regularization parameter such that jmn > 0. Accordingly
we define Hy = { E H ||W]|x, < oo} where ||Wi,, == [_m==1 pm" ([| + w )
for given 0 y. Throughout this paper, we analyze estimation problem in which the true function is included in the following model:
F = (fw W E Hy, || S1}.
This is basically two layer neural network with infinite width. As assumed later, am is assumed to decrease - oo. Its decreasing rate controls the capacity of the model. If the first layer parameters (wi,m) are fixed, this model can be regarded as a variant of the unit ball of some reproducing kernel Hilbert space (RKHS) with basis functions om [w [æ; 1])- However, since the first layer (Wi.)) is also trainable, there appears significant difference between deep and kernel approaches. The Barron class (Barron, 1993; E et al., 2019b) is relevant to this function class. Indeed, it defined as the convex hull of (ww [a;; 1J) with norm constraints on (W), W2) where is an activation function. On the other hand, we will put an explicit decay rate on am and the parameter W has an Lg-norm constraint, which makes the model F,, smaller than the Barron class.
3 ESTIMATORS
We consider two classes of estimators and discuss their differences: linear estimators and deep learning estimator with noisy gradient descent (NGD).
Linear estimator A class of linear estimators, which we consider as a representative of "shallow" learning approach, consists of all estimators that have the following form:
f(x) = E' (1P ... 2)..
Here, (pp)) can be any measurable function (and L2(Xx) >-ittegrable that the excess risk can be defined). Thus, they could be selected as the "optimal" one so that the corresponding linear esti- mator minimizes the worst case excess risk. Even if we chose such optimal one, the worst case excess risk should be lower bounded by our lower bound given in Theorem 1. It should be noted that the linear estimator does not necessarily imply "linear model." The most relevant linear estimator in the machine learning literature is the kernel ridge regression: f(x) = YT + ((x) E R² and Y
where Kx (k(zi,z;)); T=)) E 12 k(z) [k(2, x1), ............ k(x, Rd Rd + R. Therefore, the ridge regression
[y1...., yn] T R" for kernel function estimator in the NTK regime or the random feature model is also included in the class of linear estimators. The solution obtained in the early stopping criteria instead of regularization in the NTK regime under the squared loss is also included in the linear estimators. Other examples include the k-NN estimator and the Nadaraya- Watson estimator. All of them do not train the basis function in a nonlinear way, which makes difference from the deep learning approach. In the nonparametric statis- tics literature, linear estimators have been studied for estimating a wavelet series model. Donoho et al. (1990: 1996) have shown that a wavelet shrinkage estimator can outperform any linear estima- tor by showing suboptimality of linear estimators. Suzuki (2019) utilized such an argument to show superiority of deep learning but did not present any tractable optimization algorithm.
4

---

Published as a conference paper at ICLR 2021
Noisy Gradient Descent with regularization As for the neural network approach, consider noisy gradient descent algorithm. Basically, we minimize the following regularized empirical risk:
E(ww) + 1IW
Here, we employ Hi -nom as the regularizer. We note that the constant controls the relative complexity of the true function fo compared to the typical solution obtained un- der the regularization. Here, we define a linear operator A as X||W],, WT AW, that is, AW = (Apmm Wi,m: Apmm 1 m The regularized empirical risk can minimized by noisy gradient descent as Wk+1 = W₂ ([((()))) + 211 + V V where (..(L..))S..22. )m m is an dimensiodl Gaus-
? > 0 is step size and ÇK sian noise, i.e., (k.(I.m) and (2,(2.m) are independently identically distributed from the stan- dard normal distribution (Da Prato & Zabczyk, 1996). Here, vā(fw) = 1, - 2(,w(z,) ys ( [2;;; 1o'n (wI.m [r:;; 1)), am tanh' (anh'(w2,,, (W2,m/ (w (25 1)))==1 However, since V is unbounded which makes it difficult to show convergence, we employ the semi- implicit Euler scheme defined by
W4+1 = Wx- - -777-//2/0 7)V[(( -n
Es + W (W, WW.-nVEin (W--NVL(f))
(3)
where Sy = (I+nA) is easy to check that this is equivalent to the following update rule: Wi-
Wk-1 -1 (VL((( + Aw 2 (x-)) Therefore, the implicit Fuler scheme can be seen as a naive noisy gradient descent for minimizing the empirical risk with a slightly modified ridge regularization. This can be interpreted as discrete time approximation of the following infinite dimensional Langevin dynamics:
(4) where (E:)22 is the so-called cylindrical Brownian motion (see Da Prato & Zabczyk (1996) for the details). Its application and analysis for machine learning problems with non-convex objectives have been recently studied by, for example, Muzellec et al. (2020); Suzuki (2020).
dW, -VV(v(((f.)) + Al dt + 22/BdE.
The above mentioned algorithm executed on an infinite dimensional parameter space. In practice, approximate the solution by finite
should deal with finite width network. To do dimensional one: W(M) = (wI,m, 22,m)m where M corresponds to the width of the network. We identify W(M) to the "zero-padded infinite dimensional one, W (Wi,m, W2.m) with Wi.m = and W2.m = for all m > M. Accordingly, we use the same notation fwoe to indicate fw with zero padded vector W. Then, the finite dimensional version of the update rule is given by
k+1 M/()) (w(M) -VV[( + / 7 (M)) where ((M) is the Gaussian noise vector
obtained by projecting & to the first M components and ((M) is also obtained in a similar way.
4 CONVERGENCE RATE OF ESTIMATORS
In this section, we present the excess risk bounds for linear estimators and the deep learning estima- As for the linear estimators, we give its lower bound while give an upper bound for the deep learning approach. To obtain the result, we setup some assumptions on the model. Assumption 1.
(i) There exists constant Cu such that Pmm. S &G (m E N).
There exists On > 1/2 such that am S pm (m E N).
(iii) The activation functions (am)m m is bounded as [lāmlloo S 1. Moreover, they are three times differentiable and their derivatives upto third order differentiation uniformly bounded: 3C, such that [|am]]1.3 == max{] o'mlooo, loc, /o".l,,,,lo>lll... < C, (Vm E N).
The first assumption (i) controls the strength of the regularization, and combined with the second assumption (ii) and definition of the model Fy,, complexity of the model is controlled. If a and y large, the model is less complicated. Indeed, the convergence rate of the excess risk becomes
5

---

Published as a conference paper at ICLR 2021
faster if these parameters are large m " with p > 1 but we employ this setting just for a technical simplicity for ensuring convergence of the Langevin dynamics. The third assumption (iii) can be satisfied by several activation functions such as the sigmoid function and the hyperbolic tangent. The assumption || llse & 1 could be replaced by another one like ||0m II oc S C, but we fix this scaling for simple presentation.
later. The decay rate Mm S c.. can be generalized as
4.1 MINIMAX LOWER BOUND FOR LINEAR ESTIMATORS
Here, we analyze a lower bound of excess risk of linear estimators, and eventually we show that any linear estimator suffers from curse of dimensionality. To rigorously show that, we consider the following minimax excess risk over the class of linear estimators:
Riin (Fa)
inf sup f-linear fuEt,
-
where inf is taken over all linear estimators and F.D.. [:] is taken with respect to the training data Dn- This expresses the best achievable worst case error over the class of linear estimators to estimate function in F.y. To evaluate it, we additionally assume the following condition.
Assumption 2. We assume that jmm. = mm= and am = pm (m E N) (and hence Cy. = 1). There
exists monotonically decreasing sequence (bm)m=1 and 2 3 such that bm pm (Vm) with 02 > 7/2 and om = byn (b (0m u) (u E R) where a is the sigmoid function: o(u) = 1/(1+e="))
Intuitively, the parameter controls the "resolution" of each basis function Oms and the relation between parameter 0n and a2 controls the magnitude of coefficient for each basis dm- Note that the condition $ 2 3 ensures [mmlli.3 is uniformly bounded and 0 < 6m I 1 ensures [omll> S 1. Our main strategy to obtain the lower bound is to make use of the so-called convex-hull argument. That is, it is known that, for function class F, the minimax risk R(F) over a class of linear estimators is identical that for the convex hull of F (Hayakawa & Suzuki, 2020; Donoho et al., 1990):
RE (F) Rlin (conv (F)),
where cFnv(F) 1E deFi 1 E E 1, 2, N N} and conv(-) is the closure of (-) with respect to Iz(Px)-norm. Intuitively, since the linear estimator is linear to the observations (1 of outputs, a simple application of Jensen's inequality yields that its worst case еrror on the convex hull of the function class F does not increase compared with that on the original one FF (see Hayakawa & Suzuki (2020) for the details). This indicates that the linear es- timators cannot distinguish the original hypothesis class F and its convex hull. Therefore, if the class F is highly non-convex, then the linear estimators suffer from much slower convergence rate because its convex hull conv(F) becomes much "fatter" than the original one F. To make use of this argument, for each sample size n, we pick up appropriate mn and consider subset generated by the basis function mm.. . i.e., F(") ;= {amm m, F (wT,,,, [x; 1]) E Fx). By applying the con- vex hull argument to this set, we obtain the relation Run (F,) 2 Run (F = Rin (conv (T.(")) Since F((") is highly non-convex, its convex hull conv (F(")) is much larger than the original set F(")) and thus the minimax risk over the linear estimators would be much larger than that over all estimators including deep learning. More intuitively, linear estimators do not adaptively select the basis functions and thus they should prepare redundantly large class of basis functions to approx- imate functions in the target function class. The following theorem gives the lower bound of the minimax optimal excess risk over the class of linear estimators.
Theorem 1. Suppose that Var(e) > 0, Px is the uniform distribution on [0, 1]d, and Assumption 2 is satisfied. Let B
c1+
Then for arbitrary small Ke' O, we have that
02 02-7/2
28+d
R
n
72
(5)
The proof is in Appendix A. We utilized the Irie- integral representation (Irie & Miyake, 1988; Hornik et al., 1990) to show there exists a "complicated" function in the convex hull, and then adopted the technique of Zhang al. (2002) to show the lower bound. The lower bound is characterized by the decaying rate (ax) of am relative to that (a²) of the scaling factor b,n Indeed, the faster an decays with increasing m, the faster the rate of the minimax lower bound becomes.

---

Published as a conference paper at ICLR 2021
We can see that the minimax rate of linear estimators is quite sensitive to the dimension d. Actually, for relatively high dimensional settings, this lower bound becomes close to a slow rate Q11/ /n), which corresponds to the curse of dimensionality.
has been pointed out that the sample complexity of kernel methods suffers from the curse of dimensionality while deep learning can avoid that by tractable algorithms (e.g.. Ghorbani et al. (2019); Bach (2017)). Among them, Ghorbani et al. (2019) showed that if the dimensionality is polynomial against n, then the excess risk of kernel methods is bounded away from 0 for all n. On the other hand, our analysis can be applied to any linear estimator including kernel methods, and it shows that even if the dimensionality is fixed, the convergence rate of their excess risk suffers from the curse of dimensionality. This can be accomplished thanks to careful analysis of the rate of convergence. Bach (2017) derived an upper bound of the Rademacher complexity of the unit ball of the RKHS corresponding to a neural network model. However, it is just upper bound and there still large gap from excess risk estimates. Allen-Zhu & Li (2019; 2020); Bai & Lee (2020); Chen et al. (2020) also analyzed lower bound of sample complexity of kernel methods. However, their lower bound is not for the excess risk of the squared loss. Eventually, the sample complexities of all methods including deep learning take form of O(C/vn) and dependency of coefficient C' to the dimensionality or other factors such as magnitude of residual components is compared. On the other hand, our lower bound properly involves the properties of squared loss such strong convexity and smoothness and the bound shows the curse of dimensionality occurs even in the rate of convergence instead of just the coefficient. Finally, we would like to point out that several existing work (c.g., Ghorbani et al. (2019); Allen-Zhu & Li (2019)) considered a situation where the target function class changes as the sample size increases. However, our analysis reveals that separation between deep and shallow occurs even if the target function class F, is fixed.
4.2 UPPER BOUND FOR DEEP LEARNING
Here, we analyze the excess risk of deep learning trained by NGD and its algorithmic convergence rate. Our analysis heavily relies the weak convergence of the discrete time gradient Langevin dy- namics to the stationary distribution of the continuous time one (Eq. (4)). Under some assumptions, the continuous time dynamics has stationary distribution (Da Prato & Zabezyk, 1992; Maslowski, 1989; Sowers, 1992; Jacquot& & Royer, 1995; Shardlow, 1999; Hairer, 2002). If we denote the prob- ability measure on H corresponding to the stationary distribution by Too, then it is given by
d (W) x exp(-Bā(fw)), dug
where V/ is the Gaussian measure in H. with mean 0 and covariance (BA)-1 (see Da Prato & Zabczyk (1996) for the rigorous definition of the Gaussian measure on a Hilbert space). Remarkably, this can be seen as the Bayes posterior for prior distribution M/ and "log-likelihood" function exp(-8ā(W)). Through this view point, we can obtain an excess risk bound of the solution We- The proofs of all theorems in this section are in Appendix B.
Under Assumption 1, the distribution of We derived by the discrete time gradient Langevin synamics satisfies the following weak convergence property to the stationary distribution x This conver- gence rate analysis depends on the techniques by Bréhier & Kopec (2016); Muzellec et al. (2020).
Proposition 1. Assume Assumption holds and $ > n. Then, there exist spectral gaps Ar, and AG (defined in Eq. (10) of Appendix B. 1) and a constant Co such that, for any 0 a 1/4, the following convergence bound holds for almost sure observation Du:
v 1/2-0 =: Ek:
vB
Ew,, (wr.()((w))) Dz] - -enl--Ew=... (C[[] -A S (Coexp(-Nnnh) + C1
(6)
where Ci is constant depending only on cu. R, a1 Co U, (independent of 17, k, 3, X, m)).
This proposition indicates that the expected risk of W₁ can be almost identical to that of the "Bayes posterior solution" obeying ao after sufficiently large iterations k with sufficiently small step size 1 even though [(fw) is not convex. The definition of A can be found in Eq. (10). We should note that its dependency on 3 is exponential. Thus, if we take 3 M(n), then the computational cost until a sufficiently small error could be exponential with respect to the sample size n. The same convergence holds also for finite dimensional one (((M) with modified stationary distribution. The
7

---

Published as a conference paper at ICLR 2021
constants appearing in the bound are independent of the model size M (see the proof of Proposition in Appendix B). In particular, the convergence can be guaranteed even W is infinite dimensional. This is quite different from usual finite dimensional analyses (Raginsky al., 2017; Erdogdu al., 2018; Xu et al., 2018) which requires exponential dependency on the dimension, but thanks to the regularization term, we can obtain the model size independent convergence rate. Xu al. (2018) also analyzed finite dimensional gradient Langevin dynamics and obtained a similar bound where (n)) appears in place of the second term 17 1/2-a which corresponds to time discretization error. In our setting the regularization term is ||W Iir, = Em ((u)), 1|² + w2.mm/ //m. with pmm X m= but Em (l 1|2 + wg.mm) p/th for p > 1, then the time discretization error term would be modified to 1plp- 11/-1 (Andersson et al., 2016). We can interpret the finite dimensional setting as the limit of + oc which leads to 1f(r-1)/r dimensional result (O)))) as shown by Xu et al. (2018).
if we employ ||
1)/r + r that recovers the finite
In addition to the above algorithmic convergence, we also have the following convergence rate for the excess risk bound of the finite dimensional solution (MMM)
Theorem 2. Assume Assumption holds, assume y < 3 S min min(n/(2U/2) n), and 0 < 7 < 1/2 + aa. Then, if the width satisfies M 2 min { (11/2 2 -1/2((or+1), n n1/213. the expected excess risk of Wx. is bounded as
1/2 ED" Swoolllswae f fl [D,]] S max ((7 14//,,, X Hor B -AT uj +
where C is constant independent of n, 3, N, k. In particular, if we set B min (2nnn)/2U2)) n) and À = 3-1,, then for M 2 n 112 we obtain
EDD E Illf - - [nu]] $ n
Sn - E
In addition to this theorem, if we further assume Assumption 2, we obtain a refined bound as follows.
Corollary 1. Assume Assumptions 1 and hold and 1) < B, and let B3 min(n/(2U*"),) n) and == =--1. Suppose that there exists 0 S q S 8 - 3 such that 0 < 7 < 1/2 + an + q022. Then, the excess risk bound of W (M) for M 2 n2/2(ar+qa2+11) can be refined as
Ep
F P Wa (P2l E 1itgeott
These theorem and corollary shows that the tractable NGD algorithm achieves a fast convergence rate of the excess risk bound. Indeed, if q is chosen so that y > (a1 +oo1+ga+++11) then the excess risk bound converges faster than OlI/vn). Remarkably, the convergence rate is not affected by the input dimension d, which makes discrepancy from linear estimators. The bound of Theorem 2 is tightest when 7 is close to 1/2 + a1 (y x 1/2 + a1 3az for Corollary 1), and smaller y yields looser bound. This relation between 7 and (1) reflects misspecification of the "prior" distribution. When y is small, the regularization >||W|| 12, is not strong enough that the variance of the posterior distribution becomes unnecessarily large for estimating the true function f E F,. Therefore, the best achievable bound can be obtained when the regularization is correctly specified. The analysis of fast rate is in contrast to some existing work (Allen-Zhu & Li, 2019; 2020; Li et al., 2020; Bai & Lee, 2020) that basically evaluated the Rademacher complexity. This is because we essentially evaluated a local Rademacher complexity instead.
4.3 COMPARISON BETWEEN LINEAR ESTIMATORS AND DEEP LEARNING
Here, we compare the convergence rate of excess risks between the linear estimators and the neural network method trained by NGD using the bounds obtained in Theorem 1 and Corollary respec- tively. We write the lower bound (5) of the minimax excess risk of linear estimators as Ri and the excess risk of the neural network approach (7) as R To make the discussion concise, we consider
a specific situation where 3, 01 = 7 = L this case, 3 =173 Rs 5.667, which gives
d
n n ( 1I.5+2)) +
R 2 n
234d
n -*
8

---

Published as a conference paper at ICLR 2021
On the other hand, by setting O, we have
NN S aill n - (1+ )=
Thus, as long a1 11.3/d - 1 23/d d we have that
Rijn RKN and lim
BNN 0.
Rii
In particular, as d gets larger, Rig approaches to (/n while RNN is not affected by d and it gets close O(n-1 as ai gets larger. Moreover, the inequality ai 11.3/d + 1 can be satis- fied by a relatively low dimensional setting; for example, d = 10 is sufficient when On = 3. As a1 becomes large, the model becomes "simpler" because (am, ) decays faster. However, the linear estimators cannot take advantage of this information whereas deep learning can. From the convex hull argument, this discrepancy stems from the non-convexity of the model. We also note that the superiority of deep learning is shown withou! sparse regularization while several existing work showed favorable estimation property of deep learning though sparsity inducing regularization (Bach, 2017; Chizat, 2019 Hayakawa & Suzuki, 2020). However, analysis indicates that sparse regularization is not necessarily as long as the model has non-convex geometry, i.e,, sparsity is just one sufficient condition for non-convexity but not necessarily condition. The parameter setting above is just a sufficient condition and the lower bound Ri would not be tight. The superiority of deep learning would hold in much wider situations.
CONCLUSION
In this paper, we studied excess risks of linear estimators, as representative shallow methods, and neural network estimator trained by noisy gradient descent where the model is fixed and no sparsity inducing regularization is imposed. Our analysis revealed that deep learning can outperform any linear estimator even for a relatively low dimensional setting. Essentially, non-convexity of the model induces this difference and the curse of dimensionality for linear estimators is consequence of a fact that the geometry of the model becomes more "non-convex" as the dimension of input gets higher. All derived bounds are fast rate because the analyses are about the excess risk with the squared loss, which made it possible to compare the rate convergence. The fast learning rate of the deep learning approach is derived through the fact that the noisy gradient descent behaves like Bayes estimator with model size independent convergence rate.
ACKNOWLEDGMENTTS
TS was partially supported by JSPS Kakenhi (18K19793, 18H03201, and 20H00576), Japan Digital Design and JST-CREST.
REFERENCES
Z. Allen-Zhu and Y. Li. What can ResNet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems 32, pp. 9017-9028. Curran Associates, Inc., 2019.
Z. Allen-Zhu and Y. Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint arXiv:2001.04411 2020.
Z. Allen-Zhu, Y. Li, and Z. Song. A convergence theory for deep learning via wer-parrameerrizatoon. In Proceedings of International Conference on Machine Learning, pp. 242-252, 2019.
A. Andersson, R. Kruse, and Larsson. Duality in refined Mallivv-Mallaavn spaces and weak ap- proximation of SPDE. Stochastics and Partial Differential Equations Analysis and Computations, 4(1):113-149, 2016.
S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang. Fine- Fine-grained analysis of optimization and gen- cralization for overparameterizze two-layer neural networks. arXiv preprint arXiv:1901.088: 1901088490,,844 2019.

---

Published as a conference paper at ICLR 2021
F. Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Machine Learning Research, 18(19): 2017.
Y. Bai and J. D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. International Conference on Learning Reprexentations, 2020. URL https: / //oppnneeieww.. wttt//ooommmddrx11cyy/////
A. R. Barron. Universal approximation bounds for superpositions sigmoidal function. JEEE Transactions Information theory, 39(3):33-9945, 1993.
Bartlett, O. Bousquet, and Mendelson. Local Rademacher complexities. The Annals of Statis- tics, 33:1487-1537, 2005.
C.-E. Bréhier and M. Kopec. Approximation of the invariant law of SPDEs: emror analysis using Poisson equation for full-discretization scheme. IMA Journal of Numerical Analysis, 37(3): 1375-1410, 07 2016.
Y. Cao and Q. Gu. A generalization theory of gradient descent for learning over-parameterized deep ReLU networks. arXiv preprint 100.03190,.01384 2019.
A. Caponnetto and E. de Vito. Optimal rates for regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-36, 2007.
M. Chen, Y. Bai, J. D. Lee, Zhao, H. Wang, C. Xiong, and R. Socher. Towards understanding hier- archical learning: Benefits of neural representations. Advances in Neural Information Processing Systems, 33, 2020.
L. Chizat. Sparse optimization on measures with over-parameterized gradient descent. preprint arXiv:1907. 100000007..00,, 2019.
arXiv
L. Chizat and F. Bach. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv:1812.0790 2018
L. Chizat and F. Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. arXiv preprint arXiv:2002.044 04486, 2020.
G. Da Prato and J. Zabczyk. Non-explosion, boundedness and ergodicity for stochastic semilinear equations. Journal of Differential Equations, 18:181-195, 1992.
G. Da Prato and J. Zabezyk. Ergodicity for Infinite Dimensional Systems. London Mathematical Society Lecture Note Series. Cambridge University Press, 1996.
D. L. Donoho, R. C. Liu, and B. MacGibbon. Minimax risk over hyperrectangles, and implications. The Annal of Statistics, 186)):141-11477, 09 1990. doi: 1.. 2214/////117637777
D. L. Donoho, M. Johnstone, G. Kerkyacharian, and D. Picard. Density estimation by wavelet thresholding, The Annals of Statistics, 24(2):508-539, 1996.
Du, Lee, H. Li, L.. Wang, and Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675-1685, 2019a.
S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over--oramenn wver-parameteriee neural networks. International Conference on Learning Representationss 7, 2019b.
W. E, C. Ma, and L.. Wu. priori estimates of the population risk for two-layer neural networks. Communications in Mathematical Sciences, 1077:1147 2019a.
W. E, C. Ma, and L. 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, 2019b.
M. A. Erdogdu, L. Mackey, and O. Shamir. Global non-convex optimization with discretized diffu- sions. In Advances in Neural Information Processing Systems 31, pp. 9671-9680. 2018.
10

---

Published as a conference paper at ICLR 2021
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv:1904.12191 2019.
B. Ghorbani, S. Mei, T. Misiakiewicz, and A. Montanari. When do neural networks outperform kernel methods? arXiv preprint arXiv:2006. 13409, 2020.
E. Giné and V. Koltchinskii. Concentration inequalities and asymptotic results for ratio type empir- ical processes. The Annals of Probability, 14(3):1143-1211) 2006.
S. Gunasekar, J. D. Lee, D. Soudry, and N. Srebro. Implicit bias of gradient descent linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9482-9491, 2018.
M. Hairer. Exponential mixing properties of stochastic PDEs through asymptotic coupling. Probab. Theory Related Fields, 124(3)3345-385 -300-000,, 2002.
S. Hayakawa and T. Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-366 361,,,61,2200 2020. ISSN 0893-6080.
K. Hornik, M. Stinchcombe, and H. White. Universal approximation of an unknown mapping and its derivatives using multilayer feedforward networks. Neural Networks, 365):551-560, 1990.
M. Imaizumi and Fukumizu. Deep neural networks learn non-smooth functions effectively. In
K. Chaudhuri and M. Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 869-878. PMLR, 16-18 Apr 2019.
B. Irie and S. Miyake. Capabilities of three-layered perceptrons. In IEEE 1988 International Con- ference Neural Networks, pp. 641-648, 1988.
A. Jacot, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31, pp. 8580-8589, 2018.
Jacquot and Royer. Ergodicité d'une classe d' d'équutiion aux dérivées partielles stochastiques. Comptes Rendus de l'Académie des Sciences. Série Mathématiqque, 320(2):231-2366 1995.
J. M. Klusowski and A. Barron. Risk bounds for high-dimensional ridge function combinations including neural networks. arXiv preprint arXiv:1607.014 1607.01444, 2016.
V. Koltchinskii. Local Rademacher complexities and oracle inequalities in risk minimization. The Aunals of Statistics, 11:2593-2656 2006.
Y. Li, T. Ma, and H. R. Zhang. Learning wer-parametrized two-layer neural networks beyond ntk. volume 125 of Proceedings of Machine Learning Research, pp. 2613-2682. PMLR, 09-12 Jul 2020.
B. Maslowski. Strong Feller property for semilinear stochastic evolution equations and applications. In Stochastic systems and optimization (Warsaw, 1988), volume 136 of Lect. Notes Control Inf. Sci., pp. 210-224. Springer, Berlin, 1989.
S. Mei, A. Montanari, and P.-M. Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, 115633)E7665-E777,, 2018 doi: 10. 1..77//paas.1005579999
S. Mei, T. Misiakiewicz, and A. Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In A. Beygelzimer and D. Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learn- ing Research, pp. 2388-2464, Phoenix, USA, 25-28 Jun 2019, PMLR.
S. Mendelson. Improving the sample complexity using global data. IEEE Transactions Informa- tion Theory, 18:1919-1 2002.
M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
11

---

Published as a conference paper at ICLR 2021
B. Muzellec, K. Sato, M. Massias, and T. Suzuki. Dimension- free convergence rates for gradient Langevin dynamics in RKHS. arXiv preprint 2003.00306, 2020.
A. Nitanda and T. Suzuki. Stochastic particle gradient descent for infinite ensembles, arXiv preprint 1712.0043, 2017.
M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via Stochastic Gradient Langevin Dynamics: nonasymptotic analysis. arXiv e-prints, pp. arXiv:1702.03849, 2017.
G. Rotskoff and E. Vanden -ijneen. Parameters interacting particles: long time convergence and asymptotic eπror scaling of neural networks. In Advances in Neural Information Processing Systems 3/, pp. 7146-7155. Curran Associates, Inc., 2018.
G. M. Rotskoff and E. Vanden- Eijnden., Trainability and accuracy of neural networks: An interacting particle system approach. arXiv preprint urXiv:/805.00911 2019.
W. Rudin, Real and Complex Analysis (third edition). Mathematics series. McGraw- 1987.
Hhamidt-Hicber Nonparametrie regression using deep neural networks with ReLU activation function. The Annals of Statistics, 48(4), 2020.
Shardlow. Geometric ergodicity for stochastic PDEs. Stochastic Analysis and Applications, 17 (5):857-869, 1999.
R. Sowers. Large deviations for the invariant measure of reaction-diffusion equation with non- Gaussian perturbations. Probab. Theory Related Fields, 92(3):393 1992. ISSN 0178-8051.
T. Suzuki. Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionality. In International Conference on Learning Representa- lions, 2019. URL https:://tppeeeeeeee http///ppereeeeeeeeee wtterriwwwweeeeeeeeeee foremmoormmmmm/ id=HHeebsAActh
T. 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 33, pp. appear. Curran Associates, Inc., 2020.
Suzuki and A. Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. arXiv preprint arXiv:1910. 1979. 2019.
M. Welling and Y.W.. Teh. Bayesian learning via stochastic gradient Langevin dynamics. In ICML., pp. 681-688, 2011.
B. Woodworth, S. Gunasekar, J. D. Lee, E. Moroshko, P. Savarese, I. Golan, D. Soudry, and N. Sre- bro. Kernel and rich regimes in overparametrized models. volume 125 Proceedings of Machine Learning Research, pp. (673-3673. PMLR, 09-12 Jul 2020.
Xu, J. Chen, D. Zou, and Gu. Global convergence of langevin dynamics based algorithms for nonconvex optimization. In Advances in Neural Information Processing Systems, volume 31, pp. 3122-3133. Curran Associates, Inc., 2018.
G. Yehudai and O. Shamir. On the power and limitations of random features for understanding neural networks. In Advances in Neural Information Processing Systems 32, pp. 6598-666 Curran Associates, Inc., 2019.
S. Zhang, M.-Y. Wong, and Z. Zheng. Wavelet threshold estimation of a regression function with random design. Journal of Multivariate Analysis, 80(2):256-2844 2002.
D. Zou, Y. Cao. D. Zhou, and Q. Gu. Gradient descent optimizes over over-paramette wer-pprameterized deep ReLU networks. Machine Learning, 109(3):467-492, 2020.
12

---

Published as a conference paper at ICLR 2021
A PROOF OF THEOREM
We basically combine the "convex hull argument" and the minimax optimal rate analysis for linear estimators developed by Zhang al. (2002).
Zhang et al. (2002) essentially showed the following statement in their Theorem 1.
Proposition 2 (Theorem of Zhang et al. (2002)). Let be the Lebesgue measure. Suppose that the space has even partition A such that |A| = 2 for an integer K E N, each A has equivalent measure (A(A)= = 2-k for all A E A, and A is indeed a partition of St i.e., UAEA S2 A' 00 for A, A' E S and A + A'. Then, if K is chosen as n. nn 2- S n for constants 7i, 72 >> that independent of n, then there exists an event & such that, for a constant C" > 0,
P(E) o(1 and {x; I4 A (1.....,))) C'n/2" (VAE
Moreover, suppose that, for a class Fe of functions on Q there exists A > 0 that satisfies the following conditions:
1. There exists F 0 such that, for any A A. there exists g E F that satisfies g(x²) Z 1/2 AF for all x E A.
2. There exists K' and C" > 0 such that Ei= g(1,)² < C"A?2 K' for any E F on the event E.
Then, there exists constant F1 such that at least one of the following inequalities holds:
12
2
S Ruin (F²),
(8a)
4F C"
T
F3
A 2
< Rua (F))
(8b)
32
for sufficiently large n.
Before we show the main assertion, we prepare some additional lemmas. For sigmoid function a, let F(0) {u Rd + aT x + b))) |a| s 2C, ||w||| 1, 16 2 (a. E, w E Rd) for
C> 0, 0,770 0.
Lemma 1. Let (xx) = H(((x + 1) o(x - 1)) and & be its Fourier transform: ((w) == ( (e Let h > and Dw 0. Then, by setting h h-2 1) and C (2va+1)Dm, the Gaussian RBF kernel can be approximated by xh(v(D)
sup g(x) exp (-11 |||=
inf getonv (ag
xE|o,112
2h.
4
CaD exp( (ppp(-D2//2) + exp( -Dw)
(2)
for any e E [0. 1]a, where Ca is a constant depending only on d. In particular, the right hand side is O(exp(-n*)) if D n².
Proof of Lemma 1. Let (n(x) = (hh Suppose that, for f E (RR)), its Fourier transform -w" "ww'(((r) "s(r)da (w E IRd)) gives
i(w) = (2m)-d eww
f exp(iw T T f))(w)d f(x),
for every Rdl, Then the Irie- Miy-Miyykee itegral representation (Irie & Miyake (1988); also the proof of Theorem 3.1 in Homiik et al. (1990)) gives
((x) f JAER J
I
(aa + b)du(a, b) (a.e.);
IIf f is integrable, this inversion formula holds for almost every Rd (Rudin, 1987). However, assume stronger condition that holds for every x Rd.
13

---

Published as a conference paper at ICLR 2021
where dv(a,,) b) is given by
dv(a, b) Re
f (wa)ddab
2mT((w)
for any w + O. Since the characteristic function of the multivariate normal distribution gives that
J exp(in (os -x))
h2d
1/2 |
(- |x cll2 [(x) (Va R²),
(2T)d
exp
du exp
212
=f(w)
we have that
|| 11=-cl cll2)
2/h )
exp
e-iub iimb
)
whip (2T)d
(wh)21la1)
JaER
bER
(a (x- b)RRe
2T// (w)
exp
2
dadb,
for all æ E IRd. equivalent to
Since v-(()) (b 11)) and Sn = hh)(h.) by its definition, the right hand side is
I (bh T (xc c) + Re) JagRa BER
--iw
Whi2ad (2r)d
(- (wh)P[lall 12 dadb.
exp
2xhhi((w))
Here, we set w = h-1 Let N₂₂ be the probability measure corresponding to the multivariate normal with mean 0 and covariance o²1, and let AD {w Rd ||w|| s D}. Let Da 0 and Do Da(V2d + 1), and define
fD. (x) = 2D, (An.)(An)) I DaISD..Ibl
e ib/h
v T (x - c) + bjiRee
27th((11)
(-Ila]? ||a|2
exp
2 dadb.
(2m)ad
Then, we can see that, for any x [0, 17d, it holds that
[(x) Sm.
(AD.)
1
Ni(A).) / 2exp(-h" (xxAp())xexp((11 '/o)d + + 2exp(-1b-1(1p) 2 2VdD
(DoNi(AD.) (AD.))
MDD.
1
[4hN (A 4h 4he-p((Daa)
(AD.((AD.) (1)
4h
CdD2(d-2) exp(-Dd exx(-
2D,Ni (Ap.) (2Th
where C. > 0 is constant depending on only d, and we used la T (x - c) + b) 2 |b| - |a Txx
c)1 2 |6] 2 2vdD,, and vxx)) < 2 exp(-1lr)) Note that if D. = n². then the right hand side is
(h exp( )) Therefore, since (1(AD.) < 1, by setting 5 h- h C De we have =hle(1)²
that
sup x(x) cxp (- 1| (_1lx-0) c12 (112 g p(r), rE(0.11a
inf
2/2
CaD exp(_Dx) exp(
Do) (D))
(1T((1)
Hence, by rewriting D' + Da. we obtain the assertion. As noted above, the right hand is ((exp(-n*)) if D., n².
14

---

Published as a conference paper at ICLR 2021
Proof of Theorem 1. For sample size n, we fix mn which will be determined later and use Proposition 2 with F F."). If W2.m. = by hmmp with [b] I 1 and wi,m [0,1]4, then
pmin [u; -u- cl(( 2(d+ for u Rd such that ||all I 1 and [1(w1, mm, )1? I 1hnn (1/2 + (1 + lu /22d + 1)) pmnn. Therefore, Puc(a) am, W, 0 m. (wI,,, [x; 1J) = Mm (bpril (2) [mm (umastt/2 TuT(e c)/ 22(++))
F F. for all b E R with 66| I 1, u 18d with ||l] I 1, and
[0. 11. In other words, 02 +/2
on 22 (2C)- C.+ F
(m) for any C > 0 and v2(d+1) Mm..
Mmm
Therefore, by setting C = (V + 1)D (a (1))) for Dw > 0, Lemma yields that for any
C [0, 1js and given > 0, there exists g E conv (F(")) such that
2( 2(v2d + 1)
[-1l=-ol''
on 8222 Mm
exp
x1/1(1111
2h2
S Pm
t7/2
22(2dd + 1)
4
Ca D2 20x(d-))ep((DDD exp(-D2a//2 + exx((-Da
Th) h
(TT(1)]
t222000 mm
CaD
exp(-D² 2) exp(-Dra))
(v + 1)
We let Dw = n² for any K > 0 and choose pmm, as 22 pmm
-/27 Dwh = h nn We write
A
pmma
an aLt7/2+ (2C) -1 = h
21 t2a
02-7/2 +1 -(( a2-5/2
ter +1) Then, it holds that
[_1l--cf 9
A exp
A exp(--n").
21
Here, set h as h = 2 with a positive integer k. Accordingly, define partition A of Q so that any A E A can be represented as A = [2- j0, 2 2- + 1)] x ... x [2- 22- 2 (ja + 1)] by non-negative integers 0 J: - 2
(i 1, 1,...,d, d). Note that [A] = 2nh = h h-d
For each A E A. we define CA as CA = (2 (2 (ii + 1/2).... 2 k (ja + 1/2)) where (ji.-.., -a) is set of indexes that satisfies A [2- jı, 2-, + 1)] x... [2~ 2 xja 1)]- For each A E A, we define Р4 E conv ( (n)) as a function that satisfies Eq. (9) for e e= CA.
Now, we apply Proposition 2 with F²
conv(F and K K' dk. Let R REa (con((o(())())) First, we can see that there exits a constant F > 0 such that
(Λ(x) 2 FA (Vr E A),
where we used exp(-n")
< 1.
Second, in the event E introduced in the statement of Proposition 2, there exists C such that Ifi {1....,,)) xs E A') < Cn/22-a dk for all A' E A. In this case, we can check that
exp (-1
||,, - -cAl? )}²
S Aha = 2 kdd
212
1=1
by the uniform continuity of the Gaussian RBF. Therefore, we also have
1
(a(
2 <
Σ A exp (-
| 10-- 1
)"
+ cd 2 exe((=220) 2nn)
2h
s A12 + exxp(2n"')
where e >> 0 is a constant. Thus, as long as h is polynomial to n like = (((=a), the right hand side is O(A2)d)
15

---

Published as a conference paper at ICLR 2021
Now, if we write
01 + 8012 + +7/2
01 + (8 + 1)02
+1
02 7/2
02 7/2
then have A hon- by its definition.
Here, we choose k as a maximum integer that satisfies that
Fd 2 dl R In this situation, holds
32
h 2xB ~ R
Since Eq. (8b) is not satisfied, Eq. (8a) must hold, and hence have
h S R²
h2
1_202 23
h = n
Therefore, obtain that
2014
2nd2
R 2 n
20
20124
2814
n 28424
by setting x = K 20++2d"
243
This gives the assertion.
B PROOFS OF PROPOSITION 1, THEOREM 2 AND COROLLARY 1
Proposition 1, Theorem and Corollary can be shown by using Propositions 3 and 4 given in Appendix B.1 shown below.
Let TwW (1C, mi,m un W2.m mmm for W = (Wi.m, W2.m m m for a >> O, and let us consider model hw JT-a/2W- Then, the training error can be rewritten
B(ww) B(broraaw.
For notational simplicity. we let Z(W) = ((fw).
Let H(M) be (W(M) = (Wim. W2.m )MM_ Wi, E Rd+1 W2. E R, 1 m S M) and 6: (MM) + H. be the zero padding of W(M), that is, (M) = (w( we )o0 H satisfies wi.m = Wi.m, w/y 22m (m S M) and wi.m. = 0, w/ = 0 (m > M). Moreover, we define u² H H(M) as the map that extracts first M components. By abuse of notation, we write FwoM for (M)) H(M to indicate fagw(o)- Finally, let A H(M) H(M) be linear operator such that (MM) = '" (M)))))))) which is just truncation of A. Similarly, let Th ((M for w(rr) E ((M) be the operator corresponding to T for E H, i.c., T (MM) = c" (T())
B. AUXILIARY LEMMAS
First, we show some key propositions to show the main results. To do so, we utilize the result by Muzellec al. (2020) and Suzuki (2020).
Assumption 3.
There exists constant cy such that pmm. S cy-m
(ii There exist B, U > O such that the following two inequalities hold for some a E (1/4,1) almost surely:
vž(W)]l S B (VW E H),
VV(W)- Vā(W")l T.(W -WII,, (AW, W E HH).
16

---

Published as a conference paper at ICLR 2021
(iii) For any data Dw, L is three times differentiable. Let D(W) be the third-order derivative of L(W). This can be identified with a third-order linear form and V' (eW)((()hh (h,K) k) denotes the Riesz representor of I E H. + (O((W) k,,, There exists a' E [0,1), Co E
(0, co) such that VW, h. k E H. [[V (h,l)) Ca. (Calllllllll [[V
(h, k) S Ca Coll) [1k|| (a.s.).
Remark 1. In the analysis of Bréhier & Kopec (2016); Muzellec et al. (2020); Suzuki (2020),
Assumption 3-(iit) is imposed for any finite dimensional projection ((W(M)) as a function on H(M)
for all M 2 1 instead of L(W) as function of H. However, the condition on L(W) gives sufficient condition for any finite dimensional projection in our setting. Thus, we employed the current version.
Assumption 4, For the loss function (())) = (y [-))), the following conditions holds:
(i) There exists > O such that for any fw (W E H), it holds that
[x,r - ((Y, f (X))) & C(C(fw) - L(f*))
(ii) 3 > 0 is chosen so thut, for any h: Rd IR and E supp( (Px), it holds that
Eyjx=a| exp
( [
8 (e(Y, f (x)))) $
(iii) There exists Lg > such that W(Y, (YY,ho hw (X)) Vw Vw (x)(x S Lall Will (VW, W E H) almost surely.
(iv) There exists Cj such that |/w - -w 1l S C.IlW - W' (W, W E H)..
Proposition 3. Assume Assumption 3 holds and B > Suppose that RR > 0, 0 S Jw S R for any W E (a.s.). Let p 1+A4/P1 and #n
X B
+ Se. Accordingly, ler max 1}, 3x-
b+ + 1 and V 4b/ (L/t//44////2220 ())) Then, the spectral gap of the dynamics is given by
min
A
2p 2
6
(10)
4 (ogg(((V + 1)/(1 - 8))
where 0 < 8 < 1 is real number satisfying ô = (icespp-((pol((-11111 lim,- A7 (i.e. V is replaced by 4b/(, (1((oxxpp 11/2 11112-xxp(-2 A 1)). We also define Cw x(V + 1 V2(R+b) Then, for any 0 < < 1/4, the following convergence bound holds for almost sure observation D, for either L = or L= =
We define Aj =
V8
Ew, [ EW [T]
(11)
VB
SG Cw. Cw. +
Ai 17" 1/2-a
=
(12)
where C1 a constant depending only on Cu. B, L, Car,a a, R (independent of n. kc (,
Proposition 4. Assume that Assumptions 3 and 4 hold. Let â 1/{2(a + 1)} for given > O and 0 be an arbitrary real number satisfying true function fo can be represented by hw- f0 for W* Ha(at1). Then, if M z min [x (3120/00)))11//000a-++ 31/2[0(a+11], x -1/2((++1) (enlaat1nnn/222ff n2/2(0(0+11]] the expected excess risk is bounded by
< 0 < 11- 11-6 ā. Assume that the
Enn E Emgaa |C( (c(hrn/"
[n) -
S C max {AB))
IT375
20/0
nZăr x ~ g- X2, 1//1 +E
(13)
where C. is constant independent of n, B, X, n7 k.
Proof. gives
Repeating the same argument in Proposition I and using the same notation. Proposition
E [ (C(W()")))D) - Ew (n) 5k,
17

---

Published as a conference paper at ICLR 2021
for any 1 v M cc. Therefore, just need to bound the following quantity: EDD E (0 (oh (/onn//// ((
We define |W(M0] = lle (W(())) for W(M) H(M), For > O, we define Had0 be the projection of Ha to the first M components, Hbrr) (((W) W E Ha), and we define [|W (( = [[(((W( (note that since H(M) is a finite dimensional linear space, is same as H as set). Let (M)) be the Gaussian measure on H(M) with mean 0 and covariance (BA(M))- and (b be the Gaussian measure corresponding to the random variable Ty W(()) with WIM) (M) Let the concentration function be V
( 69.2 (c) =
inf W
2 @I
log b (M) ((W E H(M | +
4-1
where, if there does not exist W E H(M that satisfies the condition inf, then we define ( (c) = 00, then Let
max (inf > (c) S $ (,, 1/n].
Then, Suzuki (2020) showed the following bound:
ED"
1 (wwanwn (C [D2] - [(Fo) (M))
20/0 S C <mmax max { e²² (2 +n n 14070 (A3) T+0/00
11
(14)
n2
They also showed that, for M = oo, it holds that
S max (1B)) (3-1) 22 1n.n11 1 max (A 20=30- 83-1, .2.
Substituting this bound of E" Eq. (14), we obtain Eq. (13) for M Moreover, in their proof, if M 2 (c")-1/((a+1)) then
inf WEROD: C(hw)-2(P)ge
BX|[W]2
H00 & B(E))
Finally, since 8/3 is marginal distribution of 2/ holds that
loog 1/ (LW E H(M) || 5 + < - log 7 (00) ((W E H I|W 1 S t)).
Therefore, as long as M 2 (11)-1110(++)), the rate of E* is not deteriorated from M = oc. other words, if M 2 min (31/200 x-1/2[((++1), n 1/2(0(a-1)]) the bound (13)
oc. In
holds.
Remark Suzuki (2020) showed Proposition under a condition a > 1/2. However, this used only to ensure Assumption 3. In our setting. we can show Assumption 3 holds directly and thus we may omit the condition a > 1/2.
B.2 PROOFS OF PROPOSITION 1, THEOREM AND COROLLARY
Here, we give the proofs of Proposition and Theorem 2 simultaneously.
Proof of Proposition and Theorem 2. Let R (2 E2 an R+ U)2, Then, that (y:- ( < R. As stated above,
easily check
Propositions 3 and 4 to show the statements.
First, we show Proposition for the dynamics of (M) for any < M < co. However, it suffices to show the statement only for M because the finite dimensional version can be seen
18

---

Published as a conference paper at ICLR 2021
specific case of the infinite dimensional one. Actually, the dynamics of W( is same that of (W)) where Wi & H obeys the following dynamies:
WA+1 = Sn -W (VCCanC + 5x
2m
This is because f.ww) is determined by only the first M components v(W),, (VE(SnW))) V Were (atr:oo)_aaa.. and S, is a diagonal operator. Since the components We with indexes higher than M does not affect the objective, smoothness of the objective is not lost. The stationary distribution ((M) of the continuous dynamics corresponding to W(M) is probability measure on HL(M) that satisfies
(M) (W(M)) x dug (M)
(M) is the Gaussian measure R- with mean 0 and covariance (BA(M))-1 We where v3
notice that this is the marginal distribution of the stationary distribution of the continuous time counterpart of Wy: di (W)
Therefore, we just need to consider an infinite dimensional one. For this reasoning, we show the convergence for the original infinite dimensional dynamics (Wa) ) The convergence of the finite dimensional one (M) ) can be shown by the same manner using the argument above.
To show Proposition 1, we use Propositions 3. To do so, we need to check validity Assumptions First, we check Assumption 3. Assumption 3-(i) is ensured by Assumption Next, we check Assumption 3-ii). The boundedness of the gradient can be shown as follows:
[V((Fw) 11
Σ
Σ 1=1
2(f (zt) - v1) (rr: 1|o'm (wi, (as; 11) /|
m=1
Σ
n
2(fw (xx) - -yi)am tanh (wah R)om (w.. (xns 11)) P)
ARR 2 (d 1)C? 4Raa
(::fw((z;) vil < R, 11o'nllo S Co. || tanh' bl S 1)
<ARIEC
2 < 00. Σ
m=1
Similarly, we can show the Lipschitz continuity of the gradient as
|V - vi(fw:)l
201 2
201 { [Raa (d + ()2, -w'mm?
+ 12 [| w1mmll
Mm
m=1
+ ARa [W2mm w2 / + C2 1) - w/ 112] (:r tanh" 11 S 1)
4 + 1)0 + R2 1/ R22 C (d + 1)) max
max("m
201 a
mEN
Im (W2,m w/g || "/
2
We can also verify Assumption 3-(ii)) in a similar way. Then, we have verified Assumption 3. Therefore, may apply Proposition 3, and then we obtain Proposition 1.
19

---

Published as a conference paper at ICLR 2021
Next, show Theorem 2 by using Proposition 4. For that purpose, need to verify Assump- tion 4. The first condition can be verified as
Exyl((Y--w(aa)) - -
-e -Y ((
[x(())) (wx))))))))()+))))))))>))) -xx (x -w -Ex(((()))(M(())
-IIf- +x/()()xX)))(())))++++))))+))))+
- S REx (X) - -
The second condition can be checked as follows. Note that
B I(Y fw(x))) (Y 18-f0t -P())))))))
Ey|x==
exp
n
B (f(xx) fw(x))² 2c(fw(()) m(O)))
E
exp
n
B (f(xz) (w)()))
E.e { exp
28 (fw(() - -(a)) }
exp
n
())))) - Sw (x)))
1 148²
4U2 (Uw(1) - M()))
S
exp
exp
88 n²
Thus, under the condition
S n/ n2 the right hand side can be upper bounded by
3 1 1 U
exp
Next, we check the third and fourth conditions. Noting that
V hw (X)
(am (pm "2.m pmm
a/2 2 a/22 [x:;; [ 1|o'n (um aa////2 (uma/ wT [z 1)),
ampim 02 tanh' Lanh'(mm // 2 m2 R) R)om (mm 0/ 2 wI... (.,; 11))
m=1
have that
IV (X)
2 an I +1]
m=1
< [[d [[d+1)RR C. +1] Σ Pm
22
m=1
$ [[dd+1) + 1]c, 222
Σ m
2(-))201) =; C1 < 00
m=1
(:--a 201 a1 1122)
and
[Vwhw(X) - wwh.((X)ll
2 a (d + 1)(m ( (122m - n2 + 12,,mm 1 - wy.mml? mm
m=1
+ -a
-a ( (W2.m w2mmm /²/R² 2 + (d + 1) 1| wi.m!!? 1|
<
Σ
am 1) R2 + (d) +
2 2a
1)]l|w]) - wi.mml (W2,m _w2mm)²
m=m
20

---

Published as a conference paper at ICLR 2021
$ c max 2(m M 1)(1+))()1))) + + C. 1)][[W w C2 C2IlW- - -
for constant 0 C2 co. Therefore, it holds that Jow (X) - hw (X)] & C.llW - which yields the forth condition, and we also have
(w - kw
= 1 (X) (MD)-YJWwhhae ( (X) V (X)
(V - Vwhw(())) li2
+ 2112(1h (X) (
S8R2||WW wi + 80 - w z I| - W
which yields the third condition.
Since f F,, there exists W* H. such that fw-- Therefore, applying Proposition 4 with ai (ā = 1/(2(a1 + 1) and 0 = 7/(1 + a1) (since 7 < 1/2 - 01, the condition 0 < 1 ā
is satisfied), we obtain that for M 2 min o +224m)(a++)) +1) 31/22, x -11 n//22 }. the following excess risk bound holds:
ED"
( [C(W( ) -((*) 2 max { (AB) Ilao ाकक x 3 1/..1// +
24/0
Finally, by noting ((W( - [(f)) = I1 f (1i we obtain the assertion.
f
Finally, we give the proof of Corollary 1.
Proof of Corollary Note that
fw(
Om W2 Om am [w] 1])
m=1
pm
mm/mmmm p
902 q0a p sms (Jmm "w [x; 1]) (t. am = 101
bm 16
Σ to t 12.
(0- (5-9)az (mm m " [x:; 1)).
Therefore, may redefine of an q00 and s' +- - that obtain another representation of the model Fgi
= [frwl)== Σ
of ūm om (w [z;; 1]) W E H7, [W|,, s $1 }
F F== =
where (.) = Mm (p Note that the condition 0 = 3 s - 2 3. Therefore, Assumptions 3 and 4 are valid even for the redefined parameters a¹ s' and o. instead of a1, and On- Therefore, we can apply Theorem 2 by simply replacing O1 by a = 01 + go22
21


Reviews:
[{"review_id": "_HVFOHI0U1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper is theoretical sound and well organized. This paper shows that the Bayes estimator with Gaussian prior can outperform the linear estimators (including kernel regression and k-NN), which I believe is indeed interesting and important.\n\nBesides, I would like to raise the following comments and questions.\n\n1. The network function is different from the commonly-used one. For example, the authors need to clip the output weights using tanh function. The authors state that the reason is to ensure the boundness condition of the network function. What if using a standard parameterization of a two-layer network but performing projected (noisy) gradient descent?\n\n2. It seems that the goal of all estimators is to recover the teacher networks. However, the Bayes estimator actually uses the same network structure as the teacher one. It is more interesting to investigate the case where the underline teacher network is independent of the learned network (e.g., using an overparameterized network to learn a smaller network).\n\n3. In the description of hat f, the authors may need to clearly state the definition of the function \\phi_i.\n\n4. Does the result in Theorem 2 hold for any f^{\\circ}?\n\n5. In Proposition, the convergence results look similar to the following paper, while in their paper, the right-hand side of (6) converges to O(\\eta^{1/2}) when k\\eta goes to infinity. Could you briefly discuss why in this paper, this quantity is in the order of O(\\eta^{1/2-a})?\n\nXu, Pan, et al. \"Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization.\" arXiv preprint arXiv:1707.06618 (2017).\n\n6. Besides, I feel that the comparison with Raginsky et al., 2017 and Erdogdu et al., 2018 after Proposition may not be fair. In particular, the convergence results in these papers are derived based on different assumptions, thus their dependencies on the dimension are not directly comparable. \n\n7. Moreover, it may not be appropriate to state that “NGD achieves a fast convergence rate”, it seems that the spectral gap \\Lambda^* still has an exponential dependency on the parameter beta (shown in Proposition 3), which will be set as beta = \\Theta(n) in Theorem 2. This implies that the noisy gradient descent may require exponential time to output a good solution.\n\n8. In Theorem 2, can we view the expected error between F_{W_k^{(M)}}  and f^{\\circ} as a variant of generalization error (in expectation)? If this is the case, can we somehow apply the results in the following paper, and obtain a O(n^{-1}) generalization error bound for the Langevin dynamic gradient algorithm (if considering finite dimension case)? \n\nMou, Wenlong, et al. \"Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints.\" Conference on Learning Theory. 2018.\n\n9. A suggestion: It is better to present Section B.1 before the first part of Section B, since the proof of Proposition 1, Theorem 2, and Corollary 1 largely rely on the assumptions and propositions in Section B.1.\n\n10. Lastly, the authors may also want to include the following two NTK papers in the introduction section. \n\nZou, Difan, et al. \"Gradient descent optimizes over-parameterized deep ReLU networks.\" Machine Learning 109.3 (2020): 467-492.\n\nCao, Yuan, and Quanquan Gu. \"Generalization bounds of stochastic gradient descent for wide and deep neural networks.\" Advances in Neural Information Processing Systems. 2019.", "extra_scores": {}, "extra_text": {}}, {"review_id": "UxGrEoBjcoJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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\nThe paper aims to demonstrate the superiority of deep learning methods against kernel methods by comparing their excess risk bounds. In particular, the authors first derive the minimax lower bound for linear estimators by assuming that the target function can be represented by a teacher neural network, which implies that the linear estimators suffer from curse of dimensionality. Then the authors further derive a dimension-independent upper bound of the noisy gradient descent method for overparametrized two-layer neural networks, which theoretically confirms the benefit of deep learning methods in terms of convergence rates. The paper is well written and also interesting to read. Overall, I vote for accepting.\n\n\nConcerns:\n1. In the teacher-student setting, what is the minimax rate for any estimator of $f^0$ instead of just linear estimators? Or is the upper bound for the noisy gradient descent method minimax optimal?\n2. Traditionally we impose smoothness assumption on the target function directly (e.g. Holder space). So what is the main advantage of this teacher-student setting?\n3. In Theorem 1, I feel a little bit confused why the dimension $d$ also appears in the numerator, which is different from classical lower bounds. For example, If we assume that $f^0$ belongs to a Sobolev space of order $r$, then the minimax rate of excess risk will be $n^{-\\frac{2r}{2r+d}}$, which goes to 0 as $d$ goes to infinity. Do I have any misunderstanding?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "O5rJCVOfjZS", "reviewer": "AnonReviewer2", "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": "#### General comments\nThis paper aims at proving superiority of neural network models to any linear estimators, including kernel methods.  To attain this purpose,  this paper focuses on  two layer neural network class with an infinite width. For the non-parametric regression models within this neural network class, this paper establishes a sharp excess risk error of the least square methods with  noisy gradient descent update, although such optimization may be heavily non-convex. Moreover, a lower bound of  all linear estimators under the $L_2$-norm   are accordingly given when the true function is within the two layer neural network class, thereby showing superiority to kernel  methods.  Overall，the contribution of this paper is obvious and the literature review is full to some extent.\nThis paper is organized well and stated clearly. \n\n#### Specific Comments\n（1）After Theorem 1, the sentence \"for relative high dimensional settings, this lower bound becomes close to a slow rate $\\Omega(1/\\sqrt{n})$, which corresponds to the curse of dimensionality. \"  I argue  that this sentence may be uncorrected, \nsince the mentioned rate is independent of the input dimension, which is not a real curse of dimensionality. \n(2)  A constraint on  $f_{W}$ should be added, otherwise, it is impossible to identify $a_m$ and $\\bar{w}_{2,m}$ simultaneously. \n(3) What is the role of noisy term in NSGD algorithm, is it a similar conclusion when the standard SGD is applied? \n(4）What  is the additional difficulty encountered when analyzing a thin but deep neural network?", "extra_scores": {}, "extra_text": {}}, {"review_id": "0-ZMqwo6vLn", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "=========================\n\nSummary:\n\nThe paper shows that a two-layer neural network (although an extension to deeper models seem unproblematic) may outperform a class of linear functions in terms of the excess risk learning rate, and in a minimax optimality analysis, and when approximating a target function from the neural network class. The paper essentially shows that linear functions have a problem with the non-convexity of the neural network class, and approximate the slow rate of 1/(n)^(1/2) for increasing dimension. A neural network trained with noisy stochastic gradient descent on the other hand has a faster rate, depending on several parameters.\n\n=========================\n\n=========================\n\nPros:\n\n- Well written and polished paper.\n\n- Technically sounds as far as I can tell. (Randomly checked some parts in more detail.)\n\n- Setting and results may be interesting for a large audience.\n\n- Main results and message of the paper are to the point.\n\n=========================\n\n=========================\n\nCons:\n\nVery technical and on some parts I would have liked some more intuition and discussion. See detailed feedback and also questions for rebuttal.\n\n=========================\n\n=========================\n\nScoring:\n\nOverall I think this is a worthwhile contribution in understanding the difference in deep and shallow learning, and as the paper is very sound I will vote for accept. I will acknowledge, however, that there is a flurry of related work, as it is a very popular topic, and I can not vouch for the novelty of this contribution. The authors, however, covered much ground in that regard.\n\n=========================\n\n=========================\n\nQuestions for rebuttal:\n\nIt appears to me that the neural networks are not part of the linear functions class, and thus having a neural network target makes the linear functions being misspecified. Is that true? If so, does that play a role in the learning rate gap? In case it is not true, what is the essential difference then between the linear functions and the neural networks? Regarding that, what is phi_i in the definition of linear models?\n\nInstead of noisy gradient descent you actually use semi-implicit euler scheme for optimization, do you have any thoughts on how that might effect actual performance?\n\nAs far as I can see your current analysis does not hold for relu-activations, how easy might an extension to that be?\n\nAre you aware of any lower bounds for the neural network case, are your rates optimal?\n\n=========================\n\n=========================\n\nAdditional feedback:\n\nThe result that the minimiax rate of linear functions over a space F is the same as over its convex hull was not known to me. For me it would have been very useful if you could provide some intuition on why that is the case.\n\nYou show that the rate of the neural network is independent of the dimension. Do you have any intuition on why that is the case?\n\nUnder Equation (5), instead of \"more faster,...,more faster\" write \"the faster,..., the faster\"\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes deep networks optimized using non-convex noisy gradient descent. The main result shows that in a teacher-student setting, the excess risk converges in a fast-rate and is stronger than any linear estimators (which include kernel methods). The paper also gives a convergence rate result that depends on some spectral gaps (which can be very small) but not on dimension. Overall the paper is interesting. It should probably emphasize that the dependency on spectral gaps (and the fact that they could be exponentially small) on the convergence as the current abstract suggests efficient convergence.
Decision: Accept (Spotlight)