{
  "id": "2112.09181",
  "version": "v2",
  "published": "2021-12-16T20:10:56.000Z",
  "updated": "2023-03-16T12:57:21.000Z",
  "title": "Approximation of functions with one-bit neural networks",
  "authors": [
    "C. Sinan Güntürk",
    "Weilin Li"
  ],
  "comment": "45 pages, 7 figures, significant changes and additions",
  "categories": [
    "cs.LG",
    "cs.IT",
    "cs.NA",
    "math.IT",
    "math.NA"
  ],
  "abstract": "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 $\\pm a$ for some fixed $a\\not=0$. One of our main theorems shows that for any $f\\in C^s([0,1]^d)$ with $\\|f\\|_\\infty<1$ and error $\\varepsilon$, there is a $f_{NN}$ such that $|f(\\boldsymbol{x})-f_{NN}(\\boldsymbol{x})|\\leq \\varepsilon$ for all $\\boldsymbol{x}$ away from the boundary of $[0,1]^d$, and $f_{NN}$ is either implementable by a $\\{\\pm 1\\}$ quadratic network with $O(\\varepsilon^{-2d/s})$ parameters or a $\\{\\pm \\frac 1 2 \\}$ ReLU network with $O(\\varepsilon^{-2d/s}\\log (1/\\varepsilon))$ parameters, as $\\varepsilon\\to0$. 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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2023-03-16T12:57:21.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "one-bit neural networks",
      "parameters",
      "iterated multivariate bernstein operators",
      "relu neural networks",
      "appropriately chosen real numbers"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 45,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}