Tighter Sparse Approximation Bounds for ReLU Neural Networks
Authors: Carles Domingo-Enrich
Youssef Mroueh
Venue: ICLR 2022 Spotlight (2022)
Keywords: neural network
two-layer
infinite-width
approximation
sparse
Radon transform
Fourier transform
ReLU

Abstract: A well-known line of work (Barron, 1993; Breiman, 1993; Klusowski & Barron, 2018) provides bounds on the width $n$ of a ReLU two-layer neural network needed to approximate a function $f$ over the ball $\mathcal{B}_R(\mathbb{R}^d)$ up to error $\epsilon$, when the Fourier based quantity $C_f = \int_{\mathbb{R}^d} \|\xi\|^2 |\hat{f}(\xi)| \ d\xi$ is finite. More recently Ongie et al. (2019) used the Radon transform as a tool for analysis of infinite-width ReLU two-layer networks. In particular, they introduce the concept of Radon-based $\mathcal{R}$-norms and show that a function defined on $\mathbb{R}^d$ can be represented as an infinite-width two-layer neural network if and only if its $\mathcal{R}$-norm is finite. In this work, we extend the framework of Ongie et al. (2019) and define similar Radon-based semi-norms ($\mathcal{R}, \mathcal{U}$-norms) such that a function admits an infinite-width neural network representation on a bounded open set $\mathcal{U} \subseteq \mathbb{R}^d$ when its $\mathcal{R}, \mathcal{U}$-norm is finite. Building on this, we derive sparse (finite-width) neural network approximation bounds that refine those of Breiman (1993); Klusowski & Barron (2018). Finally, we show that infinite-width neural network representations on bounded open sets are not unique and study their structure, providing a functional view of mode connectivity.

