3 ms·

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 p

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.

blamestross 7y ago
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.
- simonster 7y ago
  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.
  - fluffything 7y ago
    Do you have a proof that the neural network approximates the function within some epsilon for all possible inputs within some range ?
    - simonster 7y ago
      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.

blamestross 7y ago

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.

simonster 7y ago
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.
- fluffything 7y ago
  Do you have a proof that the neural network approximates the function within some epsilon for all possible inputs within some range ?
  - simonster 7y ago
    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.