Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Gradient Descent Finds Global Minima of Deep Neural Networks

arxiv.org

Post reply on HN
Print view View original

21–30 of 60 posts

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#21

Post by simonhughes22 »

RandyRanderson wrote: post #16
ramgorur wrote: post #13

I did not understand the paper very well. 1. It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex. 2. The only way to guarantee is to start the gradient descent from different points in the search space or try with different step sizes if the algorithm only starts from the same point in the search space. 3. Also does "achieving zero training lo…

FF NNs of even one hidden layer are universal approximators. That is, they do find the global min. What this doesn't tell you is that it's likely a huge graph and will take a looong time to optimize for even trivial data sets. There's lots of proofs around. That's why SGD is used, and for only a small subset of training points at a time. Re 2: No. Re 3: Yes.

They are universal approximators, although the term approximator means there's an upper bound on the accuracy of how well they emulate a given function (based on the size of the network). However, just because they are universal approximators doesn't mean that you can automatically infer the optimal number of connections and weight for each of those connections in order to minimize the loss over some dataset (derived from some function). Being able to be a universal approximator does not imply you can automatically learn the best approximation of a given function. It's the difference between being capable of learning something, and having learned it. If that makes sense.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#22

Post by nshm »

ramgorur wrote: post #13

I did not understand the paper very well. 1. It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex. 2. The only way to guarantee is to start the gradient descent from different points in the search space or try with different step sizes if the algorithm only starts from the same point in the search space. 3. Also does "achieving zero training lo…

The title of the paper is really misleading. The comments here are even more misleading. The key is their theorem where they say "with high probably over random initialization". They initialize many times and sometimes it converges. Single initialization can stuck in local minimum of course.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#24

Post by nilkn »

skeptic_69 wrote: post #19
hooloovoo_zoo wrote: post #5

Earlier quoted context omitted.

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

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 co…

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]."

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#25

Post by LolWolf »

ramgorur wrote: post #13

I did not understand the paper very well. 1. It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex. 2. The only way to guarantee is to start the gradient descent from different points in the search space or try with different step sizes if the algorithm only starts from the same point in the search space. 3. Also does "achieving zero training lo…

1. > It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex.

This is false. See, e.g., [0][1].

2. I'm not really sure what the question is here.

3. If your loss is bounded from below (it is a square norm) by 0 and you achieve 0 loss, this means that 0 is a global optimum, since, by definition, no other objective value can be smaller than this number.

---

[0] Theorem A.2 in Udell's Generalized Low-Rank models paper https://arxiv.org/pdf/1410.0342.pdf

[1] B&V Convex Optimization (https://web.stanford.edu/~boyd/cvxbook/), Appendix B.1. In fact, I can't find the reference right now, but you can easily prove that GD with an appropriate step-size converges to a global optimum on this problem when initialized at (0,0), even though the problem is non-convex.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#26

Post by currymj »

orf wrote: post #23

> One of the mysteries in deep learning is random initialized first order methods like gradient descent achieve zero training loss, even if the labels are arbitrary Can someone expand on this? I've never heard of this before, at least not in the general case.

The paper “Understanding Deep Learning Requires Rethinking Generalization” was where this was first pointed out, I think.

They shuffled the labels on their datasets, so there can’t possibly be anything to learn, yet got zero training loss, meaning the network must be severely overfitting. Yet the same network trained with the actual labels shows quite good generalization. So the usual intuition about overfitting and the bias-variance tradeoff doesn’t seem to apply.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#27

Post by [deleted] »

LolWolf wrote: post #25
ramgorur wrote: post #13

I did not understand the paper very well. 1. It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex. 2. The only way to guarantee is to start the gradient descent from different points in the search space or try with different step sizes if the algorithm only starts from the same point in the search space. 3. Also does "achieving zero training lo…

1. > It's theoretically impossible to guarantee a convergence to global optima using gradient descent if the function is non-convex. This is false. See, e.g., [0][1]. 2. I'm not really sure what the question is here. 3. If your loss is bounded from below (it is a square norm) by 0 and you achieve 0 loss, this means that 0 is a global optimum, since, by definition, no other objective value can be smaller than this num…

[deleted]

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#28

Post by LolWolf »

Xcelerate wrote: post #4
brentjanderson wrote: post #3

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…

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.

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

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#29

Post by LolWolf »

ramgorur wrote: post #20
heyitsguay wrote: post #18

Earlier quoted context omitted.

Convex functions aren't the only functions with a single local (and global) minimum - consider sqrt(|x|) for a simple 1d example.

Yes, that's true. But in optimization domain the concept of "convexity" is understood in terms of set, not always from the 2nd derivative of a function. Because you might have search spaces where you are not able to differentiate the objective function at all. In those cases the "convex" means a "convex set".

Sure: you can define convexity for a function that is equivalent to the 2nd derivative definition in the case that the function is twice-differentiable, using only the definition of the convexity of a set.

Define the epigraph of a function to be the set given by {(x, t) | f(x) ≤ t}. Then, we say f is a convex function iff the epigraph is a convex set.

This is equivalent (exercise for the reader!) to the usual definition that a function f is convex iff f((1-t)x + ty) ≤ (1-t)f(x) + tf(y), for all 0 ≤ t ≤ 1, with x, y in the domain of f.

Note that neither of these two definitions require differentiability (or twice-differentiability), but the definitions are equivalent in this case.[0]

---

[0] For proofs of all of these statements see B&V's Convex Optimization.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#30

Post by skeptic_69 »

nilkn wrote: post #24
skeptic_69 wrote: post #19

Earlier quoted context omitted.

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 co…

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…

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"

Post reply on HN