5 ms·

Although I'm no expert, isn't this result an incredibly important contribution? This paper claims to prove that: > The current paper proves gradient descent ac

Although I'm no expert, isn't this result an incredibly important contribution? This paper claims to prove that: > The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet). If this variant of gradient descent is able to reach global minima in polynomial time, and if neural networks are proven to approximate any function, then ostensibly this technique could be used to guarantee the lowest error possible in approximating any function. This seems incredibly important. Can someone correct my reading of the abstract?

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 ago
  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).
hooloovoo_zoo 8y ago
Well, without reading the whole paper, two important things strike me. 1. Zero training loss is impossible in most networks because the last layer can only reach the targets asymptotically. 2. Zero training loss means nothing from a practical standpoint. We've had algorithms capable of this for a long time (knn [k=1], decision trees etc.).
- cosmic_ape 8y ago
  Yeah. And they require that the number of parameters grows at least polynomially with the size of input. In this regime, we also have another algorithm capable of zero loss -- the linear regression!
- skeptic_69 8y ago
  1. people overfit the baby datasets to zero training loss (MNIST) all the time. maybe you meant a "hard" dataset. 2. You clearly have no idea what you are talking about. This paper is trying to argue a bit about why neural networks generalize well by showing with math that a nn with some of their conditions converges to the zero training loss. It isn't remotely meant to be practical. IT IS A THEORETICAL PAPER. And comparing it to nearest neighbors of 1 is so so so so so silly it isn't even wrong. edit. #1 is actually an entire research direction in the theory of machine learning fyi. It is possible to get neural networks that massively overfit but still generalize (which Is weird). https://arxiv.org/pdf/1611.03530.pdf https://arxiv.org/pdf/1611.03530.pdf That paper was really famous. It showed you can get zero training loss on data when you replace the labels with random noise. edit 2: I am sorry to be harsh. It is just hard to read such arrant nonsense.
  - nilkn 8y ago
    I don't see how you really addressed the concerns. You say that the paper is "trying to argue a bit about why neural networks generalize well," but in fact I don't see anything in this paper about generalization or test error. The first line of future research under section seven is to look into test error instead of training error: "The current paper focuses on the train loss, but does not address the test loss. It would be an important problem to show that gradient descent can also find solutions of low test loss. In particular, existing work only demonstrate that gradient descent works under the same situations as kernel methods and random feature methods [Daniely, 2017, Li and Liang, 2018]."
    - skeptic_69 8y ago
      have you heard of something called ERM? uniform convergence? The typical way of showing generalization in ML is to show that if we have some low or zero error solution on the test data-set, for a large enough dataset, with high probability, the error on our training data set is close to the error on the real and unknown distribution. The first step which is basically "find a low error hypothesis on the training data" is called the ERM principle. In practice we observe stochastic gradient descent works pretty well in solving the ERM problem and the solutions generalize well (perform well when deployed). This is very weird since neural networks are really weird objects with very non-linear and non-convex behavior and gradient descent shouldn't play well with weird bumps and curves and valleys. People want to show mathematically that stochastic gradient descent does well on neural networks. This paper claims gradient descent is effective at minimizing quadratic loss on the training data. If we could improve the results to show that on the true distribution we also have low loss-that might be compelling that gradient descent converges to the minimum error solution. None of this explicitly stated since this is a well understood part of basic literature in learning theory. Showing an algorithm can do erm on the hypothesis class is the first and (easier ) part of showing generalization. If you want a good reference that explains this in a more coherent way I recommend looking at the first 4 chapters of understanding machine learning theory by Shai-Shalev Schwartz. If you still think the comments I was responding to are not totally incoherent-take note of the fact that the very first sentence in the paper is "One of the mysteries in deep learning is random initialized first order methods like gradient descent achieve zero training loss"
cosmic_ape 8y ago
This is not necessarily a trivial fact, but I wouldn't call it incredible. It says a net trained with gradient descent can fit the input perfectly if its much larger than the input. But this says nothing about generalization, i.e. performance on test set -- which is what we really want.
- iandanforth 8y ago
  Importantly not SGD, just GD.
  - cosmic_ape 8y ago
    you're right, fixed.
