Monte Carlo and quasi-Monte Carlo integration for likelihood functions
Yanbo Tang · 2025
Read Monte Carlo and quasi-Monte Carlo integration for likelihood functions by Yanbo Tang (2025) 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-2506-21733.txt.
Introduction
Yanbo Tang compares plain and quasi-Monte Carlo integration for the normalizing constants and marginal likelihoods that Bayesian work lives on. The paper from twenty twenty-five tracks how error scales with data count, grid size, and integral dimension jointly. At fixed dimension, random sampling's relative error picks up an extra data-driven factor that quasi sampling mostly dodges. A clean inequality states when quasi sampling wins.
High dimensions reverse the comfort. Against a Halton grid, plain Monte Carlo degrades more slowly as dimension grows, though both methods scale poorly. A new bound on the Halton sequence's star discrepancy in high dimensions is a side contribution. Practitioners get a map of which integrator to trust in which regime.
Catalog record
| CREATOR | Yanbo Tang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-21733
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Monte Carlo and quasi-Monte Carlo integration for likelihood functions Yanbo Tang Abstract We compare the integration error of Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods for approximating the normalizing constant of posterior distributions and certain marginal likelihoods. In doing so, we characterize the dependency of the relative and absolute integration errors on the number of data points ( n n ), the number of grid points ( m m ) and the dimension of the integral ( p p ). We find that if the dimension of the integral remains fixed as n n and m m tend to infinity, the scaling rate of the relative error of MC integration includes an additional n 1 / 2 log ( n ) p / 2 n^{1/2}\log(n)^{p/2} data-dependent factor, while for QMC this factor is log ( n ) p / 2 \log(n)^{p/2} . In this scenario, QMC will outperform MC if log ( m ) p − 1 / 2 / m n log ( n ) < 1 \log(m)^{p-1/2}/\sqrt{mn\log(n)}<1 , which differs from the usual result that QMC will outperform MC if log ( m ) p / m 1 / 2 < 1 \log(m)^{p}/m^{1/2}<1 .The accuracies of MC and QMC methods are also examined in the high-dimensional setting as p → ∞ p\rightarrow\infty , where MC gives more optimistic results as the scaling in dimension is slower than that of QMC when the Halton sequence is used to construct the low discrepancy grid; however both methods display poor dimensional scaling as expected. An additional contribution of this work is a bound on the high-dimensional scaling of the star discrepancy for the Halton sequence. keywords Numerical integration ; low discrepancy grids ; marginal likelihood ?? Department of Mathematics, Imperial College London, London, UK 1 Introduction The error analysis for most numerical integration techniques is performed on a fixed function f(\theta) as number of functional evaluations m\rightarrow\infty . However, in most statistical applications the function being integrated changes as more samples (denoted by n ) are collected. Assuming the parameter space \Theta\subset\mathbb{R}^{p} is compact, the normalizing constant of a posterior distribution can approximated by \displaystyle\int_{\Theta}\pi(\theta)\exp(L_{n}(\theta;Y_{n}))d\theta\approx\frac{1}{m}\sum_{i=1}^{m}\pi(\theta_{i})\exp(L_{n}(\theta_{i};Y_{n})), (1) where \pi(\theta) is the prior, l_{n}(\theta;Y_{n}) is the log-likelihood function and \theta_{i} for i=1,\dots,m is a collection of random or deterministic grid points in \Theta ; Monte Carlo (MC) integration generates these points randomly from an uniform measure, while quasi-Monte Carlo methods (QMC) use a deterministic low discrepancy grid which does not “clump” together too much, see Figure 1 for an illustration of this. Beyond approximating the normalizing constant, these integration methods can also be used in random effects models to approximate the marginal likelihood \displaystyle L_{n}(\theta;Y_{n})=\int_{U}\pi(u)\exp(L_{n}(\theta,u;Y_{n}))du\approx\frac{1}{m}\sum_{i=1}^{m}\pi(u_{i})\exp(L_{n}(\theta,u_{i};Y_{n})), (2) which can then be used to compute the marginal maximum likelihood estimator (MMLE) and generate confidence regions by estimating the curvature around the MMLE – although to do so would require multiple evaluations of the marginal likelihood and therefore require multiple instances of MC. Given that limit theorems (in n ) are used to characterize the distributional properties of the MMLE, it is then natural to analyze the approximation errors of these integrals as n\rightarrow\infty ; intuitively a reasonable condition for the approximate MMLE to be consistent is to require that the relative approximation error tends to 0 as n\rightarrow\infty uniformly around the true or pseudo-true parameter, otherwise a non-negligible bias will persist in the limit. The existing convergence rates for MC and QMC do not account for the effect of n or p , the most commonly quoted rate of convergence of Monte Carlo integration being O(m^{-1/2}) and O(\log(m)^{p}m^{-1}) for QMC. The benefit of working with random functions is that they concentrate towards a population version which is better behaved than an arbitrary function. We exploit these structures to derive bounds for MC or QMC where the dimensional dependencies of the integration errors are explicit, and compare their performances under reasonable smoothness assumptions. These upper bounds in fixed and high dimensions will be useful in providing a baseline comparison for Markov Chain Monte Carlo (MCMC) and sequential Monte Carlo (SMC), which also suffer the curse of dimensionality. For a particular MCMC method to be considered viable, it must at the very least perform better than simple MC; although bounds for the performance of MCMC are much harder to obtain than for MC and QMC. We first give some background on MC and QMC in Section 2 , before moving on to our main results for integrating the normalizing constant of a posterior distribution for the fixed-dimensional and high-dimensional case in Section 3 . We then examine the implications of our results for marginal likelihoods in Section 4 , and provide some simulation results in Section 5 before concluding the main portion of the paper with some discussions in Section 6 . Technical appendices A and B contain proofs of lemmas required for our main results for MC and QMC integration respectively. 2 Background MC integration leverages the randomness of the grid points by using the strong law of large numbers and the central limit theorem (CLT) to show consistency and rates of convergence of the estimate under first and second moment assumptions. However these results require that the function remains fixed: if both m and n change, then it is no longer clear if CLT applies to this sequence. We take an approach similar to that of Tang 2024 , where concentration inequalities are used instead of the CLT. The advantage of this approach is that it is possible to derive results when the dimension of the integral increases with the number of samples, which is necessary for the asymptotic normality of the MMLE in generalized linear mixture models, for example see Jiang, Wand and Bhaskaran 2022 and Jiang, Wand and Ghosh 2024 . The integration error for QMC is obtained by bounding the star discrepancy of the grid points and the Hardy-Kraus (HK) variation of the function being integrated, and then applying Koksma-Hlawka’s inequality; let us define these terms. Define the local discrepancy of a sequence (x_{1},\dots,x_{m}) –for x_{i}\in[0,1]^{p} –as \displaystyle\delta(a;x_{1},\dots,x_{m})=\frac{1}{m}\sum_{i=1}^{m}\mathbb{I}_{x_{i}\in[0,\mathbb{a})}-\prod_{j=1}^{p}a_{j}, where \mathbb{a}\in[0,1]^{p} and [0,\mathbb{a})=[0,a_{1})\times[0,a_{2})\times\dots\times[0,a_{p}) and we can think of the discrepancy between the estimated volume of rectangular sets based on our sample (x_{1},\dots,x_{m}) and their true volume. We then define the star discrepancy as \displaystyle D_{m}^{\star}(x_{1},\dots,x_{m})=\sup_{\mathbb{a}\in[0,1)^{p}}\delta(\mathbb{a};x_{1},\dots,x_{m}). (3) The class of functions considered in this paper is assumed to be p times differentiable, and this assumption implies an upper bound of the HK variation involving the p -th order partial derivatives of the function f(x) on the domain of integration: \displaystyle V_{HK}(f)\leq\sum_{\alpha\subset\mathcal{P}\{1,2,\dots,p\}-\emptyset}\int_{[0,1]^{p}}\frac{\partial^{|\alpha|}}{\partial x_{\alpha}}f(x_{\alpha},1_{-\alpha})dx_{\alpha}, where \mathcal{P}(A) denotes the power set of A , and the summation is taken over all subsets of 1:p except the empty set, x_{\alpha} denotes the subset of the vector x whose indices are in \alpha and 1_{-\alpha} denotes a set of 1 on all of the indices which are not in \alpha . For some intuition, it is worth noting that the HK variation in one dimension is the total variation of the function in [0,1] . The Koksma-Hlawka inequality then upper bounds the absolute error between the integral and its estimate by product of the two quantities introduced above \displaystyle\left|\int_{[0,1]^{p}}f(x)dx-\frac{\sum_{i=1}^{m}f(x_{i})}{n}\right|\leq D_{m}^{\star}(x_{1},\dots,x_{m})\cdot