Deepmind Introduces ‘AlphaTensor,’ An Artificial Intelligence (AI) System For Discovering Novel, Efficient And Exact Algorithms For Matrix Multiplication

Improving the efficiency of algorithms for fundamental computations is a crucial task nowadays as it influences the overall pace of a large number of computations that might have a significant impact. One such simple task is matrix multiplication, which can be found in systems like neural networks and scientific computing routines. Machine learning has the potential to go beyond human intuition and beat the most exemplary human-designed algorithms currently available. However, due to the vast number of possible algorithms, this process of automated algorithm discovery is complicated. DeepMind recently made a breakthrough discovery by developing AplhaTensor, the first-ever artificial intelligence (AI) system for developing new, effective, and indubitably correct algorithms for essential operations like matrix multiplication. Their approach answers a mathematical puzzle that has been open for over 50 years: how to multiply two matrices as quickly as possible. 

AlphaZero, an agent that showed superhuman performance in board games like chess, go, and shogi, is the foundation upon which AlphaTensor is built. The system expands on AlphaZero’s progression from playing traditional games to solving complex mathematical problems for the first time. The team believes this study represents an important milestone in DeepMind’s objective to improve science and use AI to solve the most fundamental problems. The research has also been published in the established Nature journal. 

Matrix multiplication has numerous real-world applications despite being one of the most simple algorithms taught to students in high school. This method is utilized for many things, including processing images on smartphones, identifying verbal commands, creating graphics for video games, and much more. Developing computing hardware that multiplies matrices effectively consumes many resources; therefore, even small gains in matrix multiplication efficiency can have a significant impact. The study investigates how the automatic development of new matrix multiplication algorithms could be advanced by using contemporary AI approaches. In order to find algorithms that are more effective than the state-of-the-art for many matrix sizes, AlphaTensor further leans on human intuition. Its AI-designed algorithms outperform those created by humans, which represents a significant advancement in algorithmic discovery.

The first step in developing the algorithm was creating a single-player game out of the problem of finding effective matrix multiplication methods. The game’s board is a three-dimensional tensor to measure how inaccurate the present algorithm is. The player tries to alter the tensor and zero out its entries by using a set of permitted moves that match algorithm instructions. When the player succeeds in doing so, this produces a matrix multiplication algorithm that can be proven accurate for any pair of matrices. Its effectiveness is measured by the number of steps required to zero out the tensor.

However, this game is very challenging compared to other conventional board games. Even for simple examples of matrix multiplication, there are more alternative algorithms to consider in this game than atoms in the universe. The DeepMind team first created several essential elements, including a novel neural network architecture that incorporates problem-specific inductive biases, a method to produce valuable synthetic data, and a recipe to take advantage of the problem’s symmetries to tackle the game’s challenges. After that, an AlphaTensor agent was taught to play the game using reinforcement learning, starting with no prior knowledge of the existing matrix multiplication techniques. The agent learns as it goes along, eventually surpassing human intuition and learning faster than previously known algorithms, including historical fast matrix multiplication algorithms like Strassen’s.

Furthermore, AlphaTensor’s algorithm is the first to outperform Strassen’s two-level approach in a finite field since it was discovered fifty years ago. These simple matrix multiplication techniques can be used as primitives to multiply significantly larger matrices of any dimension. AlphaTensor also unearths a broad range of state-of-the-art complexity algorithms, up to thousands for each size of matrix multiplication, demonstrating that the space of matrix multiplication algorithms is richer than previously believed. These methods demonstrate AlphaTensor’s adaptability in optimizing arbitrary objectives by multiplying big matrices 10–20% quicker than the conventional algorithms on the same hardware.

In order to identify the most efficient algorithms for handling computer challenges, the researchers hope their findings will serve as a stepping stone for future complexity theory research. Because matrix multiplication is a fundamental operation in many computations, techniques developed by AlphaTensor may significantly improve the efficiency of computations in various areas. The system’s adaptability to consider any form of purpose may inspire new applications for developing algorithms that optimize metrics like energy consumption and numerical stability. Even though the research was concentrated on the specific problem of matrix multiplication, DeepMind hopes to encourage others to apply AI to direct the development of algorithms for other essential computational jobs. Their research also demonstrates how AlphaZero is a potent algorithm that may be applied far beyond the realm of conventional games to assist in the solution of open issues in mathematics. The group aspires to use AI in the future to assist society in resolving some of the most significant problems in science and mathematics.

This Article is written as a research summary article by Marktechpost Staff based on the research preprint-paper 'Discovering faster matrix multiplication algorithms with reinforcement learning'.  All Credit For This Research Goes To Researchers on This Project. Check out the paper and deepmind article.

Please Don't Forget To Join Our ML Subreddit