4 ms·
The formula (from their pseudocode); m ← αm + (1-α)g // momentum c ← βm + (1-β)g // new part θ ← θ + η sign(c) // update of parameters The parameter upda
by yobbo 4y ago
The formula (from their pseudocode);
m ← αm + (1-α)g // momentum
c ← βm + (1-β)g // new part
θ ← θ + η sign(c) // update of parameters
The parameter update is via the sign of the weighted average of the momentum and the gradient.
For comparison, the gradient of abs(x) is sign(x), which is the update with L1-norm.
- WithinReason 4y agoIs the 2nd line really necessary? Since β is 0.9, the second line becomes: c ← 0.9m + (0.1)g There doesn't seem to be a significant difference between their code: θ ← θ + η sign(0.9m + (0.1)g) and just not having the 2nd line at all: θ ← θ + η sign(m)
- yobbo 4y agoTrue, those are equivalent. Might even become identical once it is compiled.
- mtcrawshaw 4y agoThe second line appears unnecessary because the formula in that comment is missing one line from the definition of LION. See my above comment.
- mtcrawshaw 4y agoYour formula is almost right but there is a slight difference. Namely the third line of Program 1 in their paper is absent from your statement, which will change the value of the momentum variable for subsequent steps. 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 https://arxiv.org/abs/1802.04434 [2] http://proceedings.mlr.press/v97/karimireddy19a.html http://proceedings.mlr.press/v97/karimireddy19a.html [3] https://arxiv.org/abs/2208.11195 https://arxiv.org/abs/2208.11195
- yobbo 4y agoYes. 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 β?
- mtcrawshaw 4y agoMoving 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.
- yobbo 4y agoIf we let βₛ be as above (SignSGD?) and βₗ be as in LION, then it looks to me that βₛ=βₗ/α should make c from both equal.