AlphaTensor: DeepMind’s Ingenious Phenom
Artificial Intelligence altering the course of the world, yet again!
On October 5, 2022 something phenomenal happened that is going to change the way we will be thinking about algorithmic discovery forever. DeepMind’s (a British AI Subsidiary of Alphabet Inc) latest piece of research got published in Nature (the world’s leading multi-disciplinary science journal), titled “Discovering faster matrix multiplication algorithms with reinforcement learning”, and the very next day, this amazing piece of work made the front page of Nature’s weekly issue. In this blog, we’ll delve deeper into what this phenomenal work has achieved, and how it is going to amplify the usefulness of every algorithm existing on the face of the Earth that relies on the fundamental concept of Matrix Multiplication.
What is AlphaTensor?
Each and everyone of us, irrespective of the field that we are pursuing has come across algorithms, and most of us use them on a daily basis without giving a second thought. Ranging from algorithms that we learnt about in our play school such as Addition, Subtraction, Multiplication and Division to algorithms that have helped bring many scientific inventions to reality such as Fast Fourier Transform (FFT), these algorithms span over what some may call an “infinite space”, or in other words, their use cases are simply uncountable. However, till now, these algorithms have been discovered majorly by humans!
But now, there is a new contender! In their paper, DeepMind has introduced AlphaTensor, the first AI system for discovering novel, efficient, and provably correct algorithms for fundamental tasks such as matrix multiplication. The process of “cooking” new algorithms is an incredibly challenging task, but the researchers at DeepMind have come up with an AI system, that has not only been able to tackle this formidable task, but at the same time, discovered a new algorithm for matrix multiplication which has broken records set decades ago by humans.
Key insights into AlphaTensor
- AlphaTensor is a Deep Reinforcement Learning (DRL) approach based on AlphaZero for discovering optimal (relative to existing ones) algorithms for multiplication of arbitrary matrices.
- It discovered optimal algorithms for many matrix sizes. A special case is of 4 x 4 matrices, where the discovered algorithm improves on Strassen’s two-level algorithm for the first time since it’s inception.
- It offers wide applicability. It finds efficient matrix multiplication algorithms tailored to specific hardware, by optimizing for actual runtime.
- A limitation of AlphaTensor is the need to pre-define a set of potential factor entries F, which discretizes the search space but can possibly lead to missing out on efficient algorithms. The researchers at DeepMind look forward to adapt AlphaTensor to search for F.
How the algorithms are discovered?
- The matrix multiplication algorithm discovery procedure is formulated as a single-player game, called TensorGame, at each step of which, the agent (or the player) selects how to combine different entries of the matrices.
- Based on the number of selected operations required to reach the correct multiplication result, a score is assigned to each step.
- Once the TensorGame is developed, AlphaTensor (a DRL agent) is trained to solve this game. Unlike traditional games like Chess and Go (~100 actions), this game has a humongous action space (~10¹² actions).
- AlphaTensor uses a specialized neural network architecture which exploits the symmetries of the problem and makes use of synthetic training games.
Improvements made by AlphaTensor
Sizedenotes the matrix multiplication problem. For instance, (2, 2, 3) denotes a problem in which a (2, 2) matrix needs to be multiplied with a (2, 3) matrix.- The complexity is measured by the number of scalar multiplications (or the number of terms in the decomposition of the tensor).
Best rank knownrefers to the best known upper bound on the tensor rank (till now), and theAlphaTensor Rankrefers to the upper bounds on the rank obtained with AlphaTensor.- The improvements achieved by AlphaTensor are shown in red.
Conclusion 👋
I wrote this blog with the aim of providing a brief summary of this latest discovery, and it skips nearly all the beautiful mathematics behind this ingenious piece of work. If you are interested in knowing more about what is happening behind the curtains, do check out the original paper (referenced earlier). Additionally, you can check out the other references as well mentioned towards the end of this blog for gaining a more enhanced understanding of this research work, and perhaps, you might end up incorporating this into your own work to achieve state-of-the-art performance in your domain.
I really hope that you liked this blog, and if you did, do put your hands together 👏 and if you would like to read more blogs, then #StayTuned. Connect with me on LinkedIn and Twitter.
