On the Universal Approximability of Quantized ReLU Neural Networks

Yukun Ding 1 Jinglan Liu 1 Yiyu Shi 1

arXiv:1802.03646v1 [cs.LG] 10 Feb 2018

Abstract
Compression is a key step to deploy large neural networks on resource-constrained platforms.
As a popular compression technique, quantization
constrains the number of distinct weight values
and thus reducing the number of bits required to
represent and store each weight. In this paper,
we study the representation power of quantized
neural networks. First, we prove the universal approximability of quantized ReLU networks. Then
we provide upper bounds of storage size given
the approximation error bound and the bit-width
of weights for function-independent and functiondependent structures. To the best of the authors’
knowledge, this is the first work on the universal
approximability as well as the associated storage
size bound of quantized neural networks.

1. Introduction
Various deep neural networks deliver state-of-the-art performance on many tasks such as target tracking, autonomous
driving, etc. Their prevalence has extended to embedded
or mobile devices for edge intelligence, where security, reliability or latency constraints refrain the networks from
running on servers or in clouds. However, large network
sizes and the associated expensive computation and memory
consumption make edge intelligence a challenging task.
In response, as will be detailed in Section 2, substantial
effort has been made to reduce the memory consumption of
neural networks while minimizing the accuracy loss. The
memory consumption of neural networks can be reduced by
either directly reducing the number of weights or decreasing
the number of bits (bit-width) needed to represent and store
each weight, which can be employed on top of each other
(Choi et al., 2016). The number of weights can be reduced
by pruning (Han et al., 2015b), weight sparsifying (Liu
et al., 2015), structured sparsity learning (Wen et al., 2016)
and low rank approximation (Denton et al., 2014). The
1

Department of Computer Science and Engineering, University of Notre Dame, IN, USA. Correspondence to: Yukun Ding
<yding5@nd.edu>.

bit-width is reduced by quantization that maps data to a
smaller set of distinct levels (Sze et al., 2017). Note that
while quantization may stand for linear quantization only
(Li et al.; Gysel et al., 2016) or nonlinear quantization only
(Han et al., 2015a; Choi et al., 2016) in different works, our
discussion will cover both cases.
However, as of today quantization is still only empirically
shown to be robust and effective to compress various neural network architectures (Hubara et al., 2016; Zhou et al.,
2017b; Zhuang et al., 2017). Its theoretical foundation still
remains mostly missing. Specifically, many important questions remain unanswered. For example:
• Why even binarized networks, those most extremely
quantized with bit-width down to one, still work well?
• How small can a quantized network be to achieve a
desired accuracy?
In this paper, we provide some insights for these questions
from a theoretical perspective. We focus on deep networks
with the ReLU activation function, which is among the most
widely used in deep neural networks (Xu et al., 2015). The
conclusions on ReLU networks can be extended to any other
networks that use piecewise linear activation functions with
finite breakpoints such as leaky ReLU immediately, as one
can replace a ReLU network by an equivalent one using
these activation functions while only increasing the number
of units and weights by constant factors (Yarotsky, 2017).
The main contributions of this paper include:
• We prove the universal approximation property of quantized ReLU networks. We prove that even the most
extremely quantized ReLU networks using two distinct
weight values are capable of representing a wide class
of functions with arbitrary accuracy.
• Given the number of distinct weights and the desired approximation error, we further provide an upper
bound of the storage size which is the total number of
bits needed to store all weights for the quantized ReLU
network.
The remainder of the paper is organized as follows. Section
2 reviews related works. Section 3 lays down the models and

On the Universal Approximability of Quantized ReLU Neural Networks

assumptions of our analysis. We prove the universal approximability and the upper bounds with function-independent
structure in Section 4 and extend it to function-dependent
structure in Section 5. Concluding remarks are given in
Section 6.

2. Related Works
Linear quantization does mapping with same distance between contiguous quantization levels and is usually implemented by storing weights as fixed-point numbers with reduced bit-width (Li et al.; Gysel et al., 2016). Nonlinear
quantization clusters weights to different groups and all
weights in one group share a single value. Then the weights
are stored using lossless binary coding (the index to a lookup
table) instead of the actual values (Han et al., 2015a; Choi
et al., 2016). The most important difference between linear quantization and nonlinear quantization is that the latter
does not require weights to be low precision values. There
are rich literatures on how to obtain quantized networks, either by linear quantization or nonlinear quantization (Zhou
et al., 2017a; Leng et al., 2017; Shayar et al., 2017).
It is reported that a pruned AlexNet can be quantized to eight
bits and five bits in convolutional layers and fully connected
layers respectively without any loss of accuracy. Similar
result is also observed in LENET-300-100, LENET-5, and
VGG-16 (Han et al., 2015a). One may argue that some of
these benchmark networks are known to have redundancy.
However, recent works show that quantization works well
even on networks that are designed to be extremely small
and compact. The bit-width of SqueezeNet, which is a stateof-the-art compact network, can be reduced to eight while
preserving the original accuracy (Gysel et al., 2016; Iandola
et al., 2016). There are some representative works that can
achieve little accuracy loss on ImageNet classification even
using binary or ternary weights (Courbariaux et al., 2015;
Rastegari et al., 2016; Li et al., 2016; Zhu et al., 2016).
More aggressively, some works also reduce the precision of
activations, e.g. (Hubara et al., 2016; Rastegari et al., 2016).
Although the classification accuracy loss can be minimized,
the universal approximation property is apparently lost, as
with limited output precision the network cannot achieve
arbitrary accuracy. Accordingly, we do not include them
in the discussion of this paper. Motivated by the great
empirical success, the training of quantized neural networks
has been analyzed theoretically (Li et al., 2017b; Li et al.;
Choi et al., 2016; Li et al., 2017a).
The universal approximability of ReLU networks is proved
in (Mhaskar & Micchelli, 1992) and revisited in (Sonoda
& Murata, 2017). Recently, Hanin discusses the expressive
power of ReLU networks with bounded width and proves
that a ReLU network with width d + 1 can approximate
any continuous convex function of d variables arbitrarily

