Browsing by Subject "Markov chain Monte Carlo"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Geometric ergodicity of a random-walk metorpolis algorithm via variable transformation and computer aided reasoning in statistics.
    (2011-06) Johnson, Leif Thomas
    With the steady increase of affordable computing, more and more often analysts are turning to computationally intensive techniques like Markov chain Monte Carlo (MCMC). To properly quantify the quality of their MCMC estimates, analysts need to know how quickly the Markov chain converges. Geometric ergodicity is a very useful benchmark for how quickly a Markov chain converges. If a Markov chain is geometrically ergodic, there are easy to use consistent estimators of the Monte Carlo standard errors (MCSEs) for the MCMC estimates, and an easy to use Central Limit Theorem for the MCMC estimates. We provide a method for finding geometrically ergodic Markov chains for classes of target densities. This method uses variable transformation to induce a proxy target distribution, and a random-walk Metropolis algorithm for the proxy target distribution will be geometrically ergodic. Because the transformations we use are one-to-one, Markov chains generated for the proxy target density can be transformed back to a sample from the original target density without loss of inference. Furthermore, because the Markov chain for the proxy distribution is geometrically ergodic, the consistent MCSEs and the CLT apply to the sample on the scale of original target density. We provide example applications of this technique to multinomial logit regression and a multivariate T distribution. Computer Aided Reasoning (CAR) uses a computer program to assist with mathematical reasoning. Proofs done in a proof assistant program are done formally, every step and inference is validated back to the axioms and rules of inference. Thus we have higher confidence in the correctness of a formally verified proof than one done with the traditional paper-and-pencil technique. Computers can track many more details than can be done by hand, so more complicated proofs with more cases and details can be done in CAR than can be done by hand, and proof assistant programs can help fill in the gaps in a proof. We give a brief overview of the proof assistant program HOL Light, and use it to formally prove the Markov inequality with an expectation based approach.
  • Thumbnail Image
    Item
    Geometric ergodicity of a random-walk Metropolis algorithm for a transformed density
    (2010-11-22) Johnson, Leif; Geyer, Charles J.
    Curvature conditions on a target density in R^k for the geometric ergodicity of a random-walk Metropolis algorithm have previously been established (Mengersen and Tweedie(1996), Roberts and Tweedie(1996), Jarner and Hansen(2000)). However, the conditions for target densities in R^k that have exponentially light tails, but are not super-exponential are difficult to apply. In this paper I establish a variable transformation to apply to such target densities, that along with a regularity condition on the target density, ensures that a random-walk Metropolis algorithm for the transformed density is geometrically ergodic. Inference can be drawn for the original target density using Markov chain Monte Carlo estimates based on the transformed density. An application to inference on the regression parameter in multinomial logit regression with a conjugate prior is given.
  • Thumbnail Image
    Item
    Geometric ergodicity of Gibbs samplers.
    (2009-07) Johnson, Alicia A.
    Due to a demand for reliable methods for exploring intractable probability distributions, the popularity of Markov chain Monte Carlo (MCMC) techniques continues to grow. In any MCMC analysis, the convergence rate of the associated Markov chain is of practical and theoretical importance. A geometrically ergodic chain converges to its target distribution at a geometric rate. In this dissertation, we establish verifiable conditions under which geometric ergodicity is guaranteed for Gibbs samplers in a general model setting. Further, we show that geometric ergodicity of the deterministic scan Gibbs sampler ensures geometric ergodicity of the Gibbs sampler under alternative scanning strategies. As an illustration, we consider Gibbs sampling for a popular Bayesian version of the general linear mixed model. In addition to ensuring the rapid convergence required for useful simulation, geometric ergodicity is a key sufficient condition for the existence of central limit theorems and consistent estimators of Monte Carlo standard errors. Thus our results allow practitioners to be as confident in inference drawn from Gibbs samplers as they would be in inference drawn from random samples from the target distribution.
  • Thumbnail Image
    Item
    Output Analysis for Markov Chain Monte Carlo
    (2017-02) Vats, Dootika
    Markov chain Monte Carlo (MCMC) is a sampling method used to estimate expectations with respect to a target distribution. An important question is when should sampling stop so that we have good estimates of these expectations? The key to answering this question lies in assessing the Monte Carlo error through a multivariate Markov chain central limit theorem (CLT). The multivariate nature of this Monte Carlo error largely has been ignored in the MCMC literature. This dissertation discusses the drawbacks of the current univariate methods of terminating simulation and introduces a multivariate framework for terminating simulation. Theoretical properties of the procedures are established. A multivariate effective sample size is defined and estimated using strongly consistent estimators of the covariance matrix in the Markov chain CLT, a property that is shown for the multivariate batch means estimator and the multivariate spectral variance estimator. A critical aspect of this procedure is that a lower bound on the number of effective samples required for a pre-specified level of precision can be determined a priori. This lower bound depends on the problem only in the dimension of the expectation being estimated, and not on the underlying stochastic process. This result is obtained by drawing a connection between terminating the simulation via effective sample size and terminating it using a relative standard deviation fixed-volume sequential stopping rule. The finite sample properties of the proposed methods are demonstrated in a variety of examples. The proposed method requires the existence of a Markov chain CLT, establishing which requires bounding the rate of convergence of the Markov chains. We establish a geometric rate of convergence for a class of Bayesian penalized regression models. We also present examples showing how it may be easier to establish rates of convergence for linchpin variable samplers than for its competitors.
  • Thumbnail Image
    Item
    Parameter estimation in social network models.
    (2011-05) Okabayashi, Saisuke
    A social network is an example of a phenomenon with complex stochastic dependence that is commonly modeled with a class of exponential families called exponential random graph models (ERGM). Maximum likelihood estimators (MLE) for such exponential families can be difficult to estimate when the likelihood is difficult to compute. Most methodologies rely on iterated estimates and are sensitive to the starting value, failing to converge if started too far from the solution. Even more problematic is that the MLE may not exist, a situation that occurs with positive probability for ERGMs. In such a case, the MLE is actually "at infinity" in some direction of the parameter space. Here we present a simple line search algorithm to find the MLE of a regular exponential family when the MLE exists and is unique. The algorithm can be started from any initial value and avoids trial-and-error experimentation. When the MLE does not exist, our algorithm adapts Geyer's (2009a) approach to detect non-existent MLEs and construct one-sided confidence intervals for how close the parameter is to infinity.
  • Thumbnail Image
    Item
    Some Convergence Results for Metropolis-Hastings Algorithms
    (2022-08) Brown, Austin
    This thesis is concerned with the computational effort required by a Metropolis-Hastings algorithm to converge to the target distribution in total variation and Wasserstein distances. First, under mild assumptions, we show the sharp convergence rate in total variation is also sharp in weaker Wasserstein distances for the Metropolis-Hastings independence sampler. We derive exact convergence expressions for general Wasserstein distances when initialization is at a specific point. Using optimization, we construct a novel centered independent proposal to develop exact convergence rates in Bayesian quantile regression and many generalized linear model settings. We show the exact convergence rate can be upper bounded in Bayesian binary response regression (e.g. logistic and probit) when the sample size and dimension grow together. Next, practitioners are often left tuning Metropolis-Hastings algorithms by trial and error or using optimal scaling guidelines to avoid poor empirical performance. We develop general lower bounds on the convergence rates of geometrically ergodic Metropolis-Hastings algorithms to study their computational complexity. If the target density concentrates with a parameter n (e.g. Bayesian posterior concentration, Laplace approximations), we show the convergence rate can tend to 1 exponentially fast if the tuning parameters do not depend carefully on the dimension and the parameter n.
  • Thumbnail Image
    Item
    Supporting Theory and Data Analysis for "Long Range Search for Maximum Likelihood in Exponential Families"
    (2011-07-23) Okabayashi, Saisuke; Geyer, Charles J.
    Exponential families are often used to model data sets with complex dependence. Maximum likelihood estimators (MLE) can be difficult to estimate when the likelihood is expensive to compute. Markov chain Monte Carlo (MCMC) methods based on the MCMC-MLE algorithm in Geyer and Thompson (1992) are guaranteed to converge in theory under certain conditions when starting from any value, but in practice such an algorithm may labor to converge when given a poor starting value. We present a simple line search algorithm to find the MLE of a regular exponential family when the MLE exists and is unique. The algorithm can be started from any initial value and avoids the trial and error experimentation associated with calibrating algorithms like stochastic approximation. Unlike many optimization algorithms, this approach utilizes first derivative information only, evaluating neither the likelihood function itself nor derivatives of higher order than first. We show convergence of the algorithm for the case where the gradient can be calculated exactly. When it cannot, it has a particularly convenient form that is easily estimable with MCMC, making the algorithm still useful to a practitioner.