Google’s DeepMind has now introduced a new Artificial Intelligence system called AlphaTensor that could discover new efficient and provably correct algorithms for fundamental tasks such as matrix multiplication.
Dubbed AlphaTensor, the system could find the fastest way to multiply two matrices, a question that has remained open for half a century. In a paper published in the journal Nature, researchers said that improving the efficiency of algorithms for fundamental computations can have a widespread impact on the overall speed of many computations.
“AlphaTensor discovered algorithms that are more efficient than state-of-the-art for many matrix sizes. Our AI-designed algorithms outperform human-designed ones, which is a major step forward in the field of algorithmic discovery,” DeepMind said in a statement.
Researchers converted the problem of finding efficient algorithms for matrix multiplication into a single-player game, and the number of possible algorithms to consider is much greater than the number of atoms in the universe. They trained AlphaTensor agents using reinforcement learning to play the game, starting without any knowledge about existing matrix multiplication algorithms.
“Through learning, AlphaTensor gradually improves over time, re-discovering historical fast matrix multiplication algorithms such as Strassen’s, eventually surpassing the realm of human intuition and discovering algorithms faster than previously known. It improves on Strassen’s two-level algorithm in a finite field for the first time since its discovery 50 years ago. These algorithms for multiplying small matrices can be used as primitives to multiply much larger matrices of arbitrary size,” DeepMind said.