Trends in algorithmic progress

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.

Page-27-Image-1311 Page-28-Image-1394 Page-29-Image-1395 Page-31-Image-1396 Page-32-Image-1397 Page-40-Image-1827 Page-41-Image-1828 Page-42-Image-1829 Page-43-Image-1830 Page-43-Image-1831 Page-47-Image-1832 Page-48-Image-1833 Page-48-Image-1834 Page-49-Image-1835 Page-50-Image-1836 Page-51-Image-1837 Page-51-Image-1838 Page-52-Image-1839 Page-52-Image-1840 Page-53-Image-1841 Page-53-Image-1842 Page-54-Image-1843 Page-54-Image-1844

  1. Grace, K. (2013), Algorithmic Progress in Six Domains, Machine Intelligence Research Institute, https://intelligence.org/files/AlgorithmicProgress.pdf

Be the first to comment

Leave a Reply

Your email address will not be published.


*