3 ms·

> Grimmer found that the fastest sequences always had one thing in common: The middle step was always a big one. Its size depended on the number of steps in the

> Grimmer found that the fastest sequences always had one thing in common: The middle step was always a big one. Its size depended on the number of steps in the repeating sequence. For a three-step sequence, the big step had length 4.9. For a 15-step sequence, the algorithm recommended one step of length 29.7. And for a 127-step sequence, the longest one tested, the big central leap was a whopping 370. At first that sounds like an absurdly large number, Grimmer said, but there were enough total steps to make up for that giant leap, so even if you blew past the bottom, you could still make it back quickly. His paper showed that this sequence can arrive at the optimal point nearly three times faster than it would by taking constant baby steps. “Sometimes, you should really overcommit,” he said. I wonder if this is a Rube Goldberg machine for imitating a second-order method. Gradient descent is slow because it can't correct for the curvature of the function, but maybe when you use a meta-algorithm to optimize the entire sequence of steps, you can arrive at something that approximates it. So the first half of the steps is getting you in position for a big approximate second-order step, and the second half is working to clean up the after-effects of that big step.

AbrahamParangi 3y ago
I would take a complementary side to this bet, in that I think it's relevant that it's extremely, extremely extremely hard to improve upon ADAM (Adaptive Moment Estimation) in terms of FLOPS-till-convergence. That this is so hard feels notable to me, like we're specifically misunderstanding something about the optimization process in higher dimensions.
- civilized 3y ago
  This paper is about convergence speed, not flops, so I'm not sure why this observation would be relevant. And at any rate, Adam being fastest assumes that second-order methods require much more computation per iteration than first-order ones, which isn't true for a lot of practical problems. Classical optimization theory favored second-order methods because their faster convergence on many problems outweighed the extra computation per iteration. The idea that Adam is best isn't a general principle, it's an empirical observation that, as far as I know, is limited to the context of training large neural networks.
  - AbrahamParangi 3y ago
    Asking about convergence speed in terms of "steps" or anything that isn't FLOPS or wall clock training speed is sometimes academically interesting but encourages "hiding the ball" so to speak. You can in general hide quantity in the number of steps by increasing the complexity of each step (for the trivial case, imagine one step of 5-ADAM which performs the ADAM update and evaluation 5 times - 5-ADAM will converge much faster than ADAM alone when measured in steps-to-convergence).
- josephg 3y ago
  What are your thoughts on Sophia, an algorithmic replacement for ADAM which promises to converge in fewer steps? https://arxiv.org/abs/2305.14342 https://arxiv.org/abs/2305.14342
  - tbalsam 3y ago
    There are dozens of dozens of optimizers. Almost every single one of them claims superiority. Some of them, like MADGRAD, are great. But sticking with the basics is pretty good in my experience.
  - lucidrains 3y ago
    https://arxiv.org/abs/2307.06440 https://arxiv.org/abs/2307.06440
tbalsam 3y ago
I think a high lr + SGD does maybe a piece of what you're talking about, and I think the most important piece. That is, the curvature can be ignored as the noise from a high lr implicitly optimizes for flatter valleys in parameter space, and I would assume that implicitly carries over to second order stuff as you could make an argument for an implicit sensing in the update step of the diagonal of the empirical Fisher via the noise of ultra high lr gradient steps. This would imply a more genetic side component to optimization here, I believe? Since this is not a directly differentiable thing, and all of this occurs as the natural effects of a higher lr? (I.e. the evolutionary update rule being, "the parameter spaces that survive, survive". Since the parameter spaces that like to survive tend to be flat, and flatness seems to correlate with generalization, then we have a good thing our our hands.) Adam on the other hand, I believe explicitly regularizes the update step relative to a biased (I believe, since it's not subtracted from momentum?) approximation of the diagonal of the empirical Fisher, hence being sort of a "anti-SGD" in that sense, I believe. This I think makes it really effective for models where you'll often see the data only once, and the model is ODE-like and needs information>>regularization, which we see with many LLMs these days. Not sure if that helps any or if that's just rambling at this point, that's what I've got and what that made me think of! <3 :))))

AbrahamParangi 3y ago

I would take a complementary side to this bet, in that I think it's relevant that it's extremely, extremely extremely hard to improve upon ADAM (Adaptive Moment Estimation) in terms of FLOPS-till-convergence. That this is so hard feels notable to me, like we're specifically misunderstanding something about the optimization process in higher dimensions.

civilized 3y ago
This paper is about convergence speed, not flops, so I'm not sure why this observation would be relevant. And at any rate, Adam being fastest assumes that second-order methods require much more computation per iteration than first-order ones, which isn't true for a lot of practical problems. Classical optimization theory favored second-order methods because their faster convergence on many problems outweighed the extra computation per iteration. The idea that Adam is best isn't a general principle, it's an empirical observation that, as far as I know, is limited to the context of training large neural networks.
- AbrahamParangi 3y ago
  Asking about convergence speed in terms of "steps" or anything that isn't FLOPS or wall clock training speed is sometimes academically interesting but encourages "hiding the ball" so to speak. You can in general hide quantity in the number of steps by increasing the complexity of each step (for the trivial case, imagine one step of 5-ADAM which performs the ADAM update and evaluation 5 times - 5-ADAM will converge much faster than ADAM alone when measured in steps-to-convergence).
josephg 3y ago
What are your thoughts on Sophia, an algorithmic replacement for ADAM which promises to converge in fewer steps? https://arxiv.org/abs/2305.14342 https://arxiv.org/abs/2305.14342
- tbalsam 3y ago
  There are dozens of dozens of optimizers. Almost every single one of them claims superiority. Some of them, like MADGRAD, are great. But sticking with the basics is pretty good in my experience.
- lucidrains 3y ago
  https://arxiv.org/abs/2307.06440 https://arxiv.org/abs/2307.06440

tbalsam 3y ago

I think a high lr + SGD does maybe a piece of what you're talking about, and I think the most important piece. That is, the curvature can be ignored as the noise from a high lr implicitly optimizes for flatter valleys in parameter space, and I would assume that implicitly carries over to second order stuff as you could make an argument for an implicit sensing in the update step of the diagonal of the empirical Fisher via the noise of ultra high lr gradient steps. This would imply a more genetic side component to optimization here, I believe? Since this is not a directly differentiable thing, and all of this occurs as the natural effects of a higher lr? (I.e. the evolutionary update rule being, "the parameter spaces that survive, survive". Since the parameter spaces that like to survive tend to be flat, and flatness seems to correlate with generalization, then we have a good thing our our hands.) Adam on the other hand, I believe explicitly regularizes the update step relative to a biased (I believe, since it's not subtracted from momentum?) approximation of the diagonal of the empirical Fisher, hence being sort of a "anti-SGD" in that sense, I believe. This I think makes it really effective for models where you'll often see the data only once, and the model is ODE-like and needs information>>regularization, which we see with many LLMs these days. Not sure if that helps any or if that's just rambling at this point, that's what I've got and what that made me think of! <3 :))))