7 ms·

Mathematics of Deep Learning [pdf]

220 points by magoghm 9y ago

banachtarski 9y ago
This is a horribly titled paper and I don't even agree with the premise necessarily. Since when did we become convinced deep learning achieves "global optimality" as they put it.
- gwern 9y ago
  > Since when did we become convinced deep learning achieves "global optimality" as they put it. There are a couple of papers over the past few years arguing/proving under various models that the local optima in deep models either are or are within epsilon of the global optima and this is why SGD reaching only local optima results in models that still work well. I assume these results are covered in OP (haven't read it yet, just answering your question).
  - catnaroek 9y ago
    > There are a couple of papers over the past few years arguing/proving under various models that the local optima in deep models either are or are within epsilon of the global optima I don't care so much for the “arguing” part, but the “proving” part got me interested. ML methods reliably being able to get epsilon-close to global optima is a BFD. What mathematical technology was used to establish these results? Could you provide links to those papers?
    - deleted 9y ago
      [deleted]
    - nabla9 9y ago
      https://arxiv.org/abs/1412.0233 https://arxiv.org/abs/1412.0233
    - vardhanw 9y ago
      https://arxiv.org/abs/1605.08361 https://arxiv.org/abs/1605.08361 https://arxiv.org/abs/1704.08045 https://arxiv.org/abs/1704.08045
- nabla9 9y ago
  When the network is deep or big enough, local minimums tend to have loss close to global optimum. There is theoretical and empirical evidence for this. Global minimum is usually overfitting so what is needed is getting close enough. In practice algorithms like stochastic gradient descent have problems distinguishing between saddle points and local minima. There is hypothesis that in many/most cases local minima where algorithms get stuck are actually saddle points with long plateau.
  - deleted 9y ago
    [deleted]
  - viewtransform 9y ago
    This mathematical hand waving plagued the field of genetic algorithms and its variants in the 90's until the 'No free lunch theorem' was published from the Santa Fe institute. It essentially said (my take on it) that if you had no information about the landscape you were searching - then couldn't say much about the algorithm you were selling. https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
    - cgmg 9y ago
      The problem with the NFL theorem is that, in a sense, it doesn't apply to the real world: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization#NFL_and_Kolmogorov_randomness https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
      - viewtransform 9y ago
        True. High-dimensional non-linear systems (like deep NNs) are a frontier we are just beginning to explore with empirical success. However, if I was a VC - my knowledge of the NFL would make me look skeptically at any grandiose claims of miracle learning algorithms. In a sense, it provides me with an upper bound to BS.
    - nabla9 9y ago
- throwaway312493 9y ago
  It is not; it actually looks like a very well-written paper, for a review, with references to all the latest developments. Your particular quibble is answered in a section along with references.
- sjg007 9y ago
  I believe this is in reference to the information bottleneck. This is an idea that there is a limit to the performance of a particular network. From an information theory point of view, a deep neural network can be viewed as compressing the input and subsequently generating a code on the other side. So the network is seen as encoding the data and because of that we can bound it using some tools based in information theory.
leecarraher 9y ago
I'm think this is a work in progress? Seems to be in ieee format, where pages are gold, and one would almost never waste an entire on references(surveys), and leave another mostly blank space. I'll wait for the peer reviewed version.
msmith10101 9y ago
Newtons method and linear algebra. High school math, basically.
- santaclaus 9y ago
  > Newtons method Where are you seeing Newton's method? I didn't think second order information was available for typical systems in statistical machine learning.
  - make3 9y ago
    my understanding is that the issue is that the full Hessian of the loss is too expensive to compute at each step for the relative size of the increase in learning speed
    - _0ffh 9y ago
      Yeah I think that's why quasi-Newton methods like BFGS have been developed.
- aisofteng 9y ago
  >For instance, local entropy, the loss that Entropy-SGD minimizes, is the solution of the Hamilton- Jacobi-Bellman PDE and can therefore be written as a stochastic optimal control problem, which penalizes greedy gradient descent. This direction further leads to connections between variants of SGD with good empirical performance and standard methods in convex optimization such as inf- convolutions and proximal methods. You clearly didn't read the article. What are you commenting on, then? It seems to be about your own understanding, since it's certainly not about the article.

220 points by magoghm 9y ago

This is a horribly titled paper and I don't even agree with the premise necessarily. Since when did we become convinced deep learning achieves "global optimality" as they put it.

gwern 9y ago
> Since when did we become convinced deep learning achieves "global optimality" as they put it. There are a couple of papers over the past few years arguing/proving under various models that the local optima in deep models either are or are within epsilon of the global optima and this is why SGD reaching only local optima results in models that still work well. I assume these results are covered in OP (haven't read it yet, just answering your question).
- catnaroek 9y ago
  > There are a couple of papers over the past few years arguing/proving under various models that the local optima in deep models either are or are within epsilon of the global optima I don't care so much for the “arguing” part, but the “proving” part got me interested. ML methods reliably being able to get epsilon-close to global optima is a BFD. What mathematical technology was used to establish these results? Could you provide links to those papers?
  - deleted 9y ago
    [deleted]
  - nabla9 9y ago
    https://arxiv.org/abs/1412.0233 https://arxiv.org/abs/1412.0233
  - vardhanw 9y ago
    https://arxiv.org/abs/1605.08361 https://arxiv.org/abs/1605.08361 https://arxiv.org/abs/1704.08045 https://arxiv.org/abs/1704.08045
nabla9 9y ago
When the network is deep or big enough, local minimums tend to have loss close to global optimum. There is theoretical and empirical evidence for this. Global minimum is usually overfitting so what is needed is getting close enough. In practice algorithms like stochastic gradient descent have problems distinguishing between saddle points and local minima. There is hypothesis that in many/most cases local minima where algorithms get stuck are actually saddle points with long plateau.
- deleted 9y ago
  [deleted]
- viewtransform 9y ago
  This mathematical hand waving plagued the field of genetic algorithms and its variants in the 90's until the 'No free lunch theorem' was published from the Santa Fe institute. It essentially said (my take on it) that if you had no information about the landscape you were searching - then couldn't say much about the algorithm you were selling. https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
  - cgmg 9y ago
    The problem with the NFL theorem is that, in a sense, it doesn't apply to the real world: https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization#NFL_and_Kolmogorov_randomness https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...
    - viewtransform 9y ago
      True. High-dimensional non-linear systems (like deep NNs) are a frontier we are just beginning to explore with empirical success. However, if I was a VC - my knowledge of the NFL would make me look skeptically at any grandiose claims of miracle learning algorithms. In a sense, it provides me with an upper bound to BS.
  - nabla9 9y ago
throwaway312493 9y ago
It is not; it actually looks like a very well-written paper, for a review, with references to all the latest developments. Your particular quibble is answered in a section along with references.
sjg007 9y ago
I believe this is in reference to the information bottleneck. This is an idea that there is a limit to the performance of a particular network. From an information theory point of view, a deep neural network can be viewed as compressing the input and subsequently generating a code on the other side. So the network is seen as encoding the data and because of that we can bound it using some tools based in information theory.

leecarraher 9y ago

I'm think this is a work in progress? Seems to be in ieee format, where pages are gold, and one would almost never waste an entire on references(surveys), and leave another mostly blank space. I'll wait for the peer reviewed version.

msmith10101 9y ago

Newtons method and linear algebra. High school math, basically.

santaclaus 9y ago
> Newtons method Where are you seeing Newton's method? I didn't think second order information was available for typical systems in statistical machine learning.
- make3 9y ago
  my understanding is that the issue is that the full Hessian of the loss is too expensive to compute at each step for the relative size of the increase in learning speed
  - _0ffh 9y ago
    Yeah I think that's why quasi-Newton methods like BFGS have been developed.
aisofteng 9y ago
>For instance, local entropy, the loss that Entropy-SGD minimizes, is the solution of the Hamilton- Jacobi-Bellman PDE and can therefore be written as a stochastic optimal control problem, which penalizes greedy gradient descent. This direction further leads to connections between variants of SGD with good empirical performance and standard methods in convex optimization such as inf- convolutions and proximal methods. You clearly didn't read the article. What are you commenting on, then? It seems to be about your own understanding, since it's certainly not about the article.