topics

on machine learning, statistics, computer science, and research.

Reading list on probabilistic numerics

07 Apr 2020

(Last updated: 04/19/2020)

Probabilistic numerical methods have experienced a recent surge of interest. However, the literature of many key contributions date back to 60s-80s, a period before many modern developments in computing. The goal here is to collect a relevant, organized reading list here. I hope to update this post with more references and possibly short descriptions of the papers as I get to reading more of them.

The Probabilistic Numerics Website has a more complete set of papers and serves as a great reference on this topic.

Recent surveys

Here are recent surveys that collect a lot of the literature and developments in the field as well as open problems the authors believe are important to tackle.

  1. Hennig, P., Osborne, M. A., & Girolami, M. (2015). Probabilistic numerics and uncertainty in computations. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 471(2179).

  2. Oates, C. J., & Sullivan, T. J. (2019). A Modern Retrospective on Probabilistic Numerics. ArXiv e-Prints, 1901.04457.

Selected historical papers

The first discussion of probabilistic numerics apparently dates back to Poincaré in 1896. Here we collect some important papers building foundations in probabilistic numerics, which mostly focused on the problem of integration.

  1. Sul’din, A. V. (1959). Wiener measure and its applications to approximation methods. I. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, (6), 145–158.

  2. Sul’din, A. V. (1960). Wiener measure and its applications to approximation methods. II. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, (5), 165–179.

  3. Kimeldorf, G. S., & Wahba, G. (1970). A correspondence between Bayesian estimation on stochastic processes and smoothing by splines. The Annals of Mathematical Statistics, 41(2), 495–502.

  4. Larkin, F. M. (1972). Gaussian measure in Hilbert space and applications in numerical analysis. Rocky Mountain Journal of Mathematics, 2(3), 379–422.

  5. Micchelli C. A., & Rivlin T. J. A survey of optimal recovery. Optimal Estimation in Approximation Theory. Springer, 1977, 1–54.

  6. Kadane, J. B., & Wasilkowski, G. W. (1985). Average case epsilon-complexity in computer science: A Bayesian view. In Bayesian Statistics 2, Proceedings of the Second Valencia International Meeting (pp. 361–374).

  7. Wozniakowski, H. A survey of information-based complexity. J. Complexity, 1(1):11–44, 1985.

  8. Diaconis, P. (1988). Bayesian numerical analysis. Statistical Decision Theory and Related Topics IV, 1, 163–175.

    (Additional notes)

    A note on the quadrature problem, i.e., estimating the integral \(\int_0^1 f(x) dx\) by considering a prior on \(f\), computing a posterior on \(f\) conditioned on information at a finite number of points \(f(t_1),\ldots,f(t_n)\), and then estimating the integral using the Bayes decision rule. Example: when using Brownian motion as a prior, the conditional expectation yields the classical trapezoidal rule for quadrature. Considers the problem of taking classical numerical procedures and seeing if they correspond to optimal decision rules (e.g., Bayes, minimax or admissible). In addition to a posterior distribution, the Bayesian approach also yields a clear approach to the design problem: i.e., how do we choose the information so that we get the best estimate of the integral? Discussion on priors that lead to linear interpolation, historical developments, recent applications, and connections with Stein estimation and consistency.

Recent papers on probabilistic numerics

For lack of a better title, here we collect more recent papers on probabilistic numerics, focusing on general overviews, rather than specific numerical methods.

Decision-theoretic views on probabilistic numerics

  1. Cockayne, J., Oates, C., Sullivan, T., & Girolami, M. (2017). Bayesian Probabilistic Numerical Methods. ArXiv e-Prints, stat.ME 1702.03673.

  2. Oates, C. J., Cockayne, J., Prangle, D., Sullivan, T. J., & Girolami, M. (2019). Optimality Criteria for Probabilistic Numerical Methods. ArXiv e-Prints, 1901.04326.

  3. Owhadi, H., & Scovel, C. (2017). Towards Machine Wald. Handbook of Uncertainty Quantification, pp. 157-191. Springer.

  4. Owhadi, H., & Scovel, C. (2017). Universal Scalable Robust Solvers from Computational Information Games and fast eigenspace adapted Multiresolution Analysis. ArXiv:1703.10761 [Math, Stat].

  5. Owhadi, H., Scovel, C., & Schafer, F (2019). Statistical Numerical Approximation. Notices of the American Mathematical Society, 66(10).

Probabilistic linear solvers

These papers propose probabilistic methods for solving linear systems \(Ax=b\), where generally a prior is placed on either the unknown quantity \(A^{-1}\) or \(A^{-1}b\), and posterior point estimates often have an explicit relationship with classical itereates obtained from iterative algorithms, such as the conjugate gradient method.

  1. Hennig, P. (2015). Probabilistic Interpretation of Linear Solvers. SIAM J on Optimization, 25(1).

  2. Cockayne, J., Oates, C., & Girolami, M. (2018). A Bayesian Conjugate Gradient Method. Bayesian Analysis, 14(23), 937–1012.

  3. Bartels, S., Cockayne, J., Ipsen, I., & Hennig, P. Probabilistic linear solvers: a unifying view. Statistics and Computing, 29(6), 1249–1263.

Probabilistic integration

In addition to the historical papers above, there are a lot of recent papers on probabilistic integration.

  1. Xie, X., Briol, F., & Girolami, M (2018). Bayesian Quadrature for Multiple Related Integrals. ICML, PMLR 80:5369-5378.

Applications

  1. Bartels, S., Hennig, P (2016). Probabilistic Approximate Least Squares. AISTATS, PMLR 51, 676-684.

  2. Garnett, R., Orborne, M.A., Reece, S., Rogers, A., Roberts, S.J. (2010). Sequential Bayesian Prediction in the Presence of Changepoints and Faults. The Computer Journal, 53(9), 1430-1446.

Tweet

Related Posts