Alhussein Fawzi, Matej Balog, Aja Huang
Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis, Pushmeet Kohli
2022 · Nature
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. Here we report a deep reinforcement learning approach based on AlphaZero 1 for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our 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, to our knowledge, since its discovery 50 years ago 2 . We 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. Our results highlight AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.
Metadata: Crossref. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
7 selected excerpts · 7 total mentions
> For a processor with well-documented microarchitecture, for which a programmer or a compiler can deterministically write an optimal program We don't even know the optimal algorithms! AlphaEvolve recently found "an algorithm to multiply 4x4 complex-valued matrices using 48 scalar multiplications, improving upon Strassen’s 1969 algorithm that was previously known as the best in this setting." - https://www.nature.com/articles/s41586-022-05172-4
See: https://www.nature.com/articles/s41586-022-05172-4 IIRC there was another paper recently, with similar methodology about computing xAx. These papers produce algorithms which aren't empirically correct, but provably correct. They do this by operating on a graph data structure, which describes the algorithm and then verifying the algebraic equality to the correct result. There is a substantial difference here. And I think utilizing algorithms which only are empirically correct can be dangerous.
One of the researchers quoted in Nature link here... in the past, when DeepMind published "AlphaTensor" [1][2] in October 2022, it took a single day (!!), see [3], for improvements to the AlphaTensor-based scheme to be discovered. This was then a few months later generalized into a significantly more comprehensive scheme [4]. I do not know whether the more general scheme that was discovered in [4] made its way back to some improved version of AlphaTensor - but this nonetheless shows that AlphaEvolve may also change, as it becomes absorbed by the community. [1] Blog: https://deepmind.google/discover/blog/discovering-novel-algo... [2] Paper: https://www.nature.com/articles/s41586-022-05172-4 [3] arxiv.org/pdf/2210.04045 [4] arxiv.org/abs/2212.01175 Flip graphs for matrix multiplication (Reposted from here, where I made a mini deep-dive into this: https://x.com/friederrrr/status/1922846803420119410?t=7jZ34P...)
Ok fair point. One such method was an improvement in matrix matrix multiplication in 2022. So I’m sure there is a potential discovery of many efficient numerical algorithms that will be uncovered with machine learning. https://www.nature.com/articles/s41586-022-05172-4 My parent comment was a knee jerk response to the over confidence and wishful thinking of computer work people to a magic AI box solving all the hard physical problems like its some simple conversation prompt away.
Remind me of this: https://www.nature.com/articles/s41586-022-05172-4 > 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. [...] We 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. Our results highlight AlphaTensor’s…
ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria. And I'll emphasis this sentence, as it seems to be the main goal/critics of the author in this post: > improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware.
If that's a typo and they meant to say "AI", then I may be remembering the article(s) being alluded to: > 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, to our knowledge, since its discovery 50 years ago. https://towardsdatascience.com/how-deepmind-discovered-new-w... https://www.nature.com/articles/s41586-022-05172-4
Related: Strassen algorithm: https://en.wikipedia.org/wiki/Strassen_algorithm Matrix multiplication algorithm: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... Discovering faster matrix multiplication algorithms with reinforcement learning: https://www.nature.com/articles/s41586-022-05172-4: General Google search: "Matrix Multiplication Optimization": https://www.google.com/search?q=matrix+multiplication+optimi...
More from the same topics.
Tom B. Brown, Benjamin Mann, Nick Ryder +28
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task.
Anders Sandberg, Eric Drexler, Toby Ord
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Haoran Xu, Fredrik Kjolstad
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.