Optimal Approximation of Zonoids and Uniform Approximation by Shallow
  Neural Networks
We study the following two related problems. The first is to determine to
what error an arbitrary zonoid in $\mathbb{R}^{d+1}$ can be approximated in the
Hausdorff distance by a sum of $n$ line segments. The second is to determine
optimal approximation rates in the uniform norm for shallow ReLU$^k$ neural
networks on their variation spaces. The first of these problems has been solved
for $d\neq 2,3$, but when $d=2,3$ a logarithmic gap between the best upper and
lower bounds remains. We close this gap, which completes the solution in all
dimensions. For the second problem, our techniques significantly improve upon
existing approximation rates when $k\geq 1$, and enable uniform approximation
of both the target function and its derivatives.
Jonathan W. Siegel
# Optimal Approximation of Zonoids and Uniform Approximation by Shallow Neural Networks

###### Abstract

We study the following two related problems. The first is to determine to what error an arbitrary zonoid in \(\mathbb{R}^{d+1}\) can be approximated in the Hausdorff distance by a sum of \(n\) line segments. The second is to determine optimal approximation rates in the uniform norm for shallow \(\mathrm{ReLU}^{k}\) neural networks on their variation spaces. The first of these problems has been solved for \(d\neq 2,3\), but when \(d=2,3\) a logarithmic gap between the best upper and lower bounds remains. We close this gap, which completes the solution in all dimensions. For the second problem, our techniques significantly improve upon existing approximation rates when \(k\geq 1\), and enable uniform approximation of both the target function and its derivatives.

## 1 Introduction

A (centered) zonotope in \(\mathbb{R}^{d+1}\) (so that the sphere \(S^{d}\subset\mathbb{R}^{d+1}\) is of dimension \(d\)) is a convex polytope \(P\) which is the Minkowski sum of finitely many centered line segments, i.e. a body of the form

\[P=\{x_{1}v_{1}+\cdots+x_{n}v_{n},\;x_{i}\in[-1,1]\} \tag{1.1}\]

for some collection of vectors \(v_{i}\in\mathbb{R}^{d+1}\). The number \(n\) is the number of summands of the zonotope. A zonoid is a convex body which is a limit of zonotopes in the Hausdorff metric.

We consider the following problem: Given an arbitrary zonoid \(Z\), how accurately can \(Z\) be approximated by a polytope \(P\) with \(n\)-summands? Here accuracy \(\epsilon\) is taken to mean that \(Z\subset P\subset(1+\epsilon)Z\).

This problem has been studied by a variety of authors (see for instance [7, 8, 9, 10, 20, 22]). Of particular interest is the case when \(Z=B^{d+1}\) is the Euclidean unit ball. In this case the problem has an equivalent formulation as (see [7]): how many directions \(v_{1},...,v_{n}\in S^{d}\) are required to estimate the surface area of a convex body in \(\mathbb{R}^{d+1}\) from the volumes of its \(d\)-dimensional projections orthogonal to each \(v_{i}\)?

In [10], it was shown using spherical harmonics that with \(n\) summands and \(Z=B^{d+1}\) the best error one can achieve is lower bounded by

\[\epsilon(n)\geq c(d)n^{-\frac{1}{2}-\frac{3}{2d}}. \tag{1.2}\]

When \(d=2,3\), this bound was matched up to logarithmic factors in [8], specifically it was shown that for general zonoids \(Z\), we have

\[\epsilon(n)\leq C(d)\begin{cases}n^{-\frac{1}{2}-\frac{3}{2d}}\sqrt{\log(n)}&d =2\\ n^{-\frac{1}{2}-\frac{3}{2d}}\log(n)^{3/2}&d=3.\end{cases} \tag{1.3}\]

For larger values of \(d\) the result in [8] gives the worse upper bound of

\[\epsilon(n)\leq C(d)n^{-\frac{1}{2}-\frac{1}{d-1}}\sqrt{\log(n)}. \tag{1.4}\]
In [9] (see also [22]) it was shown that these bounds can be attained using summands of equal length if \(Z=B^{d+1}\).

The picture was nearly completed in [28] where it was shown that we have

\[\epsilon(n)\leq C(d)\begin{cases}n^{-\frac{1}{2}-\frac{3}{2d}}\sqrt{\log(n)}&d =2,3\\ n^{-\frac{1}{2}-\frac{3}{2d}}&d\geq 4.\end{cases} \tag{1.5}\]

Moreover, it was shown that the upper bound when \(d\geq 4\) can be achieved using summands of equal length for all zonoids \(Z\).

In this work, we remove the logarithmic factors in (1.5) when \(d=2,3\), i.e. we prove that

\[\epsilon(n)\leq C(d)n^{-\frac{1}{2}-\frac{3}{2d}} \tag{1.6}\]

for all \(d\), and thus provide upper bounds exactly matching (up to a constant factor) the lower bound (1.2). To formulate these results, we pass to the dual setting (see [10, 28]). A symmetric convex body \(Z\) is a zonoid iff

\[\|x\|_{Z^{*}}:=\sup_{z\in Z}x\cdot z=\int_{S^{d}}|x\cdot y|d\tau(y) \tag{1.7}\]

for a positive measure \(\tau\) on \(S^{d}\). The body \(Z\) is a zonotope with \(n\)-summands iff \(\tau\) is supported on \(n\) points. Since our error measure is scale invariant, we may assume that \(\tau\) is a probability distribution. Given these considerations, the bound (1.6) follows from the following result.

**Theorem 1**.: _There exists a constant \(C=C(d)\) such that for any probability measure \(\tau\) on the sphere \(S^{d}\), there exists a probability measure \(\tau^{\prime}\) on \(S^{d}\) which is supported on \(n\) points, such that_

\[\sup_{x\in S^{d}}\left|\int_{S^{d}}|x\cdot y|d\tau(y)-\int_{S^{d}}|x\cdot y|d \tau^{\prime}(y)\right|\leq Cn^{-\frac{1}{2}-\frac{3}{2d}}. \tag{1.8}\]

We remark that our method produces summands of unequal length (i.e. a non-uniform distribution \(\tau^{\prime}\)) and we do not know whether this approximation can be achieved using summands of equal length (even for the ball \(B^{d+1}\)) when \(d<4\).

Recently, there has been renewed interest in the zonoid approximation problem due to its connection with approximation by shallow ReLU\({}^{k}\) neural networks [2]. The ReLU\({}^{k}\) activation function (simply called ReLU when \(k=1\)) is defined by

\[\sigma_{k}(x)=x_{+}^{k}:=\begin{cases}x^{k}&x\geq 0\\ 0&x<0,\end{cases} \tag{1.9}\]

where in the case \(k=0\) we interpret \(0^{0}=1\) (so that \(\sigma_{0}\) is the Heaviside function). A shallow ReLU\({}^{k}\) neural network is a function on \(\mathbb{R}^{d}\) of the form

\[f_{n}(x)=\sum_{i=1}^{n}a_{i}\sigma_{k}(\omega_{i}\cdot x+b_{i})=\sum_{i=1}^{n }a_{i}(\omega_{i}\cdot x+b_{i})_{+}^{k}, \tag{1.10}\]

where the \(a_{i}\in\mathbb{R}\) are coefficients, the \(\omega_{i}\in\mathbb{R}^{d}\) are directions, the \(b_{i}\in\mathbb{R}\) are the offsets (or biases) and \(n\) (the number of terms) is called the width of the network.

Shallow neural networks can be viewed as a special case of non-linear dictionary approximation. Given a Banach space \(X\), let \(\mathbb{D}\subset X\) be a bounded subset, i.e. \(\|\mathbb{D}\|:=\sup_{d\in\mathbb{D}}\|d\|_{X}<\infty\), which we call a dictionary. Non-linear dictionary approximation methods seek to approximate a target function \(f\) by elements of the set

\[\Sigma_{n}(\mathbb{D})=\left\{\sum_{i=1}^{n}a_{i}d_{i},\ a_{i}\in\mathbb{R}, \ d_{i}\in\mathbb{D}\right\} \tag{1.11}\]

of \(n\)-term linear combinations of dictionary elements. Note that because the elements \(d_{i}\) are not fixed, this a non-linear set of functions. It is often important to obtain some control on the coefficients \(a_{i}\) in a non-linear dictionary expansion. For this reason, we introduce the set

\[\Sigma_{n}^{M}(\mathbb{D})=\left\{\sum_{i=1}^{n}a_{i}d_{i},\ a_{i}\in\mathbb{ R},\ d_{i}\in\mathbb{D},\ \sum_{i=1}^{n}|a_{i}|\leq M\right\} \tag{1.12}\]

of non-linear dictionary expansions with \(\ell^{1}\)-bounded coefficients.
We consider using shallow ReLU\({}^{k}\) neural networks to approximate functions and derivatives of order up to \(k\) uniformly on a bounded domain \(\Omega\subset\mathbb{R}^{d}\), so we take our Banach space \(X\) to be the Sobolev space \(W^{k}(L_{\infty}(\Omega))\) (see for instance [17]), with norm given by

\[\|f\|_{W^{k}(L_{\infty}(\Omega))}:=\sup_{|\alpha|\leq k}\|D^{\alpha}f\|_{L^{ \infty}(\Omega)}. \tag{1.13}\]

In our analysis, without loss of generality we will often take \(\Omega=B^{d}:=\{x:\ |x|\leq 1\}\) to be the unit ball in \(\mathbb{R}^{d}\) to simplify the presentation.

Shallow neural networks correspond to non-linear approximation with the dictionary

\[\mathbb{D}=\mathbb{P}^{d}_{k}:=\{\sigma_{k}(\omega_{k}\cdot x+b_{i}),\ \omega_{i}\in S^{d-1},\ b_{i}\in[a,b]\}\subset W^{k}(L_{\infty}(\Omega)), \tag{1.14}\]

where by positive homogeneity we can take \(\omega_{i}\) on the unit sphere, and the biases \(b_{i}\) are restricted to an interval depending upon \(\Omega\) to ensure both the boundedness and expressiveness of \(\mathbb{P}^{d}_{k}\) (see for instance [39]). When \(\Omega=B^{d}\) is the unit ball in \(\mathbb{R}^{d}\), we can take \([a,b]=[-1,1]\) for example, since

