Nonlinear Behaviour of Critical Points for a Simple Neural Network
Authors: Gerrit Welper
Venue: Accepted by TMLR ()

Abstract: In severely over-parametrized regimes, neural network optimization can be analyzed by linearization techniques as the neural tangent kernel, which shows gradient descent convergence to zero training error, and landscape analysis, which shows that all local minima are global minima.

Practical networks are often much less over-parametrized, and training behavior becomes more nuanced and nonlinear. This paper contains a fine grained analysis of the nonlinearity for a simple shallow network in one dimension. We show that the networks have unfavorable critical points, which can be mitigated by sufficiently high local resolution. Given this resolution, all critical points satisfy $L_2$ loss bounds of optimal adaptive approximation in Sobolev and Besov spaces on convex and concave subdomains of the target function. These bounds cannot be matched by linear approximation methods and show nonlinear and global behavior of the critical point's inner weights.

Published in Transactions on Machine Learning Research (10/2024)
Nonlinear Behaviour of Critical Points for a Simple Neural Network
G. Welper Deportment of Mathematics University of Central Florida Orlando, FL 32816, USA
gerrit. wwritt.weperruucf.com
Reviewed on OpenReview: opppr//veee. net/ ftrumm of=
Abstract
In severely over-paramelrized regimes, neural network optimization can be analyzed by lin- earization techniques as the neural tangent kernel, which shows gradient descent convergence to zero training error, and landscape analysis, which shows that all local minima are global minima. Practical networks are often much less over- cer-paramettized, and training behaviour becomes more nuanced and nonlinear. This paper contains a fine grained analysis of the noulinearity for simple shallow network in one dimension. We show that the networks have unfavourable critical points, which can be mitigatod by sufficiently high local resolu- tion. Given this resolution, all critical points satisfy L2 loss bounds of optimal adaptive approximation in Sobolev and Besov spaces convex and concave subdomains of the tar- get function. These bounds cannot be matched by linear approximation methods and show nonlinear and global behaviour of the critical point's inner weights.
1 Introduction
In this paper, we analyze nonlinear aspects of neural network training for a simple model problem in su- pervised learning: For samples zạ and data y! = f(zz) generated by some unknown target function f, find neural network fo with weights 0 by minimizing the least squares loss. To motivate the results, first review some common approaches in the literature.
Landscape Analysis Gradient descent can easily get stuck in local minima. That this fact does not harm ncural network training is the purview of landscape analysis. It aims to demonstrate that either the loss has no local minima, in favour of saddle points, or all local minima have small loss value and therefore provide good trained works... Indeed, the papers Soudry & Carmon (2016); Kawaguchi (2016):
Nguyen & Hein (2017); Ge al. (2018); Du Du & Lee (2018); Sootanolkotabi al. (2019); Venturi al. (2019)
Kawaguchi et al. 22019) Kawaguchi & Huang (2019) show that local minima global minima, cither under
strong assumptions, or over-paraameeriiaaiio with more network width than number of samples. Absent such assumptions, one needs to be more careful, e.g. the papers Swirszez et al. (2017); Safran & Shamir (2018):
He et al. (2020); Ding et al. (2022); Jentzen & Riekert (2024), find local minima that are not global. A more fine grained analysis of the landscape is included He et al. (2020). which finds valleys of path connected local minima.
Since these results mixed, matching local and global minima may be to strong goal and may be content with simpler question:
(Q1) Do critical points have favorable properties and what are these?
To address this question, first note that ultimately we are not interested in a good training error, but rather in good generalization error inf, [e fllia()) for some probability measure P that generates the input

---

Published in Transactions on Machine Learning Research (10/2024)
samples 2;- In general, it is difficult to understand the exact nature of the global optimum, but it is much more feasible to understand upper bounds of the form
inf Iife - fIl (00), JEK, 0
(1)
where n(0) is indicator for the network size, like width, depth or total number of weights and 0 an asymptotic rate. Similar to the no-free-lunch theorem, such bounds cannot work for arbitrary S. which is why we restrict them to some compact set K. Typically, it bounds Sobolev, Besov or Barron norms or other smoothness properties of the permissible targets f. Inequalities of type ① are common in approximation theory and have been studied extensively for neural networks. A literature overview is given later in the introduction.
We use this perspective to ease the characterization of local minima. If they do not match the global minimum, can they match their scaling behaviour
flfe - (0))", fE K, 0 is a critical point of the training loss?
(2)
Such results are well established for partial differential equations (PDEs), where Sa is nonlinear approxi- mation method like adaptive finite elements or wavelets and f the solution of PDE Cohen et al.) (2002):
Morin et al.] (2002): Binev et al.] (2004). Similar results also exits for shallow neural worksrks, when trained with greedy algorithms Siegel & Xu (002bb); Siegel et al. (2023) instead of gradient descent.
Linearization Arguments In wver-parametrized regimes, typically with more network width than train- ing samples, gradient descent training does not move the network weights far from their random initialization. As result, one can obtain accurate descriptions of the training dynamics by linearising the network at the initial value. Careful analysis then provides exponential gradient descent convergence to zero training loss.
A common representative of this approach is the neural tangent kernel (NTK) introduced in Jacot et al.
(2018); Li & Liang (2018); Allen-Zhu et al. (2019); Du et al. (2019b a). and refined in Zou et al. (2020); Arora
et al. 2019a b): Su & Yang (2019) : Lee et al. (2019); Song & Yang (2019) [Zou & Gu (2019)
; Kawaguchi
& Huang [2019] Chizat et al. (2019); Oymak & Soltanolkotabi (2020); Ji & Telgarsky
2020 y Nguyen &
Mondelli 2020)] Bai & Lee (2020): Cao & Gu (2020); Chen et al. 2021 Song ct al. [2021] Lee et al.
(0022
Gentile & Welper
2022
Welper 2024b abs
Keene & Welper (2024).
Contrary to this analysis, much of the promise of neural networks relies on their severe non-linearity, leading to c.g. high expressivity and excellent function approximation properties, even in high dimensions. Can these be exploited by gradient descent traïning? If we consider less over-parametrization under-parametrrizdd regimes, the weights can move farther from their initial and break the linear dominance in the training dynamics. Empirical studies Vyas et al. (2023) (see also Lee al. (2020); Seleznova & Kutyniok (2022)) on image classification datasets show that in such regimes networks perform better than extremely wide networks with dominantly linear behaviour. A theoretical understanding of these regimes is
or even slightly
still largely unknown. This leads to a second question:
(Q2) Can training in under mnder-parametrian or only slightly over perapparaetrized regimes exploit the nonlinear nature of neural networks?
To this end, is instructive to look classical approximation methods, where fo replacod by c.g. splines, finite elements or wavelets. These depend nonlinearly on 0 if adaptivity is used and linearly if not. The non- linear variations strictly include the linear ones so that info IIfnontineur 1ampttnearrf1l ffll s infe in the upper error bounds (1) this does neither change the number of degrees of freedom (weights) n(0) nor the (maximal) rate r. It does change, however, the size of the compact sets Klinear C Knoolinear for which the given rates can be achieved, with the latter being significantly larger.
|[f flincar fll- Nonetheless,
In summary, if we want to establish approximation results (2) for noural network critical points with nonlincar compact sets Koottinear, we have to carefully exploit the nonlinear nature of the networks and can no longer rely on vanilla NTK analysis.
2

---

Published in Transactions on Machine Learning Research (10/2024)
New Contributions In this paper, we address questions [Q1) and (Q2)
for the very simple model problem
lo(x) Σ wo br),
with ReLU activation, in a one dimensional interval I E PEDC R, trained on the L2 loss llfe - fll (D))) This is probably the simplest choice with nonlinear weight dependence (of the bx), non-convex loss and fully understood approximation behaviour both in linear (b, untrained) and non- linear (6, trained) cases. The continuous loss simplifies the analysis and places the problem an under- ander-parametrized regime, independent of the width m. Empirical losses, with large numbers of samples, are expected to show similar behaviour by classical arguments in statistics and machine learning, different from the over-parametrized regime, where their application is more complicated.
Although this setup may seem simple, it contains two challenges:
1. The problem does have bad local minima.
2. Large compact sets K Knontinear in the approximation bounds (2) cannot be achieved by linear ap- proximation methods and require careful global placement of the nonlinear inner weights b,
The first result shows this global placement for all critical points of the loss function in the infinite width limit: If we order the inner weights bo S ... < bm the normalized grid size satisfies
lim
m(b, by-1) = constant (x)
(4)
with possibly a different constant for each interval which is strictly convex or concave. The factor 1/h is reciprocal to the uniform grid size h and used for normalization. The right hand side shows that the breakpoints b, are close wherever the second derivative f"(x), and hence the local approximation difficulty, is large. Generally, this requires global movement of breakpoints b, dependent on f, from initial locations independent of f. For finite m, analogous arguments show that at critical points of the loss the breakpoints equidistribute the local smoothness
|f (210 constant,
again on intervals Dy where f convex or concave. With standard approximation theory, this leads to approximation errors of the type
fo fll S 1 [|a//\))))())))
where [Z] is the number of breakpoints in the respective intervals. To avoid bad local minima, these results require the critical points to have sufficient local resolution b,, - b so that f does not have highly oscillatory features between breakpoints that are imperceptible the gradient. The rigorous statements are in Thcorems 3.3 and 3.4 and an example for the conditions is given in Scction
The results demonstrate approximation errors (2) subdomains where f is convex concave with K := K2/5 := {f E L2(D): |I 1). A subtle, but crucial, observation is that f" is measured in the very weak L2/5 (quasi-) norm (or Besov spaces in Section B.3), which allows us to achieve high approximation orders for fairly rough functions f. These are not possible for purely linear approximation methods (by Kolmogorov n-width lower bounds) and therefore demonstrate that finding local critical points of the loss landscape allows us exploit some nonlincarity of the neural networks.
Infinite Width Limit Mean field theory of neural networks Chizat & Bach 2018 Mei et al. (0018)
Rotskoff & Handen-Eijnden (2018); Sirignano & Spiliopoulos (2020) takes the infinite width limit
w. o
wor (T x) du(v,w)
for some limiting measure μ and then analyzes training of the infinite networks. For comparison, the limits of the gird size { are taken in different order: We first compute the gradient, decouple the computation of b, from w, and then take the limit afterwards.
3

---

Published in Transactions on Machine Learning Research (10/2024)
Beyond Lincarization Some recent papers analyze neural network training beyond the NTK regime. For example, Damian et al. (2022 Lee et al. (2024) demonstrate results for two layer networks that cannot be achieved by kernel methods for polynomials g(Ur) that depend only on a few dimension by the inner matrix U E Rxxd with r < d.
Approximation Universal approximation theorems Cybenko p1889: Hornik et al. (189)) Barron (1993)
Zhou (2020); ; Lu et al. (2017): Hanin & Sellke (2017) show that neural networks can approximate any function arbitrarily well. Since this is true for virtually all approximation methods in practical use, it is important to quantify the approximation error more closely. This usually leads to errors bounds of type Q which are studied extensively for neural networks. If the compact set K consists of functions with bounded Sobolev or Besov smootthess, results can be found in Gribonval et. al. (2022); Gühring el al. (2020); Opschoor et al.
(2020g; Li et al. (019); Suzuki (2019): or for improved rates that surpass classical methods for the price of discontinuous weight assignments in Yarotsky 22017 2018): Yarotsky & Zhevnerchuk (2020): Daubochies (2022); Shen al. (2019) : Lu et al. (2021). Compact sets specifically tailored to neural networks
jt al.
include Barron and related spaces Bach 2017]; Klusowski & Barron (2018); Weinan et al. 2022 Li et al.)
(2020): Siegel & Xu [2020] 2022a); Bresler & ] Parhi & Nowak (2021); Unser (023). Overviews
are in Pinkus
1999
DeVore et al. 2022 ) Weinan et al. 2020
Berner et al. (2022).
In the majority of neural network approximation results, the weights are hand-picked and only few papers
show approximation properties gradient descent trained neural networks Jentzen Riekert (022 Ibrag-
imov el al. (002);; Drews Kohler (2022); Kohler & Krzyzak (2022); Gentile & Welper (2022); ; Welper
(2024b a). These heavily rely on the outermost linear layer, or a NTK linearization and therefore show ap-
proximation guarantecs only for compact sets K that be well approximated by linear methods. Larger, nonlinear classes K can, to best of our knowledge, so far only be proven for greedy training algorithms Siegel
& Xu 2022b
Siegel et al. (2023) which rely on another non-convex optimization problem in each step.
Notations We use e for generic constants that can be different in each occurrence, but are independent of and the network width m. We abbreviate S cb, a 2 b and ca S b S ob by a S b, a 2 b and a b, respectively. We define [m] = f1,...,, m) and IP" as all polynomials of degree most r. We use Sobolev || (lw)))D) and Besov || (l)))((,,,D)) norms with their usual definitions, stated in Section B.1 For any interval I, we denote the corresponding L2 inner product by (:.)).
2 Approximation By Piecewise Linear Functions
Before we state the main results of the paper, we review relevant approximation properties of the neural networks. The set of all networks of type
T
Y m = fo() = Σ w. by) wr, by E R
corresponds exactly to continuous piecewise linear (CPwL) functions in one dimension
Σm = (flf is continuous piccewise lincar with m breakpoints).
often referred to as first order free knot splines or finite elements. To discuss the benefits of nonlincarity, we compare them with the simpler linear class
Σy = ( Em /uniforo distance between neighbouring breakpoints),
corresponding to networks with untrained inner biases b, and hence convex loss. Notice that the lat- ter set En, is linear, while the former Ym = Em is nonlinear and hence we refer to them as linear and nonlinear opprorimation methods. Their approximation errors are precisely understood:
inf | flle, S Om -m- Plfl
(5)
inf || fll,, S Cm 21 13 (k2/6) deEn
4

