logo
ResearchBunny Logo
Discovering faster matrix multiplication algorithms with reinforcement learning

Computer Science

Discovering faster matrix multiplication algorithms with reinforcement learning

A. Fawzi, M. Balog, et al.

Discover how AlphaTensor, developed by a team of researchers from DeepMind, revolutionizes matrix multiplication through deep reinforcement learning. This groundbreaking agent not only improves on Strassen's algorithm for 4x4 matrices after 50 years but also achieves remarkable flexibility and efficiency across a range of matrix sizes and applications.

00:00
00:00
Playback language: English
Abstract
This paper presents AlphaTensor, a deep reinforcement learning agent based on AlphaZero, designed to discover efficient and provably correct algorithms for matrix multiplication. AlphaTensor formulates the problem as a single-player game, TensorGame, where the goal is to find tensor decompositions. The agent surpasses state-of-the-art complexity for many matrix sizes, notably improving upon Strassen's algorithm for 4x4 matrices in a finite field for the first time in 50 years. AlphaTensor's flexibility is demonstrated through applications to structured matrix multiplication and hardware-specific optimizations, achieving improved practical efficiency.
Publisher
Nature
Published On
Oct 06, 2022
Authors
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
Tags
AlphaTensor
matrix multiplication
deep reinforcement learning
tensor decompositions
Strassen's algorithm
efficiency

Related Publications

Explore these studies to deepen your understanding of the subject.

Faster sorting algorithms discovered using deep reinforcement learning
Computer Science

Faster sorting algorithms discovered using deep reinforcement learning

D. J. Mankowitz, A. Michi, et al.

Ageing is associated with disrupted reinforcement learning whilst learning to help others is preserved
Psychology

Ageing is associated with disrupted reinforcement learning whilst learning to help others is preserved

J. Cutler, M. K. Wittmann, et al.

Enabling high throughput deep reinforcement learning with first principles to investigate catalytic reaction mechanisms
Chemistry

Enabling high throughput deep reinforcement learning with first principles to investigate catalytic reaction mechanisms

T. Lan, H. Wang, et al.

Coincidence imaging for Jones matrix with a deep-learning approach
Physics

Coincidence imaging for Jones matrix with a deep-learning approach

J. Xi, T. K. Yung, et al.

Listen, Learn & Level Up
Over 10,000 hours of research content in 25+ fields, available in 12+ languages.
No more digging through PDFs, just hit play and absorb the world's latest research in your language, on your time.
listen to research audio papers with researchbunny