True Stories of Algorithmic Improvement - LessWrong

In May 2020, OpenAI released a report on algorithmic efficiency improvements in deep learning. Main headline: Compared to 2012, it now takes 44 times less compute to train a neural network to the level of AlexNet (by contrast, Moore’s Law would yield an 11x cost improvement over this period). Our results suggest that for AI tasks with high levels of recent investment, algorithmic progress has yielded more gains than classical hardware efficiency. A lot people were surprised by this; there’s a common narrative in which AI progress has come mostly from throwing more and more compute at relatively-dumb algorithms. (This is a common interpretation of The Bitter Lesson, though I would argue it is largely a misinterpretation.) I’ve had various experiences over the years which made the result not-that-surprising. Algorithms beating compute is the sort of thing I expect by default, on a gut level. The point of this post is to tell a few of the stories which underlie that intuition, aimed especially toward people who don’t have much first-hand experience with software engineering, ML, or simulation. (There will still be some jargon, though.) Disclaimer: this does not mean that you should put tons of confidence on this view. The goal is just to provide a possible lens through which “algorithmic progress has yielded more gains than classical hardware efficiency” makes sense; I want to raise that hypothesis from entropy. I’m not going to provide the sort of evidence which would justify very high confidence, I’m just going to point it out as a hypothesis to keep in the back of your mind, and update on when results like OpenAI’s come along. REWRITE IN C Back in college, I spent a summer simulating an unusual type of biochemical oscillator, officially under the aegis of the Minnesota Supercomputing Institute. The algorithm was conceptually simple: every time a reaction occurs between two molecules, update the counts of each molecule, then randomly sample to figure out when th