Search

Importance Sampling (IS), an effective variance reduction strategy in Monte Carlo (MC) simulation, is frequently utilized for Bayesian inference and other statistical challenges. Quasi-Monte Carlo (QMC) replaces the random samples in MC with low discrepancy points and has the potential to substantially enhance error rates. In this paper, we integrate IS with a randomly shifted rank-1 lattice rule, a widely used QMC method, to approximate posterior expectations arising from Bayesian Inverse Problems (BIPs) where the posterior density tends to concentrate as the intensity of noise diminishes. Within the framework of weighted Hilbert spaces, we first establish the convergence rate of the lattice rule for a large class of unbounded integrands. This method extends to the analysis of QMC combined with IS in BIPs. Furthermore, we explore the robustness of the IS-based randomly shifted rank-1 lattice rule by determining the quadrature error rate with respect to the noise level. The effects of using Gaussian distributions and $t$-distributions as the proposal distributions on the error rate of QMC are comprehensively investigated. We find that the error rate may deteriorate at low intensity of noise when using improper proposals, such as the prior distribution. To reclaim the effectiveness of QMC, we propose a new IS method such that the lattice rule with $N$ quadrature points achieves an optimal error rate close to $O(N^{-1})$, which is insensitive to the noise level. Numerical experiments are conducted to support the theoretical results.

In statistical analysis, Monte Carlo (MC) stands as a classical numerical integration method. When encountering challenging sample problem, Markov chain Monte Carlo (MCMC) is a commonly employed method. However, the MCMC estimator is biased after a fixed number of iterations. Unbiased MCMC, an advancement achieved through coupling techniques, addresses this bias issue in MCMC. It allows us to run many short chains in parallel. Quasi-Monte Carlo (QMC), known for its high order of convergence, is an alternative of MC. By incorporating the idea of QMC into MCMC, Markov chain quasi-Monte Carlo (MCQMC) effectively reduces the variance of MCMC, especially in Gibbs samplers. This work presents a novel approach that integrates unbiased MCMC with MCQMC, called as an unbiased MCQMC method. This method renders unbiased estimators while improving the rate of convergence significantly. Numerical experiments demonstrate that unbiased MCQMC with a sample size of $N$ achieves convergence rates of approximately $O(N^{-1})$ in moderate dimensions for Gibbs sampling problems. In the setting of parallelization, unbiased MCQMC also performs better than unbiased MCMC, even running with short chains.

Sequential neural posterior estimation (SNPE) techniques have been recently proposed for dealing with simulation-based models with intractable likelihoods. They are devoted to learning the posterior from adaptively proposed simulations using neural network-based conditional density estimators. As a SNPE technique, the automatic posterior transformation (APT) method proposed by Greenberg et al. (2019) performs notably and scales to high dimensional data. However, the APT method bears the computation of an expectation of the logarithm of an intractable normalizing constant, i.e., a nested expectation. Although atomic APT was proposed to solve this by discretizing the normalizing constant, it remains challenging to analyze the convergence of learning. In this paper, we propose a nested APT method to estimate the involved nested expectation instead. This facilitates establishing the convergence analysis. Since the nested estimators for the loss function and its gradient are biased, we make use of unbiased multi-level Monte Carlo (MLMC) estimators for debiasing. To further reduce the excessive variance of the unbiased estimators, this paper also develops some truncated MLMC estimators by taking account of the trade-off between the bias and the average cost. Numerical experiments for approximating complex posteriors with multimodal in moderate dimensions are provided., Comment: 28 pages, 4 figures

Sequential neural posterior estimation (SNPE) techniques have been recently proposed for dealing with simulation-based models with intractable likelihoods. Unlike approximate Bayesian computation, SNPE techniques learn the posterior from sequential simulation using neural network-based conditional density estimators. This paper reclaims SNPE-B proposed by Lueckmann et al. (2017), which suffers from inefficiency and slow inference due to inefficient utilization of simulated data and high variance of parameter updates. To address these issues, we firstly introduce a concentrated loss function based on an adaptive calibration kernel that reweights the simulated data appropriately to improve the data efficiency. Moreover, we provide a theoretical analysis of the variance of associated Monte Carlo estimators. Based on this analysis, we then propose several variance reduction techniques to further accelerate the process of learning. Numerical experiments demonstrate that our method outperforms the original method together with other existing competitors on certain tasks., Comment: 29 pages, 7 figures

