MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search

Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng, Mert Pilanci · 2025

Read MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search by Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng, Mert Pilanci (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03833.txt.

Introduction

Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling Geng, and Mert Pilanci present MatRL in this 2025 paper, a system that designs matrix algorithms on its own. Iterative methods compute matrix functions step by step. Their speed depends heavily on tuning choices and on mixing iteration types, and hand tuning is slow work.

MatRL treats algorithm design as a sequence of choices. A reinforcement learning frame, guided by Monte Carlo tree search, plans a hybrid chain of iterations and step sizes. The chain is tailored to a given class of input matrices and to the machine at hand. The authors also prove that the discovered methods generalize beyond their training cases. The work aims to replace weeks of expert fiddling with a search that finds fast, provable recipes for each new setting.

Catalog record

CREATORSungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng, Mert Pilanci
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE64 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-03833

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search Sungyoon Kim, Rajat Vadiraj Dwaraknath, Longling geng, Mert Pilanci Abstract Iterative methods for computing matrix functions have been extensively studied and their convergence speed can be significantly improved with the right tuning of parameters and by mixing different iteration types higham1990fast . Hand - tuning the design options for optimal performance can be cumbersome, especially in modern computing environments: numerous different classical iterations and their variants exist, each with non - trivial per - step cost and tuning parameters. To this end, we propose MatRL – a reinforcement learning based framework that automatically discovers iterative algorithms for computing matrix functions. The key idea is to treat algorithm design as a sequential decision-making process. Monte-Carlo tree search is then used to plan a hybrid sequence of matrix iterations and step sizes, tailored to a specific input matrix distribution and computing environment. Moreover, we also show that the learned algorithms provably generalize to sufficiently large matrices drawn from the same distribution. Finally, we corroborate our theoretical results with numerical experiments demonstrating that MatRL produces algorithms that outperform various baselines in the literature. 1 Introduction Matrix functions are everywhere - ranging from classical applications in control theory denman1976matrix , high-dimensional ODEs higham2008functions , theoretical particle physics chen2014newton , lin2009fast , Markov models waugh1967fractional , to some recent applications in machine learning, e.g. covariance pooling li2018towards , wang2020deep , song2021approximate , graph signal processing defferrard2016convolutional , maskey2023fractional , contrastive learning richemond2023edge , and optimizer design gupta2018shampoo , jordan2024muon , ahn2025dion . For more applications see higham2008functions and references therein. It isn’t a surprise that computing matrix functions in a fast, precise, and stable manner has received numerous attention and many have tried to develop fast algorithms with guarantees that it will work in some sense. Iterative algorithms to compute matrix functions are particularly attractive in modern applications as they can avoid computing the matrix function directly using the singular value decomposition (SVD). Further, termination criteria can be chosen based on the needs of the application, which can lead to faster and more stable algorithms. Additionally, these algorithms are differentiable, leading to potential applications in auto-differentiation based settings song2022fast . From an algorithm design perspective, it would be ideal to find an algorithm that is computationally efficient, numerically stable and has faster convergence guarantees. One can imagine using different iterations from different algorithms at each step (e.g. mixing the algorithms) and specifically tuning the parameters jointly to accelerate the algorithm. However, due to the large search space (see Section 2.1 and references therein to see a vast array of existing iterative algorithms) and highly sensitive and non-trivial per iteration costs in modern computing environments, handcrafting the ideal algorithm is tedious and impractical. Table 1 : Computation times for matrix inverse and multiplication ( 4096\times 4096 ) on CPU and GPU in single (float32) and double (float64) precision. The right-most column shows the ratio of inverse time to matmul time. All computations done using PyTorch on an RTX A6000 GPU. Device Precision Inverse (ms) MatMul (ms) Inv : MatMul ratio CPU float32 251.2 8.7 48.8 1.8 5.15 float64 356.6 16.3 122.9 4.6 2.90 GPU float32 28.3 0.5 5.6 0.1 5.05 float64 423.9 6.9 252.6 6.4 1.68 A motivating experiment is presented in Table 1 . In single precision, the cost of computing a 4096\times 4096 inverse is roughly five times that of a matrix multiply on both CPU and GPU. However, switching to double precision more than halves this ratio – dropping to about 2.9 on CPU and 1.7 on GPU – because matrix multiplies become comparatively more expensive. This pronounced change in relative costs with precision underscores the need for automatic algorithm discovery, as the optimal sequence of matrix iterations will depend sensitively on both hardware and numerical precision. Besides the change in relative speeds, the gains from switching to GPU turns into a slowdown with double precision for both inverse and matmuls. This is due to the significantly lower emphasis on high precision compute capability in modern GPUs. To this end, we propose an automated solution based on Monte-Carlo tree search to decide which combination of iterations and parameters one should use given a desiderata of the user. Our solution assumes that the matrix of interest is sampled repeatedly from a certain symmetric random matrix distribution, and we want to find a good algorithm for that matrix distribution. The main idea is that iterative algorithms can be understood as a sequential decision-making process: at each step, one should choose which iteration to use and which parameters to use in that iteration. This corresponds to choosing actions in decision making, where the choice leads to the next step. At each step we get a certain reward signal based on the given desiderata, so that we can evaluate whether the action was worth it or not. Finding a good algorithm mounts to finding a good planning strategy for the given environment. Specifically, • We propose MatRL ( Algorithm 1 ), an automated algorithm searching scheme based on Monte-Carlo tree search. • The algorithms we find are faster than existing baselines, and even faster than implementations in torch.linalg. Moreover, the found algorithms differ with problem sizes, computation environment, and precision ( Section 5.1 ), meaning that MatRL adapts to different enviroments with ease. • We have a guarantee using random matrix theory that the found algorithm will generalize to different matrices drawn from the same distribution ( Section 4 ), and matrices drawn from the distribution with identical limiting eigenvalues. The paper is organized as the following: in Section 2 we discuss relevant background on iterative matrix function computation algorithms, Monte-Carlo tree search and learning algorithms via RL. Next we describe our environment in Section 3 by describing how the states, actions, state transition, and reward signals are defined. In Section 4 , we provide the generalization guarantee stemming from limiting distribution of the spectrum. We show experimental results in Section 5 showing the performance and adaptivity of MatRL, and conclude the paper in Section 6 . 2 Background 2.1 Iterative Methods to Compute Matrix Functions The basic idea of obtaining an iteration to compute matrix functions is using Newton’s method higham2008functions . For instance, say we want to compute the matrix square root. We would like to compute the root of the function f(X)=X^{2}-A , hence Newton’s method can be written as X_{k+1}=X_{k}-f^{\prime}(X_{k})^{-1}f(X_{k})=X_{k}-\frac{1}{2}X_{k}^{-1}(X_{k}^{2}-A)=\frac{1}{2}(X_{k}+X_{k}^{-1}A). (1) Newton’s method uses a first-order approximation of f at X_{k} : we may use higher order approximations to obtain Chebyshev method li2011chebyshev or Halley’s method nakatsukasa2010optimizing , guo2010newton . These higher-order methods converge cubically with appropriate initialization, but each iteration is slower than Newton’s method. We could also use inverse-free methods such as Newton-Schulz and its variants higham2008functions , higham1997stable , which approximates X_{k}^{-1} with a polynomial of X_{k} . Appropriate scaling and shifting of the spectrum to yield faster convergence has been a popular idea nakatsukasa2010optimizing , byers2008new , byers1987solving , chen2014newton , iannazzo2003note , hoskins1979faster , pan1991improved . The intuition is that by introducing additional parameters and solving an optimization problem on the spectrum, we can find a sequence of optimized parameters that depend on the spectrum of A ,

Read the complete text