Explore the vast range of titles available.

We examine the behaviour of the pseudo-marginal random walk Metropolis algorithm, where evaluations of the target density for the accept/reject probability are estimated rather than computed precisely. Under relatively general conditions on the target distribution, we obtain limiting formulae for the acceptance rate and for the expected squared jump distance, as the dimension of the target approaches infinity, under the assumption that the noise in the estimate of the log-target is additive and is independent of the position. For targets with independent and identically distributed components, we also obtain a limiting diffusion for the first component. We then consider the overall efficiency of the algorithm, in terms of both speed of mixing and computational time. Assuming the additive noise is Gaussian and is inversely proportional to the number of unbiased estimates that are used, we prove that the algorithm is optimally efficient when the variance of the noise is approximately 3.283 and the acceptance rate is approximately 7.001%. We also find that the optimal scaling is insensitive to the noise and that the optimal variance of the noise is insensitive to the scaling. The theory is illustrated with a simulation study using the particle marginal random walk Metropolis.

We study the problem of sampling high and infinite dimensional target measures arising in applications such as conditioned diffusions and inverse problems. We focus on those that arise from approximating measures on Hilbert spaces defined via a density with respect to a Gaussian reference measure. We consider the Metropolis–Hastings algorithm that adds an accept–reject mechanism to a Markov chain proposal in order to make the chain reversible with respect to the target measure. We focus on cases where the proposal is either a Gaussian random walk (RWM) with covariance equal to that of the reference measure or an Ornstein–Uhlenbeck proposal (pCN) for which the reference measure is invariant. Previous results in terms of scaling and diffusion limits suggested that the pCN has a convergence rate that is independent of the dimension while the RWM method has undesirable dimension-dependent behaviour. We confirm this claim by exhibiting a dimension-independent Wasserstein spectral gap for pCN algorithm for a large class of target measures. In our setting this Wasserstein spectral gap implies an L2-spectral gap. We use both spectral gaps to show that the ergodic average satisfies a strong law of large numbers, the central limit theorem and nonasymptotic bounds on the mean square error, all dimension independent. In contrast we show that the spectral gap of the RWM algorithm applied to the reference measures degenerates as the dimension tends to infinity.

We study convergence properties of pseudo-marginal Markov chain Monte Carlo algorithms (Andrieu and Roberts [Ann. Statist. 37 (2009) 697–725]). We find that the asymptotic variance of the pseudo-marginal algorithm is always at least as large as that of the marginal algorithm. We show that if the marginal chain admits a (right) spectral gap and the weights (normalised estimates of the target density) are uniformly bounded, then the pseudo-marginal chain has a spectral gap. In many cases, a similar result holds for the absolute spectral gap, which is equivalent to geometric ergodicity. We consider also unbounded weight distributions and recover polynomial convergence rates in more specific cases, when the marginal algorithm is uniformly ergodic or an independent Metropolis–Hastings or a random-walk Metropolis targeting a super-exponential density with regular contours. Our results on geometric and polynomial convergence rates imply central limit theorems. We also prove that under general conditions, the asymptotic variance of the pseudo-marginal algorithm converges to the asymptotic variance of the marginal algorithm if the accuracy of the estimators is increased.

Motivated by the PageRank model for graph partitioning, we develop an extension of PageRank for partitioning uniform hypergraphs. Starting from adjacency tensors of uniform hypergraphs, we establish the multi-linear pseudo-PageRank (MLPPR) model, which is formulated as a multi-linear system with nonnegative constraints. The coefficient tensor of MLPPR is a kind of Laplacian tensors of uniform hypergraphs, which are almost as sparse as adjacency tensors since no dangling corrections are incorporated. Furthermore, all frontal slices of the coefficient tensor of MLPPR are M-matrices. Theoretically, MLPPR has a solution, which is unique under mild conditions. An error bound of the MLPPR solution is analyzed when the Laplacian tensor is slightly perturbed. Computationally, by exploiting the structural Laplacian tensor, we propose a tensor splitting algorithm, which converges linearly to a solution of MLPPR. Finally, numerical experiments illustrate that MLPPR is effective and efficient for hypergraph partitioning problems.