well (Hanin, 2017). Shaham et al. construct a sparselyconnected depth-4 ReLU network and prove its error bound
(Shaham et al., 2016). Liang et al. prove that, for a large
class of piecewise smooth functions, a network with ReLU
and binary step units can provide an error bound  with O( 1 )
layers and O(poly log 1 ) neurons (Liang & Srikant, 2016).
Zhao et al. prove the universal approximation property of
low displacement rank (LDR) neural networks with a mild
condition on the displacement operator, which is the result of
another effective technique of neural network compression
(Zhao et al., 2017). Our work is based on (Yarotsky, 2017)
which provides approximation error bound for deep ReLU
networks through construction.

3. Models and Assumptions
Throughout this paper, we define ReLU networks as feedforward neural networks with the ReLU activation function
σ(x) = max(0, x). The ReLU network considered includes
several input units, a number of hidden units, and one output
unit. Without loss of generality, each unit can only connect
to units in the next layer. We denote the number of distinct
weight values as λ (λ ≥ 2), for both linear quantization and
nonlinear quantization. To store each weight, we only need
log(λ) 1 bits to encode the index i.e., the bit-width is log(λ).
The overhead to store sparse structures can be ignored because it varies depending on the implementation and can
be easily reduced to the same order as the weight storage
using techniques such as compressed sparse row (CSR) for
nonlinear quantization. The number of bits needed to store
the codebook can also be ignored, because it has lower order
of complexity.
We consider any function f in the Sobolev space: f ∈
Wn,∞ ([0, 1]d ) and
max ess sup |Dn f (x)| ≤ 1.
n:|n|≤n x∈[0,1]d

(1)

We denote this function space as Fd,n in this paper. The
space Wn,∞ consists of all locally integrable function f :
Ω → R such that Dn f ∈ L∞ (Ω), where |n| ≤ n.
Thus we are actually considering a broad range of functions
since any f that has bigger domain or derivative can be
simply scaled to satisfy given restrictions.

4. Function-independent Structure
We start our analysis with function-independent structure,
where the topology of the network is fixed for any function
considered. The main idea to prove the universal approximability is to construct a network that can achieve arbitrary
accuracy given the number of distinct weight values λ. The
1

tion

Throughout this paper, we omit base 2 for clarity of presenta-

On the Universal Approximability of Quantized ReLU Neural Networks

storage size of this network then naturally serves as an upper
bound.
We start with nonlinear quantization, and first present the
approximation of some basic functions by sub-networks
in Section 4.1. We then present the sub-network that approximates any weight in Section 4.2, and finally the whole
network composed of these sub-networks in Section 4.3.
We extend the results to linear quantization in Section 4.4.
4.1. Approximation of squaring/multiplication
Proposition 1. The function f (x) = x2 on the segment
[0, 1] can be approximated by a ReLU network fsr with only
two weight values 12 and − 21 , so that
(i) if x = 0,

fsr (x)

Since

= 0;


xy = 2


(ii) the approximate error s = O 2−2r ;
(iii) the depth is O (r);
(iv) the width is a constant;
(v) the number of weight is O (r).
Proof. For fs (x) = x2 , let fsr be the piecewise linear interpolation of f with 2r + 1 uniformly distributed breakpoints
k
r
2r , k = 0, . . . , 2 . We have
k
fsr ( r )
2

Figure 1. ReLU Implementation of fsr (x) where b and w denote
bias and weight respectively. Details of block Bm and block Bg
are depicted on the left.

k
= ( r )2 ,
2

k = 0, . . . , 2

r

(2)

