Discretization approximation: An alternative to Monte Carlo in Bayesian computation

arXiv:2512.11475 · stat.CO · Submitted 2025-12-12 · Read on arXiv

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: We're looking at the paper: "Discretization approximation: An alternative to Monte Carlo in Bayesian computation".

Jane: Here's the gist of the paper. In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation <ref:2512.11475#pg2>.

Tom: This method is very simple to understand and to implement, requiring only the calculation of posterior density values as probability masses at pre-specified support points <ref:2512.11475#pg4>.

Jane: The resulting discrete distribution can be a good approximation to the target posterior distribution, allowing all posterior quantities, including means, standard deviations, and quantiles, to be approximated by those of this completely known discrete distribution <ref:2512.11475#pg4>.

Tom: Core Methodology The basic idea of the method is discretization of the density function <ref:2512.11475#pg4>.

Title and authors: Tom: So we’re looking at this paper today: "Discretization approximation: An alternative to Monte Carlo in Bayesian computation." It’s a deterministic method for calculating posterior distributions without relying on random sampling like Markov Chain Monte Carlo methods.

Jane: That sounds really interesting because MCMC can get bogged down with high computational cost and convergence issues, so having something deterministic is always appealing when we're trying to get answers fast. What exactly does this discretization approximation method actually do?

Tom: Well, the core idea is to take that continuous density function and approximate it by turning it into a discrete distribution defined only at specific support points. You calculate the posterior density values just as probability masses at those pre-specified points, and then you use that resulting discrete distribution to estimate all the usual things we care about, like means, standard deviations, and quantiles.

Lu: The paper says this gives you a completely known discrete distribution which is expected to be a good approximation to the target posterior density as you increase the number of support points M > one <ref:2512.11475#pg1,be a good approximation to the target posterior>.

Meng: It sounds like it’s trying to bypass some of the randomness that makes MCMC so slow, but I gotta ask—is it really deterministic? Because in my world, I need something that runs reliably on production traffic, not something whose quality depends on how well we pick those points.

Tom: That's the key point they make; it is a deterministic procedure because it only requires calculating density values at pre-specified support points and then using that known discrete distribution to approximate everything.

Jane: Right, so if we look at how they handle those support points, what's the actual process for picking them? I remember hearing about different ways people choose sampling locations in data science.

Tom: They take a set of support points, let's call it AM, which is defined by M elements in a space that’s usually one-dimensional or higher. The requirement is that these points have to be uniformly scattered across the interval from zero to one.

Lu: And they define a probability measure on those support points where the probability of landing on any specific point ai is just the value of the density function at that point divided by the sum of all density values at all M points.

Title and authors: Meng: That sounds computationally intensive just setting up that measure, but if it works for high-dimensional models, it’s a big win for efficiency in production environments.

Jane: The paper talks about how this approximation improves as we increase M, and they establish a convergence rate for this discretization approximation as the number of support points goes to infinity. They also mentioned something specific about using quasi-Monte Carlo sequences for generating those points.

Tom: That’s the big theoretical claim: if you generate those support points using quasi-Monte Carlo sequences, the convergence rate is actually the same as it is in integration approximation, which is generally faster than that optimal statistical rate of one over the square root of M.

Lu: That’s significant because it means we can achieve better accuracy with fewer support points than what standard random sampling would allow for this type of problem.

Jane: So, if we translate that into something practical for someone just listening, what does that mean for how accurate our posterior estimates are when we use this discretization approximation instead of something like a standard Monte Carlo approach?

Tom: It means you can approximate all the posterior quantities—the means, the standard deviations, and the quantiles—using those values from the completely known discrete distribution.

Meng: So, it replaces a potentially slow or unstable simulation with a fixed set of calculated values based on those support points. That sounds like it could cut down our runtime significantly if we can manage the setup cost of finding those points.

Jane: Exactly, and they also showed how to get samples from this discrete distribution using random sampling, and they even have deterministic design strategies to make the resulting representation points more representative of the target distribution than just picking them randomly.

