Optimal bump functions for shallow ReLU networks
Weight decay, depth separation and the curse of dimensionality

Neural networks have revolutionized fields from computer vision [KSH12] to natural language processing [VSP${}^{+}$17]. They are the driving force behind AIs which play strategy games at superhuman levels of proficiency [SHS${}^{+}$18, SHM${}^{+}$16, SSS${}^{+}$17], facilitated major advances in scientific problems such as protein folding [TAW${}^{+}$21, JEP${}^{+}$21], and have been used for computer-assisted proofs in applied mathematics [WLGSB22]. While empirical evidence indicates that they often generalize well to previously unseen data when trained appropriately, there is little rigorous understanding of how neural networks interpolate a function between known data points.

In this article, we provide insight in the simple setting of infinitely wide ReLU networks with a single hidden layer and data which are drawn from a radially symmetric distribution on a Euclidean space $R^d$. The target function $f^{\ast }$ satisfies $f^{\ast }\left(0\right)=1$ and $f^{\ast }\left(x\right)=0$ for $|x|\ge 1$, where $|\cdot |$ denotes the Euclidean norm on $R^d$. We consider a loss functional composed of an ${\ell }^2$-error and a weight decay regularizer. Despite the fact that neural networks with a single hidden layer cannot represent compactly supported target functions exactly [Lu21], there are such functions which can be approximated efficiently even in high dimension. Here, we construct optimal infinitely wide networks, and show that the weight decay regularizer grows only linearly in the dimension $d$ of the data space, improving on the quadratic upper bound established by [OWSS19].

While highly idealized, this setting allows us to study several important aspects of neural network models:

1. Learning symmetries. The target function has two important symmetries:

   • $f^{\ast }$ is radially symmetric. While it is impossible to fit this symmetry exactly by finite networks, it can be attained asymptotically for highly overparametrized networks. More precisely, one could ask whether regularized risk minimization leads to symmetry learning. While we show that a unique radially symmetric solution exists, it remains open whether other solutions exist which do not exhibit radial symmetry.

   • $0\le f^{\ast }\le 1$ almost everywhere with respect to the data distribution. Unlike linear models, which necessarily output negative data even if all training data points are positive, neural networks have the capacity to respect this constraint. We show that risk minimization asymptotically enforces the bound everywhere on the data space, at least for the unique radially symmetric solution.

2. Fitting random or perturbed data. It is known that overparametrized neural networks can fit random data, but due to the great generality of the result, the network weights may be prohibitively large for given data. Assuming that labels are generated by a function which can be approximated well by a neural network, compactly supported bump functions can be used to obtain an upper bound on the magnitude needed for specific labels or the increase necessary in the weight decay regularizer if the labels are perturbed.

3. Depth separation and curse of dimensionality. We prove two complimentary results:

   • In dimension $d$, there exists an infinitely wide ReLU network with one hidden layer $f_d^{\ast }$ with weight decay regularizer $\sim d$ such that $f_d^{\ast }\left(0\right)=1$ and $f_d^{\ast }\left(x\right)=0$ if $|x|\ge 1$.

   • If $f_{d,\epsilon }^{\ast }$ is an infinitely wide ReLU network with one hidden layer such that $f_d^{\ast }\left(x\right)=1$ for $|x|\le \epsilon$ and $f_d^{\ast }\left(x\right)=0$ if $|x|\ge 1$, then the weight decay regularizer of $f_d^{\ast }$ grows at least exponentially as ${\epsilon }^2{d}^{1/2}(1-{\epsilon }^2{)}^{-\frac{d+1}{2}}$ in the dimension $d$ of the data space.

   The curse of dimensionality can be avoided in the second situation by using a neural network with two hidden layers, for which the weight decay regularizer only grows as $\sim d^{1/3}(1-\epsilon {)}^{-1}$.

