38 ms·

This is really not a new idea for anybody that has studied numerical optimization or done a lot of much simpler linear modeling. It has to do with the gradients

by jl2718 7y ago

This is really not a new idea for anybody that has studied numerical optimization or done a lot of much simpler linear modeling. It has to do with the gradients, which are basically random steps in high-dimensional spaces unless you align with a ‘large’ eigenvector of the Hessian. This explanation didn’t go over well at all with the ML cargo cultists until someone gave it a name. Interesting how things work.

stared 7y ago
Could you point to concrete papers, showing that empirically? (Many things were rediscovered over and over, sure.) > random steps in high-dimensional spaces unless you align with a ‘large’ eigenvector of the Hessian In this case, the main observation is different than this one, and has much more to do with sparsity (and an exponentially growing number of connections with each layer).
- lsorber 7y ago
  Nocedal has some papers in this direction.
nograpes 7y ago
Do you have any good papers or textbooks where I can learn about this from a numerical optimization perspective?
- adampk 7y ago
  https://www.amazon.com/Numerical-Optimization-Operations-Financial-Engineering-ebook/dp/B014P9ICXI https://www.amazon.com/Numerical-Optimization-Operations-Fin... seems to be "the" numerical optimization textbook
sdenton4 7y ago
It's also fun to consider that most neural network architectures are mostly piecewise linear: relu(Mx + b) for standard feedforward or convolutional layers... So one would expect a lot of knowledge and folklore from (piecewise) linear optimization to carry over nicely. IIRC, ResNet was a good example of that: It's more efficient to learn relu(x + Mx + b) than relu(Mx + b) One difficulty, though, is that proofs generally /don't/ carry over, and IME a lot of 'classical' methods constrain themselves to provable operations... So at times it can be hard to tell the difference between 'useful folklore' and 'tweak that makes the proofs work.' I've been delving into sparse coding literature from about ten years ago, and there's a lot of this kind of difficulty... Interestingly, the best sparse coding architectures ended up being very very similar to shallow neural networks. There's a nice 'deep ksvd denoising' paper from a few months back which improves handily on the older sparse coding architectures by bringing in a smattering of ideas from the DNN age; the rant at the end is makes the case for building these 'blended' architectures to get the best of both worlds. https://arxiv.org/abs/1909.13164 https://arxiv.org/abs/1909.13164 I tend to think that the DNN architectures beat the provable-domain architectures for Good Reasons, but the USEFUL response is to build awesome blended architectures that maybe go a long way towards bringing down model sizes and complexity, while increasing explainability.
- thesz 7y ago
  If I am remember correctly, residual layer has form of x+nonlin(Mx+b), not one you provided. I also found (in my "learn DL" experiments) that for ReLU the x - relu(Mx + b) version works better (trains faster and achieves better accuracy).
  - sdenton4 7y ago
    Correct; the idea is to take Identity + Tweak, so the Relu should hit the 'tweak.'
    - srean 7y ago
      Hey sdenton did you work on or publish that harmonic analysis of correlations that you had mentioned long time ago. I am still quite curious about that. If polishing it for ICML etc is too much of a downer, you can upload it to arxiv. I would love to read that.
      - sdenton4 7y ago
        Hey, send me an email (should be in my profile, or easy to guess: it's a gmail account) and I'll see what I can dig up. :) I've admittedly been pretty terrible about actually publishing... But definitely have notes and slide decks that could probably be put together into Something.
  - bonoboTP 7y ago
    Plus or minus shouldn't make any difference as long as your input distribution is symmetric around zero. A simple transformation shows you can get the same effect by just flipping the input the output and the weights. The weights are initialized from a symmetric distribution, so the only difference may come from having the input nonevenly distributed around zero. y = x - relu(Mx + b) -y = -x + relu((-M)(-x) + b) y' = x' + relu(M'x' + b) Have you tried normalizing your input to have zero mean?
    - thesz 7y ago