Lu: Theorem three shows that with these deterministic design strategies, the error between the approximation and the target distribution falls off proportionally to M over N, where N is related to how many samples you take.

Tom: And they’ve shown it can handle various scenarios well, even in high-dimensional cases. In one-dimensional examples, this discretization approximation performs much better than two other Monte Carlo methods they compared it against.

Jane: It also works for things like linear regression models where we need to compute the posterior means and quantiles of the parameters, and they noted that its speed is good enough for more than two stages in most cases.

Title and authors: Meng: How fast is "good enough" when you're deploying this? What about the practical cost of running this approximation compared to a standard MCMC sampler on a real dataset?

Tom: The paper suggests that discretization approximation has low complexity, requiring only O of M operations, which points toward it being very computationally efficient in terms of the number of calculations needed.

Lu: And they also mentioned that if you have finite expected values for certain quantities, specifically E(k1...kd)(mu f) and the variance V(f(k1...kd)), then the convergence properties hold nicely.

Jane: So, we've covered how it works mechanically, the theoretical guarantees about its speed when using quasi-Monte Carlo sequences, and some practical results showing it beats other methods in low dimensions. What’s left for us?

Tom: They’re wrapping up by saying that this discretization approximation method has a solid foundation from numerical integration theory, and because it's deterministic, noniterative, and easy to implement with fast convergence, it outperforms MCMC in terms of both accuracy and speed for many problems.

Meng: So it’s a deterministic tool that offers better performance metrics than the stochastic methods we usually default to for these complex models. That’s something I can take back to my engineering team.

Lu: It seems like they are positioning this as a good complement to MCMC, suggesting it could be used alongside other methods in Bayesian computation for developing more effective algorithms moving forward.

Jane: So, to wrap up this discussion on "Discretization approximation: An alternative to Monte Carlo in Bayesian computation," we see a deterministic method that uses pre-specified support points and known density values to approximate the target posterior distribution for calculating all key statistics.

Tom: It’s fast, it's deterministic, and it has strong theoretical backing regarding its convergence when using quasi-Monte Carlo sequences.

Lu: The work gives us a way to get better approximations without relying on the potentially slow or tricky aspects of MCMC sampling.

Meng: For me, the main thing is that if you can manage the setup cost of those support points efficiently, this could be a much cheaper way to get high-quality posterior estimates for our models.

Jane: We’ll keep an eye on how this deterministic approach fits into the broader landscape of Bayesian computation and whether it becomes a practical tool for real-world applications.

The paper's summary: Tom: So, this paper is about taking Bayesian computation, which usually relies on random sampling like Markov Chain Monte Carlo methods, and replacing it with something deterministic instead of something random.

Jane: It’s proposing a method called discretization approximation that turns the continuous density function into a discrete distribution defined only at specific support points.

Tom: Exactly. The idea is that instead of running thousands of simulations to get an answer, you just calculate the density values at those pre-specified points and use that known discrete distribution to estimate all the things we care about—the means, the standard deviations, and even quantiles.

Jane: The authors are saying this resulting discrete distribution is expected to be a very good approximation of the true posterior distribution if you choose enough support points.

Tom: They set up a set of support points, let's call them AM, which are spread out uniformly across some space. Then they define a probability measure on those points based on the density function values at those locations.

Jane: The core idea is that as you increase the number of these support points, M, the approximation gets closer and closer to the actual target distribution.

Tom: They established some solid theoretical backing for this. If you generate those support points using quasi-Monte Carlo sequences—which are deterministic but often better than purely random choices—the convergence rate is actually faster than what we usually see in standard integration approximation.

Jane: That’s a big deal because it suggests that if the setup is done right, you can get a good result with fewer points than traditional methods would need.

Tom: They show mathematically that for enough support points, the distance between their discrete measure and the target measure falls off with M to some power C times delta to the power of M.

