A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case
Authors: Greg Ongie
Rebecca Willett
Daniel Soudry
Nathan Srebro
Venue:  (2020)
Keywords: inductive bias
regularization
infinite-width networks
ReLU networks

Abstract: We give a tight characterization of the (vectorized Euclidean) norm of weights required to realize a function $f:\mathbb{R}\rightarrow \mathbb{R}^d$ as a single hidden-layer ReLU network with an unbounded number of units (infinite width), extending the univariate characterization of Savarese et al. (2019) to the multivariate case.

Published as a conference paper at ICLR 2020
A FUNCTION SPACE VIEW OF BOUNDED NORM INFI- NITE WIDTH RELU NETS: THE MULTIVARIATE CASE
Greg Ongie
Rebecca Willett
Department of Statistics University of Chicago Chicago, IL 60637, USA
Department of Statistics & Computer Science
University of Chicago
Chicago, II. 60637, USA
congie@uchicago.cco edu
willett@uchicast edu
Daniel Soudry
Nathan Srebro
Electrical Engineering Department Technion, Israel Institute of Technology Haifa, Israel
Toyota Technological Institute at Chicago Chicago, II. 60637, USA nati@ttic. edu
daniel. soudry@technionn ac.
ABSTRACT
We give tight characterization of the (vectorized Euclidean) norm of weights required to realize a function f IRd -> IR as a single hidden-layer ReLU network with an unbounded number of units (infinite width), extending the univariate char- acterization of "Savarese et al. (2019) to the multivariate case.
INTRODUCTION
It has been argued for while, and is becoming increasingly apparent in recent years, that in terms of complexity control and generalization in neural network training, "the size [magnitude] of the weights is more important then the size [number of weights or parameters] of the network" (Bartleti, 1997 Neyshabur al., [0144 Zhang al. 2016). That is, inductive bias and generalization are not achieved by limiting the size of the network, but rather by explicitly (Wei et al.) 2019) or implicitly
(Nacson et al. 2019 Lyu & 2019) controlling the magnitude of the weights.
In fact, since networks used in practice are often so large that they can fit any function (any labels) over the training data, reasonable think of the network as virtually infinite-sized and thus able to represent essentially all functions. Training and generalization ability then rests on fitting the training data while controlling, either explicitly or implicitly, the magnitude of the weights. That is, training searches over all functions, but seeks functions with small representattonal cost, given by the minimal weight norm required to represent the function. This "representational cost model
of function" is the actual inductive bias of learning- the quantity that defines class, and the functional we are actually minimizing in order to learn. Understanding learning with overparameterized (virtually infinite) networks thus rests on understanding this "representational cost", which is the subject of our paper. Representational cost appears to play an important role in generalization performance; indeed Mei & Montanari (2019) show that minimum norm solutions are optimal for generalization in certain simple cases, and recent work on "double descent" curves an example of this phenomenon (Belkin et al.) 2019 Hastie et al.) (219)).
We can also think of understanding the representational cost as asking an approximation theory question: what functions can we represent, or approximate, with our de facto model class, namely the class of functions representable with small magnitude weights? There has been much celebrated work studying approximation in terms the network size, i.e., asking how many units are necessary in order to approximate target function (Hornik et al. 1989 Cybenko 1989 Barron 1993 Pinkus, 1999]. But if complexity is actually controlled by the norm of the weights, and thus our true model class is defined by the magnitude of the weights, we should instead ask how large norm is necessary in order to capture a target function. This revised view of approximation theory should also change how view issues such depth separation: rather then asking how increasing depth reduce

---