4. Effect of regularization. Weight decay regularization is often taken as a proxy for controlling the Lipschitz constant of a neural network, as it can be computed more easily. In this highly symmetric setting, we can compare two optimal solutions:

   1. The data is fitted optimally by the function ${\hat{f}}_d\left(x\right)=max\{1-|x|,0\}$, which attains the minimal Lipschitz constant $1$. The function cannot be represented by a ReLU network with a single hidden layer and finite weights, even in the infinite width limit [EW20b, Example 5.19]. It can be presented by a neural network with two infinitely wide hidden layers and weight decay $\sim \sqrt{d}$.

   2. The weight decay regularizer of the optimal two-layer ReLU network $f_d^{\ast }$ grows like $d$, while its Lipschitz constant grows like $\sqrt{d}$.

5. Highly localized peaks. The target function can be seen as the prototypical example of learning functions which take values $y_1,\dots ,y_N$ at isolated points $x_1,\dots ,x_N$ which are separated as ‘islands’ in a ‘sea’ of points $x_{N+1},\dots ,x_M$ with labels $y_{N+1}=\cdots =y_M=0$.

6. Mollification. The infinitely wide neural networks constructed in this note can be used to establish approximation rates in function spaces for shallow neural networks by mollification, if the mollification width $\epsilon$ is optimized to balance the competition between approximation of the target function by the infinitely wide network and approximation of the infinitely wide network by finite neural networks.

To the best of our knowledge, this is the first time that an optimal solution for fitting data by neural networks has been computed in dimension $d>1$. For technical reasons, we focus on the case that $d$ is odd. The optimal radial solution can be written as a finite sum

for some coefficients ${\mu }_i\in R$ satisfying ${\sum }_{i=0}^n|{\mu }_i|={\gamma }_n\sim 3.7d$.

The article is organized as follows. In the remainder of the Introduction, we briefly review the context of this work in the literature and the notation we will use throughout the article. In Section 2, we give a brief introduction to the function spaces associated to two-layer ReLU networks with a weight decay regularizer (Barron or Radon BV spaces). Sections 3 and 4 are dedicated to the statement and proof of our main results respectively. Applications of our results can be found in Section 5. Numerical approximations of the optimal solutions $f_d^{\ast }$ can be found in Section 6. We conclude the article with a brief summary and list of open problems in Section 7.

Further numerical experiments can be found in Appendix A. Some proofs from the main part of the article are postponed to Appendix B, while proofs of results which are known in similar form are postponed to Appendix C. Slight extensions of the main results can be found in Appendix D.

In this section, we briefly review the theory of infinitely wide ReLU networks with a single hidden layer. Function spaces for this setting have been studied under the name $F_1$ in [Bac17], Barron space in [EMWW20, EMW19b, EMW19c, EMW18], Radon-BV in [PN22, PN21] and the convex hull of the ReLU dictionary or the variation space of the ReLU dictionary in [SX21a, SX21c]. In this note, we refer to them as Barron spaces in reference to the seminal work of Andrew Barron [Bar93]. Some results presented below are extensions of known results to the case where we consider a Barron semi-norm rather than the full Barron norm, corresponding to a weight decay regularizer which does not control the magnitude of the biases.

A neural network with a single hidden layer and $m\in N$ neurons can be represented as

where $(a_i,w_i,b_i)\in R\times R^d\times R$ are the weights of the neural network. For networks in which the size of the weights is controlled, this representation can be generalized to

where $\mu$ is a measure on $R^{d+2}$ and $\pi$ is a probability measure on $R^{d+2}$. More generally, due to the symmetry $a\sigma (w^{T}x+b)=\lambda (\left({\lambda }^{-1}a\right)\sigma (w^{T}x+b))$ for $\lambda \ne 0$, $\mu$ can be taken to be a signed measure. Finite networks are contained in the general setting by setting

respectively, where the parameters ${\lambda }_i\ne 0$ can be chosen freely for a convenient representation. The integral is guaranteed to converge if the Barron norm