Jane: And they also looked at sampling properties. They showed you can actually generate random samples from this discrete distribution, which is useful because it gives us a way to get actual data points from it.

Tom: But they also brought in deterministic design strategies for picking those support points, and these strategies help make the resulting approximation more representative of the target distribution than just picking them randomly.

Jane: In practice, they have shown this works pretty well across different dimensions, even in high-dimensional settings where things get complicated.

Tom: In one-dimensional examples specifically, their method outperformed two other Monte Carlo methods they tested against. And for linear regression models, it can actually compute the posterior means and quantiles of the parameters quite quickly.

Jane: It sounds like they are showing that this deterministic approach has low computational cost and fast convergence while still delivering good accuracy for many problems.

Tom: The paper concludes that discretization approximation is deterministic, noniterative, and easy to implement, making it a solid alternative to methods like Markov Chain Monte Carlo because it’s both fast and accurate.

Jane: They suggest this method could be a good tool to use alongside MCMC or other techniques in Bayesian computation for building more effective algorithms moving forward.

Tom: So, if you're looking for a way to get posterior estimates without the randomness of sampling, this paper lays out a deterministic framework that has some really interesting convergence guarantees when you use smart support point generation.

The paper's improvements: Tom: So, we're looking at how they suggest improving this discretization approximation method for Bayesian computation. It’s not just about the basic setup anymore; they are talking about making it more flexible and better at handling complex problems.

Jane: They are focusing on two big areas: how to generate those support points effectively and how to use that knowledge to get better results from the approximation itself.

Tom: The first thing they suggest is using deterministic design strategies for picking those support points, which helps make the resulting representation of the target distribution much more accurate, even when you're dealing with high-dimensional data.

Jane: That means instead of just throwing points randomly into the space, you can strategically place them to capture the important parts of that density function better.

Tom: And on top of that, they’ve looked at how to combine this discretization approach with other things, like random Fourier features simplification and support points generated by those same deterministic strategies.

Jane: That sounds like they are trying to build a hybrid method, using the best parts of both worlds—the known structure from the discretization and the sampling capability from something else.

Tom: They even show some specific results for high-dimensional problems, where they managed to get a computing time of about zero point four seconds in certain examples.

Jane: That's concrete, Tom. It means for really big datasets where MCMC would take forever, this method can actually be fast enough to run in a reasonable amount of time.

Tom: Exactly. And theoretically, they showed how the error scales nicely with M over N, where N relates to the number of samples you draw from the discrete distribution.

Jane: So what does this mean for someone who just wants a better tool? It means you can tackle those high-dimensional posteriors that used to be completely out of reach because you could get a decent estimate in under half a second instead of waiting for hours.

Tom: The implication is that this deterministic framework isn't just theoretically interesting; it has practical performance benefits for complex AI models that need fast inference or quick analysis.

Jane: It sounds like the authors are pointing toward an algorithm where you can leverage the speed of discretization while still maintaining a high degree of accuracy.

Tom: That’s right. They’re moving beyond just showing it works to suggesting how to build something more robust for real-world deployment, which is what I care about when I'm shipping models.

Jane: It makes this method feel less like a pure academic exercise and more like a tool that could actually be put into production pipelines.

Tom: And they are looking ahead by suggesting combining this discretization approximation with other methods, maybe even MCMC itself, to see if we can get the best of both worlds.

Jane: So the next step is integrating this deterministic structure into a larger framework for Bayesian computation rather than just using it as a standalone trick.

Tom: That’s what they are hinting at. It’s not about replacing everything; it's about augmenting existing tools with this deterministic precision.

Conclusion: Tom: So we’ve been talking about this discretization approximation paper, "Discretization approximation: An alternative to Monte Carlo in Bayesian computation," which basically shows how you can use a deterministic method instead of relying on random sampling for posterior distributions.

Jane: That’s right, it turns the continuous math into a discrete set of values at specific points, and those points are chosen systematically.

Tom: The main implication is that for many problems, especially in high dimensions, you can get very accurate answers much faster than traditional Monte Carlo methods allow.

