I no longer feel like I know what claim you’re advancing.
In this post and in recent comments (1, 2), you’ve said that you have proven an “equivalence” between selection and SGD under certain conditions. You’ve used phrases like “mathematically equivalent” and “a proof of equivalence.”
When someone tells me they have a mathematical proof that two things are equivalent, I read the word “equivalent” to mean “really, totally, exactly the same (under the right conditions).” I think this is a pretty standard way to interpret this kind of language. And in my critique, I argued—I think successfully—against this kind of equivalence.
From your latest comments, it appears that you are not claiming anything this strong. But now I don’t know what you are claiming. For instance, you write here:
On the distribution of noise, I’ll happily acknowledge that I didn’t show equivalence. I half expect that one could be eked out at a stretch, but I also think this is another minor and unimportant detail.
Details that are “unimportant” in one context, or for making a particular argument, may be very important in some other context or argument[1]. To take one example:
As I said elsewhere, any number of practical departures from pure SGD mess with the step size anyway (and with the gradient!) so this feels like asking for too much. Do we really think SGD vs momentum vs Adam vs … is relevant to the conclusions we want to draw? (Serious question; my best guess is ‘no’, but I hold that medium-lightly.)
This all depends on “the conclusions we want to draw.” I don’t know which conclusions you want to draw, and surely the difference between these optimizers is not always irrelevant.
If I am, say, training a neural net, then I am definitely not going to be indifferent between Adam and SGD—Adam is way faster! And even if you don’t care about speed, just about asymptotic performance, the two find solutions with different characteristics, cf. the literature on the “adaptive optimization gap.”
The profusion of different SGD-like optimizers is not evidence that the differences between them don’t matter. It’s the opposite: the differences matter a lot, and that’s why people keep coming up with new variants. If all such optimizers were about the same, there’d be no reason to make new ones.
Or, consider that the analogy only holds for infinitesimal step size, on both sides[2]. Yet the practical efficacy of SGD has much to do with the fact that it works fine even at large step sizes, up to some breaking point.
Until we tie down what we’re trying to do, I don’t know how to assess whether any of these distinctions are (ir)relevant or (un)important.
On another note, the fact that the gradient “comes out of the maths” does not seem very noteworthy to me. It’s inevitable from the problem setup: everything is rotationally symmetric except f, and we’re restricted to function evaluations inside an ϵ-ball, so we can’t feel the higher-order derivatives of f. As long as we’re not analytically computing any of those higher derivatives, we should expect any direction appearing in the result to be a function of the gradient—it’s the only source of directionality available, the only thing that breaks the symmetry[3].
Here the function of the gradient is just the identity, but I expect you’d still deem it “acceptable” if it were not, since it would still fall into the “class” of optimizers that includes Adam etc. (For Adam, the function involves the gradient and the buffers computed from it, which in turn require the introduction of a privileged basis.)
By these standards, what optimizer isn’t equivalent to gradient descent? Optimizers that analytically compute higher-order derivatives, that’s all I can come up with. Which is a strange place to draw a line in the sand, IMO: “all 0th and 1st order optimizers are the same, but 2nd+ order optimizers are different.” Surely there are lots of important differences between different 0th and 1st order optimizers?
The nice thing about a true equivalence result is that it’s not context-dependent like this. All the details match, all at once, so we can readily apply the result in whatever context we like without having to check whether this context cares about some particular nuance that didn’t transfer.
We need this limit because the SGD step never depends on higher-order derivatives, no matter the step size. But a guess-and-check optimizer like selection can feel higher-order derivatives at finite step sizes.
Likewise, we should expect a scalar like the step size to be some function of the gradient magnitude, since there aren’t any other scalars in the problem (again, ignoring higher-order derivatives). I guess there’s f itself, but it seems natural to “quotient out” that degree of freedom by requiring the optimizer to behave the same way for f and f+c.
I no longer feel like I know what claim you’re advancing.
In this post and in recent comments (1, 2), you’ve said that you have proven an “equivalence” between selection and SGD under certain conditions. You’ve used phrases like “mathematically equivalent” and “a proof of equivalence.”
When someone tells me they have a mathematical proof that two things are equivalent, I read the word “equivalent” to mean “really, totally, exactly the same (under the right conditions).” I think this is a pretty standard way to interpret this kind of language. And in my critique, I argued—I think successfully—against this kind of equivalence.
From your latest comments, it appears that you are not claiming anything this strong. But now I don’t know what you are claiming. For instance, you write here:
Details that are “unimportant” in one context, or for making a particular argument, may be very important in some other context or argument[1]. To take one example:
This all depends on “the conclusions we want to draw.” I don’t know which conclusions you want to draw, and surely the difference between these optimizers is not always irrelevant.
If I am, say, training a neural net, then I am definitely not going to be indifferent between Adam and SGD—Adam is way faster! And even if you don’t care about speed, just about asymptotic performance, the two find solutions with different characteristics, cf. the literature on the “adaptive optimization gap.”
The profusion of different SGD-like optimizers is not evidence that the differences between them don’t matter. It’s the opposite: the differences matter a lot, and that’s why people keep coming up with new variants. If all such optimizers were about the same, there’d be no reason to make new ones.
Or, consider that the analogy only holds for infinitesimal step size, on both sides[2]. Yet the practical efficacy of SGD has much to do with the fact that it works fine even at large step sizes, up to some breaking point.
Until we tie down what we’re trying to do, I don’t know how to assess whether any of these distinctions are (ir)relevant or (un)important.
On another note, the fact that the gradient “comes out of the maths” does not seem very noteworthy to me. It’s inevitable from the problem setup: everything is rotationally symmetric except f, and we’re restricted to function evaluations inside an ϵ-ball, so we can’t feel the higher-order derivatives of f. As long as we’re not analytically computing any of those higher derivatives, we should expect any direction appearing in the result to be a function of the gradient—it’s the only source of directionality available, the only thing that breaks the symmetry[3].
Here the function of the gradient is just the identity, but I expect you’d still deem it “acceptable” if it were not, since it would still fall into the “class” of optimizers that includes Adam etc. (For Adam, the function involves the gradient and the buffers computed from it, which in turn require the introduction of a privileged basis.)
By these standards, what optimizer isn’t equivalent to gradient descent? Optimizers that analytically compute higher-order derivatives, that’s all I can come up with. Which is a strange place to draw a line in the sand, IMO: “all 0th and 1st order optimizers are the same, but 2nd+ order optimizers are different.” Surely there are lots of important differences between different 0th and 1st order optimizers?
The nice thing about a true equivalence result is that it’s not context-dependent like this. All the details match, all at once, so we can readily apply the result in whatever context we like without having to check whether this context cares about some particular nuance that didn’t transfer.
We need this limit because the SGD step never depends on higher-order derivatives, no matter the step size. But a guess-and-check optimizer like selection can feel higher-order derivatives at finite step sizes.
Likewise, we should expect a scalar like the step size to be some function of the gradient magnitude, since there aren’t any other scalars in the problem (again, ignoring higher-order derivatives). I guess there’s f itself, but it seems natural to “quotient out” that degree of freedom by requiring the optimizer to behave the same way for f and f+c.