We consider the problem of estimating an expectation $ \mathbb{E}\left[ h(W)\right]$ by quasi-Monte Carlo (QMC) methods, where $ h $ is an unbounded smooth function on $ \mathbb{R}^d $ and $ W$ is a standard normal distributed random variable. To study rates of convergence for QMC on unbounded integrands, we use a smoothed projection operator to project the output of $W$ to a bounded region, which differs from the strategy of avoiding the singularities along the boundary of the unit cube $ [0,1]^d $ in 10.1137/S0036144504441573. The error is then bounded by the quadrature error of the transformed integrand and the projection error. If the function $h(\boldsymbol{x})$ and its mixed partial derivatives do not grow too fast as the Euclidean norm $|\boldsymbol{x}|$ goes to infinity, we obtain an error rate of $O(n^{-1+\epsilon})$ for QMC and randomized QMC (RQMC) with a sample size $n$ and an arbitrarily small $\epsilon>0$. However, the rate turns out to be $O(n^{-1+2M+\epsilon})$ if the functions grow exponentially with a rate of $O(\exp\{M|\boldsymbol{x}|^2\})$ for a constant $M\in(0,1/2)$. Superisingly, we find that using importance sampling with t distribution as the proposal can improve the root mean squared error of RQMC from $O(n^{-1+2M+\epsilon})$ to $O( n^{-3/2+\epsilon})$ for any $M\in(0,1/2)$.

Combining multiple sensors enables a robot to maximize its perceptual awareness of environments and enhance its robustness to external disturbance, crucial to robotic navigation. This paper proposes the FusionPortable benchmark, a complete multi-sensor dataset with a diverse set of sequences for mobile robots. This paper presents three contributions. We first advance a portable and versatile multi-sensor suite that offers rich sensory measurements: 10Hz LiDAR point clouds, 20Hz stereo frame images, high-rate and asynchronous events from stereo event cameras, 200Hz inertial readings from an IMU, and 10Hz GPS signal. Sensors are already temporally synchronized in hardware. This device is lightweight, self-contained, and has plug-and-play support for mobile robots. Second, we construct a dataset by collecting 17 sequences that cover a variety of environments on the campus by exploiting multiple robot platforms for data collection. Some sequences are challenging to existing SLAM algorithms. Third, we provide ground truth for the decouple localization and mapping performance evaluation. We additionally evaluate state-of-the-art SLAM approaches and identify their limitations. The dataset, consisting of raw sensor easurements, ground truth, calibration data, and evaluated algorithms, will be released: https://ram-lab.com/file/site/multi-sensor-dataset., Comment: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) 2022, 6 pages, 6 figures. URL: https://ram-lab.com/file/site/multi-sensor-dataset

Importance sampling (IS) is valuable in reducing the variance of Monte Carlo sampling for many areas, including finance, rare event simulation, and Bayesian inference. It is natural and obvious to combine quasi-Monte Carlo (QMC) methods with IS to achieve a faster rate of convergence. However, a naive replacement of Monte Carlo with QMC may not work well. This paper investigates the convergence rates of randomized QMC-based IS for estimating integrals with respect to a Gaussian measure, in which the IS measure is a Gaussian or $t$ distribution. We prove that if the target function satisfies the so-called boundary growth condition and the covariance matrix of the IS density has eigenvalues no smaller than 1, then randomized QMC with the Gaussian proposal has a root mean squared error of $O(N^{-1+\epsilon})$ for arbitrarily small $\epsilon>0$. Similar results of $t$ distribution as the proposal are also established. These sufficient conditions help to assess the effectiveness of IS in QMC. For some particular applications, we find that the Laplace IS, a very general approach to approximate the target function by a quadratic Taylor approximation around its mode, has eigenvalues smaller than 1, making the resulting integrand less favorable for QMC. From this point of view, when using Gaussian distributions as the IS proposal, a change of measure via Laplace IS may transform a favorable integrand into unfavorable one for QMC although the variance of Monte Carlo sampling is reduced. We also give some examples to verify our propositions and warn against naive replacement of MC with QMC under IS proposals. Numerical results suggest that using Laplace IS with $t$ distributions is more robust than that with Gaussian distributions.

This paper focuses on variational inference with intractable likelihood functions that can be unbiasedly estimated. A flexible variational approximation based on Gaussian mixtures is developed, by adopting the mixture population Monte Carlo (MPMC) algorithm in \cite{cappe2008adaptive}. MPMC updates iteratively the parameters of mixture distributions with importance sampling computations, instead of the complicated gradient estimation of the optimization objective in usual variational Bayes. Noticing that MPMC uses a fixed number of mixture components, which is difficult to predict for real applications, we further propose an automatic component--updating procedure to derive an appropriate number of components. The derived adaptive MPMC algorithm is capable of finding good approximations of the multi-modal posterior distributions even with a standard Gaussian as the initial distribution, as demonstrated in our numerical experiments., Comment: 23 pages, 7 figures