Jane: It's not just about getting a slightly better number; it’s about having a method that has a predictable convergence rate when you increase the number of support points.

Tom: The authors did show that by using quasi-Monte Carlo sequences for those points, the convergence speed is actually faster than what we usually expect from random sampling methods.

Jane: So, to summarize, they propose a deterministic way to approximate a complex posterior distribution by defining it on a discrete set of support points and using those values to calculate all the statistics you need.

Tom: It's definitely a solid piece of work because it’s deterministic and easy to implement compared to some other sampling techniques we've seen.

Jane: The real win here is that they prove the theoretical guarantees for how accurate that approximation stays as you add more support points, which gives us confidence in using it.

Lu: I think the idea of combining this with deterministic design strategies for picking those points is really ambitious; if you can make those points representative, it opens up a whole new way to explore these distributions.

Meng: From an engineering standpoint, I'm interested in the speed they achieved in high-dimensional examples; if that zero point four seconds estimate translates to real production time, that’s a win for deployment.

Lalam: I feel confident in this result because the mathematical foundation they built is pretty rigorous, and it directly addresses the computational cost issue that plagues many Bayesian inference methods.

Tom: So we’ve seen how they use this discretization approximation to get faster and more reliable estimates for things like means and quantiles in complex models.

Jane: It suggests a path forward where we can use deterministic structure to give us better performance metrics when running these kinds of calculations, which is something I think is really valuable for applied science.

Tom: This paper lays out a lot of groundwork for combining this with other techniques down the road, and that’s where the future work lies.

Shifeng Xiong

SKLMS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences · School of Mathematical Sciences, University of Chinese Academy of Sciences

stat.CO

Submitted: 2025-12-12

Updated: 2026-11-01

Comments: 26 pages, 3 figures

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 77/100

The gist: In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation <ref:2512.11475#pg2>.

Key concepts

Discretization Approximation
A method that approximates a continuous probability density function by calculating its values only at a finite set of chosen points. These points form a completely known discrete distribution that serves as an accurate stand-in for the true, complex posterior distribution.
Support Point Set (AM)
A collection of specific points in the domain [0, 1]^d chosen to define the discrete approximation. These points must be uniformly scattered and are crucial because their values are used to calculate the probability mass function of the approximation.
Convergence Rate
How quickly the approximation gets closer to the true posterior distribution as more support points (M) are added. The paper shows that using quasi-Monte Carlo sequences can achieve a convergence rate faster than standard statistical methods, leading to quicker and more accurate results.

Terminology

Summary

In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation <ref:2512. p. 0

Where the paper says it

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China xiong@amss. cn Abstract In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation.

11475#pg2>. This method is very simple to understand and to implement, requiring only the calculation of posterior density values as probability masses at pre-specified support points <ref:2512. p. 0
Where the paper says it

cn Abstract In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation. Discretization approximation is very simple to understand and to implement, It only requires calculating posterior density values as probability masses at pre-specified support points.

11475#pg4>. The resulting discrete distribution can be a good approximation to the target posterior distribution, allowing all posterior quantities, including means, standard deviations, and quantiles, to be approximated by those of this completely known discrete distribution <ref:2512. p. 0
Where the paper says it

The resulted discrete distribution can be a good approximation to the target posterior distribution. All posterior quantities, including means, standard deviations, and quantiles, can be approximated by those of this completely known discrete distribution.

11475#pg4>.

Core Methodology

The basic idea of the method is discretization of the density function <ref:2512.11475#pg4>. First, a support point set AM = 0 M i=1 ⊂ [0, 1]d for a large integer M is taken, where the elements are required to be uniformly scattered <ref:2512. p. 3

Where the paper says it

First take a support point set AM = {ai} M i=1 ⊂ [0, 1]d for a large integer M. The elements of AM are required to be uniformly scattered.

