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

41–50 of 60 posts

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#41

Post by elcomet »

currymj wrote: post #26
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…

This seems quite intuitive to me:

When you have nothing to learn, you need to memorize the data. But when there is structure, it is easier to memorize the structure, so the network will learn this first (and will memorize after).

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#42

Post by srean »

TTPrograms wrote: post #33
ramgorur wrote: post #20

Earlier quoted context omitted.

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

When talking about "convex optimization" one nearly always means that both the function and the domain are convex.

No need to define 'convex optimization' here, that follows from the definition of a convex function: F(ax + (1-a)y) <= aF(x) + (1-a) F(y) for 0<=a<=1 and x,y in domain of F. For the inequality to be satisfied ax + (1-a)y has to be in the domain. That mean the domain is convex.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#43

Post by srean »

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.

I dont think you understand what universal approximation means. It means there are parameter settings that would reduce the approximation as much as you want. Its an existential property. It does not mean that those parameters can be found.

Anyway this universal property of neural networks get a lot of airtime and people go gaga over it. Its a complete red herring. Its not the first example of a universal approximation and not the last. There is no scarcity of universal approximators. There was no such scarcity even 100s of years ago. The explanation of the success of DNNs lie elsewhere.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#44

Post by srean »

elcomet wrote: post #41
currymj wrote: post #26

Earlier quoted context omitted.

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…

This seems quite intuitive to me: When you have nothing to learn, you need to memorize the data. But when there is structure, it is easier to memorize the structure, so the network will learn this first (and will memorize after).

But thats the crux of the question: why and how does it not just memorize when we know it can do so easily ?

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#45

Post by DoctorOetker »

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…

that reference you can't find right now seems rather pertinent?

I think the OP intended and should have written:

"It's theoretically impossible to guarantee a convergence to global optima using gradient descent for an arbitrary non-convex function."

For example consider the function f(x)=sin^2(pi * x)+sin^2(pi * N/x) this function has multiple global minima at the divisors of N, where it is f(x)==0, if x or N/x is non-integer, it is guaranteed to be positive...

I am not taking a stance on if gradient descent does or does not guarantee finding global minima and is thus able to factorize cryptographic grade RSA products of primes, but the claim does appear to imply it.

Edit: the multiply symbols changed some cursive

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#46

Post by DoctorOetker »

nshm wrote: post #22
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.

but then there is very little of interest: (assuming enough smoothness and Lipschitz continuity) one expects every global minima to have a convex neighbourhood such that gradient descent starting within the neighbourhood reaches the global minimum. The initialize many times and sometimes it converges is just saying the obvious "there exist initial positions for which GD succeeds in finding a global minima"... is my interpretation correct?

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#47

Post by nshm »

DoctorOetker wrote: post #46
nshm wrote: post #22

Earlier quoted context omitted.

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.

but then there is very little of interest: (assuming enough smoothness and Lipschitz continuity) one expects every global minima to have a convex neighbourhood such that gradient descent starting within the neighbourhood reaches the global minimum. The initialize many times and sometimes it converges is just saying the obvious "there exist initial positions for which GD succeeds in finding a global minima"... is my i…

The contribution of the paper is the estimation of the convergence speed and number of parameters in neural network, that seems a valuable point.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#48

Post by DoctorOetker »

nshm wrote: post #47
DoctorOetker wrote: post #46

Earlier quoted context omitted.

but then there is very little of interest: (assuming enough smoothness and Lipschitz continuity) one expects every global minima to have a convex neighbourhood such that gradient descent starting within the neighbourhood reaches the global minimum. The initialize many times and sometimes it converges is just saying the obvious "there exist initial positions for which GD succeeds in finding a global minima"... is my i…

The contribution of the paper is the estimation of the convergence speed and number of parameters in neural network, that seems a valuable point.

The paper states for the main result:

>In this section, we show gradient descent with a constant positive step size converges to the global minimum with a linear rate.

This is rather ambiguous: it sounds like it guarantees "it WILL converge to the global minimum, btw at a linear rate" but I suspect they are really saying "IF it converges to the global minimum, THEN it will converge at a linear rate" in a way to purpousefully sound like the first statement.

could you comment on if GD does or does not find the global minimum of the integer factorization cost function in the following comment?

https://news.ycombinator.com/item?id=18439287

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#49

Post by elcomet »

srean wrote: post #44
elcomet wrote: post #41

Earlier quoted context omitted.

This seems quite intuitive to me: When you have nothing to learn, you need to memorize the data. But when there is structure, it is easier to memorize the structure, so the network will learn this first (and will memorize after).

But thats the crux of the question: why and how does it not just memorize when we know it can do so easily ?

Maybe just because it's easier to find patterns than to memorize (if you have a lot of data).

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#50

Post by currymj »

elcomet wrote: post #49
srean wrote: post #44

Earlier quoted context omitted.

But thats the crux of the question: why and how does it not just memorize when we know it can do so easily ?

Maybe just because it's easier to find patterns than to memorize (if you have a lot of data).

That sounds like it’s probably right to me. But so do lots of things that turn out to be wrong. I wish we had a better grasp of what is happening, not just plausible stories. I’m already sick of doing alchemical tinkering to find a model that works.
Post reply on HN