AI Impacts Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Trends in algorithmic progress ======

// Published 01 March, 2017; last updated 07 October, 2017 //

<HTML>
<p>Algorithmic progress has been estimated to contribute fifty to one hundred percent as much as hardware progress to overall performance progress, with low confidence.</p>
</HTML>


<HTML>
<p>Algorithmic improvements appear to be relatively incremental.</p>
</HTML>


===== Details =====


<HTML>
<p><em>We have not recently examined this topic carefully ourselves. This page currently contains relevant excerpts and sources.</em></p>
</HTML>


<HTML>
<p><a href="https://intelligence.org/files/AlgorithmicProgress.pdf">Algorithmic Progress in Six Domains</a><span class="easy-footnote-margin-adjust" id="easy-footnote-1-784"></span><span class="easy-footnote"><a href="#easy-footnote-bottom-1-784" title="Grace, K. (2013), Algorithmic Progress in Six Domains, Machine Intelligence Research Institute, https://intelligence.org/files/AlgorithmicProgress.pdf"><sup>1</sup></a></span> measured progress in the following areas, as of 2013:</p>
</HTML>


<HTML>
<ul>
<li><div class="li">Boolean satisfiability</div></li>
<li><div class="li">Chess</div></li>
<li><div class="li">Go</div></li>
<li><div class="li">Largest number factored (<a href="/doku.php?id=ai_timelines:ai_inputs:progress_in_general_purpose_factoring">our updated page</a>)
                </div></li>
<li><div class="li">MIP algorithms</div></li>
<li><div class="li">Machine learning</div></li>
</ul>
</HTML>


<HTML>
<p>Some key summary paragraphs from the paper:</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">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</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">…</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">In recent <em>Boolean satisfiability</em> (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.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;"><em>Chess programs</em> 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.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;"><em>Go programs</em> 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.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">Improvements in a variety of <em>physics simulations</em> (selected after the fact to exhibit performance increases due to software) appear to be roughly half due to hardware progress.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">The <em>largest number factored</em> 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.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">Some <em>mixed integer programming</em> (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.</p>
</HTML>


<HTML>
<p style="padding-left: 30px;">Various forms of <em>machine learning</em> have had steeply diminishing progress in percentage accuracy over recent decades. Some vision tasks have recently seen faster progress.</p>
</HTML>


<HTML>
<p>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).</p>
</HTML>


==== Figures ====


<HTML>
<p>Below are assorted figures mass-extracted from <a href="https://intelligence.org/files/AlgorithmicProgress.pdf">Algorithmic Progress in Six Domains</a>, some more self-explanatory than others. See the paper for their descriptions.</p>
</HTML>




<HTML>
<ol class="easy-footnotes-wrapper">
<li><div class="li">
<span class="easy-footnote-margin-adjust" id="easy-footnote-bottom-1-784"></span>Grace, K. (2013), Algorithmic Progress in Six Domains, Machine Intelligence Research Institute, https://intelligence.org/files/AlgorithmicProgress.pdf<a class="easy-footnote-to-top" href="#easy-footnote-1-784"></a>
</div></li>
</ol>
</HTML>
AI Impacts Wiki

User Tools

Site Tools

Page Tools
