Sparse Probabilistic Richardson Extrapolation
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Sparse Probabilistic Richardson Extrapolation".
Jane: Here's the gist of the paper. Almost every numerical task can be cast as extrapolation with respect to the fidelity or tolerance parameters of a consistent numerical method <ref:2604.02072#pg2> This perspective enables probabilistic uncertainty quantification and optimal experimental design functionality to be deployed, and also unlocks the potential for the convergence of numerical methods to be accelerated <ref:2604.02072#pg2> This paper develops a refined notion of extrapolation dimension, drastically reducing this simulation requirement when multiple tolerance parameters feature in the numerical method <ref:2604.02072#pg2> Sparsity-exploiting methodology is developed that is simultaneously simpler and more powerful compared to earlier work, and this is accompanied by sharp theoretical guarantees and substantial empirical support <ref:2604.02072#pg2> Extrapolation Dimension Concept The paper introduces the concept of extrapolation dimension, dext(f), which is defined as the minimal value of dim(A), i.e., the minimal cardinality of the index set 0 ∈ A ⊂ N d0 for which f has a non-trivial representation <ref:2604.02072#pg4> In practical terms, this dimension is interpreted as the minimum number of simulations required to accelerate convergence to f(0) <ref:2604.02072#pg4>.
Tom: The authors argue that if a simulator admits an expansion of the form (1), then the cardinality of the index set A is typically (relatively) small, suggesting that extrapolation sparsity is a general phenomenon in real-world applications <ref:2604.02072#pg2> 1.
Jane: Multivariate Richardson Extrapolation (MRE), which serves as a non-statistical sparsity-exploiting benchmark for SPRE <ref:2604.02072#pg4>.
Paper summary: Tom: Alright team, we're kicking off today with a look at Sparse Probabilistic Richardson Extrapolation. So what's the core idea here?
Jane: Well, it seems the big idea is that almost any numerical task can be framed as some kind of extrapolation based on how well you control the fidelity or tolerance settings in a consistent numerical method <ref:2604.02072#pg2>.
Lu: Exactly. This perspective lets us do probabilistic uncertainty quantification and optimal experimental design, and it also opens up the door to accelerating how numerical methods converge <ref:2604.02072#pg1>.
Meng: But the abstract points out a problem with previous work, specifically with Gauss–Richardson Extrapolation, which required a minimum number of simulations that grew super-exponentially in d, which is the number of tolerance parameters <ref:2604.02072#pg3>.
Tom: Right. So this new paper is focused on developing a refined idea for what we call the extrapolation dimension, dext(f) <ref:2604.02072#pg4>.
Jane: That concept is defined as the smallest value of dim(A), which is the minimal size of an index set A that gives a non-trivial representation for some function f <ref:2604.02072#pg4>.
Lu: In practical terms, what this means for us on the ground is it's interpreted as the minimum number of simulations you actually need to run to speed up convergence toward the true value f(zero) <ref:2604.02072#pg4>.
Meng: So if a simulator admits an expansion like that, then this index set A is usually small, suggesting that this extrapolation sparsity idea is a general thing in real-world applications <ref:2604.02072#pg1>.
Tom: It sounds like they are proposing a way to drastically reduce the simulation requirement when you have multiple tolerance parameters in your numerical method <ref:2604.02072#pg1>.
Jane: And they claim this new sparsity-exploiting methodology is simpler and more powerful than what came before, along with some really sharp theoretical guarantees and substantial empirical support <ref:2604.02072#pg1>.
Lu: That's interesting because the paper compares this approach against a few things, including Multivariate Richardson Extrapolation which serves as a benchmark for SPRE <ref:2604.02072#pg4>.
Meng: And then there's Gauss–Richardson Extrapolation, which uses a Gaussian process to model f of x and requires that minimum number of data points nmin be greater than or equal to two to d d factorial times d, which is super-exponential in the dimension d <ref:2604.02072#pg3>.
Tom: And Sparse Probabilistic Richardson Extrapolation, SPRE, seems to leverage this new extrapolation dimension concept to bring that simulation requirement down typically to being polynomial in d <ref:2604.02072#pg1>.
Jane: They also show convergence acceleration guarantees for SPRE, specifically theorem three which shows the extrapolation error for the posterior mean of the Gaussian process is bounded by something related to C h k z bounded in h RHk(Xh) <ref:2604.02072#pg4>.
Lu: And there's theorem four which demonstrates that SPRE can actually achieve *more* convergence acceleration than the Multivariate Richardson Extrapolation if you have the right regularity conditions met <ref:2604.02072#pg4>.
Meng: We need to check if this is just theoretical or if it holds up when we try to run it on actual problems at scale <ref:2604.02072#pg1>.
Tom: The authors did some empirical validation, looking at three case studies: two colliding spheres, five colliding shapes, and an agent-based flocking model <ref:2604.02072#pg1>.
Jane: And in all those settings where this extrapolation sparsity can be used, SPRE actually outperforms both the Multivariate Richardson Extrapolation and the Gauss–Richardson Extrapolation <ref:2604.02072#pg1>.
Lu: The empirical assessment shows that for white noise or Matérn-one/two kernels, the estimated index set A is robustly estimated only when h is sufficiently small, suggesting that dext(f) is about three in some cases <ref:2604.02072#pg1>.
Meng: So for deployment, what does this mean for us in terms of cost? The implementation details involve a sequential strategy alternating between learning k and A and selecting which simulations to run next <ref:2604.02072#pg1>.
Tom: They use leave-one-out cross-validation, LOOCV, to check if a kernel k and a set A are suitable through something called the predictive log density L(k, A) <ref:2604.02072#pg1>.
Jane: The experimental design part involves minimizing something called Vk,A
f(zero)Xn U X*m: subject to a total computational budget C <ref:2604.02543>
Lu: For the agent-based flocking model specifically, they use the Mesa Python library and employ methods like explicit Euler integration and Newton method constraint solvers <ref:2604.02543>.
Meng: The real question for us is how this methodology translates to production. It needs to be simple enough to run efficiently without massive computational overhead <ref:2604.02543>.
Tom: So, in conclusion, the paper establishes these sparsity-exploiting extrapolation methods as a new frontier for accelerating complex simulators <ref:2604.02543>.
Jane: SPRE is presented as a black box probabilistic numerical method using Bayesian principles to quantify uncertainty about the continuum model we are interested in <ref:2604.02543>.
Lu: And they suggest that developing a unified framework for convergence acceleration across different simulator types could be an exciting direction for future work <ref:2604.02543>.
Conclusion: Tom: So we’ve been looking at this paper called "Sparse Probabilistic Richardson Extrapolation." Basically, it’s about finding a smarter way to use simulation data when you have a lot of different tolerance settings in your numerical model <ref:2604.02072#pg1>.
Jane: Right, and the authors are introducing this concept of "extrapolation dimension," which is essentially figuring out the minimum number of simulations you actually need to run to get a good answer for a specific function <ref:2604.02072#pg4>.
Lu: They’re saying that instead of needing an astronomical number of runs, this new method can cut the required simulations down to something polynomial in the number of tolerance settings you have <ref:2604.02072#pg1>.
Meng: So, if you’re running a complex simulation for something like fluid dynamics or agent movement and you’ve got five different accuracy levels, this could mean running way fewer actual experiments to get reliable results <ref:2604.02072#pg1>.
Tom: That’s the big win here. It takes this probabilistic method, which is basically using Bayesian principles to handle uncertainty, and makes it much more practical for real-world engineering problems <ref:two thousand six hundred four point zero two zero seven two#pg1.
Jane: And they showed that when you test it on things like colliding spheres or flocking models, this sparse approach actually beats the other methods we looked at, like Gauss–Richardson Extrapolation <ref:2604.02072#pg1>.
Lu: It’s not just a theoretical trick; the paper shows that under certain conditions, you can get better acceleration than what was previously thought possible for these types of simulators <ref:2604.02072#pg4>.
Meng: But they also gave us some caveats. They found that figuring out the right set of simulations to run—that index set A—is really tricky and often requires you to know your settings very precisely early on <ref:2604.02072#pg1>.
Tom: So, the implication is that we can use this sparsity concept to design experiments much more efficiently, which is huge for saving time and money in model validation <ref:two thousand six hundred four point zero two zero seven two#pg1.
Jane: Exactly. It turns simulation from a brute-force exercise into a more targeted process, though we still need to figure out the best way to estimate that required dimension A <ref:2604.02072#pg1>.
Chris J Oates, Richard Howey, Toni Karvonen
School of Mathematics, Statistics and Physics, Newcastle University · Research Software Engineering, Newcastle University Research Software Engineering Department
stat.ME, stat.CO
Submitted: 2026-04-02
Updated: 2026-11-06
Code: https://github.com/NewcastleRSE/sparse-probabilistic-richardson-extrapolation
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 77/100
The gist: Almost every numerical task can be cast as extrapolation with respect to the fidelity or tolerance parameters of a consistent numerical method <ref:2604.02072#pg2> This perspective enables…
Key concepts
- Extrapolation Dimension (dext(f))
- This is a concept defining the minimum size of an index set required for a function's non-trivial representation. Practically, it represents the fewest simulations necessary to accelerate convergence to the desired result, suggesting sparsity is common in real applications.
- Multivariate Richardson Extrapolation (MRE)
- MRE is used as a benchmark method that does not exploit sparsity. It serves as a baseline comparison against SPRE to demonstrate how much more efficient the new sparse approach is when dealing with multiple tolerance parameters.
- Sparse Probabilistic Richardson Extrapolation (SPRE)
- SPRE leverages the extrapolation dimension concept to significantly reduce simulation requirements, often achieving polynomial scaling in terms of the dimension 'd' rather than super-exponential scaling seen in methods like Gauss–Richardson Extrapolation.
- Sparsity-Exploiting Methodology
- This refers to a new approach developed that is simpler yet more powerful than earlier works. It identifies and utilizes the inherent sparsity present in numerical simulations when multiple tolerance parameters are involved, leading to sharper theoretical guarantees.
Terminology
Summary
Almost every numerical task can be cast as extrapolation with respect to the fidelity or tolerance parameters of a consistent numerical method <ref:2604. p. 0 Sparse Probabilistic Richardson Extrapolation
Chris. Oates1∗
, Richard Howey2
, Toni Karvonen3
1 School of Mathematics, Statistics and Physics, Newcastle University, UK
2 Research Software Engineering, Newcastle University, UK
3 School of Engineering Sciences, Lappeenranta–Lahti University of Technology LUT, FI
April 3, 2026
Abstract
Almost every numerical task can be cast as extrapolation with respect to the fidelity
or tolerance parameters of a consistent numerical method. Oates1∗
, Richard Howey2
, Toni Karvonen3
1 School of Mathematics, Statistics and Physics, Newcastle University, UK
2 Research Software Engineering, Newcastle University, UK
3 School of Engineering Sciences, Lappeenranta–Lahti University of Technology LUT, FI
April 3, 2026
Abstract
Almost every numerical task can be cast as extrapolation with respect to the fidelity
or tolerance parameters of a consistent numerical method. This perspective enables
probabilistic uncertainty quantification and optimal experimental design functionality to be deployed, and also unlocks the potential for the convergence of numerical
methods to be accelerated. However, the number of
simulations was required to increase super-exponentially in d, the number of tolerance
parameters appearing in the numerical method. This paper develops a refined notion of extrapolation dimension, drastically reducing this simulation requirement when
multiple tolerance parameters feature in the numerical method. This paper develops a refined notion of extrapolation dimension, drastically reducing this simulation requirement when
multiple tolerance parameters feature in the numerical method. Sparsity-exploiting
methodology is developed that is simultaneously simpler and more powerful compared
to earlier work, and this is accompanied by sharp theoretical guarantees and substantial
empirical support.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Extrapolation Dimension Concept
The paper introduces the concept of extrapolation dimension, dext(f), which is defined as the minimal value of dim(A), i.e., the minimal cardinality of the index set 0 ∈ A ⊂ N d0 for which f has a non-trivial representation <ref:2604. p. 4 The extrapolation dimension dext(f) of a simulator f is the minimal value of dim(A), i. the minimal cardinality of the index set 0 ∈ A ⊂ N
d
0
for which f has a non-trivial representation (1). the minimal cardinality of the index set 0 ∈ A ⊂ N
d
0
for which f has a non-trivial representation (1). Put in practical terms, we will see that dext(f) is the minimum number of simulations required
to accelerate convergence to f(0); i. (Here ∥β∥0 denote the number of non-zero entries in the vector
β ∈ R
d
. )
A central argument to this paper, which we will substantiate with empirical support, is
that if a simulator admits an expansion of the form (1), then the cardinality of the index set
A is typically (relatively) small.Where the paper says it
Where the paper says it
Where the paper says it
Methods Compared
The paper compares three main approaches:
-
Multivariate Richardson Extrapolation (MRE), which serves as a non-statistical sparsity-exploiting benchmark for SPRE <ref:2604. p. 5
02072#pg4>.Where the paper says it
Although not a statistical extrapolation method, one of the main motivations for considering multivariate Richardson extrapolation (MRE) here is that the number nmin of data needed to implement it is dext(f), which is the minimal possible data requirement. As such, MRE serves as a (non-statistical) sparsity-exploiting benchmark for SPRE.
-
Gauss–Richardson Extrapolation (GRE), which uses a Gaussian process to model f(x) and requires a minimum number of data nmin ≥ (2dd! p. 1
)d, which is super-exponential in d <ref:2604. p. 2Where the paper says it
[2025], who modelled the data-generating function f using a numerical analysis-informed Gaussian process (GP), leading to a method called Gauss–Richardson Extrapolation (GRE); we provide further details in Section 2. The effectiveness of GRE was demonstrated using the aforementioned whole-heart model of Strocchi et al.
02072#pg4>.Where the paper says it
, 2025, Theorems 2 and 4] hold only when a minimum number of data nmin are provided, and this number can be lower-bounded by (2dd! )d , which is super-exponential in d.
-
Sparse Probabilistic Richardson Extrapolation (SPRE), which leverages the new notion of extrapolation dimension to reduce the simulation requirement typically to polynomial in d <ref:2604. p. 2
02072#pg2>.Where the paper says it
As with GRE, our SPRE approach is based on GPs, but here we leverage a new notion of extrapolation dimension which enables us to drastically reduce the number of simulations that need to be performed. Indeed, we establish convergence acceleration guarantees for SPRE for which the data requirement is typically polynomial in d, as opposed to super-exponential.
Convergence Acceleration Guarantees
Theorem 1 shows that for MRE, there exists a constant C, depending only on Xn, such that f h n (0) − f(0) ≤ C z constant in h sup x∈Xh R(x) <ref:2604.02072#pg4>. Theorem 3 establishes convergence acceleration for SPRE, showing that the extrapolation error for the posterior mean of the GP is bounded by Chk z bounded in h RHk(Xh) <ref:2604. p. 9 From Remark 2, the posterior mean of SPRE coincides with p(0), which is also the output
of MRE. In this edge case, a convergence acceleration result for SPRE can be deduced from
Theorem 1. 1, and theoretical analysis contained in Section 3. Remarkably, it is shown that not
only does SPRE match the convergence acceleration of MRE for the same data requirement
(which in turn depends only on the extrapolation dimension), but SPRE can unlock additional convergence acceleration if appropriate regularity conditions are satisfied.Where the paper says it
Where the paper says it
Empirical Validation
Three case studies—two colliding spheres, five colliding shapes, and an agent-based flocking model—demonstrate that extrapolation sparsity appears to hold in each case study <ref:2604.02072#pg2>. In these settings where extrapolation sparsity can be exploited, SPRE is shown to outperform GRE <ref:2604. p. 2 Indeed, we establish convergence acceleration guarantees for SPRE for which
the data requirement is typically polynomial in d, as opposed to super-exponential. Second,
through several detailed case studies we identify low extrapolation dimension as a general
phenomenon in real-world applications, in the sense that all of the simulators we consider
exhibit some form of low effective dimension (or sparsity) which can be directly exploited in
SPRE. To
∗Correspondence should be sent to chris. 1
arXiv:2604. In particular, any
theoretical analysis will need to account for the effect of the choice of kernel. Further, there
are the important practical matters of how the index set A can be estimated from data,
and how the evaluation locations {xi}
n
i=1 should be designed to be maximally informative
subject to a total computational budget.Where the paper says it
Where the paper says it
Where the paper says it
Implementation Details
The methodology involves a sequential strategy that alternates between learning k and A and selecting which simulations to run next <ref:2604.02072#pg2>. The authors employ leave-one-out cross-validation (LOOCV) to quantify the suitability of a kernel k and a set A through the predictive log-density L(k, A) <ref:2604. p. 8 )d = 64 to guarantee
convergence acceleration, and achieves this by fitting a numerical analysis-informed GP. Right: Sparse Probabilistic Richardson Extrapolation (SPRE) applied to a dataset of size
nmin = 1+dext(f), where the additional data point enables kernel parameters to be estimated
using leave-one-out cross-validation, as described in Section 3. In particular, any
theoretical analysis will need to account for the effect of the choice of kernel. Further, there
are the important practical matters of how the index set A can be estimated from data,
and how the evaluation locations {xi}
n
i=1 should be designed to be maximally informative
subject to a total computational budget.Where the paper says it
Where the paper says it
Conclusion
The contribution establishes sparsity-exploiting extrapolation methods as a novel frontier for acceleration of complex simulators <ref:2604.02072#pg2>. SPRE is presented as a black box probabilistic numerical method with Bayesian principles used to quantify uncertainty regarding the continuum model of interest <ref:2604. p. 0 This perspective enables
probabilistic uncertainty quantification and optimal experimental design functionality to be deployed, and also unlocks the potential for the convergence of numerical
methods to be accelerated. Recent work established Probabilistic Richardson Extrapolation as a proof-of-concept, demonstrating how parallel multi-fidelity simulation can
be used to accelerate simulation from a whole-heart model.Where the paper says it
References
B. Adcock. Function recovery and optimal sampling in the presence of nonuniform evaluation costs <ref:2604.02072#pg9> F. Bach. On the effectiveness of Richardson extrapolation in data science <ref:2604. p. 1 [2025],
who modelled the data-generating function f using a numerical analysis-informed Gaussian
process (GP), leading to a method called Gauss–Richardson Extrapolation (GRE); we provide further details in Section 2. The effectiveness of GRE was demonstrated using the
aforementioned whole-heart model of Strocchi et al. Keywords: computer models, extrapolation, Gaussian process, kernel methods, uncertainty quantification
1 Introduction
Mathematical models are routinely used to represent mechanisms hypothesised to govern
phenomena of interest. Inference for the parameters of these models demands a comparison
of simulations from the model against a real-world dataset. Oates1∗
, Richard Howey2
, Toni Karvonen3
1 School of Mathematics, Statistics and Physics, Newcastle University, UK
2 Research Software Engineering, Newcastle University, UK
3 School of Engineering Sciences, Lappeenranta–Lahti University of Technology LUT, FI
April 3, 2026
Abstract
Almost every numerical task can be cast as extrapolation with respect to the fidelity
or tolerance parameters of a consistent numerical method. This perspective enables
probabilistic uncertainty quantification and optimal experimental design functionality to be deployed, and also unlocks the potential for the convergence of numerical
methods to be accelerated.Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Sparsity exploitation in extrapolation dimension allows for drastically reduced simulation requirements when multiple tolerance parameters are present, potentially reducing required data from super-exponential to polynomial dependence on d.
-
The Sparse Probabilistic Richardson Extrapolation (SPRE) method can be implemented with exponentially fewer data points than the Gauss–Richardson Extrapolation (GRE) method when extrapolation sparsity is present, matching its convergence acceleration while unlocking statistical functionalities like uncertainty quantification and experimental design.
-
AI systems can utilize data-driven identification of the index set A through leave-one-out cross-validation to select optimal kernel parameters and model terms, leading to a principled selection of the expansion (1) for complex simulators.
-
The system can perform cost constrained experimental design by minimizing the posterior variance of f(0) subject to a total computational budget, as described by equation (11).
-
By leveraging different kernels such as the white noise kernel, Matern-1/2 kernel, and Matern-3/2 kernel, the AI system can achieve convergence acceleration rates up to O(h 4) for smooth residuals in some cases.
Abstract
Almost every numerical task can be cast as extrapolation with respect to the fidelity or tolerance parameters of a consistent numerical method. This perspective enables probabilistic uncertainty quantification and optimal experimental design functionality to be deployed, and also unlocks the potential for the convergence of numerical methods to be accelerated. Recent work established Probabilistic Richardson Extrapolation as a proof-of-concept, demonstrating how parallel multi-fidelity simulation can be used to accelerate simulation from a whole-heart model. However, the number of simulations was required to increase super-exponentially in d, the number of tolerance parameters appearing in the numerical method. This paper develops a refined notion of 'extrapolation dimension', drastically reducing this simulation requirement when multiple tolerance parameters feature in the numerical method. Sparsity-exploiting methodology is developed that is simultaneously simpler and more powerful compared to earlier work, and this is accompanied by sharp theoretical guarantees and substantial empirical support.
Sources
- Optimally balancing exploration and exploitation to automate multi-fidelity statistical estimation
- Comparison of Bayesian methods for extrapolation of treatment effects: a large scale simulation study
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes