7 ms·

Gradient Descent Finds Global Minima of Deep Neural Networks

133 points by superfx 8y ago

iandanforth 8y ago
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.'
- trevyn 8y ago
  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”.
  - iandanforth 8y ago
    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.
lbj 8y ago
I cant claim to fully understand the proof, but these guys have done an amazing job in terms of furthering our understanding of deep nets.
brentjanderson 8y ago
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.
ramgorur 8y ago
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 loss" mean the network has converged to the global optima? I used to know you will get zero training loss even if you are at a local minima as well. Please correct me if I am wrong.
- TTPrograms 8y ago
  1) Just because you can prove convergence for convex functions does not mean you can't prove it for non-convex functions. 2) This is "a way" not "The only way". (If A then B) does not imply (if not A then not B)
  - ramgorur 8y ago
    >Just because you can prove convergence for convex functions does not mean you can't prove it for non-convex functions. I don't understand. How do you prove a gradient descent is guaranteed to escape local minima?
    - heyitsguay 8y ago
      Convex functions aren't the only functions with a single local (and global) minimum - consider sqrt(|x|) for a simple 1d example.
      - ramgorur 8y ago
        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".
pj_mukh 8y ago
With this much wide distribution of ML algorithms in use, its still funny to see papers begin with "One of the mysteries of deep learning is that...." and then goes on to lay out the multiple ways we have no idea why some of these DL techniques work.
- deleted 8y ago
  [deleted]
orf 8y ago
> 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.
- currymj 8y ago
  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.
  - elcomet 8y ago
    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).
    - srean 8y ago
      But thats the crux of the question: why and how does it not just memorize when we know it can do so easily ?
      - elcomet 8y ago
        Maybe just because it's easier to find patterns than to memorize (if you have a lot of data).
        currymj 8y ago
        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.
fwilliams 8y ago
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.
- sytelus 8y ago
  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).
  - p1esk 8y ago
    There is bit of difference between fitting dataset to some convenient parameterized function vs finding global minima of non-convex function What's the difference? Any point where the loss is zero is global minimum.
- MAXPOOL 8y ago
  The way to tackle the problem you state would be finding similar bounds with regularization.
juskrey 8y ago
How do you gradually detect a Dirac stick?
charleshmartin 8y ago
An excellent paper which uses (some of the) results we have also found studying the weight matrices of neural networks...namely that they rarely undergo rank collapse https://calculatedcontent.com/2018/09/21/rank-collapse-in-deep-learning/ https://calculatedcontent.com/2018/09/21/rank-collapse-in-de... But they miss something..the weight matrices also display power law behavior. https://calculatedcontent.com/2018/09/09/power-laws-in-deep-learning/ https://calculatedcontent.com/2018/09/09/power-laws-in-deep-... This is also important because it was suggested in the early 90s that Heavy Tailed Spin Glasses would have a single local mimima. This fact is the basis of my early suggestion that DNNs would exhibit a spin funnel
gogut 8y ago
This paper appears in November, but in fact, Allen-Zhu (MSR, http://people.csail.mit.edu/zeyuan/ http://people.csail.mit.edu/zeyuan/ ) already posted his result in Oct. This is their first paper in Oct:https://arxiv.org/pdf/1810.12065.pdf https://arxiv.org/pdf/1810.12065.pdf, this is their second paper in Nov https://arxiv.org/pdf/1811.03962.pdf https://arxiv.org/pdf/1811.03962.pdf . In MSR Oct paper, they proved how to train RNN (which is even harder than DNN). In their Nov paper, they proved how to train DNN. Compared to their Oct one, the Nov one is actually much easier. The reason is, in RNN, every layer has the same weight matrix, but in DNN every layer could have different weight matrices. Originally, they were not planning to write this DNN paper. Since someone is complaining that RNN is not multilayer neural network, that’s why they did it. In summary, the difference between MSR paper and this paper is: if H denotes the number of layers, let m denote the number of hidden nodes. MRS paper can show we only need to assume m > poly (H), using SGD, the model can find the global optimal. However, in Du et al.’s work, they have a similar result, but they have to assume m > 2^{O(H)}. Compared to MSR paper, Du et al.’s paper is actually pretty trivial.

133 points by superfx 8y ago

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

trevyn 8y ago
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”.
- iandanforth 8y ago
  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.

lbj 8y ago

I cant claim to fully understand the proof, but these guys have done an amazing job in terms of furthering our understanding of deep nets.

brentjanderson 8y ago

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.

ramgorur 8y ago

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 loss" mean the network has converged to the global optima? I used to know you will get zero training loss even if you are at a local minima as well. Please correct me if I am wrong.

TTPrograms 8y ago
1) Just because you can prove convergence for convex functions does not mean you can't prove it for non-convex functions. 2) This is "a way" not "The only way". (If A then B) does not imply (if not A then not B)
- ramgorur 8y ago
  >Just because you can prove convergence for convex functions does not mean you can't prove it for non-convex functions. I don't understand. How do you prove a gradient descent is guaranteed to escape local minima?
  - heyitsguay 8y ago
    Convex functions aren't the only functions with a single local (and global) minimum - consider sqrt(|x|) for a simple 1d example.
    - ramgorur 8y ago
      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".