Variational Bayes (VB) is a popular tool for Bayesian inference in statistical modeling. Recently, some VB algorithms are proposed to handle intractable likelihoods with applications such as approximate Bayesian computation. In this paper, we propose several unbiased estimators based on multilevel Monte Carlo (MLMC) for the gradient of Kullback-Leibler divergence between the posterior distribution and the variational distribution when the likelihood is intractable, but can be estimated unbiasedly. The new VB algorithm differs from the VB algorithms in the literature which usually render biased gradient estimators. Moreover, we incorporate randomized quasi-Monte Carlo (RQMC) sampling within the MLMC-based gradient estimators, which was known to provide a favorable rate of convergence in numerical integration. Theoretical guarantees for RQMC are provided in this new setting. Numerical experiments show that using RQMC in MLMC greatly speeds up the VB algorithm, and finds a better parameter value than some existing competitors do.

This paper investigates two typical image-type representations for event camera-based tracking: time surface (TS) and event map (EM). Based on the original TS-based tracker, we make use of these two representations' complementary strengths to develop an enhanced version. The proposed tracker consists of a general strategy to evaluate the optimization problem's degeneracy online and then switch proper representations. Both TS and EM are motion- and scene-dependent, and thus it is important to figure out their limitations in tracking. We develop six tracker variations and conduct a thorough comparison of them on sequences covering various scenarios and motion complexities. We release our implementations and detailed results to benefit the research community on event cameras: https: //github.com/gogojjh/ESVO_extension., Comment: 9 pages, 7 figures, accepted by CVPR Workshop 2021

We consider the problem of estimating the probability of a large loss from a financial portfolio, where the future loss is expressed as a conditional expectation. Since the conditional expectation is intractable in most cases, one may resort to nested simulation. To reduce the complexity of nested simulation, we present a method that combines multilevel Monte Carlo (MLMC) and quasi-Monte Carlo (QMC). In the outer simulation, we use Monte Carlo to generate financial scenarios. In the inner simulation, we use QMC to estimate the portfolio loss in each scenario. We prove that using QMC can accelerate the convergence rates in both the crude nested simulation and the multilevel nested simulation. Under certain conditions, the complexity of MLMC can be reduced to $O(\epsilon^{-2}(\log \epsilon)^2)$ by incorporating QMC. On the other hand, we find that MLMC encounters catastrophic coupling problem due to the existence of indicator functions. To remedy this, we propose a smoothed MLMC method which uses logistic sigmoid functions to approximate indicator functions. Numerical results show that the optimal complexity $O(\epsilon^{-2})$ is almost attained when using QMC methods in both MLMC and smoothed MLMC, even in moderate high dimensions.

Conditional value at risk (CVaR) is a popular measure for quantifying portfolio risk. Sensitivity analysis of CVaR is very useful in risk management and gradient-based optimization algorithms. In this paper, we study the infinitesimal perturbation analysis estimator for CVaR sensitivity using randomized quasi-Monte Carlo (RQMC) simulation. We first prove that the RQMC-based estimator is strongly consistent under very mild conditions. Under some technical conditions, RQMC that uses $d$-dimensional points in CVaR sensitivity estimation yields a mean error rate of $O(n^{-1/2-1/(4d-2)+\epsilon})$ for arbitrarily small $\epsilon>0$. The numerical results show that the RQMC method performs better than the Monte Carlo method for all cases. The gain of plain RQMC deteriorates as the dimension $d$ increases, as predicted by the established theoretical error rate.

Quasi-Monte Carlo (QMC) method is a useful numerical tool for pricing and hedging of complex financial derivatives. These problems are usually of high dimensionality and discontinuities. The two factors may significantly deteriorate the performance of the QMC method. This paper develops an integrated method that overcomes the challenges of the high dimensionality and discontinuities concurrently. For this purpose, a smoothing method is proposed to remove the discontinuities for some typical functions arising from financial engineering. To make the smoothing method applicable for more general functions, a new path generation method is designed for simulating the paths of the underlying assets such that the resulting function has the required form. The new path generation method has an additional power to reduce the effective dimension of the target function. Our proposed method caters for a large variety of model specifications, including the Black-Scholes, exponential normal inverse Gaussian L\'evy, and Heston models. Numerical experiments dealing with these models show that in the QMC setting the proposed smoothing method in combination with the new path generation method can lead to a dramatic variance reduction for pricing exotic options with discontinuous payoffs and for calculating options' Greeks. The investigation on the effective dimension and the related characteristics explains the significant enhancement of the combined procedure.