The landscape of computational modeling in cancer systems biology is diverse, offering a spectrum of models and frameworks, each with its own trade-offs and advantages. Ideally, models are meant to be useful in refining hypotheses, to sharpen experimental procedures and, in the longer run, even for applications in personalized medicine. One of the greatest challenges is to balance model realism and detail with experimental data to eventually produce useful data-driven models. We contribute to this quest by developing a transparent, highly parsimonious, first principle in silico model of a growing avascular tumor. We initially formulate the physiological considerations and the specific model within a stochastic cell-based framework. We next formulate a corresponding mean-field model using partial differential equations which is amenable to mathematical analysis. Despite a few notable differences between the two models, we are in this way able to successfully detail the impact of all parameters in the stability of the growth process and on the eventual tumor fate of the stochastic model. This facilitates the deduction of Bayesian priors for a given situation, but also provides important insights into the underlying mechanism of tumor growth and progression. Although the resulting model framework is relatively simple and transparent, it can still reproduce the full range of known emergent behavior. We identify a novel model instability arising from nutrient starvation and we also discuss additional insight concerning possible model additions and the effects of those. Thanks to the framework’s flexibility, such additions can be readily included whenever the relevant data become available.

In this paper, we establish moment and Bernstein-type inequalities for additive functionals of geometrically ergodic Markov chains. These inequalities extend the corresponding inequalities for independent random variables. Our conditions cover Markov chains converging geometrically to the stationary distribution either in weighted total variation norm or in weighted Wasserstein distances. Our inequalities apply to unbounded functions and depend explicitly on constants appearing in the conditions that we consider.

We present a Markov chain, \"Dikin walk,\" for sampling from a convex body equipped with a self-concordant barrier. This Markov chain corresponds to a natural random walk with respect to a Riemannian metric defined using the Hessian of the barrier function. For every convex set of dimension n, there exists a self-concordant barrier whose self-concordance parameter is O(n). Consequently, a rapidly mixing Markov chain of the kind we describe can be defined (but not always be efficiently implemented) on any convex set. We use these results to design an algorithm consisting of a single random walk for optimizing a linear function on a convex set. Using results of Barthe [Geom. Fund. Anal. 12 (2002) 32-55] and Bobkov and Houdré [Ann. Probab. 25 (1997) 184-205], on the isoperimetry of products of weighted Riemannian manifolds, we obtain sharper upper bounds on the mixing time of a Dikin walk on products of convex sets than the bounds obtained from a direct application of the localization lemma. The results in this paper generalize previous results of Kannan and Narayanan [In STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing (2009) 561-570 ACM] from poly topes to spectrahedra and beyond, and improve upon those results in a special case when the convex set is a direct product of lower-dimensional convex sets. This Markov chain like the chain described in [In STOC'09—Proceedings of the 2009 ACM International Symposium on Theory of Computing (2009) 561-570 ACM] is affine-invariant.

Diffusion limits of MCMC methods in high dimensions provide a useful theoretical tool for studying computational complexity. In particular, they lead directly to precise estimates of the number of steps required to explore the target measure, in stationarity, as a function of the dimension of the state space. However, to date such results have mainly been proved for target measures with a product structure, severely limiting their applicability. The purpose of this paper is to study diffusion limits for a class of naturally occurring high-dimensional measures found from the approximation of measures on a Hubert space which are absolutely continuous with respect to a Gaussian reference measure. The diffusion limit of a random walk Metropolis algorithm to an infinite-dimensional Hubert space valued SDE (or SPDE) is proved, facilitating understanding of the computational complexity of the algorithm.

We introduce a new sampling algorithm, the equi-energy sampler, for efficient statistical sampling and estimation. Complementary to the widely used temperature-domain methods, the equi-energy sampler, utilizing the temperature–energy duality, targets the energy directly. The focus on the energy function not only facilitates efficient sampling, but also provides a powerful means for statistical estimation, for example, the calculation of the density of states and microcanonical averages in statistical mechanics. The equi-energy sampler is applied to a variety of problems, including exponential regression in statistics, motif sampling in computational biology and protein folding in biophysics.

Adaptive and interacting Markov chain Monte Carlo algorithms (MCMC) have been recently introduced in the literature. These novel simulation algorithms are designed to increase the simulation efficiency to sample complex distributions. Motivated by some recently introduced algorithms (such as the adaptive Metropolis algorithm and the interacting tempering algorithm), we develop a general methodological and theoretical framework to establish both the convergence of the marginal distribution and a strong law of large numbers. This framework weakens the conditions introduced in the pioneering paper by Roberts and Rosenthal [J. Appl Probab. 44 (2007) 458—475]. It also covers the case when the target distribution π is sampled by using Markov transition kernels with a stationary distribution that differs from π.