moultano 7y ago
I don't see any connection between what you've written and the lottery ticket hypothesis. Could you elaborate? (In particular, the core of the lottery ticket hypothesis is that layers make the nets combinatorial, and so I don't see how anything from simple linear modelling should transfer.)
- jl2718 7y ago
  RELU training is basically the same as active sets. You call it nonlinearity. I call it a constrained sub-problem. The point is that it is always linear for the active variables. If you’re talking only about gradients, you’re not doing anything non-linear.
  - moultano 7y ago
    What does that have to do with the lottery ticket hypothesis?
    - jl2718 7y ago
      Because the opposite hypothesis, that 'winning tickets' can emerge from 'bad tickets' using stochastic gradient descent, implies that randomness doesn't push you back into the null space of the generalization curvature, which you can empirically observe that it almost always will, except for the same eigenvectors which tend to reinforce where there is strong alignment already, iteration after iteration. If you train a lot of small problems you can watch this happen just by looking at the angles between each update. Maybe that's the wrong explanation; I don't know. The practitioner take-away is that some initializations are just lucky/unlucky and you learn this quickly if you start a lot of small problems from scratch. Try stochastic BFGS and the frustration forces some inquiry. The paper is very experimental, which is great, but the conjecture itself is pointing roughly at some feature of SGD (i.e. "SGD seeks out and trains a subset of well-initialized weights.") without offering much direct explanation, for which I'm offering a hand-wavy viewpoint that also comes more from experience/frustration trying to optimize in ill-conditioned local curvatures. There may be a combinatorial way to look at 'lottery tickets', and that may be more productive than looking at it as eigenbasis pursuit, but it seems to me that it certainly might have something to do with that. Either way, the terms are irrelevant, and if it is true now, it was true before it got a name.

by jl2718 7y ago

stared 7y ago

Could you point to concrete papers, showing that empirically? (Many things were rediscovered over and over, sure.) > random steps in high-dimensional spaces unless you align with a ‘large’ eigenvector of the Hessian In this case, the main observation is different than this one, and has much more to do with sparsity (and an exponentially growing number of connections with each layer).

lsorber 7y ago
Nocedal has some papers in this direction.

nograpes 7y ago

Do you have any good papers or textbooks where I can learn about this from a numerical optimization perspective?

adampk 7y ago
https://www.amazon.com/Numerical-Optimization-Operations-Financial-Engineering-ebook/dp/B014P9ICXI https://www.amazon.com/Numerical-Optimization-Operations-Fin... seems to be "the" numerical optimization textbook

sdenton4 7y ago

It's also fun to consider that most neural network architectures are mostly piecewise linear: relu(Mx + b) for standard feedforward or convolutional layers... So one would expect a lot of knowledge and folklore from (piecewise) linear optimization to carry over nicely. IIRC, ResNet was a good example of that: It's more efficient to learn relu(x + Mx + b) than relu(Mx + b) One difficulty, though, is that proofs generally /don't/ carry over, and IME a lot of 'classical' methods constrain themselves to provable operations... So at times it can be hard to tell the difference between 'useful folklore' and 'tweak that makes the proofs work.' I've been delving into sparse coding literature from about ten years ago, and there's a lot of this kind of difficulty... Interestingly, the best sparse coding architectures ended up being very very similar to shallow neural networks. There's a nice 'deep ksvd denoising' paper from a few months back which improves handily on the older sparse coding architectures by bringing in a smattering of ideas from the DNN age; the rant at the end is makes the case for building these 'blended' architectures to get the best of both worlds. https://arxiv.org/abs/1909.13164 https://arxiv.org/abs/1909.13164 I tend to think that the DNN architectures beat the provable-domain architectures for Good Reasons, but the USEFUL response is to build awesome blended architectures that maybe go a long way towards bringing down model sizes and complexity, while increasing explainability.

thesz 7y ago
If I am remember correctly, residual layer has form of x+nonlin(Mx+b), not one you provided. I also found (in my "learn DL" experiments) that for ReLU the x - relu(Mx + b) version works better (trains faster and achieves better accuracy).
- sdenton4 7y ago
  Correct; the idea is to take Identity + Tweak, so the Relu should hit the 'tweak.'
  - srean 7y ago
    Hey sdenton did you work on or publish that harmonic analysis of correlations that you had mentioned long time ago. I am still quite curious about that. If polishing it for ICML etc is too much of a downer, you can upload it to arxiv. I would love to read that.
    - sdenton4 7y ago
      Hey, send me an email (should be in my profile, or easy to guess: it's a gmail account) and I'll see what I can dig up. :) I've admittedly been pretty terrible about actually publishing... But definitely have notes and slide decks that could probably be put together into Something.
- bonoboTP 7y ago
  Plus or minus shouldn't make any difference as long as your input distribution is symmetric around zero. A simple transformation shows you can get the same effect by just flipping the input the output and the weights. The weights are initialized from a symmetric distribution, so the only difference may come from having the input nonevenly distributed around zero. y = x - relu(Mx + b) -y = -x + relu((-M)(-x) + b) y' = x' + relu(M'x' + b) Have you tried normalizing your input to have zero mean?
  - thesz 7y ago

moultano 7y ago

I don't see any connection between what you've written and the lottery ticket hypothesis. Could you elaborate? (In particular, the core of the lottery ticket hypothesis is that layers make the nets combinatorial, and so I don't see how anything from simple linear modelling should transfer.)

jl2718 7y ago
RELU training is basically the same as active sets. You call it nonlinearity. I call it a constrained sub-problem. The point is that it is always linear for the active variables. If you’re talking only about gradients, you’re not doing anything non-linear.
- moultano 7y ago
  What does that have to do with the lottery ticket hypothesis?
  - jl2718 7y ago
    Because the opposite hypothesis, that 'winning tickets' can emerge from 'bad tickets' using stochastic gradient descent, implies that randomness doesn't push you back into the null space of the generalization curvature, which you can empirically observe that it almost always will, except for the same eigenvectors which tend to reinforce where there is strong alignment already, iteration after iteration. If you train a lot of small problems you can watch this happen just by looking at the angles between each update. Maybe that's the wrong explanation; I don't know. The practitioner take-away is that some initializations are just lucky/unlucky and you learn this quickly if you start a lot of small problems from scratch. Try stochastic BFGS and the frustration forces some inquiry. The paper is very experimental, which is great, but the conjecture itself is pointing roughly at some feature of SGD (i.e. "SGD seeks out and trains a subset of well-initialized weights.") without offering much direct explanation, for which I'm offering a hand-wavy viewpoint that also comes more from experience/frustration trying to optimize in ill-conditioned local curvatures. There may be a combinatorial way to look at 'lottery tickets', and that may be more productive than looking at it as eigenbasis pursuit, but it seems to me that it certainly might have something to do with that. Either way, the terms are irrelevant, and if it is true now, it was true before it got a name.