Comment by fluffything | Hacker News Reader

Comment by fluffything | Hacker News Reader

So can any lagrange polynomial, Fourier series, ...

The real question is whether the approximation is a good one:

- can you prove error bounds ?

- can you bound the maximum error?

- is it efficient ? (low storage, low computational effort)

- is it fast to build? (low computational effort of coefficients)

- derivatives: how well does it approximate gradients, what's the error on the gradient, is it bounded? can one bound it, how fast can one evaluate them, etc.

- there are many other interesting properties: https://en.wikipedia.org/wiki/Approximation_theory

From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function. If you were to make an analogy with sorting algorithms, they would be worse than bogosort. There are no error bounds, you can't bound the maximum error, computing their coefficients is very slow (training, needs GPUs, ...), they require a lot of storage and computational power to evaluate, ...

> From pretty much every single aspect of approximation theory, neural nets are one of the worst methods to approximate a continuous function.

What about scalability? I don't know of many approximation methods that can routinely work with the amount of coefficients, datapoints, dimensionality of data etc. that neural networks are coping with. (Though AIUI compressed sensing methods might come close; compressed sensing can be seen as a kind of approximation as well.)

Yes, neural nets are successful is in large part because they are asymptotically more efficient than other models. Training time is O(n) with O(1) memory, and prediction time is O(1) with O(1) memory. Compare to e.g. kernel methods, which have nicer theory behind them, but kernel least squares is O(n^3) with O(n^2) memory to fit and O(n^2) with O(n^2) memory to predict. The coefficients are larger for neural nets, but if your data are big enough, the asymptotics win out.

Training time for a NN is not O(n), it is a function of the dataset size and the complexity of NN to approximate a given function. Similarly the memory cost is also a function of the size of the network required. The same is true for prediction time and memory costs. If you data are big enough, all the O(1) lies we tell ourselves start breaking down.

By this logic, (naive) matrix multiplication is not O(n^3) because it is a function of the precision required. The size of the neural network required to approximate a given function to within some epsilon does not change with the dataset size.

Do you have a proof that the neural network approximates the function within some epsilon for all possible inputs within some range ?

The universal approximation theorem guarantees that a finite-width neural network that approximates the function to within some epsilon exists. But, regardless of the approximation method, there is no way to certify that a given approximation method is sufficient for an arbitrary continuous function given only a finite number of samples (i.e., without oracle knowledge of the underlying function), which is the typical situation where neural networks are applied. I can construct a continuous function that has an arbitrary (but non-infinite) number of peaks in an arbitrary interval. Thus, any method that approximates the function within some epsilon for all possible inputs within that arbitrary interval must encode an arbitrary amount of information. I can also ensure that whatever the number of samples is, it's not enough to properly approximate the function.

People routinely use lagrange polynomials, fourier approximations, etc. with 10^10 or more coefficients and many more data-points. That's often orders of magnitude larger than what training most neural nets for AI need.

Reply on news.ycombinator.com