Under review as a conference paper at ICLR 2022
TIGHTER SPARSE APPROXIMATION BOUNDS FOR RELU NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
A well-known line of work (Barron, 1993; Breiman, 1993; Klusowski & Barron, 2018) provides bounds the width of a ReLU two-layer neural network needed to approximate a function f over the ball (RR up to error 6, when the Fourier based quantity C Sي- | de is finite. More recently Ongie et al. (2019) used the Radon transforr networks. In particular, they introduce the concept of Radon-based R-norms and show that a function defined on Rd can be represented as an indinite-width two- layer neural network if and only if its R-norm is finite. In this work, we extend the framework of (Ongie et al., 2019) and define similar Radon-based semi-norms (R. (-norms) such that function admits an infinite-widtt neural network repre- sentation on a bounded open set C Rdd when its R. --oorm finite. Building on this, we derive sparse winith-width) neural network approximation bounds that re- fine those of Breiman (1993); Klusowski & Barron (2018). Finally, we show that infinite-width neural network representations on bounded open and study their structure, providing a functional view of mode connectivity.
tool for analysis of infinite-width ReLU two-layer
unique
INTRODUCTION
Extensive work has shown that for neural network to be able generalize, the size magnitude of the parameters is more important than the size of the network, when the latter is large enough (Bartlett, 1997; Neyshabur et al., 2015; Zhang et al., 2016). Under certain regimes, the size of the neural networks used in practice is so large that the training data is fit perfectly and an infinite-wide width approximation appropriate. In this setting, what matters to obtain good generalization is fit the data using the right inductive bias, which is specified by how network parameters are controlled (Wei et al., 2020) together with the training algorithm used (Lyu & Li, 2020).
The infinite-width two-layer neural network model has been studied from several perspectives due to its simplicity. One can replace the finite-width ReL.U network A - ay( (4,, x) - b2) by an integral over the parameter space with respect to a signed Radon measure: [((w, x) - 6)+ da(w,, b). Thus, controlling the magnitude of the neural network parameters is akin controlling the mea- sure a according to certain norm. Bach (2017) introduced the F1-space, which is the infinite- width neural network space with norm inf [6 (w. b)), derived from the finite-width regular- izer E |a (wi, b1) (the infimum over all the measures which represent the function at hand). A different line of work (Savarese et al., 2019; Ongie et al., 2019) consider the infinite- width spaces with norm inf[[|a|[Tv = d|a: (w, b)}. which is derived from the finite-width regularizer 1 - lay ||w/|2 (i.e. omitting the bias term). Both of these works seek to find expressions for this norm, leading to characterizations of the functions that are representable by infinite-wiee networks. Savarese et al. (2019) solves the problem in the one-dimensional case: they show that for a function on R. this norm takes value max[]a ff" da, (- f' [o(o))]]- Ongie et al. (2019) give an expression for this norm (the R-norm) for functions on Rd, making use of Radon transforms (see Subsec. 2.3).
Although we mentioned in the first paragraph that in many occasions the network size is large enough that the specific number of neurons is irrelevant, when the target function is hard to approx-

---

Under review as a conference paper at ICLR 2022
imate it is interesting to have an idea of how many neurons needs to approximate it. The first contribution in this direction was by Cybenko (1989); Horiik et al. (1989), which show that two- layer neural networks with enough neurons sets in the uniform convergence topology. Later on, Barron (1993); Breiman (1993) provided sparse approximation bounds stating that if function f' is such that certain quantity Cj constructed from the Fourier transform f is finite, then there exists a neural network of width n such that the L ap- proximation error with respect to distribution of bounded support is lower than OCC, /n). More recently, Klusowski & Barron (2018) provided alternative sparse approximation bounds of Breiman (1993) by restricting to networks with bounded weights and slightly better dependency on the expense of a constant factor increasing with d (see Subsec. 2.2).
approximate any reasonable function bounded
Contributions. our work, we seek to characterize the functions that coincide with an infinite- width two-layer neural network on fixed bounded open set. This endeavor is interesting in itself because in practice, we want to learn target functions for which we know samples on a bounded set, and we are typically unconcerned with the values that the learned functions take at infinity. Moreover, the tools that we develop allow us to derive ofte--f--hh--ar sparse approximation bounds. Our main contributions are the following:
In the spirit of the R-norm introduced by Ongie et al. (2019), for any bounded open set U C Rd we define the R. uonormm of a function on R", and show that when the R. u.normmmm of f is finite, fx) can admits representation of the form fga-1x0 1 (ww, x) b)+ da(w. b) + (u, 2) + e for
x E U, where v E R c E RR and a is an even signed Radon measure.
Using the R, norrm, we derive function approximation bounds for neural networks with fixed finite width. We compute the R., -oorm of function in terms of its Fourier representation, and show that it admits an upper bound by the quantity Cy. This shows that our approximation bound is tighter than the previous bound by Breiman (1993), and meaningful in more instances (e.g. for finite-width neural networks). We also show R. 4-norm--baaa based bounds analogous to the ones of Klusowski & Barron (2018).
Setting U/ as the open unit ball of radius Rt we show that neural network representations of f on U hold for multiple even Radon measures, which contrasts with the uniqueness result provided by Ongie et al. (2019) for the case of Rdd We study the structure of the sets of Radon measures which give rise the same function on U. The non-uniqueness of the measure representing a measure could be linked to the phenomenon of mode connectivity.
Additional related work. There have been other recent works which have used the Radon transform to study neural networks in settings different from ours (Parhi & Nowak, 2021a; Bartolucci al., 2021). These two works consider the R-norm as regularizer for an inverse problem, and proceed to prove representer theorems: there exists solution of the regularized problem which is a two- layer neural network equal to the number of datapoints. Regarding infinite- width network spaces, E & Wojtowytsch (2020) present several equivalent definitions and provides a review, A well-known line of work (Mei et al., 2018; Chizat & Bach, 2018; 8; Rotskoff & Vanden-Eijnden, 2018) studies the convergence of gradient descent for infinite-width two-layer neural networks.
2 FRAMEWORK
2.1 NOTATION
Sd-1 denotes the (d - (1-1)-aae -imdennsio hypersphere (as a submanifold of Rd) and (R((d)) is the Euclidean open ball of radius R. For U C IRd measurable, the space (U) of functions vanishing at infinity contains the continuous functions f such that for any c >> 0, there exists compact K C U depending on f such that [f(x)] < e for x E U K. P(U) is the set of Borel probability measures, MU) is the space of finite signed Radon measures (which may be seen as the dual of CoUU)). Throughout the paper, the term Radon measure refers to a finite signed Radon measure for shortmess. If 7 E MMU), then I| is the total variation (TV) norm of y. Me(U) denotes the space of complex-valueee finite signed Radon measures, defined as the dual space of CU C) (the space of complex-valued functions vanishing at infinity). We denote by S(Rd) the space of
2

---

Under review as a conference paper at ICLR 2022
Schwartz functions, which contains the functions in C (RC) whose derivatives of any order decay faster than polynomials of all orders, i.. for all k. (No) supzeRd (z* ((x)) +oo. For E L' (RR). we use f to denote the unitary Fourier transforms with angular frequency, defined as f(E) = (2m)d72 JR= f(x))= (() dr. If E (R())) as well, we have the inversion formula f(x) = (2aja72 SR+ ((E)e dr. The Fourier transform is continuous automorphism on S(IR)).
2.2 EXISTING SPARSE APPROXIMATION BOUNDS
One of the classical results of the theory of two-layer neural networks (Breiman (1993), building on (Barron, 1993)) states that given probability measure p E P(BB((R))) and a function f BR ( IR admitting Fourier representation of the form f(() (2*)^/2 JR eltE.a) df()), where E Mc( is a complex-valee valuee Radon measure such that Cj = (2m)d/2 Jga 115113 dlf((s) < to0, there exists two-layer neural network f(xx) = - ai((r,ws) - by) such that
JSL ( (f(x)- f(x)) de (2R)
These classical results do not provide bounds on the magnitude of the neural network weights. More recently, Klusowski & Barron (2018) showed similar approximation bounds for two-layer ReLU networks under additional 1 and bounds on the weights 4, Namely, if C2 =
(2m)a/a SR 11El1 dlff(() < too there exists two-layer neural network f(x) ag (Wb. + 1 0; a,((u, 2) b,)+ with |a: S 1, || || S d, [0, 1], and α S 2Č,, and sup 1/(x) f(x) v c C, log n -1/--11/ =E1-1.11
1
(2)
where e is a universal constant.
2.3 REPRESENTATION RESULTS ON RD BASED ON THE RADON TRANSFORM
One defines pd denotes the space of hyperplanes on Rd whose elements may be represented by points gd-1 x IR by identifying {z|(w, x) b) with both (w, b) and (-w; -b). Thus, functions on pd are even functions on gd-1 x R and we will use both notions interchangeably..
The Radon transform and the dual Radon transform. If I IRd - R is a function which is integrable over all the hyperplanes of Rdd we may define the Radon transform Rf pd + as
Rf(w,, b) = - (elkwa))=0) f(z) dz,
V(w,b) E sd-1 IR
That is, one integrates the function ff over the hyperplane (w,b). If ④b pp function, the dual Radon transform R5 Rd + is defined as
IR is continuous
= ff (w, (w, dw; Vo E RRdd
R +
where the integral is with respect to the Hausdorff measure over Sd-1, R. and R are adjoint operators in the appropriate domains (see Lemma 13).
The Radon inversion formula. When f E C (RRd), one has that (Theorem 3.1, Helgason (201 1)) f = ca( (a(-A)(d-1)/22 R*
(3)
where Ca -(2 and (-A)a/2 denotes the (negative) fractional Laplacian, defined via its Fourier transform as ( A))/2f(() f(E)) f(E).
"Similarl,, the space M(F")) of Radon measures over pd contains the even measures in M( x R). a M(F"), fgi- xa puw, b) dar(w, b) well defined for any measurable function &o on gd-1 x R, but Spa (p(w, da(ws, b) is only defined for even yp.
3

---

Under review as a conference paper at ICLR 2022
The R-norm.
Given function f FR - R. Ongie al. (2019) introduce the quantity
sup(-caa (-A v)) bb S(S R), even, || s = if f Lipschitz otherwise.
||
+00
(4)
They call it the R-norm of although it is formally semi-norm. Here, the space S( x IR) of
Schwartz functions on g x IR. is defined, in analogy with S(R"), the space of C functions d on gd-1 x IR which for any integers k. I 2 0 and any differential operator D on Sd-1 satisfy suP(w.b) [[1 +
b) +oo (Helgason (2011), p. 5). Moreover, S(IP)) {ib E S(S x R) sb even), which means the conditions on 1p in (4) can be written as x E S(P"), |0 S 1.
The finiteness of the R-norm indicates whether function on E admits exact representation as an infinitely wide neural network. Namely, Ongie et al. (2019) in their Lemma 10 show that [| is finite if and only if there exists a (unique) even measure M(S x R) and (unique) e E R c E IR such that for any x E R.
f(x) = {
(ww, - -b da(w, b) + (0,x)+ tc.
(5)
gd 1
in which case, | ||||TTV.
Remark the following differences between this result and the bounds by (Breiman, 1993; Klusowski & Barron, 2018) shown in equations (1) and (2):
(i) in (5) we have an exact representation with infdnite-width neural networks instead of an approximation result with finite-width,
(ii) in (5) the representation holds on Rd instead of a bounded domain.
In our work, we derive representation results similar to the ones of Ongie et al. (2019) for functions defined on bounded open sets, which naturally give rise to sparse approximation results that refine those of (Breiman, 1993; Klusowski & Barron, 2018).
One property that makes the Radon transform and its dual useful to analyze neural networks can be understood at a very high level via the following argument: if f(x) fga-1 (w,, b)+p(w, b) d(w, b) + (v, + for some smooth rapidly decreasing function p. then Af(x) Ig xR (w =opww, b) d(w.b) b) = Jg p(w, (w,z)) dw = (R' (z). For a general function f of the form (5), one has similarly that (Af. :p) = (a, Rup) for any o E ((Rd). This property relates the evaluations of the measure a to the function A f via the Radon transform, and is the main ingredient in the proof Lemma 10 of Ongie et al. (2019). While we also rely on it, we need many additional tools to deal with the case of bounded open sets.
REPRESENTATION RESULTS ON BOUNDED OPEN SETS
Schwartz functions on open sets. Let S Rd be an open subset. The space of Schwartz fune- S(RR) f()) 0}, i.e. they are those Schwartz functions on iRd such that the derivatives of all orders vanish outside of U (c.f. Def. 3.2, Shaviv (2020). The structure of S(U) similar S(IRd) in that its topology is given by family of semi-norms indexed by ((2) R supzeu la ((0)())) Similarly, if V C pa is open, we define S(V) = ( (KE E S(IPd) 0h Á ko f(w, b) = 0}, where Å is the spherical Laplacian.
tions on 4 may be defined S(4) N=eamu Ceeaannneeeceo [I
The R. Let 2 C Rd be bounded open set, and let úi : (lw, (w) E @d--1 1--11x00 x RRRr U}. For any function f: R2d - IR, we define the R, normm of f as
Illl supp-cade (-A)) R" vb) 1b E S(i), & even, |//l $1). (6)
4

---

Under review as a conference paper at ICLR 2022
Note the similarity between this quantity and the R-norm defined in (4); the main differences that the supremum here is taken over the even Schwartz functions on U instead of s R, and that the non-Lipschin Lipschith case does not need separate treatment. Remark that [l S ll If f has enough regularity, we may write || R = l [R(-A)(4+1)2 A(, b) d(w;b) b). using that the fractional Laplacian is self-adjoint and R* is the adjoint of R.
Define Pdd to be the bounded open set of hyperplanes of Ie that intersect U. which in anal- ogy with Subsec. 2.3, is equal to u up to the identification of (w, with (-w, -b). Similarly, note that S(P)) { S(U), even), which allows to rewrite the conditions in (6) as
S(TR)) 1l S
The following proposition, which is based on the Riesz-Markov-Kakunn Kakutani representation theorem, shows that when the R, 2o-mm finite, can be associated to unique Radon measure over Lit. Proposition 1. If [I +oc, there exists unique Radon measure a MM(T)) such that -calf. (- 1/24 v)) = Jeg wbw, b) da(w,b) b) for any vb E ((P)) Moreover, [f = ||a]|rv
Building this, we see that neural network representation for bounded U holds when the R, U- norm is finite:
Theorem 1. Let U be a open, bounded subset of Rd.. Let Rd IR such that || < +00. Let M( be given by Proposition 1. For any 4p E S(U), there exist unique Rd and c E IR such that
J [Ww)o()) dx I (fllwre)) - +)+ da(w,,) + (v, (c, +c) p(x) dx,
That is, f(x) (p(lw,x) +) da(w,t) 1) (V,z) + for a a.. (almost everywhere) in U. If f is continuous, then the equality holds for all x E U.
Remark that this theorem does not claim that the representation given by a, v, c unique, unlike Lemma 10 by Ongie et al. (2019) concerning analogous representations on Rd. In Sec. 5 we see that such representations are in fact not unique, for particular choices of the set U. We want to underline that the proof of Theorem 1 uses completely different tools from the ones of Lemma 10 by Ongie et al. (2019): their result relies critically on the fact that the only harmonic Lipschitz functions on Rd are affine functions, which is not true for functions bounded subsets in setting.
SPARSE APPROXIMATION FOR FUNCTIONS WITH BOUNDED R, UNORM
In this section, we show how to obtain approximation bounds of a function on a bounded open set l/ using a fixed-width neural network with bounded coefficients, in terms of the RR, Uormm introduced in the previous section.
Theorem 2. Let U (IR))) be a bounded open set. Suppose that f Rdd + R is such that IR is finite, where || 1RR. is defined in (6). Let v E Rd E as in Theorem 1. Then, there exists {ww, b.) C ú and {ar) S {+1} such that the function f : Rd + R defined as
f(x) 1fIRR
a: (w(())))) - bc)+ + (0,x) +
n
fulfills. for a.e. in U.
R RRlRR Vn
F(x) ((x))
(8)
The equality holds for all x E U if is continuous.
The proof of Theorem 2 (in App. B) uses the neural network representation (7) and a probabilis-
tic argument. If one samples ((w;, bz)) from a probability distribution proportional |a],
5

---

Under review as a conference paper at ICLR 2022
Rademacher complexity bound upper- upper-bounds bounds the expectation of the supremum between ff and f, which yields the result.
Note the resemblance of (8) with the bound (I); the R,2 norm of f replaces the quantity Cy. We can also use the R. Lo-m to obtain a bound analogous to (2), that is, with a slightly better dependency in the exponent
the expense of constant factor growing with the dimension.
Proposition 2. Lel f IRd R and U C Bi (R2) open such that || R/ < +00. Then, then there
exist {a, j= S [[-1, {wi]?= S fw e R ||]|| 1} and {be C [0, 1] and is < vdllf Ie
such that the function
[(x)
az (wii b:)+
fulfills, for a.e. in U and some universal constant 0.
(f f(x)] ek < log 1-2-1144
The proof of this result (in App. B) follows readily from the representation (7) and Theorem 1 of Klusowski & Barron (2018).
4.1 LINKS WITH THE FOURIER SPARSE APPROXIMATION BOUNDS
The following result shows that setting 44 = Bn((R)) the R, 4-nom can be bounded by the Fourier- based quantities Cj, Öj introduced in Subsec. 2.2.
Theorem 3. Assume that the function ʃ Rd
R admits Fourier representation of the form f()) 12 JEJ e df(E) with f Mc(Rd) a complex-valued Radon measure. Let Cj be the quantity used in the sparse approximation bound by Breiman (1993) (see Subsec. 2.2). Then, one has that
S S2RC,
As a direct consequence of Theorem 3, when U = Bn (Rd) the right-hand side of (8) can be upper-bounded by TPC,/vn. This allows to refine the bound (1) from Breiman (1993) to bound in the supremum norm over BR (IR),, and where the approximating neural network f(x) = D. as ((x,wi) - 6:)+ (v,x) fulfills la;| [| (R.), ||w:||2 S 1 and by (-R, R).
While able prove the bound (9), the Fourier representation of f does not allow for manageable expression for the measure a described in Proposition 1. For that, the following theorem starts from slightly modified Fourier representation of f. under which one can describe the measure and provide a formula for the R, U-nomm.
Theorem 4. Let Idd R admitting the representation
f(x)=
/
ahlwwa) du(w,b). b).
(10)
for some complex-valued Radon measures μ E MM x such that du(w, b) = dul-w, -b) dp(-w, b) = dp(ww, -b), and Sge-1 6ddppl (w, b) < to0. Choosing BR(R),, the unique measure E -M(P)) specified by Proposition 1 takes the following form:
da(w,b) = - &e-ith dp(w, t) db.
where K = 2/2 ( Note that is real-valued because f fe du(w,t) t) E 1 ddllw,t)= (-t)2 du(w,, -t). Consequently, the R, BR (RR of f
R as
Il llflRR,B((R)) = ||a||zv= / ( &e- du(w.t) db.
(11)
884-1

---

Under review as a conference paper at ICLR 2022
Remark that μ is the pushforward of the measure f by the mappings & + (= #c). When the Fourier transform f admits a density, one may obtain the density of μ via a change from Euclidean to spherical coordinates: dp(w. b) = 2/2 vol(S* 'f [bw)) d(w, b). Hence, Theorem provides an operative way to compute the RR RR,4dnorm of f if one has access to the Fourier transform of f- Note that equation (11) implies that the R. Bn (RR )-orm of increases with R, and in particular smaller than the R-norm of f. which corresponds to setting R oc.
Theorems 3 and 4 are proven jointly in App. B. Note that from the expression (11) one can easily see that (R))))) is upper-bounded by RCy:
R 8d 1 Pic-it du(we,t) 1) db S S A
/ S le dlpl(w, db db= 2R / ((())
where the equality holds since j is the pushforward of f. Equation (12) makes apparent the norm 1R, is sometimes much smaller than the quantities Cj, Cj,C,, as is showcased by the follow- ing one-dimensional example (see the proof in App. B). In these situations, the sparse approximation bounds that we provide in Theorem 2 and Proposition are much better than the ones in (1)-(2).
Example 1. Take the function f R + R. defined as f(x) = cos(x) cos((1 + e)z), with e > O. I admits the Fourier representation ((x) = (2:))T2 Ja ((6) + 6-1 (E) - 61+c(E)
8_ )-1-(())) dg, We have that Cf + 2$ 2 and [[ S R (Re 2e e²).
|| (R,BB)) goes to zero as - O, while C converges to 2.
An interesting class of functions for which |Il finite but Cj. Cj are infinite are func- tions that can be written as a finite-width neural network on (R((Rd) as shown in the following proposition.
Proposition 3. Let f Rdd R defined as =())= Ein bi)+ for all Rd. with [w:)?m S gd-1, {a, tbel S R. Then, for any bounded open set U, we have Il lllu S 1 A (ag), while Cj, Cy = too if f is not an affine function.
Proposition 3 makes use of the fact that the R, U-nom is always upper-bounded by the R-norm, which also means that all the bounds developed in Ongie et al. (2019) apply for the R. nnoom. The fact that finite-width neural networks have infinite Cý was stated by E & Wojtowytsch (2020), that used them show the gap between the functions with finite Cj and functions representable by infinite-width neural networks (belonging to the Barron space, in their terminology). It remains to be seen whether the gap is closed when considering functions with finite R. n.rm i.e., whether any function admitting an infinite-width representation (7) on U has finite R, nnrrm.
Moving to the non-linear Radon transform. In many applications the function of interest f may be better represented as I [(W, (o(rr) - 4)+ da () + (v, + c, where y is fixed finite dimen- sional, non-linear and bounded feature map. Our results trivially extend to this case where in the Radon transform hyperplanes are replaced by hyperplanes in the feature space. This can be seen as the "kernel trick" applied to the Radon transform. The corresponding [I (2,44)) corresponds to the sparsity of the decomposition in the feature space, and we have better approximation when IIll < IR This gives simple condition for when transfer learning is successful, and explains the success of using random fourier features as preprocessing in implicit neural represen- tations of images and surfaces (Tancik et al., 2020). In order to go beyond the fixed feature maps and tackle deeper ReLU networks, we think that the non-lineat Radon transform (Ehrenpreis, 2003) is an interesting tool to explore. We note that Parhi & Nowak (2021b) introduced recently representer theorem for deep ReLU networks using Radon transforms as a regularizer.
INFINIE-WIDDEE REPRESENTATIONS ARE NOT UNIQUE ON BOUNDED SETS
Ongic et al. (2019) show that when the R-norm of f is finite, there is a unique measure a E M(R)) such that the representation (5) holds for E IRd In this section show that when only ask
7

---

Under review as a conference paper at ICLR 2022
the representation to hold for x in bounded open set, there exist several measures that do the job; in fact, they span an infinite-dine -inntt--dimensonnll space.
Let u = BR ( be the open ball of radius R > O in R which means that i = sd-1 x (-R. R) and 1e the set of hyperplanes (ws, x> b} such that || = and b (-R, R), which we denote by IP for simplicity. In the following we will construct a space of Radon measures (M(%)) whose neural network representation (5) coincide for all x E (R()).). Note that since any bounded subset of IR is included in some open ball, our results imply that such representations are non-unique on any bounded set.
Remark 1. When one considers representations on (R( of the sort (5) with the measure a lying in the larger space M(S x I), the non- non-umiqueness is apparent because there are two 'trivial'
kinds of symmetry at play:
(i) Related to parity: when the measure a is odd, we have Iga-1xR((e xR (ww, x) - b)+ da(w,, b) =
1/2 Sga xx ((,,z) b)+ (-(w, x) + b)+ da(w,,)
(2 Sou IxR w da(w, b),
2 Sga-1 XR b dor b). which is an affine function of
(ii) Related to boundedness: if (w, b) E (
I ((w, - b)+ restricted to BR(B ) is an affine function of x. Hence, if a is supported on sd-1 xS x (R) R. R)), x 1a/-1xa ( ((2, - b)+ da(w, b) is an affine function when restricted to BR (R
Since Sec. we restrict our scope to measures a lying in M(P(). these two kinds of symmetries are already quotiented out in our analysis. The third kind of non-uniqueness that we discuss in this section conceptually deeper, taking place within M M(Pd). )
Let (Yug ke i S Nx.d be the orthonormal basis of spherical harmonics of the space 123 (Atkinson & Han, 2012). It is well known that for any k, the functions {Yku 1 S j S Nu,a) are the restrictions to gd-1 of homogeneous polynomials of degree k, and in fact Ng.d the dimension of the space of homogeneous harmonic polynomials of degree k. Consider the following subset of even functions C (gd-) x (-R, R)):
A = (Yk, & x A.j,M'zz k = k (mod 2), k' < k: - N
where X denotes the monomial of degree K' on (-R, R). We have the following result regarding the non-uniqueness of neural network representations:
Theorem 5. If a E M(PA) is such that a E (span(AA))) then we have that 0 = (g,RI (ww, x) - b)+ da(w, b) for any x E BR(RR). That is, a yields a neural network repre- sentation of the zero-function on (Rd)). Here, we consider span(A) as a subset of M(F)) by the Riesz-Markov- -aaktanii representation theorem via the action {g. sp) = Sog s(w, b)g(w, b) d(w, b) for any g E span(A), E Co(PP)) ). and ch denotes the closure in the topology of weak convergence of M( x R).
In particular, any measure whose density is in the span of A will yield a function which is equal to zero when restricted to (x As example of this result, we show a simple measure in M(PP) which represents the zero function on B, (R²).
Example 2 (Non-zero measure representing the zero function on B, (RR2). We define the even Radon measure a E M(S x (-1, 1)) with density da(ws, b) = (Bug - +1)+ d(w, b) where w = (wo, (w),w1). Then, for any Bi (I22, (ei x) b)+ 2w)
On the one hand, Proposition states that there exists a unique measure a M(Pd) such that -ca(f. (-A)(d+1)/2R* = SFz b) da b) for any vi E S(P)) if [| is finite. On the other hand, Theorem 5 claims that functions admit distinct representations by measures in M(P)) The following theorem clarifies these two seemingly contradictory statements. Consider the follow- ing subset of even functions in Co0 (gd-) x (-R, R)), which contains A:
= (YeJ 6 X KkjjK' e ezt k = k' (mod 2), V' k, 1 1si5 Nd,K).
8

---

Under review as a conference paper at ICLR 2022
Proposition 4. Let 0 < < R'. Let f R + R such that (g too and let E M(P be the unique measure specified by Proposition Then, a the unique measure in ((P)) such that
Vp e ( (a, Rup) (B(())))
f(x)A(p(2) dr,
(13)
jk Ex s.1. k' = (mod 2), K < k 1 S S Nk.d, (a,Y x²) -calf, (-A) (Yus & lx(xxx)))
(14)
The condition (13) holds for any measure a' E MM(P)) for which f admits a representation of the form (7) on (R. Thus, a can be characterized as the unique measure in M(P such that f admits a representation of the form (7) on B (R²) and the condition (14) holds.
In (14), the quantity (f. (-A)G4t)//R (Yk.J & Ixx is well defined despite 1 | not being continuous on IR; we define it as (S, (- (- ()) ((Yk.5 & x π)), where any function in S(P)k) such that (Ya,, @ xx - E S( (which do exist, see App. C).
In short, Proposition 4 characterizes the measure from Proposition in terms of its evaluations on the spaces (( and span( B), and by Corollary 1 the direct sum of these two spaces dense in Co(P)) which by the Mraiz-Markv--Ka.
representation theorem is the predual of M(P Interestingly, the condition (13) holds for any measure .M(P)) which represents the function f on R ), but it is easy to that the condition (14) does not: by Theorem 5 we have that & span A) C span B), the measure a' defined as da' (w, b) = da(w, b) + d(w, b) db represents the function on B3 (R.), and (a', xp) (a, u²) |
It remains an open question to see whether Theorem 5 captures all the measures which represent the zero function on (RR), which we hypothesize. that was the case, we would obtain a complete characterization of the Radon measures which represent a given function BB (R²).
Mode connectivity. Mode connectivity is the phenomenon that optima of neural network losses (at least the ones found by gradient descent) turn is almost constant, and was observed empirically by Garipov et al. (2018); Draxler et al. (2018). Kuditipudi al. (2019) provided an algorithmic explanation based on dropout, and an explanation based on the noise stability property. Theorem 5 suggests an explanation for mode connectivity from functional perspective: one can construct finitely-supported measures which approximate measure E (span((),, yielding finite-width neural networks with non-zero weights which approximate the zero function on (RR4). Assuming that the data distribution supported in B&(Rd), (R2), adding multiple of one such network to an optimal network will produce little change in the loss value because the function being represented is essentially unchanged. More work is required to confirm discard this intuition.
be connected by paths where the loss value
6 CONCLUSION
We provided in this paper tighter sparse approximation bounds for two-layer ReLU neural networks. Our results build on the introduction of Radon-basse R, Eooms for functions defined on a bounded open set 24. Our bounds refine Fourier-based approximation bounds of Breiman (1993); Klusowski & Barron (2018). We also showed that the representation of infinite width neural networks on bounded open sets are not unique, which can be seen as a functional view of mode connectivity observed in training deep neural networks. We leave two open questions: whether any function admitting an infinite-width representation on 24 has a finite R.U-norm, and whether Theorem captures all the measures which represent the zero function (RR)). Finally, in order to extend our theory to deeper ReLU networks we believe that non- non-linear Radon transforms (Ehrenpreis, 2003) interesting tools to explore.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kendall Atkinson and Weimin Han. Spherical Harmonics and Approximations on the Unit Sphere: An Introduction, volume 2044. Springer, 01 2012.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. Journal of Ma- chine Learning Research, 18(19):1-53) 2017.
Andrew Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information Theory, 39:930 945, 1993.
Peter Bartlett. For valid generalization the size of the weights is more important than the size of the network. Advances in Neural Information Processing Systems, volume 9. MIT Press, 1997.
Francesca Bartolucci, Ernesto De Vito, Lorenzo Rosasco, and Stefano Vigogna. Understanding neural networks with reproducing kernel banach spaces, 2021.
L. Breiman. Hinging hyperplanes for regression, classification, and function approximation. IEEE Transactions on Information Theory, 39(3):999-0013, 1993.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in neural information processing systems, pp. 3036-3046, 2018.
G. Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of Control, Signals, and Systems (MCSS), 2(4):303-314, 1989.
Felix Draxler, Kambis Veschgini, Manfred Salmhofer, and Fred Hamprecht. Essentially no barriers in neural network energy landscape. Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 1309-1318 2018.
Weinan E and Stephan Wojtowytsch. Representation formulas and pointwise properties for barron functions, 2020.
L. Ehrenpreis. The Universality of the Radon Transform. Oxford, 2003.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
S. Helgason. Geometric Analysis Symmetric Spaces. Mathematical surveys and monographs. American Mathematical Society, 1994.
Sigurdur Helgason. Integral Geometry and Radon Transforms. Springer, 2011.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural Networks, 2(5):359-3333 366, 1989.
Sham M Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in Neural Information Processing Systems, volume 21, pp. 793-800. Curran Associates, Inc., 2009.
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, 64(12): 7649-7656, 2018
Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, and Sanjeev Arora. Explaining landscape connectivity of low-cost solutions for multilayer nets. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In 8th International Conference Learning Representations, ICLR 2020. OpenReview.net, 2020.
10

---

Under review as a conference paper at ICLR 2022
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, 115633):E766--7777, 2018.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2012.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. ICLR (Workshop), 2015.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference Learning Representations (ICLR 2020), 2019.
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, 2021a.
Rahul Parhi and Robert D. Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory, 2021b.
Grant M Rotskoff and Eric Vanden-Eijnden Neural networks interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation enror. arXiv preprint arXiv: 18Xv:1805.00915, 2018.
W. Rudin. Functional Analysis. International series in pure and applied mathematics. McGraw-Hill, 1991.
Jorge Salazar. Fubini-tonelli type theorem for non product measures in product space, 2018.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look function space? Conference on Learning Theory, 2019.
Ary Shaviv. Tempered distributions and schwartz functions on definable manifolds. Journal of Functional Analysis, 278(11), 2020.
Matthew Tancik, Pratul Srinivasan, Ben Mildenhall, Sara Fridovich-Keil. Nithin Raghavan, Utkarsh Singhal, Ravi Ramamoorthi, Jonathan T. Barron, and Ren Ng. Fourier features let net- works learn high frequency functions low dimensional domains. NeurIPS, 2020.
Colin Wei, Jason D. Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint a6Xiv: 1..1311111.000.,. 2016.


Reviews:
[{"review_id": "nGLwCzwyq39", "reviewer": "Reviewer_2kZP", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The novelty of this paper is high. By the introduction of R, U-norms the authors show that their approximation bound is tighter than bounds in the previous papers, and meaningful in more instances such as finite-width neural networks. This result will certainly help us have a better understating of deep neural networks from a theoretical way. I have checked the technique parts and find that the proofs are solid. I think this is a significant contribution to the deep learning community. The theoretical results in this paper are about two-layer ReLU neural networks. It will be interesting to see extended results on more widely used architectures in the future. Overall,  I think the results in this paper are important, as explained above.", "summary_of_the_paper": "This paper studies the class of functions that coincide with an infinite width two-layer neural network on a fixed bounded open set. First, they introduce a Radon-based R, U-norms for functions defined on a bounded open set U. Then they prove tighter sparse approximation bounds for two-layer ReLU neural networks. They also prove that the representation of infinite width neural networks on bounded open sets are not unique. ", "summary_of_the_review": "By the introduction of R, U-norms the authors show that their approximation bound is tighter than bounds in the previous papers, and meaningful in more instances such as finite-width neural networks. The novelty of this paper is high. Overall,  I think the results in this paper are significant. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "euUWES78Jcx", "reviewer": "Reviewer_3amN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThis paper uses the novel analysis tool based on Ongie et al. (2019) to consider the bounded open set case. It is technically solid. I check the detailed proof and don't find the major flaws. (I need to admit I am not very familiar with the Fourier-based approximation bounds, so it is possible my judgment on novelty is wrong. And this is why I rate my confidence as 2.)\n\nWeakness:\n\nClarify: It is still room to improve the technical part of the paper. 5 theorems and 4 propositions are shown in the 9-page main paper and more discussions on the Theorems/Proposition may be needed to make the paper easier to follow. I also suggest the authors add some discussions to further highlight the technical difference/significance of the Theorem/Proposition. \n", "summary_of_the_paper": "This paper studies the approximation bounds for the 2-layer  ReLU network.  The authors extend the analysis framework of Ongie et al. (2019) and show the approximation bounds for the infinite-width network on a bounded open set as well as the bounds for sparse (i.e., finite-width) network that refine the similar results in the literature. At last, the authors show that the infinite-width neural network representations may not be unique on bounded open sets and provide a functional view of the mode connectivity. In particular, the authors refine the R-norm introduced by Ongie et al. (2019) to R, U-norm to tickle the bounded open set case.\n\n ", "summary_of_the_review": "This paper uses the novel analysis tool to study the approximation bounds for 2-layers ReLU networks and is technically solid. However, the presentation of the paper is a little bit hard to follow and I've spent about 15 hours checking technical details of the main paper and supplyments... ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Uk0bBy7YZs", "reviewer": "Reviewer_E6s2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The presented tighter sparse approximation bounds for two-layer ReLU neural networks are of interest. Theorem 1 tells that there exists a neural network representation for a function defined on a bounded open set $\\mathcal{U}$ if its $\\mathcal{R}$, $\\mathcal{U}$-norm is finite, which generalizes the results for functions on $\\mathbb{R}^d$ in the literature and yields the sparse approximation bound in Theorem 2. Moreover, the authors discuss its tightness and links with Fourier sparse approximation bounds in Theorems 3 and 4. The non-uniqueness of neural network representations is studied in Theorem 5. I have one concern that how to check the finiteness of the $\\mathcal{R}$, $\\mathcal{U}$-norm for general functions?\n\n\nOther minor comments/typos:\n- rows above (1) and (2). Should $n$ be used instead of $m$?\n-Proposition 2, $n$ or $m$ in the approximation bound?\n", "summary_of_the_paper": "The paper provides some interesting and tighter spare approximation bounds for two-layer ReLU neural networks. The authors generalize the results for $\\mathbb{R}^d$ to a bounded open set $\\mathcal{U}\\subset\\mathbb{R}^d$ by defining the Radon-based $\\mathcal{R},\\mathcal{U}$-norms of functions. They also show that the representation of infinite width neural networks on $\\mathcal{U}$ are not unique.", "summary_of_the_review": "The paper is well organized and technically sound. The results should be interesting to the community of theoretical deep learning.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "GnHKpiQPrvs", "reviewer": "Reviewer_tNiY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I recommend acceptance.\n\nSTRENGTHS: The Radon semi-norm is a potentially useful way of understanding representation, and as the paper shows, there are examples where it can provide a much better bound than the Barron norm.\n\nWEAKNESSES: None that I am aware of.\n\nQUESTIONS:\n- Are there examples where ||_{R,U} is substantially smaller than ||_R (e.g. is this true for Example 1)? Should we expect it to be much smaller for many reasonable functions? More discussion on when/why this bound is better than the prior bounds would be helpful.", "summary_of_the_paper": "The main result of this paper is a representation theorem for functions on a bounded set U by two-layer neural networks with bounded width and bounded weights, via a semi-norm ||_{R,U} based on the Radon transform. Prior work [OWSS19] used the Radon transform to get a representation theorem for functions on R^d, but the bounded-domain setting is more realistic and allows for stronger results, since the semi-norm ||_{R,R^d} will naturally be larger than ||_{R,U}. Moreover, this paper shows that when U is a Euclidean ball, the semi-norm ||_{R,U} can be upper bounded in terms of the Barron norm, so this paper's representation theorem strengthens Barron's Theorem.", "summary_of_the_review": "This paper extends prior work on infinite-width NN approximability for bounded Radon semi-norm to finite-width NN approximability on bounded sets, which is a more reasonable setting and strengthens the classical Barron norm bounds.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors extend the result of Ongie et al. (2019)  and derive sparseneural network approximation bounds that refine previous results. The reuslts are quite ineteresting and relevant to ICLR. All the reviewers were positive about this paper.
Decision: Accept (Spotlight)