Re:Gradient Descent Finds Global Minima of Deep Neural Networks
by Xcelerate on Monday November 12, 2018 @03:14PM
(#18435318)
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.
[ Parent
| on HN ]
Re:Gradient Descent Finds Global Minima of Deep Neural Networks
by LolWolf on Monday November 12, 2018 @06:49PM
(#18437067)
Re: "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).