New Approximation Results and Optimal Estimation for Fully Connected Deep Neural Networks

abstractfarrell2021deep establish non-asymptotic high-probability bounds for general deep feedforward neural network (with rectified linear unit activation function) estimators, with farrell2021deep achieving a suboptimal convergence rate for fully connected feedforward networks. The authors suggest that improved approximation of fully connected networks could yield sharper versions of farrell2021deep without altering the theoretical framework. By deriving approximation bounds specifically for a narrower fully connected deep neural network, this note demonstrates that farrell2021deep can be improved to achieve an optimal rate (up to a logarithmic factor). Furthermore, this note briefly shows that deep neural network estimators can mitigate the curse of dimensionality for functions with compositional structure and functions defined on manifolds.

assumptionFor constants \(c_1, c_2, C_\ell \in \mathbb{R}_+\), and for any \(f \in \mathcal{F} \cup \mathcal{F}_{\mathrm{DNN}}\) and \(g \in \mathcal{F} \cup \mathcal{F}_{\mathrm{DNN}}\), assume the loss function satisfies \begin{equation*} \abs{\ell(f,\mathbf{z})-\ell(g,\mathbf{z})}\leq C_l \abs{f(x)-g(x)}. \end{equation*} For \(f_* \in \mathcal{F}\) and for any \(h \in \mathcal{F}_{\mathrm{DNN}}\), assume the curvature condition \begin{equation*} c_1 \mathbb{E}[(h-f_*)^2]\leq \mathbb{E}[\ell(h,Z)] - \mathbb{E}[\ell(f_*, Z)]\leq c_2 \mathbb{E}[(h-f_*)^2]. \end{equation*}

