The Algorithm for Hard Problems: Shake and Pull Gently

https://kazimuth.github.io/blog/post/shake-and-pull-gently/

by todsacerdoti • 4 years ago

137 13 4 years ago

kazimuth.github.io

stncls• 4 years ago

I like the explanation and video illustration of simulated annealing. Simulated annealing has varied and numerous applications. But calling it "The Only Algorithm for Hard Problems" is really giving it a lot of credit:

1. The animated graphic illustrating simulated annealing infuriates me. It is described (without calling it that) as solving a shortest Hamiltonian path problem. If you look at it, it is actually a shortest Hamiltonian cycle problem, aka. travelling salesman problem (TSP). TSP is the canonical example of problem that simulated annealing and other metaheuristics are terrible at solving [1]. Proper mathematically-justified algorithms like Lin-Kernighan-Helsgaun [2] give better (often optimal!) results orders of magnitude faster. You can even solve TSP (an NP-hard problem) with optimality guarantees with Concorde, at sizes that beggar belief [3].

2. Saying that stochastic gradient descent is kind-of the same as simmulated annealing is quite a stretch. Gradient descent attempts to give local optima, full stop. Quite the opposite of simulated annealing. Now, there is an art in ML in choosing the step size (learning rate) and starting point. But the "stochastic" part is necessary to make it work on the huge problems that DNN require, where computing a full gradient would be impossible. The claim that we use SGD to get better local optima is new to me.

3. The mention of SAT/SMT is making the analogy do a ton of work here. The article admits it, but still, I struggle to understand how backtracking, a recursive deterministic (full-search-space) enumerative algorithm has anything in common with simulated annealing, a randomized iterative heuristic.

[1] http://www.math.uwaterloo.ca/tsp/usa50/index.html

[2] http://webhotel4.ruc.dk/~keld/research/LKH/

[3] https://www.math.uwaterloo.ca/tsp/concorde.html

rocqua• 4 years ago

I could very well imagine that the random batching in stochastic gradient descent is great for regularizing and preventing local optima.

balddenimhero• 4 years ago

SAT/SMT solving is indeed a much more structured approach and I agree that the analogy does not work too well for the backtracking part. I think that it rather applies to the well-established incorporation of "restarts" of the search. Even thogh SAT/SMT solving is deterministic it still tries to avoid local maxima via such pseudo-random heuristics.

steppi• 4 years ago

I thought it was uncontroversial that stochastic gradient descent can offer at least some protection against getting trapped in an undesirable local minima. Even in 2011 when I took my first machine learning course we were taught that while SGD was first developed to make large problems more tractable, the noise introduced by evaluating the gradient on only a subset of the data can potentially help the solver escape local minima.

I don't think the analogy with simulated annealing is that much of a stretch. The learning rate is like temperature and it's pattern of decrease is like an annealing schedule. Each step is decided from the sampling distribution for the full gradient and there is a nonzero probability of climbing uphill. As the learning rate decreases the solver becomes more likely to get stuck in a local minima. See here [1] for instance, and here [2] for a more detailed discussion of how SGD can help escape local minima that goes beyond this analogy.

The analogy is incomplete and of course SGD can still get stuck in local minima, but my understanding is that there is a reasonable consensus that the noise introduced by SGD can help a solver find better local minima and the main area of contention is in trying to understand exactly why this is the case.

[1] https://leon.bottou.org/publications/pdf/nimes-1991.pdf

[2] https://proceedings.mlr.press/v80/kleinberg18a/kleinberg18a....

thorel• 4 years ago

Regarding stochastic gradient descent, I think there has been an increased understanding in recent years, that the randomness introduced by the random sampling/batching is not only helpful in reducing the computational cost (compared to computing the full gradient) but also in adding noise to escape local minima. Some variants of stochastic gradient descent in fact add some additional random noise to amplify this latter effect and some theoretical guarantees have started to emerge.

robocat• 4 years ago

The article is a passing reference to finding the shortest path of a graph using a physical model with strings tied together. Skip to 3:15 in this video to see: https://m.youtube.com/watch?v=2XRSxa03V5g

Analogue solvers are cool. I remember being told about cutting resistive paper to a shape and using electricity current to model water flow (voltage at any point ≈ height of water). https://en.m.wikipedia.org/wiki/Resistance_paper It would be so cool to model a grid of electric components using water flow!

bbbuibuild• 4 years ago

I used Simulated Annealing to help a Telecom plan a mobile & fibre network by connecting existing fibres & pipes.

There were tricky parameters - Simulated annealing was better/faster than a human for a small area - e.g. a few suburbs. For a larger area like a metropolitan area we haven't got the algorithm to compete well versus human network planner (yet?).

woevdbz• 4 years ago

This is an excellent metaphor, and I would note that the annealing strategy of always taking the good choices, and randomly accepting some bad choices too, also applies in career choices or life choices. Sometimes when you find yourself tangled up in a knot / stuck in a rut careerwise or lifewise, occasionally making a jump to something different — not necessarily something better — can give your life the kinetic energy it needs to find a better maximum. And as with annealing, the payoff of doing so early in life is higher than doing so late, so one should do more of it while young than as one gets older (if one chooses to optimize their life, that is).

swayvil• 4 years ago

I guess you'd call that "white action". Like white noise but amplified. Like regular action but noisified.

hexane360• 4 years ago

One small correction: "“Annealing” is a process where you heat slowly and cool metal to harden it."

Annealing is actually a process to soften metal (and sometimes to remove internal stresses), decreasing strength but increasing ductility and toughness. Like simulated annealing, higher temperature allows the material to jump over larger metastable hills in order to reach a more relaxed, lower energy structure.

In annealing, the temperature usually needs to be lowered slowly, because cooling introduces stresses and, to a lesser degree, because the thermodynamically favorable structure changes with temperature. Quenching (cooling quickly) creates residual thermal stresses, and locks in the high temperature structure, which is metastable at lower termperatures.

belugacat• 4 years ago

Interesting article, but you’ll notice he adjusts his grip around 0”12 because if he had kept just shaking and gently pulling they’d still have knotted. Similarly, the initial grip is already biased a certain way.

That human intuition about the physical system isn’t really captured in the algorithm. I’d be curious what rate of success a machine that truly just “shakes and pulls” would have in untangling headphones.

lqr• 4 years ago

Simulated annealing is still prone to getting stuck in local minima if the steps during the high-temperature phase are unlucky.

It's always worth trying a multi-start approach, i.e. run the same algorithm more than once (in parallel if possible) with different random initial guesses. If your problem is differentiable, then multi-start continuous optimization (gradient descent, Newton's method, etc.) can be more efficient than something like SA.

krispyfi• 4 years ago

Here is the same concept applied to the mind: https://qri.org/blog/neural-annealing#on-psychedelics

"Heat up" your mind with meditation, music and/or psychedelics, and allow it to "cool" into a less maladaptive configuration.

The Algorithm for Hard Problems: Shake and Pull Gently

Related Stories