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

31–40 of 60 posts

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#31

Post by hooloovoo_zoo »

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…

This is an intriguingly aggressive comment.

1. No, it's impossible. Actually, the theorems in this paper do not claim to reach zero loss either, as they're all inequalities on the size of the loss. The paper you cite refers to converging to zero loss, as do you in point 2. Perhaps you're referring to error, which is not the loss that is directly optimized.

2. This paper certainly isn't talking about generalization. It doesn't appear to be mentioned once. Your other paper is talking about generalization. The parent asked if this paper is super important. I gave a reason why it isn't super important for most people.

3. Massively overfitting is antithetical to generalizing. Overfitting means fitting to the extent that you're generalizing less well.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#32

Post by skeptic_69 »

hooloovoo_zoo wrote: post #31
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…

This is an intriguingly aggressive comment. 1. No, it's impossible. Actually, the theorems in this paper do not claim to reach zero loss either, as they're all inequalities on the size of the loss. The paper you cite refers to converging to zero loss, as do you in point 2. Perhaps you're referring to error, which is not the loss that is directly optimized. 2. This paper certainly isn't talking about generalization. I…

1.mmmmmmmmm ok I am willing to accept you meant the quadratic loss instead of 0-1 error. that seems reasonable.

2. this is paper is centered in a research thrust that IS focused on generalization. see my below comment.

I don't know who most people are but this paper COULD be important in understanding why stochastic gradient works well in practice.

Personally I doubt it very much.

3. massively overfitting to the training dataset BUT generalizing well is a real phenomenon and yes it is very weird. happens in deep nets and i believe adaboost. i.e. continuing to train after you have zero 0-1 loss. I agree this is a weird way to communicate this idea but that is what the community uses.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#33

Post by TTPrograms »

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

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

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#34

Post by trevyn »

iandanforth wrote: post #10

My hope is that as these bounds are refined we can start to do BotE calculations such as, "I have 50k training images of 512x512x3 and 1k classes, this means I'll need a Convolutional Resnet of at most 12 layers and 12M params to fit the training data so let's start at half that." Rather than today which is 'let's use resnet 101 and see if that works.'

You have to include some sense of what the classes encode for this to have meaning — for example, “pictures of correct mathematical proofs” vs “pictures of incorrect mathematical proofs” is going to require a much different architecture than “pictures of squares” vs “pictures of circles”.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#35

Post by iandanforth »

trevyn wrote: post #34
iandanforth wrote: post #10

My hope is that as these bounds are refined we can start to do BotE calculations such as, "I have 50k training images of 512x512x3 and 1k classes, this means I'll need a Convolutional Resnet of at most 12 layers and 12M params to fit the training data so let's start at half that." Rather than today which is 'let's use resnet 101 and see if that works.'

You have to include some sense of what the classes encode for this to have meaning — for example, “pictures of correct mathematical proofs” vs “pictures of incorrect mathematical proofs” is going to require a much different architecture than “pictures of squares” vs “pictures of circles”.

Interesting classes! To use the heuristic Andrew Ng proposed if a human could tell the difference between correct and incorrect proofs in 1 second then this problem is likely no harder than most image recognition problems. If, instead, we're talking about analysis that requires symbolic manipulation then we're pretty far outside of the current capabilities of convolutional/residual/fully connected nets for which the paper provides bounds.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#36

Post by fwilliams »

It's worth noting that the primary result of this paper has only to do with the error on the training data under empirical risk minimization. Zero training error =/= a model that generalizes. For any optimization problem, you can always add enough parameters to achieve zero error on a problem over a finite training set (imagine introducing enough variables to fully memorize the map from inputs to labels).

The major contribution of the work is showing that ResNet needs a number of parameters which is polynomial in the dataset size to converge to a global optimum in contrast to traditional neural nets which require an exponential number of parameters.

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#37

Post by sytelus »

fwilliams wrote: post #36

It's worth noting that the primary result of this paper has only to do with the error on the training data under empirical risk minimization. Zero training error =/= a model that generalizes. For any optimization problem, you can always add enough parameters to achieve zero error on a problem over a finite training set (imagine introducing enough variables to fully memorize the map from inputs to labels). The major c…

There is bit of difference between fitting dataset to some convenient parameterized function vs finding global minima of non-convex function. Also, paper claims that this can be done in polynomial time.

> The current paper proves gradient descent achieves zero training loss in polynomial time for a deep over-parameterized neural network with residual connections (ResNet).

Re: Gradient Descent Finds Global Minima of Deep Neural Networks

#38

Post by MAXPOOL »

fwilliams wrote: post #36

It's worth noting that the primary result of this paper has only to do with the error on the training data under empirical risk minimization. Zero training error =/= a model that generalizes. For any optimization problem, you can always add enough parameters to achieve zero error on a problem over a finite training set (imagine introducing enough variables to fully memorize the map from inputs to labels). The major c…

The way to tackle the problem you state would be finding similar bounds with regularization.
Post reply on HN