Abstract:Randomized linear algebra (RLA) algorithms are a modern class of numerical linear algebra techniques that play an essential role in scientific computing and machine learning, with broad and growing adoption. However, their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. In this paper, we present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode inductive bias specific to the RLA domain; (2) Monte Carlo Graph Search, which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch, and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability. Code is available at this https URL.
| Comments: | Accepted at the 43rd International Conference on Machine Learning (ICML 2026). 9 pages main text; 21 pages total |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.18004 [cs.LG] |
| (or arXiv:2605.18004v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.18004 arXiv-issued DOI via DataCite (pending registration) |
From: Ruoxin Wang [view email]
[v1]
Mon, 18 May 2026 07:57:26 UTC (1,866 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。