Extrapolating from Regularised Solutions for Solving Ill-Conditioned Linear Systems in Machine Learning
Disha Hegde [email protected], Jon Cockayne [email protected], Chris. J. Oates [email protected] · 2026
Read Extrapolating from Regularised Solutions for Solving Ill-Conditioned Linear Systems in Machine Learning by Disha Hegde [email protected], Jon Cockayne [email protected], Chris. J. Oates [email protected] (2026) 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-2606-30328.txt.
Introduction
Disha Hegde, Jon Cockayne, and Chris Oates build a Python package that solves stubborn linear systems for machine learning prototyping. Ill-conditioned systems arise constantly in Bayesian optimization and emulation. The standard fix adds a small nugget to the diagonal. Choosing that nugget size is tricky and often resists automation. Data-adaptive choices also block automatic differentiation in training pipelines.
Their package, autonugget, runs several regularized solves instead of one. Richardson extrapolation combines those solves into a better answer. Accuracy improves over any single-nugget approximation of the system. The discarded solves of adaptive procedures are finally put to use. The whole routine stays JAX-friendly for training. That compatibility keeps end-to-end training stable for users. The package targets lightweight, rapidly implemented numerical routines. Fast building, not peak performance, is the design priority.
Catalog record
| CREATOR | Disha Hegde [email protected], Jon Cockayne [email protected], Chris. J. Oates [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30328
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extrapolating from Regularised Solutions for Solving Ill-Conditioned Linear Systems in Machine Learning Disha Hegde [email protected], Jon Cockayne [email protected], Chris. J. Oates [email protected] Abstract Rapid prototyping of algorithms is a critical step in modern machine learning. Most algorithms exploit linear algebra, creating a need for lightweight numerical routines which – while potentially sub-optimal for the task at hand – can be rapidly implemented. For the numerical solution of ill-conditioned linear systems of equations, the standard solution for prototyping is Tikhonov-regularised inversion using a nugget. However, selection of the size of nugget is often difficult, and the use of data-adaptive procedures precludes automatic differentiation, introducing instabilities into end-to-end training. Further, while data-adaptive procedures perform multiple linear solves to select the size of nugget, only the result of one such solve is returned, which we argue is wasteful. This paper aims to circumvent the above difficulties, presenting autonugget ; a Python package for automatic and stable numerical solution of linear systems suitable for rapid prototyping, and fully compatible with automatic differentiation using JAX . autonugget combines multiple linear solves using Richardson extrapolation to determine the solution of the ill-conditioned system, improving in accuracy over approximations based on a single nugget. 1 Introduction Consider the problem of numerically solving Ax=b for x\in\mathbb{R}^{d} . It will be assumed that A is a symmetric positive definite matrix, but that A is (possibly severely) ill-conditioned and, as a result, solving the linear system with standard methods is challenging. This setting is ubiquitous in applied machine learning like Bayesian optimisation ( Garnett 2023 ) , emulation ( Gramacy 2020 ) , and probabilistic numerics ( Hennig et al. 2022 ) . In machine learning, a widely-used approach to improving the conditioning of the system so that it can be solved is to use Tikhonov regularisation: \displaystyle x_{\sigma}:=(A+\sigma I)^{-1}b,\qquad\sigma\geq 0, (1) where x_{\sigma}\rightarrow x in exact arithmetic as the regularisation parameter \sigma\rightarrow 0 . The regularisation parameter \sigma is referred to as a nugget . For sufficiently regular matrices A , such as positive semi-definite matrices, the conditioning of A+\sigma I improves monotonically as \sigma is increased. However, in practice this often results in a conflation of two ideals: 1. Regularisation: as a technique for penalising large values in the solution vector, improving generalisation performance. In this setting the focus is on \sigma>0 . 2. Ill-conditioning: as a technique for improving the numerical performance of solver routines. In this setting the quantity of interest is \sigma=0 , but the ill-conditioning of A causes numerical problems in the computational pipeline. In this paper, the focus is solely on the latter: we assume that the nugget is being used only as a tool to improve the conditioning of A . When using Tikhonov regularisation to improve conditioning, one usually takes \sigma to be just large enough that a numerical approximation \hat{x}_{\sigma} to x_{\sigma} can be obtained to a required level of precision using a direct method (e.g. LU-factorisation). The popularity of Tikhonov-regularisation for prototyping of algorithms is due to the simplicity with which it can be implemented, and the presence of only a single degree of freedom to be selected. For subsequent code optimisation, one would ideally upgrade from a Tikhonov-regularised direct method to a more scalable or sophisticated linear algebra routine, such as a preconditioned iterative method ( Trefethen and Bau 2022 ) , though we note that Tikhonov regularisation often forms a component of these routines, e.g. in constructing preconditioners ( Cutajar et al. 2016 ) and in certain Krylov subspace methods ( Gazzola et al. 2015 ) . Moreover, while ideally the numerics should be improved to address instabilities resulting from poor conditioning, how often this actually happens could be questioned. The aim of this paper is to address three key issues that arise in applications of Tikhonov regularisation to address poor conditioning: 1. Size of the nugget: The critical minimum value \sigma_{\star} of \sigma at which x_{\sigma} can be stably computed (i.e. as \hat{x}_{\sigma} ) will be unknown in general, and will depend sensitively on the actual values in A and b . 2. End-to-end training: Data-adaptive choices of \sigma , for example based on the condition number of A+\sigma I remaining below a specified threshold, are typically incompatible with automatic differentiation with respect to any variables \theta contained in A\equiv A_{\theta} and b\equiv b_{\theta} . This precludes straight-forward end-to-end training of machine learning algorithms via gradient descent. 3. Data-efficiency: While data-adaptive procedures perform multiple linear solves to select the size of nugget, only the result of one such solve is returned, which we argue is wasteful. To resolve these difficulties we present autonugget ; a Python package for hassle-free stable numerical solution of linear systems, fully compatible with automatic differentiation using JAX ( Bradbury et al. 2018 ) . To address data-efficiency, we explore the benefit of combining multiple linear solves corresponding to nuggets \Sigma=\{\sigma_{i}\}_{i=1}^{n} using Richardson extrapolation, which enables autonugget to improve in accuracy over approximations based on a single nugget. Automatic selection of \Sigma is performed by letting \Sigma=h\Sigma_{\mathrm{ref}} for some reference set \Sigma_{\mathrm{ref}} and selecting h to (approximately) balance the error due to extrapolation with the error due to numerical solution of ( 1 ). The autonugget package is described in Section 3 and illustrated in Figure 1 . Empirical evidence in support is presented in Section 4 . Figure 1: Illustration of autonugget : Here we plot numerical approximations \hat{x}_{\sigma} to x_{\sigma} as the nugget \sigma is varied (to aid in visualisation, only the first three coordinates are displayed). The numerical approximations were obtained using linalg.solve in numpy ( Harris et al. 2020 ) , a direct method based on LU factorisation. There is a critical value \sigma_{\star} (shaded) below which \hat{x}_{\sigma} fails to reliably approximate x_{\sigma} . On the other hand, reliable calculations can be performed when \sigma\geq\sigma_{\star} , and extrapolation of these reliable data can even provide a better approximation to x compared to \hat{x}_{\sigma_{\star}} . 1.1 Related Work The fundamental importance of linear algebra ensures ( 1 ) has been theoretically and empirically well-studied. On the other hand, we argue that there is an important gap at the interface of theory and practice with respect to existing work: Machine Learning The role of \sigma is often conflated in applied machine learning, on the one hand being a numerical parameter that one would ideally want to be small, while on the other hand serving as a ‘regulariser’ that affects downstream performance on a particular task. From this perspective, \sigma is often folded into the hyper-parameters of a machine learning algorithm and tuned end-to-end (e.g., in Bayesian inference through marginalisation). Similarly, amortised approaches, which aim to learn a mapping from the inputs of the machine learning task to an appropriate value for \sigma , have been pursued ( Chung and Español 2017 ; Alberti et al. 2021 ; De Vito et al. 2022 ) . However, both approaches represent a (possibly substantial) increase in the overall training cost. Further, there are important situations where one seeks the exact solution x of ( 1 ) as \sigma\rightarrow 0 ; for instance in regression applications, where Tikhonov regularisation can lead to predictions that are under-confident ( Andrianakis and Challenor 2012 ) . Guidance