3 ms·
The paper claims to reach the global minima of a given neural network in polynomial time. The time complexity of constructing a neural network that approximates
by Xcelerate 8y ago
The paper claims to reach the global minima of a given neural network in polynomial time. The time complexity of constructing a neural network that approximates any function is an entirely different matter. I’m not even sure how one would begin to approximate a highly algorithmic process (e.g., a hash function) using a neural network.
- LolWolf 8y agoRe: "I’m not even sure how one would begin to approximate a highly algorithmic process (e.g., a hash function) using a neural network" You build the circuit corresponding to the function and map it to an NN. Can this be discovered easily via GD? Absolutely no clue (though this paper says "yes"), but is it possible to approximate it? Yes, you can nail it exactly in a polynomial number of layers (if the algorithm takes poly-space, which is a necessary condition for it to run in poly-time).