# Approximation of functions with one-bit neural networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 41 references that are in the map.
- First posted on arXiv 16 Dec 2021.

## Builds on (most cited first, 12 of 12)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Deep Network Approximation for Smooth Functions](https://mlsanity.com/paper/2001.03040/) (2020)
- [An Analysis of Deep Neural Network Models for Practical Applications](https://mlsanity.com/paper/1605.07678/) (2016)
- [Optimal Approximation with Sparsely Connected Deep Neural Networks](https://mlsanity.com/paper/1705.01714/) (2017)
- [A Survey on Methods and Theories of Quantized Neural Networks](https://mlsanity.com/paper/1808.04752/) (2018)
- [Provable approximation properties for deep neural networks](https://mlsanity.com/paper/1509.07385/) (2015)
- [Approximation spaces of deep neural networks](https://mlsanity.com/paper/1905.01208/) (2019)
- [Nonlinear Approximation and (Deep) ReLU Networks](https://mlsanity.com/paper/1905.02199/) (2019)
- [A Greedy Algorithm for Quantizing Neural Networks](https://mlsanity.com/paper/2010.15979/) (2020)
- [Stochastic Markov Gradient Descent and Training Low-Bit Neural Networks](https://mlsanity.com/paper/2008.11117/) (2020)

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

- [A simple approach for quantizing neural networks](https://mlsanity.com/paper/2209.03487/) (2022)
- [AI in Space for Scientific Missions: Strategies for Minimizing Neural-Network Model Upload](https://mlsanity.com/paper/2406.14297/) (2024)
- [Frame Quantization of Neural Networks](https://mlsanity.com/paper/2404.08131/) (2024)
- [Beyond Discreteness: Sample Complexity Analysis of Straight-Through Estimator for 1-bit Quantization](https://mlsanity.com/paper/2505.18113/) (2025)
- [Low-Bit Quantization of Bandlimited Graph Signals via Iterative Methods](https://mlsanity.com/paper/2601.18782/) (2026)

## Abstract (arXiv)

The celebrated universal approximation theorems for neural networks roughly state that any reasonable function can be arbitrarily well-approximated by a network whose parameters are appropriately chosen real numbers. This paper examines the approximation capabilities of one-bit neural networks -- those whose nonzero parameters are ± a for some fixed anot=0. One of our main theorems shows that for any f∈ Cs([0,1]d) with |f|_∞<1 and error varepsilon, there is a fNN such that |f(boldsymbolx)-fNN(boldsymbolx)|≤ varepsilon for all boldsymbolx away from the boundary of [0,1]d, and fNN is either implementable by a ± 1 quadratic network with O(varepsilon-2d/s) parameters or a ± frac 1 2  ReLU network with O(varepsilon-2d/slog (1/varepsilon)) parameters, as varepsilon→0. We establish new approximation results for iterated multivariate Bernstein operators, error estimates for noise-shaping quantization on the Bernstein basis, and novel implementation of the Bernstein polynomials by one-bit quadratic and ReLU neural networks.