Discovering new algorithms for mathematical problems with AlphaTensor

Nature published a new article about AlphaTensor from DeepMind. It is the first artificial intelligence (AI) system to discover new, efficient, and provably correct algorithms for fundamental problems such as matrix multiplication. The AlphaTensor system is based on AlphaZero, an agent that has shown superhuman performance in board games such as chess, go, and shogi.

AlphaTensor's development shows how advanced artificial intelligence techniques can help automatically discover new matrix multiplication algorithms used to process images on smartphones, recognize speech commands, create graphics for computer games, run simulations to predict the weather, and compress data and video for sharing on the Internet.

AlphaTensor has discovered more efficient algorithms than exist today for many matrix sizes. All thanks to the fact that the system is trained to play a game that transforms the problem of finding efficient matrix multiplication algorithms. Using a set of allowed moves corresponding to the algorithm's instructions, the player tries to change the tensor and zero out his entries. If the player succeeds, he obtains a proof-correct matrix multiplication algorithm for any pair of matrices, and his efficiency is determined by the number of steps spent on tensor zeroing.

This is quite a complex game, quite different from traditional games. To solve the problems in this area, the developers have come up with several critical components, including a new neural network architecture that takes into account the inductive biases specific to the problem, a procedure for generating useful synthetic data, and a recipe for using the symmetries of the problem.

A model of a neural network that can solve university-level mathematical problems in a few seconds at the human level has previously been presented. The capabilities of AI in the field of mathematics are impressive!