/2^{-t}\right\rceil\frac{2^{-t}}{T}$; (3) $|\widetilde{f}(x) - f(x)| < \frac{2^{-t}}{T} $.

Approximation by ReLU Networks
------------------------------

With the help of Proposition \[ftp\] and the weight construction method described in Section \[weights\], we are able to apply the interpolation and cached function approach. Denoting the output of the network as $f''(x)$, we have $|f(x)-f''(x)| = |f(x)-\widetilde{f}(x)|+|\widetilde{f}(x)-f''(x)|\leq\epsilon$ by choosing appropriate hyper-parameters which are detailed in Appendix \[PT3\] and the network complexity is obtained accordingly.

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

Using the different weight construction approach as in the case of function-independent structure, we have the result for linear quantization:

\[T4\] For any $f\in \mathcal{F}_{1,1}$ , given weight maximum precision $\frac{1}{\lambda}$, there is a ReLU network with function-dependent 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(1/\epsilon\right)$; (3) the number of bits needed to store the network is $\mathcal{O}\left(\log (\lambda)/\epsilon\right)$.

Bound-based Optimal Bit-width {#sec:bitwidth}