assumptionAssume that $\mathbf{z}_i=(y_i,\mathbf{x}_i')', 1\leq i\leq n$ are i.i.d. copies of $\mathbf{Z}=(Y,\mathbf{X})\in \mathcal{Y}\times[-1,1]^d$, where $\mathbf{X}$ is continuously distributed. For an absolute constant $M>0$, assume $\norm{f_*}_\infty \leq M$ and $\mathcal{Y}\subset [-M,M]$.

theorem[General Feedforward Architecture] Suppose $f_*$ lies in a class $\mathcal{F}$. Suppose Assumption (ref) holds and define \begin{equation*} \epsilon_{\mathrm{DNN}}\coloneqq \sup_{\Tilde{f}\in\mathcal{F}}\inf_{\substack{f \in \mathcal{F}_{{\mathrm{DNN}}}\\ \norm{f}_\infty\leq 2M}} \norm{f-\Tilde{f}}_\infty. \end{equation*} Let $\hat{f}_{\mathrm{DNN}}$ be the deep ReLU network estimator defined by equation ((ref)), for a loss function obeying Assumption (ref). Then with probability at least $1 - e^{-\gamma}$, for $n$ large enough, \begin{enumerate} • $\|\hat{f}_{\mathrm{DNN}} - f_*\|_{L_2(X)}^2 \leq C\left(\frac{WL \log W}{n} \log n + \frac{\log \log n + \gamma}{n} + \epsilon_{\mathrm{DNN}}^2\right)$ • $E_n[(\hat{f}_{\mathrm{DNN}} - f_*)^2] \leq C\left(\frac{WL \log W}{n} \log n + \frac{\log \log n + \gamma}{n} + \epsilon_{\mathrm{DNN}}^2\right)$ \end{enumerate} for a constant $C > 0$ independent of $n$, which may depend on $d, M$, and other fixed constants.

assumptionAssume $f_*$ lies in $\mathcal{F}$ which is the Sobolev ball $\mathcal{W}^{\beta,\infty}([-1,1]^d)$, with smoothness $\beta \in \mathbb{N}_+$, \begin{equation*} \mathcal{W}^{\beta,\infty}([-1,1]^d)\coloneqq \{f: \max_{{\boldsymbol\alpha},\abs{\boldsymbol\alpha}\leq \beta}{\operatorname*{ess\,sup}_{\mathbf{x}\in [-1,1]^d}} \abs{D^{\boldsymbol\alpha} f(\mathbf{x})}\leq 1\}, \end{equation*} where $\boldsymbol{\alpha} = (\alpha_1,...,\alpha_d)$, $\abs{\boldsymbol\alpha}=\alpha_1+...+\alpha_d$ and $D^{\boldsymbol\alpha}f$ is the weak derivative.\footnote{Assumption (ref) requires $f_*\in[-1,1]$, which is not compatible with Assumption (ref), where $f_*\in [-M,M]$. However, since $[-M,M]$ is bounded, the results extend directly. To remain consistent with farrell2021deep, we follow their assumptions.}

theorem[Multilayer Perceptron] Suppose Assumptions (ref) and (ref) hold. Let $\hat{f}_{\mathrm{MLP}}$ be the MLP ReLU network estimator defined by equation \null((ref))\null, restricted to $\mathcal{F}_{\mathrm{MLP}}$, for a loss function obeying Assumption (ref), with width $H\asymp n^{\frac{d}{2(\beta+d)}}\log^{2} n$ and depth $L\asymp \log n$. Then with probability at least $1-\exp(-n^{\frac{d}{\beta+d}}\log^{8} n )$, for n large enough, \begin{enumerate} • $\norm{\hat{f}_{\mathrm{MLP}}-f_*}^2_{L_2(\textbf{X})}\leq C\cdot \{n^{-\frac{\beta}{\beta+d}}\log^{8} n +\frac{\log\log n}{n}\}$ and • $\mathbb{E}_n[(\hat{f}_{\mathrm{MLP}}-f_*)^2]\leq C\cdot \{n^{-\frac{\beta}{\beta+d}}\log^{8} n +\frac{\log\log n}{n}\},$ \end{enumerate} for a constant $C>0$ independent of $n$, which may depend on $d, \beta, M$, and other fixed constants.

theoremFor any $\beta,d\in \mathbb{N_+}$ and $\epsilon_{\mathrm{DNN}}\in(0,1)$, \begin{enumerate} • there is a feedforward ReLU network architecture that it can approximate any function in $\mathcal{W}^{\beta,\infty}([-1,1]^d)$ with approximation error less than $\epsilon_{\mathrm{DNN}}$, with depth $L \leq c(ln(1/\epsilon_{\mathrm{DNN}})+1)$, and width $H\leq c\epsilon_{\mathrm{DNN}}^{-\frac{d}{2\beta}}$. • This approximation network can be converted into a fully connected network without significantly change $H,L$ and $W$. The only change is the constant $c$. Using the fact that $W\leq C\cdot H^2L$ for fully connected neural networks, the total number of parameters satisfies $W_{\mathrm{MLP}}\leq c\epsilon_{\mathrm{DNN}}^{-\frac{d}{\beta}}(\ln(1/\epsilon_{\mathrm{DNN}})+1)$, with some constant $c=c(d,\beta)$. \end{enumerate}

remarkIn yarotsky2017error, the neural network was constructed via a linear combination of \( \mathcal{O}(\epsilon_{\mathrm{DNN}}^{-\frac{d}{\beta}}) \) subnetworks, requiring a width of \( \mathcal{O}(\epsilon_{\mathrm{DNN}}^{-\frac{d}{\beta}}) \). A direct fully connected implementation (where \( W \leq C \cdot H^2 L \)) would result in the number of weights at least \( \mathcal{O}(\epsilon_{\mathrm{DNN}}^{-\frac{2d}{\beta}}L) \). This is the first reason why the rate established in Theorem (ref) is suboptimal. The first point solves this by explicitly constructing a narrower network with equivalent performance.

remarkA narrower construction alone is not sufficient to solve the problem. Specifically, farrell2021deep says $H_{\mathrm{MLP}}\asymp WL$, where $H_{\mathrm{MLP}}$ is the width of the converted MLP and $W,L$ are the total number of weights and depth of the original approximation network.\footnote{In fact, farrell2021deep can be strengthened so that the width of the resulting fully connected network is bounded above by \( HL \), where \( H \) and \( L \) are the width and depth of the original architecture. However, this refinement still causes an undesirable expansion of \( H \) by an additional factor of \( L \).} Since we maintain the same number of weights as in yarotsky2017error, even with our narrower construction, applying farrell2021deep would increase the width $H_{\mathrm{MLP}}\asymp WL$, effectively squaring it. This is the second reason that Theorem (ref) is suboptimal.

theorem[Optimal Multilayer Perceptron] Suppose Assumtpions (ref) and (ref) hold. Let $\hat{f}_{\mathrm{MLP}}$ be the MLP ReLU network estimator defined by equation \null((ref))\null, for a loss function obeying Assumption (ref), with width $H\asymp n^{\frac{d}{4\beta+2d}}$ and depth $L\asymp \log n$. Then with probability at least $1-\exp(-n^{\frac{d}{2\beta+d}}\log^{4} n )$, for n large enough,\footnote{The logarithmic term could potentially be improved, but for simplicity we maintain the same log term as in farrell2021deep.} \begin{enumerate} • $\norm{\hat{f}_{\mathrm{MLP}}-f_*}^2_{L_2(\textbf{X})}\leq C\cdot \{n^{-\frac{2\beta}{2\beta+d}}\log^{4} n +\frac{\log\log n}{n}\}$ and • $\mathbb{E}_n[(\hat{f}_{\mathrm{MLP}}-f_*)^2]\leq C\cdot \{n^{-\frac{2\beta}{2\beta+d}}\log^{4} n +\frac{\log\log n}{n}\},$ \end{enumerate} for a constant $C>0$ independent of $n$, which may depend on $d, \beta, M$, and other fixed constants.

assumptionAssume $f_*\in \mathcal{W}^{\beta,\infty}_{d_*,T}([-1,1]^d)$.

exampleFor some $d_* \in \{1,..,d\}$, denote $\mathbf{x}_I=(x_{i_1},...,x_{i_{d_*}})'$, where $I=\{i_1,...,i_{d_*}\}$ and $1\leq i_1\leq \cdots\leq i_{d_*}\leq d$. And assume the structure \begin{equation*} f_0(\mathbf{x})=\sum_{I\subseteq \{1,...,d\},\abs{I}=d_*} f_I(\mathbf{x}_I), \end{equation*} where each function $f_I(\cdot)$ satisfies equation ((ref)). Denote the set of indices \( I \) as \(\mathcal{I}\), and let its cardinality be \( k \). Order the indices as \((I_1, \ldots, I_k)\). According to the definition in equation ((ref)), we have \begin{equation*} F_{j+d} = f_{I_j} \quad for j = 1, \ldots, k. \end{equation*} Furthermore, define \begin{equation*} \begin{split} F_{d+k+1}& = f_{I_1} + f_{I_2},\\ F_{d+k+j}& = F_{d+k+1} + f_{I_{j+1}}, \quad for j = 2, \ldots, k-1,\\ F_{d+2k-1}& = f_0(\mathbf{x}). \end{split} \end{equation*} Thus, we conclude that $f_0 \in \mathcal{W}^{\beta,\infty}_{d_*, d+2k-1}([-1,1]^d)$.

theoremSuppose Assumptions (ref) and (ref) hold. Let $\hat{f}_{\mathrm{MLP}}$ be the MLP ReLU network estimator defined by equation \null((ref))\null, restricted to $\mathcal{F}_{\mathrm{MLP}}$, for a loss function obeying Assumption (ref), with width $H\asymp n^{\frac{d_*}{2\beta+d_*}}\log^{2} n$ and depth $L\asymp \log n$. Then with probability at least $1-\exp(-n^{\frac{d_*}{2\beta+d_*}}\log^{4} n )$, for n large enough, \begin{enumerate} • $\norm{\hat{f}_{\mathrm{MLP}}-f_*}^2_{L_2(\textbf{X})}\leq C\cdot \{n^{-\frac{2\beta}{2\beta+d_*}}\log^{4} n +\frac{\log\log n}{n}\}$ and • $\mathbb{E}_n[(\hat{f}_{\mathrm{MLP}}-f_*)^2]\leq C\cdot \{n^{-\frac{2\beta}{2\beta+d_*}}\log^{4} n +\frac{\log\log n}{n}\},$ \end{enumerate} for a constant $C>0$ independent of n, which may depend on $d_*,M,\beta,T$, and other fixed constants, but it doesn't depend on $d$.

definition[Compact Smooth Manifold] For $k,l\in \mathbb{N}_+$, let $U\subset \mathbb{R}^k$ and $V\subset \mathbb{R}^k$. A mapping $f:U\rightarrow V$ is called smooth if for each $\mathbf{x}\in U$ there exists an open set $U'\subset \mathbb{R}^k$ such that $\mathbf{x}\in U'$. And there exists a smooth mapping $F: U'\rightarrow \mathbb{R}^l$ such that $\forall \mathbf{x}^1\in U\cap U'$, $F(\mathbf{x}^1)=f(\mathbf{x}^1)$. A map $f:U\rightarrow V$ is called a diffeomorphism if $f$ maps $U$ homeomorphically onto $V$ and if both $f$ and its inverse $f^{-1}$ are smooth. For $d,m\in \mathbb{N}_+$, a compact subset $\mathcal{M} \subset \mathbb{R}^d$ is called a compact smooth manifold of dimension $m$ if for every $\mathbf{x} \in \mathcal{M}$, there exists an open set $W\subset \mathbb{R}^k$ such that $\mathbf{x}\in W$ and $W\cap M$ is diffeomorphic to an open subset $U\subset\mathbb{R}^m$.

assumptionWe further assume that there exists a compact, smooth $ m$-dimensional manifold $\mathcal{M}\subset [-1,1]^d$ such that $\mathbf{X}\in \mathcal{M}$. And we assume $f_*$ that lies in the Sobolev ball $\mathcal{W}^{\beta,\infty}(\mathcal{M})$, with smoothness $\beta \in \mathbb{N}_+$, \begin{equation*} \mathcal{W}^{\beta,\infty}(\mathcal{M})\coloneqq \{f: \max_{{\boldsymbol\alpha},\abs{\boldsymbol\alpha}\leq \beta}{\operatorname*{ess\,sup}_{\mathbf{x}\in \mathcal{M}}} \abs{D^{\boldsymbol\alpha} f(\mathbf{x})}\leq 1\}, \end{equation*} where $\boldsymbol{\alpha} = (\alpha_1,...,\alpha_d)$, $\abs{\boldsymbol\alpha}=\alpha_1+...+\alpha_d$ and $D^{\boldsymbol\alpha}f$ is the weak derivative.

theoremSuppose Assumptions (ref) and (ref) hold. Let $\hat{f}_{\mathrm{MLP}}$ be the MLP ReLU network estimator defined by equation \null((ref))\null, restricted to $\mathcal{F}_{\mathrm{MLP}}$, for a loss function obeying Assumption (ref), with width $H\asymp n^{\frac{m}{2\beta+m}}\log^{2} n$ and depth $L\asymp \log n$. Then with probability at least $1-\exp(-n^{\frac{m}{2\beta+m}}\log^{4} n )$, for n large enough, \begin{enumerate} • $\norm{\hat{f}_{\mathrm{MLP}}-f_*}^2_{L_2(\textbf{X})}\leq C\cdot \{n^{-\frac{2\beta}{2\beta+m}}\log^{4} n +\frac{\log\log n}{n}\}$ and • $\mathbb{E}_n[(\hat{f}_{\mathrm{MLP}}-f_*)^2]\leq C\cdot \{n^{-\frac{2\beta}{2\beta+m}}\log^{4} n +\frac{\log\log n}{n}\},$ \end{enumerate} for a constant $C>0$ independent of n, which may depend on $\mathcal{M}, \beta,m$, and other fixed constants.

appendix\section{Lemma} \subsection{Lemmas used in Appendix (ref)} We will first introduce the lemma from yarotsky2017error, which combines results from liu2022optimal. We then introduce a lemma used to convert approximation neural networks into fully connected networks. These results are used to show the main results in Appendix (ref). The following lemma is based on yarotsky2017error, while its final part follows from liu2022optimal. \begin{lemma} The function $f(x)=x^2$ on the segment $[0,1]$ can be approximated with any error $\delta>0$ by a ReLU network $\Tilde{f}_{sq,\delta}$ such that $\Tilde{f}_{\mathrm{sq},\delta}(0)=0$ and $\abs{\Tilde{f}_{\mathrm{sq},\delta}-x^2}< \delta$ for $x\in [-1,1]$. Given $Q>0$, and $\epsilon \in (0,1)$, there is a ReLU network $\eta$ with two input units that implements a function $\Tilde{\times} : \mathbb{R}^2 \rightarrow \mathbb{R}$. Assume without loss of generality that $Q\geq 1$ and set \begin{equation*} \Tilde{\times}(x,y)=\frac{Q^2}{8} (\Tilde{f}_{\mathrm{sq},\delta}(\frac{\abs{x+y}}{2Q})-\Tilde{f}_{\mathrm{sq},\delta}(\frac{\abs{x}}{2Q})-\Tilde{f}_{\mathrm{sq},\delta}(\frac{\abs{y}}{2Q})), \end{equation*} where $\delta=\frac{8\epsilon}{3Q^2}$. Then, the following hold: \begin{enumerate} • for any inputs $x,y$, if $\abs{x}\leq Q$ and $\abs{y}\leq Q$, then $\abs{\Tilde{\times}(x,y)-xy}\leq \epsilon$; • $\Tilde{\times}(x,0)=\Tilde{\times}(0,y)=0$; • the depth and the number of weights and hidden units in $\eta$ are not greater than $c_1 \ln(1/\epsilon)+c_2$ with an universal constant $c_1$ and a constant $c_2 = c_2(Q)$, • the neural network can be made fully connected with a width of at most 12. \end{enumerate} \end{lemma} The next lemma enables us to convert the approximating function used in Proof (ref) into fully connected architectures. \begin{lemma} With $\Tilde{\times}(\cdot)$ defined in Lemma (ref), and a fully connected feedforward ReLU neural network is denoted by $f_\mathit{MLP}^m$ or $f_\mathit{MLP}^\alpha$, indicating dependence on the parameter $m$ or $\alpha$, respectively. We assume that, for parameters $m,\alpha\in \mathbb{R}$, $m$ takes values in a finite set $S_m$ and $\alpha$ takes values in a finite set $S_\alpha$. Denote $N_{\mathrm{max}}\coloneqq \max(\abs{S_m},\abs{S_\alpha})$. Suppose each of the neural networks has a depth at most $L$, a width at most $H$, and $a_{m,\alpha} \in \mathbb{R}$. Then, we can convert the following neural networks $\sum_{\alpha\in S_\alpha}\Tilde{\times}(\sum_{m\in S_m} a_{m,\alpha}f_\mathit{MLP}^m,f_\mathit{MLP}^\alpha)$ into fully connected architectures with depth at most $L+1+c_1 \ln(1/\epsilon)+c_2$ and width at most $\max(12,2H) N_{\mathrm{max}}$.\footnote{For simplicity, we assume the functions satisfies the definition of $\Tilde{\times}(\cdot)$.} \begin{remark} A key observation for our proof is that the input can always be passed through a ReLU activation function without altering its value, which is not possible with other activation functions (e.g., the sigmoid function). \end{remark} \begin{proof} For each $f_\mathrm{MLP}^m, m\in S_m$, if the depth is less than $L$, we can use the fact that \begin{equation*} x = \sigma_R(x)-\sigma_R(-x) \end{equation*} to extend it so that every $f_\mathrm{MLP}^m$ has the same depth $L$. Since each $f_\mathrm{MLP}^m$ is fully connected and has the same depth, combining them into a single fully connected network is achieved by simply connecting each node to the nodes in the adjacent layers. Thus, each value of $f_\mathrm{MLP}^m$ for $m\in S_m$ can be represented by the fully connected neural network with depth at most $L$ and width at most $2HN_\mathrm{max}$ with $\abs{S_m}$ output units. The same arguments apply to $f_\mathrm{MLP}^\alpha$. For each $\alpha$, the only difference of $\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m$ is $a_{m,\alpha}$. They are merely linear combinations of $f_\mathrm{MLP}^m$ for $m\in S_m$. Therefore, with one more layer, we can use the same fully connected neural network but with at most $N_\mathrm{max}$ output units to represent each value of $\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m$. Each output unit corresponds to a different value of $\alpha$. That is, \begin{equation*} \sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m = \sigma_R(\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m)-\sigma_R(-\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m) \end{equation*} and the width needed for this operation is at most $2N_\mathrm{max}$. Thus, with a single fully connected neural network, we can represent each value of $\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m$ and $f_\mathrm{MLP}^\alpha$ for each $\alpha\in S_\alpha$. The neural network has at most $2N_\mathrm{max}$ output units, depth at most $L+1$, and width at most $2HN_\mathrm{max}$. Each output unit corresponds either $\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m$ or $f_\mathrm{MLP}^\alpha$ for each $\alpha\in S_\alpha$. For each $\alpha\in S_\alpha$, each $\sum_{m\in S_m} a_{m,\alpha}f_\mathrm{MLP}^m$ corresponds to a single $f_\mathrm{MLP}^\alpha$. Thus, by Lemma (ref), we need at most $L+1+c_1 \ln(1/\epsilon)+c_2$ more layers, whose width are at most $\max(12,2H)N_\mathrm{max}$, to represent $\sum_{\alpha\in S_\alpha}\Tilde{\times}(\sum_{m\in S_ m} a_{m, \alpha}f_\mathrm{MLP}^m,f_\mathrm{MLP}^\alpha)$. \end{proof} \end{lemma} \subsection{Lemmas used in Section (ref)} The lemmas in this subsection are adapted from petersen2024mathematical, with the condition on the number of weights replaced by a condition on width. Based on the proofs in petersen2024mathematical, one can directly establish the following two lemmas. The only change is that, in determining the width, we apply our Theorem (ref) rather than yarotsky2017error, which is used there to determine the network size. For brevity, we state the two lemmas without proof. The following lemma is modified from petersen2024mathematical and used to show Theorem (ref). \begin{lemma} For any $\beta, d,d_*,T \in \mathbb{N_+}$ and $\epsilon\in (0,1)$, there is a fully connected ReLU network architecture that can represent any function in $\mathcal{W}^{\beta,\infty}_{d_*,T}([-1,1]^d)$, with the depth $L \leq c(ln(1/\epsilon)+1)$, the width $H\leq c\epsilon^{-\frac{d_*}{2\beta}}$. Moreover, using the fact that $W\leq C\cdot H^2L$, the weights $W\leq c\epsilon^{-\frac{d_*}{\beta}}(\ln(1/\epsilon)+1)$, with some constant $c=c(d_*,T,\beta)$. \end{lemma} The next lemma is modified from petersen2024mathematical, and used to show Theorem (ref). \begin{lemma} For any $\beta, d,m \in \mathbb{N_+}$ and $\epsilon\in (0,1)$, suppose $\mathcal{M}$ is a smooth, compact $m$ dimensional manifold s.t. $\mathcal{M}\subseteq [-1,1]^d$. Then, there is a fully connected ReLU network architecture that can represent any function in $\mathcal{W}^{\beta,\infty}(\mathcal{M})$, with the depth $L \leq c(ln(1/\epsilon)+1)$, the width $H\leq c\epsilon^{-\frac{m}{2\beta}}$. Moreover, using the fact that $W\leq C\cdot H^2L$, the weights $W\leq c\epsilon^{-\frac{m}{\beta}}(\ln(1/\epsilon)+1)$, with some constant $c=c(d,m,\mathcal{M},\beta)$. \end{lemma} \section{Proof} For completeness, we provide a self-contained presentation below, with our modifications clearly highlighted. Appendix (ref) reproduces yarotsky2017error, while Appendix (ref) presents our modified proof based on Appendix (ref). We also include the proof of yarotsky2017error so that readers can clearly see the connections and differences with our results. \subsection{yarotsky2017error} The following lemma is yarotsky2017error, while Theorem (ref) is a modified version of it. \begin{lemma} For any $\beta,d\in \mathbb{N_+}$ and $\epsilon\in(0,1)$, there is a ReLU network architecture that it can approximate any function in $\mathcal{W}^{\beta,\infty}([-1,1]^d)$ with error $\epsilon$, with the depth $L \leq c(ln(1/\epsilon)+1)$, the number of weights $W\leq c\epsilon^{-\frac{d}{\beta}}ln(1/\epsilon+1)$, with some constant $c=c(d,\beta)$. \end{lemma} \begin{proof} \begin{quotation} Given a $N\in \mathbb{N}_+$. Consider a partition of unity: \begin{equation*} \sum_\mathbf{m} \phi_\mathbf{m}(\mathbf{x})\equiv 1, \quad \mathbf{x}\in [-1,1]^d. \end{equation*} which is constructed by a grid of $(2N+1)^d$ function $\phi_\mathbf{m}$ on the domain $[-1,1]^d$ Here $\mathbf{m}=(m_1,...,m_d), m_i\in \{-N,...-1,0,1,...,N\}, i=1,...,d$, and define the function the function $\phi_\mathbf{m}$ as \begin{equation*} \phi_\mathbf{m}(\mathbf{x}) = \prod_{k=1}^d \psi(3N(x_k -\frac{m_k}{N})), \end{equation*} where \begin{equation*} \psi(x)=\begin{cases} 1, & \abs{x}<1,\\ 0, & 2<\abs{x},\\ 2-\abs{x}, & 1\leq \abs{x}\leq 2. \end{cases} \end{equation*} Note that \begin{equation*} \norm{\psi}_\infty=1 \quad and \quad \norm{\phi_\mathbf{m}}_\infty=1, \forall \mathbf{m} \end{equation*} and \begin{equation*} \operatorname{supp} \phi_\mathbf{m} \subset \{\mathbf{x}:\abs{x_k-\frac{m_k}{N}}<\frac{1}{N}, \forall k\}. \end{equation*} For any $\mathbf{m}\in \{-N,...,-1,0,1,...,N\}^d$, consider the degree-($\beta-1$) Taylor polynomial for the function $f$ at $\mathbf{x}=\frac{\mathbf{m}}{N}$: \begin{equation} P_\mathbf{m}(\mathbf{x}) = \sum_{{\boldsymbol{\alpha}}:\abs{\boldsymbol{\alpha}}<\beta}\frac{D^{{\boldsymbol{\alpha}}}f}{{\boldsymbol{\alpha}}!}\bigg|_{\mathbf{x} = \frac{\mathbf{m}}{N}} \left( \mathbf{x} - \frac{\mathbf{m}}{N} \right)^{{\boldsymbol{\alpha}}}, \end{equation} with ${\boldsymbol{\alpha}}!=\prod_{k=1}^d \alpha_k!$ and $(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}} = \prod_{k=1}^d (x_k-\frac{m_k}{N})^{\alpha_k}$. Define an approximation to $f$ by \begin{equation} f_1 = \sum_{\mathbf{m}\in \{-\mathbf{N},...,-1,0,1,...,\mathbf{N}\}} \phi_\mathbf{m} P_\mathbf{m}. \end{equation} Using the Taylor expansion of $f$, the approximation error is bounded by: \begin{equation*} \begin{split} \abs{f(\mathbf{x})-f_1(\mathbf{x})} &\leq \frac{2^d d^\beta}{\beta!}(\frac{1}{N})^\beta. \end{split} \end{equation*} $\forall x\in \mathbb{R}$, a ceiling function maps $x$ to the least integer greater than or equal to $x$, denoted $\ceil{x}$. Choose \begin{equation} N= \ceil{(\frac{\beta!}{2^d d^\beta}\frac{\epsilon}{2})^{-1/\beta}}, \end{equation} then \begin{equation*} \norm{f-f_1}_\infty \leq \frac{\epsilon}{2}. \end{equation*} By equation ((ref)) the coefficients of the polynomials $P_\mathbf{m}$ are uniformly bounded $\forall f \in \mathcal{W}^{\beta,\infty}([-1,1]^d)$: \begin{equation} P_\mathbf{m}(\mathbf{x})=\sum_{{\boldsymbol{\alpha}}: \abs{\mathfrak{\alpha}}<\beta} a_{\mathbf{m},\boldsymbol{\alpha}}(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}, \quad \abs{a_{\mathbf{m},\boldsymbol{\alpha}}}\leq 1. \end{equation} The second step is to construct a network architecture which can approximate any function of the form ((ref)) with uniform error $\frac{\epsilon}{2}$, assuming that $N$ is given by ((ref)) and the polynomials $P_\mathbf{m}$ are of the form ((ref)). Expand $f_1$ as \begin{equation*} f_1(\mathbf{x}) = \sum_{\mathbf{m}\in \{-N,...,-1,0,1,...,N\}^d} \sum_{{\boldsymbol{\alpha}}:\abs{\alpha}<\beta} a_{\mathbf{m},\boldsymbol{\alpha}} \phi_\mathbf{m}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}. \end{equation*} The expansion is a linear combination of $\phi_\mathbf{m}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^\mathbf{n}$, and the total number of such terms is less than $d^\beta \prod_{i=1}^d(2N+1)$. Each of them is a product of at most $d+\beta-1$ piece-wise linear univariate factors: total number of $d$ for $\psi(3Nx_k-3m_k)$ functions and at most $\beta-1$ linear expressions of $x_k-\frac{m_k}{N}$. A neural network can approximate such a product according to Lemma (ref). Choose $Q=d+\beta$ and $\delta$ (to be chosen later), and use $\Tilde{\times}(\cdot)$ (defined in Lemma (ref)) to denote the approximate multiplication and iteratively apply $\Tilde{\times}$ to approximate the product $\phi_\mathbf{m}(\mathbf{x})(\mathbf{x}-\frac{\boldsymbol{m}}{N})^\mathbf{n}$. That is, \begin{equation} \Tilde{f}_{\mathbf{m},\boldsymbol{\alpha}}(\mathbf{x}) =\Tilde{\times}(\psi(3Nx_1-3m_1),\Tilde{\times}(\psi(3Nx_2-3m_2),...,\Tilde{\times}(\psi(3Nx_k-3m_k,...)...)). \end{equation} Since, \begin{equation} \abs{\Tilde{f}_{\mathbf{m},\boldsymbol{\alpha}}(\mathbf{x})-\phi_\mathbf{m}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}}\leq (d+\beta-1)\delta \end{equation} The full approximation is: \begin{equation*} \Tilde{f}=\sum_{\boldsymbol{m}\in \{-N,...,-1,0,1,...,N\}^d}\sum_{\boldsymbol{\alpha}:\abs{\boldsymbol{\alpha}}<\beta}a_{\mathbf{m},\boldsymbol{\alpha}}\Tilde{f}_{\mathbf{m},\boldsymbol{\alpha}}. \end{equation*} There are at most $d^\beta (2N+1)^d$ possible values for $(\mathbf{m},{\boldsymbol{\alpha}})$. The approximation error of $\Tilde{f}$ is: \begin{equation*} \begin{split} \left| \Tilde{f}(\mathbf{x}) - f_1(\mathbf{x}) \right| &\leq 2^d d^\beta (d + \beta-1) \delta. \end{split} \end{equation*} Choose \begin{equation*} \delta = \frac{\epsilon}{2^{d+1}d^\beta (d+\beta-1)}, \end{equation*} then $\norm{\Tilde{f}-f_1}_\infty\leq \frac{\epsilon}{2}$. And $\norm{\Tilde{f}-f}_\infty\leq \epsilon$. \end{quotation} \end{proof} Since a full approximation neural network is a linear combination of fewer than $d^\beta \prod_{i=1}^d (2N+1)$ sub-networks, the resulting network width is $H = \mathcal{O}((2N+1)^d) = \mathcal{O}(\epsilon^{-\frac{d}{\beta}})$. \subsection{Proof of Theorem (ref)} \begin{proof} Based on the proof above, first notice that we can directly represent $\psi(\cdot)$ by a ReLU neural network, \begin{equation*} \psi(x)= \sigma_R(2-\sigma_R(x)-\sigma_R(-x))-\sigma_R(1-\sigma_R(x)-\sigma_R(-x)). \end{equation*} Since $\phi_{\mathbf{m}}(\cdot)$ is a product of $\psi(\cdot)$, we can easily approximate it using Lemma (ref). The fundamental constraint is that $a_{\mathbf{m},\boldsymbol{\alpha}}$ admits at most $d^\beta (2N+1)^d$ distinct values. Under this condition, a narrower network architecture can maintain identical approximation error bounds. This is achieved solely through an appropriate reconstruction of $\Tilde{f}_{\mathbf{m},\boldsymbol{\alpha}}(\mathbf{x})$. Constrained by the bound $W\leq C\cdot H^2L$ for fully connected neural networks, our goal is to construct a neural network with width $\mathcal{O}(2N+1)^{\frac{d}{2}}$. If $d$ is an even number, the modification is straightforward. For odd $d$, however, a more delicate construction is required. The proof is separated into three cases: Case 1: if $d$ is even, we can write: \begin{equation*} \begin{split} &\phi_{\mathbf{m}}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{{\boldsymbol{\alpha}}}\\ =& \prod_{k=1}^d \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}\\ =&\left( \prod_{k=1}^{\frac{d}{2}} \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}\right) \left( \prod_{k=\frac{d}{2}+1}^{d} \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}\right). \end{split} \end{equation*} Denote $\mathbf{m}^1=(m_1,...,m_{\frac{d}{2}}),\mathbf{m}^2 = (m_{\frac{d}{2}+1},...,m_d), {\boldsymbol{\alpha}}^1=(\alpha_1,...,\alpha_{\frac{d}{2}}), {\boldsymbol{\alpha}}^2=(\alpha_{\frac{d}{2}+1},...,\alpha_d)$, $\mathbf{x}^1=(x_1,...,x_{\frac{d}{2}})$, $\mathbf{x}^2=(x_\frac{d}{2},...,x_d)$. We can rewrite $f_1(\mathbf{x})$, so that \begin{align*} f_1(\mathbf{x}) &= \sum_{\mathbf{m}\in \{-N,...,-1,0,1,...,N\}^d} \sum_{{\boldsymbol{\alpha}}:\abs{\alpha}<\beta} a_{\mathbf{m},\boldsymbol{\alpha}} \phi_\mathbf{m}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}\\ &= \sum_{\mathbf{m}^2\in \{-N,...,-1,0,1,...,N\}^{\frac{d}{2}}} \sum_{{\boldsymbol{\alpha}^2}:\abs{\boldsymbol{\alpha}^2}<\beta} \phi_{\mathbf{m}^2}(\mathbf{x}^2)(\mathbf{x}^2-\frac{\mathbf{m}^2}{N})^{\boldsymbol{\alpha}^2}\\ &\times\left(\sum_{\mathbf{m}^1\in \{-N,...,-1,0,1,...,N\}^{\frac{d}{2}}} \sum_{{\boldsymbol{\alpha}^1}:\abs{\boldsymbol{\alpha}^1}<\beta-\abs{\boldsymbol{\alpha}^2}} a_{\mathbf{m},\boldsymbol{\alpha}} \phi_{\mathbf{m}^1}(\mathbf{x}^1)(\mathbf{x}^1-\frac{\mathbf{m}^1}{N})^{\boldsymbol{\alpha}^1}\right). \end{align*} Using the definition in equation ((ref)), we can approximate $ \phi_{\mathbf{m}^1}(\mathbf{x}^1)(\mathbf{x}^1-\frac{\mathbf{m}^1}{N})^{\boldsymbol{\alpha}^1}$ by $\Tilde{f}_{\mathbf{m}^1,{\boldsymbol{\alpha}}^1}$ and $ \phi_{\mathbf{m}^2}(\mathbf{x}^2)(\mathbf{x}^2-\frac{\mathbf{m}^2}{N})^{\boldsymbol{\alpha}^2}$ by $\Tilde{f}_{\mathbf{m}^2,{\boldsymbol{\alpha}}^2}$. From Lemma (ref), $\forall i=1,2, \Tilde{f}_{\mathbf{m}^i,{\boldsymbol{\alpha}}^i}$ can be approximated by a fully connected neural network such that its depth is $\mathcal{O}(\ln(1/\delta)+1)$ and width is $\mathcal{O}(\frac{d}{2})$. Since $(\mathbf{m}^1,{\boldsymbol{\alpha}}^1)$ and $(\mathbf{m}^2,{\boldsymbol{\alpha}}^2)$ both have at most $d^\beta (2N+1)^{\frac{d}{2}}$ possible values, with $2*d^\beta (2N+1)^{\frac{d}{2}}$ output units, depth $\mathcal{O}(\ln(1/\delta)+1)$ and width $\mathcal{O}( (2N+1)^{\frac{d}{2}})$, by Lemma (ref), we can use a (fully connected) neural network to represent all possible values for $\Tilde{f}_{\mathbf{m}^i,{\boldsymbol{\alpha}}^i}, i=1,2$. For any pair of $(\mathbf{m}^2,{\boldsymbol{\alpha}}^2)$, if ${\boldsymbol{\alpha}}^1+\boldsymbol{\alpha}^2>\beta$, we set $a_{\mathbf{m},\boldsymbol{\alpha}}=0$. By equation ((ref)), $\abs{a_{\mathbf{m},\boldsymbol{\alpha}}} \leq 1$, which satisfies the definition of the function $\Tilde{\times}(\cdot)$. Therefore, the full approximation function is redefined as \begin{equation*} \begin{split} \Tilde{f}&=2^{\frac{d}{2}}d^\beta\sum_{\mathbf{m}^2,\boldsymbol{\alpha}^2} \Tilde{\times}(\frac{1}{2^{\frac{d}{2}}d^\beta}\sum_{{\mathbf{m}^1,\boldsymbol{\alpha}^1}}a_{\mathbf{m},\boldsymbol{\alpha}}\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1),\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2)), \end{split} \end{equation*} where $\frac{1}{2^{\frac{d}{2}}d^\beta}$ is to ensure the inputs of $\Tilde{\times}(\cdot)$ satisfies the definition. By equation ((ref)), for $i=1,2$, \begin{equation*} \abs{\Tilde{f}_{\mathbf{m}^i,\boldsymbol{\alpha}^i}(\mathbf{x}^i)-\phi_{\mathbf{m}^i}(\mathbf{x}^i)(\mathbf{x}^i-\frac{\mathbf{m}^i}{N})^{\boldsymbol{\alpha}^i}}\leq (\frac{d}{2}+\abs{\boldsymbol{\alpha}^i}-1)\delta. \end{equation*} Thus, \begin{equation*} \abs{\Tilde{f}(\mathbf{x})-f_1(\mathbf{x})}\leq 2^d d^n(d+\beta)\delta, \end{equation*} we choose $\delta = \frac{\epsilon}{2^{d+1}d^{\beta}(d+\beta-1)}$, and $\norm{\Tilde{f}-f}\leq \epsilon$. By using Lemma (ref), the full approximation neural network is fully connected and has depth $\mathcal{O}(\ln(1/\delta)+1)$, and width at most $\mathcal{O}((2N+1)^{\frac{d}{2}})$. The remainder of the proof follows unchanged. Thus, the weight count scales as $\mathcal{O}((2N+1)^{d}\ln(1/\delta))$. Case 2: if $d$ is odd and $d>1$, since $d-1$ is even, only the extra dimension requires special treatment.\footnote{We implicitly assume \(N \geq 4\), which is justified since \(N\) becomes large as \(\epsilon\) approaches zero. Therefore, this assumption is made without loss of generality.} Let $\bar{d}=\frac{d+1}{2}$ denote the central dimension index. Denote $\mathbf{m}^1=(m_1,...,m_{\bar{d}-1})$,$\mathbf{m}^2 = (m_{\bar{d}+1},...,m_d)$, $\boldsymbol{\alpha}^1=(\alpha_1,...,\alpha_{\bar{d}-1})$, $\boldsymbol{\alpha}^2=(\alpha_{\bar{d}+1},...,\alpha_d)$, $\mathbf{x}^1=(x_1,...,x_{\bar{d}-1})$, $\mathbf{x}^2=(x_{\bar{d}+1},...,x_d)$. Similar to the even case, denote $ \Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)$ as the neural network to approximate $f_{\mathbf{m}^1, \boldsymbol{\alpha}^1}(\mathbf{x}^1)\coloneqq\prod_{k=1}^{\bar{d}-1} \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}$ and let $\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2)$ be the neural network to approximate $f_{\mathbf{m}^2, \boldsymbol{\alpha}^2}(\mathbf{x}^2)\coloneqq \prod_{k=\bar{d}+1}^{d} \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}$. Decompose the function: \begin{equation*} \begin{split} &\phi_{\mathbf{m}}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}\\ =& \prod_{k=1}^d \psi(3N(x_k-\frac{m_k}{N}))(x_k-\frac{m_k}{N})^{\alpha_k}\\ =& \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})^{\alpha_{\bar{d}}}f_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)f_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2), \end{split} \end{equation*} since $m_{\bar{d}}\in \{-N,...,-1,0,1,...,N\}$, the key is to separate all $2N+1$ possible values of $\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))$ into two parts, each with $\sqrt{2N+1}$ units and the combination of two parts can represent $\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))$. Denote $A=\ceil{\sqrt{2N+1}}$. And define sets: \begin{equation*} \begin{split} \mathcal{G}_g &= \{-N+i*A+g, i=0,...,A-1\}, g=0,...,A-1. \end{split} \end{equation*} Each set has $A$ elements. $\forall g=0,...,A-1$, $\forall x_{\bar{d}}\in [-1,1]$, there are at most two $m_{\bar{d}}$, each in separate sets, such that $\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))>0$. Also, define \begin{equation*} \begin{split} \mathcal{G}^1&\coloneqq \mathcal{G}_{0}\cup\mathcal{G}_{1}\cup \mathcal{G}_{A-1},\\ \mathcal{G}^2&\coloneqq \left(\bigcup_{g=2}^{A-2} \mathcal{G}_g \right). \end{split} \end{equation*} By the construction, \begin{equation*} \begin{split} \mathcal{G}^1\cup \mathcal{G}^2 &\supseteq\{-N,...,-1,0,1,...,N\}, \\ \mathcal{G}_{g'} &\cap \mathcal{G}_g = \emptyset, \quad \forall g,g'=0,...,A-1, g\ne g'. \end{split} \end{equation*} Define a new function: \begin{equation*} \kappa_b(x_{\bar{d}})=\sum_{j=-N+1+Ab}^{-N+Ab+A-1}\psi(3N(x_{\bar{d}}-\frac{j}{N})), \quad b=0,1,...,A-1. \end{equation*} Notice that $j$ doesn't include values from set $\mathcal{G}_0$. By the construction, $\forall m_{\bar{d}}\in \{-N,...,-1,0,1,...,N\}$, either $ m_{\bar{d}}\in \mathcal{G}^1$, or $ m_{\bar{d}}\in \mathcal{G}^2$. If $ m_{\bar{d}}\in \mathcal{G}^2$, there is a unique $m_{(b,g)}$, such that $m_{\bar{d}}\in [-N+1+Ab,-N+Ab+A-1]$ and $m_{\bar{d}}\in \mathcal{G}_g, g=2,...,A-2$ and $m_{\bar{d}}=m_{(b,g)}$. Notice that there are $(A-3)A$ possible values for $(g,b)$. Fix a $x_{\bar{d}}\in[-1,1]$, $\exists m \in \{-N,...,-1,0,1,...,N\}$, such that $x_{\bar{d}} \in [\frac{m}{N},\frac{m+1}{N}]$. Then, $\forall m' \in \{-N,...,-1,0,1,...,N\}$, such that $m'\ne m, m'\ne m+1$, \begin{equation*} \psi(3N(x_{\bar{d}}-\frac{m'}{N}))=0. \end{equation*} If $m\in \mathcal{G}_g$, \begin{equation*} \psi(3N(x_{\bar{d}}-\frac{m}{N})) = \sum_{i\in \mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N})). \end{equation*} If $m+1\in \mathcal{G}_g$, \begin{equation*} \psi(3N(x_{\bar{d}}-\frac{m+1}{N})) = \sum_{i\in \mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N})). \end{equation*} If $m,m+1\notin \mathcal{G}_g$, \begin{equation*} \sum_{i\in \mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N}))=0. \end{equation*} There are four possible situations. First, if $m,m+1\in \mathcal{G}^2$, then $\exists b \in \{0,1,...,A-1\}$, such that $m,m+1 \in \{-N+1+Ab,...,N+Ab+A-1\}$ and \begin{equation*} \begin{split} \kappa_b(x_{\bar{d}})&=1,\\ \kappa_{b'}(x_{\bar{d}})&=0, \quad b'\in \{0,1,...,A-1\}, b'\ne b. \end{split} \end{equation*} Then, $\forall b \in \{0,1,...,A-1\}$, \begin{equation*} \begin{split} \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=\kappa_b(x_{\bar{d}})\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N})), \quad g =2,...,A-2,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&=0, \quad \forall m_{\bar{d}}\in \mathcal{G}^1,\\ \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=0, \quad \forall m_{(b,g)}\in\mathcal{G}^2, m_{(b,g)}\ne m,m+1. \end{split} \end{equation*} For the second situation, if $m,m+1 \in \mathcal{G}^1$, then, $\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N}))=0, g =2,...,A-2$. $\forall b \in \{0,1,...,A-1\}$, \begin{equation*} \begin{split} \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=\kappa_b(x_{\bar{d}})\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N}))=0, \quad g =2,...,A-2,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&= \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})), \quad \forall m_{\bar{d}}\in \mathcal{G}^1. \end{split} \end{equation*} For the third situation, if $m\in \mathcal{G}^2, m+1\in \mathcal{G}^1$, then $\exists b \in \{0,1,...,A-1\}$, such that $m,m+1 \in \{-N+1+Ab,...,-N+Ab+A-1\}$ and \begin{equation*} \begin{split} \kappa_b(x_{\bar{d}})&=1,\\ \kappa_{b'}(x_{\bar{d}})&=0, \quad b'\in \{0,1,...,A-1\}, b'\ne b. \end{split} \end{equation*} Then, $\forall b \in \{0,1,...,A-1\}$, \begin{equation*} \begin{split} \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=\kappa_b(x_{\bar{d}})\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N})), \quad g =2,...,A-2,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&=\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})), \quad \forall m_{\bar{d}}\in \mathcal{G}^1,\\ \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=0, \quad \forall m_{(b,g)}\in\mathcal{G}^2, m_{(b,g)}\ne m,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&=0, \quad \forall m_{\bar{d}}\in \mathcal{G}^1, m_{\bar{d}}\ne m+1.\\ \end{split} \end{equation*} For the last situation, if $m\in \mathcal{G}^1, m+1\in \mathcal{G}^2$, $\forall b \in \{0,1,...,A-1\}$, \begin{equation*} \begin{split} \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=\kappa_b(x_{\bar{d}})\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N})), \quad g =2,...,A-2,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&=\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})), \quad \forall m_{\bar{d}}\in \mathcal{G}^1,\\ \psi(3N(x_{\bar{d}}-\frac{m_{(b,g)}}{N}))&=0, \quad \forall m_{(b,g)}\in\mathcal{G}^2, m_{(b,g)}\ne m+1,\\ \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))&=0, \quad \forall m_{\bar{d}}\in \mathcal{G}^1, m_{\bar{d}}\ne m.\\ \end{split} \end{equation*} In conclusion, if $m_{\bar{d}}\in \mathcal{G}^1$, \begin{equation*} \begin{split} &\phi_{\mathbf{m}}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}\\ &=\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})^{\alpha_{\bar{d}}}\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2), \end{split} \end{equation*} if $m_{\bar{d}}\in \mathcal{G}^2, m_{\bar{d}}= m_{(b,g)}$, \begin{equation*} \begin{split} &\phi_{\mathbf{m}}(\mathbf{x})(\mathbf{x}-\frac{\mathbf{m}}{N})^{\boldsymbol{\alpha}}\\ &= \psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N}))(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})^{\alpha_{\bar{d}}}\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2)\\ &=\left(\sum_{i\in\mathcal{G}_g}\psi(3N(x_{\bar{d}}-\frac{i}{N}))(x_{\bar{d}}-\frac{i}{N})^{\alpha_{\bar{d}}}\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)\right)\left(\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2)\kappa_b(x_{\bar{d}})\right), \end{split} \end{equation*} Adjusting the definition, \begin{equation*} \begin{split}\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1,g,\alpha_{\bar{d}}}(\mathbf{x}^1,x_{\bar{d}})&\coloneqq\Tilde{\times}\left(\sum_{i\in\mathcal{G}_g}\Tilde{\times}(\psi(3N(x_{\bar{d}}-\frac{i}{N})),\Tilde{\times}(x_{\bar{d}}-\frac{i}{N},\dots )),\Tilde{f}_{\mathbf{m}^1,\boldsymbol{\alpha}^1}(\mathbf{x}^1)\right),\\ \Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2,b}(\mathbf{x}^2,x_{\bar{d}})&\coloneqq\Tilde{\times}\left(\Tilde{f}_{\mathbf{m}^2,\boldsymbol{\alpha}^2}(\mathbf{x}^2),\kappa_b(x_{\bar{d}})\right). \end{split} \end{equation*} For each neural network, with at most $(d-1)^\beta (2N+1)^{\frac{d-1}{2}}\ceil{\sqrt{2N+1}}$ output units, depth $\mathcal{O}(\ln(1/\delta)+1)$ and width $\mathcal{O}((2N+1)^{\frac{d}{2}})$, by Lemma (ref), we can use a neural network to represent all possible values. For each $(\mathbf{m}^2,\boldsymbol{\alpha}^2)$ and $(\mathbf{m}^1,\boldsymbol{\alpha}^1)$, if $m_{\bar{d}}\in \mathcal{G}^2$, let $a_{\mathbf{m,\boldsymbol{\alpha}},(b,g),\alpha_{\bar{d}}}$ denote $a_{\mathbf{m},\boldsymbol{\alpha}}$ in the case $m_{\bar{d}}=m_{(b,g)}$; if $m_{\bar{d}}\in \mathcal{G}^1$, let $a_{\mathbf{m,\boldsymbol{\alpha}}}$ denote $a_{\mathbf{m},\boldsymbol{\alpha}}$. We set $a_{\mathbf{m,\boldsymbol{\alpha}},(b,g),\alpha_{\bar{d}}}=0$ if it doesn't satisfy the definition. We can rewrite $f_1(\mathbf{x})$ as \begin{equation*} \begin{split} f_1(\mathbf{x}) = \sum_{\mathbf{m}^2, \boldsymbol{\alpha}^2, b} \Bigg( & \sum_{\mathbf{m}^1, \boldsymbol{\alpha}^1,g \in \mathcal{G}^2,\alpha_{\bar{d}}} a_{\mathbf{m}^1, \boldsymbol{\alpha}^1,(b,g),\alpha_{\bar{d}}} f_{\mathbf{m}^1, \boldsymbol{\alpha}^1, g,\alpha_{\bar{d}}}(\mathbf{x}^1, x_{\bar{d}}) \Bigg)\\ &\times f_{\mathbf{m}^2, \boldsymbol{\alpha}^2, b}(\mathbf{x}^2, x_{\bar{d}}) \\ \quad + \sum_{\mathbf{m}^2, \boldsymbol{\alpha}^2} \Bigg(& \sum_{{\mathbf{m}^1, \boldsymbol{\alpha}^1, m_{\bar{d}} \in \mathcal{G}^1},\alpha_{\bar{d}}} a_{\mathbf{m}, \boldsymbol{\alpha}} \left(x_{\bar{d}} - \frac{m_{\bar{d}}}{N} \right)^{\alpha_{\bar{d}}} \psi\left( 3N\left(x_{\bar{d}} - \frac{m_{\bar{d}}}{N} \right) \right) f_{\mathbf{m}^1, \boldsymbol{\alpha}^1}(\mathbf{x}^1)\Bigg)\\ &\times f_{\mathbf{m}^2, \boldsymbol{\alpha}^2}(\mathbf{x}^2). \end{split} \end{equation*} Define the full approximation by the following: \begin{equation*} \begin{split} \Tilde{f} = 2^{\frac{d}{2}} d^\beta \sum_{\mathbf{m}^2, \boldsymbol{\alpha}^2, b} \Tilde{\times}\Bigg( & \frac{1}{2^{\frac{d}{2}} d^\beta} \sum_{\mathbf{m}^1, \boldsymbol{\alpha}^1,g \in \mathcal{G}^2,\alpha_{\bar{d}}} a_{\mathbf{m}^1, \boldsymbol{\alpha}^1,(b,g),\alpha_{\bar{d}}} \Tilde{f}_{\mathbf{m}^1, \boldsymbol{\alpha}^1, g,\alpha_{\bar{d}}}(\mathbf{x}^1, x_{\bar{d}}), \\ & \Tilde{f}_{\mathbf{m}^2, \boldsymbol{\alpha}^2, b}(\mathbf{x}^2, x_{\bar{d}}) \Bigg) \\ \quad + 2^{\frac{d}{2}} d^\beta \sum_{\mathbf{m}^2, \boldsymbol{\alpha}^2} \Tilde{\times}\Bigg( &\Tilde{f}_{\mathbf{m}^2, \boldsymbol{\alpha}^2}(\mathbf{x}^2),\\ \frac{1}{2^{\frac{d}{2}} d^\beta} \sum_{{\mathbf{m}^1, \boldsymbol{\alpha}^1, m_{\bar{d}} \in \mathcal{G}^1},\alpha_{\bar{d}}} & a_{\mathbf{m}, \boldsymbol{\alpha}} \Tilde{\times}\bigg(\Tilde{f}_{\mathbf{m}^1, \boldsymbol{\alpha}^1}(\mathbf{x}^1),\Tilde{\times}\left(\psi(3N(x_{\bar{d}}-\frac{m_{\bar{d}}}{N})),\Tilde{\times}(x_{\bar{d}}-\frac{m_{\bar{d}}}{N},\dots )\right)\bigg) \Bigg). \end{split} \end{equation*} For the neural network in the first and second lines, the depth is $\mathcal{O}(\ln(1/\delta)+1)$ and width is $\mathcal{O}((2N+1)^{\frac{d}{2}})$; since $\mathcal{G}^1$ has at most $3 \ceil{\sqrt{2N+1}}$ elements, we need neural networks in the third and fourth lines to have depth $\mathcal{O}(\ln(1/\delta)+1)$ and width $\mathcal{O}( (2N+1)^{\frac{d}{2}})$. To construct the first line's neural network, we need one more layer of composition $\Tilde{\times}(\cdot)$. Thus, we must adjust the term $d+\beta-1$ in Appendix (ref) into $d+\beta$. That is, we choose $\delta = \frac{\epsilon}{2^{d+1}d^\beta (d+\beta)\delta}$. The rest of the proof remains the same as in Appendix (ref). Case 3: if $d=1$, we need a special treatment.\footnote{Although there is no theoretical advantage in using deep neural networks when $d=1$, we include a brief proof for completeness.} The method used above requires dividing $[-1,1]$ into $N$ grids and $N$ different functions of $\psi(x)$, the width is $\mathcal{O}(N)$. Since $d\geq 2$, the largest width is $\mathcal{O}(N^{\frac{d}{2}})$, this approach is applicable to the previous cases. However, when $d=1$, we need the largest width to be $\mathcal{O}(\sqrt{N})$. We will follow the notation used above. First, notice that the function $\kappa_b(x)$ requires a width $\mathcal{O}(N)$; we first modify this function. Define a new function, $\forall b=0,1,\dots,A-1$, \begin{equation*} \Psi_b(x)=\begin{cases} 1, & x\in [-N+Ab+1,-N+Ab+A-1],\\ \psi(3N(x-\frac{-N+Ab+1}{N})), & x\in [-N+Ab,-N+Ab+1],\\ \psi(3N(x-\frac{-N+Ab+A-1}{N})), & x\in [-N+Ab+A-1,-N+Ab+A],\\ 0, &otherwise. \end{cases} \end{equation*} This function can be directly represented by a ReLU neural network with finite width and depth. Notice that \begin{equation*} \Psi_b(x)=\kappa_b(x). \end{equation*} To represent all possible values of $\Psi_b(x_{\bar{d}})$, we only need a neural network with finite depth and width $\mathcal{O}(\sqrt{N})$. $\forall m'\in \mathcal{G}^2, \exists m \in [-N+2,-N+A-2], \exists b=0,1,\dots,A-1$, such that $m' = m+b$. We denote $a_{m',\alpha}$ as $a_{m,b,\alpha}$. We notice that $f_1(x)$ can be written as: \begin{equation*} \begin{split} f_1(x) &= \sum_b\sum_\alpha \sum_{m=-N+2}^{-N+A-2} a_{m,b,\alpha} \Psi_b(x)\cdot \psi( x-\frac{m+bA}{N})( x-\frac{m+bA}{N})^{\alpha}\\ &+\sum_\alpha \sum_{m\in \mathcal{G}^1} a_{m,\alpha} \psi( x-\frac{m}{N})(x-\frac{m}{N})^{\alpha}\\ &= \sum_b \Psi_b(x)\cdot \sum_{m=-N+2}^{-N+A-2}\sum_\alpha a_{m,b,\alpha}\psi\left(-\frac{m}{N}+\sum_{b'} \Psi_{b'}(x)\cdot (x-\frac{{b'}A}{N})\right)\\ &\cdot( -\frac{m}{N} +\sum_{b'} \Psi_{b'}(x)\cdot (x-\frac{{b'}A}{N}))^{\alpha}\\ &+\sum_\alpha \sum_{m\in \mathcal{G}^1} a_{m,\alpha} \psi( x-\frac{m}{N})(x-\frac{m}{N})^{\alpha} \end{split} \end{equation*} Define the full approximation by the following: \begin{equation*} \begin{split} \Tilde{f} &= 2d^{\beta} \sum_b \Tilde{\times}\Biggl( \Psi_b(x),\\ &\frac{1}{2d^{\beta}}\sum_{m=-N+2}^{-N+A-2}\sum_\alpha a_{m,b,\alpha} \Tilde{\times}\biggl(\psi\Bigl(-\frac{m}{N}+ \sum_{b'} \Tilde{\times}\bigl( \Psi_{b'}(x),x-\frac{{b'}A}{N}\bigr)\Bigr),\\ &\Tilde{\times}\Bigl( -\frac{m}{N}+ \sum_{b'} \Tilde{\times}\bigl( \Psi_{b'}(x),x-\frac{{b'}A}{N}\bigr),\dots\Bigr)\biggr)\Biggr)\\ &+\sum_\alpha \sum_{m\in \mathcal{G}^1} a_{m,\alpha} \Tilde{\times}\left(\Psi_b(x), \Tilde{\times}\Bigl(\psi( x-\frac{m}{N}),\Tilde{\times}( x-\frac{m}{N},\dots)\Bigr)\right) \end{split} \end{equation*} The width needed for this approximation is at most $\mathcal{O}(\sqrt{N})$ and depth $\mathcal{O}(\ln(1/\delta)+1)$. The rest of the proof remains the same as above. In conclusion, there is a ReLU network that has depth $c(\ln(1/\epsilon)+1)$, width at most $c\epsilon^{-\frac{d}{2\beta}}$, and weights at most $c\epsilon^{-\frac{d}{\beta}}(\ln(1/\epsilon)+1)$, with some constant $c=c(d,\beta)$. Lemma (ref) shows that this network can be fully connected with the same level of depth, width, and weights. The only difference is the constant term $c$. \end{proof}