\[\sigma_{k}(\omega\cdot x+b)+(-1)^{k}\sigma_{k}(-\omega\cdot x-b)\]

for \(\omega\in S^{d-1}\) and \(b\in[-1,1]\) spans the space of polynomials of degree at most \(k\) on \(B^{d}\).

A typical class of functions considered in the context of non-linear dictionary approximation is the variation space of the dictionary \(\mathbb{D}\), defined as follows. Let

\[B_{1}(\mathbb{D}):=\overline{\bigcup_{n=1}^{\infty}\Sigma_{n}^{1}(\mathbb{D})}, \tag{1.15}\]

denote the closed symmetric convex hull of the dictionary \(\mathbb{D}\) and define the variation norm of a function \(f\in X\) by

\[\|f\|_{\mathcal{X}_{1}(\mathbb{D})}:=\inf\{s>0:\ f\in sB_{1}(\mathbb{D})\}. \tag{1.16}\]

This construction is also called the gauge of the set \(B_{1}(\mathbb{D})\) (see for instance [34]), and has the property that the unit ball of the \(\mathcal{K}_{1}(\mathbb{D})\)-norm is exactly the closed convex hull \(B_{1}(\mathbb{D})\). We also write

\[\mathcal{K}_{1}(\mathbb{D}):=\{f\in X;\ \|f\|_{\mathcal{X}_{1}(\mathbb{D})}<\infty\} \tag{1.17}\]

for the space of functions with finite \(\mathcal{K}_{1}(\mathbb{D})\)-norm. The variation norm has been introduced in different forms in the literature and plays an important role in statistics, signal processing, non-linear approximation, and the theory of shallow neural networks (see for instance [4, 5, 12, 13, 19, 31, 32, 36, 37, 41]).

In the case corresponding to shallow ReLU\({}^{k}\) neural networks, \(\mathbb{D}=\mathbb{P}^{d}_{k}\), the variation space can equivalently be defined via integral representations, which were studied for example in [2, 16]. Specifically, we have \(f\in\mathcal{K}_{1}(\mathbb{P}^{d}_{k})\) iff there exists a (signed measure) \(d\mu\) of bounded variation on \(S^{d-1}\times[a,b]\) such that

\[f(x)=\int_{S^{d-1}\times[a,b]}\sigma_{k}(\omega\cdot x+b)d\mu(\omega,b) \tag{1.18}\]

pointwise almost everywhere. Moreover, the variation norm is given by

\[\|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}=\inf\left\{\int_{S^{d-1}\times[a, b]}d|\mu|(\omega,b),\ f(x)=\int_{S^{d-1}\times[a,b]}\sigma_{k}(\omega\cdot x+b)d \mu(\omega,b)\right\}, \tag{1.19}\]

where the infimum above is taken over all measures with finite total variation giving such a representation of \(f\). This is due to the fact that

\[B_{1}(\mathbb{P}^{d}_{k})=\left\{\int_{S^{d-1}\times[a,b]}\sigma_{k}(\omega \cdot x+b)d\mu(\omega,b),\ \int_{S^{d-1}\times[a,b]}d|\mu|(\omega,b)\leq 1\right\}, \tag{1.20}\]

which follows from Lemma 3 in [39], and an 'empirical' discretization of the integral in (1.20) using the fact that half-spaces have bounded VC-dimension [42, 43] (note that the closure in (1.15) is taken in the \(X=W^{k}(L_{\infty})\)-norm). In fact, it follows easily from this that we get the same set \(B_{1}(\mathbb{P}^{d}_{k})\), and thus the same variation space \(\mathcal{K}_{1}(\mathbb{P}^{d}_{k})\), even if we take the closure in (1.15) with respect to a weaker norm such as \(L_{2}\).

One important question is how efficiently functions in the variation space \(\mathcal{K}_{1}(\mathbb{D})\) can be approximated by non-linear dictionary expansions \(\Sigma_{n}(\mathbb{D})\) with \(n\) terms. When the space \(X\) is a Hilbert space (or more generally a type-2 Banach space), we have the bound [4, 19, 33]

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{D})}\|f-f_{n}\|_{X}\leq C\|f\|_{\mathcal{K}_{1 }(\mathbb{D})}n^{-\frac{1}{2}}. \tag{1.21}\]
The constant here depends only upon the norm of the dictionary \(\|\mathbb{D}\|\) and the type-2 constant of the space \(X\). Moreover, the norm of the coefficients \(a_{i}\) can be controlled, so that if \(f\) is in \(B_{1}(\mathbb{D})\) (the unit ball of \(\mathcal{K}_{1}(\mathbb{D})\)), then \(f_{n}\) can be taken in \(\Sigma^{1}_{n}(\mathbb{D})\). This fact was first applied to neural network approximation by Jones and Barron [4, 19], and forms the basis of the dimension independent approximation rates obtained for shallow neural networks.

For many dictionaries, for example the dictionaries \(\mathbb{P}^{d}_{k}\) corresponding to shallow neural networks, the rate (1.21) can be significantly improved (see for instance [2, 21, 25, 38]). For instance, in the \(L_{2}\)-norm we get the rate

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{P}^{d}_{k})}\|f-f_{n}\|_{L_{2}(\Omega)}\leq C \|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}n^{-\frac{1}{2}-\frac{2k+1}{2d}}, \tag{1.22}\]

and this rate is optimal up to logarithmic factors if we require even mild control on the coefficients \(a_{i}\) (for instance \(|a_{i}|\leq C\) for a constant \(C\)) [38].

In this work, we consider approximation rates for the dictionary \(\mathbb{P}^{d}_{k}\) on the variation space \(\mathcal{K}_{1}(\mathbb{P}^{d}_{k})\) in the \(W^{m}(L_{\infty})\)-norm for \(m=0,...,k\), i.e. we consider uniform approximation of both \(f\) and its derivatives up to order \(m\). This is a much stronger error norm than the \(L_{2}\)-norm, and approximating derivatives is important for applications of shallow neural networks to scientific computing (see for instance [23, 35, 44]). For an arbitrary (bounded) dictionary \(\mathbb{D}\subset W^{m}(L_{\infty})\), no rate of approximation for \(\mathcal{K}_{1}(\mathbb{D})\) by \(\Sigma_{n}(\mathbb{D})\) can be obtained in general, i.e. there exist dictionaries for which the rate can be arbitrarily slow [14]. Thus, our results rely upon the special structure of the \(\mathbb{P}^{d}_{k}\) dictionary of ReLU\({}^{k}\) atoms.

This problem has previously been considered in the case \(m=0\), i.e. in the \(L_{\infty}\)-norm (see for instance [2, 3, 11, 21, 24, 46]). In this case, when \(k=0\) an approximation rate of

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{P}^{d}_{0})}\|f-f_{n}\|_{L_{\infty}(\Omega)} \leq C\|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{0})}n^{-\frac{1}{2}-\frac{1}{2d}}, \tag{1.23}\]

was proved in [24] using results from geometric discrepancy theory [27]. For \(k=1\), the aforementioned results on approximating zonoids by zonotopes [28] were used in [2] to get a rate of

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{P}^{d}_{1})}\|f-f_{n}\|_{L_{\infty}(g^{ \prime})}\leq C\|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}\begin{cases}n^{- \frac{1}{2}-\frac{3}{2}}\sqrt{\log n}&d=2,3\\ n^{-\frac{1}{2}-\frac{3}{2d}}&d\geq 4\end{cases} \tag{1.24}\]

on the sphere \(S^{d}\). Finally, when \(k\geq 2\), the best known result is [21]

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{P}^{d}_{1})}\|f-f_{n}\|_{L_{\infty}(\Omega)} \leq C\|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}n^{-\frac{1}{2}-\frac{1}{2}} \sqrt{\log n}. \tag{1.25}\]

We remark that for all of these results, the coefficients of \(f_{n}\) can be controlled. Specifically, if \(f\in B_{1}(\mathbb{P}^{d}_{k})\), then \(f_{n}\) can be taken in \(\Sigma^{1}_{n}(\mathbb{P}^{d}_{k})\).

By refining the techniques of discrepancy theory used to obtain these \(L_{\infty}\) bounds, we are able to prove the following result, which is essentially a generalization of Theorem 1.

**Theorem 2**.: _Let \(k\geq 0\). For any probability distribution \(\tau\) on \(S^{d-1}\times[-1,1]\) there exists a probability distribution \(\tau^{\prime}\) supported on at most \(n\) points such that for any multi-index \(\alpha\) with \(|\alpha|\leq k\) we have_

\[\sup_{x\in B^{d}}\left|D^{\alpha}_{x}\left(\int_{S^{d}}\sigma_{k}(\mathbf{\omega} \cdot x+b)d\tau(\mathbf{\omega},b)-\int_{S^{d}}\sigma_{k}(\mathbf{\omega}\cdot x+b)d \tau^{\prime}(\mathbf{\omega},b)\right)\right|\leq Cn^{-\frac{1}{2}-\frac{2(k-| \mathbf{\omega}|)+1}{2d}}, \tag{1.26}\]

_where \(D^{\alpha}_{x}\) denotes the \(\alpha\)-th order derivative with respect to \(x\). Here the constant \(C=C(d,k)\) depends only upon \(d\) and \(k\)._

As a Corollary, we obtain the following approximation rate.

**Theorem 3**.: _Let \(0\leq m\leq k\) and \(\Omega=B^{d}\). Then we have the bound_

\[\inf_{f_{n}\in\Sigma_{n}(\mathbb{P}^{d}_{k})}\|f-f_{n}\|_{W^{m}(L_{\infty}( \Omega))}\leq C\|f\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}n^{-\frac{1}{2}- \frac{2k-m}{2d}}, \tag{1.27}\]

_where \(C=C(d,k)\) is a constant. Moreover, the coefficients of \(f_{n}\) can be controlled, so if \(f\in B_{1}(\mathbb{P}^{d}_{k})\), then \(f_{n}\) can be taken in \(\Sigma^{1}_{n}(\mathbb{P}^{d}_{k})\)._

