Year: 2021

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

heading: 1 INTRODUCTION
text: Recent studies have revealed why a stochastic gradient descent for neural networks converges to a global minimum and why it generalizes well under the overparameterized setting in which the number of parameters is larger than the number of given training examples. One prominent approach is to map the learning dynamics for neural networks into function spaces and exploit the convexity of the loss functions with respect to the function. The neural tangent kernel (NTK) (Jacot et al., 2018) has provided such a connection between the learning process of a neural network and a kernel method in a reproducing kernel Hilbert space (RKHS) associated with an NTK.
The global convergence of the gradient descent was demonstrated in Du et al. (2019b); Allen-Zhu et al. (2019a); Du et al. (2019a); Allen-Zhu et al. (2019b) through the development of a theory of NTK with the overparameterization. In these theories, the positivity of the NTK on the given training examples plays a crucial role in exploiting the property of the NTK. Specifically, the positivity of the Gram-matrix of the NTK leads to a rapid decay of the training loss, and thus the learning dynamics can be localized around the initial point of a neural network with the overparameterization, resulting in the equivalence between two learning dynamics for neural networks and kernel methods with the NTK through a linear approximation of neural networks. Moreover, Arora et al. (2019a) provided a generalization bound of O(T−1/2), where T is the number of training examples, on a gradient descent under the positivity assumption of the NTK. These studies provided the first steps in understanding the role of the NTK.
However, the eigenvalues of the NTK converge to zero as the number of examples increases, as shown in Su & Yang (2019) (also see Figure 1), resulting in the degeneration of the NTK. This phenomenon indicates that the convergence rates in previous studies in terms of generalization are generally slower than O(T−1/2) owing to the dependence on the minimum eigenvalue. Moreover, Bietti & Mairal (2019); Ronen et al. (2019); Cao et al. (2019) also supported this observation by providing a precise
estimation of the decay of the eigenvalues, and Ronen et al. (2019); Cao et al. (2019) proved the spectral bias (Rahaman et al., 2019) for a neural network, where lower frequencies are learned first using a gradient descent.
By contrast, several studies showed faster convergence rates of the (averaged) stochastic gradient descent in the RKHS in terms of the generalization (Cesa-Bianchi et al., 2004; Smale & Yao, 2006; Ying & Zhou, 2006; Neu & Rosasco, 2018; Lin et al., 2020). In particular, by extending the results in a finite-dimensional case (Bach & Moulines, 2013), Dieuleveut & Bach (2016); Dieuleveut et al. (2017) showed convergence rates of O(T −2rβ 2rβ+1 ) depending on the complexity r ∈ [1/2, 1] of the target functions and the decay rate β > 1 of the eigenvalues of the kernel (a.k.a. the complexity of the hypothesis space). In addition, extensions to the random feature settings (Rahimi & Recht, 2007; Rudi & Rosasco, 2017; Carratino et al., 2018), to the multi-pass variant (Pillaud-Vivien et al., 2018b), and to the tail-averaging and mini-batching variant (Mücke et al., 2019) have been developed.
Motivation. The convergence rate of O(T −2rβ 2rβ+1 ) is always faster than O(T−1/2) and is known as the minimax optimal rate (Caponnetto & De Vito, 2007; Blanchard & Mücke, 2018). Hence, a gap exists between the theories regarding NTK and kernel methods. In other words, there is still room for an investigation into a stochastic gradient descent due to a lack of specification of the complexities of the target function and the hypothesis space. That is, to obtain faster convergence rates, we should specify the eigenspaces of the NTK that mainly contain the target function (i.e., the complexity of the target function), and specify the decay rates of the eigenvalues of the NTK (i.e., the complexity of the hypothesis space), as studied in kernel methods (Caponnetto & De Vito, 2007; Steinwart et al., 2009; Dieuleveut & Bach, 2016). In summary, the fundamental question in this study is
Can stochastic gradient descent for overparameterized neural networks achieve the optimal rate in terms of the generalization by exploiting the complexities of the target function and hypothesis space?
In this study, we answer this question in the affirmative, thereby bridging the gap between the theories of overparameterized neural networks and kernel methods.

heading: 1.1 CONTRIBUTIONS
text: The connection between neural networks and kernel methods is being understood via the NTK, but it is still unknown whether the optimal convergence rate faster than O(T−1/2) is achievable by a certain algorithm for neural networks. This is the first paper to overcome technical challenges of achieving the optimal convergence rate under the NTK regime. We obtain the minimax optimal convergence rates (Corollary 1), inherited from the learning dynamics in an RKHS, for an averaged stochastic gradient descent for neural networks. That is, we show that smooth target functions efficiently specified by the NTK are learned rapidly at faster convergence rates than O(1/ √ T ). Moreover, we
obtain an explicit optimal convergence rate of O ( T −2rd 2rd+d−1 ) for a smooth approximation of the
ReLU network (Corollary 2), where d is the dimensionality of the data space and r is the complexity of the target function specified by the NTK of the ReLU network.

heading: 1.2 TECHNICAL CHALLENGE
text: The key to showing a global convergence (Theorem 1) is making the connection between kernel methods and neural networks in some sense. Although this sort of analysis has been developed in several studies (Du et al., 2019b; Arora et al., 2019a; Weinan et al., 2019; Arora et al., 2019b;
Lee et al., 2019; 2020), we would like to emphasize that our results cannot be obtained by direct application of their results. A naive idea is to simply combine their results with the convergence analysis of the stochastic gradient descent for kernel methods, but it does not work. The main reason is that we need the L2-bound weighted by a true data distribution on the gap between dynamics of stochastic gradient descent for neural networks and kernel methods if we try to derive a convergence rate of population risks for neural networks from that for kernel methods. However, such a bound is not provided in related studies. Indeed, to the best of our knowledge, all related studies make this kind of connection regarding the gap on training dataset or sample-wise high probability bound (Lee et al., 2019; Arora et al., 2019b). That is, a statement “for every input data x with high probability |g(t)nn (x)− g(t)ntk(x)| < ” cannot yield a desired statement “‖g (t) nn − g(t)ntk‖L2(ρX) < ” where g (t) nn and g (t) ntk are t-th iterate of gradient descent for a neural network and corresponding iterate described by NTK, and ‖·‖L2(ρX) is the L2-norm weighted by a marginal data distribution ρX over the input space. Moreover, we note that we cannot utilize the positivity of the Gram-matrix of NTK which plays a crucial role in related studies because we consider the population risk with respect to ‖ · ‖L2(ρX) rather than the empirical risk.
To overcome these difficulties we develop a different strategy of the proof. First, we make a bound on the gap between two dynamics of the averaged stochastic gradient descent for a two-layer neural network and its NTK with width M (Proposition A), and obtain a generalization bound for this intermediate NTK (Theorem A in Appendix). Second, we remove the dependence on the width of M from the intermediate bound. These steps are not obvious because we need a detailed investigation to handle the misspecification of the target function by an intermediate NTK. Based on detailed analyses, we obtain a faster and precise bound than those in previous results (Arora et al., 2019a).
The following is an informal version of Proposition A providing a new connection between a two-layer neural networks and corresponding NTK with width M . Proposition 1 (Informal). Under appropriate conditions we simultaneously run averaged stochastic gradient descent for a neural network with width of M and for its NTK. Assume they share the same hyper-parameters and examples to compute stochastic gradients. Then, for arbitrary number of iterations T ∈ Z+ and > 0, there exists M ∈ Z+ depending only on T and such that ∀t ≤ T ,
‖g(t)nn − g (t) ntk‖L∞(ρX) ≤ ,
where g(t)nn and g (t) ntk are iterates obtained by averaged stochastic gradient descent.
This proposition is the key because it connects two learning dynamics for a neural network and its NTK through overparameterization without the positivity of the NTK. Instead of the positivity, this proposition says that overparameterization increases the time stayed in the NTK regime where the learning dynamics for neural networks can be characterized by the NTK. As a result, the averaged stochastic gradient descent for the overparameterized two-layer neural networks can fully inherit preferable properties from learning dynamics in the NTK as long as the network width is sufficiently large. See Appendix A for detail.

heading: 1.3 ADDITIONAL RELATED WORK
text: Besides the abovementioned studies, there are several works (Chizat & Bach, 2018b; Wu et al., 2019; Zou & Gu, 2019) that have shown the global convergence of (stochastic) gradient descent for overparameterized neural networks essentially relying on the positivity condition of NTK. Moreover, faster convergence rates of the second-order methods such as the natural gradient descent and GaussNewton method have been demonstrated (Zhang et al., 2019; Cai et al., 2019) in the similar setting, and the further improvement of Gauss-Newton method with respect to the cost per iteration has been conducted in Brand et al. (2020).
There have been several attempts to improve the overparameterization size in the NTK theory. For the regression problem, Song & Yang (2019) has succeeded in reducing the network width required in Du et al. (2019b) by utilizing matrix Chernoff bound. For the classification problem, the positivity condition can be relaxed to a separability condition using another reference model (Cao & Gu, 2019a;b; Nitanda et al., 2019; Ji & Telgarsky, 2019), resulting in mild overparameterization and generalization bounds of O(T−1/2) or O(T−1/4) on classification errors.
For an averaged stochastic gradient descent on classification problems in RKHSs, linear convergence rates of the expected classification errors have been demonstrated in Pillaud-Vivien et al. (2018a);
Nitanda & Suzuki (2019). Although our study focuses on regression problems, we describe how to combine their results with our theory in the Appendix.
The mean field regime (Nitanda & Suzuki, 2017; Mei et al., 2018; Chizat & Bach, 2018a) that is a different limit of neural networks from the NTK is also important for the global convergence analysis of the gradient descent. In the mean field regime, the learning dynamics follows the Wasserstein gradient flow which enables us to establish convergence analysis in the probability space.
Moreover, several studies (Allen-Zhu & Li, 2019; Bai & Lee, 2019; Ghorbani et al., 2019; Allen-Zhu & Li, 2020; Li et al., 2020; Suzuki, 2020) attempt to show the superiority of neural networks over kernel methods including the NTK. Although it is also very important to study the conditions beyond the NTK regime, they do not affect our contribution and vice versa. Indeed, which method is better depends on the assumption on the target function and data distribution, so it is important to investigate the optimal convergence rate and optimal method in each regime. As shown in our study, the averaged stochastic gradient descent for learning neural network achieves the optimal convergence rate if the target function is included in RKHS associated with the NTK with the small norm. It means there are no methods that outperform the averaged stochastic gradient descent under this setting.