11475#pg5>. A probability measure µ(f,AM) on AM is defined such that P(X(f,AM) = ai) = pi = f(ai)/PM j=1 f(aj) for i = 1. p. 8
Where the paper says it

Suppose that there exists a one-to-one map h defined on [0, 1]d such that the random vector Y = h(X) ∼ ψ(x) for X being uniformly distributed on [0, 1]d . By the integration equality, Z Rd f(x)dx = Z Rd f(x) ψ(x) ψ(x)dx = Z [0,1]d f (h(x)) ψ (h(x))dx, we define a probability measure µ(f,AM) on the support point set AM = {h(ai)} M i=1 as P X(f,AM) = h(ai) = pi = f (h(ai)) /ψ (h(ai)) PM j=1 f (h(aj )) /ψ (h(aj )) , i = 1, .

.., M <ref:2512. p. 0
Where the paper says it

KEY WORDS: Markov chain Monte Carlo; proposal distribution; quasi-Monte Carlo; representation point; space-filling design. 1 arXiv:2512.

11475#pg5>. This discrete measure µ(f,AM) is completely known and can be expected to be very close to the target measure µf as M increases <ref:2512. p. 3
Where the paper says it

Note that the discrete measure µ(f,AM) is completely known. It can be expected that, if AM possesses some dense properties on [0, 1]d , then µ(f,AM) will become very close to µf as M increases.

11475#pg5>.

Convergence and Theoretical Guarantees

The convergence rate of discretization approximation is established as the number of support points M goes to infinity <ref:2512.11475#pg4>. If the support points are generated from quasi-Monte Carlo sequences, then the rate is actually the same as that in integration approximation, generally faster than the optimal statistical rate Op(1/√M) <ref:2512. p. 0

Where the paper says it

We establish the convergence rate of discretization approximation as the number of support points goes to infinity. If the support points are generated from quasi-Monte Carlo sequences, then the rate is actually the same as that in integration approximation, generally faster than the optimal statistical rate.

11475#pg4>. Theorem 1 states that for sufficiently large M, dK(µ(f,AM), µf) ⩽ CδM,d <ref:2512. p. 7
Where the paper says it

The following theorem shows its convergence properties. For sufficiently large M and N, dK(µ(N,AM) , µf ) ⩽ CδM,d + C0M/N, (7) where C and C0 are positive constants independent of N, M, and d.

11475#pg7>. Furthermore, if E(k1,…,kd)(µf) < ∞ and V (f(k1,…,kd)). p. 5
Where the paper says it

For sufficiently large M, we have dK(µ(f,AM) , µf ) ⩽ CδM,d, (3) where C is a positive constant independent of M and d. Furthermore, if E(k1,.

Sampling Properties

Random samples from the density f can be generated from the discrete distribution µ(f,AM) <ref:2512.11475#pg9>. Theorem 2 indicates that if δM,d = O(1/√N), then dK(µ(N,AM), µf) = Op(1/√N) <ref:2512. p. 6

Where the paper says it

The following theorem indicates that µ(N,AM) is asymptotically equivalent to the empirical measure of the sample from µf . Suppose δM,d = O(1/ √ N).

11475#pg9>. Deterministic design strategies can improve the representativeness of µ(N,AM) from random sampling <ref:2512. p. 6
Where the paper says it

,kd)(µf ) = Op(1/ √ N). (6) Usually deterministic design strategies can improve the representativeness of µ(N,AM) from random sampling.

11475#pg9>. Theorem 3 shows that dK(µ(N,AM), µf) ⩽ C0M/N <ref:2512. p. 7
Where the paper says it

The following theorem shows its convergence properties. For sufficiently large M and N, dK(µ(N,AM) , µf ) ⩽ CδM,d + C0M/N, (7) where C and C0 are positive constants independent of N, M, and d.

11475#pg9>.

Practical Applications and Performance

Numerical examples demonstrate that the proposed method performs quite well for both low-dimensional and high-dimensional cases <ref:2512.11475#pg4>. In one-dimensional examples, DA has much better performance than the two MC methods <ref:2512. p. 0

