3 ms·
I like the explanation and video illustration of simulated annealing. Simulated annealing has varied and numerous applications. But calling it "The Only Algorit
by stncls 4y 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 http://www.math.uwaterloo.ca/tsp/usa50/index.html
[2] http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/
[3] https://www.math.uwaterloo.ca/tsp/concorde.html https://www.math.uwaterloo.ca/tsp/concorde.html
- rocqua 4y agoI could very well imagine that the random batching in stochastic gradient descent is great for regularizing and preventing local optima.
- balddenimhero 4y agoSAT/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 4y agoI 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 https://leon.bottou.org/publications/pdf/nimes-1991.pdf [2] https://proceedings.mlr.press/v80/kleinberg18a/kleinberg18a.pdf https://proceedings.mlr.press/v80/kleinberg18a/kleinberg18a....
- thorel 4y agoRegarding 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.