heading: 2 PRELIMINARY
text: Let X ⊂ Rd and Y ⊂ R be the measurable feature and label spaces, respectively. We denote by ρ a data distribution on X × Y , by ρX the marginal distribution on X , and by ρ(·|X) the conditional distribution on Y , where (X,Y ) ∼ ρ. Let `(z, y) (z ∈ R, y ∈ Y) be the squared loss function 1 2 (z − y) 2, and let g : X → R be a hypothesis. The expected risk function is defined as follows:
L(g) def= E(X,Y )∼ρ[`(g(X), Y )]. (1)
The Bayes rule gρ : X → R is a global minimizer of L over all measurable functions. For the least squares regression, the Bayes rule is known to be gρ(X) = EY [Y |X] and the excess risk of a hypothesis g (which is the difference between the expected risk of g and the expected risk of the Bayes rule gρ) is expressed as a squared L2(ρX)-distance between g and gρ (for details, see Cucker & Smale (2002)) up to a constant:
L(g)− L(gρ) = 1
2 ‖g − gρ‖2L2(ρX),
where ‖ · ‖L2(ρX) is L2-norm weighted by ρX defined as ‖g‖L2(ρX) def = (∫ g2(X)dρX(X) )1/2 (g ∈ L2(ρX)). Hence, the goal of the regression problem is to approximate gρ in terms of the L2(ρX)-distance in a given hypothesis class.
Two-layer neural networks. The hypothesis class considered in this study is the set of two-layer neural networks, which is formalized as follows. Let M ∈ Z+ be the network width (number of hidden nodes). Let a = (a1, . . . , aM )> ∈ RM (ar ∈ R) be the parameters of the output layer, B = (b1, . . . , bM ) ∈ Rd×M (br ∈ Rd) be the parameters of the input layer, and c = (c1, . . . , cM )> ∈ RM (cr ∈ R) be the bias parameters. We denote by Θ the collection of all parameters (a,B, c), and consider two-layer neural networks:
gΘ(x) = 1√ M M∑ r=1 arσ(b > r x+ γcr), (2)
where σ : R→ R is an activation function and γ > 0 is a scale of the bias terms.
Symmetric initialization. We adopt symmetric initialization for the parameters Θ. Let a(0) = (a
(0) 1 , . . . , a (0) M ) >, B(0) = (b(0)1 , . . . , b (0) M ), and c (0) = (c (0) 1 , . . . , c (0) M ) > denote the initial values for a, B, and c, respectively. Assume that the number of hidden units M ∈ Z+ is even. The parameters for the output layer are initialized as a(0)r = R for r ∈ {1, . . . , M2 } and a (0) r = −R for r ∈ {M2 + 1, . . . ,M}, where R > 0 is a positive constant. Let µ0 be a uniform distribution on the sphere Sd−1 = {b ∈ Rd | ‖b‖2 = 1} ⊂ Rd used to initialize the parameters for the input layer. The parameters for the input layer are initialized as b(0)r = b (0)
r+M2 for r ∈ {1, . . . , M2 }, where (b (0) r ) M 2 r=1
are independently drawn from the distribution µ0. The bias parameters are initialized as c (0) r = 0 for r ∈ {1, . . . ,M}. The aim of the symmetric initialization is to make an initial function gΘ(0) = 0, where Θ(0) = (a(0), B(0), c(0)). This is just for theoretical simplicity. Indeed, we can relax the symmetric initialization by considering an additional error stemming from the nonzero initialization in the function space.
Regularized expected risk minimization. Instead of minimizing the expected risk (1) itself, we consider the minimization problem of the regularized expected risk around the initial values:
min Θ
{ L(gΘ) + λ
2
( ‖a− a(0)‖22 + ‖B −B(0)‖2F + ‖c− c(0)‖22 )} . (3)
where the last term is the L2-regularization at an initial point with a regularization parameter λ > 0. This regularization forces iterations obtained by optimization algorithms to stay close to the initial value, which enables us to utilize the better convergence property of regularized kernel methods.
Averaged stochastic gradient descent. Stochastic gradient descent is the most popular method for solving large-scale machine learning problems, and its averaged variant is also frequently used to stabilize and accelerate the convergence. In this study, we analyze the generalization ability of an averaged stochastic gradient descent. The update rule is presented in Algorithm 1. Let Θ(t) = (a(t), B(t), c(t)) denote the collection of t-th iterates of parameters a ∈ RM , B ∈ Rd×M , and c ∈ RM . At t-th iterate, stochastic gradient descent using a learning rate ηt for the problem (3) with respect to a,B, c is performed on lines 4–6 for a randomly sampled example (xt, yt) ∼ ρ. These updates can be rewritten in an element-wise fashion as follows. For r ∈ {1, . . . ,M},
a(t+1)r − a(0)r = (1− ηtλ)(a(t)r − a(0)r )− ηtM−1/2(gΘ(t)(xt)− yt)σ(b(t)>r xt + γc(t)r ), b(t+1)r − b(0)r = (1− ηtλ)(b(t)r − b(0)r )− ηtM−1/2(gΘ(t)(xt)− yt)a(t)r σ′(b(t)>r xt + γc(t)r )xt, c(t+1)r − c(0)r = (1− ηtλ)(c(t)r − c(0)r )− ηtM−1/2(gΘ(t)(xt)− yt)a(t)r γσ′(b(t)>r xt + γc(t)r ),
where a(t) = (a(t)1 , . . . , a (t) M ) >, B(t) = (b(t)1 , . . . , b (t) M ), and c (t) = (c (t) 1 , . . . , c (t) M ) >. Finally, a weighted average using weights αt of the history of parameters is computed on line 9. In our theory, we consider the constant learning rate ηt = η and uniform averaging αt = 1/(T + 1).
Algorithm 1 Averaged Stochastic Gradient Descent
1: Input: number of iterations T , regularization parameter λ, learning rates (ηt)T−1t=0 , averaging weights (αt)Tt=0, initial values Θ (0) = (a(0), B(0), c(0)) 2: for t = 0 to T − 1 do 3: Randomly draw a sample (xt, yt) ∼ ρ 4: a(t+1) ← a(t) − ηt∂a`(gΘ(t)(xt), yt)− ηtλ(a(t) − a(0)) 5: B(t+1) ← B(t) − ηt∂B`(gΘ(t)(xt), yt)− ηtλ(B(t) −B(0)) 6: c(t+1) ← c(t) − ηt∂c`(gΘ(t)(xt), yt)− ηtλ(c(t) − c(0)) 7: Θ(t+1) ← (a(t+1), B(t+1), c(t+1)) 8: end for 9: Θ (T ) = ( ∑T t=0 αta (t), ∑T t=0 αtB (t), ∑T t=0 αtc
(t)) 10: Return g
Θ (T )
Integral and Covariance Operators. The integral and covariance operators associated with the kernels, which are the limit of the Gram-matrix as the number of examples goes to infinity, play a crucial role in determining the learning speed. For a given Hilbert space H, we denote by ⊗H the tensor product on H, that is, ∀(f, g) ∈ H2, f ⊗H g defines a linear operator; h ∈ H 7→ (f ⊗H g)h = 〈f, h〉H g ∈ H. Note that f ⊗H g naturally induces a bilinear function: (h, h′) ∈ H × H 7→ 〈(f ⊗H g)h, h′〉H = 〈f, h〉H 〈g, h′〉H. When H is a reproducing kernel Hilbert space (RKHS) associated with a bounded kernel k : X × X → R, the covariance operator Σ : H 7→ H is defined as follows: Set KX def = k(X, ·) and
Σ = EX∼ρX [KX ⊗H KX ].
Note that the covariance operator is a restriction of the integral operator on L2(ρX): f ∈ L2(ρX) 7−→ Σf = ∫ X f(X)KXdρX ∈ L2(ρX).
We use the same symbol as above for convenience with a slight abuse of notation. Because Σ is a compact self-adjoint operator on L2(ρX), Σ has the following eigendecomposition: Σf = ∑∞ i=1 λi 〈f, φi〉L2(ρX) φi for f ∈ L2(ρX), where {(λi, φi)} ∞ i=1 is a pair of eigenvalues and orthogonal eigenfunctions in L2(ρX). For s ∈ R, the power Σs is defined as Σsf = ∑∞ i=1 λ s i 〈f, φi〉L2(ρX) φi.

heading: 3 MAIN RESULTS: MINIMAX OPTIMAL CONVERGENCE RATES
text: In this section, we present the main results regarding the fast convergence rates of the averaged stochastic gradient descent under a certain condition on the NTK and target function gρ.
Neural tangent kernel. The NTK is a recently developed kernel function and has been shown to be extremely useful in demonstrating the global convergence of the gradient descent method for neural networks (cf., Jacot et al. (2018); Chizat & Bach (2018b); Du et al. (2019b); Allen-Zhu et al. (2019a;b); Arora et al. (2019a)). The NTK in our setting is defined as follows: ∀x, ∀x′ ∈ X ,
k∞(x, x ′) def = Eb(0) [σ(b(0)>x)σ(b(0)>x′)] +R2(x>x′ + γ2)Eb(0) [σ′(b(0)>x)σ′(b(0)>x′)], (4)
where the expectation is taken with respect to b(0) ∼ µ0. The NTK is the key to the global convergence of a neural network because it makes a connection between the (averaged) stochastic gradient descent for a neural network and the RKHS associated with k∞ (see Proposition A). Although this type of connection has been shown in previous studies (Arora et al., 2019b; Weinan et al., 2019; Lee et al., 2019; 2020), note that their results are inapplicable to our theory because we consider the population risk. Indeed, our study is the first to establish this connection for an (averaged) stochastic gradient descent in terms of the uniform distance on the support of the data distribution, enabling us to obtain faster convergence rates. We note that an NTK k∞ is the sum of two NTKs, that is, the first and second terms in (4) are NTKs for the output and input layers with bias, respectively.

heading: 3.1 GLOBAL CONVERGENCE ANALYSIS
text: LetH∞ be an RKHS associated with NTK k∞, and let Σ∞ be the corresponding integral operator. Let {λi}∞i=1 denote the eigenvalues of Σ∞ sorted in decreasing order: λ1 ≥ λ2 ≥ · · · . Assumption 1.
(A1) There exists C > 0 such that ‖σ′′‖∞ ≤ C, ‖σ′‖∞ ≤ 2, and |σ(u)| ≤ 1 + |u| for ∀u ∈ R.
(A2) supp(ρX) ⊂ {x ∈ Rd | ‖x‖2 ≤ 1}, Y ⊂ [−1, 1], R = 1, and γ ∈ [0, 1].
(A3) There exists r ∈ [1/2, 1] such that gρ ∈ Σr∞(L2(ρX)), i.e., ‖Σ−r∞ gρ‖L2(ρX) <∞.
(A4) There exists β > 1 such that λi = Θ(i−β).
Remark.
• (A1): Typical smooth activation functions, such as sigmoid and tanh functions, and smooth approximations of the ReLU, such as swish (Ramachandran et al., 2017), which performs as well as or even better than the ReLU, satisfy Assumption (A1). This condition is used to relate the two learning dynamics between neural networks and kernel methods (see Proposition A). • (A2): The boundedness (A2) of the feature space and label are often assumed for stochastic
optimization and least squares regression for theoretical guarantees (see Steinwart et al. (2009)). Note that these constants in (A2) can be relaxed to arbitrary constants. • (A3): Assumption (A3) measures the complexity of gρ because Σ∞ can be considered as a
smoothing operator using a kernel k∞. A larger r indicates a faster decay of the coefficients of expansion of gρ based on the eigenfunctions of Σ∞ and smoothens gρ. In addition, Σr∞(L2(ρX))
shrinks with respect to r and Σ1/2∞ (L2(ρX)) = H∞, resulting in gρ ∈ H∞. This condition is used to control the bias of the estimators through L2-regularization. The notation Σ−r∞ gρ represents any function G ∈ L2(ρX) such that gρ = Σr∞G. • (A4): Assumption (A4) controls the complexity of the hypothesis classH∞. A larger β indicates
a faster decay of the eigenvalues and makesH∞ smaller. This assumption is essentially needed to bound the variance of the estimators efficiently and derive a fast convergence rate. Theorem 1 and Corollary 1, 2 hold even though the condition in (A4) is relaxed to λi = O(i−β) and the lower bound λi = Ω(i−β) is necessary only for making obtained rates minimax optimal.
Under these assumptions, we derive the convergence rate of the averaged stochastic gradient descent for an overparameterized two-layer neural network, the proof is provided in the Appendix.
Theorem 1. Suppose Assumptions (A1)-(A3) hold. Run Algorithm 1 with a constant learning rate η satisfying 4(6 + λ)η ≤ 1. Then, for any > 0, ‖Σ∞‖op ≥ λ > 0, δ ∈ (0, 1), and T ∈ Z+, there exists M0 ∈ Z+ such that for any M ≥M0, the following holds with high probability at least 1− δ over the random choice of features Θ(0): E [ ‖g
Θ (T ) − gρ‖2L2(ρX)
] ≤ + α ( λ2r‖Σ−r∞ gρ‖2L2(ρX) + 1
T + 1 ‖gρ‖2H∞ +
1
λη2(T + 1)2 ‖gρ‖2H∞ ) + α
T + 1
( 1 + ‖gρ‖2L2(ρX) + ‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( Σ∞(Σ∞ + λI) −1) , where α > 0 is a universal constant and g
Θ (T ) is an iterate obtained through Algorithm 1.
Remark. The first term and second term λ2r‖Σ−r∞ gρ‖2L2(ρX) are the approximation error and bias, which can be chosen to be arbitrarily small. The first term comes from the approximation of the NTK using finite-sized neural networks, and the second term comes from the L2-regularization, which coincides with a bias term in the theory of least squares regression (Caponnetto & De Vito, 2007). The third and fourth terms come from the convergence of the averaged semi-stochastic gradient descent (which is considered in the proof) in terms of the optimization. The appearance of an inverse dependence on λ in the fourth term is common because a smaller λ indicates a weaker strong convexity, which slows down the convergence speed of the optimization methods (Rakhlin et al., 2012). The term Tr ( Σ∞(Σ∞ + λI)
−1) is the variance from the stochastic approximation of the gradient, and it is referred to as the degree of freedom or the effective dimension, which is known to be unavoidable in kernel regression problems (Caponnetto & De Vito, 2007; Dieuleveut & Bach, 2016; Rudi & Rosasco, 2017).
Global convergence in NTK regime. This theorem shows the global convergence to the Bayes rule gρ, which is a minimizer over all measurable maps because the approximation term can be arbitrarily small by taking a sufficiently large network width M . The required value of M has an exponential dependence on T ; note, however, that reducing M is not the main focus of the present study. The key technique is to relate two learning dynamics for two-layer neural networks and kernel methods in an RKHS approximating H∞ up to a small error. Unlike existing studies (Du et al., 2019b; Arora et al., 2019a;b; Weinan et al., 2019; Lee et al., 2019; 2020) showing such connections, we establish this connection in term of the L∞(ρX)-norm, which is more useful in a generalization analysis. Moreover, existing studies essentially rely on the strict positivity of the Gram-matrix to localize all iterates around an initial value, which can slow down the convergence rate in terms of the generalization because the convergence of the eigenvalues of the NTK to zero affects the Rademacher complexity. By contrast, our theory succeeds in demonstrating the global convergence in the NTK regime without the positivity of the NTK.

heading: 3.2 OPTIMAL CONVERGENCE RATE
text: We derive the fast convergence rate from Theorem 1 by utilizing Assumption (A4), which defines the complexity of the NTK. The regularization parameter λ mainly controls the trade-off within the generalization bound, that is, a smaller value decreases the bias term but increases the variance term including the degree of freedom. The degree of freedom Tr ( Σ∞(Σ∞ + λI)
−1) can be specified by imposing Assumption (A4) because it determines the decay rate of the eigenvalues of Σ∞. As a result, this trade-off between bias and variance depending on the choice of λ becomes clear, and we
can determine the optimal value. Concretely, by setting λ = T−β/(2rβ+1), the sum of the bias and variance terms is minimized, and these terms become asymptotically equivalent. Corollary 1. Suppose Assumptions (A1)-(A4) hold. Run Algorithm 1 with the constant learning rate η = O(1) satisfying 4(6 + λ)η ≤ 1 and λ = T−β/(2rβ+1). Then, for any > 0, δ ∈ (0, 1) and T ∈ Z+ satisfying ‖Σ∞‖op ≥ λ, there exists M0 ∈ Z+ such that for any M ≥ M0, the following holds with high probability at least 1− δ over the random choice of random features Θ(0):
E [ ‖g
Θ (T ) − gρ‖2L2(ρX)
] ≤ + αT −2rβ 2rβ+1 ( 1 + ‖Σ−r∞ gρ‖2L2(ρX) ) ,
where α > 0 is a universal constant and g Θ (T ) is an iterate obtained by Algorithm 1.
The resulting convergence rate is O(T −2rβ 2rβ+1 ) with respect to T by considering a sufficiently large network width of M such that the error stemming from the approximation of NTK can be ignored. Because T corresponds to the number of examples used to learn a predictor g
Θ (T ) , this convergence
rate is simply the generalization error bound for the averaged stochastic gradient descent. In general, this rate is always faster than T−1/2 and is known to be the minimax optimal rate of estimation (Caponnetto & De Vito, 2007; Blanchard & Mücke, 2018) inH∞ in the following sense. Let P(β, r) be a data distribution class satisfying Assumptions (A2)-(A4). Then,
lim τ→0 lim inf T→∞ inf h(T ) sup ρ
P [ ‖h(T ) − gρ‖2L2(ρX) > τT −2rβ 2rβ+1 ] = 1,
where ρ is taken in P(β, r) and h(T ) is taken over all mappings (xt, yt)T−1t=0 7→ h(T ) ∈ H∞.

heading: 3.3 EXPLICIT OPTIMAL CONVERGENCE RATE FOR SMOOTH APPROXIMATION OF RELU
text: For smooth activation functions that sufficiently approximate the ReLU, an optimal explicit convergence rate can be derived under the setting in which the target function is specified by NTK with the ReLU, and the data are distributed uniformly on a sphere. We denote the ReLU activation by σ(u) = max{0, u} and a smooth approximation of ReLU by σ(s), which converges to ReLU, as s→∞ in the following sense. We make alternative assumptions to (A1), (A2), and (A3): Assumption 2.
(A1’) σ(s) satisfies (A1). σ(s) and σ(s) ′ converge pointwise almost surely to σ and σ′ as s→∞.
(A2’) ρX is a uniform distribution on {x ∈ Rd | ‖x‖2 = 1}. Y ⊂ [−1, 1], R = 1, and γ ∈ (0, 1].
(A3’) The condition (A3) is satisfied by the NTK associated with the ReLU activation σ.
(A1’) and (A2’) are special cases of (A1) and (A2). There are several activation functions that satisfy this condition, including swish (Ramachandran et al., 2017): σ(s)(u) = u1+exp(−su) . Under these conditions, we can estimate the decay rate of the eigenvalues for the ReLU as β = 1 + 1d−1 , yielding the explicit optimal convergence rate by adapting the proof of Theorem 1 to the current setting. Note that Algorithm 1 is run for a neural network with a smooth approximation σ(s) of the ReLU. Corollary 2. Suppose Assumptions (A1’), (A2’), and (A3’) hold. Run Algorithm 1 with the constant learning rate η = O(1) satisfying 4(6 + λ)η ≤ 1, and λ = T−d/(2rd+d−1). Given any > 0, δ ∈ (0, 1) and T ∈ Z+ satisfying ‖Σ∞‖op ≥ 2λ, let s be an arbitrary and sufficiently large positive value. Then, there exists M0 ∈ Z+ such that for any M ≥ M0, the following holds with high probability at least 1− δ over the random choice of random features Θ(0):
E [ ‖g
Θ (T ) − gρ‖2L2(ρX)
] ≤ + αT −2rd 2rd+d−1 ( 1 + ‖Σ−r∞ gρ‖2L2(ρX) ) ,
where α > 0 is a universal constant and g Θ (T ) is an iterate obtained by Algorithm 1.

heading: 4 EXPERIMENTS
text: We verify the importance of the specification of target functions by showing the misspecification significantly slows down the convergence speed. To evaluate the misspecification, we consider
single-layer learning as well as the two-layer learning, and we see the advantage of two-layer learning. Here, note that, with evident modification of the proofs, the counterparts of Corollaries 1 and 2 for learning a single layer also hold by replacing Σ∞ with the covariance operator Σa,∞ (Σb,∞) associated with ka,∞ (kb,∞), where
ka,∞(x, x ′) = Eb(0) [σ(b(0)>x)σ(b(0)>x′)], kb,∞(x, x ′) = R2(x>x′ + γ2)Eb(0) [σ′(b(0)>x)σ′(b(0)>x′)],
which are components of k∞ = ka,∞+kb,∞ corresponding to the output and input layers, respectively. Then, from Corollaries 1 and 2, a Bayes rule gρ is learned efficiently by optimizing the layer which has a small norm ‖Σ−rgρ‖L2(ρX) for Σ ∈ {Σa,∞,Σb,∞,Σ∞}.
Experimental settings. Figure 2 (Top) depicts norms ‖Σ−rgρ‖L2(ρX) for Σ ∈ {Σa,∞,Σb,∞,Σ∞}. Bayes rules gρ are averages of eigenfunctions of Σa,∞ (left), Σb,∞ (middle), and Σ∞ (right) corresponding to the 10-largest eigenvalues excluding the first and second, with the setting: R = 1/(20 √ 2), γ = 10 √
2, and ρX is the uniform distribution on the unit sphere in R2. To estimate eigenvalues and eigenfunctions, we draw 104-samples from ρX and M = 2× 104-hidden nodes of a two-layer ReLU.
Empirical observations. We observe gρ has the smallest norm with respect to the integral operator which specifies gρ and has a comparably small norm with respect to Σ∞ even for the cases where gρ is specified by Σa,∞ or Σb,∞. This observation suggests the efficiency of learning a corresponding layer to gρ and learning both layers, and it is empirically verified. We run Algorithm 1 10-times with respect to output (blue), input (purple), and both layers (orange) of two-layer swish networks with s = 10. Figure 2 (Bottom) depicts the average and standard deviation of test errors. From the figure, we see that learning a corresponding layer to gρ and both layers exhibit faster convergence, and that misspecification significantly slows down the convergence speed in all cases.

heading: 5 CONCLUSION
text: We analyzed the convergence of the averaged stochastic gradient descent for overparameterized twolayer neural networks for a regression problem. Through the development of a new proof strategy that does not rely on the positivity of the NTK, we proved that the global convergence (Theorem 1) relies only on the overparameterization. Moreover, we demonstrated the minimax optimal convergence rates (Corollary 1) in terms of the generalization error depending on the complexities of the target function and the hypothesis class and showed the explicit optimal rate for the smooth approximation of the ReLU.

heading: ACKNOWLEDGMENTS
text: AN was partially supported by JSPS Kakenhi (19K20337) and JST-PRESTO. TS was partially supported by JSPS KAKENHI (18K19793, 18H03201, and 20H00576), Japan Digital Design, and JST CREST.

heading: A PROOF SKETCH OF THE MAIN RESULTS
text: We provide several key results and a proof sketch of Theorem 1 and Corollary 1. We first recall the definition of stochastic gradients of L in a general RKHS (H, 〈, 〉H) associated with a uniformly bounded real-valued kernel function k : X × X → R. We set KX = k(X, ·). Then, it follows that for ∀g,∀h ∈ H,
L(g + h) = L(g) + 〈E[∂z`(g(X), Y )KX ], h〉H + o(‖h‖H),
which is confirmed by the following equations:
E[l((g + h)(X), Y )] = E[l(g(X), Y ) + ∂ζ l(g(X), Y )h(X) + o(|h(X)|)], h(X) = 〈h, k(X, ·)〉H, and |h(X)| ≤ ‖h‖H √ k(X,X). This means that the stochastic gradient of L inH is given by ∂ζ`(g(X), Y )k(X, ·) for (X,Y ) ∼ ρ. In addition, the stochastic gradient of the L2-regularized risk is given by ∂ζ`(g(X), Y )k(X, ·) + λg.
A. 1 REFERENCE AVERAGED STOCHASTIC GRADIENT DESCENT
We consider a random feature approximation of NTK k∞: for an initial value B(0) = (b (0) r )Mr=1, ∀x, ∀x′ ∈ X ,
kM (x, x ′) def =
1
M M∑ r=1 σ(b(0)>r x)σ(b (0)> r x ′) + (x>x′ + γ2) M M∑ r=1 σ′(b(0)>r x)σ ′(b(0)>r x ′), (5)
We can confirm that kM is an approximation of NTK, that is, kM converges to k∞ uniformly over supp(ρX) × supp(ρX) almost surely by the uniform law of large numbers. We denote by (HM , 〈, 〉HM ) an RKHS associated with kM . By the assumptions, we see kM (x, x
′) ≤ 12 for ∀(x, x′) ∈ supp(ρX)× supp(ρX). We introduce averaged stochastic gradient descent in HM (see Algorithm 2) as a reference for Algorithm 1. The notation G(t) represents a stochastic gradient at the t-th iterate:
G(t) def = ∂z`(g (t)(xt), yt)kM (xt, ·).
Algorithm 2 Reference ASGD inHM 1: Input: number of iterations T , regularization parameter λ, learning rates (ηt)T−10=1 , averaging
weights (αt)Tt=0,
2: g(0) ← 0 3: for t = 0 to T − 1 do 4: Randomly draw a sample (xt, yt) ∼ ρ 5: g(t+1) ← (1− ηtλ)g(t) − ηtG(t) 6: end for 7: Return g(T ) = ∑T t=0 αtg (t)
The following proposition shows the equivalence between the averaged stochastic gradient descent for two-layer neural networks and that inHM up to a small constant depending on M . Proposition A. Suppose Assumptions (A1) and (A2) hold. Run Algorithms 1 and 2 with the constant learning rate ηt = η satisfying ηλ < 1 and η ≤ 1. Moreover, assume that they share the same hyper-parameter settings and the same examples (xt, yt)T−1t=0 to compute stochastic gradient. Then, for arbitrary T ∈ Z+ and > 0, there exists M ∈ Z+ depending only on T and such that ∀t ≤ T ,
‖g Θ (t) − g(t)‖L∞(ρX) ≤ , (6)
where g Θ (t) and g(t) are iterates obtained by Algorithm 1 and 2, respectively.
Remark. Note that this proposition holds for non-averaged SGD too because it is a special case of averaged SGD by setting only one αt to 1.
Key idea. This proposition is the key because it connects two learning dynamics for neural networks and RKHS HM by utilizing overparameterization without the positivity of NTK unlike existing studies (Weinan et al., 2019; Arora et al., 2019b) that provide such a connection for continuous gradient flow with the positive NTK. Instead of the positivity of NTK, Proposition A says that overparameterization increases the time stayed in the NTK regime where the learning dynamics for neural networks can be characterized by the NTK. As a result, because M is free from the other hyper-parameters, the averaged stochastic gradient descent for the overparameterized two-layer neural networks can fully inherit preferable properties from learning dynamics inHM with an appropriate choice of learning rates and regularization parameters as long as the network width is sufficiently large depending only on the number of iterations and the required accuracy.
A. 2 CONVERGENCE RATE OF THE REFERENCE ASGD
We give the convergence analysis of Algorithm 2 inHM , which will be a part of a bound in Theorem 1. Proofs essentially rely on several techniques developed in serial studies (Bach & Moulines, 2013; Dieuleveut & Bach, 2016; Dieuleveut et al., 2017; Pillaud-Vivien et al., 2018a; Rudi & Rosasco, 2017; Carratino et al., 2018) with several adaptations to our settings.
Let M ∈ Z+ ∪ {∞} be a positive number or∞. We set KM,X def = kM (X, ·) and denote by ΣM the covariance operator defined by kM :
ΣM def = EX∼ρX [KM,X ⊗HM KM,X ].
We denote by gM,λ the minimizer of the regularized risk overHM :
gM,λ def = arg min
g∈HM
{ L(g) + λ
2 ‖g‖2HM
} .
We remark that ΣM : L2(ρX) → HM is isometric (Cucker & Smale, 2002), that is, ∀(f, g) ∈ L2(ρX)× L2(ρX), 〈
Σ 1/2 M f,Σ 1/2 M g 〉 HM = 〈f, g〉L2(ρX) ,
and we use this fact frequently. It is known that gM,λ is represented as follows (Caponnetto & De Vito, 2007):
gM,λ = (ΣM + λI) −1E(X,Y )[Y KM,X ]
= (ΣM + λI) −1ΣMgρ. (7)
The following theorem provides a convergence rate of Algorithm 2 to the minimizer gM,λ. Theorem A. Suppose Assumptions (A1), (A2) and (A3) hold. Run Algorithm 2 with the constant learning rate ηt = η satisfying 4(6+λ)η ≤ 1. Then, for ∀λ > 0 and ∀δ ∈ (0, 1) there existsM0 > 0 such that for ∀M ≥M0 the following holds with high probability at least 1− δ:
E [∥∥∥g(T ) − gM,λ∥∥∥2
L2(ρX)
] ≤ 4 η2(T + 1)2 ‖(ΣM + λI)−1gM,λ‖2L2(ρX)
+ 2 · 242
T + 1 ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX)
+ 8
T + 1
( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( ΣM (ΣM + λI) −1) , where g(T ) is an iterate obtained by Algorithm 2.
Remark. The first and second terms stem from the optimization speed of a semi-stochastic part of averaged stochastic gradient descent. The first term has a better dependency on T , but it has a worse dependency on λ than the second one. This kind of deterioration due to the weak strong convexity is common in first-order optimization methods. However, as confirmed later, these two
terms are dominated by the variance term corresponding to the third term by setting hyper-parameters appropriately.
To make the bound in Theorem A free from the size of M , we introduce the following proposition. Proposition B. Suppose gρ ∈ H∞ holds. Under Assumption (A1) and (A2), for any δ ∈ (0, 1), there exists M0 ∈ Z+ such that for any M ≥M0, the following holds with high probability at least 1− δ:
‖(ΣM + λI)−1gM,λ‖2L2(ρX) ≤ 2λ −1‖gρ‖2H∞ ,
‖(ΣM + λI)−1/2gM,λ‖2L2(ρX) ≤ 2‖gρ‖ 2 H∞ ,
and if λ ≤ ‖Σ∞‖op, then Tr ( ΣM (ΣM + λI) −1) ≤ 3Tr (Σ∞(Σ∞ + λI)−1) . Remark. The last inequality on the degree of freedom was shown in Rudi & Rosasco (2017).
To show the convergence to gρ, we utilize the following decomposition:
1 3 ‖g(T ) − gρ‖2L2(ρX) ≤ ‖g (T ) − gM,λ‖2L2(ρX) + ‖gM,λ − g∞,λ‖ 2 L2(ρX)
+ ‖g∞,λ − gρ‖2L2(ρX), (8)
where g∞,λ def = arg ming∈H∞{L(g) + λ2 ‖g‖ 2 H∞}.
The first term is the optimization speed evaluated in Theorem A, and the second and third terms are approximation errors from a random feature approximation of NTK and imposing L2-regularization, respectively. These approximation terms can be evaluated by the following existing results. The next proposition is a simplified version of Lemma 8 in Carratino et al. (2018) Proposition C (Carratino et al. (2018)). Under Assumption (A1), (A2), and (A3), for any , λ > 0 and δ ∈ (0, 1], there exists M0 ∈ Z+ depending on , λ, δ such that for any M ≥M0, the following holds with high probability at least 1− δ:
‖gM,λ − g∞,λ‖2L2(ρX) ≤ .
Proposition D (Caponnetto & De Vito (2007)). Under Assumption (A3), it follows that
‖g∞,λ − gρ‖2L2(ρX) ≤ λ 2r‖Σ−r∞ gρ‖2L2(ρX).
By combining Theorem A, Proposition B, C, and D with the decomposition (8), we can establish the convergence rate of reference ASGD to reach gρ, which is simply the generalization error bound. Theorem B. Assume the same conditions as in Theorem A. Then, for ∀ > 0, ‖Σ∞‖op ≥ ∀λ > 0, and ∀δ ∈ (0, 1), there exists M0 ∈ Z+ such that for ∀M ≥ M0, the following holds with high probability at least 1− δ over the random choice of random features Θ(0):
E [ ‖g(T ) − gρ‖2L2(ρX) ] ≤ + 3λ2r‖Σ−r∞ gρ‖2L2(ρX)
+ 24
T + 1
( 288 +
1
λη2(T + 1)
) ‖gρ‖2H∞
+ 24
T + 1
( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( Σ∞(Σ∞ + λI) −1) , where g(T ) is an iterate obtained by Algorithm 2.
A. 3 CONVERGENCE RATES OF ASGD FOR NEURAL NETWORKS
As explained earlier, the generalization bound for the reference ASGD is inherited by that for twolayer neural networks through Proposition A with the following decomposition: for an iterate ΘT obtained by Algorithm 1,
‖g Θ (T ) − gρ‖L2(ρX) ≤ ‖gΘ(T ) − g (T )‖L2(ρX) + ‖g (T ) − gρ‖L2(ρX).
That is, these two terms are bounded by Proposition A and Theorem B under Assumption (A1)-(A3), resulting in Theorem 1, which exhibits comparable generalization error to Theorem B as long as the network width M is sufficiently large.
Theorem 1 immediately leads to the fast convergence rate in Corollary 1 by setting ηt = η = O(1) satisfying 4(6 + λ)η ≤ 1 and λ = T−β/(2rβ+1) with the bounds on ‖gρ‖2H∞ , ‖gρ‖ 2 L2(ρX)
, and the degree of freedom. Because β in Assumption (A4) controls the complexity of the hypothesis space H∞, it derives a bound on the degree of freedom, as shown in Caponnetto & De Vito (2007):
Tr ( Σ∞(Σ∞ + λI) −1) = O(λ−1/β). In addition, the boundedness of ‖Σ∞‖op ≤ O(1) gives
‖gρ‖H∞ = ‖Σ r− 12∞ Σ −r ∞ gρ‖L2(ρX) ≤ O ( ‖Σ−r∞ gρ‖L2(ρX) ) , ‖gρ‖L2(ρX) ≤ ‖Σ r ∞Σ −r ∞ gρ‖L2(ρX) ≤ O ( ‖Σ−r∞ gρ‖L2(ρX) ) .
This finishes the proof of Corollary 1.

heading: B PROOF OF PROPOSITION A
text: We first show the Proposition A that says the equivalence between averaged stochastic gradient descent for two-layer neural networks and that in an RKHS associated with kM .
Proof. Proof of Proposition A
Bound the growth of ‖gΘ(t)‖L∞(ρX). We first show that there exist increasing functions d(t) and M(t) depending only on t uniformly over the choice of the history of examples (xt, yt)∞t=1 used in Algorithms such that ‖gΘ(s)‖L∞(ρX) ≤ d(t) for ∀s ≤ t when M ≥M(t). We show this statement by the induction.
Without loss of generality, we assume that there is no bias term, ‖b(0)r ‖2 = 1, and supp(ρX) ⊂ {x ∈ Rd+1 | ‖x‖2 ≤ 2} by setting x← (x, γ) (where γ ∈ (0, 1)). Hence, we consider the update only for parameters a and B. The above statement clearly holds for t = 0. Thus, we assume it holds for t. We recall the specific update rules of the stochastic gradient descent:
a(t+1)r − a(0)r = (1− ηλ)(a(t)r − a(0)r )− η√ M (gΘ(t)(xt)− yt)σ(b(t)>r xt), (9) b(t+1)r − b(0)r = (1− ηλ)(b(t)r − b(0)r )− η√ M (gΘ(t)(xt)− yt)a(t)r σ′(b(t)>r xt)xt. (10)
Here, let us consider ∀M ≥ M(t). Set dMb (t) = maxs≤t,1≤r≤M ‖b (s) r ‖2. Then, by expanding equation (9), we get
|a(t+1)r − a(0)r | ≤ |a(t)r − a(0)r |+ η√ M (d(t) + 1)(1 + 2dMb (t))
≤ η√ M t∑ s=0 (d(s) + 1)(1 + 2dMb (t))
≤ η(t+ 1)√ M (d(t) + 1)(1 + 2dMb (t)), (11)
where we used ‖σ(u)‖ ≤ 1 + u and |yt| ≤ 1. As for the term |a(s)r | (s ≤ t + 1), from the similar augment for s and the monotonicity, we have for s ≤ t+ 1,
|a(s)r | ≤ 1 + |a(s)r − a(0)r |
≤ 1 + η(t+ 1)√ M (d(t) + 1)(1 + 2dMb (t))
≤ 1 + η(t+ 1)(d(t) + 1)(1 + 2dMb (t)).
We next give a bound on ‖b(t+1)r − b(0)r ‖2. By expanding equation (10), we get
‖b(t+1)r − b(0)r ‖2 ≤ ‖b(t)r − b(0)r ‖2 + 4η√ M |a(t)r |(d(t) + 1)
≤ 4η√ M t∑ s=0 |a(s)r |(d(s) + 1)
≤ 4η(t+ 1)√ M (d(t) + 1)
( 1 +
η(t+ 1)√ M (d(t) + 1)(1 + 2dMb (t))
) , (12)
where we used ‖σ′‖∞ ≤ 2 and ‖xt‖2 ≤ 2. Here, we evaluate dMb (t). From the similar augment for s ≤ t, the monotonicity, and ‖b(s)r ‖2 ≤ 1 + ‖b(s)r − b(0)r ‖2, we get
dMb (t) ≤ 1 + 4η(t+ 1)√
M (d(t) + 1)
( 1 +
η(t+ 1)√ M (d(t) + 1)(1 + 2dMb (t))
) .
Let M ′(t + 1) be a positive integer depending on t and d(t) such that t+1√ M (d(t) + 1) ≤ 14 . Let us reconsider ∀M ≥M ′(t+ 1). Then, since η ≤ 1, we have
dMb (t) ≤ 5
2 , |a(s)r | ≤
5 2 (∀s ≤ t+ 1).
From the derivation of (11) and (12) and since η ≤ 1, we have for 0 ≤ ∀s ≤ t+ 1,
|a(s)r − a(0)r | ≤ d1(t+ 1)√
M , ‖b(s)r − b(0)r ‖2 ≤ d2(t+ 1)√ M , (13)
where d1(t+ 1) and d2(t+ 1) are set to
d1(t+ 1) def = 6(t+ 1)(d(t) + 1), d2(t+ 1) def = 10(t+ 1)(d(t) + 1).
We next bound |gΘ(t+1)(x)| for x ∈ ∀supp(ρX) as follows. Since gΘ(0) ≡ 0, |gΘ(t+1)(x)| = |gΘ(t+1)(x)− gΘ(0)(x)|
≤ 1√ M M∑ r=1 {∣∣∣(a(t+1)r − a(0)r )σ(b(0)>r x)∣∣∣+ ∣∣∣a(t+1)r (σ(b(t+1)>r x))− σ(b(0)>r x)∣∣∣} ≤ 1√
M M∑ r=1 { 2 ∣∣∣a(t+1)r − a(0)r ∣∣∣+ 4 ∣∣∣a(t+1)r ∣∣∣ ∥∥∥b(t+1)r − b(0)r ∥∥∥}
≤ 2d1(t+ 1) + 10d2(t+ 1).
In summary, by setting M(t + 1) = max{M(t), 16(t + 1)2(d(t) + 1)2} and d(t + 1) = 2d1(t + 1) + 10d2(t + 1), we get ‖gΘ(t+1)‖L∞(ρX) ≤ d(t + 1) when M ≥ M(t + 1). We note that from the above construction, d(t), d1(t), d2(t) depend only on t and inequalities (13) are always hold for ∀t ∈ Z+ when M ≥M(t+ 1).
Linear approximation of the model. For a given T ∈ Z+, we consider ∀M ≥M(T ) and define the neighborhood of Θ(0) = (a(0)r , b (0) r )Mr=1:
BT (Θ (0)) def = { (ar, br) M r=1 ∈ (R× Rd+1)M | |ar| ≤ 5
2 , |ar − a(0)r | ≤ d1(T )√ M , ‖br − b(0)r ‖2 ≤ d2(T )√ M
} .
From Taylor’s formula |σ(b>r x) − σ(b (0)> r x) − σ′(b(0)>r x)(br − b(0)r )>x| ≤ 2‖σ′′‖∞‖br − b(0)r ‖22 and the smoothness of σ, we get for Θ ∈ BT (Θ(0)) and x ∈ supp(ρX),∣∣arσ(b>r x)− (a(0)r σ(b(0)>r x) + (ar − a(0)r )σ(b(0)>r x) + a(0)r σ′(b(0)>r x)(br − b(0)r )>x)∣∣ ≤ 4|ar − a(0)r |‖br − b(0)r ‖2 + 2C|ar|‖br − b(0)r ‖22
≤ 2d1(T )d2(T ) M + 5Cd22(T ) M . (14)
We here define a linear model:
hΘ(x) def = 1√ M M∑ r=1 ( (ar − a(0)r )σ(b(0)>r x) + a(0)r σ′(b(0)>r x)(br − b(0)r )>x ) .
By taking the sum of (14) over r ∈ {1, . . . ,M} and by gΘ(0) ≡ 0,
|gΘ(x)− hΘ(x)| ≤ 1√ M M∑ r=1 ( 2d1(T )d2(T ) M + 5Cd22(T ) M ) ≤ 1√
M
( 2d1(T )d2(T ) + 5Cd 2 2(T ) ) .
We denote d3(T ) def = 2d1(T )d2(T ) + 5Cd 2 2(T ). Since iterates (Θ (t))Tt=0 obtained by Algorithm 1 are contained in BT (Θ(0)), weighted averages (Θ (t) )Tt=0 are also contained in BT (Θ (0)). Thus, we get for ∀t ∈ {1, . . . , T},
|gΘ(t)(x)− hΘ(t)(x)| ≤ d3(T )√ M
, ∣∣∣g
Θ (t)(x)− h Θ (t)(x) ∣∣∣ ≤ d3(T )√ M . (15)
Recursion of hΘ(t) using the random feature approximation of NTK. We here derive a recursion of hΘ(t) using kM . From the updates (9) and (10), we have
hΘ(t+1)(x) = 1√ M M∑ r=1 ( (a(t+1)r − a(0)r )σ(b(0)>r x) + a(0)r σ′(b(0)>r x)(b(t+1)r − b(0)r )>x ) = (1− ηλ)hΘ(t)(x)− η
M M∑ r=1 (gΘ(t)(xt)− yt)σ(b(t)>r xt)σ(b(0)>r x)
− η M M∑ r=1 a(0)r σ ′(b(0)>r x)(gΘ(t)(xt)− yt)a(t)r σ′(b(t)>r xt)x>t x. (16)
Note that for t ∈ {0, . . . , T},
|(gΘ(t)(xt)− yt)σ(b(t)>r xt)− (hΘ(t)(xt)− yt)σ(b(0)>r xt)| ≤ |(gΘ(t)(xt)− hΘ(t)(xt))σ(b(0)>r xt)|+ |(gΘ(t)(xt)− yt)(σ(b(t)>r xt)− σ(b(0)>r xt))|
≤ 2d3(T )√ M + 4(d(T ) + 1)‖b(t)r − b(0)r ‖2
≤ 2√ M (d3(T ) + 2(d(T ) + 1)d2(T )) ,
and
|(gΘ(t)(xt)− yt)a(t)r σ′(b(t)>r xt)− (hΘ(t)(xt)− yt)a(0)r σ′(b(0)>r xt)| ≤ |(gΘ(t)(xt)− hΘ(t)(xt))a(0)r σ′(b(0)>r xt)|+ |(gΘ(t)(xt)− yt)(a(t)r σ′(b(t)>r xt)− a(0)r σ′(b(0)>r xt))|
≤ 2d3(T )√ M + (d(T ) + 1)|a(t)r σ′(b(t)>r xt)− a(0)r σ′(b(0)>r xt))|
≤ 2d3(T )√ M
+ (d(T ) + 1) { |a(0)r (σ′(b(t)>r xt)− σ′(b(0)>r xt))|+ |(a(t)r − a(0)r )σ′(b(t)>r xt)| } ≤ 2d3(T )√
M + 2(d(T ) + 1)
{ C‖b(t)r − b(0)r ‖2 + |a(t)r − a(0)r | } ≤ 2d3(T )√
M + 2(d(T ) + 1)√ M (d1(T ) + Cd2(T ))
= 2√ M (d3(T ) + (d(T ) + 1)(d1(T ) + Cd2(T ))) .
Plugging these two inequalities into (16), we have ∀t ∈ {1, . . . , T − 1},
hΘ(t+1)(x) ≤ (1− ηλ)hΘ(t)(x)− η
M M∑ r=1 (hΘ(t)(xt)− yt)σ(b(0)>r xt)σ(b(0)>r x)
− η M M∑ r=1 σ′(b(0)>r x)(hΘ(t)(xt)− yt)σ′(b(0)>r xt)x>t x
+ 2η√ M (2d3(T ) + (d(T ) + 1) (d1(T ) + (C + 2)d2(T )))
= (1− ηλ)hΘ(t)(x)− η(hΘ(t)(xt)− yt) 1
M M∑ r=1 ( σ(b(0)>r xt)σ(b (0)> r x) + σ ′(b(0)>r x)σ ′(b(0)>r xt)x > t x )
+ 2η√ M (2d3(T ) + (d(T ) + 1) (d1(T ) + (C + 2)d2(T ))) = (1− ηλ)hΘ(t)(x)− η(hΘ(t)(xt)− yt)kM (x, xt) + η√ M d4(T ),
where d4(T ) = 2d3(T ) + (d(T ) + 1) (d1(T ) + (C + 2)d2(T )). Clearly, the inverse inequality also holds:
hΘ(t+1)(x) ≥ (1− ηλ)hΘ(t)(x)− η(hΘ(t)(xt)− yt)kM (x, xt)− η√ M d4(T ).
Thus, we get
|hΘ(t+1)(x)− (1− ηλ)hΘ(t)(x) + η(hΘ(t)(xt)− yt)kM (x, xt)| ≤ η√ M d4(T ). (17)
Equivalence between Algorithm 1 and 2. We provide a bound between recursions of Algorithm 2 and (17). Noting that hΘ(0) ≡ g(0) ≡ 0, we have for ∀t ∈ {0, . . . , T − 1},
|hΘ(t+1)(x)− g(t+1)(x)| ≤ (1− ηλ)|hΘ(t)(x)− g(t)(x)|+ η|hΘ(t)(xt)− g(t)(xt)|kM (x, xt) + η√ M d4(T ).
Noting ‖kM‖L∞(ρX) ≤ 12 and taking a supremum over x, xt ∈ supp(ρX) in both sides, we have
‖hΘ(t+1) − g(t+1)‖L∞(ρX) ≤ (1− ηλ)‖hΘ(t) − g (t)‖L∞(ρX) + η‖hΘ(t) − g (t)‖L∞(ρX)‖kM‖L∞(ρX) + η√ M d4(T )
≤ (1− ηλ+ 12η)‖hΘ(t) − g(t)‖L∞(ρX) + η√ M d4(T )
≤ t∑
s=0
(1 + 12η)t−s η√ M d4(T )
≤ T√ M (1 + 12η)T d4(T ).
Since hΘ is a linear model, we have hΘ(T ) = ∑T t=0 αthΘ(t) and
‖h Θ (T ) − g(T )‖L∞(ρX) ≤ T∑ t=0 αt‖hΘ(t) − g(t)‖L∞(ρX) ≤ T√ M (1 + 12η)T d4(T ).
Combining this inequality with (15), we finally have
‖g Θ (T ) − g(T )‖L∞(ρX) ≤ ‖gΘ(T ) − hΘ(T )‖L∞(ρX) + ‖hΘ(T ) − g (T )‖L∞(ρX)
≤ 1√ M (d3(T ) + 13 TTd4(T )).
Because (d3(T ) + 13TTd4(T )) depends only on T and C from the construction, ‖gΘ(T ) − g(T )‖L∞(ρX) → 0 as M →∞. This finishes the proof of Proposition A.

heading: C PROOF OF THEOREM A
text: In this section, we give the proof of the convergence theory for the reference ASGD (Algorithm 2). We introduce an auxiliary result for proving Theorem A.
Lemma A. Suppose Assumption (A1), (A2), and (A3) hold. Set ξ def= Y KM,X − (KM,X ⊗HM KM,X + λI)gM,λ. Then, for ∀λ > 0 and ∀δ ∈ (0, 1) there exists M0 > 0 such that for ∀M ≥M0 the following holds with high probability at least 1− δ:
E(X,Y )∼ρ[ξ ⊗HM ξ] 4 2(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))ΣM .
Proof. Since ξ = (Y − gM,λ(X))KM,X − λgM,λ, we get E[ξ ⊗HM ξ] = E[(Y − gM,λ(X))2KM,X ⊗HM KM,X ]
− λE[(Y − gM,λ(X))KM,X ]⊗HM gM,λ − λgM,λ ⊗HM E[(Y − gM,λ(X))KM,X ] + λ2gM,λ ⊗HM gM,λ.
We evaluate an expectation in the second and third terms in the right hand side of the above equation as follows:
E[(Y − gM,λ(X))KM,X ] = E[Y KM,X − (KM,X ⊗HM KM,X)gM,λ] = E[Y KM,X ]− ΣMgM,λ = E[Y KM,X ]− ΣM (ΣM + λI)−1E[Y KM,X ] = E[Y KM,X ]− (ΣM + λI − λI)(ΣM + λI)−1E[Y KM,X ] = λ(ΣM + λI)
−1E[Y KM,X ] = λgM,λ.
Hence, we get E[ξ ⊗HM ξ] 4 E[(Y − gM,λ(X))2KM,X ⊗HM KM,X ]. For h ∈ HM ,〈 E[(Y − gM,λ(X))2KM,X ⊗HM KM,X ]h, h 〉 HM
= E[(Y − gM,λ(X))2 〈(KM,X ⊗HM KM,X)h, h〉HM ] ≤ ‖Y − gM,λ(X)‖2L∞(ρX)E[〈(KM,X ⊗HM KM,X)h, h〉HM ]
≤ 2(1 + ‖gM,λ‖2L∞(ρX))E[〈(KM,X ⊗HM KM,X)h, h〉HM ], (18) where we used Assumption (A2) for the last inequality.
Finally, we provide an upper-bound on ‖gM,λ‖L∞(ρX). Since S−1 − T−1 = −S−1(S − T )T−1 for arbitrary operators S and T , we get
‖ ( (Σ∞ + λI) −1 − (ΣM + λI)−1 ) gρ‖L2(ρX)
= ‖(Σ∞ + λI)−1(Σ∞ − ΣM )(ΣM + λI)−1gρ‖L2(ρX) = ‖(Σ∞ + λI)−1‖op‖Σ∞ − ΣM‖op‖(ΣM + λI)−1‖op‖gρ‖L2(ρX)
≤ 1 λ2 ‖Σ∞ − ΣM‖op‖gρ‖L2(ρX). (19)
We denote F∞ = (Σ∞ + λI)−1gρ and FM = (ΣM + λI)−1gρ. Noting g∞,λ = Σ∞F∞ and gM,λ = ΣMFM , we get for ∀x ∈ supp(ρX), |g∞,λ(x)− gM,λ(x)| = |Σ∞F∞(x)− ΣMFM (x)|
= ∣∣∣∣∫ X K∞,x(X)F∞(X)dρX − ∫ X KM,x(X)FM (X)dρX ∣∣∣∣ =
∣∣∣∣∫ X (K∞,x −KM,x)(X)F∞(X)dρX − ∫ X KM,x(X)(FM (X)− F∞(X))dρX ∣∣∣∣ ≤ ‖K∞,x −KM,x‖L2(ρX)‖F∞‖L2(ρX) + ‖KM,x‖L2(ρX)‖FM − F∞‖L2(ρX)
≤ 1 λ ‖k∞ − kM‖L∞(ρX)2‖gρ‖L2(ρX) + 12 λ2 ‖Σ∞ − ΣM‖op‖gρ‖L2(ρX),
where we used kM (x, x′) ≤ 12 for ∀(x, x′) ∈ supp(ρX)× supp(ρX) and inequality (19). Moreover, we get
|g∞,λ(x)| = | 〈g∞,λ,Kx〉H∞ | ≤ ‖Kx‖H∞‖g∞,λ‖H∞ ≤ 2 √
3‖Σ∞(Σ∞ + λI)−1gρ‖H∞ ≤ 2 √
3‖Σ1+r∞ (Σ∞ + λI)−1Σ−r∞ gρ‖H∞ ≤ 2 √ 3‖Σ 1 2 +r∞ (Σ∞ + λI) −1Σ−r∞ gρ‖L2(ρX) ≤ 2 √ 3‖Σ 1 2 +r∞ (Σ∞ + λI)
−1‖op‖Σ−r∞ gρ‖L2(ρX) ≤ 2 √
3‖Σ−r∞ gρ‖L2(ρX). (20)
where we used Assumption (A3) and the isometric map Σ1/2∞ : L2(ρX)→ H∞. Hence, we get
‖gM,λ‖L∞(ρX) ≤ ( 1
λ ‖k∞ − kM‖L∞(ρX)2 +
12 λ2 ‖Σ∞ − ΣM‖op
) ‖gρ‖L2(ρX) + 2 √ 3‖Σ−r∞ gρ‖L2(ρX).
By the uniform law of large numbers (Theorem 3.1 in Mohri et al. (2012)) and the Bernstein’s inequality (Proposition 3 in Rudi & Rosasco (2017)) to random operators, ‖k∞ − kM‖L∞(ρX×ρX) and ‖Σ∞ − ΣM‖op converge to zero as M → ∞ in probability. That is, for given λ > 0 and δ ∈ (0, 1), there exists M0 such that for any M ≥M0 the following holds with high probability at least 1− δ:
‖gM,λ‖L∞(ρX) ≤ 1
2 ‖gρ‖L2(ρX) + 2
√ 3‖Σ−r∞ gρ‖L2(ρX).
Combining with (18), we get〈 E[(Y − gM,λ(X))2KM,X ⊗HM KM,X ]h, h 〉 HM
≤ 2(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))E[〈(KM,X ⊗HM KM,X)h, h〉HM ].
Proof of Theorem A. Since, stochastic gradient inHM is described as
G(t) = ∂z`(g (t)(xt), yt)kM (xt, ·) = (〈 KM,xt , g (t) 〉 HM − yt ) KM,xt ,
the update rule of Algorithm 2 is g(t+1) = (1− ηλ)g(t) − η (〈 KM,xt , g (t) 〉 HM − yt ) KM,xt
= (I − ηKM,xt ⊗HM KM,xt − ηλI) g(t) + ηytKM,xt .
Hence, we get
g(t+1) − gM,λ = (I − ηKM,xt ⊗HM KM,xt − ηλI)︸ ︷︷ ︸ =αt (g(t) − gM,λ)︸ ︷︷ ︸ =At
−η(KM,xt ⊗HM KM,xt + λI)gM,λ + ηytKM,xt︸ ︷︷ ︸ =βt . (21)
This leads to the following stochastic recursion: t ∈ {0, . . . , T − 1},
At+1 = αtAt + βt = t∏ s=0 αsA0 + t∑ s=0 t∏ l=s+1 αsβs.
By taking the average, we get
AT = 1
T + 1 T∑ t=0 At
= 1
T + 1 T∑ t=0 t∏ s=0
αsA0︸ ︷︷ ︸ Bias term
+ 1
T + 1 T∑ t=0 t∑ s=0 t∏ l=s+1
αsβs︸ ︷︷ ︸ Noise term . (22)
Thus, the averageAT is composed of bias and noise terms. We next bound these two terms, separately.
Bound the bias term. Note that the bias term exactly corresponds to the recursion (21) with βt = 0. Hence, we consider the case of βt = 0 and consider the following stochastic recursion in HM : A0 = −gM,λ, At+1 = (I − ηHt − ηλI)At, where we define Ht = KM,xt ⊗HM KM,xt . In addition, we consider the deterministic recursion of this recursion: A′0 = A0, A′t+1 = (I − ηΣM − ηλI)A′t. We set
AT = 1
T + 1 T∑ t=0 At, A′T = 1 T + 1 T∑ t=0 A′t.
Then, the bias term we want to evaluate is decomposed as follows: by Minkowski’s inequality,( E[‖AT ‖2L2(ρX)] ) 1 2 ≤ ‖A′T ‖L2(ρX) + ( E[‖AT −A′T ‖2L2(ρX)] ) 1 2 . (23)
We here bound the first term in the right hand side of (23). Note that from 4(6 + λ)η ≤ 1 and ‖kM‖L∞(ρX)2 ≤ 12, we see 1 η(ΣM+λI) 4 η(12+λ)I ≺ 12I . SinceA ′ t = (I−ηΣM−ηλI)tgM,λ, its average is
A′T = 1
T + 1 T∑ t=0 A′t = 1 η(T + 1) (ΣM + λI) −1(I − (I − ηΣM − ηλ)T+1)gM,λ.
Therefore,
‖A′T ‖L2(ρX) = 1 η(T + 1) ‖(ΣM + λI)−1(I − (I − ηΣM − ηλ)T+1)gM,λ‖L2(ρX)
≤ 1 η(T + 1) ‖(ΣM + λI)−1gM,λ‖L2(ρX). (24)
We bound the second term in (23), which measures the gap between AT and A′T . To do so, we consider the following recursion:
At+1 −A′t+1 = At −A′t − η(Ht + λI)(At −A′t) + η(ΣM −Ht)A′t.
Hence, we have
‖At+1 −A′t+1‖2HM = ‖At −A ′ t‖2HM
− η 〈At −A′t, (Ht + λI)(At −A′t)− (ΣM −Ht)A′t〉HM − η 〈(Ht + λI)(At −A′t)− (ΣM −Ht)A′t, At −A′t〉HM + η2‖(Ht + λI)(At −A′t)− (ΣM −Ht)A′t‖2HM .
1In general, for any operator F : L2(ρX) → L2(ρX) that commutes with ΣM and has a common eigenbases with ΣM , it follows that F (HM ) ⊂ HM and inequality F < 0 in L2(ρX) is equivalent with F |HM< 0. Hence, we do not specify a Hilbert space we consider in such a case for the simplicity.
Let (Ft)T−1t=0 be a filtration. We take a conditional expectation given Ft: E[‖At+1 −A′t+1‖2HM | Ft] ≤ ‖At −A ′ t‖2HM − 2η 〈(ΣM + λI)(At −A ′ t), At −A′t〉HM
+ 2η2E[‖(Ht + λI)(At −A′t)‖2HM | Ft] (25) + 2η2E[‖(ΣM −Ht)A′t‖2HM | Ft], (26)
where we used ‖g + h‖2HM ≤ 2(‖g‖ 2 HM + ‖h‖ 2 HM ). For g ∈ HM , we have〈 E[(KM,xt ⊗HM KM,xt)2]g, g 〉 HM = E [〈 (KM,xt ⊗HM KM,xt)2g, g 〉 HM
] = E [〈 〈KM,xt , g〉HM (KM,xt ⊗HM KM,xt)KM,xt , g 〉 HM
] = E [〈 〈KM,xt , g〉HM kM (xt, xt)KM,xt , g 〉 HM
] = E [ 〈KM,xt , g〉 2 HM kM (xt, xt)
] ≤ 12E [ 〈KM,xt , g〉 2 HM
] = 12 〈E [KM,xt ⊗HM KM,xt ] g, g〉HM . (27)
where we used kM (xt, xt) ≤ 12 which is confirmed from the definition of kM and Assumption (A2). This means that E[H2t ] = E[(KM,xt ⊗HM KM,xt)2] 4 12ΣM on HM × HM . Hence, we get a bound on (25) as follows: E[‖(Ht + λI)(At −A′t)‖2HM | Ft] = E[ 〈 (Ht + λI) 2(At −A′t), At −A′t 〉 HM | Ft]
= 〈( λ2I + 2λΣM + E[(KM,xt ⊗HM KM,xt)2] ) (At −A′t), At −A′t 〉 HM
≤ 〈( λ2I + 2(6 + λ)ΣM ) (At −A′t), At −A′t 〉 HM .
Next, we bound a term (26): E[‖(ΣM −Ht)A′t‖2HM | Ft] = E[ 〈 (ΣM −Ht)2A′t, A′t 〉 HM | Ft]
= E[ 〈 (Σ2M − ΣMHt −HtΣM +H2t )A′t, A′t 〉 HM | Ft]
= 〈 (E[H2t ]− Σ2M )A′t, A′t 〉 HM
≤ 〈 E[H2t ]A′t, A′t 〉 HM ≤ 12 〈ΣMA′t, A′t〉HM .
Combining these inequalities, we get E[‖At+1 −A′t+1‖2HM | Ft] ≤ ‖At −A ′ t‖2HM − 2η 〈(ΣM + λI)(At −A ′ t), At −A′t〉HM
+ 2η2 〈( λ2I + 2(6 + λ)ΣM ) (At −A′t), At −A′t 〉 HM + 24η2 〈ΣMA′t, A′t〉HM = (1− 2λη + 2λ2η2)‖At −A′t‖2HM − 2η 〈ΣM (At −A ′ t), At −A′t〉HM + 4η2(6 + λ) 〈ΣM (At −A′t), At −A′t〉HM + 24η2 〈ΣMA′t, A′t〉HM ≤ ‖At −A′t‖2HM − η 〈ΣM (At −A ′ t), At −A′t〉HM
+ 24η2 〈ΣMA′t, A′t〉HM , (28) where for the last inequality we used 4η(6 + λ) ≤ 1. By taking the expectation and the average of (28) over t ∈ {0, . . . , T − 1}, we get
1
T + 1 T∑ t=0 〈ΣM (At −A′t), At −A′t〉HM ≤ 24η T + 1 T∑ t=0 〈ΣMA′t, A′t〉HM .
Since Σ1/2M : L2(ρX)→ HM is isometric, we see ‖Σ 1/2 M (At −A′t)‖HM = ‖At −A′t‖L2(ρX). Thus, the second term in (23) can be bounded as follows:
E[‖AT −A′T ‖2L2(ρX)] = E[‖Σ 1/2 M (AT −A′T )‖ 2 HM ]
≤ 1 T + 1 T∑ t=0 E[‖Σ1/2M (At −A ′ t)‖2HM ]
≤ 24η T + 1 T∑ t=0 ‖Σ1/2M A ′ t‖2HM
= 24η
T + 1 T∑ t=0 ‖Σ1/2M (I − ηΣM − ηλI) tgM,λ‖2HM
= 24η
T + 1 〈 T∑ t=0 (I − ηΣM − ηλI)2tΣ1/2M gM,λ,Σ 1/2 M gM,λ 〉 HM
≤ 24 T + 1
〈 (ΣM + λI) −1Σ 1/2 M gM,λ,Σ 1/2 M gM,λ 〉 HM
= 24
T + 1 ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX) (29)
where we used the convexity for the first inequality and we used the following inequality for the last inequality: since ‖kM‖L∞(ρX)2 ≤ 12 and η(ΣM + λI) 4 η(12 + λ)I 4 12I ,
T∑ t=0 (I − ηΣM − ηλI)2t 4 1 η (ΣM + λI) −1.
By plugging (24) and (29) into (23), we get the bound on the bias term:
E[‖AT ‖2L2(ρX)] ≤ 2‖A′T ‖ 2 L2(ρX) + 2E[‖AT −A′T ‖2L2(ρX)]
≤ 2 η2(T + 1)2 ‖(ΣM + λI)−1gM,λ‖2L2(ρX) + 242 T + 1 ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX).
(30)
Bound the noise term. Note that the noise term in (22) exactly corresponds to the recursion (21) with A0 = 0. Hence, it is enough to consider the case of A0 = 0 to evaluate the noise term. In this case, the average AT can be rewritten as follows:
AT = 1
T + 1 T∑ t=0 t∑ s=0 t∏ l=s+1 αlβs = η T + 1 T∑ s=0 T∑ t=s t∏ l=s+1
αl βs η︸ ︷︷ ︸
=Zs
.
We here evaluate the noise term. We set zs = (xs, ys). Note that since Ezs [βs] = 0, we have for s < s′, E(zs,...,zT ) [ 〈Zs, Zs′〉L2(ρX) ] = ∫ X E(zs,...,zT ) [( T∑ t=s t∏ l=s+1 αl βs η )( T∑ t=s′ t∏ l=s′+1 αl βs′ η )] dρX
= ∫ X Ezs [βs]E(zs+1,...,zT ) [ βs′ ( T∑ t=s t∏ l=s+1 αl η )( T∑ t=s′ t∏ l=s′+1 αl η )] dρX
= 0.
Therefore, we have
E[‖AT ‖2L2(ρX)] = η2
(T + 1)2 E ∥∥∥∥∥ T∑ s=0 Zs ∥∥∥∥∥ 2
L2(ρX)  = η2
(T + 1)2 E  T∑ s,s′=0 〈Zs, Zs′〉L2(ρX)  = η2
(T + 1)2 T∑ s=0 E [ 〈Zs, Zs〉L2(ρX) ] = η2
(T + 1)2 T∑ s=0 E [ ‖Σ1/2M Zs‖ 2 HM ] . (31)
Here, we apply Lemma 21 in Pillaud-Vivien et al. (2018a) with A = ΣM , H = ΣM + λI , C = 2(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))ΣM . One of required conditions in this lemma is verified by Lemma A. We verify the other required condition described below:
E [ (KM,X ⊗H KM,X + λI)CH−1(KM,X ⊗H KM,X + λI) ] 4 1
η C. (32)
Indeed, we have E [ (KM,X ⊗H KM,X + λI)CH−1(KM,X ⊗H KM,X + λI) ] = E [ KM,X ⊗H KM,XCH−1KM,X ⊗H KM,X ] + 2λΣMCH −1 + λ2CH−1
4 E [ KM,X ⊗H KM,XCH−1KM,X ⊗H KM,X ] + 6λ(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))ΣM ,
where we used ΣM (ΣM + λI)−1 4 I and λ(ΣM + λI)−1 4 I . Moreover, we see E [ KM,X ⊗H KM,XCH−1KM,X ⊗H KM,X ] = 2(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))E [ KM,X ⊗H KM,XΣM (ΣM + λI)−1KM,X ⊗H KM,X
] 4 2(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))E [ (KM,X ⊗H KM,X)2
] 4 24(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))ΣM ,
where we used (27) for the last inequality. Hence, we get E [ (KM,X ⊗H KM,X + λI)CH−1(KM,X ⊗H KM,X + λI) ] 4 (24 + 6λ)(1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX))ΣM .
Since, 4η(6 + λ) ≤ 1, the condition (32) is verified. We apply Lemma 21 in Pillaud-Vivien et al. (2018a) to (31), yielding the following inequality:
E[‖AT ‖2L2(ρX)] ≤ 4
T + 1
( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( Σ2M (ΣM + λI) −2) ≤ 4 T + 1 ( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( ΣM (ΣM + λI)
−1) . (33) Convergence rate in terms of the optimization. Finally, by combining (30) and (33) with (22), we get the convergence rate of averaged stochastic gradient descent to gM,λ:
E [∥∥∥g(T ) − gM,λ∥∥∥2
L2(ρX)
] ≤ 4 η2(T + 1)2 ‖(ΣM + λI)−1gM,λ‖2L2(ρX)
+ 2 · 242
T + 1 ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX)
+ 8
T + 1
( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( ΣM (ΣM + λI) −1) , where g(T )
def = 1T+1 ∑T t=0 g (t). This finishes the proof.

heading: D PROOF OF PROPOSITION B
text: We provide Proposition B which provides the bound on Theorem A.
Proof of Proposition B. From the Bernstein’s inequality (Proposition 3 in Rudi & Rosasco (2017)) to random operators, the covariance operator ΣM converges to Σ∞ as M → ∞ in probability. Especially, there exits M0 ∈ Z+ such that for any M ≥M0, it follows that with high probability at least 1− δ, Σ∞ − ΣM 4 12 (Σ∞ + λI) in L2(ρX). Thus, for ∀f ∈ L2(ρX), we see〈
(Σ∞ + λI) −1/2(Σ∞ − ΣM )(Σ∞ + λI)−1/2f, f 〉 L2(ρX)
= 〈 (Σ∞ − ΣM )(Σ∞ + λI)−1/2f, (Σ∞ + λI)−1/2f 〉 L2(ρX)
≤ 1 2
〈 (Σ∞ + λI)(Σ∞ + λI) −1/2f, (Σ∞ + λI) −1/2f 〉 L2(ρX)
= 1
2 ‖f‖2L2(ρX).
Hence, we have
(Σ∞ + λI) −1/2(Σ∞ − ΣM )(Σ∞ + λI)−1/2 4
1 2 I.
Following the argument in Bach (2017b), we have for ∀f ∈ L2(ρX),〈 (ΣM + λI) −1f, f 〉 L2(ρX)
= 〈 (Σ∞ + λI + ΣM − Σ∞)−1f, f 〉 L2(ρX)
= 〈( I + (Σ∞ + λI) −1/2(ΣM − Σ∞)(Σ∞ + λI)−1/2 )−1 (Σ∞ + λI) −1/2f, (Σ∞ + λI) −1/2f 〉 L2(ρX)
= 2 〈 (Σ∞ + λI) −1/2f, (Σ∞ + λI) −1/2f 〉 L2(ρX)
= 2 〈 (Σ∞ + λI) −1f, f 〉 L2(ρX) .
Thus, we confirm that with high probability at least 1− δ, (ΣM + λI) −1 4 2(Σ∞ + λI) −1 (34)
Utilizing this inequality, we show the first and second inequalities in Proposition B as follows. It is sufficient to prove the second inequality because of
‖(ΣM + λI)−1gM,λ‖2L2(ρX) ≤ 1 λ ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX)
Noting that gρ ∈ H∞ and gM,λ = (ΣM + λI)−1ΣMgρ, we get ‖(ΣM + λI)−1/2gM,λ‖2L2(ρX) = ‖(ΣM + λI) −1/2(ΣM + λI) −1ΣMgρ‖2L2(ρX)
≤ ‖(ΣM + λI)−1/2gρ‖2L2(ρX) ≤ 2‖(Σ∞ + λI)−1/2gρ‖2L2(ρX) ≤ 2‖Σ−1/2∞ gρ‖2L2(ρX) = 2‖gρ‖2H∞ .
The third inequality on the degree of freedom is a result obtained by Rudi & Rosasco (2017).

heading: E EIGENVALUE ANALYSIS OF NEURAL TANGENT KERNEL
text: E. 1 REVIEW OF SPHERICAL HARMONICS
We briefly review the spherical harmonics which is useful in analyzing the eigenvalues of dot-product kernels. For references, see Atkinson & Han (2012); Bach (2017a); Bietti & Mairal (2019); Cao et al. (2019).
Here, we denote by τd−1 is the uniform distribution on the sphere Sd−1 ⊂ Rd. The surface area of Sd−1 is ωd−1 = 2π d/2
Γ(d/2) where Γ is the Gamma function. In L2(τd−1), there is an orthonomal basis consisting of a constant 1 and the spherical harmonics Ykj(x), k ∈ Z≥1, j = 1, . . . , N(d, k), where
N(d, k) = 2k+d−2k ( k + d− 3 d− 2 ) . That is, 〈Yki, Ysj〉L2(τd−1) = δksδij and 〈Yki, 1〉L2(τd−1) = 0.
The spherical harmonics Ykj are homogeneous functions of degree k, and clearly Ykj have the same parity as k.
Legendre polynomial Pk(t) of degree k and dimension d (a.k.a. Gegenbauer polynomial) is defined as (Rodrigues’ formula):
Pk(t) = (−1/2)k Γ(d−12 ) Γ ( k + d−12 ) (1− t2)(3−d)/2( d dt )k (1− t2)k+(d−3)/2.
Legendre polynomials have the same parity as k. This polynomial is very useful in describing several formulas regarding the spherical harmonics.
Addition formula. We have the following addition formula:
N(d,k)∑ j=1 Ykj(x)Ykj(y) = N(d, k)Pk(x >y), ∀x,∀y ∈ Sd−1. (35)
Hence, we see that Pk(x>·) is spherical harmonics of degree k. Using the addition formula and the orthogonality of spherical harmonics, we have∫
Sd−1 Pj(Z
>x)Pk(Z >y)dτd−1(Z) = δjk N(d, k) Pk(x >y). (36)
Combining the following equation: for x = ted + √ 1− t2x′, (x ∈ Sd−1, x′ ∈ Sd−2, t ∈ [−1, 1]),
ωd−1 ωd−2 dτd−1(x) = (1− t2)(d−3)/2dtdτd−2(x′),
we see the orthogonality of Legendre polynomials in L2([−1, 1], (1 − t2)(d−3)/2dt) and since Pk(1) = 1 we see ∫ 1
−1 P 2k (t)(1− t2)(d−3)/2dt = ωd−1 ωd−2
1
N(d, k) .
Recurrence relation. We have the following relation:
tPk(t) = k
2k + d− 2 Pk−1(t) + k + d− 2 2k + d− 2 Pk+1(t), (37)
for k ≥ 1, and for k = 0 we have tP0(t) = P1(t).
Funk-Hecke formula. The following formula is useful in computing Fourier coefficients with respect to spherical harmonics via Legendre polynomials. For any linear combination Yk of Ykj , (j ∈ {1, . . . , N(d, k)}) and any f ∈ L2([−1, 1], (1− t2)(d−3)/2dt), we have for ∀x,∫
Sd−1 f(x>y)Yk(y)dτd−1(y) = ωd−2 ωd−1 Yk(x) ∫ 1 −1 f(t)Pk(t)(1− t2)(d−3)/2dt. (38)
This formula say that spherical harmonics are eigenfunctions of the integral operator defined by f(x>y) and each eigen-space is spanned by spherical harmonics of the same degree. Moreover, it also provides a way of computing corresponding eigenvalues.
E. 2 EIGENVALUES OF DOT-PRODUCT KERNELS
Let µ0 be the uniform distribution on Sd−1. Note that although τd−1 and µ0 are the same distribution, we use two distributions τd−1 and µ0 depending on random variables. First, we consider any activation function σ : R → R and a kernel function k(x, x′) = Eb(0)∼µ0 [σ(b (0)>x)σ(b(0) > x′)] on the sphere Sd−1. We show this kernel function is a type of dot-product kernels, that is, there is k̂ : R → R such that k(x, x′) = k̂(x>x′). In fact, it can be confirmed as follows. For any x, x′ ∈ Sd−1, we take θ ∈ [0, π] so that x>x′ = cos θ, and an orthogonal matrix A ∈ Rd×d so that Ax = (1, 0, . . . , 0)> and Ax′ = (cos θ, sin θ, 0, . . . , 0)> because A preserves the value of x>x′. Then, since µ0 is rotationally invariant we see
k(x, x′) = ∫ Sd−1 σ(b(0)>Ax)σ(b(0)>Ax′)dµ0(b (0))
= ∫ Sd−1 σ(b (0) 1 )σ(b (0) 1 cos(θ) + b (0) 2 sin(θ))dµ0(b (0)),
where b(0) = (b01, b (0) 2 , . . . , b (0) d ). In other words, we see k is a function of θ = arccos (x >x′), and is a dot-product kernel k(x, x′) = k̂(x>x′). Hence, we can apply Funk-Hecke formula (38) to k(x, ·). The derivation of eigenvalues of the integral operator follows a way developed by Bach (2017a); Bietti & Mairal (2019); Cao et al. (2019). In general, g ∈ L2(τd−1) can be decomposed by spherical harmonics as follows.
g − ∫ Sd−1 g(Z)dτd−1(Z) = ∞∑ k=1 N(d,k)∑ j=1 〈g, Ykj〉L2(τd−1) Ykj
= ∞∑ k=1 N(d,k)∑ j=1 ∫ Sd−1 g(Z)Ykj(Z)Ykj(·)dτd−1(Z)
= ∞∑ k=1 N(d, k) ∫ Sd−1 g(Z)Pk(Z >·)dτd−1(Z), (39)
where we used addition formula to the last equality.
Here, we apply this decomposition (39) to k(x, ·) = k̂(x>·). Since Pk(Z>·) is a linear combination of spherical harmonics of degree k (see addition formula), we get
k(x, ·)− ∫ Sd−1 k̂(x>Z)dτd−1(Z) = ∞∑ k=1 N(d, k) ∫ Sd−1 k̂(x>Z)Pk(Z >·)dτd−1(Z)
= ∞∑ k=1 λ̂kN(d, k)Pk(x >·), (40)
where we used Funk-Hecke formula (38) and we set λ̂k = ωd−2 ωd−1 ∫ 1 −1 k̂(t)Pk(t)(1− t 2)(d−3)/2dt. We note that λ̂k is eigenvalue with multiplicity N(d, k) of the integral operator defined by k.
Next, we derive another expression of k. In a similar way, we obtain the following equation: σ(b(0)>x)− ∫ Sd−1 σ(Z>x)dτd−1(Z) = ∞∑ k=1 µ̂kN(d, k)Pk(b (0)>x),
where µ̂k = ωd−2 ωd−1 ∫ 1 −1 σ(t)Pk(t)(1− t
2)(d−3)/2dt. By the definition of k and the orthogonality of spherical harmonics, we get
k(x, x′) = Eb(0) [ σ(b(0)>x)σ(b(0)>x′) ] =
∫ Sd−1 σ(Z>x)dτd−1(Z) ∫ Sd−1 σ(Z>x′)dτd−1(Z) + ∞∑ k=1 µ̂2kN 2(d, k)Eb(0) [ Pk(b (0)>x)Pk(b (0)>x′) ] =
∫ Sd−1 σ(Z>x)dτd−1(Z) ∫ Sd−1 σ(Z>x′)dτd−1(Z) + ∞∑ k=1 µ̂2kN(d, k)Pk(x >x′), (41)
where we used equation (36). By the rotationally invariance, we can show∫ Sd−1 k̂(x>Z)dτd−1(Z) = ∫ Sd−1 σ(Z>x)dτd−1(Z) ∫ Sd−1 σ(Z>x′)dτd−1(Z).
Thus, comparing (40) with (41), we get λ̂k = µ̂2k.
E. 3 EIGENVALUES OF NEURAL TANGENT KERNELS
Utilizing a relation λ̂k = µ̂2k, we derive a way of computing eigenvalues of the integral operator defined by the integral operators Σ∞ associated with the activation σ. Recall the definition of the neural tangent kernel:
k∞(x, x ′) def = Eb(0)∼µ0 [σ(b (0)>x)σ(b(0)>x′)] + (x>x′ + γ2)Eb(0)∼µ0 [σ ′(b(0)>x)σ′(b(0)>x′)].
A neural tangent kernel consists of three kernels:
h1(x, x ′) = Eb(0)∼µ0
[ σ(b(0)>x)σ(b(0)>x′) ] ,
h2(x, x ′) = Eb(0)∼µ0
[ σ′(b(0)>x)σ′(b(0)>x′) ] ,
h3(x, x ′) = x>x′Eb(0)∼µ0
[ σ′(b(0)>x)σ′(b(0)>x′) ] .
By the argument in the previous subsection, h1 and h2 are dot-product kernel, that is, there exist ĥ1 and ĥ2 such that h1(x, x′) = ĥ1(x>x′) and h2(x, x′) = ĥ2(x>x′). Moreover, h3 is a dot-product kernel as well because we get h3(x, x′) = ĥ3(x>x′) by setting ĥ3(t) = tĥ2(t). Hence, theory explained earlier is applicable to these kernels.
Eigenvalues µ̂k for kernels h1 and h2 are described as follows:
µ̂ (1) k = ωd−2 ωd−1 ∫ 1 −1 σ(t)Pk(t)(1− t2)(d−3)/2dt, (42)
µ̂ (2) k = ωd−2 ωd−1 ∫ 1 −1 σ′(t)Pk(t)(1− t2)(d−3)/2dt, (43)
yielding eigenvalues λ̂(1)k = (µ̂ (1) k ) 2 and λ̂(2)k = (µ̂ (2) k ) 2 for h1 and h2, respectively. As for eigenvalues λ̂(3)k for h3, we have
λ̂ (3) k = ωd−2 ωd−1 ∫ 1 −1 tĥ2(t)Pk(t)(1− t2)(d−3)/2dt
= k 2k + d− 2 ωd−2 ωd−1 ∫ 1 −1 ĥ2(t)Pk−1(t)(1− t2)(d−3)/2dt
+ k + d− 2 2k + d− 2 ωd−2 ωd−1 ∫ 1 −1 ĥ2(t)Pk+1(t)(1− t2)(d−3)/2dt
= k
2k + d− 2 λ̂
(2) k−1 + k + d− 2 2k + d− 2 λ̂ (2) k+1,
where we used the recurrence relation (37). Since, h1, h2, and h3 have the same eigenfunctions, eigenvalues λ̂∞,k of k∞ is
λ̂∞,k = λ̂ (1) k + γ 2λ̂ (2) k +
k
2k + d− 2 λ̂
(2) k−1 + k + d− 2 2k + d− 2 λ̂ (2) k+1. (44)
Hence, calculation of {λ̂∞,k}∞k=1 results in computing µ̂ (1) k and µ̂ (2) k for given activation σ.
Eigenvalues for ReLU and smooth approximations of ReLU. As for ReLU activation, its eigenvalues were derived in Bach (2017a). Let σ be ReLU. Then, µ̂(1)k = 0 and µ̂ (2) k ∼ k−d/2 when k is odd and µ̂(1)k ∼ k−d/2−1 and µ̂ (2) k = 0 when k is even. Consequently, we see λ̂∞,k = Θ(k −d).
We note that the multiplicity of λ̂∞,k is N(d, k), so that we should take into account the multiplicity to derive decay order of eigenvalues λ∞,i of Σ∞. Since 1+ ∑k j=1N(d−1, j) = N(d, k) (for details see Atkinson & Han (2012)), we see λ∞,N(d+1,k) = Θ(k−d). Moreover, N(d+ 1, k) = Θ(kd−1)
yields λ∞,N(d+1,k) = Θ ( N(d+ 1, k)−1− 1 d−1 ) . As a result, Assumption (A4) is verified with
β = 1 + 1d−1 for ReLU.
For the smooth approximation σ(s) of ReLU satisfying Assumption (A1’), we can show that every eigenvalue of Σ(s)∞ derived from σ(s) converges to that for ReLU as s→∞ because of (42) and (43) with Lebesgue’s convergence theorem.

heading: F EXPLICIT CONVERGENCE RATES FOR SMOOTH APPROXIMATION OF RELU
text: For convenience, we here list notations used in this section. In this section, let σ and σ(s) be ReLU activation and its smooth approximation satisfying (A1’), respectively, and for M ∈ Z+ ∪ {∞} let kM ,ΣM , gM,λ, k (s) M ,Σ (s) M , g (s) M,λ be corresponding kernel, integral operators, and minimizers of the regularized expected risk functions. Let g(T ) be iterates obtained by the reference ASGD (Algorithm 2) in the RKHS associated with k(s)M .
We consider the following decomposition:
1 3 ‖g(T ) − gρ‖2L2(ρX) ≤ ‖g (T ) − g(s)M,λ‖ 2 L2(ρX)
(45)
+ ‖g(s)M,λ − g (s) ∞,λ‖ 2 L2(ρX)
(46)
+ ‖g(s)∞,λ − g∞,λ‖ 2 L2(ρX)
(47)
+ ‖g∞,λ − gρ‖2L2(ρX). (48)
These terms can be made arbitrarily small by taking large M and s. As for (48) this property is a direct consequence of Proposition D. Note that Proposition C is not applicable to (46) because this proposition require the specification of the target function by k(s)∞ which does not hold in general.
In the following, we treat the remaining terms.
Proposition E. Suppose (A1’) and (A2’) hold. Then, we have
1. plimM→∞‖k (s) M − k (s) ∞ ‖L∞(ρX)2 = 0, lims→∞ ‖k (s) ∞ − k∞‖L∞(ρX)2 = 0,
2. plimM→∞ ∣∣∣Tr(Σ(s)M − Σ(s)∞ )∣∣∣ = 0, lims→∞ ∣∣∣Tr(Σ(s)∞ − Σ∞)∣∣∣ = 0,
3. plimM→∞‖g (s) M,λ − g (s) ∞,λ‖L∞(ρX) = 0, lims→∞ ‖g (s) ∞,λ − g∞,λ‖L∞(ρX) = 0,
where plim denotes the convergence in probability.
Proof. We show the first statement. By the uniform law of large numbers (Theorem 3.1 in Mohri et al. (2012)), we see the convergence in probability:
‖k(s)M − k (s) ∞ ‖L∞(ρX)2 ≤ sup
x,x′∈Sd−1 ∣∣∣∣∣ 1M M∑ r=1 σ(s)(b(0)>r x)σ (s)(b(0)>r x ′)− Eb(0) [ σ(s)(b(0)>x)σ(s)(b(0)>x′) ]∣∣∣∣∣ + (1 + γ2) sup
x,x′∈Sd−1 ∣∣∣∣∣ 1M M∑ r=1 σ(s) ′ (b(0)>r x)σ (s)′(b(0)>r x ′)− Eb(0) [ σ(s) ′ (b(0)>x)σ(s) ′ (b(0)>x′) ]∣∣∣∣∣ p−→ 0,
where the limit is taken with respect to M → ∞ and the notation p−→ denotes the convergence in probability. Next, we have the following convergence:
‖k(s)∞ − k∞‖L∞(ρX)2 ≤ sup x,x′∈Sd−1
Eb(0) [∣∣∣σ(s)(b(0)>x)σ(s)(b(0)>x′)− σ(b(0)>x)σ(b(0)>x′)∣∣∣]
+ (1 + γ2) sup x,x′∈Sd−1
Eb(0) [∣∣∣σ(s)′(b(0)>x)σ(s)′(b(0)>x′)− σ′(b(0)>x)σ′(b(0)>x′)∣∣∣]
≤ 4 sup x∈Sd−1
Eb(0) [∣∣∣σ(s)(b(0)>x)− σ(b(0)>x)∣∣∣]+ 4(1 + γ2) sup
x∈Sd−1 Eb(0) [∣∣∣σ(s)′(b(0)>x)− σ′(b(0)>x)∣∣∣] = 4
[∣∣∣σ(s)(b(0)>e1)− σ(b(0)>e1)∣∣∣]+ 4(1 + γ2)Eb(0) ∣∣∣σ(s)′(b(0)>e1)− σ′(b(0)>e1)∣∣∣→ 0, where for the first inequality we used the boundedness of σ, σ′, σ(s), and σ(s) ′ on [−1, 1], for the equality we used the rotationally invariance of the measure µ0, and the limit is taken with respect to s → ∞. For the final convergence in the above expression we used Assumption (A1’) and boundedness with Lebesgue’s convergence theorem. In general, for a kernel k and associated integral operator Σ with ρX , we have Tr (Σ) =∫ Sd−1 k(X,X)dρX . Hence,
∣∣∣Tr(Σ(s)M − Σ(s)∞ )∣∣∣ ≤ ‖k(s)M − k(s)∞ ‖L∞(ρX)2 and ∣∣∣Tr(Σ(s)∞ − Σ∞)∣∣∣ ≤ ‖k(s)∞ − k∞‖L∞(ρX)2 , and the second statement holds immediately. Finally, we show the third statement. In the same manner as the derivation of inequality (19), we get
‖((Σ(s)M + λI) −1 − (Σ(s)∞ + λI)−1)gρ‖L2(ρX) ≤
1
λ2 ‖Σ(s)M − Σ (s) ∞ ‖op‖gρ‖L2(ρX).
We denote F (s)M = (Σ (s) M + λI) −1gρ and F (s) ∞ = (Σ (s) ∞ + λI)−1gρ. Noting g (s) M,λ = Σ (s) M F (s) M and g (s) ∞,λ = Σ (s) ∞ F (s) ∞ , we get for x ∈ Sd−1,
|g(s)M,λ(x)− g (s) ∞,λ(x)| = ∣∣∣Σ(s)M F (s)M (x)− Σ(s)∞ F (s)∞ (x)∣∣∣
= ∣∣∣∣∫ X K (s) M,x(X)F (s) M (X)dρX − ∫ X K(s)∞,x(X ′)F (s)∞ (X ′)dρX ∣∣∣∣ =
∣∣∣∣∫ X (K (s) M,x −K (s) ∞,x)(X)F (s) M (X)dρX − ∫ X K(s)∞,x(X)(F (s) M − F (s) ∞ )(X)dρX ∣∣∣∣ ≤ ‖K(s)M,x −K (s) ∞,x‖L2(ρX)‖F (s) M ‖L2(ρX) + ‖K (s) ∞,x‖L2(ρX)‖F (s) M − F (s) ∞ ‖L2(ρX)
≤ 1 λ ‖k(s)M − k (s) ∞ ‖L∞(ρX)2‖gρ‖L2(ρX) + 12 λ2 ‖Σ(s)M − Σ (s) ∞ ‖op‖gρ‖L2(ρX). (49)
The both terms in the last expression (49) converge to 0 in probability because of the first statement of this proposition and the Bernstein’s inequality (Proposition 3 in Rudi & Rosasco (2017)) to random operators. This finishes the proof of the former of the third statement.
In the same manner, we have
‖g(s)∞,λ − g∞,λ‖L∞(ρX) ≤ 1
λ ‖k∞ − k(s)∞ ‖L∞(ρX)2‖gρ‖L2(ρX) +
12 λ2 ‖Σ∞ − Σ(s)∞ ‖op‖gρ‖L2(ρX).
(50)
The first term in the right hand side converges to 0 because of the first statement of this proposition. We next show the convergence ‖Σ∞ − Σ(s)∞ ‖op → 0 as s → ∞. As seen in the previous section, Σ∞ and Σ (s) ∞ share the same eigenfunctions and every eigenvalue of Σ (s) ∞ converges to that of Σ∞ as s → ∞. Let {λ(s)∞,i}∞i=1 and {λ∞,i}∞i=1 be eigenvalues of Σ (s) ∞ and Σ∞, respectively. For an
arbitrary > 0, we can take i such that ∑∞ i=i λ∞,i < . From the convergence λ (s) ∞,i → λ∞,i and
Tr ( Σ (s) ∞ ) → Tr (Σ∞) as s→∞, we see that for arbitrarily sufficiently large s, |λ(s)∞,i − λ∞,i| <
(i < i ) and ∑∞ i=i λ (s) ∞,i < 2 . Clearly, for i ≥ i , |λ (s) ∞,i − λ∞,i| ≤ ∑∞ i=i (λ (s) ∞,i + λ∞,i) < 3 .
Therefore, we conclude the uniform convergence supi∈{1,...,∞} |λ (s) ∞,i − λ∞,i| → 0 as s→∞. This implies ‖Σ∞ − Σ(s)∞ ‖op → 0 as s→∞.
So far, we have shown that (46), (47), and (48) can be made arbitrarily small by taking large s and M depending on λ. The remaining problem is to show the convergence of (45). To do so, we establish the counterpart of Theorem B by adapting Theorem A and Proposition B to the current setting.
The counterpart of Theorem B. In Theorem A, the condition (A3) is required for NTK associated with the smooth activation σ(s) and it is not satisfied in general. Note that (A3) is used for bounding ‖g(s)M,λ‖L∞(ρX) uniformly as seen in the proof of Lemma A. Let us consider the decomposition:
‖g(s)M,λ‖L∞(ρX) ≤ ‖g∞,λ‖L∞(ρX) + ‖g (s) M,λ − g (s) ∞,λ‖L∞(ρX) + ‖g (s) ∞,λ − g∞,λ‖L∞(ρX)
≤ 2 √
3‖Σ−r∞ gρ‖L2(ρX) + ‖g (s) M,λ − g (s) ∞,λ‖L∞(ρX) + ‖g (s) ∞,λ − g∞,λ‖L∞(ρX)
→ 2 √
3‖Σ−r∞ gρ‖L2(ρX).
Here, for the second inequality we used (20). Note that the inequality (20) holds for Σ∞ because the condition (A3) is supposed for ReLU. For the last inequality we used Proposition E. Hence, Theorem A can be applicable and the same convergence in Theorem A holds for σ(s). For arbitrarily sufficiently large s and M with high probability, we have
E [∥∥∥g(T ) − g(s)M,λ∥∥∥2
L2(ρX)
] ≤ 4 η2(T + 1)2 ‖(Σ(s)M + λI) −1g (s) M,λ‖ 2 L2(ρX)
+ 2 · 242
T + 1 ‖(Σ(s)M + λI) −1/2g (s) M,λ‖ 2 L2(ρX)
+ 8
T + 1
( 1 + ‖gρ‖2L2(ρX) + 24‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( Σ (s) M (Σ (s) M + λI) −1 ) .
(51)
Next, we adapt Proposition B to the current setting. By inequality (34), there exists M0 ∈ Z+ such that ∀M ≥M0, with high probability,
‖(Σ(s)M + λI) −1/2g (s) M,λ‖ 2 L2(ρX) ≤ 2‖(Σ(s)∞ + λI)−1/2gρ‖2L2(ρX).
If (Σ(s)∞ + λI)−1 4 2(Σ∞ + λI)−1 holds, then we have the counterpart of the second inequality in Proposition B because
‖(Σ∞ + λI)−1/2gρ‖2L2(ρX) ≤ ‖Σ −1/2 ∞ gρ‖2L2(ρX) = ‖gρ‖ 2 H∞ , (52)
where we used the fact that gρ is contained in H∞ because of (A3’). Note that the first inequality in Proposition B is a direct consequence of the second one. We consider eigenvalues {λ(s)∞,i}∞i=1 and {λ∞,i}∞i=1 of Σ (s) ∞ and Σ∞, respectively. Let iλ be an index such that for ∀i > iλ, λ∞,i ≤ λ2 . Since, every eigenvalue of {λ(s)∞,i}∞i=1 converges to that of {λ∞,i}∞i=1 as s→∞, for an arbitrarily sufficiently large s, we have |λ(s)∞,i−λ∞,i| ≤ λ2 for ∀i < iλ, leading to 1/(λ+λ (s) ∞,i) ≤ 2/(λ+λ∞,i). As for the case i ≥ iλ, since 32λ ≥ λ + λ∞,i, we have 1/(λ + λ (s) ∞,i) ≤ 1/λ ≤ 3/(2(λ + λ∞,i)). Combining these, we obtain (Σ(s)∞ + λI)−1 4 2(Σ∞ + λI)−1 and
lim s→∞
plimM→∞‖(Σ (s) M + λI) −1g (s) M,λ‖ 2 L2(ρX) ≤ 4λ−1‖gρ‖2H∞ , (53)
lim s→∞
plimM→∞‖(Σ (s) M + λI) −1/2g (s) M,λ‖ 2 L2(ρX) ≤ 4‖gρ‖2H∞ . (54)
These are the counterpart of the first and second inequalities in Proposition B.
Next, we consider the bound on the degree of freedom in this proposition. Assume λ ≤ 12‖Σ∞‖op. As seen earlier, an operator Σ(s)∞ converge to Σ∞ in terms of the operator norm. Hence, λ ≤ ‖Σ(s)∞ ‖op
for an arbitrarily sufficiently large s and the bound on the degree of freedom in Proposition B is applicable. We get
Tr (
Σ (s) M (Σ (s) M + λI)
−1 ) ≤ 3Tr ( Σ(s)∞ (Σ (s) ∞ + λI) −1 ) . (55)
Let us consider upper bounding the right hand side:
Tr (
Σ(s)∞ (Σ (s) ∞ + λI)
−1 )
= iλ−1∑ i=1 λ (s) ∞,i λ+ λ (s) ∞,i + ∞∑ i=iλ λ (s) ∞,i λ+ λ (s) ∞,i
≤ iλ−1∑ i=1 λ (s) ∞,i λ+ λ (s) ∞,i + 1 λ ∞∑ i=iλ λ (s) ∞,i
= iλ−1∑ i=1 λ (s) ∞,i λ+ λ (s) ∞,i − 1 λ iλ−1∑ i=1 λ (s) ∞,i + 1 λ Tr ( Σ(s)∞ ) .
On the other hand, by the definition of iλ,
2Tr ( Σ∞(Σ∞ + λI) −1) = 2 iλ−1∑ i=1 λ∞,i λ+ λ∞,i + 2 ∞∑ i=iλ λ∞,i λ+ λ∞,i
≥ 2 iλ−1∑ i=1 λ∞,i λ+ λ∞,i + 1 λ ∞∑ i=iλ λ∞,i
= 2 iλ−1∑ i=1 λ∞,i λ+ λ∞,i − 1 λ iλ−1∑ i=1 λ∞,i + 1 λ Tr (Σ∞)
≥ iλ−1∑ i=1 λ∞,i λ+ λ∞,i − 1 λ iλ−1∑ i=1 λ∞,i + 1 λ Tr (Σ∞) .
Therefore, by inequality (55), the convergence of λ(s)∞,i → λ∞,i for i ∈ {1, . . . , iλ − 1} as s→∞, and the second statement in Proposition E, we have
plims→∞ lim M→∞
Tr (
Σ (s) M (Σ (s) M + λI)
−1 ) ≤ 9Tr ( Σ∞(Σ∞ + λI) −1) . (56) Combining (45)-(48) with (51), (53), (54), and (56), we establish the counterpart of Theorem B. For given , λ, and δ, there exist sufficiently large s and M such that with high probability 1− δ,
E [∥∥∥g(T ) − gρ∥∥∥2
L2(ρX)
] ≤ + αλ2r‖Σ−r∞ gρ‖2L2(ρX) + α
T + 1
( 1 +
1
λη2(T + 1)
) ‖gρ‖2H∞
+ α
T + 1
( 1 + ‖gρ‖2L2(ρX) + ‖Σ −r ∞ gρ‖2L2(ρX) ) Tr ( Σ∞(Σ∞ + λI) −1) , (57)
where α > 0 is a universal constant.
Proof of Corollary 2. Since conditions (A1’) and (A2’) are special cases of (A1) and (A2), we can apply Proposition A to Algorithm 1 for the neural network with the smooth approximation σ(s) of ReLU. Hence, by setting ηt = η = O(1) satisfying 4(6 + λ)η ≤ 1 and λ = T−β/(2rβ+1) where β = 1 + 1d−1 , and by applying Tr ( Σ∞(Σ∞ + λI)
−1) = O(λ−1/β) (Caponnetto & De Vito, 2007) and
‖gρ‖H∞ , ‖gρ‖L2(ρX) ≤ O ( ‖Σ−r∞ gρ‖L2(ρX) ) because of ‖Σ∞‖op ≤ O(1), we finish the proof of Corollary 2.

heading: G APPLICATION TO BINARY CLASSIFICATION PROBLEMS
text: In this paper, we mainly focused on regression problems, but our idea can be applied to other applications. We briefly discuss its application to binary classification problems. A label space is set to Y = {−1, 1} and a loss function is set to be the squared loss: `(z, y) = 0.5(y − z)2. The ultimate goal of the binary classification problem is to obtain the Bayes classifier that minimizes the expected classification error, R(g) def= P(X,Y )∼ρ[sgn(g(X)) 6= Y ], over all measurable maps. It is known that the Bayes classifier is expressed as sgn(gρ(X)), where gρ is the Bayes rule of L(g) = Eρ[l(g(X), Y )] (see Zhang (2004); Bartlett et al. (2006)). Therefore, if gρ satisfies a margin condition, i.e., |gρ(x)| ≥ ∃τ > 0 on supp(ρX), then this goal is achieved by obtaining an τ/2-accurate solution of gρ in terms of the uniform norm on supp(ρX). That is, the required optimization accuracy on ‖g
Θ (T )−gρ‖L∞(ρX) to obtain the Bayes classifier depends only on
the margin τ unlike regression problems. Due to this property, averaged stochastic gradient descent in RKHSs can achieve the linear convergence rate demonstrated in Pillaud-Vivien et al. (2018a). To leverage this theory to our problem setting, we consider the following decomposition:
‖g Θ (T ) − gρ‖L∞(ρX) ≤ ‖gΘ(T ) − g (T )‖L∞(ρX) (58)
+ ‖g(T ) − gM,λ‖L∞(ρX) (59) + ‖gM,λ − g∞,λ‖L∞(ρX) (60) + ‖g∞,λ − gρ‖L∞(ρX). (61)
The last term (61) can be made arbitrary small by λ→ 0 as shown in Pillaud-Vivien et al. (2018a). A term (60) can be bounded in the same manner as the third statement of Proposition E, yielding the convergence to 0 as M → ∞ with high probability. The convergence of (59) was shown in Pillaud-Vivien et al. (2018a) and the convergence of (58) is guaranteed by Proposition A. As a result, we can show the following exponential convergence of the classification error R(g) for two-layer neural networks with a sufficiently small λ as demonstrated in Pillaud-Vivien et al. (2018a).
E[R(g Θ (T ))−R(gρ)] ≤ 2 exp(−O(λ2τ2T )).
In Nitanda & Suzuki (2019), an exponential convergence was shown for the logistic loss `(z, y) = log(1 + exp(−yz)) as well. Proposition A also holds for the logistic loss with an easier proof than the squared loss because of the boundedness of stochastic gradients of the loss. Hence, their theory is also applicable to the reference ASGD in an RKHS. In summary, (58), (59), and (61) can be bounded by the above argument. However, we note that bounding (60) is not obvious and is left for future work.

Review summaries:
This paper considers the optimization of a wide two layers neural network (for a regression task) using averaged SGD. The authors consider the Neural Tangent Kernel (NTK) regime. The NTK is a kernel defined using the activation function and the initial distribution of the parameters of the input layer. The RKHS H associated to this NTK is assumed to contain the Bayes predictor. Based on this, the authors derive a convergence rate for the predictor constructed from the T-th iterate of averaged SGD and the Bayes predictor in terms of the L2 distance wrt the distribution of the features. By specifying this bound in terms of the decay of the eigenvalues of the integral operator in H, they obtain an explicit generalization error bound, which is optimal for the class of problems considered in the paper.

This paper analyzed the averaged SGD for overparameterized two-layer NNs for regression problems. Particularly, they show that the averaged SGD can achieve the minimax optimal convergence rate, with the global convergence guarantee. To achieve, they propose a new parameter which captures the ``complexities’’ of the target function and the RKHS associated with the NTK.