We remark that by scaling, Theorems 2 and 3 can easily be extended to any bounded domain \(\Omega\subset\mathbb{R}^{d}\). Theorem 3 extends the approximation rates derived in [38] from the \(L_{2}\)-norm to the \(L_{\infty}\)-norm, which significantly improves upon existing results [2, 21, 24] when \(k\geq 1\). In addition, we obtain approximation rates in the \(W^{m}(L_{\infty})\)-norm, which
enables derivatives and function values to be uniformly approximated simultaneously. The approximation rates given in Theorem 3 are an important building block in obtaining approximation rates for shallow \(\operatorname{ReLU}^{k}\) networks on Sobolev and Besov spaces [45].

Theorems 1 and 2 are proved using a modification of the geometric discrepancy argument used in [28], while Theorem 3 is an easy Corollary of Theorem 2. Theorem 1 follows essentially as a special case of Theorem 2 when \(k=1\), except that the ReLU activation function is replaced by the absolute value function and the setting is changed to the sphere. For this reason, we only give the complete proof of Theorem 2. The changes necessary to obtain Theorem 1 are relatively straightforward and left to the reader. We begin by collecting the necessary geometric and combinatorial facts in Section 2. The proofs of Theorems 2 and 3 are given in Section 3.

## 2 Geometric Lemmas

In this section, we collect and prove the geometric Lemmas which are crucial to the proofs of Theorems 1 and 2. In particular, in the proof of Theorem 2 we will need the following covering result.

**Lemma 1**.: _Let \(P\) be an \(N\) point subset of \(S^{d-1}\times[-1,1]\) (i.e. a set of \(n\) halfspaces) and \(0<\delta<1\) be given. Then there exists a subset \(\mathcal{N}\subset B^{d}\) of the unit ball (depending upon both \(P\) and \(\delta\)) with \(|\mathcal{N}|\leq(C/\delta)^{d}\) such that for any \(x\in B^{d}\) there exists a \(z\in\mathcal{N}\) with_

* \(|x-z|\leq C\delta\sqrt{d}\)_._
* \(|P\cap\{(\omega,b)\in S^{d-1}\times[-1,1],\ \operatorname{sgn}\left(\omega \cdot x+b\right)\neq\operatorname{sgn}\left(\omega\cdot z+b\right)\}|\leq \delta N\)_._

_Here \(C\) is an absolute constant._

A version of this Lemma on the sphere, which is required for the proof of Theorem 1 was proved by Matousek [28].

**Lemma 2** (Lemma 6 in [28]).: _Let \(P\) be an \(N\)-point subset of \(S^{d}\) and \(0<\delta<1\) be given. There exists a subset \(\mathcal{N}\subset S^{d}\) (depending upon both \(P\) and \(\delta\)) with \(|\mathcal{N}|\leq C\delta^{-d}\) such that for any \(x\in S^{d}\), there exists a \(z\in\mathcal{N}\) with_

* \(|x-z|\leq\delta\)_._
* \(|P\cap\{y\in S^{d},\ \operatorname{sgn}\left(y\cdot x\right)\neq\operatorname{ sgn}\left(y\cdot z\right)\}|\leq\delta N\)_._

_Here \(C=C(d)\) is a constant independent of \(N,P\) and \(\delta\)._

The proof of Lemma 1 follows essentially the same ideas as the proof of Lemma 2 in [28]. However, for completeness we give the proof here as well. The version given in Lemma 1 explicitly tracks the dimension dependence of the constants and can be used to track the dimension dependence of the constants in Theorems 1 and 2.

We begin by recalling the relevant combinatorial background (see for instance [29], Chapter 5).

**Definition 1**.: _A set system \((X,\mathcal{S})\) consists of a set \(X\) and a collection of subsets \(\mathcal{S}\subset 2^{X}\) of \(X\)._

The particular set system which we will consider in the proof of Lemma 1 is given by

\[X=S^{d-1}\times[-1,1],\ \mathcal{S}=\left\{\{(\omega,b):\ \omega\cdot x+b\geq 0 \},\ x\in B^{d}\right\}. \tag{2.1}\]

In other words, the elements are halfspaces and the sets consists of all halfspaces containing a given point \(x\) in the unit ball.

Given a subset \(Y\subset X\), we write \(\mathcal{S}|_{Y}=\{Y\cap S,\ S\in\mathcal{S}\}\) for the system \(\mathcal{S}\) restricted to the set \(Y\).

**Definition 2** (VC-dimension [43]).: _A subset \(Y\subset X\) is shattered by \(\mathcal{S}\) if \(\mathcal{S}|_{Y}=2^{Y}\). The VC-dimension of the set system \((X,\mathcal{S})\) is the cardinality of the largest finite subset of \(X\) which is shattered by \(\mathcal{S}\)._

An important ingredient in the proof is the following bound on the VC-dimension of the set system given in (2.1).

**Lemma 3** (Lemma 3 in [24]).: _The set system in (2.1) has VC-dimension bounded by \(d\)._

Finally, we will need the following packing Lemma for set systems with bounded VC-dimension.

**Lemma 4**.: _Let \((X,\mathcal{S})\) be a set system and \(\mu\) a probability measure on the set \(X\). Define a distance \(d_{\mu}\) on the collection of subsets \(\mathcal{S}\) by_

\[d_{\mu}(S_{1},S_{2})=\mu(S_{1}\Delta S_{2}). \tag{2.2}\]
_In other words, \(d_{\mu}\) is the probability that a randomly chosen element from the measure \(\mu\) will be in one set but not the other._

_Let \(\epsilon>0\) and suppose that \(S_{1},...,S_{N}\in\mathcal{S}\) are such that \(d_{\mu}(S_{i},S_{j})\geq\epsilon\) for all \(i\neq j\). Then, if \((X,\mathcal{S})\) has VC-dimension at most \(d\), we have_

\[N\leq\left(\frac{C}{\epsilon}\right)^{d} \tag{2.3}\]

_for an absolute constant \(C\) (we can take for instance \(C=50\))._

This was first proved by Haussler in the case where \(X\) is a finite set and \(\mu\) is the counting measure [18], with a weaker result (losing a logarithmic factor) being obtained earlier by Dudley [15]. The generalization to arbitrary probability measures \(\mu\) follows from this result in a relatively simple manner, and has been noted in the case of certain geometric set systems in [26].

Proof of Lemma 4.: Consider drawing \(k\) independent random samples \(x_{1},...,x_{k}\) from the probability distribution \(\mu\) with replacement. We consider the sets

\[\bar{S}_{j}=\{i:x_{i}\in S_{j}\}\subset\{1,...,k\}. \tag{2.4}\]

It is clear that the VC-dimension of the set system \(\bar{S}_{1},...,\bar{S}_{N}\) viewed as a subsets of \(\{1,...,k\}\) is also at most \(d\). Applying Theorem 1 in [18], we see that if each pair \(\bar{S}_{i}\) and \(\bar{S}_{j}\) differ in at least \(\delta k\) elements for some \(\delta>0\), then

\[N\leq e(d+1)\left(\frac{2e}{\delta}\right)^{d}\leq\left(\frac{C}{\delta} \right)^{d} \tag{2.5}\]

for \(C=25\) (for example).

Finally, we observe that by choosing \(k\) large enough we can guarantee that any two pairs \(\bar{S}_{i}\) and \(\bar{S}_{j}\) differ in at least \(\delta k\) elements for \(\delta=\epsilon/2\) with positive probability. Indeed, for each pair of sets the fraction of elements that they differ in is an average of Bernoulli random variables with expectation at least \(\epsilon\), since \(d_{\mu}(S_{i},S_{j})\geq\epsilon\). Using standard concentration inequalities combined with a union bound (for \(k\) large enough, note that \(N\) is fixed) completes the proof. 

Proof of Lemma 1.: Consider the set system given in (2.1) and the probability measure \(\mu\) defined by

\[\mu=\frac{1}{2}\pi+\frac{1}{2}\pi_{P}, \tag{2.6}\]

where \(\pi\) is the uniform probability measure on \(S^{d-1}\times[-1,1]\), and \(\pi_{P}\) is the empirical measure associated to the set of halfspaces \(P\), i.e.

\[\pi_{P}=\frac{1}{|P|}\sum_{(\omega,b)\in P}\delta_{(\omega,b)} \tag{2.7}\]

where \(\delta_{(\omega,b)}\) denotes the Dirac measure at the point \((\omega,b)\).

Let \(x_{1},...,x_{N}\in B^{d}\) (viewed as elements of the set system \(\mathcal{S}\)) be a maximal set of points such that \(d_{\mu}(x_{i},x_{j})\geq\delta/2\). By Lemma 4 and the VC-dimension bound in Lemma 3, we have that

\[N\leq\left(\frac{2C}{\delta}\right)^{d}. \tag{2.8}\]

Moreover, given an \(z\in B^{d}\) there is an \(x_{i}\) such that \(d_{\mu}(x_{i},z)<\delta/2\) by the maximality of the set \(x_{1},...,x_{N}\). From the definition of \(\mu\), this means that \(d_{\pi}(x_{i},z)<\delta\) and \(d_{\pi_{P}}(x_{i},z)<\delta\). Given the form (2.7) of \(\pi_{P},d_{\pi_{P}}(x_{i},z)<\delta\) is equivalent to

\[|P\cap\{(\omega,b)\in S^{d-1}\times[-1,1],\ \operatorname{sgn}\left(\omega \cdot x_{i}+b\right)\neq\operatorname{sgn}\left(\omega\cdot z+b\right)\}|< \delta|P|=\delta N.\]

On the other hand, \(d_{\mu}(x_{i},z)<\delta\) implies that

\[\mathbb{E}_{\omega\in S^{d-1}}\left[\mathbb{P}(x_{i}\cdot\omega<b<z\cdot \omega\text{ or }z\cdot\omega<b<x_{i}\cdot\omega)\right]=\frac{1}{2}\mathbb{E}_{\omega\in S^{d- 1}}\big{|}(x_{i}-z)\cdot\omega|<\delta, \tag{2.9}\]

where the expectation denotes an average over the sphere \(S^{d-1}\), and the probability is over a uniformly random \(b\in[-1,1]\). It is well-known that for any fixed unit vector \(w\in S^{d-1}\) we have

