Matrix-free least squares solvers: Values, gradients, and what to do with them

Hrittik Roy, Søren Hauberg, Nicholas Krämer · 2025

Read Matrix-free least squares solvers: Values, gradients, and what to do with them by Hrittik Roy, Søren Hauberg, Nicholas Krämer (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-2510-19634.txt.

Introduction

Hrittik Roy, Søren Hauberg, and Nicholas Krämer argue that least squares, the workhorse of fitting, is underused in modern machine learning. The trick is to make a matrix-free least squares solver differentiable, so it can sit inside a learning pipeline like a neural network layer. The authors derive custom gradients that flow through the solver without forming large matrices explicitly.

Three demonstrations show the range: enforcing sparse weights on a fifty-million-parameter model, imposing conservativeness constraints inside a score-based generative model, and tuning a Gaussian process's hyperparameters by predictive performance. The paper positions differentiable least squares as a general tool that machine learning practitioners can reach for far beyond simple curve fitting.

Catalog record

CREATORHrittik Roy, Søren Hauberg, Nicholas Krämer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19634

Browse the full library · About the Tower of Babel

Full text

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

Matrix-free least squares solvers: Values, gradients, and what to do with them Hrittik Roy, Søren Hauberg, Nicholas Krämer Abstract This paper argues that the method of least squares has significant unfulfilled potential in modern machine learning, far beyond merely being a tool for fitting linear models. To release its potential, we derive custom gradients that transform the solver into a differentiable operator, like a neural network layer, enabling many diverse applications. Empirically, we demonstrate: (i) scalability by enforcing weight sparsity on a 50 million parameter model; (ii) imposing conservativeness constraints in score-based generative models; and (iii) hyperparameter tuning of Gaussian processes based on predictive performance. By doing this, our work represents the next iteration in developing differentiable linear-algebra tools and making them widely accessible to machine learning practitioners. 1 Introduction The method of least squares is commonly introduced as one of the first steps into machine learning, where it is taught as a simple approach for performing linear regression ( Bishop 2006 ) . Although its importance is recognized, it is frequently perceived as a basic tool, perhaps overshadowed by the complex non-linear models prevalent today. We argue that this misconception is a lost opportunity, and take steps towards rectifying it by providing novel tools and use cases in the present work. For least-squares problems like \mathbf{x}^{\star}\coloneqq\arg\min_{\mathbf{x}}\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2}+\lambda^{2}\|\mathbf{x}\|^{2} or \mathbf{x}^{\star}\coloneqq\arg\min_{\mathbf{x}}\|\mathbf{x}\|^{2}\penalty\ \text{s.t.}\penalty\ \mathbf{A}\mathbf{x}=\mathbf{b} , consider a computational abstraction LstSq , which takes the linear operator \mathbf{A} , vector \mathbf{b} , and a regularization weight \lambda (which could be zero), and returns the least-squares solution, \displaystyle\mathbf{x}^{\star}=\texttt{LstSq}(\mathbf{A},\mathbf{b},\lambda). (1) A central message of our work is that LstSq is not merely a solver but – if equipped with appropriate reverse-mode derivatives – a differentiable operator like a neural network layer, and that it should be used as such. One central example will be constrained optimization of a neural network (more on this later), but the method has many applications beyond this use case. More precisely, our main contributions are the following: 1. We provide an efficient JAX implementation of LstSq . The least-squares solutions are computed via LSMR ( Fong & Saunders 2011 ) , which we demonstrate is superior to alternative approaches such as solving normal equations or direct methods that instantiate the matrix. 2. We derive and implement custom reverse-differentiation rules for adaptive least-squares solvers using the adjoint method. This implementation 1 1 1 JAX library: https://github.com/pnkraemer/matfree has the advantage of working for all least-squares solvers, including adaptive solvers whose iteration count is unknown a priori. Our experiments show how the custom gradients are orders of magnitude faster than unrolling the solver’s forward pass. 3. We revive the null-space method ( Yamashita 1980 ) for constrained optimization and reformulate it as a least-squares problem. This new perspective enables using our efficient implementation of LstSq . To the best of our knowledge, ours is the first use of the null-space method in deep learning. 4. We demonstrate the least-squares-null-space method’s efficacy on a diverse set of constrained optimization tasks, such as: equivariance, weight sparsity, and conservativeness of score-based generative models, on models with up to 50 million parameters . We also provide a JAX library that seamlessly integrates the null-space method into Optax ( DeepMind et al. 2020 ) , allowing constrained optimization of neural networks with just a few lines of code. 2 2 2 JAX library: https://github.com/h-roy/nuox 5. We use the backward pass of the differentiable LstSq solver to calibrate a Gaussian process, directly optimizing the posterior fit instead of marginal-likelihood optimization. To achieve this, we exploit the natural connection between Gaussian process regression and least squares problems, and find that targeting the posterior fit improves both runtime and quality of fit over typical baselines. 2 Least squares: values, gradients, and what to do with them 2.1 Values: matrix-free least-squares in JAX For any m,n\in\mathbb{N} , let \mathbf{b}\in\mathbb{R}^{m} and \mathbf{A}\in\mathbb{R}^{m\times n} be given. Throughout this work, we assume that the matrix \mathbf{A} has full rank, and is parameterized by some \theta , \mathbf{A}=\mathbf{A}(\theta) . We distinguish least-squares problems with a tall \mathbf{A}(\theta) , which means m\geq n , from problems with a wide matrix, m\leq n . We also distinguish regularized from unregularized problems, depending on whether \lambda is zero or not. Intuitively, least squares problems seek optimal solutions \mathbf{x} to linear systems \mathbf{Ax=b} , with a possibly-nonsquare matrix \mathbf{A}\in\mathbb{R}^{m\times n} ( Björck 2024 ) . More precisely, the least-squares method solves \displaystyle\mathbf{x}^{\star}(\mathbf{\theta},\mathbf{b},\lambda)=\texttt{LstSq}(\mathbf{A}(\theta),\mathbf{b},\lambda)=\begin{cases}\arg\min_{\mathbf{x}}\|\mathbf{A(\theta)x-b}\|^{2}+\lambda^{2}\|\mathbf{x}\|^{2}&\text{if}\penalty\ \lambda\neq 0\text{ or $\mathbf{A}$ is tall},\\ \arg\min_{\mathbf{x}}\left\{\|\mathbf{x}\|^{2}\penalty\ \text{s.t.}\penalty\ \mathbf{A}(\mathbf{\theta})\mathbf{x}=\mathbf{b}\right\}&\text{if $\lambda=0$\text{ and }$\mathbf{A}$ is wide.}\end{cases} (2) For tall \mathbf{A}(\theta) , the regularized problem is well-defined for \lambda\rightarrow 0 (in the sense of admitting a unique solution in the limit). For wide \mathbf{A}(\theta) , this is not the case. Instead, the relationship between the two is that the regularized problem ( \lambda\neq 0 ) is solved by \displaystyle\mathbf{x}^{\star}(\theta,\mathbf{b},\lambda)=\mathbf{A}(\theta)^{\top}(\mathbf{A}(\theta)\mathbf{A}(\theta)^{\top}+\lambda^{2}\mathbb{I})^{-1}\mathbf{b}=(\mathbf{A}(\theta)^{\top}\mathbf{A}(\theta)+\lambda^{2}\mathbb{I})^{-1}\mathbf{A}(\theta)^{\top}\mathbf{b}. (3) In the limit of \lambda\rightarrow 0 , only one of the two parameterizations in Equation 3 is well-defined, depending on whether \mathbf{A}(\theta) is tall or wide. The corresponding limit of \mathbf{x}^{\star} for \lambda\rightarrow 0 minimizes \|\mathbf{A}\mathbf{x}-\mathbf{b}\|^{2} if \mathbf{A}(\theta) is tall, or \{\|\mathbf{x}\|^{2}\text{ s.t. }\mathbf{A}(\theta)\mathbf{x}=\mathbf{b}\} if \mathbf{A}(\theta) is wide, respectively; more on this relationship in Appendix C . Table 1: Approaches to solving least squares problems. “L.S.”: linear system; “O.T.”: orthogonal transformation. Method Property Direct Matrix-free L.S. Examples Cholesky Conj. Grad. Precision Double Double Memory \mathcal{O}(\min(m,n)^{2}) \mathcal{O}(\max\{m,n\}) O.T. Examples SVD, QR LSMR Precision Single Single Memory \mathcal{O}(mn) \mathcal{O}(\max\{m,n\}) The various methods for numerically solving least squares problems can be broadly classified across two axes. Along one axis, there are direct versus matrix-free methods, which differ in whether or not the matrix \mathbf{A}(\theta) is instantiated in memory (“direct method”, high memory demands, and for realistic problems, \mathbf{A}(\theta) is too big to store in memory) or only accessed via matrix-vector products (“matrix-free methods”, low memory demands). Along the other axis, there are approaches based on solving the linear system in Equation 3 versus those approaches that apply orthogonal transformations to \mathbf{A}(\theta) and extract \mathbf{x}^{\star} directly, for example, using Golub-Kahan-Li bidiagonalization ( Golub & Kahan 1965 ) . Methods that solve linear systems require twice the precision of methods that orthogonally transform \mathbf{A}(\theta) . This is because the solvers compute \mathbf{v}\mapsto(\mathbf{A}(\theta)^{\top}\mathbf{A}+\lambda^{2}\mathbb{I})^{-1}\mathbf{v} , which means that singular values of \mathbf{A}(\theta) are squared, affecting the conditioning of the problem accordingly. Table 1 summarises the differences in approaches. Only matrix-free methods that target orthogonal transformations combine low memory demands with the ability to work in low precision, which is why we focus on this class of solvers in the present work. As an instance of such an algorithm, our implementation uses LSMR ( Fong & Saunders 2011 ) . LSMR is equivalent to applying MINRES ( Paige & Saunders 1975a ) to the linear system in Equation 3 , but more robust because it handles matrix-vector and vector-matrix products with \mathbf{A}(\theta) separately, not in combination (thus it avoids “squaring”; Appendix A ). Commonly, for example, in SciPy’s implementation ( Virtanen et al. 2020 ) , LSMR requires access to both \mathbf{v}\mapsto\mathbf{A}(\theta)\mathbf{v} and \mathbf{u}\mapsto\mathbf{A}(\theta)^{\top}\mathbf{u} . Transposing the linear operator \mathbf{A}(\theta) manually, without instantiating \mathbf{A}(\theta) , is often tedious and a common source of error. To avoid this error source, our framework handles transposition automatically: Accessing only \mathbf{v}\mapsto\mathbf{A}(\theta)\mathbf{v} , the transposed

Read the complete text