Fall 2022 Guest Seminar - Amin Barekatain

AlphaTensor: Discovering Novel Algorithms with Reinforcement Learning by Amin Barekatain, Senior Research Engineer at Google’s DeepMind

Abstract:   Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems — from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. In this talk, I present a deep reinforcement learning approach based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. The agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. 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 further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. The results showcase AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.

Biography: Amin Barekatain is 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, New Scientist, 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.

If you would like to meet the speaker, please email mics@ucsd.edu