---

Published in Transactions on Machine Learning Research (10/2024)
These correspond exactly to the approximation bound in the introduction if we define Kspp= := {f Lz(D): Ullgg(2,) $ 1) with p 2 and p 2/5.
Up to minor differences, the Besov norms (fleg(t))) z [L, are equivalent to Sobolev norms, which bound the s-th derivative of f in Lp. The former are technical, but usually preferred in approximation theory because they are well behaved for p 1, as used in the nonlinear bound above. For orientation, these spaces are often arranged in Figure [ The sets Ks.p become larger with decreasing and decreasing p.
may trade some p for some that all spaces (s, p) above the dashed line in the figure are contained in L2 and thus Ke.p C Ko.2. See Section B.1 for definitions and DeVore & DeVore 1998] for more details.
By Sobolev embedding theorems,
Lorentz
1993 1
B
B2/s (2/5(/2/3)) 22/5))
L2 L
1/p
Figure 1: Diagram of Besov spaces. Each point (1/p, s) corresponds to one space Bx(pp) for s > 0 and Lp for
Let us compare the linear approximation Dy with the nonlinear approximation Em- First observe that in 5 the rate m is identical for both methods. Generally, piecewise linear approximation does not achieve higher rates, even f admits more smoothness. However, since || (Il X || []))(D)) the smoothness conditions for nonlinear approximation are much weaker. For example Se = sigmoid(2/e) has norms
| (D))) ~
II Lays(D) ~ ee.
(6)
Indeed, the second derivative of size -2 a region [-ce, ct] and negligible outside. Thus (L,"),
(=)(al)l - As goes to zero and fe converges to jump function, the L2 norm blows up. whereas the 22/5 norm remains bounded. This provides significantly better approximation bounds in (5) for nonlinear approximation. If we use Besov spaces instead of the second derivative, this extends to the jump function itself, which can be approximated by nonlinear methods up to order m whereas linear approximation only achieves order < m 112
While the lincar approximation has a fixed number of breakpoints b, near the jump or sharp gradicnts of Se, the adaptive spproximation can allocate more resources where f is complicated. Indeed, algorithms and proofs for the approxination bounds (5) aim for breakpoints that equidistribute the local errors
llfe flles((b.bb...))) = constant for all
or closely related the local smoothness
(1l = constant for all r.
(7)
Finally note that the bounds 5 are sharp in several ways. For example the best possible rate lincar approximation methods can achieve for functions f in the class K2,p C. K2,2/5 with 2 < S m 22 } < m- soe Lorentz al. (1996). Chapter 14, Theorem 1.1. Therefore, if we can find critical points of the neural network 9 loss that achieves second order m 2 error on the class 2/5 it must exploit the nonlincarity of the network.
5

---

Published in Transactions on Machine Learning Research (10/2024)
3 Main Result
Sctup Maybe the simplest neural network with non-convex training objective and fully understood ap- proximation properties is
Fw.v,(()) = Bo + Wox + Σ WV, B.)
(8)
in one dimension, which generates the piecewise linear functions Em of the last section. By the property (ar) = (x) for a 2 of ReLU activations, the separation of Wr and V, is redundant and we simplify the network to
fw.b: bu + WoF + Σ w - b,):
with appropriately redefined weights. The case O requires a slight technicality and is considered in the following lemma. The lemma also shows that critical points of the loss carry over to the simplified network Lemma 3.1. Let D be interval. Assume Fw,,, is crilical point of the loss minwy,n a porv.a-fliiuo Then Fw,,B is piecewise linear with m m breakpoints
b, B./Ve
for all r with W,, Vr + 0.
Furthermore, there is a network (x)) = Fw.,B(I) of width m. with the same breakpoints that is critical point of the loss min Ilfu.b f
The proof is in Section B.4 Since our main theorems characterize critical points, it suffices to consider the simplified variant of the networks. Finally, the term by + wax can be generated by two ReLUS a - b,), one with breakpoint at the left boundary and one more left of the domain. Therefore, we drop by and wy and arrive the network
fo(x) = Σ wrolx 6r),
(9)
that we consider throughout the paper. We train the network with loss
1 {())= - -flli
(10)
on some finite domain D C IR and some target function f L2()). This matches the infinite sample limit of the least squares loss and places us in an under-paramettrized regime similar classical statistics. Although the ReLU activation has kinks, this loss is strongly differentiable for all weights 0. Indeed, suffices map 0 + fo(-) from parameters to (2(D) functions. This topology is sufficiently weak to render the map differentiable, unlike the regular pointwise topology, which does not. See Gentile &
consider the network
Welper 20222) for details.
Cleanup Gradient descent and related methods converge to critical points,
VE(0) =0
(11)
which we examine more closely in the following. To ease the theoretical analysis, we start with some notational clcanup, which does not alter the actual network. First, we drop inactive ncurons with w, = Second, we join neurons with identical bias b, into one neuron and adjust the outer weights w, accordingly. Third, we drop neurons for biases b, outside of the domain D, except for the largest b, left of the domain, which influences the left boundary value of fe. Finally, we add one artificial breakpoint 6n at the right end of D, which does not change fo inside D, but avoids technicalities. This yields m. < m neurons, which we reorder according to
bo <
by
(12)
and denote as cleaned critical breakpoints. These define intervals I, := [b,-1, by] of length hy := [T]. We denote two consecutive intervals by T = T U Te+1 and hy+ 1T-

---

Published in Transactions on Machine Learning Research (10/2024)
Equidistribution We have seen in the last section that optimal asymptotic approximation rates are achieved by equidistributing local errors or smoothness via careful placement of the breakpoints by- It is instructive to start with an informal discussion of the infinite width limit. To this end, we define the grid size limit
h(x) == lim mlyy zEf,
where for every we choose the interval I, with width h, that contains æ. For uniform grid, we have grid size h, = DI/m and therefore h(x) = mh, = |D]. For non-uniform grids, h(x) measures the ratio h,/h between the actual local grid size h, and the uniform grid size h = DD/m,, up to a global factor. If the limit exists, h(z) is given by the following lemma.
Lemma 3.2. Let f be smooth and for every m let br, r E [mm]] be cleaned crilical breakpoints the limit h(x) exists, it satisfies
12 If
h(z) = ca (x)
with possibly different constant e on each interval for which (x) is non-zero.
For finite m, careful perturbation analysis leads to the first main theorem.
Theorem 3.3. Let 0 be critical point [1I,, with cleaned breakpoints in ascending order 12 For T, E {2....,mi) m) let I fr,r 1. be set of consccutive neurons with Dr = Ukez Is and
- max litt (e, let 11
(l,, }
C
min 1f"(z)) xEl+t
(13)
for some <. 9.P S oc and some sufficiently small constant C' > independent of f and hy. Then for 1, k E D7 we have equidistribution
|f ~ IIf (lapo()))
This is preciscly the equidistribution 7 used in the proofs of CPwL approximation bounds (5) We discuss the result and the major assumption 13 after the approximation theorem below. In short, high oscillations strictly contained in interval I, are imperceptible to the gradient and therefore lead to bad critical points. The assumption ensures that have enough breakpoints to fully resolve such oscillations.
Approximation Once we have established equidistribution, approximation results can be obtained along standard lines.
Theorem 3.4. Let 0 be critical point 11 with cleaned breakpoints in ascending order 12 For r, E [,...., m) , let I = fr,r 1 18 be set of conseculive neurons with Dz = Ukez In and
カート max
M ( (e,((ee)) }
1+++
C min (f"(z) xElxt
(14)
for some 1 < 9. oa and some sufficiently small constant C > 0 independent of f and hy. Then
life ffll((p))) S 11 (1a))))))
(15)
Discussion Approzimation Result: Note that [Z] is the number of breakpoints Dj and therefore is analogous to the number of breakpoints m on the full domain. Therefore, any critical point subject to the given conditions achieves asymptotically optimal CPwL approximation on subdomains Dr C D and can properly utilize the nonlinearity of the network. If we have multiple subdomains DI, and DI,, the total allocation of breakpoints on each of these may be suboptimal.
The main purpose of assumption 13 is to prevent bad critical points: Oscillations of the target f that are strictly contained inside one interval I, do not change the gradient and can cause unfavorable critical points. The assumption is satisfied the network's local resolution h, sufficiently high to capture all fine grained features of f. For comparison classical adaptive CPwL approximation methods contain "data oscillation" terms in their error bounds. See Section 5 for more careful discussion.
Resolution:

---