Published as a conference paper at ICLR 2020
the number of units required to fit function, we should instead ask how increasing depth can reduce the norn required, i.e., how the representational cost we study changes with depth.
Our discussion above directly follows that Savarese al. (2019), who initiated the study of the representational cost in term of weight magnitude. [Savarese et al. considered two-layer (i.e., single hidden layer) ReLU networks, with unbounded (essentially infinite) number of units, and where the overall Euclidean norm (sum of squares of all the weights) is controlled. (Infinite width networks of this sort have been studied from various perspectives by e.g., [Bengio al. (2006); Neyshabur eet al. (2015); Bach (2017); Mei et al. (0188). For univariate functions f R R, corresponding networks with single oieedimmaa imput and a single output. [Savarese et al. obtained a crisp
and precise characterization of the representational cost, showing that minimizing overall Euclidean
norm of the weights is equivalent to fitting a function by controlling:
max ( (1r"(()) (1))dr 1f())oo +[ r(tco)))
While this is an important first step, we are of course interested also in more than a single one- dimensional input. In this paper we derive the representational cost for any function f: R IE in any dimension d. Roughly speaking, the cost is captured by:
Il RI 1)/2 fAlla
where R is the Radon transform, A is the Laplacian, and o is a partial derivative w.r.t. the offset in the Radon transform (see Section an explanation of the Radon transform). This characterization is rigorous for odd dimensions d and for functions where the above expressions are classically well- defined (i.e., smooth enough such that all derivatives are finite, and the integrand in the Radon transform is integrable). But for many functions of interest these quantities are not well-defined classically. Instead, in Definition [ we use duality to rigorously define a semi-norm [| that captures the essence of the above quantities and is well-defined (though possibly infinite) for any f in any dimension. We show that |lfll precisely captures the representational cost of f. and in particular is finite if and only if f can be approximated arbitrarily well by bounded norm, but possibly unbounded width, ReLU network. Our precise characterization applies to an architecture with unregularized bias terms (as in Savarese et al. (2019) and single unregularized linear unit otherwise a correction accounting for a linear component is necessary, similar but more complex than the term ( + J'(+o)) in the univariate case, i.e., (T.
As we uncover, the characterization of the representational cost for multivariate functions is unfor- tunately not as simple as the characterization ①1 in the univariate case, where the Radon transform degenerates. Nevertheless, it is often easy to evaluate, and is powerful tool for studying the rep- resentational power of bounded norm ReLU networks. Furthermore, as detailed in Section 5.5 there is no kernel function for which the associated RKHS norm is the same as 2 i.e. training bounded norm neural networks fundamentally different from kernel learning. In particular, using our characterization we show the following:
All sufficiently smooth functions have finite representational cost, but the necessary degree of smoothness depends on the dimension. In particular, all functions in the Sobolev space Wd++.. (Rd)), i.e., when all derivatives up order d + 1 are L bounded,, have finite representa- tional cost, and this cost can be bounded using the Sobolev norm. (Section 5.T)
We calculate the representational cost of radial "bumps", and show there are bumps with finite support that have finite representational cost in all dimensions. The representational cost increases as 1/s for "sharp" bumps of radius E (and fixed height). (Section 5.2)
In dimensions greater than one, we show a general piecewise lincar function with bounded support has infinite representational cost (i.e., cannot be represented with bounded norm, even with infinite networks). (Section 3.3)
We obtain depth separation in terms of norm: we demonstrate a function that is representable using a depth three ReLU network (i.e., with two hidden layers) with small norm weights, but cannot be represented by any bounded-norm depth two (single hidden layer) ReLU network. As far as we are aware, this is the first depth separation result in terms of the norm required for representation. (Section 5.4
2

---

Published as a conference paper at ICLR 2020
Related Work Although the focus of most previous work on approximation theory for neural networks was on the number of units, the norm the weights was often used as an intermediate step. However, this use does not provide an exact characterization of the representational cost, only a (often very loose) upper bound, and in particular does not allow for depth separation results where lower bound is needed. See Savaress et al. (2019) for detailed discussion, e-g., contrasting with the work of Barron 1993 1994).
The connection between the Radon transform and two-layer neural networks was previously made by CCrrrlll & Dickinson (189)) and Ito (199T). who used it to obtain constructive approximations when studying approximation theory terms of network size (number of units) for threshold and sigmoidal networks. This connection also forms the foundation of ridgelet transform analysis of functions Candès & Donoho (1999): Candee) (T999). More recently, [Sonoda & Murata (2017) used ridgelet transform analysis to study the approximation properties of two-layer neural networks with unbounded activation functions, including the ReL.U.
While working on this manuscript, we learned through discussions with Matus Telgarsky of his related parallel work.
particular, [Bailey et al. (2019): Ji et al. (2019) obtained a calculation formula for the norm required to represent a radial function, paralleling our calculations in Section 5.2 and used it to show that sufficiently smooth radial functions have finite norm in any dimension, and studied how this norm changes with dimension.
2 INFINITE WIDTH RELU NETWORKS
We repeat here the discussion of Savarese et al. (019) defining the representational cost of infinite- width ReLU networks, with some corrections and changes that we highlight. Consider the collection of all two-layer networks having an unbounded number of rectified linear units (ReLUs)) ie., all
ge gd R defined by
g0(x)) = a w.w x - -b,1+ + for all x E Rd
(3)
with parameters 0 (k: W [w1,... .... wx), b- [b_. by] a [a...... a&] c)., where the width k E I is unbounded. Let θ be the collection of all such parameter vectors 8. For any O E θ we let C(0) be the sum of the squared Fuclidean norm of the weights in the network excluding the bias terms, i.e.
&
((0) (1W1 [|a|
Σ (1 la,12)
and consider the minimal representation cost necessary to exactly represent function f E Rdd IR R(f) = inf C(B) s.t. f 90-
(5)
8cB
By the 1-homogeneity of the ReLU, it is shown in Neyshabur et al. (2014) (see also Appendix A of Savarese et al. (2019)) that minimizing C(0) is the same as constraining the inner layer weight vectors {w, Ji=1 to be unit norm while minimizing the form of the outer layer weights a. Therefore, letting O' be the collection of all 0 E θ with each w; constrained to the unit sphere gd-1 : (w IR | = =1), we have
R(S) = inf ||a||] 8.1. f= go- reer
(6)
However, we see R()) is finite only if is exactly realizable a finite-width two layer ReLU network, i.e., ff must be a continuous piecewise linear function with finitely many pieces. Yet, we know that any continuous function can be approximated uniformly compact sets by allowing the number of ReLU units to grow to infinity. Since we are not concerned with the number of units, only their norm, modify our definition of representation cost to capture this larger space of functions, and "
R()) = lim inf C(0) s.l. (g)(#) - f(x) < A || & 1/e and go (0) = S(0) Eee'
(7)
'Our definition of R(f) differs from the one given in Savarese et al.
2019
We require [go(x) f(x) <
on the ball of radius 1/e rather than all IRd, and we additionally require go are needed to ensure (7) and (9) are equivalent. Also, we note the choice of zero in the condition go (0) = f(0)
(O)) These modifications
is arbitrary and can he replaced with any point 3o E Rd.
3

---

Published as a conference paper at ICLR 2020
In words, R(f) is the minimal limiting representational cost among all sequences of networks verging to f uniformly (while agreeing with f at zero).
Intuitively, if R(f) is finite this means is expressible as "infinite-width" two layer ReLU net- work whose outer-most weights are described by density a(w, b) over all weight and bias pairs (w, b) E gd-1 R. To make this intuition precise, let M($ x R) denote the space of signed measures a defined on (w, b) E gd-1 x R with finite total variation norm ||a||| = fg--1xx d/ (i.e., the analog of the L' norm for measures), and let E R. Then we define the infinite-width two-layer ReLU network ha,e (or "infinite-wiie width net" for short) by
ha.c(0)) = Jgd R
([w x - 11+t - -[bb]+ da(wr, b) +
(8)
We prove in Appendix C that R(f) is equivalent to
min R()) (AM)(((--)))ecee
||o|| 8.l. f ha.e
(9)
Hence, learning an unbounded width ReLU network by fitting some loss functional L(-) while controlling the Euclidean norm of the weights C(0) by minimizing
inf L(ge) + AC(O)
(10)
is effectively the same learning function by controlling R()):
min TU)) + AR(J).
(11)
f +R
In other words, R()) captures the true inductive bias of learning with unbounded width ReLU networks having regularized weights. Our goal is then to calculate R(f) for any function f Rd + R. and in particular characterize when finite in order to understand what functions can be approximated arbitrarily well with bounded norm but unbounded width ReLU networks.
2.1 SIMPLIHICATION VIA UNREGULARIZED LINEAR UNIT
Every two-layer ReLU network decomposes into the sum of a network with absolute value units plus linear par As demonstrated by Savarese al. (2019) in the 1-D setting, the weights on the absolute value units typically determine the representational cost, with a correction term needed if the linear part has large weight. To allow for cleaner formulation of the representation cost without this correction term, we consider adding in one additional unregularized linear unit v x (similar to a "skip connection") to "absorb" any representational cost due to the linear part.
Rdd we define the class of unbounded with two-layer ReLU networks g with a linear unit by ge (..()))) (x) = go (xx) + T æ where go as defined (3) and associate ga,v with the same weight norm C(0) as defined in (4) (i.e., we exclude the norm of the weight on the additional linear unit from the cost). We then define the representational cost (J) for this class of networks by
Namely, for any A E θ and
RT)) lim inf e++
C(0) s.l. (g), [(x)) Se V ||:||| S $// and go = /(0)
(12)
Likewise, for all a E M( RR, v E Rd, R. we define an infinite width net with a linear unit by (ax) : ha,e(x) + t x. We prove Appendix that (f())) is equivalent to:
Ri(
min
||a||| s.l. f = ha.v..
(13)
dEM(SttixB) .eE
In fact, we show the minimizer of [13 is unique and is characterized as follows:
"Our definition of ha.s also differs from the one given in Savarese al. (2019) To ensure the integral well-defined, we include the additional -[-b]+ term in the integrand. See Remark in Appendix for more discussion on this point. Such decomposition follows immediately from the identity [t]+ ( + +)
4

---

Published as a conference paper at ICLR 2020
Lemma 1. Rı(f)
||a [11 where a+ M(S R) is the unique even measurd such that f f o some v E RR", C E R.
The proof of Lemma 1 is given in Appendix D The uniqueness in Lemma | allows for more explicit characterization Rí (f) in function space relative to R(f), as we show in Section
THE RADON TRANSFORM AND ITS DUAL
Our characterization of the representational cost in Section is posed in terms of the Radon trans- form -a transform that is fundamental to computational imaging, and whose inverse is the basis of image reconstruction in computed tomography. For an investigation of its properties and appli- cations, see Helgason (199)). Here we give a brief review of the Radon transform and its dual as needed for subsequent derivations; readers familiar with these topies skip to Section 4
The Radon transform R represents a function f : R + R in terms of its integrals over all possible hyperplanes in IRd, as parameterized by the unit normal direction to the hyperplane E gd-1 and the signed distance of the hyperplane from the origin b E R:
f(x) ds(x:) for all (w, b) E sd R R R(f)(w : - Tw==bb
(14)
where ds((r) represents integration with respect (d-1))dimensione) surface measure on the hyper- plane w x = b. Note the Radon transform is an even function, i.e., Rif (w, b) = (-f((-w) -b) for all (w, b) E gd-1 x R. since the equations T x b and w æ - determine the same hyperplane. See Figure for an illustration of the Radon transform in dimension d= = 2.
The Radon transform invertible for many common spaces of functions, and inverse a compo- sition of the dual Radon transform R (i.e., the adjoint of R) followed by a filtering step in Fourier domain. The dual Radon transform R maps function @ Sd-1 1 x R + to a function over E I2d by integrating over the subset of coordinates (w, b) S gd-1 x R corresponding to all hyperplanes passing through x:
Rd (p)(x) = [ (pw, w 2) dw for all æ E Rd -ga-1
(15)
where dw represents integration with respect the surface measure of the unit sphere Sd-1, The filtering step given by (d 1)/2-power of the (negative) Laplacian (d)) where for any > 0 the operator (- e/22 is defined in Fourier domain by
(-A)af2 f(E) |I]| F(E),
(16)
using ](E) == (2m) dd2 g(x)) -E" dx to denote the d-dimensional Fourier transform at the
Fourier domain (frequeecy) variable & E Hd. When d is odd, (-A)(d-1)/ is the same as applying the usual Laplacian (d 1)/2 times, i.e., (-A)(d-1)/² = (-1) (d- 11/2, while if d is even it is a pssudo-differentia. operator given by convolution with a singular kernel. Combining these two operators gives the inversion formula f = 7a(-A) ()((A))ee (d-1))/2 (R. where " a constant depending dimension d, which holds for f belonging to many common function spaces (see, e.g., Helgason (1999)).
The dual Radon transform is also invertible by similar formula, albeit under more restrictive con- ditions on the function space. We use the following formula due to Solmon (1987) that holds for all Schwartz class functions" on gd-1 x R, which denote by S(S R):
Lemma (Solmon (9877). I is an even function i.e., sf--w, -b) = v(w, b) for all (w, b)
gd x R, belonging to the Schwartz class S(gd-1 R), then
TaR[(-A) (d- 11/2 (+}) =
(17)
where Ya- 2-2
Roughly speaking. measure a even if ((w,)) = al ww b) for all (w, E gd-1 see Appendix for a precise definition.
w.
Lie., functions y gd-1 R R that are C smooth such that ((w, b) and all its partial derivatives
decrease faster than O(bb--) as |b] + no for any N 2 0
'The assumption that sp even is necessary since odd functions are annihilated by R".
5

---

Published as a conference paper at ICLR 2020
4 REPRESENTATIONAL COST IN FUNCTION SPACE: THE R-NORM
Our starting point is to relate the Laplacian of an wifth net to the dual Radon transform of its defining measure. In particular, consider an infinite width net f defined in terms of a smooth density a(w, w. b) over gd-1 x R that decreases rapidly to zero with [b] + co, so that we can write
[
f(x)
gd-1 ([w x b/+ - [-b]+) alwr b) dw db vJa c.
(18)
Differentiating twice inside the integral, the Laplacian Af(x) ii=l 02 O2, fxx) given by
[ ga-+xx 8(w x b)a(w, b) dw db
[ alw, w ToTa x)) dw.
Af(x)
(19)
gd-1
where 5()) denotes Dirac delta] We see that the right-hand side of (99 is precisely the dual Radon transform of a, Le., we have shown Af = R {a). Applying the inversion formula for the dual Radon transform given in (I7) to this identity, and using the characterization of R₁ (f) given in Lemma ! immediately gives the following result.
Lemma 3. Suppose f = ee some a E S (3d-1 R) with even, and v E Rd, ce E R. Then and (f) = (/////1///// where "ia = 2(24)2-I-
a == (
This result suggests that more generally if we are given any function f. we ought to be able to compute R₁ (f) using the formula in Lemma The following result, proved in Appendix shows this is indeed the case assuming f is integrable and sufficiently smooth, which for simplicity state in the case of odd dimensions d. [
Proposition 1. Suppose d is odd. If both f E (RR)) and A Ad++1)/2 L' (RR), then
(f) = (AA
= 7al1 R(fHI < cc.
(20)
Here used the intertwining property of the Radon transform and the Laplacian to write ((A(+)))22) R[f) (see Appendix f more details).
Given these results, one might expect for an arbitrary function f we should have (f) equal to one of the expressions in (20). However, for many functions of interest these quantities are not classically well-defined. For example, the knite-width ReLU net f(x) E.= a a x b,l+ is a piecewise linear function that is non-smooth along each hyperplane w x b,, so its derivatives can only be understood in the distributional sense. Similarly, in this case the Radon transform of f not well-defined since unbounded and not integrable along hyperplanes.
Instead, we use duality to define functional (the "R-norm") that extends to the more general case where is possibly non-smooth or not integrable along hyperplanes. In particular, we define a functional on the space of all Lipschitz continuous functions The main idea is to re-express the L norm in (20) as a supremum of the inner product over a space of dual functions v : 8d-1 x R + R. i.e., using the fact R* is the adjoint of R and the Laplacian A is self-adjoint we write
| (4+1/2+1)22 2fIli
sup (R(A(4+1)) f}. b)
sup |
(f. (d+ 1)/2 (+))
(21)
1| 11
then restrict up to space where A (d--1)/2R' (v} is always well-defined. More formally, we have: Definition 1. For any Lipschitz continuous function f: Rdd + R define its R-nomm TO [| by
|l = sup { (-A) (v)) & E S(gd R), th even || S 11] (22)
where Pa 2(2 S(S R) is the space of
on Sd-1 x IR and (f.g) ==
Sae fx)) (d))...... If f is not Lipschitz we define || +00.
" 'Here we use Dirac deltas informally; for a formal derivation of (99 see Lemma 9 in Appendix D 'For d even, Proposition [ holds with the pscudo-differentia operators (d+1// and (-og) t +1/2 1)/2 in place of A (d+1)/2 and ar.+1 see Section
RReall that f Lipschitz continuous if there exists constant I. (depending on f) such that [f(z) - f(y) < T.I|a: - y/l for all æ. y E Rdd.
Strietty speaking, the functional ||-11pe is not norm, but it is semi-norm on the space of functions for which it finite; see Appendix

---

Published as a conference paper at ICLR 2020
We prove in Appendix that the R-norm is well-defined, though not always finite, for all Lipschitz functions and, whether finite or infinite, it is always equal to the representational cost R1(-): (-):
Theorem 1. Rí (f) = ll R for all functions f. In particular. R1(f) is finite if and only if f is Lipschitz and Il R is finite.
We give the proof of Theorem I in Appendix D but the following example illustrates many of its key elements.
We compute R1 (f) l in the case where f finite-width two-layer ReLU nerwork. First, consider the case where consists of single ReLU unit: f(x) ag [w] [w by]+ for some E I and (w1, b1) E Sa-1. Note that Af(x) = a a | x -bb)) in a distributional sense, iee. for any smooth test function up we have (AS,i) = (J,Di) = a1 (p(x))((w) x bi bi)dæ
Example 1.
a R (Rm,,) bt) So for any even 1/ E S(S x RR) we have
(olf (w)) 7a(Af, (-) =anaR((-A)) ((-))(-11/222 (vi))(
{1b})
(23)
(24)
=aiv(w1,br b1)
(25)
where in the last step we used the inversion formula (17) Since the supremum defining [I is over
all even 1/ E SSd-11
1gg-1110 x IR.) such that [| S 1, taking any v² such that vi" (un, b1) = sign(a1) and |oi). The general case now follows by linearity: let
11b b1)l S otherwise, we see that [l.
1--b bi]+ such that all the pairs {(w, ((w;,b:)) b,)] U((-w; -b:))= are distinct. f(x)) = Ex= ai [w]] x
Then for any v E SS(S-1 x TR.) we have
k
- -aalf, (- (1/1111/2R (w1) = Σ
a, bi).
(26)
i=1
Letting v/* be any even Schwartz function such that vi (w; b.) v/- (-w;, -b;) (ggn(a)) for all i I....,k k and (w,, b)] S 1 otherwise, we see that (f) [f = = lay).
The representational cost R(f) defined without the unregularized linear unit is more difficult to characterize explicitly. However, we prove that [(() is finite if and only if [|/l] is finite, and give bounds for R(f) in terms of [|flle and the norm of the gradient of the function "at infinity", similar to the expressions derived in Savarese et al. (2019) in the 1-D setting.
Theorem 2. R()) is finite if and only if ll is finite, in which case we have the bounds
max mal(1l/l : /(0 - R() | + 2(IV)((
(27)
where f(c))) = lim aar I f -| Vf dd(xdds(x) E Rd with ca Sga dw In particular, if V [(00) 0 then R() (J) = [|
2////2 Tid/25+
We give the proof of Theorem 2 in Appendix The lower bound max || fll 2 foo)) is anal- ogous to the expression for the TD representational cost 1 obtained in Savarese al. (2019). From this, one might speculate that R(()) is equal to max(Ilf I 2 [oc)))))) However, in Appendix we show this is not the case: there are examples of functions f in all dimensions such that TE(f) attains the upper bound non-trivial way (e.g., f(x, y)
|a| + y =).).
4.1 PROPERTIES OF THE R-NORM
In Appendix F we prove several useful properties for the R-norm. In particular, we show the R- norm is fact a semi-norm, i.e., it is absolutely homogeneous and satisfies the triangle inequality, if and only if ff is affine. We also show the R-norm is invariant to coordinate
while |] R translation and rotations, and prove the following scaling law under comtractions/dilation.
Proposition 2. fz) == fx//E) for any = > 0, then Ilfe R E llfll
Proposition 2 shows that "spikey" functions will necessarily have large R-norm. For example, let ff be any non-negative function supported on the ball of radius I with maximum height I such that || is finite. Then the contraction fs is supported the ball of radius with maximum height
7

---

Published as a conference paper at ICLR 2020
1, but lIfe|R IIflll blows up - O. From generalization perspective, the fact that the R-norm blows up with contractions is a desirable property, since otherwise the minimum norm fit to data would be spikes data points. In particular, this is what would happen if the representational cost involved derivatives lower than + 1, and so in this sense it is not a coincidence that || involves derivatives of order
for more discussion this point Section
Finally, we also show that having finite R-norm implies strong conditions in Fourier domain. In particular, show that if the R-norm of an L function is finite then its Fourier transform must decay rapidly along every ray. A precise statement is given in Proposition 12 in Appendix F
5 CONSEQUENCES, APPLICATIONS AND DISCUSSION
Our characterization of the representational cost for multivariate functions in terms of the R-norm unfortunately not as simple as the characterization in the univariate case. Nevertheless, it is often easy evaluate, and is powerful tool for studying the representational power of bounded norm ReLU networks.
5.1 SOBOLEV SPACES
Here we relate Sobolev spaces and the R-norm. The key result is the following upper bound, which proved in Appendix G
Proposition 3. !f IRd + is Lipschitz and
(-A) (- lR S Cr)al(-A))att)) (d+
exists in a weak sense 11 then
(28)
where ca = Iga dw
2/2 T(d/2)'
and 7/d = 2(2
Recall that if the dimension d is odd then (-A)(d+1)) is just an integer power of the negative Laplacian, which is a linear combination partial derivatives of order d + 1. Hence, we have [K--))d+1)/2 fll S
where [[ w is the Sobolev norm given by the sum of the L'-mmrm of f and the L'-norms of all its weak partial derivatives up to order d + 1. This gives the following immediate corollary to Proposition
Corollary 1. Suppose is odd. If f belongs to the Sobolev space Wd+1.1 (RR), i.e., J and all its weak derivatives up to order d 1 are in L (RR),, then [|]l| is finite and || ca7aal//llwet..
The (d + o)-order smoothness in Corollary [ is optimal in the sense that the R-norm cannot be uniformly bounded by -type Sobolev norm with smoothness of lower order. To see this, let D represent any s-order partial derivative, and f be any compactly supported function such that | and [ are finite. Then the contraction (x) == fwæ/s) obeys the scaling law D = ed=a| | D fll and so [l.sllw... = O( as + 0. Also, by Proposition 2 we have lf -- Il So the only way [e could be uniformly bounded by ||fellw-.. - 0 is if ddsd+1.
The smoothness requirements in Corollary D are also necessary from generalization perspective. In particular, if the representational cost were bounded by I -norm of derivatives order strictly less than d, could not expect generalization from finite data. This is because the data could be fit exactly with a sum of spike functions whose representational cost could be made arbitrarily small by shrinking the support of the spikes.
Here it is also interesting to compare with (Bach 2017 Proposition 5). There it is shown that the space of all two-layer infin ReLU networks defined by I,2-bounded densities contains Sobolev space W' with > (d + 1)/2. The considering an Ltytype Sobolev norm, since by similar argument to the above, is the scaling that ensures contractions fo have unbounded norm as E + O.
d/2 scaling of smoothness is necessary when
Le,, for all compactly supported smooth functions there exists locally integrable function E L (R") such that (-A)dd++1/2,, da: f gip dar
8

---

Published as a conference paper at ICLR 2020
5.2 RADIAL BUMP FUNCTIONS
To help build intuition with the R-norm and illustrate its scaling with dimension, here we study the case where is a radially symmetric function, i.e., f'()) g([2=]]) for some function g [0, xc)
R. In this case, the R-norm is expressible entirely in terms of derivatives of the radial profile function
g. as shown the following result, which is proved in Appendix H
Proposition 4. Suppose d is odd. If L' (R") with f(x) g[1+=||) then
2 (d 2
((bt))(()) db where p(b) = I, s(t) - 2t)
(29)
For example, in the d = 3 dimensional case, we have
00 l60' + +00g (d =3)
|l =2
(30)
More generally, for any odd dimension d 2 3 simple induction shows
29 is equivalent to
ll (d-2) 2)! J. (Qalg)b)]db
(31)
where Qa is a differential operator of degree (d + 33/22 having the form Qa Ei Pk. (b)
(d+3)/2
where each pk,a(b) is a polynomial in of degree 2-2. In particular, if the weak derivative ((+ 1)/2 exists and has bounded variation, then || is finite.
Example 2. Suppose d 2 3 is odd. Consider the radial hump function fax(w) ((=x)(12=11)) with IRd where for any integer l > O we define
(11 12- if0 <r<c
(r)
(32)
ifr 11,
We prove flfalll is finite if and only if 2 d+1 (see Appendix H. To illustrate the scaling with
2
dimension in Appendix we also prove that for the choice ka (d+ 1)+1)/² 12/ we have the bounds
(d 5) < Ilfa, RR I 2d(d + 5), hence [l lR ~ & Similarly, by the dilation property (2.
contraction of Ja,ka to the ball of radius has R-norm scaling ~ d² de/e.
The next example shows there there is universal choice of radial bump function in all (odd) dimensions with finite R-norm:
Example Suppose 3 odd. Consider the radial hump function f(x) = a[[[==]] with Rd where
if0 705r<4
s(r)
(33)
ifr N
Since is smo-hh and its derivatives of all orders are L -boundde,, f has finite R-norm by Proposition
5.3 PIECEWISE LINEAR FUNCTIONS
Every finite-widis width two-layer ReLU network a continuous piecewise linear function. However, the reverse is not true. For example. in dimensions two and above no compactly supported piecewise linear function expressible as finite-widhe two-layer ReLU network. natural question then is: what piecewise linear functions are represented by bounded norm infinite-width width nets, i.e., have finite R-norm? In particular, do compactly supported piecewise linear functions have finite R-norm? Here show this is generally not the case.
Proposition 5. Suppose f IRd + IR is continuous piecewise linear function with compact support, where the boundary sets between regions satisfy additional mild conditions. Then f has infinite R-norm.
1he existence of such radial function was noted in parallel work by Matus Telgarsky. Discussions with Telgarsky motivated construct and analyze using the R-norm.

---

Published as a conference paper at ICLR 2020
See Appendix ! for proof and for the precise conditions needed the boundary sets. Roughly speaking, the result holds for any "generic" piecewise linear function with compact support, i.e., function does not satisfy these conditions, then some small perturbation of the function does.
This result suggests that the space of piecewise linear functions expressible as a bounded norm wifth two-layer ReLU network is not qualitatively different the space of unite-width net- works. We go further and make the following conjecture:
Conjecture 1. A continuous piecewise linear function f has finite R-norm if and only if it is exactly representable by Smite-width two-layer ReLU network.
5.4 DEPTH SEPARATION
In an effort to understand the power of deeper networks, there has been much work showing how some functions can be much more easily approximated ferms of number of required units by deeper networks compared to shallower ones, including results showing how functions that can be well-approximated by three-layer networks require a much larger number of units to approximate if using two-layer network (e.g. Pinkus (199)); Tellarsky (2016); Liang & Srikant (2016); Safran & Shamir (2017); Yarotsky (2017). The following example shows that, also in terms of the norm, such depth separation exists for ReLU nets:
12-1211110 | is a compuctly supported piecewise linear function satisfying the conditions needed for Proposition 5 hold 133 hence has infinite representa- tional cost as two-layer ReLU network (R(f) Rı +00), but can be exactly represented as a finite-widtt three-layer ReLU network.
Example 4. The pyramid function [====[1- [1-
=
Interestingly, this result shows that, in terms of the norm, we have qualitative rather then quantita- tive depth separation: the minimal norm of the weights needed to represent the function with three layers is finite, while with only two layers it is not merely very large, but infinite. In contrast, in standard depth separation results, the separation is quantitative: we can compensate for decrease in depth and use more neurons to achieve the same approximation quality. It would be interesting to further strengthen Example by obtaining a quantitative lower bound on the norm required to e-approximate the pyramid with an infinite-width two-layer ReLU network.
5.5 THE R-NORM IS NOT A RKHS NORM
There is an ongoing debate the community on whether neural network learning can be simulated or replicated by kernel machines with the "right" kernel. In this context, it is interesting ask whether the inductive bias we uncover can be captured by kernel, or in other words, whether the R-norm is an RKHS-norm The answer is no:
Proposition The R-norm is not an RKHS norm.
This is seen immediately by the failure of the parallelogram law to hold. For example, [w, a]+ with wh, W2 Sd-1 distinct, then by Exam- ple I we have [[ll R = llfelR = 1, while [| + fell = Ilfi fallR = 2, and so
if fi (x) [w:] xx) +. f2
2 fi Ilfelll
* IIfi fall llfi - fall
5.6 GENERALIZATION IMPLICATIONS
Neyshabur et al. (2015) shows that training an unbounded-widhe neural network while regularizing the le norm of the weights results in a sample complexity proportional to varian 15 of R(f). This
paper gives an explicit characterization of R(f) and thus of the sample complexity of learning function using regularized unbounded-width neural networks.
More precisely, it satisfies condition (b) of Proposition 16 Appendix
"To he precise, the R-norm is only a semi-norm the space of functions for which it is finite, but it becomes a norm on quotient space obtained by modding out by all functions with zero R-norm, iee, all affine functions. The question is whether the R-norm on this quotient space is an RKHS norm. Their analysis does allow for unregularized hias, but be extended to allow for it.
10

---

Published as a conference paper at ICLR 2020
ACKNOWLEDGMENTS
We are grateful Matus Telgarsky (University Illinois, Urbana-Champaign) for stimulating dis- cussions, including discussing his yet unpublished work with us. In particular, Telgarsky helped us refine our view of radial bumps and realize a fixed radial function can have finite norm in all dimen- sions. We would also like to thank Guillaume Bal (University of Chicago) for helpful discussions regarding the Radon transform, and Jason Altschuler (MIT) for pointers regarding convergence of measures and Prokhorov's Theorem. Some of the work was done while DS and NS were visiting the Simons Institute for Theoretical Computer Science as participants in the Foundations of Deep Learning Program. NS was partially supported by NSF awards 1764032 and 1546500. DS was partially supported by the Israel Science Foundation (grant No. 31/1031), and by the Taub Foun- dation. RW and GO were partially supported by AFOSR award 199550-18--0166- DOE award DE-ACO2-06CH 1357, and NSF awards OAC-1934637 and DMS- 1930099.
REFERENCES
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-66 681, 2017.
Bolton Bailey, Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Approximation power of random neural networks. arXiv preprint /rXiv:/906.077099 2019.
Andrew R Barron. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions Information Theory, 39(3):930-945, 1993.
Andrew R Barron. Approximation and estimation bounds for artificial neural networks. Machine learning, (()):115-133, 1994.
Peter L Bartlett, For valid generalization the size the weights more important than the size of the network. In Neural Information Processing Systems (NeurlPS), pp. 134-140, 1997.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconeiling modern machine- learning practice and the classical birs-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 158432)):5889----
2019.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. In Neural Information Processing Systems (NeurIPS), pp. 123-130, 2006.
Vladimir Bogachev. Measure theory, volume 2. Springer Science & Business Media, 2007.
Jan Boman and Filip Lindskog. Support theorems for the Radon transform and Cramér- Wold theo- rems. Journal of theoretical probability, 22(3)x683-710, 2009.
Emmanuel J Candès. Harmonic analysis of neural networks. Applied and Computational Harmonic Analysis, 6(2):197-218, 1999.
Emmanuel J Candès and David L Donoho. Ridgelets: A key to higher-dimensional intermittency? Philosophical Transactions the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, (5761))):22495 2509, 1999.
Sean M. Carroll and Bradley W. Dickinson. Construction neural nets using the Radon transform. In International Joint Conference on Neural Networks, volume pp. 607-611, 1989. doi: 10. 1109/JCNN 1989. 118639.
George Cybenko. Approximation by superpositions sigmoidal function. Mathematics control, signals and systems, 2(4):303-314, 1989.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560, 2019.
Sigurdur Helgason. The Radon transform. Springer, 1999.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural nefworks, -366,,99336,, 1989.

---

Published as a conference paper at ICLR 2020
Yoshifusa Ito. Representation of functions by superpositions of step sigmoid function and their applications to neural network theory. Neural Networks, 4(3):385 -3944, 1991.
Ziwei Ji, Matus Telgarsky, and Ruicheng Xian. Neural tangent kernels, transportation mappings, and universal approximation. arXiv preprint arXiv:1910.0695,, 2019.
Shiyu Liang and Srikant. Why Deep Neural Networks for Function Approximation? In ICLR, 2016. / org abs
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint
2019.
Paul Malliavin. Integration and probability, volume 157. Springer Science & Business Media, 2012.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptoties and double descent curve. arXiv preprint arXiv: 053555 2019.
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)E7665--767)) 2018.
Mor Shpigel Nacson, Suriya Gunasekar, Jason D Lee, Nathan Srebro, and Daniel Soudry. Lexico- graphic and depth-sensitive margins in homogeneous and non-homogeneous deep models. arXiv preprint 1rXXi::905..0325. 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. arXiv preprint arXiv: / /412.6114 2014.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory (COLT), pp. 1376-1401, 2015.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta numerica, 8: 143-195, 1999.
Itay Safran and Ohad Shamir. Depth-Width Tradeoff' in Approximating Natural Functions with Neural Networks. ICML, pp. 1-27, 2017. ISSN 1938-7228. URL http://arxiv.orgg
foos/161... 09887
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look function space? Conference on Learning Theory (COLT), 2019.
Donald C Solmon, Asymptotic formulas for the dual Radon transform and applications. Mathema- fische Zeitschrift, 195(3):321-343, 1987.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233 2017.
Matus Telgarsky. Benefits of depth in neural networks. COLT, Feb 2016. URL httt:://aaxxxi 04485
Colin Wei, Jason D Lee, Qiang Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. arXiv preprint arXiv:1810.05366 2019.
Dmitry Yarotsky. Error bounds for approximations with deep ReLU networks. Neural Networks, 94:103-114, 2017. ISSN 18792782. doi: 10. (001/f/neunet.2011777.00000
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiy: 16/ 1,03530, 2016.
12

---

Published as a conference paper at ICLR 2020
W
5 b)
10
f(()
10
0 s.t. (cos(f), (ci(())sinn())
(a) Radon transform
(b) Dual Radon transform
Figure I: Radon transform. (a) Illustration of the Radon transform in equation 14 in dimension d = 2. The
red line of points satisfying " defines the domain of the integral line orientation (angle relative to coordinate axes) and determines
(zz) where determines the offset from the origin. (b) Illustration
of the support of the Radon transform for / [() = 8(x (-1, - 1)) (red), f(x) = 8(x (1,0) 0)) (green), and f(x) 8( (0, 1)) (blue). If function is superposition of such functions, then R(f) the sum of the curves in (b); this is typically referred
"sinogram". Furthermore, the dual Radon transform in equation 115 integrates any function pow b) over curves like one of the three in (b).
APPENDICES
A ADDITIONAL PROPERTIES OF RADON TRANSFORM
Figure | illustrates the Radon transform and its dual in dimension d = 2.
We will often use the fact that the Radon transform L' 2'(dd11 RR, i.e., if L (RR) then R(} e L (IE)). In particular, if f L (IR)) then R { is defined almost everywhere on gd-1 x IR and the function R(, is in L (R) for all w E Sd-1
bounded linear operator from L (IRd)) to
Here also recall the Fourier slice theorem for the Radon transform (see, e.g., Helgason 1999
Let f L' (RR), then for all a E IR and w E 5d-1 we have
(R = fla ww)
(34)
where Fú indicates the I-D Fourier transform in the offset variable b. From this it is easy to establish the following intertwining property of the Laplacian and the Radon transform: assuming and f are in L (Rd). we have
R(as} = R[
(35)
where O is the partial derivative in the offset variable b. More generally for any positive integer s, assuming f and / are in I,1 (Rd) we have
R(( 2((-A)=/2f] (-08)
(36)
where fractional powers of og can be defined in Fourier domain, same as fractional powers of the Laplacian. particular, (- (-a3)id+ (d)/221)/2 = (HH,))+1 where H the Hilbert transform the offset variable
odd, (-0g) = (-1)@+11/20/*+ while is even,
INFINITE-WIDTH NETS
Measures and infinite-width nets Let be signed measure ||||| = d]a denote its total variation norm. We let (Sd-1 on S 3- xR with finite total variation norm. Since Sd-1 xR is a locally compact space, M ( xR)
16 defined gd-1 x R, and let
x F.
denote the space of measures
16 be precise. we assume a is signed Radon measure; see, e.g., Malliavin 2012) for formal definition. We omit the word "Radon" and simply call a measure avoid confusion with the Radon transform, which central this work.
13

---

Published as a conference paper at ICLR 2020
is the Banach space dual of Co( x R)) the space of continuous functions on sd11 R vanishing
at infinity (Malliavin 2012 Chapter 2, Theorem 6.6), and
||]|| sup {
pp : p E Co (5 R), 11pll = <1}
(37)
For any a E (( x IR and yp E Co(S x R), we often use (a, to denote f (daa.
Any a E M( x) can be extended uniquely to a continuous linear functional on Cs( 1 RR) the space continuous and bounded functions on grl xR. In particular, since the function ypw (w æ b]+ - [-b]+ belongs to Cs x IR), we see that the infinite-width net
ho (x) = Jd x
(ww x b|+ - [-b]+ da w. b)
(38)
is well-defined for all æ E R
Remark 1. Our definition of an widhh net in differs slightly from Savarese et al. (2019): we integrate a constant shift of the ReLU [w x b]= [-b]+ with respect to the measure a(w, b) rather than (w x - b]+ as in Savarese et al. (011)) As shown above, this ensures the integral always well-defined for any measure a with finite total variation. Alternatively, we could have restricted to measures that have finite first moment, i.e, fga- [b] d d/a b) < oc, which ensures
the definition (x) := fga- x daw b) proposed in Savarese et al. (019 is always well-defined. However, restricting to measures with finite first moment complicates the function space description, and excludes from our analysis certain functions that are still naturally defined as limits of bounded norm finite-width networks, and we opt for the definition above instead. In the case that a has a finite first moment the difference between definitions is immaterial since ha and hi are equal up to an additive constant, which implies they have the same representational cost under R()) and R1(.). (-).
Even and odd measures
We say a E M( x R) is even
[
p( (w, S 180 1xB
p(-w,-b)dan b) for all 6o E Co R) (39)
Jsd 1xR
or is odd if
p(-w; w. b))da(w, b) for all ip Cu( x R). (40) 1 -8d-1 xB
s(w, b)da
It is easy show every measure ar (SL-1 x IR) is uniquely decomposable a + a where at is even and a is odd, which we call the even and odd decomposition of a. For example, if a has density u(w, 6) then at the measure with density μ² (w, b) (n(w, b) b)) and a is the measure with density μ (w, b) = (u(w, b) - u ( -b)).
We let M (IPd) denote the subspace of all even measures in M (S x K), which is the Banach space dual of (II)), the subspace of all even functions &p E Co R). Even measures play an important role in our results because of the following observations.
Let MS R) with even and odd decomposition
at + a= Then we have ha hat + ha- By the identity [4]+ + [-0]+ = |4| we can show
ha+ (x) gu 1
(ww b) (bl)da (w, b).
(41)
Likewise, by the identity [t]+ - -1- we have
ha- (2)) 0 xc
(42)
where vo 1/2 fga XR wda (w.b), Hence, ha decomposes into sum of a component with absolute value activations and a linear function. In particular, if f = ha,v,e for some a E M R),e v E Rd, E R. letting a be the even part of a, we always have f = hat, w'.c. for some o E Rd. In other words, we lose no generality by restricting ourselves to infinite width nets of the form h,, where is even (t.e., M (F
We will need the following fact about even and odd decompositions of measures under the total variation norm:
14

---

Published as a conference paper at ICLR 2020
Proposition 7. Let a M( x R) with at + + where at is even and a is odd. Then ||at|1 11 S ||a|| and la 1| I ||]|11-
Proof. For any & E Co( x R) we can write y ++ + p- where p+ b) = ( b) + , -6)) is even and (-(ww, b) 1 (( b) <p--pp w, -6)) is odd. Note that J p da S da+ since pa O. Furthermore, if ( b) I 1 for all (w.b) S x R
that (,+(ww,)) b]1 - (1 b) ( w., bb]l I for all (w,b) gd-1 RR Therefore, in the dual definition of ||a+|l given in (37) it suffices to take the supremum all even functions E Co(Sd-1 x IR) Hence,
{ و da
R) 11pll0 $1}
|alli sup
(43)
/ pdd + ʃ pda :0 : Co 11,1ll s
sup
(44)
{ pdda + pdd : x R),11splo 1 even
2 sup
(45)
{ pdda : E Co( x 1/llx 11 even
sup
(46)
||a 1
(47)
similar argument shows ||a lla $ ||a|]1-
Lipschitz continuity of width nets Define Lip(R to be the space of all real-valued Lipschitz continuous functions on IRd. For any f E Lip(IE"), define |lf := supady x
[(v)
Le., the smallest possible Lipschitz constant. The following result shows that (Rd( is a natural space work in when considering infinite-width nets:
Proposition 8 (Infinite-width nets Lipschitz). Let f for any M(Sd-1 x R), v Rd E R. Then Lip(R") with llflle s
||a]|2 ||00
Proof. First we prove for all even E (P*), |lA S ||al1//2.
By the reverse triangle inequality have |w TuuT Tax b) |w0 y bll < |m0 T (ar y)
for all x y
Rd w 5d-1. E Therefore, using identity (41) for all x, y E Idd we see that
1
[h. (2)) gd xR
(Iw x - -bl-lur Tu y bl) (wr, b)
(48)
2
1
$
|1w0 x se-bi -bl-/w"
/w To
b1| dla:((w.)) b)
(49)
2
xx
1
lw TwT(x: y)ld(a (w.b)
(50)
2
gg 1xR
1
2 |: y y|ll||||1
(51)
which shows ha Lipschitz with |/allz < ||a|11/2.
More generally, for any infinite-width net = ha with a E M( x RR. v E Rd and
c E R. From the even and odd decomposition
at + a we have f hat to where 2 -gg--1x wda (ux, b). Hence, || 22 S 1h//2 Therefore, by the triangle inequality, || < ||at|l// + || 1/ + |||||| S ||a||| + ||.]]. which gives the claim.
Vo 1
C OPTIMIZATION CHARACTERIZATTOO OF REPRESENTATIONAL COST
Here we establish the optimization equivalents of the representational costs R(f) and Rf(f) given in Ø and (13).
15

---

Published as a conference paper at ICLR 2020
As intermediate step, first give equivalent expressions for R(f) and (f( in terms of se- quences finite-width two-layer ReLU networks converging pointwise to f. For this we need to introduce some additional notation and definitions.
We let A(S 1 x IR) denote the space of all measures given by a finite linear combination of Diracs, i... all a E M(Sd-1x x R) of the form Σ a:d(w, ..) for some E IR. (w;, bz) E &d-1 I,, i 1,...k, k, where ((w,b) denotes Dirac delta at location (w, E 5 R. We call any AA($5~11 x R) a discrete measure.
Note there is one-to-one correspondence between discrete measures and finite-width two layer ReLU nets (up to bias term). Namely, for any 0 O' defining a finite-width net go(x)
E a,(2;; x - b,]+ + c, setting a = Σ (,0(mn.hh)) we have = ha,e' with c' = (0)
We write 0 E e' + a E A(Sd-1 x IR) to indicate this correspondence. Furthermore, in this case C(0) = Σー= la =|aa|l
We also recall some facts related to the convergence of sequences of measures. Let Cs R) denote the set of all continuous and bounded functions on Sd-1 x R. A sequence of measures {a,) with 0, E MSd x R) is said to converge narrowly
measure E (S x R) if s - f yp da for all E Ca (Sd-1 x R). Also, a sequence {(r,} ) is called tight if for all & >> 0 there exists compact set Kg C gd-1 x E such that (k5) < E for all n sufficiently large. Every narrowly convergent sequence
measures is tight (Malliavin 2012 Theorem 6.8). Conversely, any sequence {ann } that is tight and uniformly bounded in total variation norm has narrowly convergent subsequence; this is due to a version of Prokhorov's Theorem for signed measures (Bogachev 2007 Theorem 8.6.2).
Now we establish the following equivalent expressions for the representational costs R(-) and R.)..
Lemma 4. For any f : Rdd + let Jo denote the function fo(a:) = f(x) f(0). For R(J) as defined in 7 and Rf) as defined in (2), we have
R() inf lim ||a on E A( x R), has - So pointwise, {an) tight 1 (52)
n-000
and
R1 (f) = inf sup ||aall1 : an E A(5 x xR), Un E Rd, Nan + fo pointwise, {an} right
n-000
(53)
Proof. We prove the identity in (2) for R(f); the identity in 53 for Ri(f) follows by the same argument. Define
Re(f)= = inf C(0) s.t. (x) f(x)] se & | < 1/s and go f(0)
(54)
#eer
so that R(f) lim (f). Also, let L(f) denote the right-hand side of (52)
First, suppose R(f) is finite. Let En 1/n. Then by definition of R(f), for all there exists
On E O' such that ((0))) < Rs (f) En, while g9,, (x) f(x) < En for |||||| - 1/s, and go., (0) f()). Note that On E O' + an E M( -igd-1-0 IR) with go.,. ha..e where c 90, (0)
f(0) and ||a 1 C(Ox). Hence, haw (x) = 90., (a) f(0). and we have [ha,, (x) - fo(x)) =
Igo. (x) f(x) S e. for ||س||| S 1/en. Therefore, ho. + So pointwise, while
lim sup ||a,ll1 S n=0000
(f) + + = R()),
(55)
220000
which shows L(F) S R(f). Finally, it suffices to show {a.,) } has a tight subsequence, since we can reproduce the steps above with respect to the subsequence. Towards this end, define qr (w) = [lw x - bld]aa/ (w,, b). which is well-defined since on, is discrete and has compact support. Then qn is Lipschitz with 1q S ||a,,|1 1 < B for some finite B, hence the sequence {4 } is uniformly Lipschitz. By the Arzela-Ascol. Theorem, {q,,) has subsequence {9m.. that converges uniformly on compact subsets. In particular, 9n, (0) = d a (w. b) S < oo for some L, which implies the sequence {an,) } is tight.
16

---

Published as a conference paper at ICLR 2020
Conversely, suppose L(f) is finite. Fix any 0. Then by definition of L(f) there exists sequence
an E MM x R) + 8, E @' such that lim || exists with lim || [ < ((f) + E,
f(0) converges to f pointwise and satisfies fa for all n. Since, limm- | < L(f) + &, there exists an Ni such that for all n 2 Ni we have ||o II I I(f) + e. By Proposition 8 the Lipschitz constant of fn is bounded above by ||a,Il1 for all n, hence the sequence fn is uniformly Lipschitz. This implies fa + uniformly on compact subsets, and there exists an N2 such that (x) f())] S for all ||||| S 1/s and (0) f() for all n 2 N2. For all n 2 N2, fn satisfies the constraints in the definition of (- Therefore, for all 2 max(N1, N we have
while fa == han.c 90, with
f(0)
Rs (f) C(O,) = [aall1 S L(f)+
(56)
Taking the limit as + O, we get R()) Σ I(.)). Therefore, we have shown R(f) is finite if and only if L(f) is finite, which case R(f) = L(f), giving the claim.
The following lemma shows every infinite-width net is the pointwise limit of sequence of finite- width nets defined in terms of sequence of measures uniformly bounded in total variation norm.
Lemma 5. Let f ha for any a E (Sd-1 x R).u E 12, and R. Then there exists sequence of discrete measures On A(Sd-1 [R] with ||an||i S ||al| such that Jn ham. converges to pointwise.
Proof. For any E M(S--1 x IR) there exists sequence of discrete measures on converging
narrowly to a such that ||a,]]] ||xx| MMallivvin 2012 Chapter 2, Theorem 6.9). Let Jn b.n. Since the function (w, b) + w x bj+
+ is continuous and bounded, we have
fn(x) f(x) for all E Rd i.e. fn + pointwise.
Lemma 6. We have the equivalences
R(f)
min aEM RRR
|aal|2 s.t. = ha,e:
(57)
and
min Ri( aEM(sa- xR) CER
|alll s.l. ha
(58)
Proof. We prove the R(f) case; the (f) case follows by the same argument. Throughout the proof we use the equivalence of R()) given in Lemma and let M(J) denote the right-hand side of (77.
Assume R(() is finite. Then there exists tight sequence {an), 0n E A( x IR) that is uni- formly bounded in total variation norm such that ha, + fo pointwise. Therefore, by Prokhokov's Theorem, {a,, has subsequence {ane) converging narrowly to measure a, hence fo ha- Furthermore, narrow convergence implies ||a|]] < lim sup; |an, ll1 < lim limsupp-po ||a, ll and M(f) lim sup, [|a,,]1. Taking the infimum over all such sequences {a,); have M(f) < R(f).
Conversely, assume M(f) is finite. Let a E M( x R) be any measure such that fo = ha- By Lemma 5 there exists sequence (ax), On A( x RR,, such that ha, > pointwise, while ||a,, S ||a|]2. Hence, R(f) S limsup ||a,|]: ||a||]. Since this holds for any with fo ha. we that R(f) < M(f),, proving the claim.
Now we show that if ff is an infinite-widtt net, R(( is equal to the minimal total variation norm of all measures defining f (in fact, later show for every infinite-width net is defined in terms of unique even measure, whose total variation norm is equal to Rí (f); see Lemma 10
Lemma 7, We have
min Rf(f)= (""
la ll1 s.t. f hat.p.r v.e
(59)
where the minimization is over all even a E M(dd).
17

---

Published as a conference paper at ICLR 2020
Proof. Suppose f h,, e for some M( x R), C R. If a has even and odd decomposition at + a then = hat 0.0 ha-.p.c hat,v', for some v' R.. Also, by
Proposition 7 we have ||at|| ||| < ||at + a
a- 11 ||a]| for any a" odd. Hence, the optimization
problem describing Ri(J) in (58 reduces to 59
D EXTENSION OF R-NORM TO LIPSCHITZ FUNCTIONS AND PROOF OF THEOREM
To simplify notation we let ((P)) denote the space of even Schwartz functions on sd-1 x xR, i.e., vo E S(P*) if uh S(8 R) with (, b) (0 bb) for all (w, gd-1 x I.
We will need a finer characterization of the image of Schwartz functions under the dual Radon transform than what is given in Lemma 9 which is also due to [Solmon (1987):
Lemma 8 (Solmon 1987). Theorem 7.7). Let gb E (((P)) and define y Val 7a(- (ol-A)(d-1//2R) (v).
Then yp E C**(""" with ((x)) O[1 44 and Axp(x) = ([ d 2) as || + cc. Moreover,
R(p}= = v.
Using the above result we show the functional ||,fll given in Definition I well-defined:
Proposition 9. For any f E Lip(R the map Ly(b) == ra all & E S(IP)), hence |lfll sup {Lb(T}) & E S(IP),, 11 S 1 is a well-defined functional taking on values in [0, +00).
is finite for
Proof. Since f is globally Lipschitz we have [f(x) = 0(1 l)) while for any sb E S(Ld)) we have (-A))d++1/222) { = 0(|===1---)) by Lemma hence (-)r))
{+)( =
O[[|=]| --11 is absolutely integrable, and so (f. (-
( ((d+1)/2 { is finite.
(A))))41//2 (v))) * 0, we can choose the sign of & so that the inner product is positive, which shows that |f 2 0.
In Section 4 we showed Ah, RD (a when a was a measure with smooth density having rapid decay. The next key lemma shows this equality still holds in the sense of distributions when a is any measure in M (IPd..
Lemma 9. Let f = havve for any a E M(P'), E Rdd c E R. Then we have (f. Ayp) = (a, R(p)) for all ip E Cx such that spxx) = O(1 and Ap(x) = 0[1 - as
[<|| - 00.
T x b), which is generated by the even measure oo(w', b/) = 1/2 (5(ww' w, b) + 5(w' + un 1/ + b)). An easy calculation shows that Arw,((x) =
Proof. Consider the ridge function Tw, (2)) _ //w
8(w" T x -)b) b) in the sense of distributions, ie., for all test functions yp E ((Rd) we have
f (rm.(())) da [
p(x) ds(z) (ur))
(60)
Since (w b) is well-defined for all yo E (RI) with decay like O[|==|]-)) by continuity Arw, à (x) extends uniquely to a distribution acting on this larger space of test functions.
Now consider the more general case of f ho with a E M(Pd). Then for all y E (RR(R) with (px) = O [z -4) and A = (11=11 -d-2) as | - oo we have
Rd f(x) ((x) dx = Jzd (Lgg
2 [lwT T x - bl (b)) da(w, 6) Aup(x) dx
(61)
1xR
2 b(wwaa x bl (x(x) da do(w.,)
(62)
1 XR
(Fee (w.((x)Ap(p) dx) da(w,))
(63)
3d-1 xR
R1yp)(1, b) do((r.
(64)
1
18

---

Published as a conference paper at ICLR 2020
where in 62 we applied Fubini'ss theorem to exchange the order of integration, whose application is justified since
(a]()) _áá-ixR (1w) xx -1- -66) (()) b) = [
(65)
and by assumption Ap(œ) = 0(122)1-d--2) hence ha (z)) = O[I and so J (z))4))p) dx < oc.
Finally, if f - ha.n, for any E M(P)), E R E R. since affine functions vanish under the Laplacian we have (S)))) = (ha: Aip,, reducing this to the previous case, which gives the claim.
The following lemma shows | is finite if and only if f is an infdh net, in which case ll is given by the total variation norm of the unique even measure defining f.
Lemma 10. Let J E Lip(Rd). Then I|/ is finite if and only if there exists a unique even measure E (Pa) and unique v E TR,, e E with f f= ba,v,e in which case [l = =||0]]-
Proof. Suppose ı is finite. Then by definition f belongs to Lip( and the linear functional (v()) ra( (- (-A) (d-)(/1)//2== {e)} is continuous on S(IP)) with norm [ Since S(Pd) is dense subspace of (T( by continuity there exists a unique extension T.y to all of (o with the same norm. Hence, by the Riesz representation theorem, there a unique measure a E M (Pd) such that f,y (w) = J da for all e E (o(2)) and || = |||||1--
We now show f ha,v,c for some E R c E R. First, we prove Af Aha as tempered distributions (i.e., as linear functionals on the space of Schwartz functions S(R")) By Lemma we have (Aha, 4p) = (a,, (xx)) for any &p E S(RR), hence
(Aha: .p) = (a, R(1))
(66)
(R(())
(67)
[[)(R(b))
(68)
(69)
--
(70)
(f,Ap)
(71)
P)
(72)
where in son
68
we used the fact that R( E S(PP4) for all E S(R)) Hella-
1999
Theorem 2.4), and in (T)) used the inversion formula for Radon transform: -Ajd [R( = yp for all S(Rd) (Helgason 1999 Theorem 3.1).
Hence, we have shown Af Ah, as tempered distributions. This means f- ha is in null space of the Laplacian acting on tempered distributions, which implies f- where is some harmonic polynomial (i.e. p is a polynomial in a (#1,..,, La) such that Ap(x) = 0 for all x E Rd).. Finally, since both ff and ha are Lipschitz they have at most linear growth at infinity, so must p. This implies p must an affine function p(ar) = x + c, which shows f ha,v,e as claimed.
Conversely, suppose f ha,e, for some a M(P)), (w) in Co with p(x) = 0([x=||-d),
Rd, R. Let & E S(Id). By
Lemma 8 the function to -na(-A)(d- Ap(x) = -[[[<=]]---2 as ||-||| + co, and d = R( Hence, by Lemma we have Ly(x) = (S. As) = (a, R(w}) = (a, v))
(73)
This shows
||l = supf w) 1 S(Pd), 11bll $ 1} = supf(a, w) : v E CP 110llo I 1]
(74)
(75)
||a|]]
(76)
19

---

Published as a conference paper at ICLR 2020
where the second to last equality holds since S(R") is dense subspace of Co()),, and the last equality is by the dual characterization of the total variation norm.
Finally, to show uniqueness, suppose ha,v, hig,"',' for some other even 3 M M v' R. E R. Then the function ha,v. h3 = 8a-8,v-p'.c- is identically zero, hence by the argument above - IR |a B111 = O, which implies B. Therefore, ha, ha which also implies v' = v and c
Note that Lemma is essentially a corollary of the uniqueness in the preceding result; we give the proof here for completeness.
Proof Lemma 7 Suppose (f) is finite. Then by the optimization characterization in Lemma 7 we have ha,v.c for some even a E M(P), v E Rd c E Rd, and R1 (f) is the minimum of ||a+||| over all even measures at E M(P4) and v' E RR, E such that f ,at,w w,,e' By Lemma 10 there is unique even measure at E M(P),, v R2, and c R such that f = hal o.c Hence, Ri (f) = ||a+||1.
Now we give the proof of our main theorem, which shows llflR = Rf(f).
Proof of Theorem 7 Suppose (J) is finite. By Lemma [T(()= ||al|1 where E ( is the unique even mcasure such that f = havv. for some v R,,CE c R. Furthermore, |If a l
by Lemma 10 Hence, (f) = ll Conversely, [l is finite, then by Lemma 10 we have
f Na, for a unique even measure a E M(P"), and again by Lemma | || ||]]]
(f).)
/ The Radon transform a bounded linear operator from (RR) to ('( R) (see, e.g., Boman & Lindskog (2009)) Hence, if A 1)+1) L'(Rd) then R(A ((A E (RR)).. Let a E M (Pd) be the even measure on gd-1 x with density RaR (d+1)/2f) ( f). Then |a||] = =a ( (RRaadd-i))) (d-1)/2
Proof of Proposition
f) f) i.e., the total variation norm of coincides with the nnom of its density. Therefore, by definition of [| we have
[l sup(na(f. (1+11/2 R" (b})
S(PP), 1}
(77)
sup((na (d- 1)/2 f], x) : sa E S(P)) 11 $
(78)
= sup((a, v) : 1 E S(Pd)) |1 11}
(79)
|all] Yal R (d+ 11/2 ff
(80)
where we used the fact that the Schwartz class S((d) is dense in (Pd) and the dual definition of the total variation norm (37). If additionally f L (I,),, have R1A (d+1)/2f) or R(() by the Fourier slice theorem, which gives || = ral Tallor" og RR(3ll,
E PROOF OF THEOREM 2
We show how our results change without the addition of the unregularized linear unit v at in Specifically, we want to characterize T(([) given in 7 (or equivalently its optimization formulation Unlike in the univariate setting, R() does not have simple closed form expression in higher dimensions. However, for any f E Lip( prove the bounds
max V < R(( < | + f
(81)
where the vector (co) E Rd can be thought of as the gradient of the function "at infinity"; see below for formal definition. In particular, if f=x) vanishes at infinity then ff(c)) 0 and we have R()) || (J).
20

---

Published as a conference paper at ICLR 2020
For any f E Lip(R*), define Vf(cc) R by
Vf(x) lim
||||=r V((x) ds(æ))
(82)
card-1
where cu = Sgs dw. We will relate (co) to the "linear part" of an infinite-width net. Towards this end, define ; (S4-1 x R) + Rd be the linear operator given by
- { V(a) 2 g w da(w,, b).
(83)
Note that a a+ o. where at is even and a' is odd, then V(aa) Jg w dert (w,b) b) = O. In particular, if we set vo = V(ar), then ha- (x) = 0/ a.
V(a since
Lemma 11. Suppose f = ha for any E M( x RR) E R. Then, Vf((o) = V(a).
Proof. A simple calculation shows the weak gradient of f ha,e is given by
f(x) 1
H(w x b) da(w,,)
(84)
where H is defined H()) 1 0 and H(I) = 0 if < 0 otherwise. Therefore, we have
1 lim pd ||
ds(x)
lim
HrrwJur w - -b) duo' da(w,
(85)
0-000 gdd xR ga-1
w (fr dw da(w, b)
lim
(86)
n-y00 Jgd
xR
Jgd
duw')
{ 1xR
do(ww,))
(87)
Finally, dividing both sides by ca fgu-1 dw gives the result.
Lemma 12. If (ar) 1o then R()) 2|/
Proof. Note that f hare only if odd and V(a) -oo Hence, have
R(( min ||]|| s.t. V(a) vo
(88)
The adjoint V . CS R. is given by [V, b) } w y. Therefore, the dual of the convex program above is given by
max yERd
w-y= max fy y v0llool
(89)
b 52
| bll $1
1 w 'll 1 holds if and only if ||>||| 2. This means 2 2// is a lower bound for R(f). Since this bound is reached with the primal feasible choice a defined by
where we used the fact that ||V* yl1oo max
alw, b) ||ma|||
|!olll b)
vo
8
b
(90)
have R(f) v/| claimed.
Now give the proof of Theorem
Note every Lipschitz function has weak gradient Vf E (R"), V.((o)) is well-defined.
21

---

Published as a conference paper at ICLR 2020
Proof of Theorem 2 Suppose |lfllR is finite. Set vo
Vf(co). Then by Lemma 10 there is
unique even measure at such that = to.e for some unique vo E R. e e R, with |l ||at ||. Therefore, R((s) is equivalent the optimization problem
R(f) min ||at + + s.t. V(a = Do odd
(91)
Since ||at + ||a ||
||a ||r. by Lemma 12 we that R()) S ||at || 2/
Now we show the lower bound. By Proposition we have ||at + a --] 2 ||a+|| = -1/ which
gives R(()) 2 Ilfll By Proposition 7 we also have +o+++==1l I|a 2 ||a By the proof of Lemma
12 the minimum of ||a-|| over all odd a such that V(a=) ) vy given by 2/ voll (o))]
Therefore, R(f) 2 max [l 2 (oo) as claimed.
Finally, we show there are examples where the upper bound in Theorem 2 is attained. Proposition 10. There exist f _d + IR in all dimensions d such that
R()) = || + f(x)](
(92)
Proof. Let w+, w- E gd-1 be orthogonal. Consider = ha defined by = at + + with
at = ō(w w..b) b) 8(w + w4+ b) d(w w_,b) 8(w + w.,b)
(93)
(94)
Hence, f(x) = [ w _ x (e.g., in 2-D one such function is f(z, y) = x lv). Replacing the TV-norm with its dual definition, the dual problem for R(() in this instance is given by:
sup PS x VER" ||V' y+ $1
w y + (at,p)
(95)
Set 3/ = 2u.., and let yp" be continuous approximation sign(a+)) whose support is localized an arbitrarily small neighborhood of +(w+, 0). Then the pair (sp", yy) is dual feasible since
f1 w Tww
if +w and 0
(ww b) [V* y"y"" [[,,)) + b) w T w- (w,
w
else
and so |bb w. b)l 1. For these choices of (fp v²) the dual objective is 2|| [/tl-|++1fffl ||+ which gives lower bound R(f). But this is also upper bound on R(f) hence R(f) = [l + 2|| Since fcc) = w., the result follows.
F PROPERTIES OF THE R-NORM
Here we prove the properties of R-norm discuseed in Section 4.1 including Proposition 2
Proposition 11. The R-norm has the following properties:
(I-homogeneity and triangle inequality) If [| l1ll1 < oc, then ||c fllx = |c] for all R and || gll S ll + -1 ie., Il-ll a semi-norm.
(Amithilation of affine functions) [[ if and only if f is affine, i.e., f(x) u + for some E Rdd C R.
(Translation and rotation invariance) 1f gf(()) s(U + where y E Rd and U E Idddd is any orthogonal matrix, then || ||
(Scaling with dilations/comtractions) Suppose I co. Let fc(w) = fww/s), then [| =
22

---

Published as a conference paper at ICLR 2020
Proof. The 1-homogenity and triangle inequality properties follow immediate from the linearity of all operations and the definition by way of set supremum.
Clearly Ilf
0 if f is affine. Conversely, suppose If 0 then by the uniqueness in Lemma 10 we have 0, and so hu,w.e for some & E Rd and IR, hence is affine.
For simplicity we demonstrate proofs of the remaining properties under the same condi- tions of Proposition | i.e., d odd, and where J, f T.'(R)) so that l| = Tallat+IR(ffll < oc. The general case follows from standard duality
Yal (/A/R(((+)))))) arguments.
To show translation invariance, define (x)) = f(a - y)- Then since A commutes with transla- tions we have A Ad+1)/2 f(w) [A(d+1)/3 Also, for any function g see that
R(glw))(u,b b) = w b+ w y).
(96)
Therefore,
[wll
[R ( (w)) (wo, b) dw db
(97)
-31-1xR
RR (d+1/22 //w b + w y) dw db
998)
33 1x
(R(A(d+1)/2 /2 (w,, b)] dw db ||
(99)
xR
To show rotation invariance, let ft((x)) = [(Uw+) where U is any orthogonal x d matrix.
Then, using the fact that the Laplacian commutes with rotations, we have (2 fv(()) = A (d+11)/2 ((U)), and since R(yr b) = (Rg)(Uw, b). we see that R(A frr
( b), and so
| = lR
(100)
To show the scaling under contractions/dilaations (i.e., Proposition 2p let fa(x) = f(x/e)) for e > 0.
Then
R(.ee(w,bb)
(xxE)ds((x)
(101)
WT m=b Tmmb
=
Tw f(z)ds(()
(102)
d (i
(103)
Hence, we have
1 RRJE) = 1 10 ( (R,
(104)
= [( b/e)l
(105)
and so
{
10 Rg{t b) dur db = 8- f
a (1,, dw db
(106)
9d 1xB
1xR
= =1 /
(R, b) dw db
(107)
-ga-
= [|fl|R
(108)
Fourier estimates For any Lipschitz function f we can always interpret Af in distributional sense. An interesting special case is when Af is distribution of order zero, f.e., when there exists a constant such that (Af, p) S Cl for all smooth compactly supported functions yp so that Af extends uniquely to measure having finite total variation. In this case, the Fourier transform
23

---

Published as a conference paper at ICLR 2020
of Af, defined as ff(E) (Af, e -2== E for all & E R is continuous and bounded function, and we can make use of an extension of the Fourier slice theorem to Radon transforms of measures (see, e.g.. Boman & Lindskog (2009)) to analyze properties of |1/l|x In particular, the following result shows that in order for the IIT R to be finite, the Fourier transform of Af (or the Fourier transform of f if it exists classically) must decay at a dimensionally dependent rate.
Proposition 12. Suppose Af is a distribution of order zero. Then [l is finite only if (f = 0(Ia|-(d-1) (d-1) as |or + oo for all w E gd-1 If additionally f E L (R*), then [lflR is finite only if f(o ((r-w) = (d(+))) 1d+1)) as |ol| - for all w E ES0-1
Proof. If As E ((R)) is a finite measure then its Radon transform R(4ʃ} E M(P4) exists as a finite measure, i.e., can define Ri } via duality as (R[Af), () (Af. RT[p) for all o E (IRR)) (see, e.g., Boman & Lindskog (2009). Additionally, the restriction R{Af (w. E (RR is well-defined finite measure for all Sd-1, and its I-D Fourier transform in the b variable is given by
Ao w) for all w E EESO :0 E RR
(109)
By Lemma 10 Il. RR is finite if and only if the functional Ly(b) = -akf
-- (d))))
(w))
defined for all z/ E S(P") extends to a unique measure a E M(F)). We compute the Fourier
transform of a in the b variable via duality: for all & E ((IP)) have
(Foo, v)) = Foop)
(110)
--aaff ( (-A) (Fopp)
(111)
-T, (-A) (d- (- (FwP)
(112)
=YalAf, R (1-0))
(113)
=ra(Af, R' (F
(114)
=
(115)
= -a(FFR 1, ())
(116)
7a((o1"-F,R(AA)) 4)
(117)
This shows Frex = J [ in the sense of distributions. Since FrR is defined pointwise for all (w, b) E gd-1 x R so is Fier and we have
= - (w, 0) = rala| P w))
(118)
Finally, since a a finite measure, we know |F I &||a|| = O(1), which gives the first result. If additionally f E L' (IR") then we have Af(E) = which gives the second result.
and so (w, b) |o| f(o-w)
G UPPER AND LOWER BOUNDS
Here we prove several upper and lower bounds for the R-norm. Proposition 3 is an immediate corollary of the following upper bound:
Proposition 13. If (TAA)(d+1)2) f is a finite measure, then
||/l S racall( racal((-)(d+t)2 fll,,
(119)
In particular, if (-A)(4+1)/2 exists in weak sense then || || can be interpreted as the norm.
Proof. Straight from definitions we have
| = sup { (na(f (-A) (d+ (w)) : o S(P"), 11 $
(120)
= ssup haa(( (0) R² (v)) S(Pd), 11 $
(121)
< sup ( ( (d+1)/2 f, e (ORR) 11:/1l0 S ca)
(122)
(c)ell(-A)((t)))))
(123)
24

---

Published as a conference paper at ICLR 2020
where we used the fact that R$ (p) (R( for yp E S(Pd) Solmon 1987 Corollary 3.6) and have (RT(()) I ca for all E S(P such that 1/ I since
(+) /
f dw cd- Sa-1
lp(w,, w JuTan ax) dwo
(124)
The following result also gives useful lower bound on the R-norm. Proposition 14. If Lip((R)) then
|| sup {U, : v E (R( s1}.
(125)
Proof.
Let SH (F C S(Pd)) denote the image of ((Rd) under the Radon transform. Then
|1 = sup { Pa(s; (- (v)) : S(P"), $1}
(126)
2 sup Pa(S. (- (- (- Rd (v)) 1 Sn (H 11 $
(127)
= sup { (a(ff ( ( : S(R)) |R $1} =1
(128)
sup (f,, AΦ) S(R)) (R ~ =
(129)
where in the last step we used the inversion formula: yp J fa(-A)(d-1/2R (R(p)) for all y S(
Further simplifying the lower bound above gives the following.
Proposition 15. If f Lip(RR) then
Il 2 sup ( Ap)) ip E S(R"), Ikel1 s $1}.
(130)
In particular, if f exists weak sense then || 2 |1
Proof. If || = f [ dæ 1 then clearly [R( b) = - (())ds(())) < SooT [x(xx) dx(x) < 1. Hence ||vella < implies || 1. Combining this with the previous proposition gives the first bound. Additionally, by the dual definition of the L norm, and since S(TR.) is dense in 7.¹ (RR),, the second bound follows.
a-
H RADIAL BUMP FUNCTIONS
Proof of Proposition 4. Assume f E L'RR)) so that its Radon transform R(F} is well- defined, and for simplicity assume odd. Note that for radially symmetric function we have (w, b) = p(b) for some even function E (T), i.e., the Radon transform of radially symmetric function does not depend on the unit direction w E sd-1, Supposing ((d+1) p(()))p(()) exists either as a function or a measure, we have
|| = 7 t R(SHI = naca / pbb)lab.
(131)
where cæ Sgu- 1eg--des dw
4/2 [d72]
Now we derive an expression for p(b) in terms of g. First, since p(b) = (w b) for any E gd-1, we can choose e (1, O....... ..., 0), which gives
p(b) = R(S((e))) = ([[æl])d ... dx = JEn Il 12 + | )d
(132)
where we have set ã (I2, ... Ft). Changing to polar coordinates over dd have
3 dd ca-1 1- g(V 12 + 222
p(b) 3a-1
g( g(VB 12
(133)
25

---

Published as a conference paper at ICLR 2020
By the change of variables t² = b² + r2, , O, we have
p(b) ca-1 /,- s(1)(12 -b)(dd
(134)
Hence, we see that
(d - 2)! glatt1) [/,00 s(t)((e - 13 03)(d-3)/22
11
(135)
where we used the fact that pacaca-1 [d-2)!
Calculations in Example 2
Let [(x) = -dl,k (1|2=]) with æ E Rd where
(1- 22) 0
gax((r) 10
(136)
if 2 1.
for any l: > O. Then a straightforward calculation using (34) gives
b2))++
if [6 i 2 1.
p(b)
(137)
0
21((-1//2)+ Hence, we have || finite if and only if p() has bounded 2 2 0. or equivalently, d = 3 then we need k: 2 in order for || to be finite, consistent with the previous example.
where Ca.s 3(2)
variation, which is true if and only if k d + d=1
d+1 For example,
(d + 5)/2 so that p(b) Cd,(445)/2(( b²) 22) for [6] S and p(b) 0 otherwise. Then we can show that jad+1 s 18d+1 p(0) for [6] s and ad+1 p(b) = 0 for all |6] Z 1. Therefore.
To illustrate scaling of Il with dimension d, we set k: (d + 1)/2 +
[
|l (d - 2)
1 p(b) S (d - 2) 18 |(0) p(0)
(138)
Performing binomial expansion of p(b) and taking derivatives, we obtain
2 18t+ 18 ((0)) 2C, 2Ca (d + 1)/2 (d (d-
d
(d 1)d(d 1) 2d(d 5)
(139)
for all odd d 2 3. By the lower bound in Proposition 15 we also have |1/ 2 |A =
(AS(0) = d(d + 5). Hence || d.
I PIECEWISE LINEAR FUNCTIONS
Here we state and prove a more formal version of Proposition 5 Before stating our result, we will need a few definitions relating to the geometry of piecewise linear functions. Recall that any piecewise linear function (with finitely many pieces) is divided into polyhedral regions separated by a finite number of boundaries. Each boundary is (d - 1)-dimensional and contained in a unique hyperplane. Hence, with every boundary hyperplane containing it, which we call the boundary normal. Additionally, in the case of compactly supported piecewise linear functions, every boundary set that touches the complement of the support set we call an outer boundary, otherwise we call an inner boundary.
associate the unique (up to sign) unit normal to the
Proposition 16. Suppose f R + TR. is a continuous piecewise linear function with compact support such that one (or both) of the following conditions hold:
(a) least one of the boundary normals is not parallel with every other boundary normal, or (b) f is everywhere convex (or everywhere concave) when restricted to its support, and at least one of the inner boundary normals is parallel with all outer boundary normals.
Then has infinite R-norm.
26

---

Published as a conference paper at ICLR 2020
Proof. Assume f is continuous piecewise linear function with compact support satisfying assump- tion (a) or (b). Let .i.... ..., B, denote the boundaries between the regions. Since f is piecewise linear and continuous, the distributional Laplacian Af decomposes into a linear combination of Dirac mea- sures supported on the d dimensional boundary sets BR, i.e., for all smooth test functions we have
/ ((x) (s)))s())) Br
(Af.
Σ Rm
(140)
for some non-zero coefficients C E R. where ds indicates integration with respect to the d - dimensional surface measure on Bg- In particular, if Bş is the boundary separating neighboring regions Rp and Ry then Cs + 9, where Ip and 9r are the gradient vectors of f in the region Rp and Rg respectively, with sign determined by whether the function is locally concave (+) or convex (-) at the boundary. Note that Af is distribution of order zero, i.e., it can be identified with a measure having finite total variation, and has a well-defined Fourier transform given by
Âf(E)
Σ Ck
---2n ds(x).
(141)
Ba
We show that (T(E) violates the necessary decay requirements of Proposition 12 in order for f to have finite R-norm. In particular, we show under both conditions (a) and (b) there exists a w such that Af(a w) is asymptotically constant as |o| - which gives the claim.
For all I.... n, let wy, denote boundary normal the boundary By (i.e., vector wy e S such that w. x = 0 for all æ E B₁, which is unique up to sign).
We first prove the claim under condition (a). Suppose, without loss of generality, that the boundary normal wi is not parallel with all the others, i.e., wi o ww for all k = 2, We will write
Āj(a w1) Fi(o) F2(o)
(142)
where Fi( = c1 Sp, e e- ds(x) and F2(0) = Σk= che Sr. e -22xow, dss()), and give decay estimates for Fi and F2 separately.
First, consider For). Since w. for all x E B1 have
/
22 " / ds(x) = s(Bi),
Fi(d)=
(143)
B,
where sB1)) is the (d 1) dimensioonal surface measure of B1. In particular F(a) is non-zero constant for all a E R.
Now consider (or).. In this case, the integrand of Jp. e e-12nam "ds(x) for all k = 2, ..., is not constant, since by assumption w, not parallel with any of the boundary normals W2, .... wn- By an orthogonal change of coordinates, we can rewrite the surface integral over Bg as a vol- ume integral over a set B₁ embedded in (d 1) dimeessioaa space á = (ø1,..., kd-1),
) so that JB. -2TTw " ds())) Jé. e -2nou dæ for some for some non-zero wh E Rd-1, Observe that g( = :2 w
12mo has divergence g( 12mww T Therefore, by the divergence theorem we have
12 $ dē
J.. V g())dē
(144)
f.a. g(t)] _ n
(145)
e 2 # &wi, n())ds(())
(146)
i2Too JaB.
where re(t) is the outward unit normal to the boundary 0ß. This gives the estimate
e -12mom a dā = 0(1o)) |o| + 0c,
(147)
Bg
27

---

Published as a conference paper at ICLR 2020
which holds for any l 2..., Therefore, F2(0) = Ek=2 Ck JB. e " ds(x) = 0
lor oc. This shows that Af wi) + CIs(BI),, i.., As wi) is asymptotically constant, which proves the claim.
Now prove the claim under condition (b). Without loss of generality, let wi be inner boundary normal that is not parallel with any outer boundary normal, and assume f is concave when restricted its support. Let [ be the indices of all inner boundary normals parallel with w (including itself), let 12 be the indices of all inner boundary normals that are not parallel with wi, and let O be the indices of all outer boundary normals. Then we write
Df(o w1) F1,(0) + [
(148)
where F1,(a) = Eken Cs Sp. e ibnow "d((x)) (o) = EKEE, Cb Sm. -irrow " "ds()), and Fo(o) = -xso Ck Jm. e-ixxowi "x)) By the same argument as above, we can show Fr, (o) = EKER, (xs( Since the function is concave when restricted to its support, all of the c with k E 1 are positive, hence the sum ΣKE,, (sS(B)) is non-zero, which shows F1 (o) is non- zero constant for all a R. Likewise, by the same argument as above, we can show Fr = 0(1/o) and Fo(o) O(1/o). Therefore, Af(a -wi) is asymptotically constant, which proves the claim.
28


Reviews:
[{"review_id": "ryx--vwTYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the author analysis the (approximate) function class generated by an infinite-width network when the Euclidean norm is bounded. They extend the work of Savarese et al. on the univariable function by introducing the Randon Transform and R-norm to this problem.  The authors finally prove that any function in Sobolev space could be (approximately) obtained by a bounded network. The results achieved implies some generalization performance analysis and the induction error. Also, according to the authors, the difference between R-norm and RKHS norm might lead to the distinct from neural networks and kernel methods.\n\nI would recommend accepting this paper since it might give a good insight into understanding the performance of the network beyond the traditional method.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hkx2sBPpKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper gives characterization of the norm required to approximate a given multivariate function by an infinite-width two-layer neural network. An important result is the relation between Radon-transform and the $\\mathcal{R}$-norm. This paper also shows application of the norm on some special case.\n\nI suggest this paper being accepted because it provides new insights into the approximation theory for neural networks. The perspective of norm constraint is different from the traditional approximation theory and may serve as a good contribution to the community.\n\nOne question is that: in section 4, the equation (19) is differentiated twice to get the equation (20) containing Dirac delta. Although this is intuitively correct, this seems not a strict derivation to my mathematical background. It would be great if the authors can show the strict definition and derivation presented here.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkgBuY4sFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies the function space regularization behavior of learning with an infinite-width ReLU network with a bound on the l2 norm of weights, in arbitrary dimension, extending the univariate study of Savarese et al. (2019).\n\nThe authors show that the corresponding regularization function is more or less an L1 norm of the (weak) (d+1)st derivatives of the function, and provide a rigorous formal characterization in terms of the \"R-norm\", which is expressed via duality through the Radon transform and powers of the Laplacian.\n\nIn addition, the paper provides a number of implications of this study, such as approximation results through Sobolev spaces, an analysis of the norm of radial bump functions, and a new type of depth separation result in terms of norm as opposed to width.\n\nOverall, this is a strong paper making several interesting and important contributions for our understanding of the inductive bias of ReLU networks. I thus recommend acceptance.\n\nA few comments:\n* is it possible to obtain precise characterizations of interpolating solutions in this setting (other than a mere representer theorem with ReLUs), as done in Savarese et al (2019, Theorem 3.3) for the univariate case?\n\n* perhaps the results of Section 5.1 should be contrasted with those of Bach (2017, e.g. Prop. 5), which only require ~ d/2 derivatives instead of ~ d here, albeit with stronger requirements, for essentially the same functional space (though the approximation result is obtained from an associated RKHS, which is smaller).\n\n* are the results on radial bump functions intended to provide insight on approximation or depth separation? what was the motivation behind this section?\n\nOther minor comments/typos:\n- after Prop. 1: \"intertwining\" appears twice\n- eq. (22): missing f in l.h.s.\n- eq. (23): is the first minus sign needed?\n- before Thm. 1: point to which Appendix\n- Section 4.1, \"In particular, this is what would happen ... d+1\": this should be further explained\n- Section 4.1, final paragraph, \"in order R-norm to be\": rephrase\n- Section 5.4, \"required norm with three layers is finite\": which norm? maybe point to a reference? Also, Example 5 could be explained in further detail\n- Section 5.5: what is an RKHS semi-norm? you'd always have ||f|| = 0 => f = 0 in an RKHS, by the reproducing property", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The article studies the set of functions expressed by a  network with bounded parameters in the limit of large width, relating the required norm to the norm of a transform of the target function, and extending previous work that addressed the univariate case. The article contains a number of observations and consequences. The reviewers were quite positive about this article. 
Decision: Accept (Poster)