Approximation lower bounds under distinct selection assumptions

By [F2], the hypotheses of clause (i) imply $\epsilon \ge c_{d,n}(W+1{)}^{-n\mathrm{/}d}$. Since $W\ge 1$, we have $W+1\le 2W$, hence $W\ge \frac{1}{2}{c}_{d,n}^{d\mathrm{/}n}{\epsilon }^{-d\mathrm{/}n}$. The decoder needs no continuity; exactly the selector topology in the statement is used.

For clause (ii), write $p(t)=(4t(1-t){)}^{n+1}$ on $[0,1]$, extended by zero, and $\psi (x)={\prod }_{r=1}^{d}p(x_r)$. The polynomial has endpoint zeros of order $n+1$, so its zero extension is $C^n$. Put $B={\max }_{\mathrm{\mid }\alpha \mathrm{\mid }\le n}\mathrm{\parallel }{D}^{\alpha }\psi {\mathrm{\parallel }}_{\mathrm{\infty }}\ge 1$. Partition the cube into $K^d$ cubes of side $1\mathrm{/}K$, with lower vertices $v_j$, and define ${\varphi }_j(x)=B^{-1}{K}^{-n}\psi (K(x-v_j))$. All derivatives through order $n$ vanish at support boundaries, so the weak derivatives of these finite sums are their classical derivatives, as follows by integration by parts with zero boundary terms. Disjoint support interiors imply that every $f_{\sigma }={\sum }_{j=1}^{K^d}{\sigma }_j{\varphi }_j$, ${\sigma }_j\in \{-1,1\}$, belongs to $F_{d,n}$, since $\mathrm{\parallel }{D}^{\alpha }{f}_{\sigma }{\mathrm{\parallel }}_{\mathrm{\infty }}\le K^{\mathrm{\mid }\alpha \mathrm{\mid }-n}\le 1$ for $\mathrm{\mid }\alpha \mathrm{\mid }\le n$. At the center $x_j$ of cube $j$, $f_{\sigma }(x_j)={\sigma }_j{B}^{-1}{K}^{-n}$.

For clause (iii), nonlinearity of $f$ implies that its Hessian is nonzero at an interior point; otherwise all first derivatives are constant on the connected cube and $f$ is affine. A symmetric nonzero Hessian has a direction with nonzero second directional derivative. By continuity choose a short interior segment and parameterize it by $t\in [0,1]$, so $g(t)=f(a+tv)$ has either $g^{\mathrm{\prime }\mathrm{\prime }}\ge c_0>0$ throughout or $g^{\mathrm{\prime }\mathrm{\prime }}\le -c_0<0$ throughout. The approximating network restricts to a scalar-input network of at most the same depth and unit count.

For sufficiently small $\epsilon >0$, choose $K=\lfloor (1\mathrm{/}(4B\epsilon ){)}^{1\mathrm{/}n}\rfloor \ge \frac{1}{2}(1\mathrm{/}(4B\epsilon ){)}^{1\mathrm{/}n}$. Then the center amplitude $B^{-1}{K}^{-n}$ is at least $4\epsilon$. Every approximant to $f_{\sigma }$ within $\epsilon$ has positive output at centers with ${\sigma }_j=1$ and negative output at centers with ${\sigma }_j=-1$. Thus the threshold classifiers from the one fixed architecture shatter these $K^d\ge c_{d,n}{\epsilon }^{-d\mathrm{/}n}$ centers.

Combining step 2.1 with the first bound in [F3] gives $c_{d,n}{\epsilon }^{-d\mathrm{/}n}\le C{W}^2$, hence $W\ge c{\epsilon }^{-d\mathrm{/}(2n)}$. Shrinking the constant covers the remaining non-small accuracies, because any scalar-output architecture has $W\ge 1$.

If $L\le c_1(\log (1\mathrm{/}\epsilon ){)}^p$, the second bound in [F3] gives $c_{d,n}{\epsilon }^{-d\mathrm{/}n}\le C{c}_1^{2}W(\log (1\mathrm{/}\epsilon ){)}^{2p}\log (2W)$. For sufficiently small $\epsilon$, if $W\ge {\epsilon }^{-d\mathrm{/}n}$ the desired conclusion follows directly since $\log (1\mathrm{/}\epsilon )\ge 1$. Otherwise $\log (2W)\le \log 2+(d\mathrm{/}n)\log (1\mathrm{/}\epsilon )\le C_{d,n}\log (1\mathrm{/}\epsilon )$, and rearrangement gives $W\ge c_2{\epsilon }^{-d\mathrm{/}n}(\log (1\mathrm{/}\epsilon ){)}^{-2p-1}$. No assumption on continuity of the targetwise weight choices was made in either shattering argument.

Write $H=L-2$ and let $U$ be its hidden unit count. Discard units with no path to the output and absorb input-independent units into their downstream biases; this preserves the restricted function and does not increase the remaining hidden unit count. Partition the remaining hidden units by topological rank, where rank is the greatest number of hidden units on an input-to-that-unit path. Every rank is at most $H$, and every predecessor hidden unit has smaller rank. Let $n_{\mathrm{\ell }}$ count rank $\mathrm{\ell }$, setting $n_{\mathrm{\ell }}=0$ for unused ranks; these are counts in a partition, not inserted computation layers. Maintain a common affine partition for the input and all earlier unit outputs, retaining those outputs when the next rank is processed. Every preactivation at that rank is affine on each existing interval, including all skip-edge terms, so its at most $n_{\mathrm{\ell }}$ zeros split that interval into at most $n_{\mathrm{\ell }}+1$ pieces. Thus the interval count in [F1] applies to this rank partition, and ${\sum }_{\mathrm{\ell }}{n}_{\mathrm{\ell }}\le U$. By AM–GM, the restricted network has at most $M\le {\prod }_{\mathrm{\ell }=1}^H(n_{\mathrm{\ell }}+1)\le (1+U\mathrm{/}H{)}^H$ affine intervals. One has length $h\ge 1\mathrm{/}M$. On this interval the network output $r$ is affine. If $g^{\mathrm{\prime }\mathrm{\prime }}\ge c_0$, midpoint convexity applied to $g(t)-c_0{t}^2\mathrm{/}2$ gives $g(a)+g(b)-2g((a+b)\mathrm{/}2)\ge c_0{h}^2\mathrm{/}4$; in the other case apply this to $-g$. The affine second difference of $r$ is zero; the three uniform errors bound the absolute second difference of $g$ by $4\epsilon$. Thus $\epsilon \ge c_0\mathrm{/}(16M^2)$. Rearranging gives $U\ge c(f,L){\epsilon }^{-1\mathrm{/}(2H)}$ for small $\epsilon$. Each hidden unit has a counted bias parameter, so the number of weights is at least $U$, proving clause (iii). AC and its countable-choice consequence are inherited through the stated Sobolev representative and width suppliers; the finite sign and segment constructions require no additional choice.