Discovering Practical Algorithms for Least Squares using Language Models

Least squares is a central problem in scientific computing with applications across many domains such as the natural and social sciences. The design and implementation of state-of-the-art algorithms for solving least squares are often based on worst-case theoretical analysis and tailored to provide numerically stable solutions. These principles are often too conservative in real-world settings, incurring severe runtime slowdowns. Manually designing per-use-case algorithm implementations, on the other hand, requires domain knowledge and tedious trial-and-error. In this work, we leverage recent progress in large language model-guided automated discovery to automate the design of practical algorithms for numerical linear algebra applications. More specifically, our methodology frames the search for practical least squares algorithms as a meta-discovery problem: given a family of downstream solver tasks, we combine language model-guided algorithm evolution with robust meta-evaluation accounting for runtime and solver accuracy. We demonstrate the effectiveness and flexibility of our framework by discovering faster practical algorithms across an extensive list of synthetic and real-world least squares tasks. The discovered algorithms are $2\times$ faster than optimized baselines on large kernel regression tasks from the SUSY dataset for high-energy particle physics classification with up to one million rows. Additionally, we analyze the algorithms discovered by our framework and decompose the runtime improvements across algorithmic changes, hyperparameter optimization, and code engineering.