13 ms·
Risky Giant Steps Can Solve Optimization Problems Faster
- pama 3y agoI like how computational results occasionally generate unexpected answers that drive mathematicians to work out new theories.
- junon 3y agoScientific process, baby. This is how a lot of it works. Very rarely does the novel idea come very first.
- mistermann 3y agoThis processed has been adopted and formalized by science but has been used since pre-historic times.
- marmakoide 3y agoI glanced at the paper. Does the paper focus on semidefinite programming, where the objective function is linear, subjects to linear inequalities constraints ?
- ProfGrimmer 3y agoMy 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.
- bainsfather 3y agoI 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?
- yorwba 3y agoPrevious discussion: https://news.ycombinator.com/item?id=37100283 https://news.ycombinator.com/item?id=37100283 (22 comments, 1 day ago) https://news.ycombinator.com/item?id=36735590 https://news.ycombinator.com/item?id=36735590 (2 comments, 29 days ago)
- deleted 3y ago[deleted]
- asimpletune 3y agoForgive 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.
- chrisdbanks 3y agoYes. Outlier experiments vs incremental experiments. Sometimes you need to break out of a local maxima.
- notpachet 3y ago"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 https://youtu.be/OqEeIG8aPPk?t=591
- civilized 3y ago> 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.
- AbrahamParangi 3y agoI 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.
- civilized 3y agoThis 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.
- hnben 3y ago> 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)
- uoaei 3y agoRelated, and known (at least empirically) for a while, Lévy flight sampling methods: https://en.wikipedia.org/wiki/L%C3%A9vy_flight https://en.wikipedia.org/wiki/L%C3%A9vy_flight
- contravariant 3y agoIs 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.
- uoaei 3y agoYes, 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.
- jonnycat 3y agoTheir 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_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.
- marmakoide 3y agoThere 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.
- bell-cot 3y agoCritical 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.
- tbalsam 3y agoHi! 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.
- jeroenvlek 3y agoTo 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!
- xeonmc 3y agoAcerbic insight. However, what did you mean precisely by the community being a “scientific” one?
- jeroenvlek 3y agoYeah, 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.
- jasonjmcghee 3y agoLeslie 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 https://arxiv.org/abs/1708.07120
- quanto 3y agoThe 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.