Where the paper says it

We also provide random sampling and representation point construction methods from discretization approximation. Numerical examples including some benchmarks demonstrate that the proposed method performs quite well for both low-dimensional and high-dimensional cases.

11475#pg9>. For linear regression models, DA can compute posterior means and quantiles of the parameters <ref:2512. p. 5
Where the paper says it

Theorem 1 indicates that the completely known distribution µ(f,AM) are very close to µf , and that the approximation error can be arbitrarily small. Therefore, the means, quantiles, and standard deviations of µ(f,AM) , which are easy to compute, can be used to approximate those of µf .

11475#pg9>. The fast speed of discretization approximation allows more than two stages for most cases <ref:2512. p. 2
Where the paper says it

The results are encouraging, demonstrating that the proposed method performs well for all these examples in both low-dimensional and high-dimensional cases. In particular, it outperforms popular MC/MCMC methods in terms of accuracy and/or speed.

11475#pg10>.

Conclusion and Future Directions

Discretization approximation has a solid theoretical foundation from numerical integration theory, and is deterministic, noniterative, flexible, and easy to implement with fast convergence and low computational cost <ref:2512.11475#pg22>. It outperforms MCMC in terms of both accuracy and speed for many problems <ref:2512. p. 2

Where the paper says it

The results are encouraging, demonstrating that the proposed method performs well for all these examples in both low-dimensional and high-dimensional cases. In particular, it outperforms popular MC/MCMC methods in terms of accuracy and/or speed.

11475#pg4>. The work suggests that discretization approximation can be a good complement to MCMC <ref:2512. p. 0
Where the paper says it

Discretization approximation is very simple to understand and to implement, It only requires calculating posterior density values as probability masses at pre-specified support points. The resulted discrete distribution can be a good approximation to the target posterior distribution.

11475#pg21>. In the future, discretization approximation can be combined with MCMC or other methods to develop more effective algorithms in Bayesian computation <ref:2512. p. 0
Where the paper says it

Discretization approximation: An alternative to Monte Carlo in Bayesian computation Shifeng Xiong1 2 1. SKLMS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China 2.

11475#pg10>.

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

  1. Deterministic Approximation for Bayesian Computation: The system can compute posterior quantities such as means, standard deviations, and quantiles by calculating density values at pre-specified support points, which are approximated by a completely known discrete distribution.

  2. Superior Sampling and Representation Point Construction: The AI can generate both random sampling and deterministic design strategies from discretization approximation, producing representation points that act as representation points of the target distribution.

  3. Faster Convergence Rate for Approximations: When support points are generated from quasi-Monte Carlo sequences, the convergence rate is actually the same as that in integration approximation, generally faster than the optimal statistical rate Op(1/sqrt(M)) and can be much higher for smooth functions.

  4. Efficient High-Dimensional Posterior Calculation: The system can approximate posterior predictive densities using support points generated by discretization approximation and random Fourier features simplification, achieving a computing time of about 0.4 seconds in specific examples with high-dimensional problems.

Abstract

In this paper we propose a new deterministic approximation method, called discretization approximation, for Bayesian computation. Discretization approximation is very simple to understand and to implement, It only requires calculating posterior density values as probability masses at pre-specified support points. The resulting discrete distribution can be a good approximation to the target posterior distribution. All posterior quantities, including means, standard deviations, and quantiles, can be approximated by those of this completely known discrete distribution. We establish the convergence rate of discretization approximation as the number of support points goes to infinity. If the support points are generated from quasi-Monte Carlo sequences, then the rate is actually the same as that in integration approximation, generally faster than the optimal statistical rate. In this sense, discretization approximation is superior to the popular Markov chain Monte Carlo method. We also provide random sampling and representation point construction methods from discretization approximation. Numerical examples including some benchmarks demonstrate that the proposed method performs quite well for both low-dimensional and high-dimensional cases.

Related papers