\[\mathbb{E}_{\omega\in S^{d-1}}|w\cdot\omega|\geq cd^{-1/2} \tag{2.10}\]

for an absolute constant \(c\). Together with (2.9), this implies that \(|x_{i}-z|<C\delta\sqrt{d}\) as desired.
## 3 Approximation by Shallow ReLU\({}^{k}\) Neural Networks

In this section, we give the proof of Theorem 2, which follows easily from the following Proposition.

**Proposition 1**.: _Fix an integer \(k\geq 0\). Let \(\tau\) be a probability distribution on the sphere \(S^{d-1}\times[-1,1]\) which is supported on \(N\) points for \(N\) sufficiently large (\(N\geq 6\) is sufficient). Then there exists a probability distribution \(\tau^{\prime}\) supported on at most \((1-c)N\) points such that for all multi-indices \(\alpha\) with \(|\alpha|\leq k\) we have_

\[\sup_{x\in\mathbb{P}^{d}}\left|D_{x}^{\alpha}\left(\int_{S^{d-1}\times[-1,1]} \sigma_{k}(\mathbf{\omega}\cdot x+b)d\tau(\mathbf{\omega},b)-\int_{S^{d-1}\times[-1,1]} \sigma_{k}(\mathbf{\omega}\cdot x+b)d\tau^{\prime}(\mathbf{\omega},b)\right)\right|\leq CN ^{-\frac{1}{2}-\frac{2(k-|\mathbf{\omega}|)+1}{2d}}, \tag{3.1}\]

_where \(D_{x}^{\alpha}\) denotes the \(\alpha\)-th order derivative with respect to \(x\). Here \(C=C(d,k)\) and \(c\) is an absolute constant._

Proof of Theorem 2.: We repeatedly apply Proposition 1 to the distribution \(\tau\) until the size of the support set is at most \(n/2\). By Proposition 1, for any multi-index \(\alpha\) the error incurred in the \(\alpha\)-th derivative is bounded by

\[Cn^{-\frac{1}{2}-\frac{2(k-|\mathbf{\omega}|)+1}{2d}}\left(\sum_{j=0}^{\infty}(1- c)^{j\left(\frac{1}{2}+\frac{2(k-|\mathbf{\omega}|)+1}{2d}\right)}\right)\lesssim n^{- \frac{1}{2}-\frac{2(k-|\mathbf{\omega}|)+1}{2d}}, \tag{3.2}\]

since the errors in each step form a geometric series whose sum is bounded by a multiple of its largest term (which is the error made in the last step). 

Proof of Theorem 3.: Suppose without loss of generality that \(\left\|f\right\|_{\mathcal{K}_{1}(\mathbb{P}^{d}_{k})}\leq 1\), i.e. that \(f\in B_{1}(\mathbb{P}^{d}_{k})\).

By definition, this means that for any \(\varepsilon>0\) there exist parameters \((\omega_{1},b_{1}),...,(\omega_{N},b_{N})\in S^{d}\times[-1,1]\) and weights \(a_{1},...,a_{N}\in\mathbb{R}\) (for a sufficiently large \(N\)) such that

\[\left\|f-\sum_{i=1}^{N}a_{i}\sigma_{k}(\omega_{i}\cdot x+b_{i})\right\|_{W^{k }(L_{m}(S^{d}))}<\varepsilon, \tag{3.3}\]

and \(\sum_{i=1}^{N}|a_{i}|\leq 1\). The next step is to approximate the sum in (3.3) by an element in \(\Sigma_{n}^{1}(\mathbb{P}^{d}_{k})\). To do this, we split the sum into its positive and negative parts, i.e. we write

\[\sum_{i=1}^{N}a_{i}\sigma_{k}(\omega_{i}\cdot x+b_{i})=\sum_{a_{i}>0}a_{i} \sigma_{k}(\omega_{i}\cdot x+b_{i})-\sum_{a_{i}<0}|a_{i}|\sigma_{k}(\omega_{i }\cdot x+b_{i}). \tag{3.4}\]

By considering the positive and negative pieces separately, we essentially reduce to the case where all \(a_{i}\) are positive. In this case, the sum can be written

\[\sum_{i=1}^{N}a_{i}\sigma_{k}(\omega_{i}\cdot x+b_{i})=\int_{S^{d-1}\times[-1, 1]}\sigma_{k}(\mathbf{\omega}\cdot x+b)d\tau(\mathbf{\omega},b) \tag{3.5}\]

for a probablity measure \(\tau\) supported on at most \(N\) points.

Applying Theorem 2 gives an \(f_{n}\in\Sigma_{n/2}^{1}(\mathbb{P}^{d}_{k})\) such that

\[\left\|f_{n}-\sum_{i=1}^{N}a_{i}\sigma_{k}(\omega_{i}\cdot x+b_{i})\right\|_{W^ {m}(L_{m}(S^{d}))}\leq Cn^{-\frac{1}{2}-\frac{2(k-m)+1}{2d}}, \tag{3.6}\]

whenever \(a_{i}\geq 0\) and \(\sum_{i=1}^{N}a_{i}=1\). Applying this to the positive and negative parts in (3.4) and summing them gives an \(f_{n}\in\Sigma_{n}^{1}(\mathbb{P}^{d}_{k})\) such that

\[\left\|f-f_{n}\right\|_{W^{m}(L_{m}(S^{d}))}\leq Cn^{-\frac{1}{2}-\frac{2(k-m )+1}{2d}}+\varepsilon. \tag{3.7}\]

Since \(\varepsilon>0\) was arbitrary, this completes the proof. 

It remains to prove Proposition 1. The proof utilizes the ideas of geometric discrepancy theory and borrows many ideas from the proof of Proposition 9 in [28]. However, Proposition 9 in [28] only deals with uniform distributions, and a few key modifications are required to deal with the case of 'unbalanced' distributions \(\tau\), which enables us to remove the logarithmic factors in all dimensions in Theorems 1, 2, and 3. In addition, dealing with the higher order smoothness of the ReLU\({}^{k}\) activation function introduces significant technical difficulties.
We first introduce some notation. We will need to work with symmetric tensors in order to handle higher order derivatives of multivariate functions. Our tensors will be defined on the ambient space \(\mathbb{R}^{d+1}\) containing the sphere \(S^{d}\), so let \(I=\{1,...,d+1\}\) denote the relevant indexing set. A (symmetric) tensor \(X\) of order \(m\) is an array of numbers indexed by a tuple \(\mathbf{i}\in I^{m}\), which satisfies

\[X_{\mathbf{i}}=X_{\pi(\mathbf{i})} \tag{3.8}\]

for any permutation \(\pi\) of \(\{1,...,m\}\). Here \(\pi(\mathbf{i})_{j}=\mathbf{i}_{\pi(j)}\) for \(j=1,...,m\). Note that vectors in \(\mathbb{R}^{d+1}\) are symmetric tensors of order one. We adopt the \(\ell^{m}\) norm on the space of symmetric tensors, i.e.

\[\|X\|:=\max_{\mathbf{i}\in I^{m}}|X_{\mathbf{i}}|. \tag{3.9}\]

Given tensors \(X\) and \(Y\) of orders \(m_{1}\) and \(m_{2}\), their tensor product, which is a tensor of order \(m_{1}+m_{2}\), is defined in the standard way by

\[(X\otimes Y)_{\mathbf{ij}}=X_{\mathbf{i}}Y_{\mathbf{j}}, \tag{3.10}\]

where \(\mathbf{i}\in I^{m_{1}}\), \(\mathbf{j}\in I^{m_{2}}\) and \(\mathbf{ij}\) denotes concatenation. We will also write \(X^{\otimes r}\) for the \(r\)-fold tensor product of \(X\) with itself. Supposing that \(m_{1}\geq m_{2}\), we define the contraction, which is a tensor of order \(m_{1}-m_{2}\) by

\[\langle X,Y\rangle_{\mathbf{i}}=\sum_{\mathbf{j}\in I^{m_{2}}}X_{\mathbf{i}} Y_{\mathbf{j}}. \tag{3.11}\]

Note that since we will be exclusively working with \(\mathbb{R}^{d+1}\) with the standard inner product, to simplify the presentation we will not make the distinction between covariance and contravariance in the following.

We remark that repeated contraction can be written in terms of the tensor product in the following way

\[\langle\langle X,Y\rangle,Z\rangle=\langle X,Y\otimes Z\rangle, \tag{3.12}\]

and also note the inequality

\[\|\langle X,Y\rangle\|\leq C\|X\|\|Y\|, \tag{3.13}\]

where \(C=C(d,k)=(d+1)^{k}\).

Given an order \(0\leq m\leq k\), we denote the \(m\)-th derivative (tensor) of the ReLU\({}^{k}\) function (with \(\omega\) and \(b\) fixed) by

\[\sigma_{k}^{(m)}(x;\omega,b)=D_{x}^{m}[\sigma_{k}(\omega\cdot x+b)]=\begin{cases} \frac{k!}{(k-m)!}(\omega\cdot x+b)^{k-m}\omega^{\otimes m}&\omega\cdot x+b \geq 0\\ 0&\omega\cdot x+b<0.\end{cases} \tag{3.14}\]

In order to deal with the additional smoothness of the activation function we will need to utilize higher-order Taylor polynomials. Given points \(x_{1},x_{2}\in S^{d}\), parameters \((\omega,b)\in S^{d-1}\times[-1,1]\), an order \(0\leq m\leq k\), and a number of terms \(0\leq r\leq k-m\), we denote by

\[\mathcal{T}_{x_{1}}^{m,r}(x_{2};\omega,b):=\sum_{q=0}^{r}\frac{1}{q!}\left< \sigma_{k}^{(m+q)}(x_{1};\omega,b),(x_{2}-x_{1})^{\otimes q}\right> \tag{3.15}\]

the \(r\)-th order Taylor polynomials of \(\sigma_{k}^{(m)}(x;\omega,b)\) around \(x_{1}\) evaluated at \(x_{2}\).

Proof of Proposition 1.: Note that since \(\tau\) is supported on \(N\) points the integral which we are trying to approximate in Proposition 1 is given by

