Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods
Authors: Shunta Akiyama
Taiji Suzuki
Venue: ICLR 2023 poster (2023)
Keywords: Deep learning theory
optimization
learning theory
excess risk

Abstract: While deep learning has outperformed other methods for various tasks, theoretical frameworks that explain its reason have not been fully established. We investigate the excess risk of two-layer ReLU neural networks in a teacher-student regression model, in which a student network learns an unknown teacher network through its outputs. Especially, we consider the student network that has the same width as the teacher network and is trained in two phases: first by noisy gradient descent and then by the vanilla gradient descent. Our result shows that the student network provably reaches a near-global optimal solution and outperforms any kernel methods estimator (more generally, linear estimators), including neural tangent kernel approach, random feature model, and other kernel methods, in a sense of the minimax optimal rate. The key concept inducing this superiority is the non-convexity of the neural network models. Even though the loss landscape is highly non-convex, the student network adaptively learns the teacher neurons.

Published as a conference paper at ICLR 2023
EXCESS RISK OF TWO-LAYER RELU NEURAL NET- WORKS IN TEACHER-STUDENT SETTINGS AND ITS SU- PERIORITY TO KERNEL METHODS
Shunta Akiyama
Graduate School of Information Science and Technology, The University of Tokyo, Japan aaaaaaakkiiaaaaammm.m.aaam i-tokyo.ac. ip
Taiji Suzuki
Graduate School of Information Science and Technology, The University of Tokyo, Japan Center for Advanced Intelligence Project, RIKEN, Japan taijidme i. u-tokyo. ac.
ABSTRACT
While deep learning has outperformed other methods for various tasks, theoretical frameworks that explain its reason have not been fully established. We investigate the excess risk of two-layer ReLU neural networks in a teacher-student regression model, in which student network learns an unknown teacher network through its outputs. Especially, we consider the student network that has the same width as the teacher network and trained in two phases: first by noisy gradient descent and then by the vanilla gradient descent. Our result shows that the student net- work provably reaches a near- grear-llobal optimal solution and outperforms any kernel methods estimator (more generally, linear estimators), including neural tangent sense
kernel approach, random feature model, and other kernel methods, the minimax optimal rate. The key concept inducing this superiority is the non- convexity of the neural network models. Even though the loss landscape is highly non-convex, the student network adaptively learns the teacher neurons.
INTRODUCTION
Explaining why deep learning empirically outperforms other methods has been one of the most sig- nificant issues. In particular, from the theoretical viewpoint, it is important to reveal the mechanism of how deep learning trained by an optimization method such as gradient descent can achieve supe- rior generalization performance. To this end, we focus on the excess risk of two-layer ReLU neural networks in a nonparametric regression problem and compare its rate to that of kernel methods. One of the difficulties in showing generalization abilities of deep learning is the non-convexity of the associated optimization problem Li et al.) (2018), which may let the solution stacked in a bad local minimum. To alleviate the non-convexity of neural network optimization, recent studies focus on paraamtttttiiiiioonnn as the promising approaches. Indeed, it is fully exploited by (i) Neural
Tangent Kernel (NTK) (Jacot et al. 2018 Allen-Zhu et al. 2019 Arora et al. 2019 Du al. 2019
Weinan et al. 2020 Zou et al. 2020) and (ii) mean field analysis (Nitanda & Suzuki 2017 Chizat
& Bacc 2018
Mei 2018
al. 2019 Tzen Raginsky 2020 Chizat
2021]Suzzkk & Akiyama 2021).
In the setting of NTK, relatively large-scale initialization is considered. Then the gradient descent related to parameters of neural networks can be reduced to the convex optimization RKHS, which is easier to analyze. However, in this regime, it is hard to explain the superiority of deep learning because the estimation ability of the obtained estimator is reduced to that of the corresponding kernel. From this perspective, recent works focus on the "beyond kernel" type analysis Allen-Zhu &
Li (2019))) Bai & Lee (020); Li et al. (2020); Chen et al. (2020); Refinetti et al. (2021) | Abbe et al. (022). Although their analysis shows the superiority of deep learning to kernel methods in each setting, in terms the sample size (n). all derived bounds are essentially 2(1/ This bound is
known to be sub-optimal for regression problems Caponnetto & De Vito 2007

---

Published as a conference paper at ICLR 2023
In the mean field analysis setting, kind of continuous limit of the neural network is considered, and its convergence to some specific target functions has been analyzed. This regime is more suitable in terms of "beyond kernel" perspective. but it essentially deals with a continuous limit and hence is difficult to control the discretization error when considering a teacher network with a finite width. Indeed, the optimization complexity has been exploited recently in some research, but it still requires an exponential time complexity in the worst case (Mei et al. 20188; Hu et al. 2019, Nitanda et al.) 2021a). This problem is mainly due to the lack of landscape analysis that requires closer exploitation of the problem structure. For example, we may consider the teacher student setting where the true function represented as a neural network. This allows us to use the landscape analysis in the optimization analysis and give more precise analysis of the statistical performance. In particular, we can obtain a more precise characterization of the excess risk (e.g., Suzuki & Akiyama (20T))
More recently, some studies have focused on the feature learning ability of neural networks (Abbe et al. 2021 2022] Chizat & Bach| 2020; [a et al., 2022 Nguyen (02T). Among them, (Abhe et al. 22021) considers estimation of the function with staircase property and multi-dimensional Boolean inputs and shows that neural networks can learn that structure through stochastic gradient descent. Moreover, Abbe al. (022) studies similar setting and shows that in a nigh-dimensional setting, two-layer neural networks with sufficiently smooth activation can outperform the kernel method. However, obtained bound is still 0(1/vn) and requires higher smoothness for activation as the dimensionality of the Boolean inputs increases.
The teacher-student setting is one of the most common settings for theoretical studies, e.g.. Tian Safran & Shamir 2018 Goldt et al. 2019 Zhang et al. 22119) Safran et al., [021; Tian 2020
Yehudai & Shamir| 2020 Suzuki & Akiyama 2021 Zhou et |
Akiyama & Suzuki 2021 to
name a few. Zhong et al. (017)) studies the case where the teacher and student have the same width,
shows that the strong convexity holds around the parameters of the teacher network and proposes a special tensor method for initialization to achieve the global convergence to the global optimal. However, its global convergence is guaranteed only for a special initialization which excludes a pure gradient descent method. [Safran & Shamir| (2018) empirically shows that gradient descent is likely to converge to non-global optimal local minima, even if we prepare a student that has the same size as the teacher. More recently, Yehudai & Shamir (2020) shows that even in the simplest case where the teacher and student have the width one, there exist distributions and activation functions in which gradient descent fails to learn. Safran et al. (202T) shows the strong convexity around the parameters of the teacher network in the case where the teacher and student have the same width for Gaussian inputs. They also study the effect of weer-parameterization and show that over- parameterization will change the spurious local minima into the saddle points. However, it should be noted that this does not imply that gradient descent can reach the global optima. [Akiyama & Suzuki (202I) shows that the gradient descent with a sparse regularization can achieve the global optimal solution for an werrpaaaameterize student network. Thanks to the sparse regularization, the global optimal solution can exactly recover the teacher network. However, this research requires highly wwer-parameterized network. Indeed, it requires an exponentially large number of widths in terms of the dimensionality and the sample size. Moreover, they impose quite strong assumptions such that there is no observation noise and the parameter of each neuron in the teacher network should be orthogonal to each other.
The superiority of deep learning against kernel methods has also been discussed in the nonparametric statistics literature. They show the minimax optimality of deep learning in terms of excess risk. Especially a line of research (Schmidt-Hiehed
2020 Suzuki 2018 Hayakawa & Suzuki 20200 Suzuki & Nitandal 2021; Suzuki & Akiyama| 2021) shows that deep learning achieves faster rates of convergence than linear estimators in several settings. Here, the linear estimators are a general class of estimators that includes kernel ridge regression, k-NN regression, and Nadaraya- Watson estimator. Among them, Suzuki & Akiyama (202T) treats tractable optimization algorithm in a teacher-student setting, but they require an exponential computational complexity and smooth activation function, which does not include ReLU.
In this paper, we consider a gradient descent with two phases, a noisy gradient descent first and a vanilla gradient descent next. Our analysis shows that through this method, the student network recovers the teacher network in a polynomial order computational complexity (with respet to the sample size) without using exponentially wide network, even though we do not need the strong assumptions such as the no-existence of noise and orthogonality. Moreover, we evaluate the excess risk of the trained network and show that the trained network can outperform any linear estimators,
2

---

Published as a conference paper at ICLR 2023
including kernel methods, in terms of its dependence the sample size. More specifically, contributions can be summarized as follows:
We show that by two-phase gradient descent, the student network, which has the same width the teacher network, provably reaches the near-optimal solution. Moreover, conduct a refined analysis of the excess risk and provide the upper bound for the excess risk of the student network, which is much faster than that obtained by the generalization bound analysis with the Rademacher complexity argument. Throughout this paper, our analysis does not require the highly over parameterization and any special initialization schemes.
We provide a comparison of the excess risk between the student network and linear estima- tors and show that while the linear estimators much suffer from the curse of dimensionality, the student network less suffers from that. Particularly, in high dimensional settings, the convergence rate of the excess risk of any linear estimators becomes close to O(n ((n-1/2), which coincides with the classical bound derived by the Rademacher complexity argument.
The lower bound of the excess risk derived in this paper is valid for any linear estimator. The analysis is considerably general because the class of linear estimators includes kernel ridge regression with any kernel. This generality implies that the derived upper bound can- not derived by the argument that uses fixed kernel, including Neural Tangent Kernel.
2 PROBLEM SETTINGS
Notations
For m E N, let [m] == (1....,, m). For x E IRd, || denotes its Euclidean norm. We denote the inner product between x, y R by (z, Σド= Lith. s denotes the unit sphere in Rdd For a matrix W, we denote its operator and Frobenius norm by [|Wll2 and ||W |F. respectively.
Here, we introduce the problem setting and the model that we consider in this paper. We focus on a regression problem where we observe n training examples Dn = (x,, generated by the following model for an unknown measurable function f R2d - IR:
y: = f(x,))
where (a::) is independently identically distributed sequence from Px that is the uniform distri- bution over gd-1, and 6 are i.i.d. random variables satisfying Bic] 0, E[c]] v², and Icl < U a.s.. Our goal is to estimate the true function fo through the training data. To this end, we consider the square loss Ey, f(x) = (y ((x)) and define the expected risk and the em- respectively. In this paper, we measure the performance of an estimator f by the excess risk L(F)
pirical risk as L(f) == Ex, (X(Y, [(X) and Z(J) = 1
inf C(f). Since fameasurahle
inf C(f)= = C(f)) we can check that the excess risk coincides with II ff-fo1) (1 the L2- distance between and fe, We remark that the excess risk is different from the generalization gap c()) - Z()). Indeed, when considering the convergence rate with respect to n, the generalization gap typically converges to zero with O(1/vm) Wainwright (2019). On the other hand, the excess risk can converge with the rate faster than ((1/ Vn), which is known as fast learning rate.
2.1 MODEL OF TRUE FUNCTIONS
To evaluate the excess risk, we introduce a function class in which the true function f is included. In this paper, focus the teacher-student setting with two-layer ReL.U neural networks, in which the true function (called teacher) is given by
m7
fa- (x)= Σ a afo((((..))) x)), j=1
where (u) max(u, 0} is the ReLU activation, m is the width of the teacher model satisfying
m < d, and af E R, wj E Idd for j [m] are its parameters. We impose several conditions for the
parameters of the teacher networks. Let W (wf wy w E Rd and σi > 02 2 2 dm
3

---

Published as a conference paper at ICLR 2023
be the singular values of W First, assume that a; E {=1} for any [mm] Note that by 1-
homogeneity of the ReLU activation this condition does not restrict the generality of the teacher
networks. Moreover, we assume that there exists min > 0 such that om min- If d m
0, there
exists an example in which fa has multiple representations. Indeed, Zhou et (021 shows
that in the case a 1 for all j E [m]] and Σ wg O, it holds that fa 2 ( x)) Σz=1 w(. r)). Hence, throughout this paper, we focus on the estimation problem in which the true function is included in the following class:
FF (Se,wo a (+13", || S 1, > m
This class represents the two-layer neural networks with the ReLU activation whose width is most the dimensionality of the inputs. The constraint ||o]||2 S 1 is assumed only for the analytical simplicity and can be extended any positive constants.
3 ESTIMATORS
In this section, we introduce the classes of estimators: linear estimators and neural networks (student networks) trained by two-phase gradient descent. The linear estimator is introduced as a general- ization of the kernel method. We will show separation between any linear estimator and neural net- works by giving a suboptimal rate of the excess risk for the linear estimators (Theorem 4.I). which simultaneously gives separation between the kernel methods and the neural network approach. A detailed comparison of the excess risk of these estimators will conducted in Section
3.1
LINEAR ESTIMATORS
Given observation (11,))),-.. (Iin Un), an estimator fis called linear if represented by
n
f(x)= Σ (...
where (p=) is sequence of measurable and T22 (2x (o((P))-nnne iintegraae functions. The most important example in this study the kernel ridge regression estimator. We note that the kernel ridge estimator is given by f(x) = (T(Kx + AI) k(z), where Kx (1)...)........ k(0, =T,]] E R² and Y [v...... Dn) R. which is linear to the output observation Y. Since this form is involved in the definition of linear estimators, the kernel ridge regression with any kernel function can be seen as one of the linear estimators. The choice of y; is arbitrary, and thus the choice of the kernel function is also arbitrary. Therefore, may choose the best kernel function before observe the data. However, show in Theorem 4. it suffers from a suboptimal rate. Other examples include the k-NN estimator Watson estimator. Thus our analysis gives suboptimality of not only the kernel method but also these well-known linear estimators. [Suzuki] (2018); Hayakawa & Suzuki (2020) utilized such an argument to show the superiority of deep learning but did not present any tractable optimization algorithm.
(k(x;, 2,))) E R= k(x) T E E for a kernel function k R2 Rd >
will
and the Nadaraya- Watson
3.2 STUDENT NETWORKS TRAINED BY TWO-PHASE GRADIENT DESCENT
We prepare the neural network trained through the observation data (called student), defined by
fxx;0) Σ (
1=1
where 0 = ((a), (.).... (am, Wm.) E (d++1mm = O. We assume that the student and teacher networks have the same width. Based on this formulation, we aim to train the parameter 0 that will be provably close that of the teacher network. To this end, we introduce the training algorithm, two-phase gradient descent, which we consider in this paper.
((( x²) [ x)) for any TR /R0/(0) and Rd
4

---

Published as a conference paper at ICLR 2023
Phase I: noisy gradient descent For r let == R. tanh (rlr1/2R) be clipping of where R > is a fixed constant. In the first phase, we conduct a noisy gradient descent with the weight decay regularization. The objective function used to train the student network is given as follows:
Rx(0)=
Σ -v- s(;; + Σ (as) +uu;+, 2n
1
||w;))")
where 0 is the element- clipping of 0 and À >> 0 is regularization parameter. The parameter clipping ensures the bounded objective value and smoothness of the expected risk around the origin, which will be helpful in our analysis. Then, the parameters of the student network are updated by
0(++1) = -( VR (OLM)
2n(1))
(
where 17(1) O is step-size, {c(N) k- are independently identically distributed noises from the standard normal distribution, and 3 > 0 is a constant called inverse temperature. This type of noisy gradient descent is called gradient Langevin dynamics. It is known that by letting 3 be large, can ensure that the smooth objective function will decrease. On the other hand, because of the non-smoothness of the ReLU activation, the objective function R, is also non-smooth. Hence is difficult to guarantee the small objective value. To overcome this problem, we evaluate the expected one instead in the theoretical analysis, which is given by
(0) = 10 (fa (t)
+
Σ j=1
(a,1 +lu,,]1²)
We can ensure a small (0) after a sufficient number of iterations (see Section 4.2 for the detail).
Phase II: vanilla gradient descent After phase I, we ensure that for each node of the student network, there is a node of the teacher network that is relatively close to each other. Then we move to conduct the vanilla gradient descent to estimate the parameters of the teacher more precisely. Before conducting the gradient descent, we rescale the parameters as follows:
(k) sg)(a(")), w <- (a(()) (M)
Vj E [m)]
We note this transformation does not change the output of the student network thanks to the 1- homogeneity the ReLU activation. After that, we update the parameters of the first layer by
(1+1) (()) (2 ((
where 17(2) > O is a step-size different from o and R(W) = 1 Em f(z;; 0))² In this phase, we no longer need to update the parameters of both layers. Moreover, the regularization term and the gradient noise added in phase I are also unnecessary. These simplifications of the optimization algorithm are based on the strong convexity of R(W)) around W the parameters of the teacher network. The analysis for this local convergence property is based on that of Zhang et al. evaluate the excess risk of the student network.
2n
2019), and eventually,
The overall training algorithm can be seen in Algorithm [ In summary, we characterize the role of each phase follows: in phase I, the student network explore the parameter space globally and finds the parameters that are relatively close to that teachers, and phase II, the vanilla gradient descent for the first layer outputs more precise parameters, as analyze in Section 4.2
Remark 3.1. Akiyama & Suzuki (202T) also considered the convergence of the gradient descent in for the ReLU activation while we consider the Le-reuularization given by Σm E)= + [[w,)??). These two regularizations are essentially the same since the minimum of the later regularization under the constraint of [ajl[w,ll| = const. is given by 2 2 >>= |ajlllyy| by the arithmetic -eeemetti-ggometiicc mean relation. On the other hand, Akiyama & Suzuki (2021) l) consider vanilla gradient descent instead of the noisy gradient descent. This makes difficutt to reach the local region around the optimal solution, and their analysis required an exponentially large width find the region. We may narrow network in this paper with the same width as the teacher network. This is due to the ability of the gradient Langevin dynamics to explore the entire space and find the near global optimal solution.
a teacher-student model. They considered sparse regularization, Σx= /-==|aayll [ay]]|u, for
5

---

Published as a conference paper at ICLR 2023
Algorithm Two-Phase Gradient Descent
Input: max iteration k(1) and k(2), stepsize parameter r7(), r7(2) > 0, regularization parameter
À > 0, inverse temperature 0.
1: Initialization: g Po-
2: for k 1, ........................... ,,1)) do
3:
((k) ~ (0, 1m)
4: ((++1) = g 17 (Rx + 20(1)) ((8)
5: end for
6: Reparameterization:
aj = sgn a (, 20g (4) = =1a/1/ T
7: for k k= ==) 1, + 2, 122 do
8: ((++1) (Kk)) 12 R
9: end for
4 EXCESS RISK ANALYSIS AND ITS COMPARISON
This section provides the excess risk bounds for linear estimators and the deep learning estimator (the trained student network). More precisely, we give its lower bound for linear estimators and upper bound for the student network. As consequence, it will be provided that the student network achieves a faster learning rate and less hurt from a curse of dimensionality than linear estimators.
4.1 MINIMAX LOWER BOUND FOR LINEAR ESTIMATORS
Here, we analyze the excess risk of linear estimators and introduce its lower bound. More specifi- cally, we consider the minimax excess risk over the class of linear estimators given as follows:
Rii (F))
inf sup ED. ff (l))) fe
filimeur
where the infimum is taken over all linear estimators, and the expectation is taken for the training data. This expresses the infimum of worst-case error over the class of linear estimators to estimate function class F Namely, any class of linear estimators cannot achieve faster excess risk than Rui (F=). Based on this concept, we provide our result about the excess risk bound for linear estimators. Under the definition of F by Eq. (T). we can obtain the lower bound as follows:
Theorem 4.1. For arbitrary small O, we have that
Rin 2 n 2412 m
The proof can be seen in Appendix A This theorem implies that under d 2 2, the convergence
rate of excess risk is least slower than n d + oc, the convergence rate of excess risk will be close to 1/2 in high dimensional settings, which coincides with the generalization bounds derived by the Rademacher complexity argument. Hence, we can conclude that the linear estimators suffer from the curse of dimensionality.
n 2/3 Moreover, since - 2d+2 - -1/2 as
d+2
The key strategy to show this theorem is the following "convex-hull argument" given as follows:
Pin (F)) Riin (conv (F))),
and conv is the closure of conv(.) in Lz2( (2())) ). By combining this argument with the minimax optimal rate analysis exploited Zhang et al. (2002) for linear estimators, we obtain the rate Theorem 4.1
where conv (FO) = [EN Agfa I N, 2 ,,
This equality implies that the linear estimators cannot distinguish the original class F and its convex hull conv(FF), Therefore, if the function class F is highly non-convex, then the linear estimators result in a much slower convergence rate since conv (JF) will be much larger than that of the original class _ Indeed, we can show that the convex hull of the teacher network class is considerably larger than the original function class, which causes the curse of dimensionality. For example, the mean of two teacher networks with a width m can be a network with width 2m, which shows that (F consist of much wider networks. See Appendix for more details.

---

Published as a conference paper at ICLR 2023
4.2 EXCESS RISK OF THE NEURAL NETWORKS
Here, we give an upper bound of the excess risk of the student network trained by Algorithm The main result is shown in Theorem 4.6 which states that the student network can achieve the excess risk with ).. This consequence is obtained by three-step analysis. First, (1) we provide a con- vergence guarantee for phase and phase II in Algorithm We first show that by phase I, the value of R. (8()) will be sufficiently small (see Proposition 4.3) Then, (2) can show that the param- eters of the student network and the teacher networks are close to each other by Proposition [4.4 By using the strong convexity around the parameters of the teacher network, the convergence of phase II is ensured. By combining these result, (3) we get the excess risk bound as Theorem 4.6
(1) Convergence in phase First, we provide a convergence result and theoretical strategy of the proof for phase I. Since the ReLU activation is non-smooth, the loss function Rx is also non- smooth. Therefore it is difficult to ensure the convergence of the gradient Langevin dynamics. To overcome this problem, we evaluate the value of (-)-)) instead by considering the update ((k+1)
g(k) (R (0(#)) -2
B <(8), and bound the residual due using the gradient of (A)-)-
This update can be interpreted as the discretization of the following stochastic differential equation:
df - BVR + V2dB,
where (B))22 is the standard Brownian motion in ( () It is known that this process has a unique invariant distribution Too that satisfies d= (0) exp(-6RX Intuitively, as 3 + oo, this invariant measure concentrates around the minimizer of Rx. Hence, by letting 33 sufficiently large, obtaining a near-optimal solution will be guaranteed.
dg
Such a technique for optimization guaranteed in recent works (Raginsky al. 2017 Erdogdu et al. 2018). However, as we stated above, they require a smooth objective function. Therefore we cannot use the same technique here directly. To overcome this difficulty, we evaluate the difference between VR, and VRA as follows:
Lemma 4.2. There exists a constant C > 0 such that with probability at least 5, holds that
- vRAco) S CCRmy dllog(mdn/0)
Verad= = sup (R) -
This lemma implies that with high probability, the difference between VRA and VR, will vanish as n - oc. Thanks to this lemma, we can connect the dynamics of the non-smooth objective with that of the smooth objective and import the convergence analysis developed so far in the smooth objective. In particular, we utilize the technique developed by Vempala & Wibisono (2019) (see Appendix C for more details). We should note that our result extends the existing one Vempala & Wibisono 2019) in the sense that it gives the convergence for the non non-differential objective function R. As consequence, Proposition 4.3. Let R3, be the minimum value of RR in O, q be a density function of woo (i.e., (0) x exp(=3Rx(0)) and Hy(p) Jn p(0) log q(o) constant e, C > and the log-Sobolev constant a (defined in Lemma C.4) such that with step-size 0 < (2) < ma after k(1)) 2 anpe
obtain the following convergence result for phase I.
p(0) dx be the KL-divergence. There exists
Dha
log (Po( iteration, the output (0k) satisfies
([(x(00))) - S (A+ exp(m 3) 8
d
log
m 22d
3nd
23
with probability at least 1 - 8, where the expectation is taken over the initialization and Gaussian random variables added in the algorithm.
Therefore, we can see that phase I optimization can find near optimal solution with a polynomial time complexity (with respect to n) even though the objective function is non-smooth. It also may be considered to use the gradient Langevin dynamics reach the global optimal solution by using higher B. However, it requires increasing the inverse temperature exponentially related to n and other parameters, which leads exponential computational complexity. To overcome this difficulty,

---

Published as a conference paper at ICLR 2023
utilize the local landscape of the objective function. We can show the objective function will be strongly convex around the teacher parameters and we do not need to use the gradient noise and any regularization. Indeed, we can show that the vanilla gradient descent reach the global optimal solution in phase II, as shown in the following.
(2) Convergence in phase II: Next, we prove the convergence guarantée of phase II and provide an upper bound of the excess risk. The convergence result is based on the fact that when (0) is small enough (guaranteed in Proposition 4.3), the parameters of the student network will be close to those of the teacher network, as the following proposition:
Proposition 4.4. There exists a threshold c = poly(m m such that by letting S co/ m, if c= (0) R S co, it holds that for every j E [m). there exists k- E [m] such that sgn(at,) = 0j
and |ax, wkk w/ || S cam/ m
The proof of this proposition can be seen in Appendix D We utilize the technique in Zhou et al. (202]) which give the same results to the cases when the activation is the absolute value function. In this proposition, we compare the parameters of the teacher network with the normalized student parameters. This normalization is needed because of the I-homogeneity of the ReLU activation. The inequality @k, Wi,, will S c0,n/iimm ensures the closeness of parameters in the sense of the direction and the amplitude. Combining this with the equality sgn(ax,) ) = aj, we can conclude the closeness and move to ensure the local convergence. Thanks to this closeness and local strong convexity, we can ensure the convergence in phase as follows:
Lemma 4.5. Let K == am and = [[T d,)/am Suppose that the condition is Proposi- tion 4.4 holds. Then there exists absolute constants C₁ C22 Ca. Ca. Cs such that under
cix dd
(md)
n
log
(I + 22)
Om
0m
the output of the gradient descent with stee-size 17 S ognim satisfies
a2om min m log + cal
Czll b om
IIf - 1 S
ōk²
R²3m²
n
after k iterations with probability least c5d-10
(3) Unified risk bound: By combining (1) and (2), we obtain a unified result as follows:
Theorem 4.6. There exists eo = poly(m- minn) and constants C and C' > such that for any
0 < 1, under n 2 Ao exp(or, m²) where σb == beg, let (1) -2-33-1 eexpmm? (m3 3) and 1(2) k(O) + log( (g((C'nn())-2)) then the output of Algorithm with X oad 3 = 2(0 d),
(7() O(Ag exp(o, (m)) and m/ O( satisfies
020 _2omi m logn
-4
II I' (Px) x
n
with probability at least 1 - b - d010, where δ
oy)/om m
The proof of this theorem also can be seen in Appendix the excess risk of the student networks is bounded by
D
This theorem implies that for fixed m,
Ep., Ill 1 Sn-
we get the faster rate n 11 in terms of the sample size. Moreover, the dependence of the excess risk on the dimensionality d does not appear explicitly. Therefore we can conclude that the student network less suffers from the curse of dimensionality than linear estimators. As we pointed out in the previous subsection, the convex hull argument causes the curse of dimensionality for linear estimators since they only prepare a fixed basis. On the other hand, the student network can "find" the basis of the teacher network via noisy gradient descent in phase I and eventually avoid the curse of dimensionality.
As compared to the lower bound derived for linear estimators in Theorem 4.1
8

---

Published as a conference paper at ICLR 2023
traniing crror
phase
phase jowill gradient desrent)
(nntay gradiet descent)
loss
10m²
500
:020
2000
iterations
Figure 1: Convergence of the training loss and test loss.
Remark 4.7. Akiyama & Suzuki (2021) establishes the local convergence theory for the student wider than the teacher. However, it cannot apply here since they only consider the teacher whose parameters are orthogonal to each other. (uzuki & Akiyama (2021) also showed the benefit of the neural network and showed the superiority of deep learning in teacher-student setting where the teacher has infinite width. They assume that the teacher has decaying importance; that is, the where aj S j and Wi, S j-h (with exponent a, b >> 0) for bounded smooth activation a. Our analysis does not assume the decay of importance, and the activation function is the non-differential ReLU function. Moreover, Suzuki & Akiyama (202T) considers pure gradient Langevin dynamics instead of the two-stage algorithm, which results in the exponential computational complexity in contrast to our analysis.
teacher can be written as fo -i=1 (.,((333
NUMERICAL EXPERIMENT
In this section, we conduct a numerical experiment to justify our theoretical results. We apply Algorithm 1 to the settings d
50. For the teacher network, employ aj = for 1 S s 25, a3 for 26 I S 50 and (.,,,.., w)), Iso its parameters. The parameters of the student network are initialized by g(0) ~ (((0,_m(d+) We use the sample with n = 1000 as the training data. Hyperparameters are set to () = ()) 0.01, 8 100, 0.01, x 1000 and kmax 2000. Figure shows the experimental result. The orange line represents the training loss without the regularization term. The blue line represents the test loss. Since we can compute the generalization еттоr analytically (see Appendix B). we utilize its value as the test loss.
We can see that in phase I, both the training and losses decrease first and then fall flat. At the beginning of phase II, we can observe that both the training and test losses decrease linearly. This reflects the strong convexity around the parameters of the teacher network, as we stated in the convergence guarantee of phase II. While the training loss keeps going up and down, the curve of the test loss is relatively smooth. This difference is due to the smoothness the generalization loss (or R2), which use in the convergence analysis in phase I. The test loss does not keep decreasing and converges to a constant. The existence the sample noise causes this phenomenon: even if the parameters of the student coincide with that of the teacher, its training loss will not be zero. Thus we can say that the numerical experiment is consistent with our theoretical results.
CONCLUSION
In this paper, we focus on the nonparametric regression problem, in which a true function is given by two-layer neural network with the ReLU activation, and evaluate the excess risks of linear esti- mators and neural networks trained by two-phase gradient descent. Our analysis revealed that while any linear estimator suffers from the curse of dimensionality, deep learning can avoid it and out- perform linear estimators, which include the neural tangent kernel approach, random feature model, and other kernel methods. Essentially, the non-convexity of the model induces this difference.

---

Published as a conference paper at ICLR 2023
REFERENCES
Emmanuel Abbe, Enric Boix-adsera Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning. In Advances in Neural Information Processing Systems, volume 34, pp. 26989-221 27002. Curran Associates, Inc., 2021.
Emmanuel Abbe, Enric Boix-Adsera, and Theodor Misiakiewicz. The merged-staircase property: necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. arXiv preprint 200.022002008588, 2022.
Shunta Akiyama and Taiji Suzuki. On learnability via gradient method for two-layer relu neural net- works in teacher-student setting. In Proceedings of the 38th International Conference Machine Learning, volume 139, pp. 152-162. PMLR, 2021.
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? In Advances in Neural Information Processing Systems, pp. 9017-9028, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 252.252. PMLR, 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Jimmy Ba, Murat A Erdogdu, Taiji Suzuki, Zhichao Wang, Denny Wu, and Greg Yang. High- dimensional asymptotics of feature learning: How one gradient step improves the representation. arXiv preprint arXiv:2205.014:1 2022.
Yu Bai and Jason D. Lec. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference Learning Representations, 2020. URL htttps:/
net/ wttp://rrmmmrk1lyyaaaa
D. Bakry and M. Émery. Diffusions hypercontractives. In Séminaire de Probabilités XIX 1983/84, pp. 177-206. Springer, 1985.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for ConvNet with Gaussian inputs. Proceedings of the 34th International Conference on Machine Learning, volume 70, pp. 605-614. PMLR, 2017.
T Tony Cai, Jianqing Fan, and Tiefeng Jiang. Distributions of angles in random packing on spheres. Journal of Machine Learning Research, 14:1837-1864, 2013.
Andrea Caponnetto and Ernesto De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7(3):331-368, 2007.
Minshuo Chen, Yu Bai, Jason D Lee, Tuo Zhao, Huan Wang. Caiming Xiong, and Richard
Socher. Towards understanding hicrarchical learning: Benefits of neural representa- tions. In Advances in Neural Information Processing Systems, volume 33. pp. 22134- 22145. 2020. URL ptttpsss//rroceeding....c merra. httpp/cccccapppe////111112 http://pppeeoeoooooooooeoeeoeeee
Eb64 7ww7672269366000 2tt4////66627751ebebbbeeeaaaab1
pdf
Lenaic Chizat. Sparse optimization on measures with over-parameterized gradient descent. Mathe- matical Programming, pp. 1-46, 2021.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Processing Systems, volume 31, pp. 3036-3046, 2018.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
Youngmin Cho and Lawrence Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems, volume 22, 2009.
10

---

Published as a conference paper at ICLR 2023
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685, 2019.
2019.
Murat A Erdogdu, Lester Mackey, and Ohad Shamir. Global non-convex optimization with dis- cretized diffusions. Advances in Neural Information Processing Systems 31, pp. 9671-9680, 2018.
Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborová. Dy- namics of stochastic gradient descent for two-layer neural networks in the teacher-student setup. In Advances in Neural Information Processing Systems, pp. 6981-6991, 2019.
Satoshi Hayakawa and Taiji Suzuki. On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces. Neural Networks, 123:343-361, 2020.
Richard Holley and Daniel W Stroock. Logarithmic sobolev inequalities and stochastic ising models. Journal of Statistical Physics, 46: 16:1159-1111 1194, 1987.
Kaitong Hu, Zhenjie Ren, David Siska, and Lukasz Szpruch. Mcan-field langevin dynamics and energy landscape of neural networks, arXiv preprint arXiv: 1et..-9759.77, 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in Neural Information Processing Systems, pp. 8571- - 8580, 2018.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In Advances in Neural Information Processing Systems, pp. 6389-6399, 2018.
Yuanzhi Li, Tengyu Ma, and Hongyang R. Zhang. Learning pver-parametrized two-layer neural networks beyond NTK. In Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 2613-2682. PMLR, 2020.
Song Mei, Yu Bai, and Andrea Montanari. The landscape of empirical risk for nonconvex losses. The Annals of Statistics, 46(6A))2747-2777, 2018a. ISSN 00905364, 21688966.
Song Mei, Andrea Montanari, and Phan Nguyen. A mean field view of the landscape two- layer neural networks. Proceedings of the National Academy of Sciences, 115(33):E76655-7777,, 2018b.
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pp. 2388- 2464. PMLR, 2019.
Phan-Minh Nguyen. Analysis of feature learning in weight-tied autoencoders via the mean field lens. arXiv preprint 1=x.x:2/022083/7 2021.
Atsushi Nitanda and Taiji Suzuki. Stochastic particle gradient descent for infinite ensembles. arXiv preprint weXiv:171..05A. 2017.
Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Particle dual averaging: Optimization of mean field neural networks with global convergence rate analysis. In Advances in Neural Information Processing Systems, volume 34. Curran Associates, Inc., 2021a. appear.
Atsushi Nitanda, Denny Wu, and Taiji Suzuki. Particle dual averaging: Optimization of mean field neural network with global convergence rate analysis. Advances in Neural Information Processing Systems, 34, 2021b.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pp- 1674-1703. PMLR, 2017.
Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. Classifying high- dimensional gaussian mixtures: Where kemel methods fail and neural networks succeed. In International Conference Machine Learning, pp. 8936-8947, PMLR, 2021.

---

Published as a conference paper at ICLR 2023
Itay Safran and Ohad Shamir. Spurious local minima common in two-layer ReLU neural net- works. In International Conference on Machine Learning, pp. 4433-4444444 4441. PMLR, 2018.
Itay M Safran, Gilad Yehudai, and Ohad Shamir. The effects of mild paraamatmtttinnnnoonnn on the optimization landscape of shallow relu neural networks. In Conference on Learning Theory, pp. 3889-3934. PMLR, 2021.
Johannes Schmidt-Hieber Nonparametric regression using deep neural networks with ReLU acti- vation function. The Annals of Statistics,, 48(4):1875-1897 2020.
Taiji Suzuki. Adaptivity of deep relu network for learning besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. In International Conference Learning Representa- tions, 2018.
Taiji Suzuki and Shunta Akiyama. Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority kernel methods. In International Conference on Learning Representations, 2021.
Taiji Suzuki and Atsushi Nitanda. Deep learning is adaptive to intrinsic dimensionality of model smoothness in anisotropic Besov space. Advances in Neural Information Processing Systems, volume 34, pp. 3609-3621, 2021.
Yuandong Tian. An analytical formula of population gradient for two-layered ReLU network and its applications convergence and critical point analysis. Proceedings of the 34th International Conference Machine Learning, volume 70, pp. 3404-3413, 2017.
Yuandong Tian. Student specialization in deep rectified networks with finite width and input dimen- sion. In Proceedings of the 37th International Conference on Machine Learning, volume 119, pp. 9470-9480. PMLR, 2020.
Belinda Tzen and Maxim Raginsky. A mean-field theory of lazy training in two-layer neu- ral nets: entropic regularization and controlled McKean-Vlasse dynamics. arXiv preprint DrXiv:2002.01987 2020.
Santosh Vempala and Andre Wibisono. Rapid convergence of the unadjusted langevin algorithm: Isoperimetry suffices. Advances in neural information processing systems, 32:8094-8106, 2019.
Martin J. Wainwright. High-Dimensional Statisties: A Asymmstypoooiic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/ 9781 108627771.
Weinan, Chao Ma, and Lei Wu. comparative analysis of optimization and generalization prop- crties of two-layer neural network and random feature models under gradient descent dynamics. Science China Mathematics, pp. 1-24. 2020.
Gilad Yehudai and Ohad Shamir. Learning a single neuron with gradient methods. In Proceedings of the 33rd Conference Learning Theory, volume 125, pp. 3756-3786, 2020.
Shuanglin Zhang, Man- Yu Wong, and Zhongguo Zheng. Wavelet threshold estimation of regres- sion function with random design. Journal of multivariate analysis, 80(2))256-288 2002.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-layer relu networks via gradient descent. In Proceedings of Machine Learning Research, volume 89, pp. 1524-1534. PMLR, 2019.
Kai Zhong, Zhao Song, Prateek Jain, Peter L Bartlett, and Inderjit S Dhillon. Recovery guaran- tees for wo--hhdde--lyeee neural networks. In International conference on machine learning, pp- 4140-4149, PMLR, 2017.
Mo Zhou, Rong Ge, and Chi Jin. A local convergence theory for mildly wer-parametrrized two- layer neural network. Conference on Learning Theory, pp. 4577-4632. PMLR, 2021.
Difan Zou, Yuan Cao. Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over- parameterized deep ReLU networks. Machine Learning, 109 2020.
12

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREM 4.1
First, we introduce the formal statement of the "convex hull argmunent" we stated in Section 4.1
Proposition A.I (Hayakawa & Suzuki (2020)). The minimax optimal rate of linear estimators on larget function class F is the same as that on the corvex hull of F
Riin (F²) = Rlnn (conv (F))),
where c)nv(F")= = {E A IN NNNNNEE 2, O.E = 13 and conv(.) is the closure of conv(.) in (Px)
For the proof, we use this convex hull argument and the minimax optimal rate analysis for linear estimators developed by ZZhang al. (202). They essentially showed the following statement in their Theorem 1. Note that they consider the class of linear estimators on the Euclidean space, but we can apply the same argument for the class of linear estimators on Sd-1
Proposition A.2 (Theorem 1 of al. (2002). Let μ be uniform measure on Sd-1 satisfying = 1. Suppose that the space 52 has even partition A such that |A| = 2 for an integer K E N, each A A has measure a12 S μ(A) S a:2 for constants 0₁, 02 O, and A is indeed partition of S2, i.e., UAEAA = Ω A n A' 0 for A, A' E A and A + A'. Then, if K chosen as n -1 2- <n> for constants 71. 72 that are independent of n, then there exists an event & such that, for constant C' > O.
P(E) 2 1 - o(1) and (I xh E A (1.....,)))) ,))H S C'a222 (A E E).
Moreover, suppose that, for class F of functions Ω there exists A following conditions:
0 that satisfies the
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 ((E)) < C" K' for any 9 E F on the event E.
Then, there exists constant F1 such that at least one of the following inequalities holds:
F2
2
I Pün (F*),
4F C
n
F3
2 K
< R (F))
32
for sufficiently large n. Lemma A.3. Let < A S 1/2 and let g gd-1 R be a function defined by
d
g(0) d
Σ
(2,)
+
2 (z, +2A x1) -
1
1 _0(2, 24 x1)
j=2
Then it holds that g(x) 2 f/r x E (e) and g(x) = 0 for a & B (e)). where e₁ =
(1,0,...., 0) gd-1 and (e)) = f gd-1 || - - S r) for r > 0.
Proof. Let - -0(x)) t + 24 21
20(1, - 2A .1) First suppose that B
Then, we have F1 2 1 and وzح < for any E (
.d. 1 2 < A, it holds that
(=(x)= = (x;;) + 2 0 24 2
24 m1) (2A -1 xッ A(1 0
A.
2
Moreover, if - < x < 0, we get
g,(x)= = -0 + / (a, + 2A 11) + o 24 x1)) =1)= 1 (a,
(0, +2 +) A(1 A(1-))2 2
Hence, we get the first assertion by g(x) 2 Σ} A.
13

---

Published as a conference paper at ICLR 2023
Next suppose B2 (e1). Then, it holds that.r, 2 2A > 2Av for any j {2, ..... d]. Hence
it holds that |2//=1| | 2 2A, and we obtain that sgn(2, + +2 =11 s2) = sgm(r; - 22 x1) E {+1}. We check gj (z) 0 for each case, and hence it holds that g(z) 0. Thus get the second assertion.
proof of Theorem 4.7 Let consider the covering of S by spherical caps, i... (x) n nS-1 for some æ E S with radius r satisfying r (0, 1). It is known that there is covering A with |A| ~ r- (ignoring logarithm terms). Then, by letting r 2 K/d, there exists a covering A satisfying [A] 2
For each A .A, we define function 9A by the same manner as in Lemma A.3 i.c., for A A written by (xA gi-1 with FA S we consider the orthogonal basis including TA and define DΛ with regrading 4A as e1- Define F == {9A/2 A E A). is not difficult to check that Fà E (F). Then by Proposition A.1 it holds that
Bin (F)) Rain (conv (F") Rii (F));
where the inequality follows from Ft E conv Hence, it suffices to give the lower bound for the right hand side. Now, we apply Proposition A.2 with F = F and K = K', Applying Lemma A.3 with A = 2- -/dd In the event & which we introduce in Proposition A.2 there exists constant C" such that Kz Iy A [I....,n]] n.)) S C'agn2 for all A E A. Therefore, obtain that
ga(x,)² < -22 K A 2 2- A²
Therefore, Proposition we get the assertion.
A.2 gives Rin (F)) min 2 2- (1+42//)) By letting 2 d/2((411)
B EXPLICIT FORM OF THE OBJECTIVE FUNCTION AND ITS GRADIENT
In this section, derive the explicit form of R-(-) (.) and its gradient, which utilize in analysis (especially that of the convergence in phase l). First, for w. v E (O), we have that
E Ex Nempxlo((w,,, (o) B ((,, x))]
sin plw, u) + (π o(w, u)) cos d(w, v)
| |
(2)
2nd
where ((w,e) v) = arccos((1s) v)/l[//]]el]l The second equality follows from E,- 1a [|) and
sin o(w, v) + (a o(w, u)) cos d(w, v) |
Ba- x) ()((((=)))))))))))))))
2T
(see Cho & Saul 22099 Safran & Shamir (2018)) Moreover, the first equality follows from that fact that for ă (0, Ia). 2 == | and ø |/||ž|| are random variables that independently follow the Chi-squared distribution and the uniform distribution on Sd-1 respectively, and therefore,
= Ej 112 ( (()
Ex-xy lo((w, x)) EE 11
By using Eq. get
(0) = En (x) + 2l1012
=
Ex
Σ
T,a I(w,, wz)) + Σ
agay [wu (7)) + 2110112
2
1
14

---

which is the gradient of [wx, v) with respect to (see Brutzkus & Globerson (2017) Safran & Published as a conference paper at ICLR 2023
where ö is the element- clipping of w R and
T(w, v) sin @(u,, v) + (л H(w, v)) cos o(w,
1/ ||||
2nd
Next, we move to derive the gradient of (A(-)) Note that dr = |r|/cosh (rlr1/2R). Then, since (rl/cosh(rr////2)) e" + ter 2 2 + |r] for E IR, we have that cosh(r|r|/2RR) 2 + //24 and hence di S (1R+ S minfrr). 16R2 (ep2211//))) < 4R. Moreover, through a straightforward calculation, we can show that is 1-Lipschitz (in other words, the mapping r + f 1-smooth).
Using this, each component of the gradient of (-(-) can be written as follows:
dā
m a. wg)) da,
dā
V a, (x)
Σ a,I ( (w,, mz)) daj
+ 2λa
(3)
dwig
dwy
V mx Rx(0) = Σ d,a J W w))
Ty [ ii 1z o dwy
+ 2Xwg,
(4)
dwy
where denotes the Hadamard product and
Jww v) || ||||||||| sin ob (w, v)w + (x (ww, v))v
2nd
Shamir (2018))
C PROOF OF PROPOSITION 4.3
This section provides the convergence guarantee for phase I. Our objective is to give the proof of Proposition 4.3 To this end, we first introduce the theory around the gradient Langevin dynamics exploited Vempala & Wibisono (2019).
C.I A BRIEF NOTE ON THE GRADIENT LANGEVIN DYNAMICS
In their analysis, the following notion of the log-Sobolev inequality plays the essential role, which defined as follows:
Definition C.1. probability distribution with a density function q satisfies the log-Sobolev in- equality (LSI) if there exists constant a >> 0 such that for all smooth function g. it holds that
2 Eg 19
Eglo² log 9²1 E.y ( log 1
called a log-Sobolev constant.
It is known that the LSI is equivalent to the following inequality:
(p) S _ (Vp P),
(5)
20x
where H₂(p) = Jg p00 log p(0] do is the KL divergence, (v()) = JR v(0) v log p(0) q(P)
d0 is the
((0)
relative Fisher information, and P is the set of all probability density functions.
Now we consider the sampling from the probability distribution & over Rdd, We assume that loo q(-) Ed + R differentiable. One of the well-known and promising approaches is up- dating the parameter ((0) sampled from an initial distribution Po as follows:
0(k+1) ((k) 1)
()(k)) + (*)
(6)
is constant and (k) (0 La) an independent standard Gaussian random variable. Vempala & Wibisono 2019) shows that if the LSI holds and - log y has a smoothness, the sufficient number of updates actually achieves the sampling from q. in sense that the KL divergence between the distribution of ((k) and q will be small.
where 77
15

---

Published as a conference paper at ICLR 2023
Theorem C.2 (1 Vempala & Wibisono 2019 Theorem 1)). Suppose that probability measure with density function 4 satisfies the LSI and log is T-smooth. Then for any ((0) Po with (Po))).
the sequence (0(k)) with step-size 0 < n 21. satisfies
SndL2
Hg(pt) S exp(-onk))
a
Hence for any 8 > O, the oulput of the update
6
with step-size v S TZ min ( achieves
Hg(pi) < 8 after k 2 on log 2Ha(pe) iterations.
L
C.2 PROOF OF LEMMA
The goal of this section is to prove Proposition 4.3 the convergence of gradient Langevin dynamics. As stated in Section 4.2 consider the value of R-(-) instead of R2(.), and ensure its value will decrease enough. To this end, we first prove Lemma 4.2 which evaluates the difference between (-)(+) and (-).
proof of Lemma 4.2 The proof of Lemma 4.2 basically based on that of Theorem 1 Mei et al. (2018a) and Lemma 5.3 in ZZhang et al. (2019). For the notational simplicity we denote m(d + 1) = D. Let Ne be the e-covering number of B (D. with respect to the b2- distance. Let θ, = (0.....;xx) be corresponding e-cover with |o, = N. It known that log N = -loog (3VDR/c) is sufficient to ensure the existence of such covering.
First we note that (R) (R) 1 Σn Ve(yi, (x;; 0)) VEil(y. (a;; 0))] For each E O, let j(0) E arg min 0,1l and sco)). For E (,,, we consider the JE[N]
following decomposition:
((;;;))0;))) VE(((,,(0;00)
Vlly, ((;;; 0)) Ve f(;; 01)
Vlly,, f(z;; - fx;
7
VE[E(y.f(x; (
This gives that
[(,,, VE(e(,, <
1
Velu, ((;; ((y,, θ1)
Vel,, - f(x;),
VE(((u.f(=;00) VE(
16

---

Published as a conference paper at ICLR 2023
and hence it holds that
P
sup
V Velui, ()z;0)) VIEl((, ((x;)))>-VV(((,((((000)) 2t)
(b.(D.)
s P
sup (EB(O.V
Ve(y. - V
n
+ P
sup
V Eyr, (101
2
(OB(D.
(II)
+ P
sup (oB
2
(m))
for any t > 0. Then evaluate the each term of the RHS.
Upper bound on (I): Since Vi(yi, [(x;; 0)) ([(())))) yt) V 0), holds that
Vily,, f(a;;; 0)) - Ve(y,, f(z;;; 0))
=2 =f - f(r;; - (. vV((((( vz(=;00)
Therefore, have that
Vi(yn, f(x;0)) - 2
sup (CB(O.VDR)
2
(1a=;0) (z:; V
S P
sup (EB(O,vDM)
2
(V)(() - v[(=;0) (
+ P
sup (D.)D))
2
(EB
Since the mapping that the first term must be zero as long as 2 cmR As for the second term, since [f; 0) yel S mit + U + for any Hi. Vi and 0 E O, it holds that
+ fx; 0) is 2i-ssccciitz and f=x;;
< 2mR for any 0 E θ, holds
(T) =
sup
(f(x;:) (V(((()))))) V)(xx))) [)]
26
(EB(D,,DR))
12
2
V Vs(z; 0) [[<s
t E V[(z vs(as:)) To this end, we con-
S P
sup (EB(D.DDR)
2
6(mR2+U++) + +U+++
n
Hence, we move to evaluate
sup BB (U.VDD
sider the decomposition
2
(Ix: 0) v)(
n
Σ
m
2
V a, (2 0) - Voy [)] +
V Way f(x;; 0) - Vn,, J von]((os)))] ))
17

---

Published as a conference paper at ICLR 2023
where
dā, daj"
V Ve, fa,;))) - a, (i,, 2z) 2 0]2; O dūj
Vay f( = ((09 xx)) =
dwj
This decomposition implies that
(1) < P
max
sup
V (1
V Voz Vo,
2
t 12m(mRR U +1)
JE[m]8 E (D.DR)
2
t
+ P
max je|ml] EB (D)
sup
V w (zz;:0) Vw, (w,
2 12m(m U +
For each term, it holds that
dā
dāj dā- day
Va, ( Vaz Jaz[(r=
5
(o (1(0)) o (1ūة
a ((10g,
da-
day
dā da,
dā
dā-
S ||00 r
da,
day
I 4R rHyll + 2/āz إزة S 4 +
and
dwy
Vu, (x1;)) - Vw, f(z S (1( x.) 2 0} - 1((0g x.) 2 0f)xz O
dwy
dwy
+
(āg - ) 25) 2 032; O
dwy
dro
dwi
+
01 (1(((10) 21) 2 03.; 3
duy
dw,
dw
R
(1) 2 0} ( x;) 2 0})zz
dwy
+4Rllā, اارة 4 -,,1
(I(((ū) xx) 2 0) [1((ú,, m;) 2 0})az 3 dw
< R
+ &Re.
dmy
The first term can be bounded by
dũj dw,
(I 210 2 0} (((1)) 2x) 2 0))x, 3
s [I( 2 0} ((b0), 2 03) ||,y
S 11 x1) S t} ||
where the last inequality follows from (ūū,, v.) - (10,. m3)l s 10 - الرنة | S c. Therefore, we obtain that
# E [n]] K1, S {e} -|00
(I) S max sup (e)
n
24mR(m + U +1)
#lie [n] Kwy,, 2i)1 $ {e} ||00
P
max [E
n
24mR(mR2 + + 1)
as long as 24m Ri m R3 +0+1) maxf4Re, c, 8Rc] 8Rc. We have that
# fiE [n]] 110 < c) ||0يا|
P
24m R m R + U + +1)
# E [n] (10 x.8il <c} P
24mR(mR2 + + 1)
18

---

Published as a conference paper at ICLR 2023
when tū * O. If ú 0, the LHS must be long as t 0. Lemma 12 in Cai et al. (2013)
shows that for each j and i, the angle between diy and 2; is distributed with density function
h(0) = 1 r(#)
V (sin o)
E 10.
r(1) for
Since 1 of I A implies |cos Φ1 any Φ E [0, r.. it holds that
sin
Φ) S A for any A > and h(0) - v= (
π (( 5e) S P
des
2e
S de
2
|00
|00
where Oiy is the angle between wi and Tz. Therefore, #(i E [n] ((ūg, - c} follows the Binomial distribution (n, p) with p S *
Since random variables that follows the Binomial distribution is bounded and especially sub-Gaussian Wainwright (2019) it holds that
2/de
i E [n] x1)) S e 2 2
2vde
# {i E
[n] K10,, s Sc
P
< P
+ p)
I exp( 2ms
for arbitrarily By taking uniform bound, we obtain that
#lie [n]]
K20 x.)) {
2vde V=||ū;]|
P max fm
+
S
V Hence, as long as Rm +U +1)2vd (verified later in this proof), by letting
48m R(m R Mill we obtain that
#liE [n] (10 r.)] Se
de
P max
jEim
n
S mNN exp
-2n 24mR(mml + 1)]1(00
2n
t
$ mn exp
dR2
2AmR(mRR +U +1)
where the last inequality follows from
|| S dRR.. As result, the term (I) can be bounded by
2n dRe
2
(L) S mN exp
2AmR(mIi +U +U +
Upper bound on (II): First, we observe that the term (II) is equivalent to
2 4
P
max JE(N
Σ
f( VE((W, ((;;))
For each E [N]. straightforward calculation gives that [[V[( f(;; f,))il < 2R(m + 1), and hence the vector Vl(u, (ax;; is sub-Gaussian with a parameter R(mit + 1), i.e., holds that
f f(;;0,)) - 5((e(y.((x;0,))
< 2e
1862
n2a
3
with G R(mRi 1) for arbitrary t 0. By taking uniform bound, obtain
max jEIN n
fly, VE((yy (x)1
M 3
< 2Ne 1862
19

---

Published as a conference paper at ICLR 2023
Upper bound (III:: The goal is obtaining (III) 0 for sufficiently small Particularly, assume that e < here. To this end, we aim to show
VEle(y, fz; ((::))]] s cL'e
(7)
with a constant e > 0 and = (m² (mmm2²)) R²). First we consider the case where the absolute value of the each component in 0 is bounded by 1/2. By Lemma C.5 it holds that
VIE [illyy, fx;; ((( - T/ Osc0)|l = T/ (10-
for any E with Om=² Moreover, a straightforward calculation shows that mapping r > 2/ tanh ( R) (the inverse mapping of + R (tanh(r/2R)) is 8-Lipschitz in [0, 1/2]. we
have |10 ,1) lI - 8|10 0| = Se. Therefore, we obtain that
|>>l| z ('(
i... Eq. 7 with 8. Assume that there is component of 9 whose absolute value is greater than 1/2. First, suppose that component of ú is greater than 1/2 for E [m]. We consider the decomposition
V. B(l(y, V ,, Blely, f(z; 0))l|
dũ dæ;
V a Biely, f(x;0))] V Biy(y, f(z; 0))1
+
EE E[l(y, fzz 0))l
dwy
dw, dw;
Since || 1/2, we can check that the mapping di E El((y. f(x 0) is I." smooth
with L" O(mR2dd-1/2) according to its Hessian (see Safran & Shamir (2018) Since
day dany
S 4vdR, the first term is at most O(RR²) c. Since [B[E(y, fa; 0) I 2R(mR +
1) and r + is 1-smooth, the second term is at most ((mR3) c. Hence we get that Wwy B(e(v, f(; f(=; (x:: O(mRR) In the case layl 1/2 for j E [m], the same bound also holds with Va, E[[ (z;; Ve, ElKyy f(r; 0)1| By using these bound instead of Lemma E.5 and 1, we obtain the same bound Eq. in this case. Eq. 7 implies (III) = 0 as long as 1/2, which gives the assertion.
V.,, f
V
Combining (I-(III): Combining these bounds, we get that
P
sup (EB(D.VDR)
Vln, (V(())))-E((( 0))] 21
dR2 2AmR(mRP ) 2Ne 1867
2n
2
< m. exp
+0
3VDR
=exp
D Doog
e
2n
24mR + + 1) +1)) 2)
) + exp (- (
nt
m exp
d.²2
1882(mRt)
+ 1)2
as long as 2 Co max(mll's mR(mmt2 + U),, L'e holds with a constant Co > 0. By letting t = 1/2 and e = C2 dling with constants C > 0 and C2 > 0, we obtain the conclusion.
nm
C.3 PROOF OF THE CONVERGENCE IN PHASE
Based on the results so far, we move the proof of Proposition 4.3 The proof is conducted in two- step. First, evaluate the "distance" between the कo and the distribution of (Kk) Moreover, it is
20

---

Published as a conference paper at ICLR 2023
ensured that the function value R2) where is sampled from Too will be small for sufficiently large B. Combining these two facts, small, which concludes Proposition 4.3 The following proposition ensures the convergence of the marginal distribution of ((k) to the invariant measure Too:
guarantee that the function value Rx (o(k)) also will be
Proposition C.3. Suppose that the probability measure Toe satisfies the LSI with a constant a and R-(()) is L-smooth with L >> 1. Let be a density function of Toe (i.e., g(0) x exp(-8Rx(0)) with 3 > 2. For any ((0) Po with Hp() < +00, the sequence (8(8)) k== with step-size 0 < 17
4312 satisfies
Hg(ps) S exp (oxp--o"
an/"1 k: Hyp 163rr
323V2
grad
30
where == mm 1), ps is the density function of the marginal distribution of g(k), and Vgrad is
constant introduced in Lemma 4.2 In particular, for any 6 >> 0, the output of phase I with step-size 77(1
5a 328L2D
achieves Hy(ps)
5
328V
poud after k 2 anl log
(M,(Pa) iterations.
3a
As we stated in Section 4.2 our result extends the existing one Vempala & Wibisono 2019) in the sense that it gives the convergence for the non-differential objective function Rx Indeed, this
difference appears in the last term, 328V graed
3a Since V2 grad S n by Lemma 4.2 we can ensure that this error diverges to zero as the sample size n increases. To apply this result to ensure the convergence of the phase and RA is smooth, and we clarify them as follows:
just need to check that the invariant measure Too satisfies the LSI
Lemma C.4 (log-Sobolev inequality). The invariant measure Too satisfies the LSI with a constant 2,3 (xp(-83mmRR)
Lemma C.S (smoothness). Rx(-) is I-smooth, i.e., for any 0, 0' E.. - || LI|0 0'| holds with L = Omm² 2 R + A).
The proof of these lemmas can be seen in Appendix
Remark C.6. In Lemma C.4 the LSI constant a depends exponentially on m, which results in the exponential dependency of phase I convergence on m. This is caused by the fact that the sup-norm of the student network depends on m (see the proof of Lemma (C.4). Therefore, we can indeed remove this dependency by considering the following settings: (1) utilizing the mean field network (multiplying 1/m to the output of the student), (2) wys are directed to different directions to some extent, and hence the sup-norm can be bounded.
To ensure Proposition C3.3 first show the following lemma, which evaluates the each step of the gradient Langevin dynamics.
Lemma C.7. Suppose that tos satisfies the LSI with a constant a and R2x,)) is L-smooth with > 1, and B > 2. Then for any g(0) ~ Po with Hy(Po) < +00, if0 < n 1312, it holds that
Hg(pw+1) S S (p())) + 12.2 V grad:
where is the density function of the marginal distribution of ((t) and Vgrod is the constant defined in Lemma 4.2
Proof. The proof of Lemma C.7 is basically based on that of Lemma in Vempala Wibisono
2019). For notational simplicity suppose i and let 0g g The one step of the gradient Langevin dynamics
((1) ((0) R (100)
2n (0)
can be seen as an output at time n/3 the following SDE:
dd;- RV)x(00) + v2dB,
21

---

Published as a conference paper at ICLR 2023
where {Brhso is the standard Brownian motion in θ (= R((++))m). As Vempala & Wibisono 2019), it holds that
(0,10) V (210000100)3372266)) + +ppro(0)loo)
Ot
and therefore,
d dt Hg(px) = -g(pr) + B. [(VRA10)) - -VR. V log Pc(O)) )
(00),,
((o.)
where pqo(-10o) the conditional density, and Pro is the density of the joint distribution of On and O..
Then we evaluate the second term. The inner product in this term can be bounded by
pr(O)) - (RA(0.) - (00) || (0.))
2 1
log (o() (0,)
(RA(0,) (R)( V log
V
4
s (0.) - (RA
+ PR - (0)
1
1 log (c))
2
((o,)
In the above bound, we use b) < a² b2/4 for a, b E RR in the first inequality and ||a bl12 < 2
2||a||2 + 2 1b|2 for o, b E RD in the second inequality. Therefore, by using Lemma 4.2
we get that
( (R.) (O)(),); V log (0,))
(b.)
E Eo
(c() 12 (
S 2V grad + 2E poi
(0+) (RA(
+ Ep
1
Vlog
= 2V2 grad" + plE
(O.) (OA(
+ 4
1 Jc(o))
Then the second term is bounded by
Epoc
(R)(01) - VRX(06)
|9
< I. T. pos
|10e [101-]
2T
= E.
-iVRx(00) + V 3 c(0)
= =. Poi
VRA(Ob) + (VR) (R)
21 110)
T Pos
< 21.2 (BPoo)
Epoc
[VR2(0))11] + -Vorad)
+ 1,2 D
B
1
T,1
a HP(Po) + 212 + 217² 2 T, 1,2 Vraa + tI D.
$ 3
In the last inequality, we use Lemma 10 in Vempala & Wibisono (019) and | >> 2. Thus we obtain d dt Ho(p)) s - [g(p)) + 8 L
3
a Hg(P)) + 43t L 23tL + (2,87 L2 + 2)V grad
3a
L4
< -ー 2
Hg(pt) +
(p)))) + 6,3t + 43v2 grad
a
since the LSI (Eq.
(5) holds and tL < nL < 1. Multiplying both sides by 230//2 and integrating
them from = -o n1-11 we get
2( Jan/28 - 1)
LB H2(m)) + 6,n + 43V2 grad
e 30n/28 (emn/2HHH(p) Hg(p)) - Hg(po) <
30
1
27
a Hg(Po) DT, + 4V2 ggrdd)
22

---

Published as a conference paper at ICLR 2023
where use the inequality c" I 2a for E [0, and 3an/28 Σ 1 (derived from the assumption of 17). Rearranging this inequality, we have
1 1 (Pg te- 23-3/222 (121) DL2 + 8V gradd)
(p) S -an/28
a
Se S H (P() + 12n2 DL + 8n
grad:
where the last inequality follows from + 1 S po by Ph and pn by pk+1, we get the conclusion.
163
1
+
on 23
S e2//20 By replacing
proof of Proposition C.3
C.7 holds that By Lemma
Hp(ps) Se- -onk// (P)) + (12n)² DI.2
811 grad
k==1
Se a Hg(P)) +
12n DL2 V
grad
eank/ Hg(P)) + 163mDL2
32 grad
- e
3a
where, the last incquality follows from L > (derived from Lemma C.5 and 1 - c j for E [0, +] and
T
T. Thus get the assertion.
proof of Proposition 4.3 By the Villlnilami theorem, it holds that W2(ps, q)² S 3 H.pp)) There-
fore, Proposition C.3 implies that after ls 2 on
A log (00 iteration, it holds that
2
325V?
grad
W2(px, 9) S
8 +
3a
Then we obtain that
[[ - R S (E(Rx - -Ey [R)())) + (TR [Rx(0)] R3))
C(A+ + m)
8 2
2
32 2
grad
D
log
eT.
+ 1))
3a
23
M
where Lemma
E.1 and Lemma
E.2 for the inequality. By specifying a, L, M and by we get the conslusion.
applying Lemma C.4
Lemma
C.5 and Lemma
E.3
D PROOF OF THEOREM 4.6
The objective of this section is to prove Theorem 4.6 First, by the noisy gradient descent, the objective value decreases enough, and we ensure that for each node of the teacher network, there exists a node the student network that "close" to each other. Then we can prove the local convergence property based on the strong convexity around the parameters of the teacher network.
The proof of the local convergence relies on that of Zhang et al. (2019). They consider the setting where the parameters of the second layer are all positive, i.e., aj af for all j [m]] and provide the following proposition:
be a teacher network with parameters W = (wi w w IRdxm, == a1/am is the condition number of W and (I] o,)//"/) Assume the inputs (x.) are sampled from ( Ia), and the outputs (y))_1 generated from the teacher network. Suppose that the initial estimator (()) satisfies ||(00] - l com/n' mm? where 0 is small enough absolute constant. Then there exists absolute constants Ct. C2. C3. Cs. and 6s such that under
Proposition D.1 (Theorem 4.2 of Zhang et al. 2019 Let fo: : 1 E ((u), x))
11x log
(mnd)
(I 11 + v²),
om
6m
23

---

Published as a conference paper at ICLR 2023
the output of the gradient descent with step-size 17 cgkin satisfies
[| - 1 - (1
c37
|| - 1| + c202 m f dlog (1 + x²)
xx²
with probability at least 1 cgd-10
Their proof can also be applied to the setting in this paper, i... aj, ag {+1] holds, and if teacher node j and a student node ky are close to each other, it holds that aj ak₁- In Proposition 4.3 if it
holds that ( R3 beu. we obtain that
(2(0(()) R3 <0
(8)
with probability at least b, by using the Markov inequality. In the rest of this section, we assume that (8) is satisfied. In this case, if Proposition [.4 is ensured, we can apply Proposition D.I and Theorem 4.6 proved. We give its proof in the rest of this section.
proof of Proposition 4.4 Let 0"
wfaj,
..... (a w)))).
Then by Rx) - Rx(00) s
(0) - R2 S Ev. it holds that
m
2 Fr (J S [(;; (1) +
|as1 + ||000 12) S 1
|ag1 + -110031²) + c0:
and therefore,
Eg (o)) - f(;; (x: 2
6D Σ
lag12 + ||m||1 + +co
1
j=1
cu
[1 + W (1/) + ED S 3E0
(9)
where we use laz1² = 1 for all j E [m] and Σラ= ||0 11 | S ml|lVo S m. Then
move evaluate the LHS. Since (u) utlul for R, holds that
f(x;0) ajo (w0 x)) 2
Σ
Σ
a ()((,,))))) + 2)),
j=1
Σ ( x))
1
Σ
m
aj <1tr (10f.x))
2
==1
Hence we have that
[Jar,,w f (=== [1;
2 Ex
Σ a (1(0) 12)| + (w]f Σ
a (((1),,))) + (w)
1 Ex
Σ
Kw] xn|l - Σ a, (ul sill
- Ex
az
0 Wi x
8
where the last equality follows from E, (ll x)) (wg, x>) 0 for all w1, We Rd which follows from the fact that the distribution Px is symmetric. Then Eq. 9 gives that
27
m
m Σ
Ex
Σ
(uf,
a (ulK,, j=1
24c
(10)
27
F
Σ
Σ
aj W
<
24ca-
(11)
j=1
24

---

Published as a conference paper at ICLR 2023
The analysis based on Eq. (TO), the error analysis of student networks with the absolute value activation, is conducted in Zhou et al. (202T). Here we import Lemma D22 from their tech- nique. They focus on the setting where aj 1 for all j E [ml) but
apply it here.
Then get that for every j [m], there exists kj E [m]] and constant C > 0 such that 5/3 2/3 and ||| wky will s poly(m, m/in)
arccos((uu,, wx>) w//e// [I) I Cmm min
-5/3
We simply denote k, by j. Since Zhou et al. (2021) uses the absolute value for the activation, may hold that arccos ( (wof, wy///llu II wg II) >> 7/2 (i.e, wz and we have "opposite" directions). From now on, omit such cases by Eq. (TI). Let (a1,...? am) (ai:-... ..amm and WA (wf Wi..... wn wm). And we denote the angle between wi and wy by Øj. Then, Eq. (11) can be rewritten as
Ex Px [ Waz) 24ca.
Let ã ~ (0, Ta), since x2 == || and Φ == -/||=||||| are random variables that independently follow the Chi-squared distribution and the uniform distribution on g0-1 respectively. Hence holds that
Ex Px ((a WA EB-W(0,L [ WA
E (1.. [r2]] (a, WaYl?
d I 24c0-
E5-N((,,))) ||11
d
This implies (a, 2 & 240gd. Since w3 wj = (1 - (wj. wzy) wF + [twf. wyyw - w,) and Kww. wy)oo will = sin Hj. we have that
(a, Wa) - (wi, w2) w2))a,,.... (1 (win wm) )am))mm Wo
+ (a, Wa) ((1- (wi,, w w1))ai (a.........................."a.. (win Wm) )mm) T wo
= =(11 (w,,
(w Wim) )am wo
+ ( a, (ww ui ) wT: (w Wm) w wm))
and the second term is at most O - 5/3 2//3). As for the first term, it holds that it is least min
mmin Σ}=(( (1 - (wrg, w2 Hence, by letting e = o(d m 1mm-3/2, 3/2 it must hold that (wf, wy) > which gives the assertion.
Lemma D.2 (Lemma 9 and Lemma 10 in Zhou et al. m Kw], æ>) is a teacher network with parameters wi.-.., .......10 w.. E RRd satisfying Wmax for all e such that if a student network F:x Σi= kw,,, x²) satisfies - 2 < S en, it holds that for every E [m], there exists ky [m] and a constant C' Ouch that arccos (1 (I(w5, ww>>//|ww5 [Illwxl)) S Cru w. w
2021 Assume that x NN(0,T) Ia) and
f : x +
min arccos (wwf, / [[ IIl II) 2 A for A > and Wmin S <[[w0] 51:32
(m] Then there exists a threshold 6n = poly A, m
-5/3 e//3
and [ax, [wn, will < poly(m, A- )
E AUXILIARY LEMMAS
E. EVALUATION OF THE INVARIANT MEASURE
This subsection provides lemmas about the evaluation of the function value sampled from the in- variant measure 3. These are utilized in the proof of Proposition 4.3 (see Appendix C First, we introduce two results from Raginsky et al. (2017), and then we prove the dissipativity, which is imposed an assumption in these results.
Lemma E.1 (Propasition 11 in Raginsky et al. (017)). Suppose that f f + R satisfies the following conditions:
f is L-smooth.
25

---

Published as a conference paper at ICLR 2023
*f is (M,b) disssiiattee i.e., it holds that (8, Vf(()) 2 M|08| Then, for uny 3 2 2/M, it holds that
for any 0 E G
d
eL
+ 11
Eg [f(0)] min f(0) v log 8E9
2
M
Lemma E.2 (Lemmaa and Lemma Raginsky et al. (2017)) Let μil, 422 be two probability
measures on @ with finite second moments, and let f 6 - R be (M, diddiiipe function satisfying V f(O)]l & for B 2 O. Then, it holds that
1o gdmn - S gdluol (Mo+ + B)
where x² = max |10| du,, Se |101 duz)
Lemma E.3 (dissipativity). Rx(-) is (M, -isisipateeee with M 2A and b 8m22 R2.
Proof. By straightforward calculation, we have that
m
(0, (R)(0)) Σ
aj
V R2(0)
W Vwy Rx)
==1
dā
dā, da,
Σ 1=1
aj
0g [m 1z))
Σ t=1
a [w. ;))
+ 220z
daj
f=1
m
dwj dwj
dwi dwy
Wij
aga Jujj w))
CzūjJ J (wx, my)
2X103
dāj
dā, day
2X
+
aj
T ( w3)
daj
a (wi w))
j
i=1
m
dwi
dwi
W
a (W;, wf)
a. (1,, 1yy
dwy
dwy
As for the second term and the third term, since [[(,, w)1 < | and [[[ww, x),,,)] S |el1/2 for any w. v E IRd, we have that
àc I (w; w))
dā
Σ
a (w w.))
dā,
da
da
1=1
1=1
dā
a da,
ag ( (ii, wr))
Σ
a
[wu wr)
< 4m3 R²,
1=1
and
dw; + Σ
w.) o dwy
Wj. Σ
Ja w3) 00)00 C
JaājJ(wü
dw,
duy
1=1
==1
m
dw dwy
a, (w;, T.y) o du,
0.0 [ w))
+
< 4m2
dw
j=1
Combining these inequality, we get that
(0, (R)(0)) > 2111012 At²
which gives the conclusion.
26

---

Published as a conference paper at ICLR 2023
E.2 PROOF OF LEMMA
In this subsection, we give a proof to Lemma C.4 the LSI for the invariant measure Toe- The key notion is that RĄ be decomposed the bounded term (Iz-distance) and the strongly convex term (regularization term). Combining this fact with the following lemma, we can ensure the LSI.
Lemma E.4 (Holley & Stroock (1987); Nitanda et al. (021b)). Let probability measure on θ with a density function satisfy the LSI with constant a. For a function f O - IR that satisfies [f(0)] & B for any 0 E O, a probability measure defined by
Q(0)d0= = exp(J(0)))())
[g(exp(((0))((1)]
satisfies the LSI with constant exp(-4B)
proof of Lemma C.4 First, we note that
3 exp(-3Rx(0))d0 exp (-8X1101) exp (-2 B ((x) f(;; d0.
Since the function 0 + /2110| 1| is 23A-strongly convex, a measure with density exp (3a]10) de
satisfies the LSI with constant B3 Bakry & Emeery 1985). Moreover, by straightforward calcu-
lation shows that 2 En (Fae, (x) - fx; 0) I 28m² 2 R Lemma E.4 Empliee that xoo satisfies the LSI with a constant exx(epp(8823) R²) which gives the conclusion.
E.3 PROOF OF LEMMA
In this subsection we write C(0) = E. (z)
Rx()== + x1101
Since 0 ++ A || 2--smohhh it sufficient to show that L(.) is I'-smooth with T (mm2 To this end, let 0, 0' E O. We consider the decomposition
for proving Lemma C.5
VC(0) VC())
V Vay ((0) - Ve,, vw, )
Va, [()) - va, + ww - V (()))
1=1
where
Vay Vay C(0') = Σ
a T wg))
dāj
d d' w//)
da'
da
da,
m
dā
da day
Σ
a (i
a alI(w; wy))
daz
m
dwū
dw
V n (()) V.,, C(0')
Σ
agd (wi, mz
a J ( w
+
dw,
dw,
1
dw - ďे ( w3))
dw
+ a,āyJ
2
dw,
dwy
i=1
(see Eq. 3 and Eq. (4) The following lemma gives an upper bound for each term
Lemma F.S. For any 0, 0' E e and j E [m], it holds that
5 2vdR
V (()) - (()') S
(las - ags (laj-
+ || - w/(l) + 2
[w;; Will
2
d
1=1
V ((0) V c(0))| < m
(2R
+ 2R ) (1a, anي + +1w - w + 2 > (la: - a'l + 1| - -
d
27

---

Published as a conference paper at ICLR 2023
Proof. The proof is based on the straightforward calculation. As for the first inequality, for every i E [m], it holds that
dā, at d. w/)
dæ
à (w;; wy)
daz
daj
dāj
dā-
(0:1(0; wzn) a (1,, (.y))
+
(a/ my) - ( mby)
da;
da
dāj
dā;
da'
(a/l(u;, w/) T (())
+ ad T, w/))
daj
da
da,
$ |0,- dال" |108|11100)) |l
dR2
dR?
|
4R + ||00 ا ||
4R + [0; will
4R +
R
|ā, 0,1
2d
2d
2d
2d
5R
$
(aa - a'Sl + |100 - wl|l) + 2 L0; w/lbb
2
and
dā;
dd'
a 1 (w; w8))
ai (w, mtr)
da;
daj
dāj
(dā; dā' da,
(a) [10 wzz) ai 1( [mo w²))
+ a: [w] w/)
da-
day
[0- wdy || + vdR
2v (1a3 dg} + ||w - w2]l),
< 2d
2d [0
S d
< || < 1 for any j E [m]. Then the triangle incquality gives the first assertion. As for the second inequality, for every E [m]. it holds that
where use ||/|||
(,āā (wi, ú.))
dæj dw;
a (uo 1))
duy
(a.a, (.y) ब a G., m3)) dw
dw
/
J(,, 18)) -, w()) ①
(w,,
duy
dw,
dey
dwij
+
(dja J [w, my)) - J [10 x7))
+ Jaok w3) o
dwy
dwj
dw,
VdR
VdR
4VdR+ + 12² Vd
< IR|a a/}
4VdR R|a, aأيه
||w, wlill AVdR
2d
2d
2d
+ R²² Vd
vdR
|| will 4v dR + 21²
||w; -w'sl
2d
2d
< 2R (la,
d/
||y w/ ||) + 22 at1 + I|ll - -w((l) w(ll).
and
dw,
dwy
a [w; w)) du,
J (T/ w
dwy
dwij
du du,
(a:a3, J (ws,, 1z3) a'a J (w;, w1l)
- J.a,, wf))
dwy
dw,
dw
+ [gaz J ( w))) o
dw,
dwy
1
R
2R
< 2d 0, 0'1
AR + R 2d
||00
+
2d
[wu
w/1l
=
[a, ag + +|lu, - ww/ll)
Again by using the triangle inequality, obtain the conclusion.
28

---

Published as a conference paper at ICLR 2023
proof of Lemmal C.3
By using Lemma E.5
VC(
1
Va, [()) - va,((0)) + V [(0) - Vw, (()))
1=1
5R
2v2R
2R
+2R
22 +2R
Σ (1a agو + +|lwa, wi$ll)
d
5R
2vdR
2R d
5 m
+ 2R
21
2173
V2m 10 0'1 = L' - 0'll
2
holds with I' = Om Ra). Combining this with the fact that the mapping 0 - A|1011 is smooooh and the triangle inequality, we obtain that R.(-) is L-soooth with L = (m Rt + A), which gives the conclusion.
29


Reviews:
[{"review_id": "mFF7k3d0tWv", "reviewer": "Reviewer_Xjf3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "This paper consider the optimization and the statistical guarantee of two-layer ReLU neural networks under the teacher-student settings, demonstrating that we can obtain a fast rate on the excess risk with a computational-efficient two phase optimization algorithm, that can be shown to beat any linear estimators on the statistical efficiency.", "summary_of_the_review": "The main concern for me is about the novelty. If I understand correctly, the only new content for this paper is the computational efficient algorithm. However, this part is presented poorly. I do have a specific question on this two-phase algorithm. Following the constants selected in Theorem 4.5, we still need $k^{(1)} = \\exp(\\mathrm{poly}(m))$, which can still be pathological when $m$ is not so small. Is this really satisfactory? Furthermore, \tI’m wondering if Proposition 4.3 is a satisfactory result, as when $\\beta$ goes to infinity, the risk does not go to 0. ", "strength_and_weaknesses": "### Strength:\n* The conclusion on the superiority of the neural networks is interesting.\n\n### Weakness:\n* The presentation of the paper, especially Section 4.2 should be improved. The two-phase algorithms are not presented in a unified way, which leads to some ambiguities for me.\n* The results are not a substantial improvement over [1]. The only new result for this paper is showing that when the teacher and the student have the same width, we can have a computationally efficient algorithm to perform the estimation, using the idea from [2].\n\n[1] Suzuki, Taiji, and Shunta Akiyama. \"Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods.\" In International Conference on Learning Representations. 2021.\n\n[2] Zhang, Xiao, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. \"Learning one-hidden-layer relu networks via gradient descent.\" In The 22nd international conference on artificial intelligence and statistics, pp. 1524-1534. PMLR, 2019.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "jmBX070IaU", "reviewer": "Reviewer_vbHH", "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": "This paper studies the excess risk of two-layer ReLU neural networks in a teacher-student regression model. In particular, they showed that the student network could learn the teacher network under certain conditions in two phases: first by noisy gradient descent\nand then by vanilla gradient descent. ", "summary_of_the_review": "In general, this paper is well written. My only concern is whether the exact recovery of the parameter is necessary for NN training, if we only care about the excess risk. Instead of reparemetrizing, can we directly decrease the noise level in Noise GD to zero?", "strength_and_weaknesses": "Strength:\n1. The proposed algorithm can recover the teacher network's parameters, which is a hard problem. \n2. This paper is well-written and organized.\n3. This paper has proof and experiments to support their results.\n\nWeakness:\n1. This paper requires the student network has the same width as the teacher network. It is unknown whether such a result can be generalized to the case where we don't know m in advance.\n2. To connect the noisy SGD and vanilla SGD, the algorithm requires reparameterizing the neural network. This kind of trick seems to be impractical in real applications, especially for DNNs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hKCLIDzGed", "reviewer": "Reviewer_51MF", "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": "The authors consider learning from a two-layer network, using a) a student with matching architecture trained with a two-phase Langevin+GD procedure b) linear methods. They provide upper (resp. lower) bounds on excess test error with the number of samples, and show that the student net always display faster rates than linear method. Their discussion also provides some insight about the role of convexity (or lack thereof) to rationalize these findings.", "summary_of_the_review": "Although I have not reviewed the proof, the paper comes across as clear, well-written, and seems to my understanding to bring solid results, I am therefore giving a good score, but with average-low confidence.\n\nThe paper does not display to me a clear weakness, my only comment being that a plot which illustrates the main point of the paper would to my mind improve on the clarity and impact.", "strength_and_weaknesses": "Strengths:\n\nThe paper is overall well-written, clear and easy to follow. The related works are very satisfyingly discussed.  The question asked (when, and why do neural net outperform linear methods) is definitely an important one, and the setting the authors study is very natural. I have not read the proofs.\n\nWeaknesses:\n\nA plot with the learning curves of the student network, along with those of some kernel methods (RF. NTK, or usual kernels such as RBF), with the relevant upper/lower rates of decay, would be extremely helpful in visualizing (and bolstering) the theoretical results.\n\nQuestions:\n\nTo my understanding, the bound for the student network seems to hold after a threshold of the order of exp(m**2) (theorem 4.5), which can be extremely large already for widths 50, thereby raising the question of whether the regime described can be observed at all unless the network is very narrow. More discussion in this sense would be helpful (or, in the case I am misunderstanding, a clarification from the authors). Note that this is more a clarification question and in any case the results remain of interest.\n\nFor small m (e.g. m=2), does the student net perform clearly better than the linear methods right after the threshold in n predicted in Theorem 4.5? For large dimensions d, I would naively expect from the results of Aubin et al. (The committee machine....., 2019) that there exists a large range of n where this is not the case.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aTPbeaxcQ-", "reviewer": "Reviewer_xk6b", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper studies the excess risk of two-layer ReLU neural networks training by two-stage gradient based algorithms with spherical data iid spread on the unit sphere. Under such neural networks training, the authors demonstrate that, two layer neural networks are able to achieve the minimax $O(1/n)$ rate in a certain norm-based space, when compared to kernel methods with $O(n^{-1/2})$ rate (slightly faster  than this rate via the convex argument technique).", "summary_of_the_review": "This work presents the separation between kernel methods and neural networks in terms of excess risk, but the problem setting with a few $m$, sufficiently large $\\beta$ in Proposition 4.3, and the function space require more discussion and refinement for publication. I suggest 1) the authors center around a few $m$ for the teacher network, but the student network allows for more neurons;\n2) fix the over-parameterization issue in the excess risk;\n3) avoid an exponential order of a sufficiently large $\\beta$ in Proposition 4.3.", "strength_and_weaknesses": "**Pros:** \n\n1. propose a two-stage gradient descent algorithm combining the gradient Langevin dynamics and standard gradient descent over the first layer for neural networks training\n\n2. Study the separation between kernel methods and neural networks in terms of excess risk\n\n\n**Cons:**\n\n1. The authors claimed that their results do not require high over-parameterization conditions. However, according to Theorem 4.5, the convergence rate is $O(m^5/n)$, as well as the minimum singular value $\\sigma_{min}$ heavily depending on $m$. \nThat means, their results are only valid to $m \\ll n$ rather than over-parameterization.\nFurthermore, I don’t agree with the authors’ current claimed $O(1/n)$ rate for neural networks, because this is a width-dependent result though the authors set $m < d$ in this work. \nInstead, kernel methods obtain a width-independent $O(n^{-1/2})$ convergence rate, e.g., (Bach, JMLR 2017, Gal et al. NeurIPS 2022). Hence, in this case, it is not enough to show the separation between kernel methods and neural networks.\n\n[1] Vardi, Gal, Ohad Shamir, and Nathan Srebro. \"The Sample Complexity of One-Hidden-Layer Neural Networks.\" NeurIPS 2022.\n\n2. If we put the above key issue aside, a small $m$ (as well as the experiments) makes sense for the teacher network with few activations.  But for the student network, a few $m$ significantly restrict the model expressivity. I'm wondering the size of function space (in my next question). Besides, this also effects the convergence of phase II in Proposition 4.4 with $O(1/m^3)$. The convergence results require to work in a large $m$ setting, falling into a self-contradiction suitation.\n\n3. The considered function space in Eq. (1) is a norm-based function space, and can be regarded as a subspace of variational space for two-layer neural networks via signed measure (or similar to the path-norm based space), see (Bach, JMLR2017). The separation between kernel methods and two-layer neural networks has been studied in this larger space [2] as kernel methods suffer from the curse of dimensionality $\\Omega(n^{-1/d})$. \n\n[2] Parhi, Rahul, and Robert D. Nowak. \"Near-minimax optimal estimation with shallow ReLU neural networks.\" IEEE Transactions on Information Theory (2022).\n\nWhile this work focuses on a smaller function space and kernel methods are close to the $O(n^{-1/2})$ rate in high dimensional settings. I understand the authors aim to show the separation between kernel methods and neural networks on the convergence rate: $O(n^{-1/2})$ vs. $O(1/n)$. However, strictly speaking, this is not the claimed “curse of dimensionality” in the approximation theory view.\n\n4. Proposition 4.3 appears vacuous due to the exponential order of $m$ and $\\beta$. Regarding $\\beta$, the authors suggest using “a sufficiently large $\\beta$” in phase I to ensure a near-optimal result. However, it makes the first term exponentially large in the first term of Proposition 4.4, resulting in a vacuous result.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ULfgnZ5rev-", "reviewer": "Reviewer_VLSM", "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": "This paper studies the excess risk of learning neural networks in the teacher-student setting, as well as the theoretical superiority of neural networks over other linear (or kernel) methods. It provides an excess risk bound of $\\frac{\\log n}{n}$ convergence rate (with polynomial dependency on other parameters) for the neural networks, and also a minimax lower bound of $n^{-\\frac{d+2}{2d+2}-o(1)}$ for all kernel methods to learn the same target function class.", "summary_of_the_review": "This paper presents a solid contribution to the area of deep learning theory, although it has not resolved all the problems under its setting, it still manages to improve the previous analysis and give an almost complete story of learning in the student-teacher setting beyond kernel methods. ", "strength_and_weaknesses": "Strengths:\n1. This paper is clearly and rigorously written. All the notations are well explained and most of the technical difficulties are introduced naturally. It is very delightful to read as the paper managed to convey these highly technical statements with such clarity and fine elaboration.\n2. The story in this paper is complete, in that this paper almost resolves most of the questions in its setting. They have the convergence guarantee with well-explained optimization algorithms and analysis, and also a generalization guarantee as excess risk upper bound. For the lower bound, they proved the LB for all linear classes (kernels) that their generalization over the teacher class is poor compared to student neural nets. \n3. The problem this paper deals with is a long-pursued one in the deep learning theory community. The results in this paper go beyond the previous works and are proven for a setting with almost minimal assumptions over the target function class (for example, it goes beyond the orthogonality condition on which many previous results are based, and it goes beyond the local convergence result of Zhou et al. 2021). This is highly non-trivial progress in this direction. The results of this paper also provide some solid technical contributions.\n\nWeaknesses:\n1. The two-stage optimization process, which uses two different optimization algorithms, seems to be the remaining problem to solve. It would be better if the analysis can be applied to settings without this technical workaround.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster