I wonder how efficiently it can do that compared to other systems.
For example a short iterative function like this:
function(complex c)
complex z=0
int steps=0
while (z<someNumber & steps<someNumber)
z=z^2+c;
steps++;
return steps<someNumber;
Can calculate with extremely high accuracy if a point in the complex plane is in the mandelbrot set or not. I would assume that a NN with the same accuracy would be of enormous size. It would probably have way more neurons then there are atoms in the universe.
Smoothness isn't necessary to prove the result, just continuity.
You do need smoothness to prove a bound on the rate of convergence of the basis representation, and given that the boundary of the Mandelbrot doesn't have a closed form representation (as far as I'm aware), I think that the convergence of the neural network representation would be extremely slow.
The advantage of neural networks is that they can be trained. You can give it a set of inputs and desired outputs, and do gradient descent on it.
Neural networks are essentially like trainable digital circuits. The proof of universality shows that neurons can approximate any kind of logic gate (or any input output mapping, like a lookup table.) A lookup table by itself isn't terribly useful, but you can put them in a series and make arbitrary circuits. And that makes (deep) neural networks strictly more powerful than "shallow" methods.
A very important caveat is the ability to be trained + universality does not mean they can be trained to fit any function to arbitrary precision in finite time.
Well of course not. If you could fit any neural network to any function quickly, you would have super powers. But in practice, local optima do seem to stop being an issue in big neural networks.
Also this article shows a method of how to construct a lookup table from a neural network in linear time. So in the worst case you can just memorize the input to output table, quickly. In the best case you can fit a simple elegant model, which fits the data perfectly with very few parameters. Given unlimited amounts of time to search the parameter space. Real world NNs are somewhere between these two.
That's one of the issues with results from theoretical math- the result is true, but it might not be useful.
As another commenter in the thread talks about, we can get a nearly identical result by using polynomials of extremely large degree, but that doesn't work well, because of overfitting. We could come up with a polynomial that also calculates with arbitrarily high accuracy if a point is in the Mandelbrot set or not, but it might end up being of 10100 degree, which is useless.
For example a short iterative function like this:
Can calculate with extremely high accuracy if a point in the complex plane is in the mandelbrot set or not. I would assume that a NN with the same accuracy would be of enormous size. It would probably have way more neurons then there are atoms in the universe.