\[\int_{S^{d-1}\times[-1,1]}\sigma_{k}(\omega\cdot x+b)d\tau(\omega,b)=\sum_{( \omega,b)\in S}a_{\omega,b}\sigma_{k}(\omega\cdot x+b), \tag{3.16}\]

where \(|S|=N\) and the coefficients \(a_{\omega,b}\) satisfy \(a_{\omega,b}\geq 0\) and \(\sum_{(\omega,b)\in S}a_{\omega,b}=1\).

Let \(M\) denote the median of the coefficients \(a_{\omega,b}\) and set

\[S_{-}=\{(\omega,b)\in S:\ a_{\omega,b}\leq M\},\ \ S_{+}=\{(\omega,b)\in S:a_{ \omega,b}>M\}.\]

This gives a decomposition of the sum in (3.16) in terms of its large and small coefficients

\[\sum_{(\omega,b)\in S}a_{\omega,b}\sigma_{k}(\omega\cdot x+b)=\sum_{(\omega,b )\in S_{-}}a_{\omega,b}\sigma_{k}(\omega\cdot x+b)+\sum_{(\omega,b)\in S_{+}}a _{\omega,b}\sigma_{k}(\omega\cdot x+b). \tag{3.17}\]

We will leave the second, i.e. the large, sum untouched and approximate the small sum by

\[\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\sigma_{k}(\omega\cdot x+b)\approx\sum_{ (\omega,b)\in T}b_{\omega,b}\sigma_{k}(\omega\cdot x+b), \tag{3.18}\]
where \(T\subset S_{-}\) and \(|T|\leq(1-c)|S_{-}|\), the new coefficients \(b_{\omega,b}\geq 0\) and satisfy

\[\sum_{(\omega,b)\in T}b_{\omega,b}=\sum_{(\omega,b)\in S_{-}}a_{\omega,b},\]

and the error of approximation satisfies (using the tensor norm we have introduced)

\[\sup_{x\in\mathcal{S}^{d}}\left\|\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\sigma_{ k}^{(m)}(x;\omega,b)-\sum_{(\omega,b)\in T}b_{\omega,b}\sigma_{k}^{(m)}(x; \omega,b)\right\|\leq CN^{-\frac{1}{2}-\frac{2(k-m)+1}{2d}} \tag{3.19}\]

for \(m=0,...,k\). Setting

\[\tau^{\prime}=\sum_{(\omega,b)\in T}b_{\omega,b}\delta_{\omega,b}+\sum_{( \omega,b)\in S_{+}}a_{\omega,b}\delta_{\omega,b} \tag{3.20}\]

now completes the proof since \(|S_{-}|\geq N/2\) (here \(\delta_{\omega,b}\) denotes the Dirac delta distribution at \((\omega,b)\)).

We now turn to the heart of the proof, which is constructing an approximation (3.18) which satisfies (3.19). Note first that by construction, we have

\[\max_{(\omega,b)\in S_{-}}a_{\omega,b}\leq M\leq\frac{2}{N}, \tag{3.21}\]

i.e. all of the coefficients in the small half are at most \(2/N\). This holds since at least half (i.e. at least \(N/2\)) of the \(a_{\omega,b}\) are at least as large as the median \(M\) and \(\sum_{(\omega,b)\in S}a_{\omega,b}=1\).

Next we construct a multi-scale covering of the ball using Lemma 1. For \(l=1,...,L\) with \(2^{L}>N\) we apply Lemma 1 with \(P=S_{-}\) and \(\delta=2^{-l}\) to obtain a sequence of sets \(N_{l}\subset B^{d}\) with \(|N_{l}|\leq(C2^{l})^{d}\) such that for any \(x\in B^{l}\) there exists a \(z\in N_{l}\) with \(|x-z|\leq C2^{-l}\sqrt{d}\) and

\[|\{y\in S_{-}:\operatorname{sgn}\left(y\cdot x\right)\neq\operatorname{sgn} \left(y\cdot z\right)\}|\leq 2^{-l}|S_{-}|\leq 2^{-l}N.\]

Given a point \(x\in S^{d}\), we denote by \(\pi_{l}(x)\) the point \(z\in N_{l}\) satisfying these properties (if this point is not unique we choose one arbitrarily for each \(x\)).

For each level \(l=1,...,L\), each point \(x\in N_{l}\), and each index \(m=0,..,k\) we consider the function

\[\phi_{x,l}^{m}(\omega,b)=\begin{cases}\sigma_{k}^{(m)}(x;\omega,b)-\mathcal{T }_{\pi_{l-1}(x)}^{m,k-m}(x;\omega,b)&l\geq 2\\ \sigma_{k}^{(m)}(x;\omega,b)&l=1,\end{cases} \tag{3.22}\]

where \(\mathcal{T}_{\pi_{l-1}(x)}^{m,k-m}(x;\omega,b)\) is the \((k-m)\)-th order Taylor polynomial of \(\sigma_{k}^{(m)}(x;\omega,b)\) defined in (3.15).

We note the following bounds on \(\phi_{x,l}^{m}(\omega,b)\). First, if \(\operatorname{sgn}\left(\omega\cdot x+b\right)=\operatorname{sgn}\left( \omega\cdot\pi_{l-1}(x)+b\right)\) (for \(l\geq 2\)), then

\[\phi_{x,l}^{m}(\omega,b)=0. \tag{3.23}\]

This holds since on the half space \(\{x:\omega\cdot x+b\geq 0\}\) the function \(\sigma_{k}^{(m)}(x;\omega,b)\) is a polynomial of degree \(k-m\) in \(x\). Thus on this half-space it is equal to its \((k-m)\)-th order Taylor polynomial about any point. So if \(x\) and \(\pi_{l-1}(x)\) both lie in this half-space, then the difference in (3.22) vanishes. On the other hand, if \(x\) and \(\pi_{l-1}(x)\) both lie in the complement, then all terms in (3.22) are 0.

On the other hand, for any \(x\in B^{d}\) and \((\omega,b)\in S^{d-1}\times[-1,1]\) we have the bound

\[\|\phi_{x,l}^{m}(\omega,b)\|\leq C2^{-l(k-m)}, \tag{3.24}\]

where \(C=C(d,k)\). This holds since \(\sigma_{k}^{(m)}(x;\omega,b)\) (as a function of \(x\)) has \((k-m)\)-th order derivatives which are bounded by \(C(k)=k!2^{k-m}\) for \(x\in B^{d}\) by (3.14). Thus using Taylor's theorem the difference in (3.22) is bounded by

\[\left\|\sigma_{k}^{(m)}(x;\omega,b)-\mathcal{T}_{\pi_{l-1}(x)}^{m,k-m}(x; \omega,b)\right\|\leq C|x-\pi_{l-1}(x)|^{k-m}\leq C2^{-l(k-m)}, \tag{3.25}\]

for \(C=C(d,k)\). When \(l=1\) we also trivially obtain the bound (3.24).

The next step is to decompose the functions \(\sigma_{k}^{(m)}(x;\omega,b)\) with \((\omega,b)\in S_{-}\) in terms of the \(\phi_{x,l}^{m}(\omega,b)\). This is captured in the following technical Lemma.
**Lemma 5**.: _Let \(\phi_{x,l}^{m}\) be defined by (3.22). For \(x\in S^{l}\) define \(x_{L}=\pi_{L}(x)\) and \(x_{l}=\pi_{l}(x_{l+1})\) for \(l<L\)._

_Then for any \(m=0,...,k\), \(x\in S^{l}\) and \((\omega,b)\in S_{-}\) we have_

\[\sigma_{k}^{(m)}(x;\omega,b)=\sum_{l=1}^{L}\phi_{x_{j},j}^{m}(\omega,b)+\sum_{ i=1}^{k-m}\sum_{l=1}^{L}\left\langle\phi_{x_{l},l}^{m+i}(\omega,b),\Gamma_{ lid}^{m}(x)\right\rangle, \tag{3.26}\]

_for a collection of tensors \(\Gamma_{i,l}^{m}(x)\) depending upon \(x\) which satisfy the bound_

\[\|\Gamma_{i,l}^{m}(x)\|\leq C2^{-il}, \tag{3.27}\]

_for a constant \(C(d,k)\)._

The proof of this Lemma is a technical, but relatively straightforward calculation, so we postpone it until the end of this Section and complete the proof of Proposition 1 first.

Utilizing the decomposition (3.26) we write the LHS of (3.19) as

\[\begin{split}\sup_{x\in S^{l}}&\left\|\sum_{l=1}^{ L}\left[\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\phi_{x_{l},l}^{m}(\omega,b)- \sum_{(\omega,b)\in T}b_{\omega,b}c\phi_{x_{l},l}^{m}(\omega,b)\right]\right. \\ &\left.+\sum_{l=1}^{L}\sum_{l=1}^{k-m}\left\langle\sum_{(\omega, b)\in S_{-}}a_{\omega,b}\phi_{x_{l},l}^{m+i}(\omega,b)-\sum_{(\omega,b)\in T }b_{\omega,b}\phi_{x_{l},l}^{m+i}(\omega,b),\Gamma_{i,l}^{m}(x)\right\rangle \right\|.\end{split} \tag{3.28}\]

Utilizing the triangle inequality, the bound (3.13), and the bound (3.27), we see that it suffices to find the subset \(T\subset S_{-}\) with \(|T|\leq(1-c)|S_{-}|\), and new coefficients \(b_{\omega,b}\geq 0\) satisfying \(\sum_{(\omega,b)\in T}b_{\omega,b}=\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\) such that for \(m=0,...,k\) we have

\[\sum_{l=1}^{L}\sum_{i=0}^{k-m}2^{-il}\sup_{x\in N_{l}}\left\|\sum_{(\omega,b) \in S_{-}}a_{\omega,b}\phi_{x,l}^{m+i}(\omega,b)-\sum_{(\omega,b)\in T}b_{ \omega,b}\phi_{x,l}^{m+i}(\omega,b)\right\|\leq CN^{-\frac{1}{2}-\frac{2(k-m) +1}{2d}} \tag{3.29}\]

for a constant \(C=C(d,k)\).

