Re:Symbolic Discovery of Optimization Algorithms
by yobbo on Saturday February 18, 2023 @11:48AM
(#34848321)
Yes. I omitted time-indices, and moved the momentum-update up to before the parameter-update. In their pseudo-code θₜ updated with mₜ₋₁ whereas above, it would be with mₜ.
I suspect it is equivalent up to slightly different α and β?
Re:Symbolic Discovery of Optimization Algorithms
by mtcrawshaw on Saturday February 18, 2023 @12:31PM
(#34848868)
Moving the momentum update before the parameter update changes the algorithm from LION to SignSGD. The only novel part of their algorithm is the fact that the momentum changes after the update is computed. They are not equivalent even if you can choose coefficients however you like. But as I said, if I had to guess I would say that this does not cause a fundamental change in the behavior of the optimization.
To be fair, I don't think that this operation will fundamentally change the behavior of the algorithm. In fact, I don't think their algorithm has a fundamentally different behavior than SignSGD with momentum, whose convergence behavior is well-understood [1, 2, 3]. Actually, the algorithm you described is equivalent to SignSGD with momentum. In the algorithm you described, m is a convex combination of m and g (with coefficient alpha), then c is a convex combination of updated m and g (with coefficient beta). This is exactly the same as setting c as a convex combination of m and g with coefficient alpha*beta. And that is exactly SignSGD with momentum. The only difference between the algorithm you described (equivalent to SignSGD) and LION is that they further modify the value of the momentum after computing the update with an additional convex combination operation. Again, I am skeptical that this operation will fundamentally change the behavior of the algorithm. But that's just my guess.
[1] https://arxiv.org/abs/1802.04434
[2] http://proceedings.mlr.press/v97/karimireddy19a.html
[3] https://arxiv.org/abs/2208.11195