Published in Transactions on Machine Learning Research (10/2024)
Smoothness: The fourth order smoothness in (13 is higher than the smoothness in the approximation bounds and seems to contradict the discussion in Section 2 Indeed, it does rule out limiting cases like jump functions. This is also the reason why we can use Sobolev type norms instead of Besov norms. However, functions with large gradients as in example (6) are permissible. In this case assumption (13) provides some a-posteriori bounds on the resolution necessary lo achieve equidistribution and adaplive approximation errors. However, even if this requires large networks none of the constants enters the approximation error itself: As soon as the networks are big enough, we obtaín nonlinear approximation bounds with small constants only dependent the favourable [|// smoothness bound.
Conver/Concauve. Assumption 13 implicitly entails that is concave convex on each subdomain Dz. While it is not clear if this is strictly necessary, longer stretches with f"(x) = 0 seemn problematic: In these f is linear and can be approximated with zero local error. Then any breakpoint in this region has no good gradient information for its placement.
The networks are zero fa(æ) for all < bn left of the leftmost breakpoint. To avoid dealing with this boundary condition, we exclude the corresponding interval 4, by requiring s,r 2 2 in the definition of I.
Left Boundary:
Comparison with NTK Theory: In over perrparametrriee NTK regimes the weights do not move far from their initialization during gradient descent training. This implies that uniformly initialized breakpoints b, remain uniform and can generally not equidistribute local errors. Accordingly, the approximation error achieved after training is bounded by (ff S m (((a(()) in Gentile Welper (2022) for some constants a 2 and 0 S 1/2. In particular, the smoothness is measured in the L.2 norm as for uniform CPwI. approximation and not in suitable larger Lp norm for adaptive CPwL approximation.
Inner Weights: The equidistribution results carry over to more standard networks Fw,,,n with inner weights Vr, as defined in ( Indeed, by Lemma B.2 the breakpoints of a critical point Fw.v.B match the breakpoints of a critical point fu,b, for which Thcorem 3.3 provides cquidistribution on convex/concave sub-domains.
4 Proof Idea
This section contains a short overview over the proof. The optimization of the outer weights wy is convex and therefore fairly simple. On the other hand, the optimization of the inner weights b, is non-convex and
the main objective of the prove to demonstrate their equidistribution in Thcorem 3.3 Once this property
is established, the approximation Theorem 3.4 follows by standard arguments DeVore (1998). The proof proceeds in several steps.
1. Critical Points: Define the spaces
X = span (Or, fo r E [m]] = span b,) r e [m]].
X = span fo r E [m]] span(w, b,) r E [m]]
of the partial derivatives and the residual к == fo - f. Then, by taking linear combinations, it is easy to see that the critical point conditions
0e,6(0)= = (N, Og fo) = 0,
are equivalent to
(R, v) 0,
VEX+X.
(16)
2. Eliminate wy: In the critical point conditions the residual к depends on both w. and by. To show equidistribution, which depends on b, only, we eliminate w, from the equations. To this end, define the Izzorthogonnl complement space X so that
x+x=xex+
X
8

---

Published in Transactions on Machine Learning Research (10/2024)
Since X is the span of all neurons o(x-b,) we have fo X and therefore (x, (fo - f.u) (f.e). for all X- by orthogonality. Thus, the critical point condition implies
(f = 0, vE
This condition does not depend on wy any longer and guarantees equidistribution, as we show the following steps of the proof.
3. Characterization of the Complement space X=: We construct basis functions
h hx)" -1-+10((z))
x 2 I, x E 1,+1
px(x))
0,
clsc
for X supported on two consecutive intervals I, and 1,41- The critical point condition then yields
(f. ()) 0 and integration by parts
hy , (f" de+1)1--
(17)
Since the functions and are non-negative bump functions, the smoothness conditions of the main theorems imply that
[Ifll ~ hr
(/"""""r)) 2.)1. hf dr41)144 ~ [Iflleeyp((ee))
(18)
Refined Analysis: While the last two equations provide equidistribution on two neighbouring in- tervals, they are insufficient: (18) has the wrong norm, L1/2 instead of L2/5, and too inaccurato when chaining over large numbers of intervals. 117 cannot be chained directly because the functions ó # è are asymmetric. A more refined analysis of the asymmetry and passing to the limit m + oo shows that the grid size limit h(x) limm-te mh, for I, satisfics the differential equation
1 1" pW 10==-h1
where the left hand side originates from 17 and the right hand side from the asymmetry. This a first order linear differential equation for 12, Solving it with an integrating factor leads to [ 0 and the extra power 4/5 leads to proper grid size limit for L2/5 equidistribution. The main result Theorem 3.3 follows from perturbation analysis of this ODE for finite h,-
5 Unfavourable Critical Points
5.1
Critical Points with High Oscillations
Recall from
16 that critical points given by the condition
(ʃe f. u) = 0,
V X X
To construct unfavourable critical points, we merely need perturbation & that is orthogonal + X. Then fo also critical point for f f yp:
(fa 0,
VEX+X.
It is casy to construct &o so that fo is a bad approximation. To provide a simple example, let f = 0 so that fo = must also be zero. Now choose two neighbouring breakpoints b, and br+1 and define an oscillation ş supported inside I, = [b,- by], with some margin to the boundary and orthogonal to all linear functions pl. Then, we have yp X + X and fe
a critical point for approximating + op with arbitrarily large approximation error e||p|]]. On the other hand, the network fo may have an arbitrary number breakpoints outside of T,. With optimal placement, they all be used approximate & and make the approximation

---

Published in Transactions on Machine Learning Research (10/2024)
error arbitrarily small. This simple example is sufficient for our purposes, but the literature contains many
more Swirszez et al. (2017) Safran & Shamir (2018): He et al. (2020) Ding et al. (2022 Jentzen & Riekert h2024..
Note that by construction any small perturbation of the outer weights wy or the breakpoints b, does not change the loss for approximating 0y so that the large error is imperceptible to gradient based optimizers. In the main theorems, assumption (13) ensures that the network has sufficient resolution that the target f cannot have any severe sub-grid oscillations. For comparison, classical adaptive CPwL approximation algorithms error indicators steer the approximation towards error equidistribution. Theoretical results
then include extra "data oscillation" error terms to capture sub-grid oscillations Cohen et al. (2002): Binev
et al. b000);; Morin et al. (2002).
5.2 Avoiding Critical Points with High Oscillations
This section provides an informal motivation how assumption (13) rules out bad local minima with sub- grid oscillations. To this end, first note that in case the target f is simple function, like e.g- second degree polynomial, it clearly cannot oscillate as vp in the counter example. Of course this is too strong an assumption, but what if f is close to second order polynomial? Since second order approximation converges faster than first order approximation, for sufficiently small intervals 1, = b,], we can expect
inf Ilf Pallea(1.) SC inf |lf Pillea(T.) S Cll fo foll P2E
(19)
PIEPi
for some arbitrarily small constant C, with the last implied by the linearity of fe on I,.. Denoting the minimizer on the left by P2,r, with the triangle inequality, it is easy to show (see c.g. (36 that
(1 + C)-
( S - Sollentr) (1))))>)_----llppaapa foll
(20)
i.e the error approximating f and of approximating the simple function P2,r is about the same. Hence, if we can prove error equidistribution for locally simple functions P2,r, we also obtain error equidistribution
for f
Il - follea(1.) ~ llp2.- - (o ~ 1lp2. - folle,(1)) ~ |lf - fol foll
for any two intervals r and 8. This is a slightly stronger alternative to the equidistribution of smooth- ness in Theorem 3.3 In summary, given [19), we can reduce equidistribution from arbitrary to simpler equidistribution of piccewisc second degree polynomials.
Before we discuss 19 more carefully, let apply our observations the counter example from the last section. If the oscillation &p from the example is orthogonal to pt and p2, the best approximations and the network from the example satisfy pl p2 fa 0 and we have
lpp.r follea(()) 0,
Il folle2(1.) =
# O,
which contradicts the norm equivalence 20 Hence, if we can establish in the counter example are not possible.
19 severe sub-grid oscillations as
Let us now consider the condition [9 more carefully. Informally, it follows directly from assumption
of the main thcorems. Indeed, standard direct approximation incqualities (41) provide the first degree approximation error
inf |l 11f-Pille (P $ (2) PIEM
and the second degree approximation error
inf |l -f--aal P2llea(1)) S ( ( P1EP2
Notice that the second degree approximation has higher power on hy and therefore much smaller for small intervals. Assumption (13) contains concrete criterion when this happens (replacing hr with h, for
10

---

Published in Transactions on Machine Learning Research (10/2024)
3.-
077 degine1 degine 2
3.0-
0.5
3.2
0.4
-16
-14
0.42
(a) Coarse interval I,
(b) Fine interval 1,
Figure Approximation a oscillatory = L5 L3 constructed from Legendre basis polynomials [i On the coarse interval (left), the first. and second degree approximation do not capture the function correctly. On the zoom in a fine interval (right), the second degree approximation captures the bulk of the function, whereas the first degree approximation does not.
simplicity). It implies
13 x
|| P2ll S ( P2Er2
inf
cChi min ())
sel.
$
min [1)) seI,
cCh
IL)(())
for some constant C' that is assumed to be sufficiently small. Direct approximation results tend to be sharp asymptotically, in which case we can directly compare the first and second order approximation to obtain 19h:
inf |lf p2lle,(1.) S CCh (1, S C inf |lf Pille,(E)) P2EF2
PIEPI
A rigorous argument is c.g. in Lemma A.27 applied to f" and constant polynomials p/. The lemma also includes replacements (Jo - -,"),, R (Jo P2.r, u), of f by local polynomials for the critical point conditions (16), which require a little more care because of missing absolute values and potential cancellation.
A simple illustration is given in Figure We can see that the approximation on coarse interval does not capture the oscillatory correctly. On the fine interval, the second degree approximation is fairly accurate, and captures the bulk of f, required by (20).
5.3 Feasibility of Assumptions
When is the main assumption 13 satisfied? A simple guarantee can be given if
f smooth (1)(() ()), ( [l,,,D)) S for some S and p from 13
f is uniformly convex (or concave) (x) 2 C. for some constant > 0 and all E D (or convex region as in the main thcorems).
In this case, with the crude bound [[f(s) (L,(1.) & [1] [l,, s = 3, the assumption reduces to
- h
CC
for some sufficiently small C. This is clearly satisfied if the breakpoints are close so that h, |by- by is small. Note that practically the constants S and C-1 may be large that need many breakpoints to
11

---

Published in Transactions on Machine Learning Research (10/2024)
0.30
0.30
0.25
0.2
0.3
0.0
0.05
0.5-
-1.0
(a) Uniform initial bias.
(b) Random initial bias.
Figure 3: Cusp function 21 (red) and neural network approximation (blue) at each 20000-th epoch (light
to dark blue). The circle markers show the location of the breakpoints.
apply Theorems 3.3 and 3.4
However, once we can, the resulting equidistribution and approximation errors have standard constants that are independent of C and S.
We have argued that the condition [1 is simple lo verify for given critical point. A more difficult question is to what extent we can guarantee that these favourable critical points are the limit of gradient descent. We can choose h, arbitrarily small at the initial breakpoints. By stability gradicnt descent, one may argue that two breakpoints that are close at the initial may remain so during training. This would entail (13) also for the gradient descent limit. However, a rigorous argument requires a full understanding of the gradient descent dynamics, which not considered in this paper and left for future research.
6 Numerical Experiments
This section contains some preliminary numerical experiments. We train the target function
f(x)
|x 0.1
x E [-1,]]
(21)
which has cusp at the origin. This entails that f" is not contained in [2([-1,1), but is contained in L2) so that we expect a better performance of nonlinear approximation. Intuitively, this is achieved by moving more breakpoints to the vicinity of the cusp. Figure X shows the evolution of the networks and breakpoints during gradient descent training with the following setup
Network architecture 9
Network width: 16.
Learning rate: 0.01.
1280 samples in 10 batches.
100000 epochs, with plot of the network every 20000 epochs.
The results show that gradient descent moves the breakpoints towards the cusp at the origin, as expected. However, the convergence is very slow and requires a substantial number epochs in relation to the simplicity of the problem.
References
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
12

---

Published in Transactions on Machine Learning Research (10/2024)
International Conference Mochine Learning, volume 97 of Proceedings of Machine Learning Re- search, pp. 242-252, 252, Long Beach, California, USA, 09-15 Jun 2019. PMT.R Full version available at /tapp::/arxiv.oor//bb////t wwtg/b///////i/// /tte/abb/1811.03922
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized 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 infinitely wide neural net. In H. Wallach, H. Larochelle, A. Beygelzimer, F. A'cch Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019b.
Francis Bach. Breaking the curse of dimensionality with convex neural networks Journal of Machine Learning Research, 18(19):1 53, 2017.
Yu Bai and Jason D. Lee. Beyond linearization: On quadratic and higher-order approximation of wide neural networks. In International Conference on Learning Representations, 2020.
A. R. Barron. Universal approximation bounds for superpositions a sigmoidal function. JEEE Transactions on Information Theory, 39(3)0 945, 1993.
Julius Berner, Philipp Grohs, Gitta Kutyniok, and Philipp Petersen. The Modern Mathematics of Deep Learning. In Philipp Grohs and Gitta Kutyniok (eds.), Mathematical Aspects of Deep Learning, pp. 1-111. Cambridge University Press, 1 edition, 2022. ISBN 9781009025096 9781316516782.
Peter Binev, Wolfgang Dahmen, and Ron DeVore. Adaptive Finite Element Methods with convergence rates. Numerische Mathematík, (7 April 2004.
Guy Bresler and Dheeraj Nagaraj. Sharp representation theorems for ReLU networks with precise dependence on depth. In Н. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral 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(04):3349 3356, April 2020. ISSN 2374-3468, 2159-5399.
Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over nor-paaramtteiization is sufficient to learn deep reflu} networks? In International Conference on Leurning Representations, 2021.
Lénaic Chizat and Francis Bach. On the global convergence gradient descent for wer-parameterized models using optimal transport. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bisnchia and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. https://arxiv argg/bs//800 19118.995555.....
Lénaïc Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' 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 11 Beyond the Elliptic Case. Founda- lions of Compulational Mathematics, 2(3):203 202, August 2002. ISSN 16153375.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Math. Control Signal Systems, 2: 303-314, 1989.
Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn representations with gradient descent. In Po-Ling Loh and Maxim Raginsky (ods.), Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 5413-5452. 5452. PMLR, 02-05 Jul 2022.
13

---

Published in Transactions on Machine Learning Research (10/2024)
I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova. Nonlinear Approximation and (Deep) ReLU Networks. Constructive Approrimation, 55(1):127-172, February 2022. ISSN 0176-4276, 1432-0940.
R.A. DeVore and G.G. Lorentz. Constructive Approzimation. Grundlehren der mathematischen Wis- senschaften. Springer Berlin Heidelberg, 1993. ISBN 9783540500270.
Ronald DeVore, Boris Hanin, and Guergana Petrova. Neural network approximation. Acta Numerica, 30: 327 444, 2021.
Ronald A. DeVore. Nonlincar approximation. Acta Numerica, 7:51-150, 1998.
Tian Ding, Dawei Li, and Ruoyu Sun. Suboptimal Local Minima Exist for Wide Neural Networks with Smooth Activations. Mathemalics of Operalions Research, 47(4):2784-281) November 2022. TSSN 0364- 765X, 1526-5471.
Selina Drews and Michael Kohler. On the universal consistency of an over-paraametrized deep neural network estimate learned by gradient descent, 2022. https://axx.v.orr/abb///// 14288
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 Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 1329-1333 PMLR, 10-15 Jul 2018.
ittps://arxiiy org/ abs// /10.//10..... 012066
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. 1675-1688 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 ono-hidden-laye neural networks with landscape design. In International Conference on Learning Represenlations, 2018. httpp::/aaxxw..or//bbb//////
R. Gentile and G. Welper. Approximation results for gradient descent trained shallow neural networks in 1d, 2022. https://arxiw.org/bbbs//// wwtp://wwww.abb//...ooem
Rémi Gribonval, Gitta Kutyniok, Morten Nielson, and Felix Voigtlacnder. Approximation Spaces Deep Neural Networks. Constructive Approzimation, 55(1):259 367, February 2022. ISSN 0176-4276, 1432-0940.
Ingo Güthring, Gitta Kutyniok, and Philipp Petersen. Error bounds for approximations with deep ReLU neural networks in ws.p norms. Analysis and Applications, 18(05):803-88) 859,, 2020.
Boris Hanin and Mark Sellke. Approximating continuous functions by ReLU nets of minimal width. https:
//arxiv.org/ab//Ii 11278 2017.
Fengxiang He, Bohan Wang, and Dacheng Tao. Piecewise linear activations substantially shape the loss
surfaces of neural networks. In International Conference on Learning Representations, 2020.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks, 2(5))359-38) 366, 1989. ISSN 0893-6080.
Shokhrukh Ibragimov, Armulf Jentzen, and Adrian Rickert. 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://arxiy: http:///aaxiv..oo/aaa/////s///
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. Cosa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
14

---

Published in Transactions on Machine Learning Research (10/2024)
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(260):1 50, 2022.
Arnulf Jentzen and Adrian Rickert. Non-convergence to global minimizers for adam and stochastic gradient descent optimization and constructions of local minimizers in the training of artificial neural networks, 2024.
Ziwei and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small lest error with shallow ReL.U networks. In International Conference on Learning Represenlations, 2020.
Kenji Kawaguchi. Deep learning without poor local minima. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
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 Communicatiion, Control, and Computing (Allerton), pp. 92 92-99, 2019.
Kenji Kawaguchi, Jiaoyang Huang, and Leslie Pack Kaelbling. Every Local Minimum Value Is the Global Minimum Value of Induced Model in Nonconvex Machine Learning. Neural Compulation, 31 (11)))22993 2323, 12 2019. ISSN 0899-7667.
B. Keene and G. Welper. Approximation estimation and optimization errors for deep neural network, 2024. Submitted, under double blind review.
Jason M. Klusowski and Andrew R. Barron. Approximation by combinations of ReLU and squared ReLU ridge functions with el and e controls. IEEE Transactions on Information Theory, 61(12):7649-7656, 2018.
Michael Kohler and Adam Krzyzak. Analysis of the rate of convergence of an over-paraametrizeed deep neural network estimate learned by gradient descent, 2022.
wwwpxx/v.rrr/bbb//21.000 01443
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dicc-iickstein, 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' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Jachoon Lee, Samuel Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 15156-15172 Curran Associates, Inc., 2020.
Jason D. Lee, Kazusato Oko, Taiji Suzuki, and Denny Wu. Neural network learns low-dimensional polyno- mials with sgd near the information-theorell limit, 2024.
Jongmin Lee, Joo Young Choi, Ernest K Ryu, and Albert No. Neural tangent kernel analysis of deep narrow neural networks. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (cds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Resewrch, pp. 12282 12351. PMLR, 17 23 Jul 2022.
Bo Li, Shanshan Tang, and Haijun Yu. Better approximations of high dimensional smooth functions by doep neural networks with rectified power units. Communicationss in Computational Physics, 27 411, 2019. ISSN 1991-7120.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cosa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8157-8166. Curran Associates, Inc., 2018.
15

---

Published in Transactions on Machine Learning Research (10/2024)
Zhong Li, Chao Ma, and Lei Wu. Complexity measures for neural networks with general activation functions using path-based norms, 2020. https://arxiv wwtp:/rrggbbb//......
George G. Lorentz, Manfred v. Golitschek, and Yuly Makovoz. Constructive Approzimation: Advanced
Problems. Springer-Verlag Berlin Heidelberg, 1996.
Jianfeng Lu, Zuowei Shen, Haizhao Yang, and Shijun Zhang. Deep network approximation for smooth functions. STAM Journal on Mathematical Analysis, 5365):5465-5500, 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.), Advances in Newral Information Processing Systems 30, pp. 3231-62391 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, 115(33) E7671, 2018. ISSN 0027-8424.
06561
Pedro Morin, Ricardo H. Nochetto, and Kunibert G. Siebert. Convergence of adaptive finite element methods. SIAM Review, 44(4):631-65) 2002.
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 on Machine Learning, volume 70 of Procerdings of Machine Learning Research, 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. Tarochelle, 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.
Joost A. A. Opschoor, Philipp C. Petersen, and Christoph Schwab. Deep ReLU networks and high-order finite element methods. Analysis and Applications, 18(05):715 770, 2020.
S. Oymak and M. Soltanolkotabi. Toward moderate overparameteriration Global convergence guarantoes for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1(1):84 105, 2020.
Rahul Parhi and Robert D. Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1-40 2021.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acla Numerica, 8:143-195, 1999.
Grant M. Rotskoff and Eric -ijndnnEEinden.. Neural networks as interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. CoRR, abs/1885.00915, 2018. htttps//arxxv.orrg http//bb//88055 00915
Itay Safran and Ohad Shamir. Spurious local minima common in two-layer ReLU neural networks. Tn Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4433-4441, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Mariia Seleznova and Gitta Kutyniok. Analyzing finite neural networks: Can we trust neural tangent kernel theory? In Joan Bruna, Jan Hesthaven, and Lenka Zdeborova (eds.), Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, volume 145 of Proceedings of Machine Learning Research. pp. 868 895. PMLR, 16 19 Aug 2022.
Zuowei Shen, Haizhao Yang, and Shijun Zhang. Nonlinear approximation via compositions. Neural Networks, 119:74 84, 2019. ISSN 0893-6080.
Jonathan W. Siegel and Jinchao Xu. Approximation rates for neural networks with general activation functions. Neural Networks, 128:313 321, 2020. ISSN 0893-6080.
16

---

Published in Transactions on Machine Learning Research (10/2024)
Jonathan W. Siegel and Jinchao Xu. High-order approximation rates for shallow neural networks with cosine and ReLU* activation functions. Applied and Compulalional Harmonic Analysis, 58:1-26, 2022a. ISSN 1063-5203.
Jonathan W. Siegel and Jinchao Xu. Optimal convergence rates for the orthogonal greedy algorithm. JEEE Transactions on Information Theory, 68(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 PDFs. Journal of Computational Physics, 484:112084, July 2023.
ISSN 00219991.
Justin Sirignano and Konstantinos Spiliopoulos. Mcan field analysis of neural networks: A law of large numbers. STAM Journal on Applied Mathemalics, 80(2):7255 752, 2020.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason D. Lee. Theoretical insights into the optimization land- scape of over- paeemearaeeeri shallow neural networks. IEEE Transactions on Information Theory, 65(2): 742-769, 2019. https://arxiv, http:///////////////a/a 04926
ChaeHwan Song, Ali Ramezani-Keebya, 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 Vanghan (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 11247 11259. Curran Associates, Inc., 2021.
Zhao Song and Xin Yang. Quadratic suffices for over-parametrriatioo via matrix chernoff bound, 2019. https://arxiv,
03593
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multilayer neural networks, 2016. https://arxiv wttpp/wwwwww.w//////.a....// 08361
Lili Su and Pengkun Yang. On learning over-parameterrzee neural networks: A functional approximation perspective. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'AchéeBue,, E. Fox, and R. Garnelt (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 rate and curse of dimensionality. In International Conference on Learning Representations, 2019.
Grzegorz Swirszcz, Wojeiech Marian Czarnocki, and Razvan Pascanu. Local minima in training of neural networks, 2017. http:////wwww...ggg//////......
Michael Unser. Ridges, neural networks, and the radon transform. Journal of Machine Learning Research, 14337) 2023.
Luca Venturi, Afonso S. Bandeira, and Joan Bruna. Spurious valleys in one-hiddeen-layr neural network optimization landscapes. Journal of Machine Learning Research, 20(133):1-34, 2019. hhttss///axii:
org/abs/1802.0633
Nikhil Vyas, Yamini Bansal, and Preetum Nakkiran. Empirical limitations of the NTK for understanding scaling laws in deep learning. Transactions Machine Learning Research, 2023. ISSN 2835-8856.
E Weinan, Ma Chao, Wu Lei, and Stephan Wojtowytsch. Towards mathematical understanding of neural neaeork-based machine learning: What we know and what we don't. CSTAM Transactions on Applied Mathematics, 1(4):561-6) 615, 2020. ISSN 2708-0579.
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 406, February 2022. ISSN 0176-4276, 1432-0940.
G. Welper. Approximation and gradient descent training with neural networks, 2024a.
https://arra
org/ alg/055.2405... 11696
17

---

Published in Transactions on Machine Learning Research (10/2024)
Gerrit Welper. Approximation results for gradient flow trained neural networks. Journal of Machine Learn- ing, 3(2):107-175, 2024b.
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. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 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 H. Larochelle, M. Ranzalo, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 13003-13011 Curran Associates, Inc., 2020.
Ding-Xuae Xuan Zhou. Universality of deep convolutional neural networks. Applied and Compulational Harmonic Analysis, 48(2):7877 794, 2020. ISSN 1063-5203.
Difan Zou and Quanquan Gu. An improved analysis of training per-parameterized deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alch6-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 over-parameterized deep ReLU networks. Machine Learning, 109(3):467 492, 2020.
18

---

Published in Transactions on Machine Learning Research (10/2024)
A Proof of the Main Results
We follow roughly the steps in the proof overview in Section
Section
A.1 characterizes the critical points, constructs the complement space X and provides some
of its properties.
Section proves the distribution of the grid size limit for infinite width in Lemma 3.2
3. Section proves equidistribution in Theorem 3.3
Section proves the approximation properties of the critical points in Theorem 3.4
A.1
Critical Points and the Complement Space X
A.1.1 Critical Points
We have already seen in the proof overview that the weights critical point if and only if (k, v) for all v E X + +X, with residual k == fe f. For reference, this is stated again in the following lemma, together with a characterization of the spaces X and X.
Lemma A.1. Let be critical point 11 with cleaned breakpoints in ascending order 12
Then
(N, = 0, x = (u E (2(D))((bb) = 0, v/z. E FF, I....,....... m) (x, =0,
e Lz(D))olı, IP 1. m}
Proof. In (16]. we have that the critical points are given by the condition (K,, u) 0 for all in the span X of the partial derivatives ow, and in the span X of the partial derivatives Ōr f. Hence, it sulfices to show that the span of the derivatives matches the two sets in the lemmaa. Indeed, one readily computes
fo (N, -...b,))))
fb (n, w.
Clearly ReLU activations a(. by) span piccewise lincar functions and their derivatives w,ā(-- b,) span piecewise constants because in the cleanup before Theorem 3.4 we have already dropped all neurons with w, = 0. Finally, by the same cleamup, the leftmost breakpoint maybe inside or outside of D, but anyways, we must have v(bo) = 0 because no partial derivative has support left of this point.
Note that the network itself is continuous piecewise linear (CPwL) so that fo X and the first critical point condition
(K, v) 0, v V X
is merely bost La projection for the outer weights w,. Together with the second condition
(x 0, xEX+X
(22)
this formally matches a best L2 projection onto discontinuous piecewise linear (DPwL) functions. However, So is not discontinuous and instead we have to move the breakpoints b, to satisfy all conditions.
Recall from the proof overview that we split X + X into X and the Lg-orthogonal complement X+:
X x+ x
X X1x
Since the neural network fo contained X, this implies (S.u) = (So - (,u) = =K,,) for all X and therefore at a critical point (x, v) we have
(,,)) EEX-
(23)
Unlike the residual = fo - f, the target f does not depend on the outer weights w, and therefore the last condition decouples the computation of the inner weights b, from the outer weights w,. This will be crucial to prove equidistribution, which also depends the inner weights b,, only.
19

---

Published in Transactions on Machine Learning Research (10/2024)
A.1.2 The Complement Space X
In this section, we construct an explicit basis for the complement space X+, As is customary for e.g. finite elements, we first define suitable lunctions on the reference interval f = [0, and then use the bijective affine linear transform
i-
T₃( (b, - br- + by-1,
T hy
-I=
to define corresponding functions the interval L. We use hat to emphasize that certain quantity is defined on the reference interval.
The construction starts with the four functions
é: + R,
6(x) -x +2?
:: f R,
ò(x) = x² 2x +
(24)
:: R d(x) d(x) + d(x),
6: R δ(x) = o(x) - d(x),
defined on the reference interval î and shown in Figure 4 are defined with the affine transform
The corresponding functions the interval I,
{
To (x), EEl I.
(x)
(25)
I
extended by zero outside of I,, for any"E (-5)
(a) 5
(b)
(c) Φ
(d)
Figure 4: Functions defined 24
From or and dr. we can construct all functions X that we need for the proof of the main results, as given the next lemmna.
Lemma A.2. Let fr and dr be defined by 25 Then
h b4410"+1 e x-,
2, 2....,
Although the second derivative might seem artificial at first, the function o will be more useful than o. down the road.
Proof. We abbreviate 9r. it is sufficient to show (vr, H&) = for a basis Hs, s = O...., m of X. We choose hat functions centered at bg, i.c.
= := 0- hr Clearly di and d4 are piecewise linear so that fr. E X + and
T 1
E Tsp E lot1,
H.(1)
(z)
0
elsc.
Using the compact supports of ér, dr. H₂, the derivatives T- hy, (T= = h;,, the chain rule d" = (6" o T- and transforming to the reference interval, we compute
(er, H Hr-1) n- / 8" (z)(1 (2) da (()( +) dā = 1/') (-60 2)(1 +)) de 0
20

---

Published in Transactions on Machine Learning Research (10/2024)
and
n { 8" (t)) fr f((2 4) 0
(cr, Hr+1)
lr41
and
(0,, Hp) b, f 8" o, (x)T, (x) hrt1 / 6" o ofF -T7
1.
. (-62 2) f (62 -)
(-1) -
2) dē
=0
All other (err, H&) have non-overlgpping support and therefore evaluate to zero. In conclusion (ppr, H₂) = 0 for basis H, of X-. Together with fr E e X-, this concludes the proof.
The following lemma the cornerstone for showing equidistribution in Lemma 3.2 and Theorem 3.3
Lemma A.3. Let by, [m] be cleaned critical breakpoints
Let Ør, dr. Φr, Or be defined by
25
Then
hylf" b.)1, hy+1 drt1)
Since ó, and or are nen-nigative bump functions, under the conditions of the main theorem, one can show that her 2- "1f"" hr (f", 6r) ~ brrf",,; (with an argument analogous to Lemma A.27 Therefore, repeated application of the Lemma yields equidistribution
2- hr [1")),,()))) ~ "y" (.) = ( (r+1)) ~ 1 (11
between neighbouring intervals. However, repeated application for distant intervals 4, and I, accumulates too much error. For the main oquidistribution theorem we chain the identity of the lemma directly, which requires careful consideration of the difference Φ, dr dr.
that critical points, we have (f.)) for all X+. By Lemma A.2 the lunction hr 1y 1/ contained X+ and therefore we may substitute it for v to obtain
Proof. Recall from 23
(f. hr41 =
hr(f = hrt1 (f, D'
(26)
This shows the lemma, except that the two derivatives are on the wrong side of the inner product, which we correct with integration by parts:
hy (J. 8 --(b)) - , = -(b,) h, (b)r,
where in the first step we have used that 56 (b,-1) = and d,(,,) = & T, (br))/ -h,1 and the second step that of is zero on the boundary, by the boundary values in Lemma A.4 in the technical supplements. Analogously, we obtain
hy41 (f. bf41(f."" dh = -f(b,) - hrt &f =f(brr + 1 draidem
Plugging into 26 we conclude that
-f(b,) h, b.)1. = --((br) + ho-1 (f
which yields the lemma upon cancelling fbb.).
21

---

Published in Transactions on Machine Learning Research (10/2024)
A.1.3 Technical Properties of ér. 인r. or. or
This section contains several technical properties of the functions ér. drs Sr. o, defined
25
Lemma A.4. Let én and dr be defined by 25 Then
(0)) = 0,
6(1) = 0, d(1) 0,
o'(0) = O,
((1) = -1, 2((1) 0,
((0) 0,
d'(0) 1,
Proof. Follows directly from the explicit formulas for o and a in 24
Lemma A.5. Let or and dr be defoned by 25 Then for all x E
20
)(x) 2 0.
Proof. & and à are third order polynomials for which the lemma follows by elementary computation.
Lemma A.6. Let or and dr be defined by Then
25
h (T, 6)
hr
h?
hr
(1, 12'
(x, Q)
+
br-11
20
20
12
(1, (1,0),, h,
hr
h
hy
(T, ")),
(x, Φ)
+
b
30
30
12
Proof. For any functions 0 and @ defined on the reference interval and corresponding functions OoT, and @ $ T the interval I,, we have
(v, =h, ((0))(())))) da.
Therefore, for 0 = 1 and & = o and 3 = à we have
h
(1,6)).. hr,1, hr -33 + di
12'
(1,6)) = (1) = lrr / $3 13- 24 + i dā
hr
12
Likewise, since the transformation of f - f to the interval I, is T, we have
(T,1 (,-,,,))1 = -2, 5); = hr 1, 81(-0" + db hr
20
16682 [ -20² + 5)) di
h
"-,,,,)1. 11,(2,)) d)1 1yr
Finally, the function x transformed to the reference interval is Tr( (b, Thus, together with the identities above
br 16
by
h, + by-1-
h
h
(x, hT,, o h2 ò); + h (1, Q6;
by
20
12
12
h
(x, dr)1, (T,, = ( d) + h,bb,
12 11
30
which completes the proof.
22

---

Published in Transactions on Machine Learning Research (10/2024)
A.2 Equilibration for the Limit h
A.2.1 Results
We have seen in Section 2 that we can achieve optimal approximation rales by equilibrating the smoothness |f (z)))))))))) on all intervals I, In this section, we provide an argument that in the limit of small intervals
h + 0, the cquidistribution and the critical point conditions yield the same adapted grids. This section is
kepl informal, put provides intuition and guidelines for rigorous analysis for finite h, in Section A.3
To provide meaningful limits, consider the grid size limit
h(x) = lim mhy. m=0
where ht is the size of the interval I, that contains x and the network width m a normalization factor. On a uniform grid, this normalization yields h(x) = |DI. Throughout this section, we assume that the limit exists. We first consider the limit of equidistribution in the following lemma.
Lemma A.7. Assume that the limit h(x) exists. Let f be smooth and let the intervols be equilibrated = [[ for all r,s and for all m. Then for m + do the grid size limit satisfies
h(x) = cc)=
for some consland
This limit confirms the expectation that we want a fine grid wherever the function has little smoothness, here expressed by a large second derivative (x)) comparison, the limiting grid of the critical points satisfy the following lemma.
Lemma A.8 (Lemma restated). Let f be smooth and for every m let by, r [m]] be cleaned critical breakpoints
If the limit h(x) exists, it satisfies
b(()) = = (=))
with possibly different constant e₁ on each interval for which (x) is non-zero.
We observe that the grid size limit is identical the density of the smoothness norm equidistribution in Lemma 3.2, up to global factor each interval for which f" is non-zero. Thus, in the limit, critical points have a proper grid distribution every strictly convex concave stretch of the target function f, but may be imbalanced between these strotches.
The proof relies on the observation that in the limit the grid size satisfies the ODE in the following lemma.
Lemma A.9. Let f be smooth and for every mn let br, E [m]] be cleaned critical breakpoints the limit h(x) exists, it satisfies the differential equation
11
12
If
[a()) = (()))3""())) -
The proofs of all lemmas are given in the following section.
A.2.2 Proofs
We first prove the limit for norm equidistribution.
Proof of Lemma 3.2 Since f is smooth, we have
(1
5/2 hr f (x))2)) dx)
-
m 5/2 (llytt) = (m/,,)8/2 5/2
('()) "
23

---

Published in Transactions on Machine Learning Research (10/2024)
Since by equidistribution the left hand side is independent of the interval I, containing z; the right hand side is independent of a and thus
(( const
h(x) const (x))
which concludes the proof.
To prove the analogous result for critical points, recall that from Lemma A.3 that (f 6r)1, hr+1(f 0041) We show that in the limit this reduces to an ODE for the grid size h(z). To this end, we first need some technical lemmas.
Lemma A.10. Let be smooth and ér, o, be defined by 25 Then
1
lim (v, 10,61)1 = v(x),
m- hr
12
1
lim
(v, 6 - -dr)s,
v' (x:).
h2
60
Proof. Since v is smooth and o, non-negative (Lemma A.5 by the mean value theorem and normalization (1, (1,0).. = /t/12 (Lemma A.6 we have
(v, 6r)1. = v(E) h, (1, át), = u(E)
hr
12
for some & E Ip. In the limit m oo and intervals I, that contain x, this yields the first formula of the lemma.
To show the second limit, define
(xx) / é(v) -(y) dy -
1 2x 2/ //(0² -2x x2)
and 6, == o (T,)-1 Then V = Φ b = (grr 2h 11 Furthermore, & has boundary values
(()) (1) = 0, is non- non-positive on and
hr (1, 11, = hr (b()) dā 60
by transforming to the reference interval with T, and TV hr. Using integration by parts, & S 0 and the mcan value theorem, it follows that
(u, b, 2r)1. = hr
(v' - 2r)1. = -d( hr (1, 1.),) = -'(() 60'
h?
Taking the limit m + co, this yields the second formula of the lemma.
Next, we show that the grid size limit satisfies the ODE in Lemma A.9
Proof of Lemma A.9 By a telescopic sum, we have
h, b.)1, hr,ff, ---
Σ
helf" hall",ba) -h-1(f" 2
bmr+1
24

---

Published in Transactions on Machine Learning Research (10/2024)
Since the intervals I, originate from critical point, by Lemma A.3 have he-1(f", 2x-1)1e-1 (f dahT and therefore
hol b,) -
(r" ée)s, hr
Σ
hxls" 6x) ho( du)
k=++1
hnlf" , ,6%% -Qx)sa
Multiplying by m² yields
(mh))² (S"""6" (mh,)² (1"",r)) =
(mhs)) (8" 1r iu)
hg
l12
k=++1
By Lemma A.10 in the limit m + oo this converges to
1 {()))(((>>) -
12 h(0)
60 J
{(=)3
12
where we have used that the terms in the Riemann h, at the end converges to dz. Multiplying by 12 and differentiation with respect to yields the lemma.
constant each interval I, that the extra
It remains to solve the ODE in the last Lemma.
Proof of Lemma 3.2
A.8 We abbreviate g == f" By Lemma A.9 the grid size limit /t satisfies the ODE
[h" = 1 hh
5
which is first order linear in &2, whenever g(x) 0. To solve it, define the integrating factor μ by the ODE
gp' 5 p
with the explicit solution
1² g
gu -
In(n)) = - In(g)'
1 = 11/5
/ 5
up to global multiplicative factor. Multiplying the original ODE with μe, obtain
1 [R - --2 -
113 g) u 1² gp'
(1 gul"
Hence 122 gj is constant. Plugging in = f" and the explicit solution μ 1/5 yields ( = c for some constant c. Solving for h yields the lemma.
A.3 Equilibrium for Finite h
In this section, prove the main equidistribution theorem, restated here for convenience:
Theorem A.11 (Theorem 3.3
restated). Let 0 be critical point (11), with cleaned breakpoints in ascending 12 For r, E m let I = fr.r + l.....s} be set of consecutive neurons with Dr == Ukez 4x
order and
( [e, het 1-1 (1 (I,,(ees) } < C min [f"(x) max +
(27)
zElxt
for some < 9.P S oc and some sufficiently small constant C 1, k E DI we have equidistribution
independent of f and by Then for
|1" II (''le))))())
25

---

Published in Transactions on Machine Learning Research (10/2024)
A.3.1 Notations
Throughout this section, we abbreviate
(o) = 4 ér)
(.(o) == h (u, Φr)
(28)
(x) = h, (ve (r)
ā.( h, 2r)1.
(29)
and in case f" even shorter
á = (1))));
à, a, (s"),
n. = a,())
0 5y:=0,(0 a,())..
(30)
We will also repeatedly use the integrating factor
a,
=
(31)
analogous to the one that was used in the solution of the ODE from Lemma A.9 in the infinite width limit.
A.3.2 Overview
Recall from Lemma A.9 that for m + oc, the grid size limit h(x) and the integrating factor u(x) satisfy the two ODEs
1 h22 1""
1
f" - 8"
5
respectively. follows that
[h2 "wll'<1''"'> [h' 4 h
5 112 1 1"
(32)
where in the first step have used the product rule and in the third the two ODEs for h and p. For finite hr, we follow a similar argument:
Lemma A.12 replaces the derivative on the left hand side with a difference and the zero on the right hand side with perturbation terms (7) (IV) that we prove to be small subsequent sections. As result, the terms hā are almost constant between neighbouring intervals.
Lemmas A.13 and A.14 bound error accumulation when comparing hāa,4, = |1 o.}$ over multiple intervals, resulting equidistribution of this quantity.
Thcorem 3.3 then follows from [h a.Ja || by Lemma A.27 the end of this section.
A.3.3 Proof of the Main Result
The assumptions for the main theorems confine the results to regions where f is convex concave. For the time being, make this assumption explicit by assuming a, 2 0, which will be removed later.
Lemma A.12. Let br, r E [m] be cleaned critical breakpoints
12
Let ār, ā, and μ4, be defined by
28
31
ār 2 0 and a = 1155. Then
12-10r41/4-111 - -h, k2 (I) + (IT) (117)+ (IV),
with
(I) 1 [ār++ 1 + 0z alār+1 ar1lur+1
(1I) = [h2 - 1 1
(111) a²h,a0 |ar+1 arl 12
(IV) a02//041 az Rr + h Ry Ry.
26

---

Published in Transactions on Machine Learning Research (10/2024)
and for some 0 &r <
R2 = a((x 1)(5,d, + {t)ā,+1) [ar+1 ā.
Proof.
We mimic the steps in the motivation
32 starting with the product rule:
+++10+1//++ - h, 1 1, n,,arlur41 [6r]
(33)
The next step in the motivation is to invoke the ODEs for and μ. The former based on Lemma A.3 which we can invoke directly (twice the second step below) together with the observation that K, = hf br),,, etc., to obtain
122 44 4r+1 hā = (h2 dr+1 1zāaz) + (R74 är+1 -(āax)
(h dr+1 1 (h, - hl.a))
+++11++1+ + hīāx..
For the second term, we don't invoke the μ ODE directly, but instead compute the derivative, rather difference, using the explicit formula 14, a.. Applying Taylor expansion for 2a obtain
pr+1 M4 0,+1 ar -aa, -ar+1(rr+11 - -a,] Rr
(34)
and Taylor remainder
:= 1)(,,a, (1 (1-Ex E.) a-- Pla,11 a.,
(35)
for some 0 &, < 1. Plugging these identitics into (33] and using 0, Mr, obtain
1 11410441/441 h, 0r++ h + ( [ār4] ā. Ry loxā [ūr+1
= @1 + h h. + 1r - ār] + 1, R,
In the continuous motivation 32 the terms on the right hand side cancel to zero. the discrete case, we rearrange the right hand side into summands that we prove be small later:
h2 11+41 12 (K?+1 - 12
+ +1,(ār+1 + āxlur-1 + ah, (ār+1 - arl
ahl/lu411 [r][ār+1 ār] + 12, Rrr
11241 h22
+ N2(ār+1 1 + ã + a0ar41 o, [rr]
ahh(uu+1 - ,, lār+1 ā,} + 1² Ry.
We will see later that the third but last and last lines contain small perturbation terms and the second but last line is zero for f" p (Lemma A6. and close to zero for general f". For now, we eliminate the difference pr+1 - pr by Taylor expansion (34), (35 to obtain
ah; anş url(ar+1 - a.1 = 222aa Taap--(@r4a (0r+1 - a,}² + ah - a,
and therefore
h h24110411041 h 22 = [h? - h2 2r1111/1111111
+ 12 12, + âs + aldr41 dr]]pr+1
a² 22a 12 (ar41 - a,1² ahl(ar41 - a.]RR + 12
This concludes the proof, upon reordering terms.
27

---

Published in Transactions on Machine Learning Research (10/2024)
The previous lemma shows that hearpr is comparable two neighbouring intervals I, and 1,+1- Applying the argument repeatedly, allows us to compare n, across multiple intervals. The following lemma bounds the compound error.
Lemma A.13. Let zn E I and hy 2 0 for k. = m. Assume
1ak+1 2k S calhx + h6+12k47 2k+1]
and the conditions
1 cali&
m
1
1 + 2cdCa L hk Cd.
$ 1 20d
hg
2'
C2
for the two constants Cds Cd 2 0. Then for all r, [m] we have
Ca 2r S 2o S Ca
Proof. We first show that 2 does not change sign. To this end, assume 2k-1 2 0 and 2k S 0. Then, by assumption
|ek+1l + l2 S ca[ha|zk| + ba+1|2*+11 S zk+1| + |zk|s
2
which directly implies 2ạ = 2h+1 = O. Therefore, in the following we assume without loss of generality that 2 2
By symnetry it suffices to show 2s Cazy. To this end, assume without loss of generality < and by induction that the statement is true for all I k I s-1 1. We show the statement for & With telescopic sum, we have
2k+1
24 S
heok + ha+1 S 2ca Σ
hEEk
k=r
k=r
k=r
2cd
hk
max (2,,
max 2 S 2cd
Σ he
max Cazr J.
rSkss
where in the second step have used the first assumption of the lemma, in the third index shift the Me412444 summands and in the last the induction hypothesis.
We proceed with the two options for the maximum separately. In case max(zs, Cazr j = we have
24 2y S 20d
Σ
hw
2
2a
20d
Σ hE
2r S Catei
where we have solved the first inequality for 2, and then estimated the bracket by the given assumptions. By the same reasoning, in the case max(za, Cazrr Oazr we have
24 2r S 2ca
Σ ho
Cdzr
2g 1 2caC's
Σ hw
2x S Catee
Thus, in any case we have 2, S Cazy and the lemma follows by induction.
Combining the last two lemmas shows that 12 is equidistributed across multiple intervals I,.. This requires to bound the terms (7) (TV), which technical and deferred to Section A.3.5 later.
28

---

Published in Transactions on Machine Learning Research (10/2024)
Lemma A.14. Let by, [m]] be cleaned critical breakpoints
11
12
Assume that
7 (Ip()))))) Net (| (eg((ee))
max h (
min [f"()))
xEl++
for some < q.p S do and some sufficiently small constant >> O, independent of f and h,, and r contained in some consecutive indices C. [m]. Then
h2 Talus h1.a, Mr
for all r, I.
Proof. First note that by Lemma A.20 in the technical supplements we have a, ~ ar+1 so that they cannot change sign. Upon eventually replacing f with -f, we may assume without loss generality that a, 2 Then, the result follows from Lemma A. 1.13 with the choice 2 hL To prove its assumptions, we have to show
12 ār 11 Ma S ca(M,a, Mr Mhr + ca
for some sufficiently small ca so that the lemmas restrictions the constants satisfied. By Lemma A.12 we have
h2 1 h, -1))
for some terms (4) - (IV) that are bounded by Lemmas
A.23
A.24
A.25
A.26
These lemmas require
h2 "1f (11 1- (La(te))
C
min (x)( 2ef+
hr+ (
min zEi,
(x)),),,
possibly with different 1 p. S oo and for sufficiently small constant C. This matches the given assumption and concludes the proof.
The technical Lemma
A.27
below shows that h² [aal (l which allows us to conclude the proof
of the main Theorem 3.3
Proof of Theorem 3.3 tribution
From Lemma A.14 together with the definition 14, 14: |a,1-1/5 we have the equidis-
122 02 ~ n2(
and by Lemma A.27 we have the equivalence
h31a,1 t [h la |
Combining these equivalences, the norms 11 are equilibrated and the result follows.
A.3.4 Technical Lemmas
This Section contains collection of technical lemmas that used to bound (T)-(IV) in Lemma A.12
29

---

Published in Transactions on Machine Learning Research (10/2024)
Lemma A.15. Let ér, er, कr, or be defined by 25 and by 28
Then
hr
(,(1) 0,
(x)
60
1
hr
(,) = 6'
(x(x)
+ 1
12
6
h + hy
(1) 0, (1) = 0,
(x+1(x) - (x)
12
Proof. From 5. 5. dr and Lemma A.6
we have
hr
(1,0r)s, = =(1, (1,0r).
0,
12
12
h
hr
h2
hr
h
(r, br)1. (x, drli.
b,
20
12
30
12
60
Dividing by hy and plugging in the definition of är on the left hand side shows the first two identities of the lemma. Likewise, with the definition o, or or, have
hr
hr
hr
(1, (1,0)),- = (1, (,) (1, (1,
12
12
6
h1
hr
h
hr
h
hr
(z, (c. (ar, 6r), + (2,, b.),
by-
by
by
1
20
12
30
12
12
which shows the second two identities of the lemma. It follows that
h (1, 2r+1) - (1,
0,
6
h,+1
1
hr
h (z, 2rt1) hr (x, (r.
by
bp-1
12
12
hp+1
hr
hr
h + hr
12
12
where we have used that by - b,-1 hy Again, plugging in the definitions of the left hand side shows the remaining identities of the lemma.
Lemma A.16. Let ä, and å, be defined by 22 and a = -1/5. Then
+ +,
+ (1)) a, (p) = 0.
for all linear IP.
Proof. Since (-) and (-). are linear, it suffices to show the lemma for p = and I. For the former by
Lemma A.15 we have
(1)(1) - = 0 + - 0.
For the latter, we have
hr+1
hr
h + hr
(x+1 (x) + a(ār+1())) ār(x))
60
12
because a 1/5..
30

---

Published in Transactions on Machine Learning Research (10/2024)
Lemma A.17. Let or and or be defined by 25 of the s-th derivatives are bounded by
Then for any p oo and integer 2 0 the Lp norms
16 [1,((-)) ~ h
|1 (lp(T.) ~ h hē²
with constants that depend on p and s.
Proof. On the reference interval I, have 11 form some constants that depend on p and 8. Hence, we only need to check the scaling for the transform to the interval I, by integral substitution:
12,,1,) = = o (x) dx = n// f, (6(8)) dē ~ hT
Taking the p-th root shows the claimed equivalences for &r. The result for di follows analogously.
Lemma A.18. Let (v) and (v) be defined by 28 and 1 S S 0o. Define the joint interval J = I 1,41 of size hy4 = |1++|. Then
1. [,)( < hr [1olL,,(,.)-
[ar( S hr ||00 [xp(T.)-
3. (ar)) s hr+ ( + hr || [10'lles().)))
4. a,(u) 2 minser, u(x) and (,(v) 2 1
12 min v(x) for D E {á, à}.
Proof. Throughout the proof define g by 1/p + 1/q so that -1 + 1/9 = -1/p.
1. By Hölder's inequality and Lemma A.17 have
a [v]] = h1 (v, Or + dr)1. S hr "or''lllll, Illle, + )rlle,(1.))
$ h || | < hr / [Illle
2. By Lemna A.15
we have (,( = 0. Hence, c is the best L, constant approximation to e, with standard direct approximation inequalities
[11 in the supplementary material), we obtain
[ā,(u)) = ( - c)1 = h (0 e, or - -dr)
< 1 - cl (( òrlle,(1.) S h 1,"1l,lo''ll,,,,
< hr レ
3. By Lemma A.15
have ār+1 (1) 0. Hence, if the best Lp constant approximation to on the joint interval l+t = 1,11 U I,, we have
(1) - a,(1) = | (v c) - ār(v -c]
< 1 (1 2r+1)) trsal + 1- c, 1.)1.1
31

---

Published in Transactions on Machine Learning Research (10/2024)
With standard direct approximation inequalities the second term as before:
(41 in the supplementary material), estimate
h (c0 c, 6,) - h 110 <ll cl
0rlle.(1.)
hp 110 cll,,(1...)) ) ho by+ 11
s shrthr || (epp(to))
With analogous argument on the interval I,+1, we obtain
(0)+1(0) ār(x)] S lirt (1i43 + byr nr+) 1 1elle,
By Lemma A.5 the function o, = o, + Φ. is non-negative. Therefore, by the mcan value theorem for some & E Ir
1 (v) = hi (v. Ør)1. = li (E)' 2 hw min u(x) (,),,, min e(x)ā,(1) min o(x), sel.
zer.
6 sel,
where in the last step we have used Lemma A.15 Analogously, one can show that á, (x) 2 12 minser, v(x) and (v) 2 12 minser, u(x:, using that (,(1) 12 by normalization Lemma A.6
Lemma A.19. Let b,, E [m]] be cleaned critical breakpoints
11
Then
12
[f'(x)] Nr+ (1Z + 2 b) I1. (Le,))))))))
|0 13 min
Proof. From Lemma A.3 we have hy (f", br)1, hrt1(f" drtz)emn or equivalently h²dar 1 and therefore 12+1 12 /1, This implies
[ dr
1 [ār+1 - 4r1h?
h h =
h
@r+1
Cr41
We first bound [àr41 á.l. To this end, note that
(1) 2rt1)) (1,
12 =0,
12
where the second but last step we have used the normalization properties Lemma A.6
Hence, we obtain
là árl S hy+ ( + hr |l ||(")11,,())))
with a proof that is identical to the same bound for (ār+1 - ārl in Lemma A.18 Next, we bound
12
6,41
min [f"(x)
by Lemma A.18 We conclude that
12
hrth? ( h + hī |1 (1
112-1 - 47l5 min (x)
32

---

Published in Transactions on Machine Learning Research (10/2024)
Starting with h h2410r-1/á, instead of h2++1 hedr /å,t/ár+1 at the beginning of the proof, obtain the same inequality with the term h replaced by h/41- Thus, we can simplify to
12
Mr+ hytt + 2- :) 11 (1p((t)))))))))
1 h
min [f"()))
which completes the proof.
Lemma A.20. Let b,, E [m]] be cleaned critical breakpoints
11
12
Assume that
K+ 1- 1= (1,(1+4)) S C min (z)
sEl,-
for a sufficiently small constant C independent of I and hr Then
hp hy+1,
a, 0y+1,
Pr ~ Pr+1-
Proof. All equivalences in this lemma are based on the following observation: For two numbers a, b E R we have
1 za 5 b 2a.
la- bl = max{ |6}}
(36)
First note that and have same sign. Indeed, if a 2 0 and b S 0, we have
|a| + |b| S max max[ [8|} Σ 2 (lal + [b]),
which implics b 0. Thus, without loss of generality assume a, b 2 0. In case minfa, b} a, we have
3 2 0, al a
b bb <
1
b bb] N a b6
a 2 00 2 2
(a, b} = b, analogously we have } < a S 3b. Rearranging this is equivalent za < 2a. Using the worst of the two cases yields the claim.
and thus la < < 3a. In case min
We now turn the statements of the lemma.
1. By Lemma
A.19 and the given assumptions, we have
12
Nrt (h44 hr 2- 1|5 (eeltre)))
12-11 n21 < min [f"(x)
12
122 My " (1"(lep(re)
S minzel14 [x"()))
< schh < maxthry hr Hhy
for sufficiently small constant C. It follows that
1:2 1 12
1
lb hpl =
- max(hr. hr413
hr+1 + hr
and thus with 36 we obtain h 5 hr+1 S hr-
33

---

Published in Transactions on Machine Learning Research (10/2024)
2. By the first part of the lemmna have by hr+1 and therefore hr h/ h S h Thus, by Lemma A.18 and the given assumptions we have
[a,+1 arl S chr+ ( + hr h) II lE,(trn) S ch (1 S cC
min (f" - dr.
sel,
2
for sufficiently small constant C. With (36) this implics 2a, ar+1 S ar.
Since H4, = |a,1% the previous part of the lemma directly implies H4 ~ p4++1
Lemma A.21. Let PEP-- 1
N be the best linear approzimation of fr in Lp some interval Then for 1 S xo
J 3 I and ā,, är be defined in. 28 30
a. (P) h | [)))
J 1.-á [ 211 (1.
Proof- Let 1/p 1/9
that -1 + 1/9- -1/p- Then
a., - ā, (P)l = (ā" - P)| = 11, 15" -P, + -dr)1.
h 1 (I),,(J)) 11,, - 2. (1l((1)))) S 1 (
$ , - (|(())) [1e,(5)--
The result for a follows analogously.
Lemma A.22. Let ā, (v) 2 0 and for some 3 E R assume
1 1 s C min [o(x]]-
welrt
Then
min |u(x)) ar.
zEI.
With the given assumption, this implies v'(x) = 0 on 7, that is constant and thus zero everywhere. In this case we have (,) = and the result follows.
Proof. First assume that min |m(x)) 0.
If min |o(x)] * 0, the function u(z) does not change sign and since a,((v) 2 0, we must have u(x) 2 0
for all r E I, because or 2 0 (Lemma A.50. Then the result follows directly from Lemma A.18
A.3.5 Bounds for (7) (IV) in Lemma A.12
In this section, bound the terms (I)-(IV) in Lemma A.12
The bounds are of the form (I) (IV) [hza,pr/h, h,,,, all with one extra factor hy. which allows to control the cumulative error for equidis- tribution over longer distances by Lemma A.13
Lemma A.23. Let b,, E [m]] be cleaned critical breakpoints
2
and ā,,, 0,+1 0. Assume that
h
11 I
min [f'()) xeIrt
for some consland C independent of f and hr. Then
(I) = h2(ā141 + ãz + a(ar+1 - ar11m441 S Cihāa, |h, + [h? ar 14444/2
34

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. First note that by Lemma A.16 for all P IPl
we have
(p) + (P) + alā a,)) 0.
Hence, in case mingel,, [x"()) = the given assumption implies f(4) = 0 so that f IPl and (1) = 0. case min [x)( + 0, follows that with a, - ",( etc.,
(1) h2(ār + āx + afār+1 ar]]ur=1
h2(ār+1(P) + (x(P) alar+ 1 (P) or (P)llur+++
(37)
= -,](a++1 P) + āz( - P) + al0,+1 (8" P) a. PPilp++t-
We choose the best Lp(1+) approximation for P and estimate all terms separately. First, we have "Laals" Plus= = 1 lax āz (P))pR S 2 hr 2- [1](0))12,(,-)1
I Ch min [5"()))rr S hh, = C(h -R zEIr+
where in the second step we have used Lemma A.21 in the third our assumptions, in the fourth (f S a
analogous to Lemma A..2 with min If" (z) # 0 and in the second but last h, ~ hr+1 by Lemma A.20 Analogously, we obtain
a (s" - P)uR & Ch,āa,
as well as for all other combination of indices r and + because H4 ~ pr+1 by Lemma A.20 Using these
estimates for all four terms in 377, we obtain
(T) S C [( + (1 4111
which shows the lemma.
Lemma A.24. Let by, E [m]] be cleaned crilical breakpoints
12
and 0,41 2 0. Assume
1 "1 (e, SC K,
min I (z) wet,
for some constant independent of f and hr. Then
(II) = -h 21 & Ch ā MMttrtlhtt
Proof. By Lemma A.19 and the given assumptions, we have
|2211 121 S
2- 2- mingel++ [f"(x)] hr+ (1 + hr
12
|15 (n((oo)))))) S Cha
where in the last step have used h,41 hy by Lemma A.20 From Lemma A.18 the given assumptions, and [x)( < dr+1 (Lemma A.22), we have
|a,41l $ h (1,,t & Cha min 1f"(x) $ Ch Ch:41ar4 ar+1 selet
Combining these two inequalities yields the lemma.
Lemma A.25. Let by, E [m] cleaned critical breakpoints
and a 2 0. Assume
- h+t [15" C min
[f'())
aet
for some constant 0 < C. < independent of f and hr. Then
(ITT) a (0rt1 -,,²² x Ch
35

---

Published in Transactions on Machine Learning Research (10/2024)
Proof. From Lemma A.18 the given assumptions, hr+1 hr (Lemma A.20 and [f) S a, (Lemma
A.22
we have
To++1 arl S 1 ( + n I[(")l) & C min (f"()) & Ch.
+el++
Thus, with ,4, = 07 we have
(ITT) = a [ār+1 - -
a C S Chia,a, = ur
This completes the proof.
Lemma A.26. Let by, [m] be cleaned crilical breakpoints
11
and Cr 0y 0. Assume
トー h II S SC min [=)l
aet,
for some constant S C S independent of f and hr- Then
(IV) = (ar ar + n, Br S (hrārppr)h.
with Ry deftned in Lemma A.1%
Proof. Recall that R2 is defined by
R = a(a - 1) + (1 & ),)++11 2 - a,}
for some 0 < & < 1. From Lemma A.18
the given assumptions, hr41 ~ hr (Lemma A.20
and [s) S a
(Lemmaa A.22). we have
Jā,-1 - arl S hr+ ( (
+ no tr+t (1 S Ch min (f"(x) & Cha
aElet
From Lemma, A.20 we have ār ~ ārt1 and thus
E, + (1 - (x) ~ ar.
Combining these estimates, with 0., we obtain
R, S Kā - 2C S Ch
well
12 - a.JR, S Since C' S 1, we have C²2 3
S (h
C²,0² < C, which proves the lemma.
A.3.6 Norm Equivalences
This section contains the equivalences of hifar and Tpp norms.
Lemma A.27. Let < S do and 0 < S oo. Let P E To be the [T, best constant approzimation of some function g and assume
h (0 S O min 19(x)
xElr
for some sufficiently small constant C > independent of f and hy Then
1. (,(9) a. (P).
36

---

Published in Transactions on Machine Learning Research (10/2024)
2. [99lle((1)) (l))) (lallz.(T.) ~ h3 a. (g)l-
Proof. Recall from the proof of Lemma A.20 that for two numbers a, b have
S max b}
b.
(38)
1. In case ā, 2 0, by Lemma A.21 and [(()] S ār (Lemma A.22 we have
< hr 1- l1 (1,)) S C min sEI
(g) - ā, (P)
(g())l Ca,
For sufficiently small C, with 38 this implies (g) ār (P)). The case ār(g) follows by replacing g with- -g.
We first consider the case S < co. Using direct approximation inequalities in the supple- mentary material), we have
||lo|l,,(,)) - S 11g Pl),,())) S hr 1+b-1 |1 (1))lle((1))
min [ø(x)) sc C// (o(x)) de s (1 set
< Chă
which implies | ~ [Plll, with
38 for sufficienlly small C.
In case q 1, by Taylor's theorem, we have u² 1 (&u + (1 E)v)9--(u for some < With [0(x) and == |PI. this implics
/ -(x))1-1P(a))) dx
119112 |1P111,
/ (((()))((z)) - -[- [P(x)] de
< min [o(z)) Pl)z)((.) zer.
min lo(x)) 1- |6g - Pllc,(1.) aer.
< min |x(x))=>1<> 2- | (1,,()))
zer.
C min (g(x)|/~\//,> min [x(a)
wel.
sel
Ch, min !g(x))
sel.
s sc ((())1drr
C11g(())11
where in the third step we have used q - 1 < 0 and that P= P=g(1) IP| > minzer, Ig(x)) for some n I,, as can easily be seen by by first order optimality criteria and the mean value theorem. In the fourth step we have used that || (1,)) I hr 1- #1|- |1,, by Hölder's inequality and in the sixth the given assumptions. Again with (38) this implics llgll L. [IPIIL,(..) for sufficiently small C
and thus the statement of the lemma by taking the q-th root.
37

---

Published in Transactions on Machine Learning Research (10/2024)
3. We first show the desired identities for P instead of g. Indeed, we have
[ = h, Pl
1 (P)= = - [, (P. 6.)1
12 1 P.
With the first two equivalences of this lemma,, this implies
(1. ~ [|Pll,,(a.) = h |P| hy (a,( 1+12,(1)
which concludes the proof.
A.4 Approximation
In this section, we prove the main approximation result, restated here for convenience:
Theorem A.28 (Theorem 3.4
restated). Let 0 be critical point (1Ip, with cleaned breakpoints in ascending order 12 For r, (2...., m., let I = fr, + 1.....s} be set of consecutive neurons with DI == Ukez Tk and
max 1 | lkt
(1( [p(()))); lxt |1 }
SC
min |5"
(39)
xElx
for some 1 <...P and some sufficiently small constant C > 0 independent of f and hy. Then
life flle2(D2) & | ( (D))
(40)
Since we have already established equidistribution in Theorem 3.3 the approximation results is standard.
Proof. We first split the L2 norm
llfe fl fo)))(z)) = Σ llfo fllia(1.)
ret
Σ rET
[lfo fll (2
llfe flliz(1.))
rET
SET
where in the last step we have inserted an artificial sum for later By 22 and the discussion thereafter each interval 1, the neural network is best linear approximation and therefore by standard direct approximation results 41 in the supplementary matcrial), we have
32+ 1
[ 112
$
By Lemma A.27 have
h $ 1 ~ 18th,,a,11
| ~ 11
L2)o(1))
and therefore
flfo - f1
11 Paspo(t))
I
PET
SET
38

---

Published in Transactions on Machine Learning Research (10/2024)
As side remark, we could have used llfe fll & |f mg 2 (Fa)(()))) directly if we would use Besov norms. Anyways, note that the sum depends on 8, but the summands depend on r, which we fix with equidistribution (1)a())) ~ (a)stt))))))) from Theorem 3.3 Then
[ (DL
(L))(L)
rEI
BEI
Σ
(D))
PEI
f
Z
which concludes the proof.
B Technical Supplements
B.1 Besov Spaces
For integer 2 0 and 1 1 p 00, Sobolev norms are defined by
( = Σ (P
(fW = [1 (2((D)
r=0
For Besov norms, define the difference operators (z) f(+ f(x) and A = A extended by zero case E D, and the r-th order modulus of smoothness
w (S, 0p = sup | |
Then for 0 <.g.- < oo, and the smallest integer r 8, the Besov norms are defined by
dt ! MB; == [1.00 (1 (f, 4)l
|| || = (D) -1/ +
1
See DeVore & Lorentz
(993)
DeVore
1998 for details.
B.2
Direct Approximation Estimates
For the best Lp approximation with polynomials pr-1 of degree at most r on interval it is well known that
inf |l. - pll pl),, $ pEPr-1
(,,
(41)
for all >>>0>> 0 and 1 1 s.9. with + 1 0. See c.g.
DeVore 1998). (6.9).
B.3 Main Results with Besov Norms
In the main Theorem 3.4 we use the Sobolev lype norm ()))),,, which is unusual for := 2/5 < 1. This is permissible, because the assumptions (13) requires higher weak derivatives in regular 4p norms with I p co. this section, we consider a similar result in Besov norms. These allow a larger range q.p in the assumptions. Up an arbitrarily small discrepancy in smoothness, the approximation bounds use the same norms than classical adaptive approximation in 5
39

---

Published in Transactions on Machine Learning Research (10/2024)
Theorem B.1. Let 0 be critical point 11 with cleaned breakpoints in ascending order 12 For 7, E (2,..., m) let I = fr, 88 be set of conscculive neurons with Dr = UKez Tx. and assume
:
(A (lottte S C
min ((4]f)x)).
(42)
kk+
1f (3
S
min
[f*())) #
(43)
=Elx
11 15" SC
min 1f*( * 00
(44)
zel++
uniformly for all t > 0, o 2/5, some 1 S os S 0c, some
s s xo, some $ S q S oo and a sufficiently
small constant C > 0 independent of and hg. Then
llfe fll S 2 (1
for every s
The result is proven analogously to Theorem 3.4 with few small changes that point out in the following.
Proof.
Assumptions: Assumptions
43
yield
$ k+
|1"
1- B3 M) Mat "0"""ll1l,,,a < C min [/"(x)) #0, #EP
max
analogous to 13 with Sobolev norms replaced by Besov norms, which allow the larger ranges & S p S 00 and S q S so. Reconsidering the proof of Theorem 3.4 the non-zero condition on the Then, we replace the use of the
left hand side ensures the second case in the proof of Lemma A.2 12 approximation inequality
41 with
inf II C---PlL..c PEP
with > 0 and r - 0, which remains true in case < 1, see c.g. DeVore 1998), (6.8). We make this replacement in the proofs of Lemmas A.18 A.19 A.21 and A.27 where we obtain minimal p. if we approximate in the L norm after applying Hölder's inequality.
2. Conclusion: By assumption
42 and Lemma A.27 for any p 00 and <<3 by have
h Wr (J, (g ~ he wr (S.O)
1 h I [BBB),,
1 1 ((BB(LL)0))
For 1 1s 0o, is well known that Sobolev and Besov spaces are closely related. Using this the second step below and Hölder's inequality the first, we have
(l")),, & hr "I h &
Plugging this into the approximation bounds of Theorem 3.4 we obtain
fe fllr,(Pz) S [Z] -1 f11"" (Da))(D)) S - (flgg(
for any s < 2, which concludes the proof.
40

---

Published in Transactions on Machine Learning Research (10/2024)
B.4 Networks in Inner Weights
In this section we prove Lemma 3.1 Without loss of generality, use the domain D = show an abstract characterization of critical points, similar to the proof sketch in Section 4 Lemma B.2. For an arbitrary function + fo E Lz(D), the weights E R are a critical point of the loss Ilfe ( if and only if
1-1 We first
(fo f, u) O,
v E span E [m]}.
Proof. The critical points are given by
(Jo S.0, = 0, r [m].
Clearly, the condition the lemma implics the critical point condition. In the other direction, taking linear combinations of the critical point condition directly implies the condition of the lemma.
Proof of Lemma 3.1 We first show that fw,ya and fw.b represent the same functions and then relate their critical points.
1. Construction of fwab We use the property (ar) (x) for all 2 0 of ReLU activations to rewrite FW,VBB as
Fw.YB:== == Bo + Σ (.,((B)) Wox +
Σ W.
sign(V.)<:
B,
[V.
V-=0
Wr,V+
This is already in the same format as fw,b: except for the term (V,) inside the activation. We can easily eliminate with the formula.
x(-x+bx + = o - b) -
(45)
and obtain
Fw.yn:= = Bn + Σ (Bo - Σ
ΣW.B, W.B., ( Σ V,co
Wo
w.lv%
x+
W.IVolo
B, V
V.=0
V.<O
Wr.V
after rearranging terms. Note that the first two parenthesis are constant and thus, we can find fw,b by matching terms. The last formula also shows that the breakpoints B,/V, for all with nonzero W, and V,,
2. Critical Points:
Let Fw,V be critical point and fur be the corresponding network constructed above. We show that the latter is also critical point for optimization of w and b. To this end, define the linear spaces
Xy == span( D {w,, b, [m]]. De {Wr, V,, Br), r [m]].
Xp == span
Since f..B Fw.VB, by Lemina B.2 it suffices to show that X₁ C XF. First note that
Ob, = Üz, Fw.VBB X
Ow, Sw.b I = Ow, FW.VVB Xr.
For 0, have
B, V
1, [V/]" o (VrI - B.)
1
E span
span (dB,FW...B... Fw..B,. Fw..B. C XF.
41

---

Published in Transactions on Machine Learning Research (10/2024)
where in the first span have used 45 if V, < 0 and by construction we know that Wr, V, # 0. Analogously, we obtain
Br Vr
Sm = w,o x
E span (1,0 - B,)) = span (0n, Fw.v.n, Sn, Fw...) c Xr.
Thus, partial derivatives of fwi are contained in XF so that X, C XF, which concludes the proof
42


Reviews:
[{"review_id": "xP4iIHWgdD", "reviewer": "Reviewer_Pdkp", "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": "I appreciate that authors provide explanations and context from approximation theory. I think these parts substantially increase a potential readership of the paper and advise against removing or altering them. Overall, I find organization of the paper to be clear enough for the reader with modest experience in approximation theory.\n\nThat said, in my opinion some explanations and the framing of the main results can be improved. This is further explained in the next section of the review.", "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": "Authors consider a $D=1$ approximation problem with ridge function of the form $\\hat{f}(w, b) = \\sum_{r=1}^{m}w_r\\text{ReLU}(x - b_r),\\,w_r, b_r \\in \\mathbb{R}$ adapted to the setting of gradient-based method applied to $L_2$ loss $L(w, b) = \\left\\\\|\\hat{f} - f\\right\\\\|_2^2$. More specifically, they argue that gradient-based method introduce small adjustments to the parameters until they reach critical point $w^{\\star}, b^{\\star}$ with $\\left<f -\\hat{f}(w^{\\star}, b^{\\star}), \\partial_w \\hat{f}(w^{\\star}, b^{\\star})\\right> = \\left<f -\\hat{f}(w^{\\star}, b^{\\star}), \\partial_b \\hat{f}(w^{\\star}, b^{\\star})\\right> = 0$. So they study how the approximation error scales with the number of parameters at a critical point specified above. In this setting they show that for “good” critical points error scales optimally with the number of parameters. “Bad” critical points exist and may have an arbitrarily large error that is not reducible by gradient-based technique alone. A condition is given that defines a “good” critical point and an argument is made about what may constitute a “bad” critical point.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested Changes\n\n1. Authors consider $\\text{ReLU}$ activation function that has very useful property $\\text{ReLU}(ax) = |a|\\text{ReLU}\\left(\\text{sign}(a)x\\right)$. It seems to me that the space of functions $\\hat{f}(w, b) = \\sum_{s=\\pm 1}\\sum_{r=1}^{m}w_{r,s}\\text{ReLU}(s x - b_{r,s}),\\,w_{r,s}, b_{r,s} \\in \\mathbb{R}$ is the same as a space of $\\sum_{r}w_r\\text{ReLU}(a_rx + b_r)$. Given that, the results of the authors should be possible to extend in the case of standard feedforward neural networks with $\\text{ReLU}$ activations and a single hidden layer. Can the authors please comment on that?\n2. Conditions (13) and (14) are clearly very important. Can the authors please provide a more intuitive explanation in style of Section 5 on the meaning of these conditions. What kind of function and grid may violate this condition? What are the examples when this condition holds?\n3. Discussion in Section 5 is very helpful and intuitive. Indeed, it is hard to argue that under these unfavorable conditions local adjustments of weights is futile and gradient-based methods fail. However, it is not explained clearly enough how this is related to the main result given in Theorem 3.3 and to the conditions (13) and (14). Is it possible to transfer aforementioned conditions to a practical conclusion? For example, if I have a function from a certain class is it always possible to select a fine enough grid (the choice of $b_r$) such that condition (13) / (14) holds? If this is the case, can the authors construct examples that demonstrate this property?\n4. I also want to point out that the framing of the obtained result is somewhat not accurate. Authors refer to the “good” (e.g., dense enough to result in equidistribution) locations of $b_r$ as “sufficiently fine resolution.” This sounds a little misleading, since $b_r$ are selected at will only during the initialisation, unless authors want to bypass gradient descent and redistribute / add $b_r$ according to some other training rule (e.g., greedy). Can the authors please comment on that part? Is it possible to relate main result to initialisation and, when the number of $b_r$ is large to the overparameterized case (at least for sufficiently smooth targets)?", "broader_impact_concerns": "na", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HbXDGh1a5d", "reviewer": "Reviewer_ZmLz", "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": "### Strength\n\nThe paper provides a fine-grained analysis of the approximation ability of the studied network, with a comparison with the linear approximation. The paper also provides mathematical insights into why the approximation result can be established.\n\n### Weakness\n\n**Weakness 1: Lack of Clarity and Readability**: The paper is very difficult to follow. **First**, some of the terminologies and concepts appear to be directly borrowed from other fields, such as finite element analysis. which I believe are unfamiliar to the broader machine learning community. For example, on Page 3:\n\n1. The definition of \"normalized grid size\" is unclear. It is related to the interval between $b_i$'s. I don't know why multiplying by the network width $m$ is called \"normalization\".\n\n2. The term \"local resolution\" is never clearly defined. I had to guess its meaning.\n\n3. \"Generally, this requires global movement of breakpoints $b_r$ from $f$ independent initial locations\". Why is the movement of $b_r$ independent of initial locations? If the initial locations are appropriate, why would they need to be moved?\n\n4. \"have highly oscillatory features between breakpoints that are imperceptible to the gradient.\". The term \"oscillatory feature\" is not defined, and what does this whole sentence mean?\n\nThese are just a few examples from a single page; there are numerous other instances throughout the paper.\n\n**Second**, the technical content is presented in a manner that is not accessible to general readers. Key arguments are often preceded by lengthy and complex primers, making the main points difficult to grasp. For example, in Section 2, the crucial argument \"Therefore, if we can find critical points ... it must exploit the nonlinearity of the network\" is buried at the end of the section.\n\n**Weakness 2: Lack of Discussion on Important References**: The paper does not adequately cite or discuss key references. For instance, in the context of landscape studies, [R1] and [R2] have shown that bad local minima exist in arbitrarily deep and wide neural networks with smooth and piecewise linear activations. Specifically, [R2] demonstrates that arbitrarily bad local minima can exist in ReLU networks, in a more general setting than that considered in this paper.\n\n**Weakness 3: Unclear Contribution**: I have several concerns regarding the contributions claimed by this paper:\n\n1. The paper claims that it studies the approximation error of critical points, distinguishing itself from universal approximation studies. However, (1) it does not characterize all critical points, and (2) it only considers training error in a finite domain. In this case, a sufficiently wide network can be trained very well with $\\theta$ in a sufficiently large compact set. Then analyzing the universal approximating error is equivalent to analyzing the the global minimum (a critical point) of the training problem. \n\n2. The setting is overly simplified. The network has only one input dimension and has no input weights (only input bias is considered). This setup resembles a one-dimensional interpolation problem rather than a typical neural network. I doubt it can provide sufficient insight into general neural networks. Additionally, the authors frequently reference splines, but it is unclear whether the techniques used in this paper are direct extensions of approximation analysis methods from interpolation. The authors should clarify this point.\n\n3. The claim that the paper analyzes \"nonlinear behavior\" is overstated. The paper merely shows that nonlinear models can achieve better approximation than linear models, which is not a surprising result. The paper does not study any training dynamics. In particular, the paper references that NTK is a \"linearization argument\", treating it as an important motivation. However, NTK studies do analyze training dynamics, as they typically focus on the convergence of training.\n\n[R1] Tian Ding, Dawei Li, and Ruoyu Sun. \"Suboptimal local minima exist for wide neural networks with smooth activations.\" Mathematics of Operations Research 47.4 (2022): 2784-2814.\n\n[R2] Fengxiang He, Bohan Wang, and Dacheng Tao. \"Piecewise linear activations substantially shape the loss surfaces of neural networks.\" ICLR 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "The paper studies the critical points of a two-layer, 1-dim-input, 1-dim-output simplified network. Specifically, the paper shows that under certain conditions, critical points approximate the ground truth with diminishing error with order $m^{-2}$, where $m$ is the width of the network. The paper claims the following major insights:\n\n1. The result shows that these critical points \"exploit the non-linearity of the network\" because linear approximation can not achieve the same result. Precisely, linear approximation can also achieve $m^{-2}$ approximation error, but only for ground truth functions in a much smaller class.\n\n2. The results are achieved by sufficiently high resolution, where resolution is measured by the size of intervals between two consecutive bias terms $b_i$ and $b_{i+1}$. Under sufficiently high resolution, the neural network approximates every concave or convex subdomain of the ground truth with a linear segment.\n\n3. Unfavourable critical points (with high approximation loss) can also be constructed.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "According to the weakness, I suggest to:\n\n1. Improve the presentation;\n\n2. Compare with the above references;\n\n3. Clearly justify the contribution of this paper.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8TOurZ7aSM", "reviewer": "Reviewer_xGKk", "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": "I found the writing of this submission extremely unclear. Perhaps I'm not the right audience for this, but I would have greatly preferred (1) a clearer distinction between known work and the paper's contributions, (2) more background, and definitions of jargon specific to this area; (3) more details on the implications of the paper's results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "The paper studies the training behavior of a simple shallow neural network in one dimension. The over-parametrization regime of neural networks has been extensively studied via linearization and landscape analysis. However, these analysis techniques are not quite sufficient to capture the nonlinear dynamics when the network is much less over-parametrized.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "My primary concern with this submission is, in my opinion, a lack of clarity in the exposition. I found it incredibly difficult to read this paper and parse what its contribution is, both conceptually and technically. Therefore, my biggest requested change is to drastically improve the writing of this paper for it to be intelligible to readers beyond just those that work on this specific topic.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "HsdF9D8Bes", "reviewer": "Reviewer_YTYo", "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 conducts a detailed examination of the nonlinearity present in a basic shallow neural network, moving beyond the oversimplifications of the over-parametrized regime. This analysis delivers valuable insights into the intricate optimization landscape of real-world neural networks.\n2. The paper recognizes the existence of unfavorable critical points within the neural network and demonstrates that these critical points can be alleviated by mitigated by ensuring a sufficiently high local resolution.\n\nWeaknesses:\n1. The analysis is limited to a simple shallow network in one dimension, which may not be fully representative of the complexity of practical neural network architectures.\n2. While the theoretical insights are valuable, the paper does not explore the practical implications or applications of these findings.", "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 a detailed investigation of the nonlinearity inherent in a simple shallow network operating in one dimension. The analysis reveals that these networks can exhibit unfavorable critical points, which can be mitigated by ensuring a sufficiently high local resolution. The paper demonstrates that when the local resolution is sufficiently high, all critical points of the network satisfy L2 loss bounds that are optimal in terms of adaptive approximation in Sobolev and Besov spaces. Crucially, these bounds cannot be matched by linear approximation methods, highlighting the inherent nonlinearity and global behavior of the critical points' inner weights.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Could you provide additional clarification on Assumption (13)? Any concrete example?\n\n2. The paper is primarily theoretical, without any empirical validation. Could you provide analogous illustrations based on experimental results?\n\n3. In what ways could your findings be utilized to enhance deep learning algorithms?\n\n4. What are the primary challenges in generalizing the results to high dimensions?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall, this work examines the network’s nonlinearity, moving beyond the oversimplifications of over-parameterization. The findings provide valuable insights into the complex optimization landscape of real-world neural networks. All reviewers acknowledge the technical contributions of this paper and recommend acceptance.

Very minor comment: fix the reference issues at "f a PDE ???." (right after eq. (2)), and at "capture sub-grid oscillations ???."  (at the end of  Section 5.1).
Decision: Accept (poster)