Risky Giant Steps Can Solve Optimization Problems Faster | Hacker News Reader

Risky Giant Steps Can Solve Optimization Problems Faster

quantamagazine.org

75 pointssonabinu31 comments

> 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.

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.

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.

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).

What are your thoughts on Sophia, an algorithmic replacement for ADAM which promises to converge in fewer steps?

https://arxiv.org/abs/2305.14342

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.

https://arxiv.org/abs/2307.06440

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 :))))

Critical bit:

> However, while these insights may change how researchers think about gradient descent, they likely won’t change how the technique is currently used. Grimmer’s paper focused only on smooth functions, which have no sharp kinks, and convex functions, which are shaped like a bowl and only have one optimal value at the bottom. These kinds of functions are fundamental to theory but less relevant in practice; the optimization programs machine learning researchers use are usually much more complicated...

And machine learning is by no means the only area in which the "real world" curves subject to optimization have, ah, "problematic" shapes.

Forgive me if this sounds naive but it sort of reminds me of life in a way. I equate these little steps to the way most of our industries or institutions focus on producing incremental and predictable progress. In such an environment many of the power gives way to manager and administrator type participants. Think of academia or how most of tech has become (ie sass).

On the other hand, while that is certainly useful, it pales in comparison to that being combined with a non-linear aoproach, where you’re not trying to optimize a known process but fundamentally rethink the question altogether. To me that’s reminiscent of physics in the early twentieth century, democracy and liberal economies during the enlightenment, and even modern literature, in a sense, like Joyce.

I don’t really have a point beyond that, and it’s just an analogy after all. It’s still neat to think about and recognize similarities between a discovery in the computational world and a personal observation about our own world. Even if it’s a misguided analogy, it feels true.

"Continuous improvement isn't nearly as important as discontinuous improvement. Creativity is a discontinuity. A creative act breaks with the chain that has come before it. It's not continuous. One never becomes a leader by continuously improving -- that's imitation of the leader. You never become a leader by imitating them and improving slightly. You only become a leader by leapfrogging those who are ahead of you. And that comes about through creativity."

-- Russ Ackoff

https://youtu.be/OqEeIG8aPPk?t=591

Yes. Outlier experiments vs incremental experiments. Sometimes you need to break out of a local maxima.

Their mathematical analysis is for sure beyond my understanding, but on some level, I'm surprised this is surprising. While baby steps may be the norm in gradient descent, there are plenty of there optimization techniques that embrace larger step sizes. Some, like simulated annealing, explicitly model changes in step size over time. Others, like genetic algorithms with crossover let the balance between exploration (big steps) vs exploitation (small steps) emerge more organically.

In fact, applying the idea of "no free lunch in search and optimization" (https://en.wikipedia.org/wiki/No_free_lunch_in_search_and_op...), you'd kind of expect this result: sometimes big steps good, sometimes big steps bad.

There are fairly old takes on that idea. For example, the evolutionary algorithm community knew the relevance of using steps size drawn from a Cauchy distribution, for example "Evolutionary Programming Made Faster", Xin Yao et al., 1999.

Previous discussion:

https://news.ycombinator.com/item?id=37100283 (22 comments, 1 day ago)

https://news.ycombinator.com/item?id=36735590 (2 comments, 29 days ago)

Hi! I've worked a lot with ML algorithms, and I believe this is tied in with regret. Not only do huge steps (after an initial warmup) get to a rough minimum faster, due to the energy involved, the minimum found tends to be more shallow, because the parameters jitter around so much during training.

It sort of makes sense too as you're approaching a finite goal in an optimization problem -- first, tiny steps to take any initial steps that might be huge due to any initialization differences, then annealing up to huge steps, then small steps again as you approach the end of your optimization process, and your signal:noise ratio is much lower.

The overshooting and correcting pattern (and 'fractal' therein) can be understood analogously by considering the binary search tree. The tree is fractal (i.e. sub trees) and each step may overshoot until the solution is found.

This analogy can be made rigorous by looking at bisection search on a convex function instead of a simple binary search tree. The same pattern holds. "Fractal" patterns occur because the problem is invariant under scaling.

What is interesting is the initial half of small steps. I have not read the original paper to give a professional view on the mathematics, but it may just be that initial small steps are priming the optimizer to find the right scale.

Unfortunately, it may just be that the findings are not something fundamental to gradient descent or optimization in general, but just an observed property of the smooth convex cost function considered under this particular algorithmic investigation.

To me this is a bit exemplary of how science sometimes gets functional myopia. Conceptionally obvious: Playing with step sizes gives you higher chance of getting closer to the global (not local) optimum initially, because you can scout , but you want to get your algorithm working, so let's slap on a heuristic and let's first converge for local optima with learning rate decay. Then most people in the scientific community seem to forget (for example) about this heuristic, because it's Always Been There and direct all their focus on improving the status quo, forgetting that the assumption we put there is also a construction area. Lumpers and splitters, I guess. This sounds bitter, I'm actually happy Mr. Grimmer took this on!

Acerbic insight. However, what did you mean precisely by the community being a “scientific” one?

Yeah, agreed that it was a bit sour. I'm actually optimistic by nature ;)

I meant that in academia sometimes some theories are taken for granted and land in a blind spot for improvement. But yeah, that's definitely not limited to academia. Technical debt is every where.

Related, and known (at least empirically) for a while, Lévy flight sampling methods:

https://en.wikipedia.org/wiki/L%C3%A9vy_flight

Is that when you use a Lévy flight in some kind of MCMC algorithm, or is it something else? The wikipedia article doesn't say much about using it for sampling.

Yes, essentially it is a random walk (i.e. Monte Carlo method, suitable for use in MCMC).

The general principle/innovation is to use power-law or similarly heavy-tailed distributions for step lengths as opposed to constant, Gaussian, etc. step lengths for the purpose of exiting local minima.

Leslie Smith has a number of great papers- this one is particularly relevant. I believe he coined the term “super-convergence” in the space of training neural networks. Same idea- using very large learning rates post-warmup can speed up training an order of magnitude. https://arxiv.org/abs/1708.07120

I like how computational results occasionally generate unexpected answers that drive mathematicians to work out new theories.

Scientific process, baby. This is how a lot of it works. Very rarely does the novel idea come very first.

This processed has been adopted and formalized by science but has been used since pre-historic times.

> Grimmer found that the fastest sequences always had one thing in common: The middle step was always a big one.

So... it's like binary-search, but you don't know the maximum before hand? (i.e. you double the step size until you overshoot, then do regular binary search from there)

I glanced at the paper. Does the paper focus on semidefinite programming, where the objective function is linear, subjects to linear inequalities constraints ?

My paper gives guarantees for any smooth convex minimization problem. The semidefinite programming is needed to solve a meta-optimization problem in the analysis of these generic problems. It's a tool rather than the target.

I read the Quanta article because I am interested in optimisations for deep neural nets.

Am I right in concluding that your work doesn't apply to that area, as it is looking at a much 'easier' case?

Reply on news.ycombinator.com