pj_mukh 8y ago

With this much wide distribution of ML algorithms in use, its still funny to see papers begin with "One of the mysteries of deep learning is that...." and then goes on to lay out the multiple ways we have no idea why some of these DL techniques work.

deleted 8y ago
[deleted]

orf 8y ago

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

currymj 8y ago
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.
- elcomet 8y ago
  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).
  - srean 8y ago
    But thats the crux of the question: why and how does it not just memorize when we know it can do so easily ?
    - elcomet 8y ago
      Maybe just because it's easier to find patterns than to memorize (if you have a lot of data).
      - currymj 8y ago
        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.

fwilliams 8y ago

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.

sytelus 8y ago
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).
- p1esk 8y ago
  There is bit of difference between fitting dataset to some convenient parameterized function vs finding global minima of non-convex function What's the difference? Any point where the loss is zero is global minimum.
MAXPOOL 8y ago
The way to tackle the problem you state would be finding similar bounds with regularization.

juskrey 8y ago

How do you gradually detect a Dirac stick?

charleshmartin 8y ago

An excellent paper which uses (some of the) results we have also found studying the weight matrices of neural networks...namely that they rarely undergo rank collapse https://calculatedcontent.com/2018/09/21/rank-collapse-in-deep-learning/ https://calculatedcontent.com/2018/09/21/rank-collapse-in-de... But they miss something..the weight matrices also display power law behavior. https://calculatedcontent.com/2018/09/09/power-laws-in-deep-learning/ https://calculatedcontent.com/2018/09/09/power-laws-in-deep-... This is also important because it was suggested in the early 90s that Heavy Tailed Spin Glasses would have a single local mimima. This fact is the basis of my early suggestion that DNNs would exhibit a spin funnel

gogut 8y ago

This paper appears in November, but in fact, Allen-Zhu (MSR, http://people.csail.mit.edu/zeyuan/ http://people.csail.mit.edu/zeyuan/ ) already posted his result in Oct. This is their first paper in Oct:https://arxiv.org/pdf/1810.12065.pdf https://arxiv.org/pdf/1810.12065.pdf, this is their second paper in Nov https://arxiv.org/pdf/1811.03962.pdf https://arxiv.org/pdf/1811.03962.pdf . In MSR Oct paper, they proved how to train RNN (which is even harder than DNN). In their Nov paper, they proved how to train DNN. Compared to their Oct one, the Nov one is actually much easier. The reason is, in RNN, every layer has the same weight matrix, but in DNN every layer could have different weight matrices. Originally, they were not planning to write this DNN paper. Since someone is complaining that RNN is not multilayer neural network, that’s why they did it. In summary, the difference between MSR paper and this paper is: if H denotes the number of layers, let m denote the number of hidden nodes. MRS paper can show we only need to assume m > poly (H), using SGD, the model can find the global optimal. However, in Du et al.’s work, they have a similar result, but they have to assume m > 2^{O(H)}. Compared to MSR paper, Du et al.’s paper is actually pretty trivial.