is finite, where $|\mu |={\mu }^{+}+{\mu }^{-}$ denotes the total variation measure of the signed measure $\mu ={\mu }^{+}-{\mu }^{-}$. The infimum must be taken since the representation of a function in this fashion is highly non-unique [EW20b, Section 2.1]. The two representations of the norm coincide by [EW20b, Section 2.4].

The norm in the parameter variable $w$ is chosen dual to the norm in the data variable $x$ such that the inequality $|w^{T}x|\le |w|\cdot |x|$ holds. In particular, if distances in the data domain are measured in the ${\ell }^p$-sense for $p\in [1,\infty ]$, then distances in the parameter domain are measured in the ${\ell }^q$-sense for $q=\frac{p}{p-1}$. For compatibility with radial symmetry, we focus on the case $p=\frac{p}{p-1}=2$ in this note.

We refer to the space $\{f:\parallel f{\parallel }_B<\infty \}$ as Barron space $B$, or at times $B\left(R^d\right)$ to indicate dependence on dimension.

Due to the control over the bias, the Barron norm as defined in [EMW19b, EW20b] is not invariant under translations in the data space, i.e. the functions $f$ and $f(\cdot +\overline{x})$ generally have a different norm for $\overline{x}\ne 0$. By contrast, the following Barron semi-norm is translation invariant and has useful properties which suffice in many applications:

We will address the convergence of the integrals in (2) without control over $b$ in Proposition 2.1. This is more in line with the approach in [OWSS19, PN21], where the magnitude of the bias is also not controlled. We opt for controlling $|a{|}^2+|w{|}^2$ rather than $|a|\cdot |w|$ for convenience, but note that the classical Barron norm could be defined in this fashion, too. The key observation is that the ReLU activation function $\sigma \left(z\right)=max\{z,0\}$ is positively one-homogeneous, i.e. $\sigma \left(\lambda z\right)=\lambda \sigma \left(z\right)$ for all $\lambda >0$. In particular

i.e. we may normalize neurons $(a_i,w_i,b_i)$ to

without changing the output of the neural network. In particular $|a{|}^2+|w{|}^2=2|a||w|$, indicating that we could define the Barron norm in the analogous fashion by squares. Indeed, in the infinite limit it is even possible to assume that $\pi$ is supported on the set $|a|=|w|=\sqrt{[f{]}_B}$. For a more technically rigorous discussion, see e.g. [EW20b].

By a slight abuse of terminology, we will also refer to $B_0$ as Barron space from now on. We briefly note the following properties, which relate the Barron semi-norm and more well-established quantities.

All statements could be given in terms of a general signed measure $\mu$ instead of $\pi$. The proof, along with other proofs from this section, can be found in Appendix C.

Functions in Barron spaces are defined by means of an explicit representation formula. Paradoxically, this explicit characterization often makes it difficult to verify whether a given function is in Barron space. A more abstract framework was created in [OWSS19] by the means of the Radon transform, based on the observation that

i.e. the second spatial derivatives of a ReLU network with one hidden layer are superpositions of measures concentrated on the hyperplanes $W_i=\{x:w_i^{T}x+b_i=0\}$. This allows for a characterization of Barron spaces in terms of second derivatives. The Radon transform is used as a technical tool in order to dualize from hyperplanes to points. This convenient characterization allows the construction of some examples of functions in Barron space.

Based on the same intuition, we point out two observations. The first demonstrates that the singular set $\Sigma$ of a Barron function (i.e. the set where the functions is not differentiable) is ‘straight’ and lower dimensional. This is a stronger version of Rademacher’s theorem, which states that the singular set of a Lipschitz function is Lebesgue null, in the context of Barron spaces. The following statement has the stronger implication that $\Sigma$ is contained in a countable union of affine subspaces of $R^d$ and therefore has Hausdorff dimension $\le d-1$.

The fact that the singular set is straight has two immediate implications.

