BayesCG As An Uncertainty Aware Version of CG

Tim W. Reid, Ilse C. F. Ipsen, Jon Cockayne, Chris J. Oates

TL;DR

This paper introduces BayesCG, an "uncertainty-aware" probabilistic extension of the Conjugate Gradient (CG) method for solving linear systems. It provides a principled way to quantify the uncertainty in the solution due to early termination of the iterative solver, producing low-rank posterior covariances that are computationally efficient and useful for downstream uncertainty propagation.

What Problem Does This Paper Address?

Solving linear systems of equations ($Ax = b$) is a fundamental problem in scientific computing. The Conjugate Gradient (CG) method is a popular iterative solver for symmetric positive-definite matrices. However, CG is often terminated early when the residual is small enough, meaning the solution is not exact. This introduces uncertainty in the computed solution. Traditional error estimates for CG are often insufficient for propagating this uncertainty to subsequent computations in a pipeline. This paper addresses this by developing a probabilistic framework, BayesCG, that models the uncertainty in the solution and provides a distribution that can be propagated.

Methods

The core contribution is an efficient implementation of BayesCG that extends previous work by allowing for singular prior covariances. This is achieved by:

  • Extending BayesCG to Singular Priors: The theoretical framework is adapted to handle singular prior covariance matrices, which is crucial for the proposed low-rank posterior approach.
  • Introducing a New Krylov Prior: A novel prior distribution is designed that leverages Krylov subspaces. This prior is singular, depends on CG quantities, and importantly, leads to low-rank posterior covariances.
  • Low-Rank Posterior Covariances: The posterior covariances are maintained in a factored, low-rank form. This significantly reduces computational cost and memory requirements, making it practical to generate samples for uncertainty analysis.
  • Recursive Computations: Efficient recursive formulas are derived for updating posterior means and covariances, mirroring the iterative nature of CG.
  • Practical Algorithm (Algorithm 3.1): A concrete algorithm is presented that combines CG iterations for the posterior mean with a limited number of additional iterations to compute the factors of the approximate posterior covariance.

Datasets

Not discussed in the paper. The paper focuses on numerical experiments using synthetic linear systems with specified properties (e.g., condition number, eigenvalue distribution).

Key Insights and Ideas

  • Uncertainty-Aware Solvers are Crucial: For complex computational pipelines, simply knowing the residual of a linear solve isn't enough. A probabilistic model of the solution's uncertainty is needed for meaningful downstream analysis.
  • Low-Rank Priors/Posteriors are Key to Efficiency: The novelty of the "Krylov prior" lies in its ability to generate low-rank posterior covariances. This is a significant computational advantage over methods that produce full-rank covariances.
  • BayesCG Mimics CG Convergence: The posterior means of BayesCG, under the proposed Krylov prior, are identical to the CG iterates. This means BayesCG inherits CG's convergence speed for the mean while also providing uncertainty estimates.
  • Calibrated Posteriors for Error Estimation: The specific Krylov prior is designed such that the trace of the posterior covariance accurately reflects the true error in the posterior mean, making it a reliable indicator of uncertainty.

Key Results

  • Efficient BayesCG Implementation: The proposed BayesCG algorithm (Algorithm 3.1) is computationally efficient, especially for large systems, due to the low-rank factored form of posterior covariances.
  • Accurate Uncertainty Modeling: Numerical experiments demonstrate that BayesCG, particularly with the specific Krylov prior, produces posterior distributions that accurately model the uncertainty in the solution, as evidenced by error estimates from posterior samples.
  • Improved Error Estimation: The paper shows that BayesCG with the Krylov prior can provide more reliable error estimates compared to previous probabilistic CG methods, especially when dealing with uncertainty in downstream computations.
  • Comparison with Existing Methods: The paper compares its approach to existing probabilistic CG methods and CG error estimation techniques, highlighting the advantages in terms of computational cost and accuracy of uncertainty quantification.

Limitations and Future Work

  • Calibration Rigor: While empirical evidence suggests good calibration, the authors note that a rigorous investigation of calibration for BayesCG under the specific Krylov prior is a subject for a separate paper.
  • Analytical Propagation: The paper mentions that analytical propagation of the posterior has proven elusive, and empirical propagation is currently the primary option.
  • Statistical Aspects: Future work will focus on the statistical aspects of BayesCG under the Krylov prior, including quantifying approximation errors of low-rank posteriors and further investigating calibration.
  • Computational Pipeline Impact: A separate paper will assess the effect of CG accuracy in a computational pipeline, specifically for generalized singular value decomposition.

Summary updated

Abstract

The Bayesian Conjugate Gradient method (BayesCG) is a probabilistic generalization of the Conjugate Gradient method (CG) for solving linear systems with real symmetric positive definite coefficient matrices. Our CG-based implementation of BayesCG under a structure-exploiting prior distribution represents an 'uncertainty-aware' version of CG. Its output consists of CG iterates and posterior covariances that can be propagated to subsequent computations. The covariances have low-rank and are maintained in factored form. This allows easy generation of accurate samples to probe uncertainty in downstream computations. Numerical experiments confirm the effectiveness of the low-rank posterior covariances.
BibTeX
@inproceedings{reid2020bayescg,
  author = {Tim W. Reid and Ilse C. F. Ipsen and Jon Cockayne and Chris J. Oates},
  title = {{BayesCG As An Uncertainty Aware Version of CG}},
  booktitle = {ePrints},
  year = {2020},
  doi = {10.48550/arxiv.2008.03225},
}
Figure