To find this set \(T\) and new coefficients \(b_{\omega,b}\), we divide the set \(P=S_{-}\) into disjoint subsets \(P_{1},..,P_{l}\) of size \(3\) with

\[\left|\bigcup_{i=1}^{l}P_{i}\right|\geq|S_{-}|/2. \tag{3.30}\]

(Note that here we need \(|S_{-}|\geq 3\) which follows from \(N\geq 6\).) We denote the three elements of each set \(P_{j}\) by

\[P_{j}=\{u_{j},v_{j},w_{j}\},\]

which are ordered so that the coefficients satisfy \(0\leq a_{u_{j}}\leq a_{v_{j}}\leq a_{w_{j}}\). Note that \(S_{-}\) contains halfspaces and so each of the elements \(u_{j},v_{j},w_{j}\) consist of an \((\omega,b)\) tuple.

Based upon the partition \(P_{1},...,P_{l}\), we will use a modification of the partial coloring argument given in [28] (the idea is originally due to Spencer [40] and Beck [6]). The main difference is in how we use a partial coloring to reduce the number of terms in the sum over \(S_{-}\).

Given a 'partial coloring' \(\chi:\{1,...,t\}\rightarrow\{-1,0,1\}\), we transform the sum \(\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\sigma_{k}(\omega\cdot x+b)\) in the following way. If \(\chi(j)=1\), we remove the term corresponding to \(u_{j}\), double the coefficient \(a_{v_{j}}\) of the term corresponding to \(v_{j}\), and add the difference \(a_{u_{j}}-a_{v_{j}}\) to the coefficient \(a_{w_{j}}\) of the term corresponding to \(w_{j}\). If \(\chi(j)=-1\), we do the same but reverse the roles of \(u_{j}\) and \(v_{j}\).

This results in a transformed sum \(\sum_{(\omega,b)\in T}b_{\omega,b}\sigma_{k}(\omega\cdot x+b)\) over a set \(T\subset S_{-}\) and with coefficients \(b_{\omega,b}\) for \((\omega,b)\in T\) described as follows. Let

\[R_{j}=\begin{cases}\emptyset&\chi(j)=0\\ \{u_{j}\}&\chi(j)=1\\ \{v_{j}\}&\chi(j)=-1,\end{cases} \tag{3.31}\]

denote the removed set for each \(P_{j}\). Then the set \(T\) is given by

\[T=S_{-}\setminus\left(\bigcup_{j=1}^{l}R_{j}\right), \tag{3.32}\]
and for \((\omega,b)\in T\) the coefficients \(b_{\omega,b}\) are given by

\[b_{\omega,b}=\begin{cases}a_{\omega,b}&(\omega,b)\notin\bigcup_{j}P_{j}\\ (1+\chi(j))a_{\omega,b}&(\omega,b)=v_{j}\\ (1-\chi(j))a_{\omega,b}&(\omega,b)=u_{j}\\ a_{\omega,b}+\chi(j)(a_{uj}-a_{v_{j}})&(\omega,b)=w_{j}.\end{cases} \tag{3.33}\]

We have constructed this transformation so that

\[\sum_{(\omega,b)\in T}b_{\omega,b}=\sum_{(\omega,b)\in S_{-}}a_{\omega,b},\]

the \(b_{\omega,b}\geq 0\) since \(w_{j}\) has the largest coefficient among the halfspaces in \(P_{j}\), and for any \(x\in S^{d}\) the error in the \(m\)-th derivative is given by

\[\begin{split}\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\sigma^{(m)}_ {k}(x;\omega,b)-\sum_{(\omega,b)\in T}b_{\omega,b}\sigma^{(m)}_{k}(x;\omega,b) =\\ \sum_{j=1}^{t}\chi(j)\left[-a_{u_{j}}\sigma^{(m)}_{k}(x;u_{j})+a _{v_{j}}\sigma^{(m)}_{k}(x;v_{j})+(a_{u_{j}}-a_{v_{j}})\sigma^{(m)}_{k}(x;w_{ j})\right].\end{split} \tag{3.34}\]

Using the linearity of the derivative and the definition of the Taylor polynomial (3.15), this implies that for any \(x\in S^{d}\), any level \(l=1,...,L\), and any \(m=0,...,k\) we have

\[\sum_{(\omega,b)\in S_{-}}a_{\omega,b}\phi^{m}_{x,l}(\omega,b)-\sum_{(\omega, b)\in T}b_{\omega,b}\phi^{m}_{x,l}(\omega,b)=\sum_{j=1}^{l}\chi(j)\Psi^{m}_{x,l,j}, \tag{3.35}\]

where we have defined

\[\Psi^{m}_{x,l,j}=-a_{u_{j}}\phi^{m}_{x,l}(u_{j})+a_{v_{j}}\phi^{m}_{x,l}(v_{j} )+(a_{u_{j}}-a_{v_{j}})\phi^{m}_{x,l}(w_{j}). \tag{3.36}\]

Further, for any index \(j\) such that \(\chi(j)\neq 0\), we have eliminated one term (either \(u_{j}\) or \(v_{j}\)) from the sum. Thus

\[|T|=|S|-|\{j:\ \chi(j)\neq 0\}|. \tag{3.37}\]

We proceed to find a partial coloring \(\chi:\{1,...,t\}\rightarrow\{-1,0,1\}\) with a positive fraction of non-zero entries, i.e. with \(|\{j:\ \chi(j)\neq 0\}|\geq ct\), such that for \(m=0,...,k\)

\[\sum_{l=1}^{L}\sum_{i=0}^{k-k}2^{-il}\sup_{x\in N_{l}}\left\|\sum_{j=1}^{t} \chi(j)\Psi^{m+l}_{x,l,j}\right\|\leq CN^{-\frac{1}{2}-\frac{2(k-m)+1}{2d}}, \tag{3.38}\]

for a constant \(C=C(d,k)\).

By (3.35) this will guarantee that the LHS in (3.29) is sufficiently small, and by (3.37) this will guarantee that the set \(T\) is small enough, since by (3.30)

\[|T|=|S|-|\{j:\ \chi(j)\neq 0\}|\leq|S|-ct\leq\left(1-\frac{c}{6}\right)|S_{-}|. \tag{3.39}\]

The existence of such a partial coloring \(\chi\) follows from a well-known technique in discrepancy theory called the partial coloring method.

Given a (total) coloring \(\varepsilon:\{1,...,t\}\rightarrow\{\pm 1\}\) we consider the quantities

\[E^{m}_{x,l}(\varepsilon):=\sum_{j=1}^{l}\varepsilon(j)\Psi^{m}_{x,l,j} \tag{3.40}\]

for each \(x\in N_{l}\). We would like to find a coloring \(\varepsilon\) such that \(\|E^{m}_{x,l}(\varepsilon)\|\leq\Delta^{m}_{l}\) for all \(l=1,...,L\), \(m=0,...,k\) and \(x\in N_{l}\), where the \(\Delta^{m}_{l}\) are suitable parameters chosen so that

\[\sum_{l=1}^{L}\sum_{i=0}^{k-m}2^{-il}\Delta^{m+i}_{l}\leq CN^{-\frac{1}{2}- \frac{2(k-m)+1}{2d}}, \tag{3.41}\]

for \(m=0,...,k\).
One strategy would be to choose \(\varepsilon\) uniformly at random, bound the tail of the random variable \(E_{x,l}^{m}(\varepsilon)\), and use a union bound over \(x\in N_{l}\). Unfortunately, this strategy will lose a factor \(\sqrt{\log N}\). The ingenious method to get around this, due to Spencer [40] and Beck [6], is to show that instead there exist _two_ colorings \(\varepsilon_{1}\) and \(\varepsilon_{2}\) such that \(\|E_{x,l}^{m}(\varepsilon_{1})-E_{x,l}^{m}(\varepsilon_{2})\|\leq\Delta_{l}^ {m}\) for all \(l=1,...,L\), \(m=0,...,k\), and \(x\in N_{l}\), and such that \(\varepsilon_{1}\) and \(\varepsilon_{2}\) differ in many indices, i.e.

\[|\{j:\,\varepsilon_{1}(j)\neq\varepsilon_{2}(j)\}|\geq ct \tag{3.42}\]

for an absolute constant \(c\). Then \(\chi=\frac{1}{2}(\varepsilon_{1}-\varepsilon_{2})\) gives the desired partial coloring.

We will prove the existence of these two colorings \(\varepsilon_{1}\) and \(\varepsilon_{2}\) for suitably chosen parameters \(\Delta_{l}^{m}\) satisfying (3.41). To help organize this calculation, it is convenient to introduce the notion of the entropy of a discrete distribution (see for instance [1, 29]). (Note that for simplicity all of the logarithms in the following are taken with base 2.)

**Definition 3**.: _Let \(X\) be a discrete random variable, i.e. the range of \(X\) is a countable set \(\Lambda\). The entropy of \(X\) is defined by_

\[H(X)=-\sum_{\lambda\in\Lambda}p_{\lambda}\log(p_{\lambda}), \tag{3.43}\]

_where \(p_{\lambda}=\mathbb{P}(X=\lambda)\) is the probability of the outcome \(\lambda\)._

One important property of the entropy we will use is subadditivity, i.e. if \(X=(X_{1},...,X_{r})\), then

\[H(X)\leq\sum_{j=1}^{r}H(X_{j}), \tag{3.44}\]

where we have equality in the above bound when the components \(X_{j}\) of \(X\) are independent.

An important component of the calculation is the following Lemma from [28] (see also [1, 30]).

**Lemma 6** (Lemma 11 in [28]).: _Let \(\varepsilon:\{1,...,t\}\to\{\pm 1\}\) be a uniformly random coloring. Let \(b\) be a function of \(\varepsilon\) and suppose that the entropy satisfies \(H(b(\varepsilon))\leq t/5\). Then there exist two colorings \(\varepsilon_{1},\varepsilon_{2}\) differing in at least \(t/4\) components such that \(b(\varepsilon_{1})=b(\varepsilon_{2})\)._

We utilize this lemma in the following way. Take each entry of the (tensor-valued) random variable \(E_{x,l}^{m}(\varepsilon)\) defined in (3.40) and round it to the nearest multiple of the (still undetermined) parameter \(\Delta_{l}^{m}\). This results in a random variable

