News for hackers. Stuff that matters.
Re:Symbolic Discovery of Optimization Algorithms by yobbo on Saturday February 18, 2023 @10:15AM (#34847471)
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.

Re:Symbolic Discovery of Optimization Algorithms by WithinReason on Saturday February 18, 2023 @11:10AM (#34847949)
Is 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)

Re:Symbolic Discovery of Optimization Algorithms by mtcrawshaw on Saturday February 18, 2023 @11:26AM (#34848102)
The second line appears unnecessary because the formula in that comment is missing one line from the definition of LION. See my above comment.
Re:Symbolic Discovery of Optimization Algorithms by yobbo on Saturday February 18, 2023 @11:25AM (#34848090)
True, those are equivalent. Might even become identical once it is compiled.
Re:Symbolic Discovery of Optimization Algorithms by mtcrawshaw on Saturday February 18, 2023 @11:16AM (#34848013)
Your 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

[2] http://proceedings.mlr.press/v97/karimireddy19a.html

[3] https://arxiv.org/abs/2208.11195

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.
Re:Symbolic Discovery of Optimization Algorithms by yobbo on Sunday February 19, 2023 @04:34AM (#34855932)
If we let βₛ be as above (SignSGD) and βₗ be as in LION, then it looks to me that βₛ=βₗ/α should make c from both equal.