quantization except for a different sub-network for weight approximation with width $t$ and depth $\frac{t}{\log \lambda}$+1. Here we give the theorem and the proof is included in Appendix \[PT2\].

\[T1linear\] For any $f\in \mathcal{F}_{d,n}$ , given weight maximum precision $\frac{1}{\lambda}$, there is a ReLU network with fixed structure that can approximate $f$ with any error $\epsilon\in(0,1)$, such that (1) the depth is $\mathcal{O}\left(\log \left(1/\epsilon\right)\right)$; (2) the number of weights is $\mathcal{O}\left(\left(\log\left(1/\epsilon\right)+\frac{\log^2\left(1/\epsilon\right)}{\log \lambda}\right)\left(1/\epsilon\right)^{\frac{d}{n}}\right)$; (3) the number of bits needed to store the network is $\mathcal{O}\left(\left(\log (\lambda)\log\left(1/\epsilon\right)+\log^2\left(1/\epsilon\right)\right)\left(1/\epsilon\right)^{\frac{d}{n}}\right)$.

Function-dependent Structure {#sec:dependent}
============================

The network complexity can be reduced if the network topology can be set according to a specific target function, i.e. function-dependent structure. In this section, we provide an upper bound for function-dependent structure when $d =1$ and $n=1$, which is asymptotically better than that of a fixed structure. Specifically, we first define an approximation to $f(x)$ as $\widetilde{f}(x)$ that has special properties to match the peculiarity of quantized networks. Then we use piecewise linear interpolation and “cached” functions [@yarotsky2017error] to approximate $\widetilde{f}(x)$ by a ReLU network.

Function Transformation
-----------------------

While simply using piecewise linear interpolation at the scale of $\epsilon$ can satisfy the error bound with $\mathcal{O}\left(1/\epsilon\right)$ weights, the complexity can 