In this paper we propose a dimension-reduction strategy in order to improve the performance of importance sampling in high dimension. The idea is to estimate variance terms in a small number of suitably chosen directions. We first prove that the optimal directions, i.e., the ones that minimize the Kullback--Leibler divergence with the optimal auxiliary density, are the eigenvectors associated to extreme (small or large) eigenvalues of the optimal covariance matrix. We then perform extensive numerical experiments that show that as dimension increases, these directions give estimations which are very close to optimal. Moreover, we show that the estimation remains accurate even when a simple empirical estimator of the covariance matrix is used to estimate these directions. These theoretical and numerical results open the way for different generalizations, in particular the incorporation of such ideas in adaptive importance sampling schemes.
相關內容
The Bouncy Particle sampler (BPS) and the Zig-Zag sampler (ZZS) are continuous time, non-reversible Monte Carlo methods based on piecewise deterministic Markov processes. Experiments show that the speed of convergence of these samplers can be affected by the shape of the target distribution, as for instance in the case of anisotropic targets. We propose an adaptive scheme that iteratively learns all or part of the covariance matrix of the target and takes advantage of the obtained information to modify the underlying process with the aim of increasing the speed of convergence. Moreover, we define an adaptive scheme that automatically tunes the refreshment rate of the BPS or ZZS. We prove ergodicity and a law of large numbers for all the proposed adaptive algorithms. Finally, we show the benefits of the adaptive samplers with several numerical simulations.
We consider the estimation of densities in multiple subpopulations, where the available sample size in each subpopulation greatly varies. This problem occurs in epidemiology, for example, where different diseases may share similar pathogenic mechanism but differ in their prevalence. Without specifying a parametric form, our proposed method pools information from the population and estimate the density in each subpopulation in a data-driven fashion. Drawing from functional data analysis, low-dimensional approximating density families in the form of exponential families are constructed from the principal modes of variation in the log-densities. Subpopulation densities are subsequently fitted in the approximating families based on likelihood principles and shrinkage. The approximating families increase in their flexibility as the number of components increases and can approximate arbitrary infinite-dimensional densities. We also derive convergence results of the density estimates with discrete observations. The proposed methods are shown to be interpretable and efficient in simulation as well as applications to electronic medical record and rainfall data.
Given a function $u\in L^2=L^2(D,\mu)$, where $D\subset \mathbb R^d$ and $\mu$ is a measure on $D$, and a linear subspace $V_n\subset L^2$ of dimension $n$, we show that near-best approximation of $u$ in $V_n$ can be computed from a near-optimal budget of $Cn$ pointwise evaluations of $u$, with $C>1$ a universal constant. The sampling points are drawn according to some random distribution, the approximation is computed by a weighted least-squares method, and the error is assessed in expected $L^2$ norm. This result improves on the results in [6,8] which require a sampling budget that is sub-optimal by a logarithmic factor, thanks to a sparsification strategy introduced in [17,18]. As a consequence, we obtain for any compact class $\mathcal K\subset L^2$ that the sampling number $\rho_{Cn}^{\rm rand}(\mathcal K)_{L^2}$ in the randomized setting is dominated by the Kolmogorov $n$-width $d_n(\mathcal K)_{L^2}$. While our result shows the existence of a randomized sampling with such near-optimal properties, we discuss remaining issues concerning its generation by a computationally efficient algorithm.
Chance constrained optimization problems allow to model problems where constraints involving stochastic components should only be violated with a small probability. Evolutionary algorithms have recently been applied to this scenario and shown to achieve high quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance constrained optimization. We study the scenario of stochastic components that are independent and Normally distributed. By generalizing results for the class of linear functions to the sum of transformed linear functions, we show that the (1+1)~EA can optimize the chance constrained setting without additional constraints in time O(n log n). However, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time for the (1+1)~EA. We therefore propose a multi-objective formulation of the problem which trades off the expected cost and its variance. We show that multi-objective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we show that this approach can also be used to compute a set of optimal solutions for the chance constrained minimum spanning tree problem.
Matching methods are widely used for causal inference in observational studies. Among them, nearest neighbor matching is arguably the most popular. However, nearest neighbor matching does not generally yield an average treatment effect estimator that is $\sqrt{n}$-consistent (Abadie and Imbens, 2006). Are matching methods not $\sqrt{n}$-consistent in general? In this paper, we study a recent class of matching methods that use integer programming to directly target aggregate covariate balance as opposed to finding close neighbor matches. We show that under suitable conditions these methods can yield simple estimators that are $\sqrt{n}$-consistent and asymptotically optimal.
Stochastic optimal principle leads to the resolution of a partial differential equation (PDE), namely the Hamilton-Jacobi-Bellman (HJB) equation. In general, this equation cannot be solved analytically, thus numerical algorithms are the only tools to provide accurate approximations. The aims of this paper is to introduce a novel fitted finite volume method to solve high dimensional degenerated HJB equation from stochastic optimal control problems in high dimension ($ n\geq 3$). The challenge here is due to the nature of our HJB equation which is a degenerated second-order partial differential equation coupled with an optimization problem. For such problems, standard scheme such as finite difference method losses its monotonicity and therefore the convergence toward the viscosity solution may not be guarantee. We discretize the HJB equation using the fitted finite volume method, well known to tackle degenerated PDEs, while the time discretisation is performed using the Implicit Euler scheme. We show that matrices resulting from spatial discretization and temporal discretization are M--matrices. Numerical results in finance demonstrating the accuracy of the proposed numerical method comparing to the standard finite difference method are provided.
In this paper, we propose an infinite-dimensional version of the Stein variational gradient descent (iSVGD) method for solving Bayesian inverse problems. The method can generate approximate samples from posteriors efficiently. Based on the concepts of operator-valued kernels and function-valued reproducing kernel Hilbert spaces, a rigorous definition is given for the infinite-dimensional objects, e.g., the Stein operator, which are proved to be the limit of finite-dimensional ones. Moreover, a more efficient iSVGD with preconditioning operators is constructed by generalizing the change of variables formula and introducing a regularity parameter. The proposed algorithms are applied to an inverse problem of the steady state Darcy flow equation. Numerical results confirm our theoretical findings and demonstrate the potential applications of the proposed approach in the posterior sampling of large-scale nonlinear statistical inverse problems.
In this paper, we use an implicit two-derivative deferred correction time discretization approach and combine it with a spatial discretization of the discontinuous Galerkin spectral element method to solve (non-)linear PDEs. The resulting numerical method is high order accurate in space and time. As the novel scheme handles two time derivatives, the spatial operator for both derivatives has to be defined. This results in an extended system matrix of the scheme. We analyze this matrix regarding possible simplifications and an efficient way to solve the arising (non-)linear system of equations. It is shown how a carefully designed preconditioner and a matrix-free approach allow for an efficient implementation and application of the novel scheme. For both, linear advection and the compressible Euler equations, up to eighth order of accuracy in time is shown. Finally, it is illustrated how the method can be used to approximate solutions to the compressible Navier-Stokes equations.
Many complicated Bayesian posteriors are difficult to approximate by either sampling or optimisation methods. Therefore we propose a novel approach combining features of both. We use a flexible parameterised family of densities, such as a normalising flow. Given a density from this family approximating the posterior, we use importance sampling to produce a weighted sample from a more accurate posterior approximation. This sample is then used in optimisation to update the parameters of the approximate density, which we view as distilling the importance sampling results. We iterate these steps and gradually improve the quality of the posterior approximation. We illustrate our method in two challenging examples: a queueing model and a stochastic differential equation model.
Stochastic gradient Markov chain Monte Carlo (SGMCMC) has become a popular method for scalable Bayesian inference. These methods are based on sampling a discrete-time approximation to a continuous time process, such as the Langevin diffusion. When applied to distributions defined on a constrained space, such as the simplex, the time-discretisation error can dominate when we are near the boundary of the space. We demonstrate that while current SGMCMC methods for the simplex perform well in certain cases, they struggle with sparse simplex spaces; when many of the components are close to zero. However, most popular large-scale applications of Bayesian inference on simplex spaces, such as network or topic models, are sparse. We argue that this poor performance is due to the biases of SGMCMC caused by the discretization error. To get around this, we propose the stochastic CIR process, which removes all discretization error and we prove that samples from the stochastic CIR process are asymptotically unbiased. Use of the stochastic CIR process within a SGMCMC algorithm is shown to give substantially better performance for a topic model and a Dirichlet process mixture model than existing SGMCMC approaches.
小貼士
登錄享
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191