Discovering faster matrix multiplication algorithms with reinforcement learning
Problem
Discovering more efficient matrix multiplication algorithms is hard because the space of possible algorithms is enormous and human intuition is limited.
Why it matters
Matrix multiplication speed affects the overall speed of a large amount of computation, from neural networks to scientific computing.
What the AI did
AlphaTensor, a deep reinforcement learning agent based on AlphaZero, plays a single-player game of finding tensor decompositions to discover efficient, provably correct matrix multiplication algorithms.
Results
Discovered provably correct algorithms that outperform the state-of-the-art for matrix multiplication (abstract truncated before specific figures).
Impact
Machine-discovered algorithms outperform the best human-designed ones for a fundamental computation.
Record
| Venue | Nature |
|---|---|
| Published | 2022 |
| Work type | article |
| Authors | Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera‐Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz et al. |
| Citations | 476 (OpenAlex, at import time) |
| References | 45 |
| Model or method | AlphaTensor (deep reinforcement learning, based on AlphaZero) |
| Organization | not stated in source |
| Primary source | https://doi.org/10.1038/s41586-022-05172-4 |
| Open access | hybrid |
| Keywords | matrix multiplication, reinforcement learning, AlphaTensor, algorithm discovery, tensor decomposition |
Importance rating
significant — thousands to millions affected
Abstract states improving such fundamental computations can have widespread impact on overall speed of large amounts of computation, from neural networks to scientific computing; first improvement on Strassen's algorithm in 50 years for a case.
More in Mathematics
| # | Paper | Year | Citations | Importance |
|---|---|---|---|---|
| 1 | Solving olympiad geometry without human demonstrations | 2024 | 307 |
7
|
| 2 | Mathematical discoveries from program search with large language models | 2023 | 509 |
6
|
| 3 | Superhuman AI for multiplayer poker | 2019 | 583 |
6
|
| 4 | Efficient generator of mathematical expressions for symbolic regression | 2023 | 20 |
4
|
| 5 | Symbolic regression as a feature engineering method for machine and deep learning regression tasks | 2024 | 19 |
4
|