# What is the number of neurons required to approximate a polynomial of degree n?

I learned about the universal approximation theorem from this guide. It states that a network even with a single hidden layer can approximate any function within some bound, given a sufficient number of neurons. Or mathematically, $${|g(x)−f(x)|< \epsilon}$$, where $${g(x)}$$ is the approximation, $${f(x)}$$ is the target function and is $$\epsilon$$ is an arbitrary bound.

A polynomial of degree $$n$$ has at maximum $$n-1$$ turning points (where the derivative of the polynomial changes sign). With each new turning point, the approximation seems to become more complex.

I'm not necessarily looking for a formula, but I'd like to get a general idea on how to figure out the sufficient number of neurons is for a reasonable approximation of a polynomial with a single layer of the neural network (you may consider "reasonable" to be $$\epsilon = 0.0001$$). To ask in other words, how would adding one more neuron affect the model's ability to express a polynomial?

• That's actually a pretty hard problem. Only an expert can answer this (or maybe not), the representational capacity of Neural Net is a pretty hard problem to solve, but I think a scientist named Peter Bartlett has some work on this stuff. – DuttaA Jan 2 at 18:58
• If the network has one hidden layer, there are papers like A closer look at the approximation capabilities of neural networks (Kai Fong Ernest Chong) saying "... given approximation threshold $\epsilon$ ... if $X$ in $\mathbb R^n$ is compact, then a neural network with $n$ input units, $m$ output units, and a single hidden layer with $\binom{n+d}{d}$ hidden units (independent of $m$ and $\epsilon$), can uniformly approximate any polynomial function $f:X \to \mathbb R^m$ whose total degree is at most $d$ for each of its $m$ coordinate functions." – Vepir Jan 4 at 15:38
• @Vepir Feel free to attempt to write a formal answer below, even though it only partially answers the question. – nbro Jan 5 at 0:37