s = ||fsr (x) − fs (x)||∞ ≤ 2−2(r+1) .
Consider the function g : [0, 1] 7→ [0, 1]:
(
2x
x < 12
g(x) =
2(1 − x) x ≥ 12 .

fsr (x) = x −

2
−

 x 2
2

−

 y 2
2

!
,

(6)

we can implement multiplication with the help of Proposition 1.
Proposition 2. Given x ∈ [−1, 1], y ∈ [−1, 1], and only
two weight values 12 and − 12 , there is a ReLU network with
two input units that implements a function ×0 : R2 7→ R, so
that
(i) if x = 0 or y = 0, then ×0 (x, y) = 0;
0
(ii) for any
 x, y, the error ×0 = | × (x, y) − xy| =
−2r
O 2
;

(iii) the depth is O (r);

and the approximation error

Note that

x+y
2

r
X

2−2i g ◦i (x)

(3)

(4)

(5)

i=1

where g ◦i (x) is the i-th iterate of g(x). Since g(x) can
be implemented by a ReLU network as g(x) = 2σ(x) −
4σ(x − 12 ), g ◦r (x) can be obtained by concatenating such
implementation of g(x) for r times.
Now, to implement fsr (x) based on g ◦r (x), all we need
are weights {2−2 , 2−4 , · · · , 2−2(r−1) , 2−2r }, which can be
easily constructed with additional 2r layers and the weight
1
r
2 . Then, fs (x) can be implemented by a ReLU network
as in Figure 1. A connection from or to a block indicates
connections to all units in the block. Some units are copied
to compensate the scaling caused by 12 and to facilitate the
construction of higher level networks.

(iv) the width is a constant;
(v) the number of weights is O (r).
Proof. Build a sub-network ξs that computes fxr as in Proposition 1 and let
 

 
 
|x + y|
|x|
|y|
0
r
r
r
× (x, y) = 2 fs
− fs
− fs
.
2
2
2
(7)
Then the statement (i) is followed by property (i) of Proposition 1. Inserting Equation (3) to Equation (7), we get the
error bound of ×0 :
×0 ≤ 6 · 2−2(r+1) .

(8)

Since we can easily construct a sub-network Babs that computes the absolute value, ×0 (x, y) can be constructed as a
linear combination of three parallel ξs ’s and feed them with
|x| |y|
|x+y|
2 , 2 , and
2 . Then claims of statement (iii), (iv), and
(v) are also obtained.
4.2. Approximation of weights
Proposition 3. A connection with any weight w ∈ [−1, 1]
in a ReLU network can be approximated by a sub-network

On the Universal Approximability of Quantized ReLU Neural Networks

that has only λ ≥ 2 distinct weights, so that
(i) the sub-network is equivalent to a connection with weight
w0 where |w0 − w| < 2−t ;


1
(ii) the depth is O λt λ−1 ;
(iii) the width is O(t);


1
(iv) the number of weights is O λt λ−1 +1 ;
Proof. Consider that we need a weight w to feed the input
x to a unit in the next layer as wx. With limited number of
distinct weight values, we can construct the weight we need
by cascade and combination.
For clarity, we first consider w ≥ 0 and x ≥ 0, and relax
these assumptions later. The connections with w = 0 can
be seen as an empty network while w = 1 can be easily
implemented by 4 units with weight 12 . Now we show how
to represent all integral multiples of 2−t from 2−t to 1−2−t .
1
Without loss of generality, we assume t λ−1 is an integer.
1
We use λ weights that include − 2 and W :
W , {2−1 , 2−t

1
λ−1

, 2−t

2
λ−1

, · · · , 2−t

λ−2
λ−1

}.

(9)

We first construct all w from Wc which is defined as
Wc , {2−1 , 2−2 , · · · , 2−(t−1) }.

(10)

the network is solely determined by w and works for any
input x.
4.3. Approximation of general smooth functions
Theorem 1. For any f ∈ Fd,n , given λ distinct weights,
there is a ReLU network with fixed structure that can approximate f with any error  ∈ (0, 1), so that
 

 1

1
n2d+3 λ−1
+ log  ;
(i) the depth is O λ log 
(ii) the number of weights is
 
 1 +1  d 
1 n
n2d+3 λ−1
;
O λ log 

(iii) the number of bits needed to store the network is


1
 λ−1

+1
d
d+3
1 n
.
O λ(log λ) log n2


Proof. The proof is composed of four parts. We first approximate f by Taylor polynomial as f2 and prove the approximation error bound. Then we approximate f2 by a ReLU
network that is denoted as f 0 with bounded error. After that,
we present the ReLU implementation the network f 0 . At
last, we show the complexity of the network.
Consider a function:

1

Similar to a numeral system with radix equal to t λ−1 , any
wi ∈ Wc can be obtained by concatenating weights from W
1
while every weights in W is used no greater than t λ−1 − 1
times.
After that, all integral multiples of 2−t from 2−t to
1 − 2−t can be represented by a binary expansion on
Wc . Note that connections in the last layer for binary expansion use weight 12 , thus additional 2−1 is multiplied
to scale the resolution from 2−(t−1) to 2−t . Since for
any
in
 weight
 Wc we need to concatenate no more than
1
λ−1
λ t
− 1 weights in a straight line, the sub-network
 1

has no greater than λ t λ−1 − 1 + 1 layers, and no greater
 1

than 4tλ t λ−1 − 1 + 8t + 4 weights.
We now relax the assumption w ≥ 0. When w < 0, the
sub-network can be constructed as w = |w|, while we use
− 12 instead of 12 in the last layer. To relax the assumption
x ≥ 0, we can make a duplication of the sub-network. Let
all the weights in the first layer of the sub-network be 12 for
one and − 12 for the other. Here we are utilizing the gate
property of ReLU. In this way, one sub-network is activated
only when x > 0 and the other is activated only when x < 0.
The sign of the output can be adjusted by flipping the sign
of weights in the last layer. Note that the configuration of

ψm (x) =

d
Y

h(3N xk − 3mk ),

(11)

k=1

where m = (m1 , · · · , md ) ∈ {0, 1, · · · , N }d , and h(x) is
defined as follows:


|x| ≤ 1
1
h(x) = 2 − |x| 1 < |x| < 2 .
(12)


0
|x| ≥ 2
Note that
X

ψm (x) ≡ 1,

x ∈ [0, 1]d

(13)

m

and

mk
1
(14)
< ∀k}.
N
N
For all m, the order n−1 Taylor polynomial for the function
f is

