# On the Universal Approximability and Complexity Bounds of Quantized ReLU Neural Networks

arXiv: https://arxiv.org/abs/1802.03646 · HTML: https://mlsanity.com/paper/1802.03646/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2018.

## Built on by (most cited first, 12 of 12)

- [Demystifying and Generalizing BinaryConnect](https://mlsanity.com/paper/2110.13220/) (2021)
- [Approximation speed of quantized vs. unquantized ReLU neural networks and beyond](https://mlsanity.com/paper/2205.11874/) (2022)
- [Why Quantization Improves Generalization: NTK of Binary Weight Neural Networks](https://mlsanity.com/paper/2206.05916/) (2022)
- [Expressive Power of ReLU and Step Networks under Floating-Point Operations](https://mlsanity.com/paper/2401.15121/) (2024)
- [On Expressive Power of Quantized Neural Networks under Fixed-Point Arithmetic](https://mlsanity.com/paper/2409.00297/) (2024)
- [High-Dimensional Learning Dynamics of Quantized Models with Straight-Through Estimator](https://mlsanity.com/paper/2510.10693/) (2025)
- [Seeking Interpretability and Explainability in Binary Activated Neural Networks](https://mlsanity.com/paper/2209.03450/) (2022)
- [Effect of Weight Quantization on Learning Models by Typical Case Analysis](https://mlsanity.com/paper/2401.17269/) (2024)
- [Universal Approximation Theorems of Fully Connected Binarized Neural Networks](https://mlsanity.com/paper/2102.02631/) (2021)
- [Expressive Power of Floating-Point Neural Networks with Arbitrary Reduction Orders and Inexact Activation Implementations](https://mlsanity.com/paper/2605.28704/) (2026)
- [Closing the Theory-Practice Gap in Spiking Transformers via Effective Dimension](https://mlsanity.com/paper/2604.15769/) (2026)
- [On the Expressive Power of Weight Quantization in Large Language Models](https://mlsanity.com/paper/2606.22249/) (2026)

## Abstract (arXiv)

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 on a wide class of functions. Then we provide upper bounds on the number of weights and the memory size for a given approximation error bound and the bit-width of weights for function-independent and function-dependent structures. Our results reveal that, to attain an approximation error bound of ε, the number of weights needed by a quantized network is no more than Oleft(log5(1/ε)right) times that of an unquantized network. This overhead is of much lower order than the lower bound of the number of weights needed for the error bound, supporting the empirical success of various quantization techniques. To the best of our knowledge, this is the first in-depth study on the complexity bounds of quantized neural networks.