A brief inspection of the proof of [EW20b, Theorem 5.18] reveals that Proposition 2.3 and 2.4 reveals that both statements remain valid for $B_0\left(R^d\right)$. A stronger result on radial Barron functions is proved below in Lemma 4.1. Secondly, we recall a characterization of one-dimensional Barron spaces, which is essentially the simpler one-dimensional case of the Radon transform construction. A similar statement can also be found e.g. in [EW20b, Example 4.1] and [LMW20].

We believe that the upper bound is, in fact an identity. We now recall a property of Barron spaces $B_0$.

For the sake of completeness, we sketch a probablistic proof in Appendix C. This formulation of the direct approximation theorem improves on known results in two major ways:

1. The dependence on the data distribution $P$ is only through the ‘projected second moments’ $M_{2,proj}\left(P\right):={max}_{|w|\le 1}{\int }_{R^d}|w^{T}x{|}^{2}dP$ rather than the full second moments $M_2\left(P\right):={\int }_{R^d}|x{|}^{2}dP$. It is easy to see that

   $$M_{2,proj}\left(P\right)\le M_2\left(P\right)=\sum _{i=1}^d{\int }_{R^d}|e_i^{T}x{|}^{2}dP\le d\cdot M_{2,proj}\left(P\right)$$

   for any probability measure $P$ on $R^d$, and that equality is attained for any measure $P$ which is the product of $d$ one-dimensional probability measures, e.g. a standard normal distribution. The constant in the bound may therefore be significantly smaller in high dimension.

2. The bound depends on the Barron semi-norm, but not the full Barron norm.

While the constants are improved in this formulation compared to e.g. [EMW18, EMW19b, EW20b], the result is not expected to be sharp in terms of the rate which is achieved. An improvement from $m^{-1/2}$ to $m^{-1/2-3/2d}$ in the classical setting can be found in [SX21b] at the cost of a more involved proof.

Many of the results above are somewhat specific to ReLU activation as the proofs either use positive homogeneity or the property that ${\sigma }^{\prime \prime }=\delta$. Both are shared by leaky ReLU activation.

We are finally ready to state (and prove) the main results of this article rigorously.

The Bernstein constant is a quantity in classical numerical analysis and approximation theory arising when approximating the function $h\left(x\right)=|x|$ by polynomials in $L^{\infty }(-1,1)$, see e.g. [Tre19]. From the proof of Theorem 3.1, we obtain an algorithm to compute $f_d^{\ast }$ to arbitrary precision, which is implemented in Section 6.

The functions $f_d^{\ast }$ are radially symmetric, compactly supported and non-negative. In particular, they can serve as mollifiers to easily prove quantitative approximation results for two-layer ReLU networks in general function classes. In a companion article [Wojb], we prove that they are achieved as (radial averages of) empirical risk minimizers with a weight decay regularizer.

Note that we do not exclude the possibility that other minimizers exist which are not radially symmetric. From direct arguments, we can only conclude that the set of minimizers is convex and invariant under coordinate rotations. The existence of at least one radially symmetric minimizer follows relatively easily, while its uniqueness is established below by construction. For any minimizer ${\tilde{f}}_d\in {argmin}_{f\in F}[f{]}_B$, which may not not be radially symmetric, the radial average

is a radially symmetric minimizer, i.e. ${\tilde{f}}_{d,av}\equiv f_d^{\ast }$. Knowledge of the unique minimizer after radial averaging allows us to study optimization algorithms for implicit bias and finding global optima. This line of inquiry is pursued in upcoming work [Wojc].

We find it easier to deal with odd dimensions, as the function $(1-s^2{)}^{\frac{d-1}{2}}$ is a polynomial in this case. This is analogous to the observations of [OWSS19]. We remark that, if $f:R^D\to R$ is a Barron function and $d\le D$, then

is also a Barron function and $[\tilde{f}{]}_{B\left(R^d\right)}\le [f{]}_{B\left(R^D\right)}$, so the limit