X Dn f
m n
Tm =
x−
.
(15)
m
n! x= N
N
supp ψm ⊂ {x : xk −

n:|n|<n

According to Tm , we define an approximation to f by Taylor
polynomial using Tm0 as
X
f2 ,
ψm Tm0 ,
(16)
m∈{0,··· ,N }d

On the Universal Approximability of Quantized ReLU Neural Networks

where
Tm0

X

=

βm,n



n:|n|<n

and βm,n is
ple of

1
n

Dn f
n!

m
x= N

d n−|n|
.
N

m n
x−
,
N

(17)

rounded to the nearest integral multi-

Proposition 2. Consider that if we construct our function ×0
with | ×0 (x, y) − xy| < ×0 = 2−2(r+1) , then
| ×0 (x, y) − xz| ≤ |x(y − z)| + ×0 .

(21)

0
Applying Equation (21) to |fm,n
(x) − fm,n (x)| repeatedly,
we bound it to Equation (22) on the next page.

Then the approximation error of f2 is bounded by Equation
(18).
X
|f (x) − f2 (x)| = |
ψm (x)(f (x) − Tm0 (x))|
m

X

≤

m
m:|xk − Nk

≤ 2d

|f (x) − Tm0 (x)|

1
|< N
∀k

max
m

m:|xk −

2d

k
N

max
m

m:|xk −

2d dn
≤
n!

1
|< N
∀k



1
N
X

k
N

Finally, we define our approximation to f (x) as f 0 (x):
f 0 (x) ,

X

X

0
βm,n fm,n
(x).

(23)

m∈{0,··· ,N }d n:0<|n|<n

Using Equation (22), we get the error bound of the approximation to f2 (x) as in Equation (24).

|f (x) − Tm (x)|+

1
|< N
∀k

|Tm (x) − Tm0 (x)|

|f 0 (x) − f2 (x)| = |

X

X


0
(x) − fm,n (x) |
βm,n fm,n

m∈{0,··· ,N }d n:|n|<n

n

n

max ess sup |D f (x)|+
n:|n|=n x∈[0,1]d

=|

X

X


0
βm,n fm,n
(x) − fm,n (x) |


m:x∈suppψm n:|n|<n
Dn f
m n
X
0
2
max |βm,n −
| (x − )
≤ 2d max
|fm,n
(x) − fm,n (x)|
n!
N
m:x∈suppψ
m
n:|n|<n
n:|n|<n
 n
d n
2d dn 1
≤
2
d
(d
+
n
−
1) ×0 .
+
≤
n!
N
(24)
 n
 1  n−1 ! The second line follows again the support property and
d
2
d
d
d
+ ··· +
statement (i) of Proposition 2. The third line uses the bound
n
N
N
N
|βm,n | ≤ 1.
 n 

d
1
≤ 2d
1+
Then the final approximation error bound is as follows:
N
n!
(18)
|f 0 (x) − f (x)| ≤ |f 0 (x) − f2 (x)| + |f (x) − f2 (x)|
The second step follows ψm (x) = 0 when x ∈
/ suppψm . In
 n
d
d n
d+1
the third step we turn the sum to multiplication, because for
≤ 2 d (d + n − 1) ×0 + 2
.
d
N
any x there are up to 2 terms ψm (x) that are not equal to
(25)
zero. The fourth step uses a Lagrange’s form of the Taylor
Using
Equation
(8)
and
choosing
r
as
remainder. The fifth step follows different round precision
of βm,n in different order and the fact that the number of
log (6N n (d + n − 1))
terms with order i is not greater than di .
r=
− 1,
(26)
2
We rewrite f2 as
the approximation error turns to
X
X
f2 =
βm,n fm,n (x),
(19)
 n
d
m∈{0,··· ,N }d n:|n|<n
0
d
(27)
.
|f (x) − f (x)| ≤ 3 · 2
N
where


n
m
fm,n (x) = ψm x −
.
(20)
For any given  > 0, we need
N
Note that βm,n is a constant and thus f2 is a linear combi
1
nation of at most dn (N + 1)d terms of fm,n (x). Note that
3 · 2d dn n
N≥
.
(28)
when d = 1, the number of terms should be n(N + 1)d

instead; but for simplicity of presentation we loosely use
the same expression as they are on the same order.
We now present the construction of the network for f 0 (x).
0
0
We define an approximation to fm,n (x) as fm,n (x). The only
If every fm,n
(x) can be computed by a sub-network, then
0
0
0
difference between fm,n (x) and fm,n (x) is that all multiplif (x) is simply a weighted sum of all outputs of fm,n
(x).
0
cation operations are approximated by × as discussed in
By Proposition 3, we can implement the needed weights
d



On the Universal Approximability of Quantized ReLU Neural Networks





m|n| 
m1  0 
0
fm,n
(x) − fm,n (x) = ×0 h(3N x1 − 3m1 ), · · · , ×0 h(3N xd − 3md ), ×0 xi1 −
, × · · · , xi|n| −
N
N





mi|n| 
mi1 
− h(3N x1 − 3m1 ) h(3N x2 − 3m2 ) · · · h(3N xd − 3md ) xi1 −
· · · xi|n| −
N
N
≤ (d + |n|)×0
i1 , · · · , i|n| ∈ {1, 2, · · · , d}
(22)

Table 1. Block configuration for function-independent structure

Figure 2. ReLU implementation of f 0 (x). The connections of all
Bfmn are the same. Every connection from BN to other blocks
has no greater than two weights.

βm,n by choosing t = log
0
to constructing fm,n
(x).

nN n
dn .

Then we simplify the task

×0 can be implemented
as discussed in Proposition 2. For

i
h( 3N xi − m
,
noticing
that h(x) = h(−x), we can
N
mi
mi
i
first compute |xi − m
|
as
σ(x
N
 i − N )+σ( N −xi ) and then
mi
scale it to 3N |xi − N | . The implementation of h(x) can
thus be simplified as 1−σ(x−1)+σ(x−2) since the input is
nonnegative. Furthermore, by choosing N as cd2 where c ∈
n
if n > 1.
N and c > 1, N1 is an integral multiple of n1 Nd



n 2
When n = 1, N1 is an integral multiple of n1 Nd
. As
discussed in Proposition 3, we build a weight construction
network Bw in the way that all integral multiples of the
i
minimal precision can be obtained. Therefore, all m
N can
be obtained in the same way as βm,n , except that we need to
concatenate two weight construction sub-networks.
So far we have proved that, for any f ∈ Fd,n there exists a
network that approximates f arbitrary well with as few as 2
distinct weight values. This proves the universal approximability of qunatized ReLU networks, and answers the first
question in Section 1.
Now we analyze the complexity of the network. The implementation of f 0 (x) is shown in Figure 2. The function and size of blocks are listed in Table 1. While we
can write the complexity of the network in an explicit
expression, here we use the O notation for clarity. Let
Nd , Nw , Nb be the depth, the number of weights, and the
number of bits required respectively. The weight construction blocks Bw have the highest order of number of weights

block

function

width

Bw

construct weights

t

depth
 1

λ t λ−1 − 1 + 1

BN
Babs
Bs
Bh
B×0

construct N1 , · · · , NN−1
get absolute values
scale by 3N
implement h(x)
implement ×0 (x, y)

2N
4
4
12
60

1
1
log 3N
2
1
3r + 1



1
and we have Nw = O λt λ−1 +1 N d . Meanwhile, we get


1
n
Nd = O λt λ−1 + log N . Inserting t = log nN
dn and
 1
N = O 1 n , we get
 1
 !

1
n2d+3 λ−1
+ log
Nd = O λ log



(29)

and
n2d+3
Nw = O λ log



1
d !
 λ−1
+1   n
1
.


(30)

Multiplying Nw by log λ, Nb is obtained. This answers the
second question in Section 1 and concludes the proof of
Theorem 1.
4.4. Extension to Linear quantization
With λ distinct values, a linearly quantized network has a
minimal resolution of λ1 . The proof for the approximability
of linear quantization can be done similarly except for a
different sub-network for weight approximation with width
t and depth logt λ +1. Here we give the conclusion for brevity:
Given weight maximum precision λ1 , there exists a ReLU
network that can approximate any
f ∈ Fd,n with
 any error

1
1
 ∈ (0, 1) so that the depth is O
log λ + 1 log  , the


2 1  nd
number of weights is O log1 λ log 1
, and the


d 


2
1 n
number of bits is O log 1
, which are asymptot
ically worse than those in the nonlinear quantization.

On the Universal Approximability of Quantized ReLU Neural Networks

5. Function-dependent Structure
The network complexity can be reduced if the network topology can be set according to a specific target function, i.e.
function-independent 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 fixed structure. Specifically, we first define an approximation to f (x) as fe(x) that has special properties to match the
peculiarity of quantized networks. Then we use piecewise
linear interpolation and “cached” functions (Yarotsky, 2017)
to approximate fe(x) by ReLU networks.

Figure 3. An example to illustrate the relationship between f (x),
f + and fe(x).

5.1. Function Transformation
While simply using piecewise linear interpolation at the
scale of  can satisfy the error bound with O () weights,
the complexity can be reduced by first doing interpolation
at a coarser scale and then fill the details in the intervals to
make the error go down to . By assigning “cached function”
to every interval depending on specific functionand proper

1
scaling, the number of weights is reduced to O  log(1/)
without constraints on weights (Yarotsky, 2017).
The key difficulty in applying this approach to quantized
ReLU networks is that the required linear interpolation at
i
T exactly where i = 1, 2, · · · , T is not feasible because of
the constraint on weight selection.
To this end, we transform f (x) to fe such that the approximation
 error is bounded; the Lipschitz constant is preserved;
i
e
f T are reachable under the constraints of weight selection without increasing the requirement on weight precision.
We first divide [0, 1] into T intervals uniformly and define
f + (x) as






T f dTTxe
−t
dT
xe
2

,
f + (x) , f (x) + 

 T −f
2−t
T


(31)
where t ∈ N. Note that f + ( Ti ) =



T f ( Ti )
2−t



−t

2
T

and

+

df (x)
dx

(x)
= dfdx
on( Ti , i+1
T ) where , i = 1, 2, · · · , T . Then,
e
we define f (x):
&
'
T
f
(0)
2−t
,
(32)
fe(0) ,
−t
2
T

dfe(x)
,
dx

(

sgn(f + (x) − fe(x))
df (x)
dx

fe(x) 6= f + (x)
(33)
fe(x) = f + (x).

f + (x) is parallel with f (x) on any given interval ( Ti , i+1
T ]
−t
and is shifted to let f + ( Ti ) be an integral multiple of 2T .

−t
fe( Ti ) is f ( Ti ) rounded up to an integral multiple of 2T .
Meanwhile, fe(x) approaches f (x) with fixed slope whenever they are not equal. An example is shown in Figure 3.

Proposition 4. fe(x) defined above has the following three
properties.
(i)fe(x) is a continuous function with Lipschitz constant 1;


T f ( Ti ) 2−t
(ii) fe( Ti ) =
2−t
T ;
(iii) |fe(x) − f (x)| <

2−t
T ;

Proof. Statement (i) follows the definition directly.
We give a proof for statement (ii) by contradiction and induction. If fe( Ti ) = f + ( Ti ), then fe(x) = f + (x) on ( Ti , i+1
T ].
The proof idea for fe( Ti ) > f + ( Ti ) and fe( Ti ) < f + ( Ti ) are
basically the same thus we present the
 proofof the latter for
T f ( Ti ) 2−t
brevity. We first assume fe( Ti ) =
2−t
T , which is
satisfied by Equation (32) when i = 0. Since fe(x) = f + (x)
+
e
after the first intersection on ( Ti , i+1
T ], if f (x) and f (x)
+ i+1
e i+1
have no intersection on ( Ti , i+1
T ], then f ( T ) < f ( T )
e
(x)
because fe( Ti ) < f + ( Ti ). Meanwhile, we have dfdx
= 1,
and


  Z i+1 e
T
i+1
i
df (x)
fe
= fe
+
dx
i
T
T
dx
T
&
'
T f Ti
2−t
1
=
+
−t
2
T
T
&

'
T f Ti + T1
2−t
(34)
=
2−t
T
&
'
T f i+1
2−t
T
≥
−t
2
T


i+1
≥ f+
.
T

On the Universal Approximability of Quantized ReLU Neural Networks
+ i+1
This contradicts the fact that fe( i+1
T ) < f ( T ). Thus
i
+
fe(x) and f (x)
 intersect
 on (0, T ] and in turn guarantee
i+1
T
f
( T ) 2−t
that fe( i+1
T )=
2−t
T . By induction, we prove that

fe(x) and f + (x) intersect on every interval ( Ti , i+1
T ]. This
implies statement (ii).
Now we prove the statement (iii). Note that we have
−t
0 ≤ fe( Ti ) − f ( Ti ) ≤ 2T by statement (ii). In every
+
e
interval ( Ti , i+1
T ), f (x) = f (x) after the their intersec−t
tion. Therefore we have 0 ≤ |f + (x) − f (x)| ≤ 2T by
Equation (31). Before the intersection, if fe(0) < f + (0),
+
d(fe(x)−f + (x))
(x)
≥ 0. Since dfdx(x) = dfdx
on ( Ti , i+1
dx
T ),
d(fe(x)−f (x))
i
i
e
we have
≥ 0, thus 0 ≤ f ( T ) − f ( T ) ≤
dx
−t
fe(x) − f (x) ≤ f + (x) − f (x) ≤ 2T . If fe( Ti ) ≥ f + ( Ti ),
+

apply the same logic and we obtain 0 ≤ f (x) − f (x) ≤
−t
fe(x)−f (x) ≤ fe( Ti )−f ( Ti ) ≤ 2T . This implies statement
(iii) and concludes the proof.

Table 2. Block configuration for function-dependent structure.
Terms with lower order are omitted.
block
BT
Bδ
Bm
Bf T
BΦ
Bs1
Bs2
Bs3
Bf1∗
Bf2∗
Bf3∗
Bf 00

function
construct 1, 2, · · · , T
construct δ
1
, · · · , m−1
construct m
m
implement f T (x)
implement Φ(x)
scale by T
scale by T1
scale by 1δ
first layer of f ∗
second layer of f ∗
third layer of f ∗
implement f 00 (x)

width
log T
1
t
T
4T
4
1
4
T
3m
m3m
4

depth
log T
1
λ(t λ−1 )
1
λ(t λ−1 )
1
1
log T
log T
log m
1
1
1
1

1
8
t = log m, δ = 8m
, T =  log
1 , and denote the output of

00
the network as f (x), we have |f (x) − f 00 (x)| = |f (x) −
fe(x)| + |fe(x) − f 00 (x)| ≤ .

The approximation network is shown in Figure 4. The sizes
of blocks are given in Table 2 where f T is the uniform linear
interpolation function of f with T − 1 breakpoints, f ∗ is
the sum of the selected cached functions, Φ(x) is a filtering
function.

Figure 4. ReLU implementation of f 00 (x). Illustration only, details
are omitted. For example, arrows between blocks can represent
more than one connection in the network and there are short-cut
connections that allow scaling only part of the inputs.

5.2. Implementation by ReLU Networks
Theorem 2. For any f ∈ F1,1 , given λ distinct weights,
there is a ReLU network with function-dependent structure
that can approximate f with any error  ∈ (0, 1), so that

 1

(i) the depth is O λ log log 1 λ−1 + log 1 ;
(ii) the number of weights is


 1 +1
O λ log log 1 λ−1 + 1
(iii) the number of bits needed to store the network is



 1 +1
O log λ λ log log 1 λ−1 + 1 .
Proof. We use the construction idea from (Yarotsky, 2017)
and the weight construction method described in Section

4.2. By choosing the hyper-parameters as m = 12 log 1 ,

The inputs connections to Bf1∗ and the connections inside Bm have higher order to the number of weights than others.  The total depth is
 1

O λ log log 1 λ−1 + log 1 . The total number of


 1 +1
weights required is O λ log log 1 λ−1 + 1 and the



 1 +1
number of bits is O log λ λ log log 1 λ−1 + 1 .

5.3. Extension to Linear Quantization
Using the same construction method, we obtain the following conclusion: For any f ∈ F1,1 , given weight maximum
precision λ1 , there is a function-dependent ReLU network
that can approximate
 f with any error  ∈ (0, 1) so that
 the
1
depth is O log 1 , the
number
of
weights
is
O
 , and


the number of bits is O

log λ


.

6. Conclusion
In this paper, we have presented an analysis of the representation power of quantized neural networks. The proof for
the universal approximability of quantized ReLU networks
and upper bounds for the number of parameters and storage
size with given approximation accuracy and bit-width are
given for the first time.

On the Universal Approximability of Quantized ReLU Neural Networks

References
Choi, Yoojin, El-Khamy, Mostafa, and Lee, Jungwon. Towards the limit of network quantization. arXiv preprint
arXiv:1612.01543, 2016.
Courbariaux, Matthieu, Bengio, Yoshua, and David, JeanPierre. Binaryconnect: Training deep neural networks
with binary weights during propagations. In Advances in
Neural Information Processing Systems, pp. 3123–3131,
2015.
Denton, Emily L, Zaremba, Wojciech, Bruna, Joan, LeCun,
Yann, and Fergus, Rob. Exploiting linear structure within
convolutional networks for efficient evaluation. In Advances in Neural Information Processing Systems, pp.
1269–1277, 2014.
Gysel, Philipp, Motamedi, Mohammad, and Ghiasi, Soheil.
Hardware-oriented approximation of convolutional neural
networks. arXiv preprint arXiv:1604.03168, 2016.
Han, Song, Mao, Huizi, and Dally, William J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv
preprint arXiv:1510.00149, 2015a.
Han, Song, Pool, Jeff, Tran, John, and Dally, William.
Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems, pp. 1135–1143, 2015b.
Hanin, Boris. Universal function approximation by deep
neural nets with bounded width and relu activations.
arXiv preprint arXiv:1708.02691, 2017.
Hubara, Itay, Courbariaux, Matthieu, Soudry, Daniel, ElYaniv, Ran, and Bengio, Yoshua. Quantized neural networks: Training neural networks with low
precision weights and activations. arXiv preprint
arXiv:1609.07061, 2016.
Iandola, Forrest N, Han, Song, Moskewicz, Matthew W,
Ashraf, Khalid, Dally, William J, and Keutzer, Kurt.
Squeezenet: Alexnet-level accuracy with 50x fewer
parameters and¡ 0.5 mb model size. arXiv preprint
arXiv:1602.07360, 2016.
Langley, P. Crafting papers on machine learning. In Langley,
Pat (ed.), Proceedings of the 17th International Conference on Machine Learning (ICML 2000), pp. 1207–1216,
Stanford, CA, 2000. Morgan Kaufmann.
Leng, Cong, Li, Hao, Zhu, Shenghuo, and Jin, Rong. Extremely low bit neural network: Squeeze the last bit out
with admm. arXiv preprint arXiv:1707.09870, 2017.
Li, Fengfu, Zhang, Bo, and Liu, Bin. Ternary weight networks. arXiv preprint arXiv:1605.04711, 2016.

Li, Hao, De, Soham, Xu, Zheng, Studer, Christoph, Samet,
Hanan, and Goldstein, Tom. Towards a deeper understanding of training quantized neural networks.
Li, Hao, De, Soham, Xu, Zheng, Studer, Christoph, Samet,
Hanan, and Goldstein, Tom. Training quantized nets:
A deeper understanding. In Guyon, I., Luxburg, U. V.,
Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S.,
and Garnett, R. (eds.), Advances in Neural Information
Processing Systems 30, pp. 5807–5817. 2017a.
Li, Hao, De, Soham, Xu, Zheng, Studer, Christoph, Samet,
Hanan, and Goldstein, Tom. Training quantized nets: A
deeper understanding. In Advances in Neural Information
Processing Systems, pp. 5813–5823, 2017b.
Liang, Shiyu and Srikant, R. Why deep neural networks for
function approximation? 2016.
Liu, Baoyuan, Wang, Min, Foroosh, Hassan, Tappen, Marshall, and Pensky, Marianna. Sparse convolutional neural
networks. In Proceedings of the IEEE Conference on
Computer Vision and Pattern Recognition, pp. 806–814,
2015.
Mhaskar, Hrushikesh N and Micchelli, Charles A. Approximation by superposition of sigmoidal and radial basis
functions. Advances in Applied mathematics, 13(3):350–
373, 1992.
Rastegari, Mohammad, Ordonez, Vicente, Redmon, Joseph,
and Farhadi, Ali. Xnor-net: Imagenet classification using binary convolutional neural networks. In European
Conference on Computer Vision, pp. 525–542. Springer,
2016.
Shaham, Uri, Cloninger, Alexander, and Coifman, Ronald R.
Provable approximation properties for deep neural networks. Applied and Computational Harmonic Analysis,
2016.
Shayar, Oran, Levi, Dan, and Fetaya, Ethan. Learning
discrete weights using the local reparameterization trick.
arXiv preprint arXiv:1710.07739, 2017.
Sonoda, Sho and Murata, Noboru. Neural network with
unbounded activation functions is universal approximator.
Applied and Computational Harmonic Analysis, 43(2):
233–268, 2017.
Sze, Vivienne, Chen, Yu-Hsin, Yang, Tien-Ju, and Emer,
Joel. Efficient processing of deep neural networks: A
tutorial and survey. arXiv preprint arXiv:1703.09039,
2017.
Wen, Wei, Wu, Chunpeng, Wang, Yandan, Chen, Yiran,
and Li, Hai. Learning structured sparsity in deep neural
networks. In Advances in Neural Information Processing
Systems, pp. 2074–2082, 2016.

On the Universal Approximability of Quantized ReLU Neural Networks

Xu, Bing, Wang, Naiyan, Chen, Tianqi, and Li, Mu. Empirical evaluation of rectified activations in convolutional
network. arXiv preprint arXiv:1505.00853, 2015.
Yarotsky, Dmitry. Error bounds for approximations with
deep relu networks. Neural Networks, 94:103–114, 2017.
Zhao, Liang, Liao, Siyu, Wang, Yanzhi, Tang, Jian, and
Yuan, Bo. Theoretical properties for neural networks
with weight matrices of low displacement rank. arXiv
preprint arXiv:1703.00144, 2017.
Zhou, Aojun, Yao, Anbang, Guo, Yiwen, Xu, Lin, and Chen,
Yurong. Incremental network quantization: Towards lossless cnns with low-precision weights. arXiv preprint
arXiv:1702.03044, 2017a.
Zhou, Yiren, Moosavi-Dezfooli, Seyed-Mohsen, Cheung, Ngai-Man, and Frossard, Pascal. Adaptive quantization for deep neural network.
arXiv preprint
arXiv:1712.01048, 2017b.
Zhu, Chenzhuo, Han, Song, Mao, Huizi, and Dally,
William J. Trained ternary quantization. arXiv preprint
arXiv:1612.01064, 2016.
Zhuang, Bohan, Shen, Chunhua, Tan, Mingkui, Liu,
Lingqiao, and Reid, Ian. Towards effective lowbitwidth convolutional neural networks. arXiv preprint
arXiv:1711.00205, 2017.

