Approximation, Estimation and Optimization Errors for a Deep Neural Network
Authors: Gerrit Welper
Benjamin Keene
Venue: Accepted by TMLR ()

Abstract: The error of supervised learning is typically split into three components: approximation, estimation and optimization errors. While all three have been extensively studied in the literature, a unified treatment is less frequent, in part because of conflicting assumptions. Current approximation results rely on carefully hand crafted weights or practically unavailable information, which are difficult to achieve by gradient descent. Optimization theory is best understood in over-parametrized regimes with more weights than samples, while classical estimation errors require the opposite regime with more samples than weights.

This paper contains two results which bound all three error components simultaneously for (non-convex) training of the second but last layer of deep fully connected networks on the unit sphere. The first uses a regular least squares loss and shows convergence in the under-parametrized regime. The second uses a kernel based loss function and shows convergence in both under and over-parametrized regimes.

Published in Transactions on Machine Learning Research (02/2023)
Approximation, Estimation and Optimization Errors for Deep Neural Network
B. Keene
keenedrucf edu
Deportment of Mathematics University of Central Florida Orlondo, FL 32816, USA
G. Welper
gerrit.welperrRuef.et edu
Department of Mathematics University of Central Florida Orlando, FL 32816, USA
Reviewed on OpenReview:
openrevvee.. net/ formm id= d=ND5haNNu
Abstract
The error of supervised learning is typically split into three components: approximation, estimation and optimization errors. While all three have been extensively studied in the literature, unified treatment less frequent, in part bocause of conflicting assumptions. Current approximation results rely on carefully hand crafted weights or practically unavail- able information, which are difficult to achieve by gradient descent. Optimization theory is best understood in over-paramctrized regimes with more weights than samples, while clas- sical estimation errors require the opposite regime with more samples than weights. This paper contains two results which bound all three error components simultaneously for (non- convex) training of the second but last layer of deep fully connected networks on the unit sphere. The first uses a regular least squares loss and shows convergence the under- parametrized regime. The second uses kernel based loss function and shows convergence in both under and wver-parametrized regimes.
1 Introduction
this paper, we consider supervised learning fully connected neural networks without bias: For network fo with weights f and normalized training samples (It, y:) on the d-dimensional sphere, we minimize the loss
N
{(0)
Σ (s((z)) - yal ?
2N
by gradient descent. We also consider alternative losses, which allow more flexibility with regard to the num- ber of samples and network size. The main results provide complete error analysis including approzimation errors, estimation errors and optimization errors (Shaley-Shwartz & Ben-David 2014).
1.1 Literature Review
If the data points = f(x.)) are generated by some unknown target function f. how well can the network approximate it, i.e. how large is the error infa []ʃo fll on some domain D. ignoring error contributions from sampling and optimization algorithms? Typical results establish bounds
Approximation Error:
inf fl.e - fll(a(D) S ',,
f E K,
(1)

---

Published in Transactions on Machine Learning Research (02/2023)
for some rate O, with an asymptotic rate n(()"", where n(0) is complexity measure of the network, e-g. width, depth or total number of weights. Any quantifiable rate requires some prior conditions on f: here given by membership in a compact set K, which typically consists of functions with bounded Sobolev, Besov, Barron or other smoothness norms.
First results show universal approximation properties (Cybenko) 1989 Hornik et al. 1989 Barron 1993
Zhou 2020 Lu al. 2017 Hanin & Sellke, 2017) and reproduction of classical approximation rates for targets
with Sobolev and Besov regularity (Gribonval et al. 2022 Güihring et al.) 2020 Opschoor et al. 2020
et al. 2019 Suzuki 2019 More recent papers provide super-convergence results, where networks outperform
classical methods, as well as optimality benchmarks like manifold width, for the price of discontinuous weight
assignments (Yarotsky] 2017 2018 Yarotsky & Zhevnerchuk, 2020
Daubechies et al. 2022 Shen et al. 2019
Lu et al. 2021). Approximation results with smoothness requirements more tailored to neural networks use
Barron and related spaces (Bach) 2017 Klusowski & Barron 2018 Weinan et al. 2022
Li et al.
2020 Siegel
& Xu 2020: 2022a Bresler Nagaraj 2020). Several surveys are given in (Pinkus 1999
DeVore ct al.
2021
Weinan et al. 2020 Berner et. al.
2022
In the above results, the weights are not trained by practical optimizers, but rather hand-picked or sampled from practically unknown distributions. Practical networks do not always achieve the thcoretical bounds Adcock & Dexter (2021); Grohs & Voigtlaender (2023 The papers Jentzen & Riekert (2022); Tbragimov et al. ) Gentile & Welper (2022); Welper 20024b a are closely related to the results in this paper and
provide an analysis of approximation errors in combination with gradient descent training. Finally [Siegel & Xu (202bb): (Siegel et al. (2023); Beck al.
(2022): Herrmann et al. (2022) consider approximation or
estimation with alternative optimizers like greedy algorithms.
Generalization and Estimation errors: Practically, one can neither evaluate nor optimize the L2(D) error directly, and therefore trains the sample or empirical loss, resulting in the empirical risk minimizer Q. The resulting expected loss is called the generalization ervor and split into the approrimation error and a remaining estimation error, (Shalev-Shwartz & Ben- David 2014)
inf llfe fl) inf llfo fILL,
[Ifo ---fll inf llfe
flliaco)
inf
There are many techniques to bound generalization and estimation errors, for example by establishing uniform bounds between the expected and sample loss
N
sup 0
life -flli
1
Σ 1=1
(o((=)) - f(x:)12 CC+
(2)
2N
for some complexity measure C of the neural networks like VC-dimension Rademacher complexity. VC- dimension bounds of the form VC-dim < (LL(()) for total number of weights n00) and depth L are in
Neyshabur et al. 2017); Bartlett et al. 1998 Harvey et al. (2017) Bounds for the Rademacher complexity
tend to be independent of the size of the network as e.g. O VT.
for weight W in the Frobcnius
norm from Golowich et al.] (2018). Similar bounds are in Neyshabur et al. (015);; Liang et al. (2019): Tu eet al. (2020). While the norm [["|| may grow for wide networks with standard scaling, newer results depend on the difference ||W W to some reference initial weights W6 in Frobenius and other matrix norms, which tends to be small in the over-parametrrzed limit and leads to some combined generalization and gradient descent convergence results (Cao & Gui (020). Other Rademacher complexity bounds rely on snoothness (Weinan et al. 2022 2019). Further techniques include margin theory (Jakubovitz et al.] 2019
Neyshabur et al.] 2018]] Bartlett et al. 2017) mutual information (Asadi et al. 2018 Steinke & Zakynthinon,
Empirical observations show that against conventional wisdom neural networks generalize well in over- parametrized regimes, with enough
2020) compression (Arora et al. 2018) and Besov regularity (Suzuki) 2019
weights to fit random data, (Neyshabur el. al. 2017 Zhang al. 2017
Geiger et al. 2019)
Optimization Error: Both the empirical loss minimizer â argmin ((0) and the approximation error info [lfe - /IlE, build on optimization problem. Since these non-convex, can we icactically compute
2

---

Published in Transactions on Machine Learning Research (02/2023)
the minimizers, at least sufficiently good substitute? This question is addressed in the optimization
literature for neural networks. The approach in this paper relies on the neural tangent kernel (NTK) coined
in Jacot et al. (2018) and introduced simultaneously in Li & Liang (2018): 0: Aluen-Zhu et al. (2019); Du et al.
(2019b a). The concept is further developed in /oo et al. [2020]: Arora et al. [dl.[201)) 22019a bb: Su & Yang (019
Lee et al. (2019) : Song & Yang (2019); Zou & Gu (2019) 9 Kawaguchi & Huang (2019 Chizat el al. 2019 :
Oymak & Soltanolkotabi (2020);
: Ji & Telgarsky (2020); Nguyen & Mondelli (2020 Bai & Lec (2020)
; Chen
et al. [2021]; ); Song et al. (2021);
b; Lee al. (2022 ; Gentile Welper (2022); Welper (2024b a). In this paper
we use lower bounds for the NTK that originate from Bietti & Mairal (2019): Geifman et al. (2020): ; Ji et al.
(2020); ; Chen & Xu (2021). The optimization literature contains may other approaches that we only mention
briefly: Landscape analysis Nguyen & Hein 2017 Ge et al. 2018 Du & Lee 2018 Soltanolkotabi et al.
2019: Venturi et. al.
2019). Wasserslein gradient flow (Soudry & Carmon 2016 Safran & Shamir 2018
Chizat & Bach 2018 Mei et al. 2018 Rotskoff & Vanden- -ijndenn-Ejjen,
2018 Sirignano & Spiliopoulos
2020
as well as several overviews [Weinan et al. 2020
Berner al. 2022
Roberts ct al.
2022).
The definition of stochastic gradient descent intertwines optimiza- tion with sampling and the literature provides positive effects on generalization. This can be analyzed in abstract settings, e-g. the paper Hardt et al. (2016) bounds the generalization error between empirical and expected risk of SGD iterates of general convex and non-convex objective functions. In addition, it bounds the expected loss between SGD and empirical risk minimizers in the convex casc.
Gencralization and Optimization:
Other papers are more specific to neural networks, i.e. Cao & Gu 2020 Nitanda & Suzuki 2021 consider
a combination of estimation and optimization in paraperreet regimes. The latter proves generalization errors for stochastic gradient descent by comparing its dynamics with an NTK idcalization, yielding minimax optimal SGD convergence rates. In addition, it does not require any lower bounds on the NTK eigenvalues, similar to Welper (2024b) and the current paper. The papers Wang & Ma (2023); Liu et al. (2022); Park
et al. ( ; Neu al. (2021) find improved estimation bounds by explicitly incorporating gradient descent dynamics. Another closely related set of results is Drews & Kohler (2022) Kohler & Krzyzak (0222) which
consider all three error contributions and control the optimization error based on the contributions of the
final layer.
1.2 New Contributions
This paper contains generalization error bounds of the form
Il (84 E ma + m N-C
where m is the width of the fully connected network fa, N is the number of samples and a, b, 2 are constants specified more closely in the main Theorems 2.2 2.4 The weights 0 on the left hand side are the output of gradient descent training on two different discrete losses. For simplicity, we confine the data to uniform samples on the unit sphere and train only the non-convex second but last layer. The new contributions of this bound are as follows:
Less Over-Parametrization: While over-parametrrzatioo in total number of weights is common in prac- tical neural networks, current optimization theory heavily relies much larger networks with more width than samples m >> N. In contrast, successful architectures like AlexNet Krizhevsky el al. (2012) or ResNet He et al. (2016) are much thinner m < N (including channels, width and height).
Our result does not require any relation between m and N. For > 0, this provides small bounds in m < N regimes (including under-paramettriztion
For a kernel based loss, Theorem 2.44 achieves b = 0, resulting in small bounds for any regime m 5 N (including under- and over parammttrattiitnon)) To the best of our knowledge, this is the first result that shows gradient descent convergence for deep neural networks independent of the relation between network size and number of samples.
Unified Analysis: The given bound contains approximation errors (m "n="),, estimation errors (m'N*) and optimization errors (0 is trained by GD). These bounds can be found in the literature in isolation, but
3

---

Published in Transactions on Machine Learning Research (02/2023)
rarely in single theorem because of confficting assumptions. The optimization literature requires parametrization so that all data. y/ = f(;) can be correctly reproduced by the network yi = fo(x)) This directly entails maximally large Rademacher complexity and hence conflicts with common assumptions for estimation error bounds. In the infinite sample limit considered in approximation theory, this also confines the larget functions f to neural networks themselves, instead of rich classes of practical relevance. Therefore, the approximation literature ignores the optimization problem in favour of simpler hand-picked weights.
Only few papers in the literature balance all required assumptions and provide bounds for approxi- mation, estimation and optimization in one single theorem. The papers Drews & Kohler (2022); ; Kohler & Krzyzak (2022). use non-standard architecturos, which allow derivation of crror bounds from the last layer alone. This is à convex training objective, in contrast to this paper, which analyzes the training contribu- tions form non-convex layers of standard fully connected networks. The papers Cao & Gui (020)) ; Nitanda
& Suzuki
(2021) include estimation and optimization errors, but require excessive over-parametrization as is typical in the current literature.
Estimation: The prior work Gentile Welper (2022) Welper 2024b establishes approximation and optimization error bounds. This paper contributes corresponding analysis of the estimation errors, based two alternative approaches. The first follows more traditional lines and bounds the complexity of the network directly. The second relies on smoothness bounds that arise from gradient descent training.
1.3 Overview
We use the following two techniques to show estimation errors.
The most common complexity measures are VC-dimension and Rademacher com- plexity, which in turn can be bounded by chaining techniques, i... by Dudley's incquality (Shalev-Shwarde & Ben-David 2014). In our case, is convenient. to skip the Rademacher complexity and use Dudley's inequality directly because it has already been used to establish NTK concentration inequalities for the approximation and optimization error bounds (Welper 2024b
Network Complexity:
We minimizes the sample loss
1 N 2
{(0) ( f(x.)1²
Σ
(3)
for N uniformly random normalized samples I; on the unit sphere gd-1 with gradient descent. We show that as long as the error does not satisfy the approximation and estimation error estimate
fo - (1 S m N
with network width m, the gradient descent error decreases exponentially. The rates a, b and c are specified in Theorem 2.2 below and depend on the Sobolev smoothness of the target function f. Although we optimize the discrete sample loss, we bound the error in the continuous (2d8111) norm and therefore obtain the expected or generalization error. The result is comparable to standard machine learning theory. In particular, the second term requires that the number of samples N is larger than the width of the network (up to some power).
Smoothness: While requiring more samples N than width m matches common wisdom in machine learning theory, it does not explain the empirical obscrvation that neural networks generalize well in over aver-parametried regimes. To establish generalization error bounds in this regime, we rely on a different complexity measure: The approximation and optimization results in Welper (2024b a) establish that the Sobolev norm of the gradient descont iterates [l.f=- fl remains uniformly bounded, independent the size of the network. If 1+d/2, Sobolev embedding theorems imply that fo is uniformly Lipschitz and therefore the estimation error bound (2) can be proven by uniform laws of large numbers (Vershynin 2018 Section 8.2).
4

---

Published in Transactions on Machine Learning Research (02/2023)
Unfortunately, the current theory only provides bounds for 1/2, insufficient for the argument. We may, however, proceed with the kernel loss
N (k(as, 5, 112.
(0) 2N
(4)
with uniformly random 24, which probes the residual fo f with an integral kernel k(z, y), 2, y s in the L2 inner product (. and is casier to bound in low regularity settings. Morcover, for common kernels like the heat kernel, Gaussian kernel e=12-v?/0² or Laplacian kernel e-lx-yl/o this loss converges to the standard mean squared loss for
and proper normalization.
Although our interest in this kernel loss is of theoretical nature, to explore arguments for generalization in over-panee ceet-paaamttized regimes, it is similar to variational losses in VPINNs (Kharazmi et al.) 2019 2021 used to solve PDEs with neural networks. In this application, it is common that PDE solutions do not admit continuous point evaluations, and instead one probes the residual (fa - f.v) with test functions v from some linear subspace, for which the given kernels would be one example.
The kernel loss also bears a resemblance with randomized smoothing (Cohen al. 2019 : In order mitigate adversarial allacks on classifier for y classes, these methods choose the class that is most likely under normal perturbations ~ 63)
g(x) arg maggaa Pr [fo +c)
cEy
In comparison, for a Gaussian kernel with variance 82, the kernel loss is identical the mean squares loss of the averaged network
(o(x) = E[fo(1 + c)] (k(x,)),fo)
The second main result shows that for the kernel loss, gradient descent decreases exponentially until it reaches the approximation and estimation error
[e / (1222 S m + N
again with rates a and dependent on the Sobolev regularity of f as specified in Theorem 2.4 The two error contributions on the left. hand side are decoupled and we achieve the worst case of the approximation error m and the sample error - Contrary to the first result and conventional machine learning theory, this allows meaningful generalization errors even in over-parametrized regimes with more samples N than width m.
Estimation and Gradient Descent: To obtain the results, do not bound the difference between empirical and expected loss (2) directly. Instead, compare the gradient descent evolution to an idealized method trained on the continuous L2 loss:
g"
trained by gradient descent on loss 13 or
trained by gradient descent on loss [ / 11122 (844-11
Convergence of the latter is establishod in Welper 2024a From this we prove convergence for the former based on perturbation analysis and sample errors for the respective gradients (not the loss as in standard analysis ). This approach reminiscent of Cohen et al. (2002), which analyzes adaptive PDE solvers by comparing them with idealized infinite dimensional ones. The sample errors are established by Dudley's inequality for the sample loss 8 and by matrix Bernstein inequalities for the kernel loss 44.
2 Main Results
This section contains the main results of the paper.
5

---

Published in Transactions on Machine Learning Research (02/2023)
2.1
Setup
The setup is almost identical to Welper (024b a). with the major difference that the references train idealized continuous (2(5)11) loss, whereas we train practical sample losses.
Notations We denote generic constants by c, which may be different in each occurrence, but do not depend the width m, number of samples N or input dimension d. Alternatively, we use the shorthand S b, a a b, a ~ b to denote I cb, 2 cb, S b S respectively.
For integer 8, Sobolev spaces Ha (Sd-1) consist of all functions on gd-1 with L2 (Sdd11 bounded weak deriva- tives of order s. For non-integer s, these spaces can be defined by the decay of their expansion
1 1)
0c Σ Σ
(1
122112211
22)) 20 (x,,r))
(5)
j=1
in spherical harmonics
y
0, 0,1,2....
s5)s((),
(6)
for suitable numbers v((), see e.g. Barceló et al. 2020
We denote the corresponding inner product by
Network We consider fully connected networks without bias
f'(x) = Wo,, 1/2 (f (= (x+ = m'm
(7)
of depth L, with normalized imputs in the unit sphere I E S and standard scaling. We summarize trainable weights in the parameter 0 and abbreviate the network by fo(x) = fx+ To obtain simple non-convex model problem, we optimize the second but last layer WL-1 and initialize all weights randomly
Wh E (-1,+1]1xm
i..d. Rademacher
not trained, trained not trained
W1.1 E X
i.i.d. N(O,1)
W gmetxxme -= 1, L.
i.d. NN
T E xd
iid. 10,
not trained.
All hidden layers are of comparable size, the input d-dimensional and the output scalar:
m1-1,
== S my mn 2 d.
Activation Functions We require smooth activation functions with no more than linear growth and derivatives bounded as follows:
lo (x) |=|
(1) (1)
i= 1,2,
(0)) <p(x),
3, 4,
(8)
for some polynomial p(x).
Training All networks are trained by gradient descent
go+l = nr - Vol(0"),
(9)
with learning rate 7>> > We use different losses E(B) for the main results and define them in the respective sections.

---

Published in Transactions on Machine Learning Research (02/2023)
Neural Tangent Kernel The main results require coercivity of the neural tangent kernel, which has been
shown in Welper (024b) for ReLU activations based on Bietti & Mairal (2019); Geifman et al. (2020); Chen
& Xu 2022)) but remains open for smoother activations ( used in this paper. Since we only train the sccond but last layer, in our case the neural tangent kernel (NTK) is informally defined as
y(x,y)
lim Σ (.fo(t)0.ffo)))
(10)
width
with partial derivatives Ow--1 abbreviated by single index a with 1,.... R myma-1- The coercivity condition is then stated as
HJ= HI=I ((:,)))()) dy
(1, H. H.HfHssgge- & 11
(11)
for some 3 > O, all S {0, s) some smoothness level S S and all ( ). Again, for networks with ReLU activations, bias and all layers trained this true with d/2,, see Welper 2024b).
In addition, the main results require
(1)
L,
(12)
for the Gaussian process that describes the forward evaluation the random initial network in the infinite width limit (Jacot et al. 22188). Its correlation matrices E(x, y) E(x y) only depend on the angle between 2, y Sd-1 and are, defined by
(x,,,) xy,
Ex y)
Ed -01 v) == (,, (u), (w)).
A
Σ Ex x.'
E E'yy v)
As for coercivity, this property is known for ReLU activations, where Σ(1) = 1, see Chen & Xu 2021 and is expected to be a minor technical assumption for smoother activations the NTK cocrcivity and with it left for futurre work.
The condition directly related
2.2 Result I: Pointwise Sampling
For the first result, use the standard least squares loss
1 1 {(0)
Σ ((x,))
(13)
2
with N independent uniform samples I; E 8d-1 We first collect all major assumptions.
Assumption 2.1. Assume:
The neural network
8 is trained by gradient descent 9
The NTK satisfies coercivity for 0 S 2s < 3 and the forward process satisfies 12
All hidden layers are of similar size: mo ~ m m.
Smoothness is bounded by < 1/2.
5. Define h and follows and choose learning rate & and arbitrary that
h ekm 2T
= 2.20
7. 3 h/m,
0sa<l-s
for some constant Ch. that may depend on the initial error I] fl fll

---

Published in Transactions on Machine Learning Research (02/2023)
The following result is similar to Welper 20244a Theorem 2.2), which only considers approximation and
optimization errors. While the reference trains on the continuous (2(S1=1) loss, we train on the discrete sample loss and therefore also include estimation errors.
Theorem 2.2. Assume we train the sample loss 13 let Assumption 2.1 1 be satisfied, let [ E m/ and define
3/2
A sample (m, NN ca N1/2 ht- 22 || fll (3-1)
for some sufficiently large ca. Then with residual n" == f0n f and probability at least - + while the gradient descent error exceeds the final approzimation and estimation error
122 2 ca (m- íía + A (m, N1) $ |
(8
k: n,
(14)
we have
|| (B(8--1) S -e->11** (0am00000mm (1) 11
(80-11)
|| [1
C'I[k"]] "1 (84-1)
for sufficiently large constants Cay e and C independent of m, kn and k².
The proof is in Section B.2 The assumptions relate the smoothness, the size the network and number of samples. The only major assumption the coercivity (11). 122, which is open for our activations but can
be easily inferred from the literature (Bietti & Mairal 2019 Geifman al., 2020 Chen & Xu 2021) for ReLU activations. In the latter case, B depends on the input dimension d and therefore all other bounds are also dimension dependent, although this is not explicit in the stated results. See Welper (2024b) for details, and numerical verification for smoother activations required in the theorem.
The result shows that gradient descent converges exponentially fast until the error sufficiently small 14] and we have
|| 118-111 co (m 2 + Asampte
(m, (m, Ni) || (87
(15)
The first summand, m + together with the smoothness ||<^ ||~0 11 1) provides a typical approximation
error bound of the form 1 The second term sample: bounds the sample error and has the typical N-1/2 dependence on the number of samples together with some factors of m and that measure the complexity of the network. In particular, for the overall error be small, we must have more samples than width m.
Remark 2.3. We can simplify the fonal error bound 15 as follows. First, we allow all constants to depend on the initial value xD and drop all terms that contain it. Nest, we distribute the outer expoment s/3 3 the summands, for the price of a slightly worse constant, and obtain
|| (1.1 S m 3 rra + Asample (m. N)a.
Next, we unravel the definitions of Asample and h to arrive at
|| 112 1) S m 1 - +
N1/2
3/2
1-
$
S m 2
N112
3/2
m
2140
1-
28
$
Observing the constroints on s, 3 and a, we abbreviate the exponents by some rumberr a, e 2 0 to obtain
[e - (84 S m + N-.
2.3 Result II: Kernel Sampling
Motivation
Generalization errors can be derived from bounds of the form
n Σ
sup llfo - f112n(80-1) - 2N
[f((z.) - f((x)) SC+N-1/2
8

---

Published in Transactions on Machine Learning Research (02/2023)
which controls the difference between the expected and empirical loss, uniformly in all parameters 0 contained in a set θ of all relevant parameters. The bound on the right hand side depends on some complexity measure C' such as Rademacher complexity. By the supremum in the estimate, the complexity bound usually depends on the size of the hypothesis class {fo 8 E )). In Theorem 2.2 this gives rise to the m dependent Asample(m) (m, N) and therelore to the requirement. of more samples than network size (although we technically apply the argument to the gradient, not the loss).
In order to decouple the size of the network form the number of samples, use the observation from Welper (202bb) or Theorem 2.2 that in the initial NTK regime the Sobolev norm HS*-1) of the residual K fo f does not grow, i.c. |** (8--8 I || (B4-))- Hence, we may replace the sample error with bound of the form
N Σ |x(x;)) 2NV
1
sup
|I (84-1)
SC+
(16)
| gdd-1, x s (as-11)
which is independent of the network size. If is sufficiently large so that 13 is embedded into L (gd-1)
with some margin, this estimate can be shown by a uniform law of large numbers, as e.g. in Vershynin (2018) Chapter 8.2). Such an embedding also ensures a bounded loss function, which is assumed for standard VC dimension and Rademacher complexity bounds of the gencralization error. For small 8, favorable right hand side cannot be expected. Indeed, the map continuous, otherwise one can find perturbation R so that || Lg [ S || R S || R|| is small and ||<|| ||]|| is large and as a result the left hand side of (16) must be large for either k or R. By the Sobolev embedding theorem (Adams & Fournier 2008) the continuity holds for s 2 d/2 and fails otherwise. Unfortunately, our results provide low Sobolev regularity & < 1/2, insufficient for this embedding.
||<]]] 1. Ex Im(x;)]? from H to R must be
For first theoretical exploration of alternative complexity measures and in order to stay compatible with carlier approximation and optimization results, we change the point evaluation to localized integrals
1 2N
eh (0)
(K(,,, 1, 113
(17)
with uniformly random x; and some integral kernel k: d: gd-1 R that is smoothing and allows continuous evaluation for all 0. Note that many standard kernels, like heat, Gaussian and Laplacian kernels, converge to the Dirac delta for their "width" going to zero. As a result, the loss e converges to the regular mean square loss E in 13 See Section 2.4 for more details.
Kernels Before we state the main result, we need some properties of the kernel. First, we assume is zonal, i.e. that k(z,y) v) k(>"g). As a result, by the Funk-Hecke formula (Atkinson & Han 2012) the eigenfumctions are spherical harmonics Y
6 and for the corresponding eigenvalues Aij. we require
1 \uj $1, ISL 15is v(),
(18)
Au 1, 1> isss v())
so that up to a limiting level L > 0 the eigenvalues are of unit size and falling thereafter. In addition, the kernels are bounded
sup [|k(2, )122 S Ck.
(19)
zeD
We defer more thorough discussion of kernels with the given properties to Scction 2.4 and for the time being consider convolutional kernel on the line instead of zonal kernel on the sphere, to avoid lechnicalities.
In this case, a natural example is the Gaussian kernel ko(x - y) /2 Fourier transform with continuous eigenvalues
It is diagonalized by the
2.22
e X(w) = ko(w) = 2 π
for which we obtain 18 by the simple observation
X(w) & 1, w E R.
X(w) Z1
9

---

Published in Transactions on Machine Learning Research (02/2023)
Similar kernels the sphere are more technical and discussed in Section 2.4
Result Unlike more traditional complexity measures in machine learning, the smoothness H- [I="| is byproduct of the gradient descent method and independent of the size of the nelwork. This yields error bounds with decoupled approximation and sampling error in the following theorem.
Theorem 2.4. Assume train the kernel loss (17) with conditions 18
19
and corresponding constants
C₁ and L. Let Assumption 2.1 be satisfied and for arbitrary IN 2 N define
1/2 +
N
1/2
A (m, N) ca c
+C
-
L
N
TN
for some sufficiently large ca. Then with K" == fen-f and probability at least 1- 2TN [eTN - TN - -1] while the gradient descent error exceeds the final approzimation and estimation error
|| 1122080811 2 co (m 1m-22m 2 + sammpe(m, NY) $ || (11
n
we have
||x" (.nlli (82-111) S Ce 7e + Am (8e
C'In || 5 (I (8-
for sufficiently large constants Ca, c and C independent of m, Ra and n²"
As for Theorem 2.2 the error decays exponentially until the final sum of approximation and sample error is reached. Unlike Theorem 2.2 the sample error (mampte(m, .V) does not depend on the network size m. Hence, the final error is the worse the approximation and the sample error and provides meaningful error bounds both in under- and over-parametrized regimes.
If we choose the best possible ratio N C+ T,a between the number of samples N and the success probability parameter TN, given the parameters L and Cş of the kernel, obtain
TN
A sample (m, N) (1 (1+caal cc))
(20)
converging to zero for large corresponding to locally concentrated kernels, see Section 2.4
The theorem contains the inequality|| (g [ bounded in the Sobolev norm. Hence, for the generalization error, we consider the hypothesis class of bounded Sobolev functions, instead of neural networks with bounded weights as typical Rademacher or margin bounds.
S (()=")))--000-))) and therefore x" fo remains
Remark 2.5. Analogous to Remark we can oblain a simplified error bound after training
fl 1122,13 1) S m * -
Here, we use that Asaple does not depend on m and can be bounded by (20 To eliminate L, we con choose e.g. TN = VN and solve the ratio = C² La for N. Note, however, that Ck and are not independent, which is worked out for the heat kernel in 22 below.
2.4 Kernels
In this section, we consider kernels that meet our assumptions
18 and
19
Heat Kernel We first consider the heat kernel k, (x, y) on the sphere gd-1 defined as the solution of the heat equation with Dirac delta as initial condition Zhao & Song 2018
V.ke(..v) - Akrl..v 0,
ko y) 8(-,))
10

---

Published in Transactions on Machine Learning Research (02/2023)
where A is the Laplace-Bos Laplace-Beltrami Beltrami operator on the sphere and 8( y) the Dirac delta distribution the sphere. On the flat space Rd, this kernel is identical to the Gaussian kernel (2z)-1/24- x =-vlptt" while the sphere they differ. We use the heat kernel because it allows particularly simple verification of our kernel assumptions.
Indeed, since the Laplace-Beltrami Beltrami operator's cigenfunctions are spherical harmonics Y/ with eigenvalues -I(l + d ---) 2) [Atkinson & Han 2012), the heat equation has the explicit solution
ke(2, v) = Σ
uta My (x)) (1) 6(, 6(,,)) Σ
1(++ 2) (z)
(21)
Lj
1
in its eigenbasis. Therefore, the eigenvalues of the kernel are A = 1(+dd22) and with 1(l + d - 2)t s 11
S t- 1-1/2 we have
S N1 1
1 1-1/2
Nd S 1,
1 12 1-/2
so that the kernel assumption 18 is satisfied with I. = ct 1/2 Since the eigenvalues decay exponentially, the Sobolev norms of the kernel are bounded. More concretely, Lemma D.1 in the supplementary material shows that
(1 2) S C2 =: ct d+3//2
In conclusion, the heat kernel satisfies all assumptions of Theorem 2.4 and the sample error (20
simplifies
to
A sampte (m, N) S (1 ca)1%/4
N t
2--
(22)
TN
for the given number of samples. By construction, for -> the kernel converges to the Dirac delta and therefore the kernel loss 17 converges to the sample loss 13
Gaussian and Laplace Kernels In order to obtain some further insight into permissible kernels, we consider the Gaussian and Laplacian kernels
1
1 س
kg(z y)
ky - y) 2t
22T
on the real line R. For s 1/2, these are clearly bounded in (R). Moreover, since these are convolutional kernels, the eigenvalues correspond to the Fourier coefficients, given by
ko(w)) = 2/T
kz(W) = V 11+
e
Thus, we easily obtain the analogues of the eigenvalue bounds 18
ko(w) $1,
w R,
ka(w) 2 1,
w²6 < 1 1w 7'
hy (w) 1,
IR
(w)) 11
wat < + |o|
Similar results on the sphere are significantly more involved and beyond the scope of this paper. See c.g. Geifman et al. (2020) Appendix C) for an analysis of the Laplace kernel, without the fine grained dependence on f required for our purposes.
2.5 Sketch of Proof
Overview This section contains a short overview over the proofs of Theorems 2.2 and introducing a scale of continuous loss functions
2.4
We start by
1 - (
(s(0)
S E (0,8).
2
11

---

Published in Transactions on Machine Learning Research (02/2023)
For S 5=0 0, this loss is the generalization or L2(D) error. For S = O, the loss is used to control the Sobolev smoothness of the neural networks later in the proof. For convenience, we abbreviate (:: = ( HD(D)) and K := fe- - f. A simple calculation and the mean value theorem yield that the loss evolves as
ks(0") - Σ (r, 0
for some 9 on the line segment between 0 and g--1. On the left hand side, we use the &g loss, i.e. the generalization error or the smoothness, because these are the quantities we ultimately want to control in the theorems. On the right hand side, we have the discrete loss l that we actually train on. By perturbation argument, we replace the discrete loss with the continuous one:
(s(0nt1)- - (s(0")= = - Σ (n"
- E (k" 8rfa) (0,((0)) )r
=: GDo + PERTURBATION
The perturbation term will be bounded by
PERTURBATION & 7Asamppe (m,, N N) |loll**
giving rise to the terms (mmmtee N) in the main theorems.
Convergence of GD, We first consider the case that the perturbation term PERTURBATION zero. This
corresponds to training the continuous (2) loss to directly and has been studied in Welper 2024b a). The convergence analysis is based on the observation that
Eo(0r+1)- lo(0r) S -y "e",Hn"), + perturbation, (0(+1) (,(0") S -r "r",H""), perturbation,
(23)
where H is the linear integral operator induced by the neural tangent kernel
A ((x = lim Σ width
(1)
In short, the terms -y (k<", ".n,,Hi Hs") are lincarization of the gradient Voll1 usually found in gradient descent analysis. This linearization remains accurate because of the crucial observation that the weights go - n do not move far from their initial during training.
Ignoring the lincarization error, the left. hand sides of (3 are bilinear forms and therefore allow simple convergence proofs if the cigenvalues of are lower bounded. While this true in over-paramen cer-parametrized regimes, for the (2) loss, the NTK is compact operator and the eigenvalues converge to zero. Therefore, consider coupled evolution of the to and E, losses: The latter ensures that the networks remain uniformly bounded in the Sobolev norms (D). This implics that the residual n" is concentrated in low frequencies or equivalently eigenspaces corresponding to large eigenvalues. Therefore, the system is comparable to ones with lower bounded eigenvalues and allows us to prove convergence of the to loss.
Since this theory already contains perturbation terms, the new terms PERTURBATION from sampling the gradient can be added the theory with only minimal changes, shown Theorem A.I
Bounds for PERTURBATION The main new contribution of the paper is to show that PERTURBATION, i.e. the difference between the gradients of the continuous loss to and the discrete loss & remain small. The arguments are similar to standard generalization error bounds, which address the difference between to e directly.
Classical techniques to bound generalization errors inchude VC-dimension or Rademacher complexity, which, in turn, are sometimes bounded by Dudley's inequality (Shalev-Shwartz & Ben- David 2014]
12

---

Published in Transactions on Machine Learning Research (02/2023)
In Section B use the latter directly to bound PERTURBATION for the least squares loss 13 This is convenient because similar techniques are used in the prior work Welper (2024b) to show concentration of the NTK. The argument is reminiscent of the uniform law of large numbers as shown in Vershynin (0018 Chapter 8.2).
2. For the kernel loss 17 take different route in Section C First, in the limit of infinite samples, heat, Gauss and Laplace kernels do not converge to the L2 -l-sss. They rather converge to a dual norm Il5o - / r for primal norm || |I = Pli + 4l| 11 HD(D)) some a > 0 and a parameter for the width of the kernel.
In the NTK convergence analysis, we have already shown that the residual før - f is concentrated in low frequencies and as a result for carefully chosen t, the Lz(D) part of the above norms dominate the Ha part. Together with concentration results for the kernels, this time shown by matrix Bernstein inequalities, this implies gradient descent convergence in the L2 norm.
Remark on Generalization Errors and Optimization Many generalization error bounds in the liter- ature involve terms like N- |W W/ le (or other norms) that include the distance of the weights from their initial, which stays small in NTK gradient descent convergence proofs. Concretely, if we use the bound from the first equation the proof of Theorem A.I. which underlies all main results, we obtain on the trained layer
- 1 11- S m m W =: ml10 Goll. S mh m--irda S 1/2
for some a 2 0, where || is the Frobenius norm, || the spectral norm and the middle equality the definition of the || ||. norm. Therefore, the generalization error bounds be further bounded by Hence, to obtain small generalization error, must be in an under-perametrized regime with < N. This conflicts with over-paramettriatioon assumptions in most NTK convergence results. While the generalization bounds and NTK convergence may be reconciled with a finer analysis, we rely on the NTK results in Welper 2024b a), which also work in under-parametrin regimes.
N= 1 W
N
2.6 Extensions
This section contains a brief outlook on two major assumptions.
Training of all Layers In the main Theorems 2.2 and 2.4 we train only the second but last layer, while all other weights remain frozen at their random initialization.
Including the remaining layers is relatively simple in standard NTK theory. The training of cach layer adds one matrix Hé to the NTK, that training select layers A C II. the gradient descent loss reduction in 23 becomes
(o(ttt1 - lo(0m) S
Σ (N". H + perturbation.
EEA
For finite networks and their infinite width limits, the terms (,"H"mn") 2 are non-nogative so that including more layers in the training gives strictly sharper results.
The argument is more delicate for loss (0m) with smoother s 0, that we include in 23 extend standard NTK theory to undor-parametrizee regimes. In this casc, the terms {N", H² expected to be non-negative in the infinite width limit and only approxinately so for finite width networks. Therefore, careful additional perturbation and concentration analysis would be required to include the training of all layers in the main theorems, which is beyond the scope of this paper.
Sample distribution The fully connected networks in 7 do not have a bias and as a result, the input æ always yiclds output fo(x) = o, independent of the network weights. This degenerate case is avoided by restricting the input the sphere. Introducing bias would likely avoid this issue and allow more general domains, however, this would require revision of cited results in Appendix D Non-uniform distributions
13

---

Published in Transactions on Machine Learning Research (02/2023)
would likely require some changes, in particular, the Sobolev norms in the smoothness bounds would need to be adapted accordingly.
3 Numerical Experiments
In this section, we supplement the theoretical findings with some preliminary numerical convergence rates with respect to network width and number of samples. We consider the following test case:
Network Architecture: Fully connected with bias and ReLU activation.
Input data: Uniformly distributed on the cube [-1,
Labels: Gaussian density function of the input samples, i.e. = e
Test Loss: In order to approach the L2(D) error, the test loss computed on large number of 1000 uniformly sampled zq with mean squared loss, no malter the loss function used for training.
To approximate the kernel loss, we uniformly sample N points =; E [-1, 1] and then for each i we sample N₂ = 10 samples from the normal distribution (2, 0.01) to obtain 24 E NNN, Then, we approximate the kernel by Monte Carlo integration
Kernel Loss:
(0) ~
fo(wig) - f(ziz)
Training: 20000 gradient descent steps with learning rate 0.05.
Repetition: Since the randomness of data and initialization is important for the theoretical results, all reported losses are an average of 20 trials.
After sulficiently many gradient descent steps, in m and N, Theorems 2.2 and 2.4 guarantee the convergence rates
fl f11,, S m 0.00277 + m 0.1991 N-0.0833
Ilʃe - -11222804-1 S m 00.0777
+ N N-0.0033
respectively, where we have chosen dimension d = 3, 3 = d/2, which is true for ReLU activations described after [I], m 3/2} 1/2, which is the maximal allowed value in the theorems and a = 8, which is the (excluded) upper limit. In addition, for the kernel bound, we use 12 with TN = N/2, to balance the number of samples and the kernel width.
For comparison, we also consider the best possible rates for functions with bounded Sobolev norm HS The best. approximation rate be computed with manifold width (Lorentz et al. 1996) and the best possible sampling rate is the minimax rate (Yang) 1999 Tsybakov 2009), given by
m
respectively. These are higher than the guaranteed rates in the main theorems. For classical approximation methods, the smoothness is capped by the polynomial's degree, which would be two for ReLU activations, yielding rate m m/33 The definition of the minimax rate is independent of the neural network and therefore allows 8 + 00 and hence rate N-1/2 (up to possibly growing constants).
Figure and Table I contain the estimated convergence rates of the test loss for training with mean squared loss (MSE) 13 and kernel loss (17). All plots are log scale that slopes along the or y axes correspond to convergence rates. To compare the rates, note that the MSE loss Il fll reported in the tables differers from the error [o fl] 1, in the theoretical bounds by a square.
14

---

Published in Transactions on Machine Learning Research (02/2023)
0.00104
0.000638
0.000597
0.000391
0.000343
Loss
0,00024
0.000197
0.000147
0. 0.0001133
32
9e-05
32
6.49e-05
40
5. 5.52e-05
40
50
48
Witth
50
48
Width
1000
56
1000
Samples
150
250
Samples
150
200
250
64
(a) MSE Loss, dim=3, depth=5.
(b) Kernel Loss, dim=3, depth=5.
Figure 1: Test loss for training with mean squared loss 13 (left) and kernel loss log-scaled so that the slope corresponds convergence rates.
17
(right). All axes are
Dimension and Depth 5
Trained with MSE Loss
dof rate
N rate
m
N
100
150
200
250
100
150
200
250
40
0.331
1.33
1.33
1.19
1.9
1.36
0.743
0.896
48
0.833
0.328
0.628
1.06
1.86
1.13
0.933
1.25
56
1.13
0.969
1.25
0.434
2.2
1.07
1.08
0.684
64
-1.03
2.05
0.967
1.47
1.56
2.08
0.582
0.985
Dimension 3 and Depth
Trained with Kernel Loss
dof rate
rate
m N
100
150
200
250
100
150
200
250
40
1.08
0.676
0.748
1.07
1.65
0.939
0.797
0.482
48
0.229
0.517
0.433
1.05
1.23
1.07
0.744
0.987
56
1.69
1.77
1.75
1.11
2.02
1.1
0.734
0.539
64
-0.54
-0.218
0.898
1.19
1.71
1.21
1.25
0.713
Table 1: Estimated convergence rates between neighbouring losses for the given m/N. Left: Rate along the column, i.c. with respect to m. Right: Rate along rows, i.c. with respect to number of samples N. The first table is trained with mean squared loss (MSE)
13) and the second with kernel loss [17
We first observe that the reported rates have significant variance despite being averaged over 20 separate runs. Individual runs are even more noisy. The majority of the table entries remain below the theoretically optimal rates, but are higher than the rates guaranteed by the theorems. While the thcorems seem pessimistie, is worth noting that the optimal rates utilize the high smoothness of the target. function s 2 2, whereas the theorems only allow smoothness up to 1/2. At the expense of high rates, this does allow much rougher target functions for which the optimal rates would be lower, as well. More detailed experiments are left for future work.
Finally note that despite severe over parametrization, the loss decreases with respect to N, although with slowing rate. This matches the thcoretical results for the kernel loss, which provides bounds in over- parametrized regimes, but does decrease below the approximation error. More detailed results, including the loss and shallow networks, contained in Appendix F.
15

---

Published in Transactions on Machine Learning Research (02/2023)
4 Conclusion
The literature contains large number of papers that bound approximation, estimation and optimization errors of neural networks. Because of conflicting assumptions, these results are usually not compatible. This paper contains a unified analysis that bounds all three error components at once. Unlike the contemporary literature, it does not rely on excessively wide networks or over over-varameet parametrization. Instead, we have seen for kernel loss that the generalization error can be bounded by the maximum of approximation and estimation errors, independent of any relation between width m and number of samples N.
The generalization errors of this paper achieved for bounded number of gradient descent steps, where the training dynamics is dominated by the neural langent kernel (NTK). Beyond this bound, the NTK loses its relevance and more nonlinear behaviour is possible. A rigorous analysis is left for future work.
References
Robert A. Adams and John J F. Fournier. Sobolev spaces. Number 140 in Pure and applied mathematics. Acad. Press, Amsterdam, 2. ed., [nachdr.]. edition, 2008. ISBN 9780120441433.
Ben Adcock and Nick Dexter. The gap between theory and practice in function approximation with doep neural networks. SIAM Journal on Mathemalics of Data Science, 3(2):624 655, 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Re- search, pp. 242-252, Long Beach, California, USA, 09-15 Jun 2019. PMLR. Full version available at https: / httaaaivvv..raaaaa http//ab///11...111 03962
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 254 263.
PMLR, 10-15 Jul 2018.
Sanjeev Arora, Simon Du, Wei HU, Zhiyuan Li, and Ruosong Wang. Fino-grained analysis of optimization and generalization for overparameteriiee two-layer neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 322-332, Long Beach, California, USA, 09-15 Jun 2019a. PMLR.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Russ R Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32.
Curran Associates, Inc., 2019b.
Amir Asadi, Emmanuel Abbe, and Sergio Verdu. Chaining mutual information and tightening generalization bounds. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biancha and R. Garnett (eds.). Advances in Newral Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Kendall Atkinson and Weimin Han. Spherical harmonics and approrimations on the unit sphere an indroduc- tion. Number 2044 in Lecture notes in mathematics. Springer- Verlaa, Berlin, 2012. ISBN 9783642259821.
Francis Bach. Breaking the curse dimensionality with convex neural networks. Journal of Machine Learning Research, 1811):115,,, 2017.
Yu Bai and Jason D. Lec. Beyond lincarization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations, 2020.
Juan Antonio Barceló, Teresa Luque, and Salvador Esteva. Characterization of sobolev spaces on the sphere. Journal of Mathematical Analysis and Applications, 491(1):124240, 2020. ISSN 0022-247X.
16

---

Published in Transactions on Machine Learning Research (02/2023)
A. R. Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930-9M) 1993.
Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In M. Kearns, S. Solla, and D. Cohn (eds.), Advances in Neural Information Processing Systems, volume 11. MIT PRess, 1998.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normmaizzed margin bounds for neu- ral networks. In 1. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systemss volume 30. Curran Associates, Inc., 2017.
Christian Beck, Armulf Jentzen, and Benno Kuckuck. Full error analysis for the training of deep neural networks. Infinite Dimensional Analysis, Quantum Probability and Related Topics, (1(02):215000,, June 2022. ISSN 0219-0257, 1793-6306.
Julius Berner, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. The Modern Mathematics of Deep Learning. In Philipp Grohs and Gitta Kutyniok (ods.), Mathematical Aspects of Deep Learning, pp. 1-111. Cambridge Universily Press, 1 edition, 2022. ISBN 9781009025096 9781316516782.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. In H. Wallach, H. Larochelle, A. Beygekimer, F. d' d'Alché-Buee E. Fox, and R. Garnett (eds.), Advances in Neurul Infor- mation Processing Systems, volume 32, Curran Associates, Inc., 2019.
Guy Bresler and Dheeraj Nagaraj. Sharp representation theorems for ReLU networks with precise dependence on depth. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (ods.), Advances in Neural Information Processing Systems, volume 33, pp. 10697 10706. Curran Associates, Inc., 2020.
Yuan Cao and Quanquan Gu. Generalization Error Bounds of Gradient Descent for Learning Over- Parameterized Deep ReLU Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 34((4))3344933 3356, April 2020. ISSN 2374-3468, 2159-5399.
Lin Chen and Sheng Xu. Deep neural tangent kernel and laplace kernel have the same rkhs. In International Conference on Learning Representations, 2021.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-parameelerization is sufficient to learn deep reflu} networks? In International Conference on Learning Representations, 2021.
Lénaic Chizat and Francis Bach. On the global convergence of gradient descent for wee-parameterized models using optimal transport. Tn S. Bengio, H. Wallach, H. Tarochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. https://arxiv httppp://aaxxio.og//bbb///////// ab/////5..1110...... 19044495550......
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
A. Cohen, W. Dahmen, and R. DeVore. Adaptive Wavelet. Methods II Beyond the Elliptic Case. Founda- tions of Computational Mathematics, 2(3):203 202, August 2002. ISSN 16153375.
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In Kamalika Chaudhuri and Ruslan Salakhutdinov (ods.), Proccedings of the 36th International Conference on Machine Learning, volune 97 of Proceedings of Machine Learning Research, pp. 1310 1320. PMLR, 09-15 Jun 2019.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signal Systems, 2: 303 314, 1989.
I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear Approximation and (Deep) ReLU Networks. Constructive Approrimation, 55(1):117-172, February 2022. ISSN 0176-4276, 1432-0940.
17

---

Published in Transactions on Machine Learning Research (02/2023)
Ronald DeVore, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numerica, 30: 327-444, 2021.
Selina Drews and Michael Kohler. On the universal consistency of an over-paranelrized deep neural network estimate learned by gradient descent, 2022. hctps://arxiw.org/aaa http:/iwwwrr//bbb//////baaa 14283
Simon Du and Jason Lee. On the power of over-parametrization in neural networks with quadratic activation. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1329 1338. PMLR, 10-15 15 Jul 2018.
petps://arxisn www.iii.....aaaaeeeeeeee htte/bbb/1100..... 1803.1033.000 01206
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai, Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1685-1685, Long Beach, California, USA, 09-15 Jun 2019a. PMLR.
Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2019b.
Rong Ge, Jason D. Lee, and Tengyu Ma. Learning onc-hidden-layer neural networks with landscape design. /t/1//ab/1111..0000
In International Conference on Learning Represenlations, 2018.
Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Basri Ronen. On the similarity between the laplace and neural tangent kernels. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Tin (eds.), Advances Neural Information Processing Systems, volume 33, pp. 1451-1461. Curran Associates, Inc., 2020.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' d'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. CoRR, abs/1901.01608, 2019.
R. Gentile and G. Welper. Approximation results for gradient descent trained shallow neural networks in wttp:/wwwwr//bbb//2/.002333
1d, 2022.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural net- works. In Sébasticn Bubeck, Vianney Perchet, and Philippe Rigollet (ods.), Proceedings of the 31st Confer- ence On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 297 299. PMLR, 06-09 Jul 2018.
Rémi Gribonval, Gitta Kutyniok, Morten Niclson, and Felix Voigtlaender. Approximation Spaces of Decp Neural Networks. Construclive Approzimation, 55(1):255 367, February 2022. ISSN 0176-4276, 1432-0940.
Philipp Grohs and Felix Voigtlaender. Proof of the Theory-to- Practice Gap in Deep Learning via Sampling Complexity bounds for Neural Network Approximation Spaces. Foundations of Computational Mathemat- ies, July 2023. ISSN 1615-3375, 1615-3383.
Ingo Gühring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep ReLU neural networks in ws.p norms. Analysis and Applications, 18(05):803 859, 2020.
Boris Hanin and Mark Sellke. Approximating contimuous functions by ReLU nets of minimal width. https //arxiv.org abs/1710. 11278 2017.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Reseorch, pp. New York, New York, USA, 20-22 Jun 2016. PMLR.
Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight VC-dimension bounds for piecewise lincar neural networks. In Satyen Kale and Ohad Shamir (ods.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 1064-1068. PMLR, 07-10 Jul 2017.
18

---

Published in Transactions on Machine Learning Research (02/2023)
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Compuler Vision and Paltern Recognition (CVPR), pp- 770-778, June 2016.
Lukas Herrmann, Joost A. A. Opschoor, and Christoph Schwab. Constructive deep ReLU neural network approximation. Journal of Scientific. Compuling, 90(2):75, 2022.
Kurt Hornik, Maxwell Stinchoombe, and Halbert White. Multilayer feedforward networks are universal approximators. Newral Networks, 2(5):359-366 1989. ISSN 0893-6080.
Daniel Hsu, Sham Kakade, and Tong Zhang. Tail inequalities for sums of random matrices that depend on the intrinsic dimension. Electronic Communications in Probability, 17:1 - 13, 2012.
Shokhrukh Ibragimov, Arnulf Jentzen, and Adrian Riekert. Convergence to good non-optimal critical points in the training of neural networks: Gradient descent optimization with one random initialization overcomes all bad non-global local minima with high probability, 2022. https://arxiv. httpp::/aaaxii.og/abbbbb.. wrg/abs/22122 2212. 13111
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (ods.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
Daniel Jakubovitz, Raja Giryes, and Miguel R. D. Rodrigues. Generalization Error in Deep Learning. Tn Holger Boche, Giuseppe Caire, Robert Calderbank, Gitta Kutyniok, Rudolf Mathar, and Philipp Petersen (eds.); Compressed Sensing and Its Applications, pp. 153 193. Springer International Publishing, Cham, 2019. ISBN 9783319730738 9783319730745.
Armulf Jentzen and Adrian Rickert. A proof of convergence for the gradient descent optimization method with random initializations in the training of neural networks with relu activation for piecewise linear target functions. Journal of Machine Learning Research, 23 (320))111500, 2022.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks. In International Conference on Learning Representations, 2020.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent, kernels, transportation mappings, and universal approximation. In International Conference on Learning Representations, 2020.
Kenji Kawaguchi and Jiaoyang Huang. Gradient descent. finds global minima for generalizable deep neural networks of practical sizes. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 92 99, 2019.
E. Kharazmi, Z. Zhang, and G. E. Karniadakis, Variational physics-informed neural networks for solving partial differential equations, 2019. https://arxiv org/abs/1912.0082
Ehsan Kharazmi, Zhongqiang Zhang, and George E.M. Karniadakis. hp-vpinns: Variational physics- neural networks with domain decomposition. Computer Methods in Applied Mechanics and Engineering, 374:113547, 2021. ISSN 0045-7825.
Jason M. Klusowski and Andrew R. Barron. Approximation by combinations of ReLU and squared ReLU ridge functions with e and e controls. IEEE Trunsactions on Information Theory, 64(12):7649-766 2018.
Michael Kohler and Adam Krzyzak. Analysis of the rate of convergence of an over-parametrizee deep neural network estimate learned by gradient descent, 2022. http:::://aaxi..o///b/////// 01444
Alex Krizhevsky, Πya Sutskever, and GeofTrey E Hinton. Imagenet. classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097 1105. Curran Associates, Inc., 2012.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dicksiics,,,,, and Jeffrey Pennington. Wide neural networks of any depth evolve as lincar models under gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alch-BBuc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
19

---

Published in Transactions on Machine Learning Research (02/2023)
Jongmin Lee, Joo Young Choi, Ernest K. Ryu, and Albert No. Neural tangent kernel analysis of deep narrow neural networks. In Kamalika Chaudhuri, Stelanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12282-12351. PMLR, 17-23 Jul 2022.
Bo Li, Shanshan Tang, and Haijun Yu. Better approximations of high dimensional smooth functions by deep neural networks with rectified power units. Communiccation in Compulational Physics, 27(2):379 411, 2019. ISSN 1991-7120.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8157-8166. Curran Associates, Inc., 2018.
Zhong Li, Chao Ma, and Lei Wu. Complexity measures for neural networks with general activation functions using path-based norms, 2020. http:://aaxxiv.og//bbb//////// 06132
Tengyuan Liang, Tomaso Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, gcometry, and complexity of neural networks. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the T'wendy-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 888 896. PMLR, 16 18 Apr 2019.
Fusheng Liu, Haizhao Yang. Soufiane Hayou, and Qianxiao Li. From optimization dynamics to generalization bounds via Lojasiewicz gradient inequality. Transactions on Machine Learning Research, 2022. ISSN 2835- 8856.
George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz. Constructive Ayprozimation: Advanced Problems. Springer-Verlag Berlin Heidelberg, 1996.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. SIAM Journal on Mothematical Analysis, 536555556555 2021.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Aduances in Neural Information Processing Systems 30, pp. 6231-6239 Curran Associates, Inc., 2017.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layer neural networks. Proceedings of the National Academy of Sciences, E76633) 2018. ISSN 0027-8424. httts:://arxts org/ abaaaaaaaaaa http//884.06600 06561
Stanislav Minsker. On some extensions bernstein's inequality for self-adjoint operators. Statistics & Probability Letters, 127:111 119, 2017. ISSN 0167-7152.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information-theorciic generalization bounds for stochastic gradient descent. In Mikhail Belkin and Samory Kpotufe (eds.), Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pp. 3526-3566 3545. PMLR, 15-19 Aug 2021.
Behnam Neyshabur, Ryota Tomioka, and Srebro Nathan. Norm-based capacity control neural networks. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1376-1400 Paris, France, 03 18-06 Jul 2015. PMLR
Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Srebro Nati. Exploring generalization in deep learning. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advonces in Neural Information Processing Systems, volume 30. Curran Associates, Tne., 2017.
20

---

Published in Transactions on Machine Learning Research (02/2023)
Behnam Neyshabur, Srinadh Bhojanapalli, and Srebro Nathan. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Represenlations. 2018.
Quynh Nguyen and Matthias Hein. The loss surface of deep and wide neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Reseorch, pp. 2603-2612. PMLR, 06-11 Aug 2017.
Quynh N Nguyen and Marco Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11961-11972. Curran Associates, Inc., 2020.
Atsushi Nitanda and Taiji Suzuki. Optimal rates for averaged stochastic gradient descent under neural tangent kernel regime. In International Conference on Learning Representations, 2021.
Joost A. A. Opschoor, Philipp C. Petersen, and Christoph Schwab. Deep ReLU networks and high-order finite clement methods. Analysis and Applications, 18(6)):7),-770, 2020.
S. Oymak and M. Soltanolkotabi. Toward moderate overparameterization:: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84-105, 2020.
Sejun Park, Umut Simsekli, and Murat A Erdogdu. Generalization bounds for stochastic gradient descent via localized 8) varresiioonS-covrr In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acla Numerico, 8:143-195, 1999.
Daniel A. Roberts, Sho Yaiday, and Boris Hanin. The Principles of Deep Learning Theory: An Effective Theory Approuch to Understanding Neural Networks. Cambridge University Press, 2022.
Grant M. Rotskoff and Eric Handen-Eijnded Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. CoRR, abs/1805.00915 2018. https://arras https/////xxivoo//bbbb/////// wwwp:/o////aa/eeeeeeeeee aa0aaa//.../..////// 00915)
Itay Safran and Ohad Shamir. Spurious local minima are common in two-laycr RcLU noural networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 4433 088-4441, Stockholmsmässan, Stockholm Sweden, 10 15 Jul 2018. PMLR.
S. Shalev-Shwartz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Un- derstanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. ISBN 9781107057135.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Nonlinear approximation via compositions. Neural Networks, 119:74-80 84, 2019. ISSN 0893-6080,
Jonathan W. Siegel and Jinchao Xu. Approximation rates for neural networks with general activation functions. Neural Networks, 128:313-32/. 2020. ISSN 0893-6080.
Jonathan W. Siegel and Jinchao Xu. High-order approximation rates for shallow neural networks with cosine and * activation functions. Applied and Computational Harmonic Analysis, 58:1-25 2022a. ISSN 1063-5203.
Jonathan W. Siegel and Jinchao Xu. Optimal convergence rates for the orthogonal greedy algorithm. JEEE Transactions on Information Theory, (8(5):3354-3361 2022b.
Jonathan W. Siegel, Qingguo Hong, Xianlin Jin, Wenrui Hao, and Jinchao Xu. Greedy training algorithms for neural networks and applications to PDEs. Journal of Computational Physics, 484:112084, July 2023.
ISSN 00219991.
21

---

Published in Transactions on Machine Learning Research (02/2023)
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A law of large numbers. STAM Journal on Applied Mathemalics, 80(2):725-755 2020.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D. Lee. Theoretical insights into the optimization land- scape of over-varanne over-paramettrized shallow neural networks. IEEE Transactions on Information Theory, 65(:):
742 769, 2019. httpss//aarxi..oorr/ba///1/// 04926
ChaeHwan Song, Ali Kamezani-Kebrya, Thomas Pethick, Armin Eftekhari, and Volkan Cevher. Sub- quadratic overparameterization for shallow neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Newral Information Processing Systems, vol- une 34, pp. 11247 11259. Curran Associales, Inc., 2021.
Zhao Song and Xin Yang. Quadratic suffices for over-paramelriiatioo via matrix chernoff bound, 2019. htttps//arxiv... httg//bb/1990..0000
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks, 2016. /tapes//arrav.orrg/aa//E66..... 08361
Elias M. Stein and Guido Weiss. Introduction to Fourier Analysis on Euclidean Spaces (PMS-32). Princeton University Press, December 1972. ISBN 9781 478188988..99
Thomas Steinke and Lydia Zakynthinou. Reasoning About Generalization via Conditional Mutual Informa- tion. In Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 8437-3452. PMLR, 09-12 Jul 2020.
Lili Su and Pengkun Yang. On learning over-parameelerived neural networks: A functional approximation perspective. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alcéé-uu, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Taiji Suzuki. Adaptivity of deep reLU network for learning in besov and mixed smooth besov spaces: optimal rale and curse of dimensionality. In International Conference Learning Represenlations, 2019.
Joel A. Tropp. An introduttion to matrix concentration inequalities. Foundalions and Trends in Machine Learning, 8(1-2):1-23)) 2015. ISSN 1935-8237.
Alexandre B. Tsybakov. Introduction to nonparametric estimation. Springer series in statistics. Springer, New York; ; London, 2009. ISBN 9780387790510 9780387790527.
Zhuozhuo Tu, Fengxiang He, and Dacheng Tao. Understanding generalization in recurrent neural networks. In International Conference on Learning Representations, 2020.
Luca Venturi, Afonso S. Bandeira, and Joan Bruna. Spurious valleys in one-hidden-layer neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1 34, 2019. https://arxiv
org/
Roman Vershynin. High-dimensional probability: an introduction with applications in dala science. Num- ber 47 in Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, Cambridge: New York, NY, 2018. ISBN 9781108415194
Mingze Wang and Chao Ma. Generalization error bounds for deep neural networks trained by sgd, 2023. www.orsg///..ooooo.ooo.ooo.o.. abs/ /2066 03299
E. Weinan, Chao Ma, and Lei Wu. A priori estimates of the population risk for two-layer neural networks. Communications in Mathematical Sciences, 10751:1407-1425, 2019. ISSN 1945-0796.
E. Weinan, Ma Chao, Wu Lei, and Stephan Wojtowytsch. Towards mathematical understanding of neural based machine learning: What we know and what we don't. CSIAM Transactions on Applied Mathematics, ((4):561-615 2020. ISSN 2708-0579.
22

---

Published in Transactions on Machine Learning Research (02/2023)
E Weinan, Chao Ma, and Lei Wu. The Barron Space and the Flow-Induced Function Spaces for Neural Network Models. Constructive Approzimation, 55(1):369-40) February 2022. ISSN 0176-4276, 1432-0940.
G. Welper. Approximation and gradient descent training with neural networks, 2024a. org/ pog/abs/2405..c 11696
https://arxiv.
Gerrit. Welper. Approximation results for gradient flow trained neural networks. Journal of Machine Learn- ing, ((2):107-175) 2024b.
Yuhong Yang. Minimax nonparametric classification Ji. rates of convergence. IEEE Transactions on Infor- mation Theory, 45(7):2271 2284, 1999.
Dmitry Yarotsky, Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103 114, 2017. ISSN 0893-6080.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep ReLU networks. Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31sl Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 639 649. PMLR, 06 09 Jul 2018.
Dmitry Yarotsky and Anton Zhevnerchuk. The phase diagram of approximation rates for deep neural networks. In Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13005 13015. Curran Associates, Inc., 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Represenlations, 2017.
Chenchao Zhao and Jun S. Song. Exact Heat Kernel on Hypersphere and Its Applications in Kernel SVM. Frontiers in Applied Mathematics and Statistics, 4:1, January 2018. ISSN 2297-4687.
Ding-Xun Xuan Zhou. Universality of deep convolutional neural networks. Applied and Computational Harmonic Analysis, 48(2):787-7794 2020. ISSN 1063-5203.
Difan Zou and Quanquan Gu. An improved analysis of training over-parameterized deep neural networks. H. Wallach, H. Larochelle, A. Beygelzimer, d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes wer-parameterized deep ReLU networks. Machine Learning, 109(3):467 492, 2020.
23

---

Published in Transactions on Machine Learning Research (02/2023)
A Gradient Descent Convergence
A.1 Convergence Result
In this section, we prove an abstracted convergence result that is the foundation for Theorems 2.2 and 2.4 To this end, let c RR be a set of admissible weights, and H" 8 8 consider
&eR. R a set of Hilbert spaces. Then we
f::0- + - H.,
0 + fa.
(24)
1
f::H 71" +R
0 > (0)
11 fll..
(25)
f: 7. + R,
0 - (()),
(26)
where to corresponds to the continuous loss, or generalization error, and l to the discrete loss. The Hilbert || ||e = -l and are related by the interpolation incquality
spaces have norms
1 - 11--101
(27)
for for all a, b, R. Typically, we choose Sobolev spaces H (D), the neural network fo(.) e L2(D) = 7D, and some discrete loss e, but this is not important throughout this section. The statement of the following result relies on the empirical NTK and NTK
H Σ (0.100)0.111"
H= lim width-oo
where f" the -addojint of f. Note that the adjoint, contained the dual space (HO),, applied to a function is (v) v) and as result, corresponds the integral operator induced by the integral kernel in
The following convergence result is almost identical to Welper 2024a Theorem 3.1), up to new error term for the difference between the Hilbert space loss En and the discrete sample loss E in 33
Theorem A.1. Assume minimize the loss f of the parametrized function 0 fe E 7t in 24 with gradient descent g and Hilbert spaces (27). Define the residual n* =fgr ff Let m be an indicator for the network size that satisfies the inequalities below. With a > 0 from 31 below, assume that
1. H is coercive for S= and S and some B > 2s
|ul|3_ S Hv)
U S-B
(28)
2. For some norm ||-11,, the distance of the weights from their initial value is bownded by
|100 10 S 1, 1....,n
||@nt1 -00 =
(29)
k=
3. The learning rate 7y is sufficiently small so that
7 (Vol(t"))l & c.m + =:
(30)
for some constant Cp. that may depend on the initial error ||=="|0o-
4. For S = and 5 = 8, initial value 0", any 0,0 E O and anyy h O, the bounds ||0p-0 0l._ S h and
||000 Ø|l_ s h imply
|| Ha.llss, cha
| 00.. 5 Hg.olls.0 chaa
(31)
24

---

Published in Transactions on Machine Learning Research (02/2023)
5. For S 5=0 0 and S s, we have
H Hg 1ls.0 cAm 21 h.
(32)
There is a bound A sample (ma. N) and sufficiently large constant ca so that
R
sup 8 9 Seah
(..5 -,,40)))) s campie (m, N) 1o 11.
(33)
r=1
6 9
Seah
for all gradient descent iterates x² with lo S n.
Them, while the gradient descent error exceeds the final approzimation and estimation error
||** 11 2 m 1 - + saample (m. NY) $ ||x=
k S n.
(34)
we have
1 S Ce -1- -Armpht
|| S x
for sufficiently large constants Ca, e and C independent of m, kD and k²#1
The theorem has long list of assumptions, which verify for the proof of the main theorems in Sections B and C below. The coercivity (28) is the only major assumption that remains in the main theorems. The second assumption
(29) is used to show that the weights do not move far from their initial and the third
(30p provides bounds for the learning rate. The next two assumptions (31 and (32) are major components of NTK analysis and require that the NTK is Hölder continuous and that the empirical NTK concentrates close to the infinite width limit. Finally, assumption (33) bounds the difference between the gradient of the continuous L2 loss and the discrete loss L. The last assumption is the major concern of this paper, while all others have been established in Welper 2024b ab.
The proof is identical to Welper 2024a Thcorem 3.1), with one difference: The error reduction lemma Welper 2024a Lemma 3.2) is replaced with Lemma A.2 below. This introduces a new error term form the sample loss. While this extra error term only requires minimal changes in the proof, for the convenience of the reader, we include it Section
A.2 Gradient Descent Error Reduction
The first step in our convergence proof establishes an error decay every gradient descent step. matches Welper (2024a) Lemma 3.2) up to an additional error term [sampte(m, for the difference between the continuous and discrete losses.
Lemma A.2. Assume that. 30
31
and 33 hold. Assume that 1100 0nll. S h. Then
(s(0r+1)- (s (s(o - (x, Hk) + cyh | AAsmpte (m, ||]]|o||]]]]
Proof. Applying the mean value theorem the gradient descent step gn+l - nt with A" == Vol((0))
obtain
(0( - -ss(0") = ( - A ) (0))
= --- - AA")A"
for some & E (0, 1). Abbreviating = xr' and plugging in the derivatives (²( 1K, sl and n = >==7(0,((0)] (0,0(0)) yields
-(sh))))s(()))) = - Σ (n, ( )
25

---

Published in Transactions on Machine Learning Research (02/2023)
Next, replace the derivative 0,0 of the discrete loss by the corresponding derivative of the continuous loss (0) = 0.
es(Ant1) - -l( - E -a) (0,60((0))))))) (0,e((0)) (.6((
Σ -ma fro
E -(0))))
0.
Let us first estimate (7). To this end, express (u, k) by the H dual e*k (v, n) and obtain
(1) = 7 E (ks,
0r ((o))
= =-> (m. ki
-00.fo--ea-))0000m k
=-y (Ni ssm
Adding and subtracting terms to compare Jon-Ean can and for with the initial fao, we obtain
(1) -y (m, Hgg Ho0
+ (ri, Ho0 000 Hgg ook))
7 (ni Hg H -ga- ont
Assumption 32
implies
(n,, (60.garc) = = (Ic, HK)) + (n. H Hoo,ook) S - (n, Hx) + |||||||l||<]
and Assumption 31
with h = h and h = h || implics
Hg -o- Hoo lls.o S cha
Ho o0 Hpm en Ils.o c(h ((h++11a)1))
Combining these incqualitics, yields
(1) - 3erh ||]]]
|*]|o||[|ss
(K, HK) + c | <
where in the last step we have used that | I1. = > (o Il. & h by assumption (30
It remains to bound (IT). Again, using |ll S h and the assumptions of this lemma, we have |100 - (0" +
{A")]l $ h for all & E [o, 1). Thus, with Assumption (33) and our abbreviation x = xe", we obtain
(11) = - Σ Or (0,e(0-) - )
S 7eeampi N N ||]l0||///1
Combining (T) and (TT) yields the lemma.
A.3 Proof of Theorem A.1
The following proof is identical Welper (2024a] Theorem 3.1) up to the additional error term A Asample(m N). We include the proof to trace the minor modification and keep the paper self contained.
26

---

Published in Transactions on Machine Learning Research (02/2023)
Proof of Theorem A.1 The proof is based on the gradient descent error reduction in Lemma A.2 All of its assumptions are given, except the weight distance We assume
0n 0011. which we include in the induction hypothesis:
|| S e->>i -->(**+||++ ||=
h² max Isk
110| 0 Il. 2 c.m í =: h
for all S n and A A sample (m, N) and prove the case n + by induction. With the induction
hypothesis and assumptions (30 (31]
32) and (33 Lemma
A.2 together with coercivity
implies
1
||^"|8 S ->||>~|| ey | 1
||
- e
1>>0 || I1 < II. + > |e || 1la9
or shorter
|10 11 - ||=0 S - + A]][]* I|I
||**+111 11: - 1< < ->||<~ + Mch + |o]""""""||>*"" Ia.-
This not a closed iteration of the ||^**| and ||<| residuals because of the || || and || I|s- norms. We eliminate them with the interpolation inequalities 27
-||1|2 S <-1|ello 28
28
||s||oo S ||<||| ||c|||
||:||a
||e||o < [ni1==,l/
-||+|| S -1xxllo ||~|||-
20
20
that
|| - 11 x -7|| 112+
2+ 29
||x*
29
+ 71 A|||""1| 12:
||*++111 112 - || 2 >>||<> Ila" [|x" + 1100 + A |s || | ||...
Error bounds for this iteration are given in Lemma D.5 with n + 1 == || 11: w- = ||<| P 3/s.
==== and b d = ha A. To show the lemma's assumption 50 we use 2s E B that
23
1 S 2
2 (
2
8
P
2p
1
Hence, assumption 34 implies
2 1 2 (mm mm (nn2adaa +2) 3 |n0 (h* +2)² 1|:911 >
b
d
2
vo
a
and Lemma D.5 is applicable. Therefore, we obtain
|| 11 $ e 1 ||6 9
| 11 ||
which shows the first induction hypothesis.
It remains bound ha+1 show the socond induction hypothesis. To this end note that
hn+1 max ksn+1
||00 80 S
| 1lo x
1hh +Ak]+=) los
where in the second step have used assumption bound the latter sum
29 and in the third step the induction hypothesis. We
- th +
<
- dk 7(ha + Al
27

---

Published in Transactions on Machine Learning Research (02/2023)
to conclude that
1 hut1 c vm y/h A
1114 I c
vm nha 1115"1o
S
c
h 1 1lo = h.
vm
In the last step we have used that the definition of h implies
h = c.m -aria
Ch m
m 1 - 11 -
Vm
V'
vm
for constant ch e/|x:llo dependent on ||x" Together with the first induction hypothesis this concludes the proof.
B Sampling
In this section, we prove bounds for the error A samplee(, N) between continuous and sample loss (Lemma
B.4 and then Theorem 2.2 Throughout the section, we use the following regularity conditions on the
activation function
la (x)
2A 25
(35)
la (x)
(36)
b
(r)
S
1.
(37)
Moreover, for the time being, we assume that the weight matrices are bounded
|We|| n 1/2 z
W m 1/2 21,
||||| S 1a E D.
(38)
Typically We will be the initial weight and W the weight of later gradient descent step. Likewise, we denote by 0, fa and fe, etc. the weights, networks and layers based on the perturbed W For the main theorems, these bounds follow from properties of random matrices at the initial weights and the observation that weights do not move far from their initial in 29
Throughout the section, we abbreviate = gd-1, La L2(D), H = HD) and (.) = ()) when convenient.
B.1 Concentration
In this section, for the sample loss {(0) = 1 E [f((x;) - f(x:)?, we bound the sample error
IN
Σ kk 0,fe) nS (0,0(0) 0,(o(0))
sup 0.8
This establishes assumption main result. Let us abbreviate
33 in the abstract convergence Theorem A. and leads to the proof of the first
R Yo = Σ (n, O, us (0,0(0) - 0,4,
which is a random variable with respect to the sample points x; implicitly contained in the discrete loss E(O). Since the &o loss is the expectation of the sample loss é, it easy to see that EE [Yo] = and sulfices to show concentration results. These follow from Dudley's inequality, for which we proof that has sub-gaussian increments, i.c.
|| Yollos S 0 0...
28

---

Published in Transactions on Machine Learning Research (02/2023)
Throughout the section, use Orliez and weight norms
|| w/2 = inf { > 0: E Texp [x]]] 2
|0|_ == - | m
1/22
where we have used that 0 W because we only train the second but last layer. || denotes the Euclidean norm for vectors and the induced matrix norm for matrices. As in the introduction, we abbreviate D Dd=
Before we prove sub-gaussian increments, we bound several components involved in Yo separately. We start with the factor (M, G, 30) n1-
Lemma B.1. Let 0 S < 1 and assume a salisfies
35
36
the weights salisfy
38 and are of equivalent
size mg mL-1- Then
Σ
(n, 0,fo) H S |
Proof. By Lemma D.2 cited from
Welper
2024b), with sufficiently small so that + e < the bilinear
form
B(u, = S u(x)
R
Σ
0,So(z)0, v(y) dxdy
=
(u, fx (0, u)
for and in L2 is bounded by
Bu,, v) S || H -|llll
and can therefore be extended to all u, v E H- In this case the L2 inner product (:.) turns into the -- x Ha dual pairing. Denoting by R: H H- the Riesz map, we obtain
B
(x, Orfo)
Σ
(n, 0, (0rfe. k)
R
(Re, f. (0, Rk) B(Rr, Rx) S Rx -|<e]
which proves the lemma
Next, we consider the loss 0,((0) = 1 ((x,),00,0(())) and show sub-gaussian increments for the sum- mands. As usual, we abbreviate (D) To
Lemma B.2. Let < <1 and assume || S m2 a satisfies 35
37
and the weights satisfy
38
Let X be uniform random variable with values in and set
Xo = xx) -E
f(x(X)V(((X))
Then
||||8 Xollly,, S 1/2 110 1l|..
||| do S 1/2
Note that x(X) is scalar and VSo(X) Vwi-1fo(X) a matrix. With the convention Owy-1 O, for suitable r, we may also regard fX) as vector and thus [[x(X)Vf(X)]] as the Euclidean vector norm, which we do in the following.
29

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. We split X9 Zg [Zo] into random part and an expectation, with
Zo == V.X)V.
and estimate both terms separately.
Estimate ||||5 Zzy Zu First, we upper bound the æ---norm by the and separate the factor 6:
Zoll Ilo S 1111z0
20 Vlll VV
R
= sup
[x(x) (0,fo(x) 0xfo())]]
(39)
xED
S || L... fe folllii
The first factor is bounded by
||= S = + 11 S m/
where we have used that - f- fa for some weights 0 that satisfy 38 that [lll S mm-1/ assumption and llfelle... 2 m m/2 by Lemma D.3 cited from Welper 2024b)
1/2 by
To bound the second factor, recall that the derivatives O for r E {I...., R} are shorthand for the derivatives Ow of the sccond but last layer. A short caleulation shows that
w So - 1/2 1111m,,,1 1/2 (J a (1/-)) W 1
(40)
(0)
=10
see e.g. Welper (2024b] Proof of Lemma 6.18) for details. The weights WL of the last layer have only one index because the network is scalar valued. The layer f does not depend on W4-1 and therefore vj does not depend on WL-1, Then, for all x E D, have
-
Σ (0),,()), ww,, (0)o;)
Σ 4
wf (u:(0) u.(0))² 03
Σ # (u:(0) (.))) ΣΦ²
< || |2((0) 110)11
Since Wh = #1, we have
| S m
and from Lemma D.3 cited from Welper
2024b
together with the Lipschitz continuity of a and ò,
we have
[|u(0) u(0)ll S m 110 +1.
||l||| S m/2
Thus, we obtain
V - [z())
S 110 -11.
for all x. E D and therefore together with 139 that
||||
Zo |l| v.
S m
1/2 1|0
0 +l...
30

---

Published in Transactions on Machine Learning Research (02/2023)
2. Estimate | Zg] E [Z,]
||: First, using that X is uniform, we factor out the residual
/ k(x) (o.f((t) O. -+.(((()) dx
E Za] E 12
/ [. 0.fo(a)1 de r=1
D
| 11 a, L.00
where in the first inequality we have used Cauchy-Schward Schwarz and in the last one exchanged the order of sum and integral. The right hand side is identical to (39) and bounded the same way.
Combining the estimates for Zo and its expectation and using that the 4ormn of a non-negative constant is upper bounded by the constant itself, we obtain
|| Xolll 02 S Ze - Zollll 2t. + | [Z] - E [Z)] IIII
5 m 110 0l1.
which shows the first part of the lemma.
The proof of the second bound |||Xell]lss S 5m/ 1/2 is identical upon replacing X, and Zo with 0 throughout
the proof. Using a(x) S 1, we obtain []m(O)]] S m/22 instead of |l((0) - u(0)ll X m 110 - 01. by Lemma D.3 Omitting the factor ||0 oll. in the left hand side throughout the rest of the proof shows the second part of the lemma.
The next lemma establishes the sub-gaussian increments of the random variable Yo.
Lemma B.3. Let <<1 and assume I| S mm//2, satisfies (35 Let X be uniform random variable D and for 0, 0 E E set
36
(37
and the weights satisfy
38
Yg
Σ
(n.0.fo) (0,((0) 0,(o
Then
1/2 N
1/2
1 Yollo 1/
||*]| 100 -ll
Yoll < N ||
Proof. Plugging in the definitions of the loss l and its continuum limit lo, we have
0,e(0) N
(,0o( O,fo) [kd,
and therefore
N Yo
1 N
(R, J.Ja) H ((xx))0,6(zz)) - - -xx(()),00)X
X
N 211
=M,
With Hoelfding's inequality, we estimate the -oom by
Yo Yolle
Σ T(X
Xb))
|| a (xx - x55)1
N
N2
1=1
31

---

Published in Transactions on Machine Learning Research (02/2023)
The argument of the #2-norm is bounded by [X; - x;)1 = |ull|
Xiil and thus
N
1
1|
Yoll
| |u|
x
2/2
N
24
|| 110 21?
N2
1m
m
|<|
2
11--01.. 21?
N
H8
where the last inequalities follows from
| x ||||
|||I -xix-xxlll,, S 2m 10-01...
by Lemmas B. and
B 2 respectively. Taking the square root completes the proof of the first inequality.
The second follows analogously by replacing Yo and Xo with zero throughout the proof.
Lemma B.4. Let < and assume ||[|| S m2/2 satisfies (35
and the weights satisfy weight @ that satisfies (38
37
38p. Let O₁ 10 θ 0 |l - h} for h S and some initial (trained) Then with probability least 2 exp( (mm???)
n Σ
m3/2
sup P
(n, Hs (0,2(0) - 0,6o(0))
N1/2 k|]
Proof. We abbreviate
Yo Σ (ss S,So) Hs (0,e(0)
-,((())) 0,()(0))
and prove the lemma with Dudley's inequality. We have established in Lemma B.3 that Yg has sub- -abb-aassiin increments
||oo Yollas $ (M))
1/2 [s]| 110 -ll..
Next, we estimate the covering numbers in Dudley's inequality. The set of eligible parameters O₁ is contained in the ball of radius h in R in the [l-Il.-norm. Hence, for every e 2 0 there is an e-covering of at most
N(+) <
(3)
3h
c-balls, c.g.
Lorentz et al. 1996. Chapter 15, Proposition 1.3). Then, using log S x xx,
Vlog ((e) de = R2/2 /"' log
3h de S R 1"' V (2 de = 1
12213)
S mh,
where in the last step have used that R2/2 Hence, Dudley's inequality (with tail bounds) implies that for all u 2 0
1/2 sup Noo - Yol S 0
|||||| Hs [/ Vlog (N)) de + uh
holds with probability at least 1 - 2cxp(-ui x2) Choosing yields
1/2
sup e,0
YY Yol S m
32

---

Published in Transactions on Machine Learning Research (02/2023)
with probability at least 2exp(-m²). The sub-gaussian bound ||Voll22 2 (x)
1/2 | from Lemma
B.3
implies
(x) N ms
1/2
with probability least 2exp(-m211) Then, the lemma follows from supsee, (oo S supaee, \oo Yoo Yoo).
B.2 Convergence: Proof of Theorem 2.2
Proof of Theorem 2.2 The theorem follows from Theorem A.1 with Ht Ha and 7 L2, for which we have verify all assumptions. Most of them have been established in the proof of Welper (2024a) Theorem 2.2), which is identical to the one of this paper, except that it uses continuous L2 loss instead of sample loss. This results in the extra assumption (33 which is the only one left to verify.
By Lemma B.4 with probability at least 1- --xxp((mmm1²) we have
3/2
sup BE
(K* 0,Sa) -0,e(0)-0,6a)) 0,(6(0)]
S
N1/2 h ||=,,
which provides an estimate for A ssampte (m, N) up to a missing factor || |r2 To insert this factor, we use the lower bound from Assumption (34 For k S n
| ca (h + A sample (m, N)) || 11 2 cal 11x"
which implies
1 h 10 H² 11e..
Inserting this into the application of Lemma B.4 above, we obtain
R (n. arfa) H (0,0(0) - (,))(
3/2
sup PE
x
N1/2
h²
2
|
--1
H²
||
|1azl1 1| 1 11s..
Comparing to the definition of A sample (m, N) in assumption
33
we obtain
m/2
sample (m, N) -
h
9 n: I
N1/2
which shows the assumption.
It remains to consider the success probability. From the parts of the proof shown in Welper 2024a the bounds fail with probability cL(e m + - and from above with probability e-mmth 2 cm
because
h == c.m= - 2 112 for any a > 0 from 30
This completes the proof, together with an index shift + 1 + n between the statements of Theorems A.I and 2.2
C Kernels
this section, we prove Theorem 2.4 based on bounds for the error (m, between the L2(D) loss and the kernel loss
N (k(2,, ). f)²
(a))) = 2N
33

---

Published in Transactions on Machine Learning Research (02/2023)
for kernels ((zz,) y) with z, E D = S and x; uniformly and independently sampled on the domain D. We denote the corresponding expected loss by
2|D] J, (k(x,-), f3² dx.
(0) = =0==
We consider this expectation in Section C.1 which is generally not identical to f (D) Then, we show corresponding concentration inequalties based on matrix Bernstein inequalities in Section proof of Theorem 2.4 is in Section C.3
The
Throughout this section, we abbreviate D gd-1, L2 L2(D), H (D) and (:) (, (.)) when convenient.
C.1 Expectation
Define the inner product and norm that give rise to the expected kernel loss
N
(u, 2)
(u, k(a,, }) (k((2), u,
- = (, hh (0) :- -
2 llfo - fll..
(41)
N
Unfortunately, the norm ||- || is not equivalent to the Le norm and therefore the expected loss e (0) is not equivalent to the L2 loss (o). To bridge this gap, this section, we construct a modified inner product and corresponding norm and loss
(u, 0)2
| 1111 (,))
[00 = 51.6 11. - 11
(42)
with the following properties:
The two inner products (e and (, are close for smooth functions.
2. The norm || | and loss (0) are equivalent to || ll and lo(O), respectively.
To this end, we first characterize the inner product (s)) Lemma C.1. Assume the symmetric kernel l: D + has Lg-orthogonal eigenfunctions ey with eigenvalues d;- Then for any u, v E T.2
N (u, k(,,x)()) (M(2)) 0,
(u,v)
E
Σ X3 (u, 2hd u)
Proof. We denote the expectation by E. By the law of large numbers, we have
N
(u, (u,k((,)))) (K(2)) (1 u) = -bbb - (u, (0.k(,,))) x)) (k(z, ). )).)) v) dr.
1
E
N
Plugging in u, in eigenbasis
(u, (aa 1b.
(u, v1) sr.
we oblain
{u, 1/a) (N, (h)) / (Whe k(,,x))) (K(xr. -), sha) dx
E =
s,t=1
[D / (a())))()) dr x (u, (ia)) ())..))
(u, 1/aa (u, wbx) Aade 1
8
34

---

Published in Transactions on Machine Learning Research (02/2023)
where in the second step have used eigenvalue and vector definition k(,))) (z) and in the last step we have used that v, is orthonormal basis, with normalized squared expectation.
In the next lemma, we define the modified inner product (,:) and prove the properties from the introduction of this section.
Lemma C.2. Assume the symmetric kernet k: D D - IR has L2 Lo-orthogonal eigenfunctions by and eigen- values Xg with
1 1イ 1, JsJ,
AS 11 j>J.
Define a lower bounded perturbalion X3 of the eigenvalue X3 and the corresponding inner product
A3
j s J j2 J.
(u, 1) = Σ X3 (/x (1br.)).
max 13
For some increasing weights μ 2 lel
|ull
Σ 16 u}
the norm of Hilbert space Ht Then for all u, v E L2 and s 20
(u, 0)2 - (u, 12//
Σ [23 X3 (u, why) (1) u)
S μj Iellleal
and the induced norm || |13 = :) is equivalent to the L2 norm.
The weights My and H. define smoothness space, which left generic for now but will be replaced by Sobolev spaces below.
Proof. We have
20
Σ j=1
[>
X3] (u, 1b, (155,)) v)
Σ [>] X31 (u, )by (W)) 1)
i>f
1/2
1/2
Σ
A33
X31 (ue, 2by)
Σ
|2
x31
(b)
1>J
JDJ
1/2
1/2
Σ (u, 23)
Σ
b1)
315"|uull ||u|lez |1011
where the first equality follows from \3 A, for J, the second from Cauchy-Schward and the third from
0 < X3 - X3 < by definition of X; for > J. The last incquality follows from
Σ j>J
(u, b3)² s [|ul12
and
Σ (u,b,)==1p)) J>J
20 pj
Σ
2
(u, 13))
2MI 20 Σ 1 (1, = 2T |ul f...
j>f
1>J
Finally, by construction, the cigenvalues Xy ~ 1 are upper and lower bounded by one and therefore the norm || lla is equivalent. to the Ta norm.
35

---

Published in Transactions on Machine Learning Research (02/2023)
C.2
Concentration
We show concentration for
Σ
(r 0,Jo) H² (0) - 0,
except for the wrong expected loss (0) instead of lu(0), which will be considered in the next sect.ion. Throughout this section, denote the adjoint of u, by u², that (f, u) v, For weights 0, 0 E θ use the abbreviation
which matches Assumption 133
Fa 0,0 = Σ fo (arSa,
(43)
which shows up repeatedly in the following proofs. We first bound its norm.
Lemma C.3. Assume that salisfies the growth and Lipschitz conditions 35
36 and may be different
in each layer. Assume all weights in the networks, 0, and the domain are bounded 138 5 <sss<1
Then for
1F S ||||||
Proof. Let (5 be the H-S x H dual pairing and R: HS - H-9 the corresponding Riesz map. Since the H--norm is the dual of H-8, we have
R So (0r n) H8
11
sup 1/0 Iy N-
V, o (0. 16) us
sup - S1
v. Σ O a.fedrfē
Rx
where in the last step we have used the definition of the adjoint functional fJ E H-S so that (Jō- 6)) HS (fa. Rıc) = fī RR).. Formally, in this argument (:.)) is the H H dual pairing, which reduces the L2 inner product in case Rs is in L2, see the proof of Lemma B.T for more details. By Lemma D.2 cited from
Welper (2024b), with sufficiently small so that + < 1, we obtain
S sup
||]|a---|RRe| < ||Rs|H-> S [|K]] H-s = ||m]| S ||i|| ||
where we have used the embeddings
|| 1| I -1== and ||. l| S 111 because $ $ s.
The next lemma shows the main concentration result.
Lemma C.4. Assume that a salisfies the growth and Lipschitz conditions 35
136
and may be different
in each layer. Assume all weights in the networks, 0, and the domain are bounded (38) Assume the kernel
is bounded by supzen llk( M2,, I C₁. Then for 0 s < with probability at least 1 2t (e' - 1- we have
(K, fa) (0) S SC² (V+ # Ielleallael
for all H
Proof. The lemma states that the gradient of the sample loss is close its average, with high probability, which show by the matrix Bernstein inequality. To this end, first unravel the definition of the loss to
36

---

Published in Transactions on Machine Learning Research (02/2023)
define appropriate random matrices:
tc, Drfe) H- a (0)
Σ
(k(zs, -) k)) (k(2), 0o) (R. drfo)
N
(k,, k( )) (1e(2 -), arfo) (1c, 0r m
N
k(r >)((,,))) )* Σ fo (n. 8 8, n-
N
M
0
with Ps g defined in
43 and the integral kernel
1 N
M = Σ k(z,, )k(c,
N
With an analogons computation, we obtain the expectation with respect to the samples 2;
(k, Orfo) 0 0,00 = (R,,
E
with
N
k( )1((3ss))) -3 / k(x,, k(x,,)) )k((()))))) dx.
M = E
It follows that
(k, O. (0) (0)
(N,IM- MFF (1)x I ||5||,,1| - 1111 (44)
The last term
F k S ||<|||
(45)
is bounded by Lemma C.3 so that it remains to bound || M| To this end note that M is sum of rank one operators, each depending on one independent sample dy. Hence, concentration follows from dimension free matrix Bernstein inequalities (Hsu et al.) 2012 Tropp 2015 Minsker 2017). We use a
corollary shown in Gentile & Welper (2022) and stated in the supplementary material Lemma D.4 for which
we only need to bound
[|<(,,)) 11 = ||k[,, -I--- & ||( )ll C².
for all I E D, provided by the assumptions of the lemma.. With Lemma D.4 this provides
M M1l--1 2 (V++ #4 N )
Pr ||
< 2t (e' - t -t 1)
Together with 44 and 45 this proves the lemma.
C.3 Convergence: Proof of Theorem 2.4
We first bound A Asampte (m, N) based the results in the last two sections.
37

---

Published in Transactions on Machine Learning Research (02/2023)
Lemma C.5. Assume that satisfies the growth and Lipschitz conditions in each layer. Assume all weights in the networks, 0, 0 and the domain are bounded k: D R is zonal, i.e. k(z,8) y) = k(x²))) y), and has eigenvalues Xιj with
35
36
and may be different
138
Assume the kernel
15 No L ISL isis(())
A - 1, 1> 15j5 vl))
and inder structure and v(l) matching spherical harmonics
6 and
sup [ik[0, 121z S Ck- xED
Then for 0 SSS S < 1 with probabilily al least 1 21 [e. - 1| for all E Hd we have
Σ nr So) H8
-, -0) ch
V N
+
1 N
I. -.-5[1ss]] Lo [
with loss (0) defined in 42
Note that the conclusion of the lemma contains both S and s. This allows S = but also the choice S = 0 for which the last summand the right hand side does not provide meaningful bound we insist that ==s=0. O.
Proof. We first split the difference into expectation and concentration components:
π
Σ
(k, Orfe) ns - [+]
R
R
Σ
(R, 0. ns (0) - -0), (0)
Σ
(n, So 12 [0) - (,
(7) + (TT).
The first part (I) is bounded by Lemma C.4
(T) 5²
V N
+ x || ||:||all16l10
with probability at least 1 - 2t (e' - - 1)
To estimate the expectation part (IT), first note that the Funk-Hecke formula Attinssn & Han 2012) implies that the eigenfunctions of the zonal kernel k(.,)) are spherical harmonics Y and thus Le ort orthogonal. Hence, we obtain the loss
(0) =
- llf
fl1
Xi
5o
{
A max 1)
i J j 2 J.
l.j
by Lemma
2.2
The partial derivatives of the modified and expected kernel loss are given by
a,7((0) = Σ X6 ks x2) (x
1.j
and
(0 E
- 2B ( (x. (<xr7) (ve. (n, k( )) (k(2,, )), 0,
N
38

---

Published in Transactions on Machine Learning Research (02/2023)
by Lemma C
respectively. It follows that
(11) Σ
Ks Dr Sa
Σ |Ng
-ig (s, vr.0
1.
Σ
[Nt X5]
K X2)
YP, 0r Σ
(ni, Do
15
Σ
[N X3l (M.Y²) (vi, F. Po.xx).
with f. defined in
43 Bounding the latter with Lemma C.3 and using Lemma C.2
we conclude that
(11) S 1 M | H- S Mr Iklllz I
where μr the weights in the definition of the Sobolev space H via spherical harmonics 5 P4 ~ I. Together with the bounds for (T) this completes the proof.
and therefore
Proof of Theorem 2.4 The theorem follows from Theorem A.1 It shows gradient descent convergence in arbitrary scales of Hilbert spaces, for which the natural choice is 71* = H² However, we replace the L2 H norm with the equivalent || || norm to utilize our concentration result in Lemma C.5 This choice does not alter any assumptions or conclusions, except coercivity which uses the 7 inner product instead of the corresponding norm. We show that coercivity of the L2 inner product implies coercivity of the ||: inner
product as well as the sample assumption (33). All other assumptions are proven in Welper 2.2) for an analogous result without sample error.
2024b Theorem
Coercivity 28): : Since the neural tangent kernel is zonal, by the Funk-Hecke formula (Atkinson & Han 2012 it has spherical harmonics as eigenfunctions with some eigenvalues Mij, so that we have
(u, Hu), = Σ
Xinno ~ Σ mo = (v, Hu),
1.j
1
with my = -(,, (1,Yt)) and the ||- norm from Lg-coercivity.
42
Hence, || |1lll- is equivalent to the regular
2. Assumption
We show that with high probability for all A, 0 with ||l||. distance to the initial 80 smaller than S and S E {0,s) we have the bound
33
R
Σ
(k, 0.f (0) (x)) s [[ll
(46)
with
TN A Ssample NM, N) of
1/2
N
1/2
+
C
- + L-
(47)
N
TN
which provides Assumption
To this end, by Lemma 2nN TE -NN 1] for all H we have
13
C.5
with t == and probability at least
Σ (r, Or (0) [(0] $ C¹
R
TN
1/2
[ + -=""||l|aa (48)
N
39

---

Published in Transactions on Machine Learning Research (02/2023)
This yields the claimed bounds [66]
47
for S s. For S 0 the last summand has the wrong To replace the Ha norm with an
norm: [ ||]|||rr instead of Le norm note that assumption
|| I. 1=
34 yields
| 2 ca
mm +ím + sample (m, N))
|| 2
C
TN 1/2
||
N
for A S n. Moreover, by induction, from Theorem arrive at
A.1
we have ||,. 1| x ||x0 and therefore
N
1/2
|| S C
||
TN
Together with (8) this yields the claimed bounds the case S = s above, this establishes assumption
16 33
and (47
for the case S = 0. Together with
This completes the proof, together with an index shift 1 n between the statements of Theorems A.1 and 2.2
D Supplementary Material
D.1 Technical Lemmas
Lemma D.1. Let ke(x, y) be the heat kernel defined
21
Then for all y E Sd-1
443/2
Proof. Plugging the definition of the heat kernel 21 into the definition of Sobolev norms we obtain
2a v(l)
(12 d 22212) 2s
1- 22 (w)
1
1=0 j=1
$ 1 +
00
22 e
2
v(1)
Yp (v))
2
t=0
j=1
Since 12/())2 $ v(I) and v(1) S pd-2 see
Stein Weiss 1972
Chapter 4.2, Corollary 2.9), we obtain
(1(( 1) 1 + Σ 22 e
21
+ / 22+2d 2e 2/ dl
-1+t +1+
20+2d - 20 dx S 6----33312
were we have substituted x Ivt and used that the latter integral is bounded.
D.2 Results from Gentile & Welper (0022): ; Welper (2024b
To keep the paper self contained, this section contains several results from Gentile & Welper a202
2022 Welper
Lemma D.2. Assume that and ā satisfy the growth and Lipschitz conditions
35
36
and may be
different in each layer. Assume the weights, perturbed weights and domain are bounded mL-1 N... my. Then for O < 8 <<<1 and mo = mm
38 and m
n
1h f(x) Σ 0,fo(z)0, g(v) dx dy S -00-
40

---

Published in Transactions on Machine Learning Research (02/2023)
Proof. This is direct consequence of Welper (0224b Lemma 7.16) and Welper 2024b sulficiently small so that 8 < 1, the former shows that
Lemma 6.7). For
JDNDD (())k(, dr dy s - ( 1ol-----yyyllllooottttttt (1
for k(z,)) v) Σt- f. and where || 1o. 1) Hölder norm of order + in the variables and y. Technically, the reference does not include the case 8 0, which follows directly from sup-norm bound and the fact that the domain is bounded. The second reference Welper 2024b Lemma 6.7) shows that
I 1
where k(z,y) = (.f((2)0.fo()) is denoted by P. Combining the two incqualitics yields the result.
Lemma D.3 (Welper
2024b
Lemma 6.2)). Assune that ||>||| S
1. Assume that satisfies the growth condition 35 and may be different in each layer. Assume the weighls are bounded (38 Then
2-1
|| E mg
1/2
W
1/2
mg
Assume that a satisfies the growth and Lipschitz conditions each layer. Assume the weights and perturbed weights are bounded
335 and 36 and may be different in
Then
(1)( (x)) E mo
1/2
W
1/2 m WK
max {
w |
| m 1/2
jzt
Corollary 6.4)). Let Ei, i i= L...., be independent random variables, U, V Hilbert spaces and X; X((E:) = u:(E)))((Ei) = v.uf be Bochner integrable rank one operators with 0s and uf E U*. Assume there are μ and such that for all I,...,
Lemma D.4 (Gentile & Welper 2202
||u"|uu- $ p.
||1/| S
almost surely. Then, for any t > 0,
Pr Σ X; [X,]]]
>
/
2pv1
< 21 -ct--1))
n
3n
Proof. The only difference to the reference is that we assume ||u" llu- S instead of ||ullo s which is equivalent due to the Riesz representation theorem.
Lemma D.5 (Welper that satisfy
2024a Lemma 3.3)). Let a.b,c,,d d 0 and 1/2. Let un and un be two sequences
Un+1 Un S -yau + P aduns
(49)
Unt1 Un S -youh 1-P 7 /un
Furthermore, assume that
2p
2 b 0
uk >
Up.
uk
v0.
for all ls O,..., 1.
(50)
Then
Un e-bb uns
Un. S vg.
41

---

Published in Transactions on Machine Learning Research (02/2023)
0.001
0.000794
0.000685
0.000538
0.000469
Loss
0. 9.000392
0.000321
0.000275
0.00022
32
0.00 0.000193
32
0000511
0.000136
50
48
Witth
50
Width
1000
56
1000
Samples
150
250
Samples
150
200
250
64
(a) MSE Loss, dim=3, depth=2.
(b) Kernel Loss, dim=3, depth=2.
Figure 2: Test loss for training with mean squared loss 13 (left) and so that the slope corresponds convergence rates.
(right). All axes are log-scaled
E
Extra Numerical Experiments
This appendix contains some extra numerical results for the setup in Section g
Section 3 does not report any losses. They are contained in the exlended Table 2
This section also contains experiments for shallow networks in three dimensions, shown in Figure 2
and Table 2
Figure contains results for the shallow network with MSE loss in 7 dimensions and with larger range for samples and width.
The observations from Section 3 remain unchanged. The deep networks performs slightly better than the shallow ones, but have significantly more weights in total.
42

---

Published in Transactions on Machine Learning Research (02/2023)
0.0117
0.00645
0.00356
Loss
0.00196
0.00108
32
0.000597
64
50
Width
128
250
Samples
500
256
750
Figure 3: Test loss for training with mean squared loss 13 for dimension and depth 2. All axes are log-scaled so that the slope corresponds to convergence rates.
43

---

Published in Transactions on Machine Learning Research (02/2023)
250
0.524
0.917
0.222
0.0546
250
0 0.896
1.25
0.684
0.985
250
0.388
0.662
0.536
0.232
250
0.482
0.987
0.539
0.713
200
0.169
0.805
0.367
0. 0.893
200
0.743
0.933
1.08
0.582
200
0.246
0. 0.672
0.565
0.664
200
0.797
0.744
0.734
1.25
N rate
N rate
N rate
N rate
150
1.34
0.631
0.943
0.601
150
1.36
1.13
1.07
2.08
150
0.871
0.469
0.756
0.732
150
0.939
1.07
1.1
1.21
Trained with Kernel Loss
Trained with Kernel Loss
Dimension 3 and Depth 2 - Trained with MSE Loss
Dimension 3 and Depth Trained with MSE Loss
100
0.832
1.08
1.6
1.22
100
1.9
1.86
2.2
1.56
100
1.26
1.2
1.16
1.49
100
1.65
1.23
2.02
1.71
250
0.955
1.36
0.0938
0.58
250
1.19
1.06
0.434
1.47
250
0.677
0. 0.898
0.474
0.756
250
1.07
1.05
1.11
1.19
dof rate
200
0.659
0.883
1.1
0.859
dof rate
200
1.33
0.628
1.25
0.967
dof rate
200
1.47
0.563
0.658
1.26
dof rate
200
0.748
0.433
1.75
0.898
150
1.3
-0.119
1.92
-0.273
150
1.33
0.328
0.969
2.05
150
1.43
-0.11
0.858
1.05
150
0.676
0.517
1.77
-0.218
Dimension 3 and Depth 2
Dimension 3 aud Depth 5
100
0.719
1.45
1.1
0.768
100
0.331
0 0.833
1.13
-1.03
100
1. 1.29
0.784
0.103
1.12
100
1.08
0.229
1.69
00.54
0.000212
0.000165
0.000163
0.000151
0.000102
8. 3.44e-05
7.89e-05
6.49e-05
0.00019
0.000162
0.00015
0.000136
9.29e-05
7.67e-05
6.47e-05
5.52e-05
250
250
250
250
0.000238
0.000203
0.000171
0.000153
0.000125
0.000111
9.19e-05
8.08e-05
0.000208
0. 0.000187
0. 0.000169
0.000143
0.000103
9. 9.56e-05
7.29e-05
6.47e-05
200
200
200
200
Test Loss
Test Loss
Test Loss
Test Loss
0.00025
0.000256
0.00019
0.000197
0.000155
0.000146
0.000126
9.55e-05
0.000223
0.000227
0.000199
0.000173
0.00013
0.000118
9.01e-05
9.27e-05
150
150
150
150
0.00043
0.00033
0.000279
0.000252
0.000268
0.00023
0.000194
0.000222
0.000317
0.000275
0.000271
0.000233
0.00019
0.000183
0.000141
0.000151
100
100
100
100
m2 m N
m. N
172 m /
T72 N
10
48
56
64
40
48
56
64
10
48
56
64
40
48
56
64
Table 2: Loss and estimated convergence rates between neighbouring losses the given m/N. Left: Rate
along the column, iee. with respect m. Right: Rate along rows, i.e. with respect to number of samples
N. The first table is trained with mean squared loss (MSE) (13) and the second with kernel loss [7
44


Reviews:
[{"review_id": "LhAcLbr2fg", "reviewer": "Reviewer_naT1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper offers a fresh perspective that differs from much of the existing literature.  \n\n2. It considers of both under- and over-parameterized regimes, without requiring different assumptions for analyzing approximation, estimation, and optimization errors.\n\n**Weaknesses and Questions:**\n\n1. While the theorem statements are clear, it remains unclear how the approximation, estimation, and optimization errors are individually characterized. For example, in Theorem 2.2, Equation (14) includes terms like $ m^{-1/2} $ and $ \\Delta_{\\text{sample}} $, which appear to represent approximation and estimation errors, respectively, since one diminish with $ m $ and the other diminishes with  $ m $  and $ N $. However, these do not seem to align directly with the definitions provided in the introduction. Does this mean the authors did not follow the error decomposition as defined earlier?\n\n2. This leads to a broader concern: the remaining term in Equation (14) seems to be tied to the choice of algorithm. Specifically, the $ m^{-1/2} $ term arises due to the use of gradient descent, and $ \\Delta_{\\text{sample}} $ stems from perturbations analysis of gradient descent. However, the definition of approximation (and to some extent, estimation) error should be independent of the algorithm. Put differently, if we were to use an optimization method other than gradient descent, could we potentially obtain a better bound in Equation (14)?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper aims to provide a unified framework for quantifying approximation, estimation, and optimization errors when using gradient descent to minimize empirical loss. The authors establish theorems showing that the total error decreases exponentially until it reaches a level. The results apply to least squares loss in the under-parameterized regime, and to kernel-based losses in both under- and over-parameterized settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. In the equation above (2), authors use $\\hat \\theta$ on the left-hand side and $ \\theta$ on the right-hand side. \n\n2. Should \"permutation\" be \"perturbation\"?", "broader_impact_concerns": "N.A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6FglalIjYE", "reviewer": "Reviewer_2mbw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is well-written.\n2. Settings and assumptions are stated clearly.\n3. The new bound established in the paper requires less overparameterization, thus reducing the gap between theory and practice.\n\nWeaknesses:\n1. While the introduction states the bound as $\\lesssim m^{-a} + m^b N^{-c}$, the main theorems 2.2 and 2.3 do not state the result in this way. I wonder if the authors could resolve this discrepancy.\n2. In contrast to real-world neural network training, only the second-to-last layer is trained in the paper. I wonder if the main results still hold if more layers are trained.\n3. The data is assumed to be sampled from the uniform distribution on a sphere, which is a very restrictive assumption. I wonder if the main results still hold if a more general class of distributions is considered.\n4. While the bound may need less overparameterization than previous works, modern neural networks are certainly not trained in the NTK regime. A more substantial improvement over existing analyses would be analyzing the training regime beyond the NTK, even if this may not lead to a better test error bound / less overparameterization in the short term.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an NTK-based analysis of deep neural networks with only the second-to-last layer trained and proves that the test error could be bounded as $\\lesssim m^{-a} + m^b N^{-c}$, where $m$ is the width and $N$ is the sample size. Two settings are considered: pointwise sampling and kernel sampling.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the authors' responses to my Weaknesses 1 - 3 raised above.", "broader_impact_concerns": "/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9i6G4ORHOs", "reviewer": "Reviewer_gMn3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper is well-written and easy to follow. \n2. This paper provides a nice analysis of gradient descent in neural network training by systematically handling approximation, estimation, and optimization errors in one framework. \n3. The analysis seems rigorous though I didn't check the proofs thoroughly.\n\n\nQuestions:\n\n1. What is the benefit of assuming $x_i$ lies on the unit sphere? Is there a transformation allowing you to map a general $x_i \\in \\mathbb{R}^{d-1}$ to the unit sphere in $\\mathbb{R}^d$? \nFor instance, using the transformation $  x \\mapsto \\frac{(x,1)}{\\sqrt{||x||^2 + 1}},$ can the authors extend the current results to $x_i$ in $\\mathbb{R}^{d-1}$?\n\n2. If considering the case $y = f(x) + e$ instead of the exact interpolation problem, what is the main difficulty?\n\n3. How does the hidden layer size $m$ affect Theorems 2.2 and 2.3, aside from influencing the upper bound on $||f||$ and the probability lower bound?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the challenge of analyzing all three main sources of error in neural network learning---namely approximation, estimation, and optimization errors. Typically, each error type is studied in isolation or with partial overlap. In contrast, this paper aims to provide a unified theoretical framework that bounds all three simultaneously under specific settings involving fully connected networks trained by gradient descent, examining both standard $L2$ loss and a kernel loss. In this setup, the training samples $x_i$ lie on the unit sphere, and $y_i = f(x_i)$ represents the function values that the network aims to interpolate. A key takeaway is that, under the neural tangent kernel (NTK) regime, while the network’s generalization error remains above a certain threshold, the gradient descent procedure reduces the error exponentially fast in each iteration.\n\n\nI enjoyed reading the paper and I think the results presented in the paper deliver valuable insights. It would be very helpful if the authors could clarify the questions below.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested Changes:\n\n1. Equation (4) does not match Equation (16).\n2. On page 5, there is a typo in the lines beginning with $ g_{\\theta}(x)$; an extra “)” appears.\n3. On page 5, what is the purpose of introducing $g(x)$ and $ g_{\\theta}(x)$? It seems that setting $ g(x) \\equiv 0 $ might be possible.\n4. On page 6, under Equation (7), there are multiple typos in the lines beginning with $W^L$, $W^{L-1}$, and $ W^1 $. This makes it unclear which weight matrices are being trained and which are not.\n5. On page 11, the word \"permutation\" should probably be replaced by \"perturbation\". The first equation containing the term PERMUTATION needs to be realigned.\n6. On page 12, under \"Remark on Generalization Errors and Optimization\", the norms $||W^{L-1} - W_0^{L-1}||$ and $|| \\theta-\\theta_0 ||_*$ are introduced, but their definitions do not appear until page 28.\n7. On page 26, the variables $x_{n+1}$ and $y_{n+1}$ are used as variables distinct from the training data $(x_i,y_i)$.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)