J. Watson Research Center\
    `{yding5,jliu16,yshi4}@nd.edu, jinjun@us.ibm.com`\
bibliography:
- 'iclr2019\_conference.bib'
title: |
    On the Universal Approximability and\
    Complexity Bounds of Quantized ReLU\
    Neural Networks
---

Introduction {#sec:intro}
============

Various deep neural networks deliver state-of-the-art performance on many tasks such as object recognition and natural language processing using new learning strategies and architectures [@chen2017learning; @he2016identity; @kumar2016ask; @ioffe2015batch; @vaswani2017attention]. 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 with the associated expensive computation and memory consumption make edge intelligence even more challenging [@cheng2018recent; @sandler2018inverted].

In response, as will be more detailed in Section \[sec:related\], 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 [@choi2016towards]. The number of weights can be reduced by pruning [@han2015learning], weight sparsifying [@liu2015sparse], structured sparsity learning [@wen2016learning] and low rank approximation [@denton2014exploiting]. The bit-width is reduced by 