\[b_{x,l}^{m}(\varepsilon)=[(\Delta_{l}^{m})^{-1}E_{x,l}^{m}(\varepsilon)], \tag{3.45}\]

where \([\cdot]\) denote the (component-wise) nearest integer function. Note that if \(b_{x,l}^{m}(\varepsilon_{1})=b_{x,l}^{m}(\varepsilon_{2})\), then it follows that \(\|E_{x,l}^{m}(\varepsilon_{1})-E_{x,l}^{m}(\varepsilon_{2})\|\leq\Delta_{l}^ {m}\). Applying Lemma 6 and the subadditivity of the entropy (3.44), we see that if

\[\sum_{l=1}^{L}\sum_{m=0}^{k}\sum_{x\in N_{l}}H(b_{x,l}^{m}(\varepsilon))\leq t/5 \tag{3.46}\]

for an appropriate choice of \(\Delta_{l}^{m}\) satisfying (3.41), then there exist two colorings \(\varepsilon_{1}\) and \(\varepsilon_{2}\) satisfying the desired condition with \(c=1/4\).

It remains to choose the parameters \(\Delta_{l}^{m}\) satisfying (3.41) and to bound the sum in (3.46). For this, we utilize the following Lemma from [28], which bounds the entropy of a 'rounded' random variable in terms of the tails of the underlying real-valued random variable.

**Lemma 7** (Lemma 11 in [28]).: _Let \(E\) be a real valued random variable satisfying the tail estimates_

\[\mathbb{P}(E\geq\alpha M)\leq e^{-\alpha^{2}/2},\;\mathbb{P}(E\leq-\alpha M) \leq e^{-\alpha^{2}/2}, \tag{3.47}\]

_for some parameter \(M\). Let \(b(E)\) denote the random variable obtained by rounding \(E\) to the nearest multiple of \(\Delta=2\lambda M\). Then the entropy of \(b\) satisfies_

\[H(b)\leq G(\lambda):=C_{0}\begin{cases}e^{-\lambda^{2}/9}&\lambda\geq 10\\ 1&.1<\lambda<10\\ -\log(\lambda)&\lambda\leq.1\end{cases} \tag{3.48}\]

_for an absolute constant \(C_{0}\)._
To apply this Lemma, we bound the tails of the random variables \(E^{m}_{x,l}(\varepsilon)\). This follows using Bernstein's inequality as in [28]. Fix an \(l\geq 2\) and an \(x\in N_{l}\). We call an index \(j\) 'good' if

\[\operatorname{sgn}(\omega\cdot x+b)=\operatorname{sgn}(\omega\cdot\pi_{l-1}(x) =b) \tag{3.49}\]

for \((\omega,b)=u_{j},v_{j},\) and \(w_{j}\), and 'bad' otherwise. Using (3.23) we see that for the good indices we have

\[\Psi^{m}_{x,l,j}=0. \tag{3.50}\]

For the bad indices, we utilize 3.24 to get

\[\|\Psi^{m}_{x,l,j}\|\leq C2^{-(k-m)l}N^{-1}, \tag{3.51}\]

since \(a_{u_{j}},a_{v_{j}}\leq 2/N\) by (3.21). Next, we bound the number of bad indices. An index is bad if

\[\operatorname{sgn}(\omega\cdot x+b)\neq\operatorname{sgn}(\omega\cdot\pi_{l- 1}(x)+b), \tag{3.52}\]

for \((\omega,b)=u_{j},v_{j}\) or \(w_{j}\). From the construction of \(N_{l-1}\) using Lemma 2, the number of \((\omega,b)\) for which (3.52) occurs (and thus the number of bad indices) is bounded by \(2^{-l}|S_{-}|\leq C2^{-l}N\).

Thus, Bernstein's inequality (applied only to the bad indices) gives the following bound on the components of the random variable \(E^{m}_{x,l}\),

\[\mathbb{P}\left((E^{m}_{x,l})_{l}\geq\alpha M^{m}_{l}\right)\leq e^{-\alpha^{ 2}/2} \tag{3.53}\]

for all \(\mathbf{i}\in I^{m}\), where

\[M^{m}_{l}=C2^{-\left(k-m+\frac{1}{2}\right)}lN^{-1/2}, \tag{3.54}\]

for a constant \(C=C(d,k)\). The same bound holds also for the negative tails.

The proof is completed via the following calculation (see [28, 30] for similar calculations). We let \(\alpha,\beta>0\) be parameters to be specified in a moment and define a function

\[\Lambda_{\alpha,\beta}(x)=\begin{cases}2^{\alpha x}&x\geq 0\\ 2^{\beta x}&x\leq 0.\end{cases} \tag{3.55}\]

Let \(\kappa>0\) be another parameter and set \(\tau\) to be the largest integer satisfying \(2^{d\tau}\leq\kappa N\). We set the discretization parameter to be

\[\Delta^{m}_{l}=2M^{m}_{l}\Lambda_{\alpha,\beta}(l-\tau). \tag{3.56}\]

Fix an \(m\) with \(0\leq m\leq k\). We calculate

\[\begin{split}\sum_{l=1}^{L}\sum_{i=0}^{k-m}2^{-il}\Delta^{m+i}_{l} &\leq CN^{-1/2}\sum_{l=0}^{k-m}\sum_{l=-\infty}^{\infty}2^{-il}2^{- \left(k-m-i+\frac{1}{2}\right)l}\Lambda_{\alpha,\beta}(l-\tau)\\ &\leq CN^{-1/2}\sum_{l=-\infty}^{\infty}2^{-\left(k-m+\frac{1}{2} \right)l}\Lambda_{\alpha,\beta}(l-\tau),\end{split} \tag{3.57}\]

since all of the terms in the sum over \(i\) are the same. Making a change of variables in the last sum, we get

\[\sum_{l=1}^{L}\sum_{i=0}^{k-m}2^{-il}\Delta^{m+i}_{l}\leq CN^{-1/2}2^{-\left( k-m+\frac{1}{2}\right)\tau}\sum_{l=-\infty}^{\infty}2^{-\left(k-m+\frac{1}{2} \right)l}\Lambda_{\alpha,\beta}(l). \tag{3.58}\]

If we now choose \(\alpha\) and \(\beta\) such that the above sum over \(l\) converges (this will happen as long as \(\alpha<k-m+\frac{1}{2}<\beta\)), then we get

\[\sum_{l=1}^{L}\sum_{i=0}^{k-m}2^{-il}\Delta^{m+i}_{l}\leq CN^{-\frac{1}{2}- \frac{2(k-m)+1}{2d}}, \tag{3.59}\]

since by construction \(2^{\tau}\geq(1/2)(\kappa N)^{1/d}\) (note the constant \(C\) depends upon the choice of \(\kappa\) which will be made shortly). This verifies (3.41).

To verify the entropy condition, we calculate

\[\sum_{l=1}^{L}\sum_{m=0}^{k}\sum_{x\in N_{l}}H(b^{m}_{x,l}(\varepsilon))\leq \sum_{l=1}^{L}\sum_{m=0}^{k}\sum_{x\in N_{l}}\sum_{l\in I^{m}}H(b^{m}_{x,l}( \varepsilon)_{\mathbf{i}}) \tag{3.60}\]
using subadditivity of the entropy. We now use Lemma 7 combined with the tail bound estimate (3.53) to get

\[H(b^{m}_{x,l}(\mathbf{e})_{i})\leq G(\Delta^{m}_{l}/(2M^{m}_{l}))=G(\Lambda_{\alpha, \beta}(l-\tau)). \tag{3.61}\]

Using that \(|I^{m}|\leq C=C(d,k)\) and \(|N_{l}|\leq C2^{dl}\), we get that

\[\sum_{l=1}^{L}\sum_{m=0}^{k}\sum_{x\in\mathcal{N}_{l}}H(b^{m}_{x,l}(\mathbf{e})) \leq C\sum_{l=1}^{L}2^{dl}G(\Lambda_{\alpha,\beta}(l-\tau))\leq C\sum_{l=\infty }^{\infty}2^{dl}G(\Lambda_{\alpha,\beta}(l-\tau)). \tag{3.62}\]

Finally, making another change of variables, we get

\[\sum_{l=1}^{L}\sum_{m=0}^{k}\sum_{x\in\mathcal{N}_{l}}H(b^{m}_{x,l}(\mathbf{e})) \leq C2^{d\tau}\sum_{l=\infty}^{\infty}2^{dl}G(\Lambda_{\alpha,\beta}(l))\leq C \kappa N, \tag{3.63}\]

since it is easy to verify that the above sum over \(l\) converges for any \(\alpha,\beta>0\). Choosing \(\kappa\) sufficiently small so that \(C\kappa\leq 1/60\) will guarantee that the condition (3.46) is satisfied (since \(t\geq N/12\) by (3.30)) and this completes the proof. 

Proof of Lemma 5.: We first prove that for \(m=0,...,k\), \((\mathbf{\omega},b)\in S^{d-1}\times[-1,1]\) and \(l=1,...,L\) we have

\[\sigma^{(m)}_{k}(x_{l};\mathbf{\omega},b)=\sum_{j=1}^{l}\phi^{m}_{x_{j,j},l}(\mathbf{ \omega},b)+\sum_{i=1}^{k-m-1}\sum_{j=1}^{l}\left\langle\phi^{m+i}_{x_{j,j}}( \mathbf{\omega},b),\Gamma^{m,l}_{i,j}(x)\right\rangle, \tag{3.64}\]

where the tensors \(\Gamma^{m,l}_{i,j}(x)\) satisfy the bound

\[\left\|\Gamma^{m,l}_{i,j}(x)\right\|\leq C2^{-ij}, \tag{3.65}\]

for a constant \(C=C(d,k)\).

We prove this by (reverse) induction on \(m\). Note if \(m=k\) the equation (3.64) holds since the definition of \(\phi^{(m)}_{x,l}\) in (3.22) becomes

