It is the first AI system capable of finding new algorithms for elementary tasks like matrix multiplication that are both efficient and provably right.
In today’s world, where the speed of a large number of computations can have a major impact, optimising algorithms for fundamental computations is an important effort. Matrix multiplication is an example of a system that performs this type of straightforward operation, and it is used in several contexts, including neural networks and scientific computing. Machine learning has the potential to outperform even the most impressive algorithms developed by humans. However, the enormous number of alternative algorithms makes the process of automated algorithm discovery difficult. Recently, DeepMind made a ground-breaking discovery when they created AplhaTensor, the first artificial intelligence (AI) system capable of creating novel, efficient, and unarguable right algorithms for fundamental operations like matrix multiplication. Their method solves a problem in mathematics that has persisted for more than 50 years: how to multiply two matrices as efficiently as feasible.
AlphaTensor is based on AlphaZero, an agent that demonstrated superhuman ability in board games like chess, go, and shogi. Expanding on AlphaZero’s earlier forays into solving simple games, the approach enables it to go on to more difficult mathematical issues. Team members see this research as a major step toward achieving DeepMind’s mission to advance scientific knowledge and apply AI to tackle the world’s most pressing challenges. The study was published in the prestigious Nature journal as well.
Matrix multiplication is one of the simplest algorithms introduced to high school students, yet it has many practical uses. This technique is used for a wide range of applications, from image processing on smartphones and recognising voice instructions to making game visuals. Due to the high cost of developing efficient computer hardware for matrix multiplication, even modest improvements in this area can have a major bearing on the field. The research looks into how modern AI techniques can be used to improve the automatic development of novel algorithms for matrix multiplication. AlphaTensor further relies on human intuition to create algorithms that are more successful than the state-of-the-art for numerous matrix sizes. Its artificial intelligence-designed algorithms are superior to those developed by humans, marking a major step forward in algorithmic discovery.
The process of designing the algorithm started with turning the quest for efficient matrix multiplication techniques into a single-player game. The current algorithm’s accuracy is represented on a three-dimensional tensor playing field. Using a limited number of actions that conform to the algorithm’s directives, the player attempts to modify the tensor and render all of its entries null. When the player accomplishes this, a matrix multiplication algorithm is generated that can be verified as correct for any given set of matrices. The number of operations needed to cancel the tensor is a quantitative indicator of its efficiency.
This is a board game, but it’s a lot harder than the average board game. There are more possible algorithms in this game than atoms in the cosmos, and that’s just for basic operations like matrix multiplication. Prior to tackling the game’s obstacles, the DeepMind team developed a novel neural network design that integrates problem-specific inductive biases, a way to produce important synthetic data, and a recipe to exploit the problem’s symmetries. After then, a reinforcement learning system was used to coach an AlphaTensor agent through the game without the aid of any prior knowledge of the aforementioned matrix multiplication techniques. As it progresses, the agent acquires the ability to learn at a rate that exceeds human intuition and outpaces all known algorithms, even historical rapid matrix multiplication techniques such as Strassen’s.
In addition, since its discovery fifty years ago, Strassen’s two-level technique in a finite field has never been surpassed until AlphaTensor’s algorithm. These straightforward methods of matrix multiplication can serve as building blocks when multiplying matrices of higher dimensions. Furthermore, AlphaTensor finds thousands of state-of-the-art complexity algorithms for each matrix size, proving that the space of matrix multiplication methods is more diverse than was previously thought. These approaches multiply large matrices 10-20% faster than traditional algorithms on the same hardware, demonstrating AlphaTensor’s flexibility in optimising arbitrary objectives.
Researchers are hopeful that their work will pave the way for additional study of complexity theory, which could help in the identification of the most effective algorithms for tackling computer difficulties. Techniques developed by AlphaTensor may considerably increase the efficiency of computations in many fields, as matrix multiplication is a fundamental operation in many computations. Because of the system’s flexibility, it could be used in novel contexts, such as the design of algorithms that maximise energy efficiency and numerical stability. Although DeepMind’s study focused on the challenge of matrix multiplication, the company believes that its work will inspire others to use artificial intelligence to steer the development of algorithms for other crucial computer tasks. Their findings also show that AlphaZero is a powerful algorithm with potential uses well beyond the area of traditional games, including contributing to the solution of unresolved problems in mathematics. The team’s long-term goal is to employ AI to help solve some of the world’s toughest scientific and mathematical challenges.