This paper studies the rate of convergence for conditional quasi-Monte Carlo (QMC), which is a counterpart of conditional Monte Carlo. We focus on discontinuous integrands defined on the whole of $R^d$, which can be unbounded. Under suitable conditions, we show that conditional QMC not only has the smoothing effect (up to infinitely times differentiable), but also can bring orders of magnitude reduction in integration error compared to plain QMC. Particularly, for some typical problems in options pricing and Greeks estimation, conditional randomized QMC that uses $n$ samples yields a mean error of $O(n^{-1+\epsilon})$ for arbitrarily small $\epsilon>0$. As a by-product, we find that this rate also applies to randomized QMC integration with all terms of the ANOVA decomposition of the discontinuous integrand, except the one of highest order.

Quantiles and expected shortfalls are usually used to measure risks of stochastic systems, which are often estimated by Monte Carlo methods. This paper focuses on the use of quasi-Monte Carlo (QMC) method, whose convergence rate is asymptotically better than Monte Carlo in the numerical integration. We first prove the convergence of QMC-based quantile estimates under very mild conditions, and then establish a deterministic error bound of $O(N^{-1/d})$ for the quantile estimates, where $d$ is the dimension of the QMC point sets used in the simulation and $N$ is the sample size. Under certain conditions, we show that the mean squared error (MSE) of the randomized QMC estimate for expected shortfall is $o(N^{-1})$. Moreover, under stronger conditions the MSE can be improved to $O(N^{-1-1/(2d-1)+\epsilon})$ for arbitrarily small $\epsilon>0$.

Recently, He and Owen (2016) proposed the use of Hilbert's space filling curve (HSFC) in numerical integration as a way of reducing the dimension from $d>1$ to $d=1$. This paper studies the asymptotic normality of the HSFC-based estimate when using scrambled van der Corput sequence as input. We show that the estimate has an asymptotic normal distribution for functions in $C^1([0,1]^d)$, excluding the trivial case of constant functions. The asymptotic normality also holds for discontinuous functions under mild conditions. It was previously known only that scrambled $(0,m,d)$-net quadratures enjoy the asymptotic normality for smooth enough functions, whose mixed partial gradients satisfy a H\"older condition. As a by-product, we find lower bounds for the variance of the HSFC-based estimate. Particularly, for nontrivial functions in $C^1([0,1]^d)$, the low bound is of order $n^{-1-2/d}$, which matches the rate of the upper bound established in He and Owen (2016).

This paper studies randomized quasi-Monte Carlo (QMC) sampling for discontinuous integrands having singularities along the boundary of the unit cube $[0,1]^d$. Both discontinuities and singularities are extremely common in the pricing and hedging of financial derivatives and have a tremendous impact on the accuracy of QMC. It was previously known that the root mean square error of randomized QMC is only $o(n^{-1/2})$ for discontinuous functions with singularities. We find that under some mild conditions, randomized QMC yields an expected error of $O(n^{-1/2-1/(4d-2)+\epsilon})$ for arbitrarily small $\epsilon>0$. Moreover, one can get a better rate if the boundary of discontinuities is parallel to some coordinate axes. As a by-product, we find that the expected error rate attains $O(n^{-1+\epsilon})$ if the discontinuities are QMC-friendly, in the sense that all the discontinuity boundaries are parallel to coordinate axes. The results can be used to assess the QMC accuracy for some typical problems from financial engineering.

We study the properties of points in $[0,1]^d$ generated by applying Hilbert's space-filling curve to uniformly distributed points in $[0,1]$. For deterministic sampling we obtain a discrepancy of $O(n^{-1/d})$ for $d\ge2$. For random stratified sampling, and scrambled van der Corput points, we get a mean squared error of $O(n^{-1-2/d})$ for integration of Lipshitz continuous integrands, when $d\ge3$. These rates are the same as one gets by sampling on $d$ dimensional grids and they show a deterioration with increasing $d$. The rate for Lipshitz functions is however best possible at that level of smoothness and is better than plain IID sampling. Unlike grids, space-filling curve sampling provides points at any desired sample size, and the van der Corput version is extensible in $n$. Additionally we show that certain discontinuous functions with infinite variation in the sense of Hardy and Krause can be integrated with a mean squared error of $O(n^{-1-1/d})$. It was previously known only that the rate was $o(n^{-1})$. Other space-filling curves, such as those due to Sierpinski and Peano, also attain these rates, while upper bounds for the Lebesgue curve are somewhat worse, as if the dimension were $\log_2(3)$ times as high., Comment: 22 pages, 6 figures