jey 8y ago
I interpret it as saying: "non-convexity ain't no big deal in this context", and this is the latest contribution in a line of other "no spurious local minima" machine learning theory research. It's interesting for showing that it applies to a rather complex model like ResNet.
- cosmic_ape 8y ago
  Its quite important that its not so much about "non-convexity", its more about "random initialization". All these results, and there are others, more sophisticated, basically say that after random init everything is already good, and the gradient descent just has to train the highest layer, without screwing up the previous ones. They are all pretty naive that way.

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 ago
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).

hooloovoo_zoo 8y ago

Well, without reading the whole paper, two important things strike me. 1. Zero training loss is impossible in most networks because the last layer can only reach the targets asymptotically. 2. Zero training loss means nothing from a practical standpoint. We've had algorithms capable of this for a long time (knn [k=1], decision trees etc.).

cosmic_ape 8y ago
Yeah. And they require that the number of parameters grows at least polynomially with the size of input. In this regime, we also have another algorithm capable of zero loss -- the linear regression!
skeptic_69 8y ago
1. people overfit the baby datasets to zero training loss (MNIST) all the time. maybe you meant a "hard" dataset. 2. You clearly have no idea what you are talking about. This paper is trying to argue a bit about why neural networks generalize well by showing with math that a nn with some of their conditions converges to the zero training loss. It isn't remotely meant to be practical. IT IS A THEORETICAL PAPER. And comparing it to nearest neighbors of 1 is so so so so so silly it isn't even wrong. edit. #1 is actually an entire research direction in the theory of machine learning fyi. It is possible to get neural networks that massively overfit but still generalize (which Is weird). https://arxiv.org/pdf/1611.03530.pdf https://arxiv.org/pdf/1611.03530.pdf That paper was really famous. It showed you can get zero training loss on data when you replace the labels with random noise. edit 2: I am sorry to be harsh. It is just hard to read such arrant nonsense.
- nilkn 8y ago
  I don't see how you really addressed the concerns. You say that the paper is "trying to argue a bit about why neural networks generalize well," but in fact I don't see anything in this paper about generalization or test error. The first line of future research under section seven is to look into test error instead of training error: "The current paper focuses on the train loss, but does not address the test loss. It would be an important problem to show that gradient descent can also find solutions of low test loss. In particular, existing work only demonstrate that gradient descent works under the same situations as kernel methods and random feature methods [Daniely, 2017, Li and Liang, 2018]."
  - skeptic_69 8y ago
    have you heard of something called ERM? uniform convergence? The typical way of showing generalization in ML is to show that if we have some low or zero error solution on the test data-set, for a large enough dataset, with high probability, the error on our training data set is close to the error on the real and unknown distribution. The first step which is basically "find a low error hypothesis on the training data" is called the ERM principle. In practice we observe stochastic gradient descent works pretty well in solving the ERM problem and the solutions generalize well (perform well when deployed). This is very weird since neural networks are really weird objects with very non-linear and non-convex behavior and gradient descent shouldn't play well with weird bumps and curves and valleys. People want to show mathematically that stochastic gradient descent does well on neural networks. This paper claims gradient descent is effective at minimizing quadratic loss on the training data. If we could improve the results to show that on the true distribution we also have low loss-that might be compelling that gradient descent converges to the minimum error solution. None of this explicitly stated since this is a well understood part of basic literature in learning theory. Showing an algorithm can do erm on the hypothesis class is the first and (easier ) part of showing generalization. If you want a good reference that explains this in a more coherent way I recommend looking at the first 4 chapters of understanding machine learning theory by Shai-Shalev Schwartz. If you still think the comments I was responding to are not totally incoherent-take note of the fact that the very first sentence in the paper is "One of the mysteries in deep learning is random initialized first order methods like gradient descent achieve zero training loss"

cosmic_ape 8y ago

This is not necessarily a trivial fact, but I wouldn't call it incredible. It says a net trained with gradient descent can fit the input perfectly if its much larger than the input. But this says nothing about generalization, i.e. performance on test set -- which is what we really want.

iandanforth 8y ago
Importantly not SGD, just GD.
- cosmic_ape 8y ago
  you're right, fixed.

jey 8y ago

I interpret it as saying: "non-convexity ain't no big deal in this context", and this is the latest contribution in a line of other "no spurious local minima" machine learning theory research. It's interesting for showing that it applies to a rather complex model like ResNet.

cosmic_ape 8y ago
Its quite important that its not so much about "non-convexity", its more about "random initialization". All these results, and there are others, more sophisticated, basically say that after random init everything is already good, and the gradient descent just has to train the highest layer, without screwing up the previous ones. They are all pretty naive that way.