\[\phi^{m}_{x,l}(\mathbf{\omega},b)=\begin{cases}\sigma^{(m)}_{k}(x,\mathbf{\omega},b)- \sigma^{(m)}_{k}(\pi_{l-1}(x);\mathbf{\omega},b)&l\geq 2\\ \sigma^{(m)}_{k}(x,\mathbf{\omega},b)&l=1,\end{cases} \tag{3.66}\]

Let \(0\leq m\leq k\) and suppose that (3.64) holds for \(m+1,...,k\). We will show that it also holds for \(m\). Expanding out the Taylor polynomial in the definition of \(\phi^{m}_{x,l}\) for \(x=x_{l}\) we see that

\[\sigma^{(m)}_{k}(x_{l};\mathbf{\omega},b) =\phi^{m}_{x_{l},l}(\mathbf{\omega},b)+\mathcal{T}^{m,k-m}_{x_{l-1}}( x_{l};\mathbf{\omega},b) \tag{3.67}\] \[=\phi^{m}_{x_{l},l}(\mathbf{\omega},b)+\sum_{\mathbf{\omega}=0}^{k-m}\frac {1}{q!}\left\langle\sigma^{(m+q)}_{k}(x_{l-1};\mathbf{\omega},b),(x_{l}-x_{l-1})^ {\otimes q}\right\rangle\] \[=\phi^{m}_{x_{l},l}(\mathbf{\omega},b)+\sigma^{(m)}_{k}(x_{l-1};\mathbf{ \omega},b)+\sum_{q=1}^{k-m}\frac{1}{q!}\left\langle\sigma^{(m+q)}_{k}(x_{l-1}; \mathbf{\omega},b),(x_{l}-x_{l-1})^{\otimes q}\right\rangle.\]

Applying this expansion recursively to \(\sigma^{(m)}_{k}(x_{l-1};\mathbf{\omega},b)\), we get

\[\sigma^{(m)}_{k}(x_{l};\mathbf{\omega},b)=\sum_{j=1}^{l}\phi^{m}_{x_{j,j}}(\mathbf{ \omega},b)+\sum_{p=1}^{l-1}\sum_{q=1}^{k-m}\frac{1}{q!}\left\langle\sigma^{(m+q )}_{k}(x_{p};\mathbf{\omega},b),(x_{p+1}-x_{p})^{\otimes q}\right\rangle. \tag{3.68}\]

Now we use the inductive assumption to expand \(\sigma^{(m+q)}_{k}(x_{p};\mathbf{\omega},b)\) using (3.64) and apply the identity (3.12) to get

\[\sigma^{(m)}_{k}(x_{l};\mathbf{\omega},b)=\sum_{j=1}^{l}\phi^{m}_{x_{j,j}}(\mathbf{\omega},b) +\sum_{p=1}^{l-1}\sum_{q=1}^{k-m}\frac{1}{q!}\sum_{j=1}^{p}\left\langle\phi ^{m+q}_{x_{j,j}}(\mathbf{\omega},b),(x_{p+1}-x_{p})^{\otimes q}\right\rangle \tag{3.69}\] \[+\sum_{p=1}^{l-1}\sum_{q=1}^{k-m}\frac{1}{q!}\sum_{j=1}^{k-m-q-1} \sum_{j=1}^{q-p-1}\left\langle\phi^{m+q+\ell}_{x_{j,j}}(\mathbf{\omega},b),\Gamma^{m +q,l}_{f,j}(x)\otimes(x_{p+1}-x_{p})^{\otimes q}\right\rangle.\]

Rearranging this sum, we obtain

\[\sigma^{(m)}_{k}(x_{l};\mathbf{\omega},b)=\sum_{j=1}^{l}\phi^{m}_{x_{j,j}}(\mathbf{ \omega},b)+\sum_{i=1}^{k-m}\sum_{j=1}^{l-1}\left\langle\phi^{m+i}_{x_{j,j}}(\mathbf{ \omega},b),\Gamma^{m,l}_{i,j}(x)\right\rangle, \tag{3.70}\]
where the tensors \(\Gamma_{i,j}^{m,l}(x)\) are defined recursively by

\[\Gamma_{i,j}^{m,l}(x)=\frac{1}{i!}\sum_{p=j}^{l-1}(x_{p+1}-x_{p})^{\otimes j}+ \sum_{p=q}^{l-1}\sum_{q=1}^{i-1}\frac{1}{q!}\Gamma_{i-q,j}^{m+q,l}(x)\otimes(x_{ p+1}-x_{p})^{\otimes q}. \tag{3.71}\]

Finally, we bound the norm \(\|\Gamma_{i,j}^{m,l}(x)\|\). By construction, the points \(x_{p}\) satisfy \(|x_{p+1}-x_{p}|\leq C2^{-p}\) for a dimension dependent constant \(C=C(d)\) (in the Euclidean norm which bounds the \(\ell^{\infty}\)-norm). This gives the bound

\[\|\Gamma_{i,j}^{m,l}(x)\|\leq C\left(\frac{1}{i!}\sum_{p=j}^{l-1}2^{-pj}+\sum_ {p=j}^{l-1}\sum_{q=1}^{i-1}\frac{1}{q!}2^{-pq}\|\Gamma_{i-q,j}^{m+q,l}\|\right). \tag{3.72}\]

Utilizing the inductive assumption to bound \(\|\Gamma_{i-q,j}^{m+q,l}\|\) we get

\[\|\Gamma_{i,j}^{m,l}\| \leq C\left(\frac{1}{i!}\sum_{p=j}^{l-1}2^{-pj}+\sum_{p=j}^{l-1} \sum_{q=1}^{i-1}\frac{1}{q!}2^{-pq}2^{-(i-q)j}\right) \tag{3.73}\] \[\leq C\left(\frac{1}{i!}\sum_{p=j}^{\infty}2^{-pj}+2^{-ij}\sum_{p =j}^{\infty}\sum_{q=1}^{\infty}\frac{1}{q!}2^{-q(p-j)}\right)\leq C2^{-ij},\]

for a potentially different constant \(C\). However, the induction is completed after a finite number (namely \(k+1\)) steps. Thus the constant \(C=C(d,k)\) can be taken uniform in \(m\). This proves (3.64).

To prove (3.26), we write

\[\sigma_{k}^{(m)}(x;\omega,b) =\left[\sigma_{k}^{(m)}(x;\omega,b)-\mathcal{T}_{\omega_{L}}^{m, k-m}(x;\omega,b)\right]+\mathcal{T}_{\omega_{L}}^{m,k-m}(x,\omega,b) \tag{3.74}\] \[=\left[\sigma_{k}^{(m)}(x;\omega,b)-\mathcal{T}_{\omega_{L}}^{m, k-m}(x;\omega,b)\right]+\sum_{q=0}^{k-m}\frac{1}{q!}\left\langle\sigma_{k}^{(m+q)} (x_{L};\omega,b),(x-x_{L})^{\otimes q}\right\rangle.\]

We claim that if \(\omega,b\in S_{-}\), then the first term

\[\sigma_{k}^{(m)}(x;\omega,b)-\mathcal{T}_{\omega_{L}}^{m,k-m}(x;\omega,b)=0. \tag{3.75}\]

This follows since by construction using Lemma 1, we have the bound

\[|S_{-}\cap\{(\omega,b)\in S^{d-1}\times[-1,1],\ \operatorname{sgn}\left( \omega\cdot x+b\right)\neq\operatorname{sgn}\left(\omega\cdot\pi_{L}(x)+b \right)\}|\leq 2^{-L}|S_{-}|<1, \tag{3.76}\]

since \(2^{-L}<N^{-1}\). Thus for all \((\omega,b)\in S_{-}\) and \(x\in S^{d}\), we have \(\operatorname{sgn}\left(\omega\cdot x+b\right)=\operatorname{sgn}\left(\omega \cdot\pi_{L}(x)+b\right)\), and the argument following (3.23) implies that the difference in (3.75) vanishes.

Next, we expand each term in the sum in (3.74) using (3.64) with \(l=L\) to get (using again the identity (3.12))

\[\sigma_{k}^{(m)}(x;\omega,b)=\sum_{q=0}^{k-m}\frac{1}{q!}\sum_{j=1}^{L}\left\langle \phi_{x,j,j}^{m+q}(\omega,b),(x-x_{L})^{\otimes q}\right\rangle+\sum_{q=0}^{k- m}\frac{1}{q!}\sum_{\ell^{\prime}=-1}^{k-m-q}\sum_{j=1}^{L-1}\left\langle\phi_{x,j,j}^{m+q+\ell^{\prime}}(\omega,b),\Gamma_{\ell^{\prime},j}^{m+q,L}\otimes(x -x_{L})^{\otimes q}\right\rangle. \tag{3.77}\]

Rewriting this, we get

\[\sigma_{k}^{(m)}(x;\omega,b)=\sum_{j=1}^{L}\phi_{x,j,j}^{m}(\omega,b)+\sum_{i= 1}^{k-m}\sum_{j=1}^{L}\left\langle\phi_{x,j,j}^{m+i}(\omega,b),\Gamma_{i,j}^{m }(x)\right\rangle, \tag{3.78}\]

where the tensors \(\Gamma_{i,j}^{m}(x)\) are given by

\[\Gamma_{i,j}^{m}(x)=\frac{1}{i!}(x-x_{L})^{\otimes i}+\sum_{q=0}^{i-1}\Gamma_{ i-q,j}^{m+q,L}\otimes(x-x_{L})^{\otimes q}. \tag{3.79}\]

Finally, we bound the norm \(\|\Gamma_{i,j}^{m}(x)\|\). Utilizing that \(|x-x_{L}|\leq C2^{-L}\) and the bound (3.65) we get

\[\|\Gamma_{i,j}^{m}(x)\|\leq\frac{2^{-Li}}{i!}+C\sum_{q=0}^{i-1}2^{-(i-q)j}2^{- Liq}\leq C2^{-ij}, \tag{3.80}\]

for a constant \(C(d,k)\), since \(j\leq L\) and \(0\leq i\leq k\). Upon relabelling \(j\) to \(l\) this is exactly Lemma 5.
## 4 Acknowledgements

We would like to thank Ron DeVore, Rob Nowak, Jinchao Xu, and Rahul Parhi for helpful discussions. This work was supported by the National Science Foundation (DMS-2111387 and CCF-2205004).
