Target-independent ReLU rate on the unit Sobolev ball

Choose an integer $N\ge 2$ with $C(d,n)N^{-n}\le \epsilon \mathrm{/}2$ and form $g_N$ from [F1]. Then $N\le C^{\mathrm{\prime }}(d,n){\epsilon }^{-1\mathrm{/}n}$, so the number of grid centers is $(N+1{)}^d=O_{d,n}({\epsilon }^{-d\mathrm{/}n})$.

For each center $a_m$, write its Taylor polynomial as a finite sum of monomials in the scaled variables $z_i=N(x_i-a_{m,i})$, multiplied by coefficients $D^{\alpha }f(a_m)N^{-\mathrm{\mid }\alpha \mathrm{\mid }}\mathrm{/}\alpha !$. On the support of ${\varphi }_m$, $\mathrm{\mid }{z}_i\mathrm{\mid }\le 1$, and all coefficients are bounded by a constant depending only on $d,n$. The hat ${\varphi }_m$ is the product of $d$ one-dimensional ReLU hats, since $\mathrm{\mid }z\mathrm{\mid }=\rho (z)+\rho (-z)$ and $u_{+}=\rho (u)$. There are only a number depending on $d,n$ of products and summands. Choose the error of each product operation to be $\eta \mathrm{/}C(d,n)$; inductively, multiplying by a factor of magnitude at most $1$ adds at most that error to the previous product error, and summing the finitely many terms multiplies it by at most another $C(d,n)$. On the hat support, all intermediate inputs stay in fixed bounded intervals depending only on $d,n$, so the bounded-domain error guarantee in [F2] applies there and the monomial sum followed by multiplication by the hat has term error at most $\eta$. Off the hat support, the final product is exactly zero: although the error guarantee is only used on the bounded square, the explicit product formula in [F2] defines a network globally, and the axis cancellation proved there holds for every value of the other input. Thus the local error is zero there. The resulting subnetwork has $O_{d,n}(1+\log (1\mathrm{/}\eta ))$ weights, units, and depth.

At any $x$, at most $2^d$ of the exact hats are nonzero by [F1], and the constructed approximate term is zero outside the same support. Thus summing all local subnetworks gives a network ${\mathrm{\Phi }}_f$ with $\mathrm{\parallel }{g}_N-{\mathrm{\Phi }}_f{\mathrm{\parallel }}_{\mathrm{\infty }}\le 2^d\eta$. Choose $\eta =\epsilon \mathrm{/}{2}^{d+1}$. Then the triangle inequality and step 1.1 give $\mathrm{\parallel }f-{\mathrm{\Phi }}_f{\mathrm{\parallel }}_{\mathrm{\infty }}\le \epsilon$.

The local polynomial degree and number of terms depend only on $d,n$, while the grid size depends only on $N$. All local subnetworks have depth $O_{d,n}(1+\log (1\mathrm{/}\eta ))$ and size of the same order; they run in parallel and their outputs are summed affinely. Hence the total depth is $O_{d,n}(1+\log (1\mathrm{/}\epsilon ))$ and the total weights and units are $O_{d,n}(N^d(1+\log (1\mathrm{/}\epsilon )))=O_{d,n}({\epsilon }^{-d\mathrm{/}n}(1+\log (1\mathrm{/}\epsilon )))$. The edge pattern depends on $N,d,n,\epsilon$ but not on $f$; only Taylor coefficients and output weights depend on $f$.