Approximation of functions with one-bit neural networks

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.