Table of Contents
Trends in algorithmic progress
Published 01 March, 2017; last updated 07 October, 2017
Algorithmic progress has been estimated to contribute fifty to one hundred percent as much as hardware progress to overall performance progress, with low confidence.
Algorithmic improvements appear to be relatively incremental.
Details
We have not recently examined this topic carefully ourselves. This page currently contains relevant excerpts and sources.
Algorithmic Progress in Six Domains1 measured progress in the following areas, as of 2013:
- Boolean satisfiability
- Chess
- Go
- Largest number factored (our updated page)
- MIP algorithms
- Machine learning
Some key summary paragraphs from the paper:
Many of these areas appear to experience fast improvement, though the data are often noisy. For tasks in these areas, gains from algorithmic progress have been roughly fifty to one hundred percent as large as those from hardware progress. Improvements tend to be incremental, forming a relatively smooth curve on the scale of years
…
In recent Boolean satisfiability (SAT) competitions, SAT solver performance has increased 5–15% per year, depending on the type of problem. However, these gains have been driven by widely varying improvements on particular problems. Retrospective surveys of SAT performance (on problems chosen after the fact) display significantly faster progress.
Chess programs have improved by around fifty Elo points per year over the last four decades. Estimates for the significance of hardware improvements are very noisy but are consistent with hardware improvements being responsible for approximately half of all progress. Progress has been smooth on the scale of years since the 1960s, except for the past five.
Go programs have improved about one stone per year for the last three decades. Hardware doublings produce diminishing Elo gains on a scale consistent with accounting for around half of all progress.
Improvements in a variety of physics simulations (selected after the fact to exhibit performance increases due to software) appear to be roughly half due to hardware progress.
The largest number factored to date has grown by about 5.5 digits per year for the last two decades; computing power increased ten-thousand-fold over this period, and it is unclear how much of the increase is due to hardware progress.
Some mixed integer programming (MIP) algorithms, run on modern MIP instances with modern hardware, have roughly doubled in speed each year. MIP is an important optimization problem, but one which has been called to attention after the fact due to performance improvements. Other optimization problems have had more inconsistent (and harder to determine) improvements.
Various forms of machine learning have had steeply diminishing progress in percentage accuracy over recent decades. Some vision tasks have recently seen faster progress.
Note that these points have not been updated for developments since 2013, and machine learning in particular is generally observed to have seen more progress very recently (as of 2017).
Figures
Below are assorted figures mass-extracted from Algorithmic Progress in Six Domains, some more self-explanatory than others. See the paper for their descriptions.
