Computer science: Artificial intelligence boosts algorithm efficiency

The automated discovery of algorithms for multiplication of matrices, using a deep reinforcement learning approach devised by DeepMind, is reported in Nature this week. This approach quickly re-discovers the best currently known algorithms, but also new ones that are faster than any previous human and computer-designed algorithms. The findings highlight the potential of deep reinforcement learning for finding new approaches for solving more efficiently existing computational tasks.

Improving the efficiency of algorithms that execute fundamental computational operations can affect the overall speed of a large number of computations. Alhussein Fawzi and colleagues describe a deep reinforcement learning approach for the automated discovery of algorithms for an important primitive computational task: matrix multiplication, which is routinely used in vast arrays of computations. The system, named AlphaTensor, is tasked with playing a game in which the goal is to find the best way to multiply two matrices (arrays of numbers). This game is far more challenging than traditional games (such as chess or Go), requiring around one trillion more actions in some cases. AlphaTensor identifies previously known algorithms (thereby proving the system works) as well as finding completely new algorithms. In some cases, the discoveries improve upon algorithms that haven’t been improved for more than 50 years despite much research. Furthermore, AlphaTensor could be optimized to discover algorithms that work particularly well in certain circumstances, for running on specific types of computers.

The authors note some limitations to their system, such as it needing some predefined components that may cause it to miss a subset of efficient algorithms. However, AlphaTensor’s discoveries could improve computational tasks that use multiplication algorithms as well as demonstrate how reinforcement learning can be used to find new and unexpected solutions to known problems.