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

arXiv: https://arxiv.org/abs/2507.03833 · HTML: https://mlsanity.com/paper/2507.03833/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 53 references that are in the map.
- First posted on arXiv 4 Jul 2025.

## Builds on (most cited first, 10 of 10)

- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Shampoo: Preconditioned Stochastic Tensor Optimization](https://mlsanity.com/paper/1802.09568/) (2018)
- [Towards Faster Training of Global Covariance Pooling Networks by Iterative Matrix Square Root Normalization](https://mlsanity.com/paper/1712.01034/) (2017)
- [A Fractional Graph Laplacian Approach to Oversmoothing](https://mlsanity.com/paper/2305.13084/) (2023)
- [Deep CNNs Meet Global Covariance Pooling: Better Representation and Generalization](https://mlsanity.com/paper/1904.06836/) (2019)
- [Learning to Optimize Neural Nets](https://mlsanity.com/paper/1703.00441/) (2017)
- [Deep Generative Symbolic Regression with Monte-Carlo-Tree-Search](https://mlsanity.com/paper/2302.11223/) (2023)
- [Why Approximate Matrix Square Root Outperforms Accurate SVD in Global Covariance Pooling?](https://mlsanity.com/paper/2105.02498/) (2021)
- [The Edge of Orthogonality: A Simple View of What Makes BYOL Tick](https://mlsanity.com/paper/2302.04817/) (2023)
- [Fast Differentiable Matrix Square Root](https://mlsanity.com/paper/2201.08663/) (2022)

## Built on by (most cited first, 1 of 1)

- [PRISM: Distribution-free Adaptive Computation of Matrix Functions for Accelerating Neural Network Training](https://mlsanity.com/paper/2601.22137/) (2026)

## Abstract (arXiv)

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. Handtuning 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.