Title: AlphaTensor: Algorithm Discovery using Reinforcement Learning
Abstract: Improving the efficiency of algorithms for fundamental computational tasks such as matrix multiplication can have widespread impact, as it affects the overall speed of a large amount of computations. Automatic discovery of algorithms using ML offers the prospect of reaching beyond human intuition and outperforming the current best human–designed algorithms. In this talk I’ll present AlphaTensor, our RL agent based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. AlphaTensor discovered algorithms that outperform the state–of–the–art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two–level algorithm for the first time since its discovery 50 years ago. I’ll present our problem formulation as a single–player game, the key ingredients that enable tackling such difficult mathematical problems using RL, and the flexibility of the AlphaTensor framework.
Bio: Amin Barekatainis a Senior Research Engineer at Google’s DeepMind in London. He received his master’s degree in Computer Science from the Technical University of Munich with the highest honors. His research interests broadly include reinforcement learning, focusing on AlphaZero/MuZero algorithms and their applications in Mathematics and Algorithmic Discovery. Amin’s latest work, AlphaTensor — featured in Nature front cover, Science’s Top 10 Breakthroughs of 2022, and The Independent — discovers new, faster, and exact Matrix Multiplication algorithms beating a 50–year–old record in Computer Science and Mathematics. Moreover, Amin has published relevant research at top machine learning venues, including NeurIPS (spotlight publication), ICML, and IJCAI.