skip to main content

Explore Research Products in the NSF-PAR

Title: Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast
The Gibbs Sampler is a general method for sampling high-dimensional distributions, dating back to 1971. In each step of the Gibbs Sampler, we pick a random coordinate and re-sample that coordinate from the distribution induced by fixing all the other coordinates. While it has become widely used over the past half-century, guarantees of efficient convergence have been elusive. We show that for a convex body K in ℝⁿ with diameter D, the mixing time of the Coordinate Hit-and-Run (CHAR) algorithm on K is polynomial in n and D. We also give a lower bound on the mixing rate of CHAR, showing that it is strictly worse than hit-and-run and the ball walk in the worst case.  more » « less
Award ID(s):
2007443 1839323
NSF-PAR ID:
10282914
Author(s) / Creator(s):
;
Editor(s):
Buchin, Kevin; Colin de Verdi\` 
Date Published:
Journal Name:
ACM Symposium on Computational Geometry
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , 27th International Conference on Principles of Distributed Systems (OPODIS 2023))
    Bessani, Alysson ; Défago, Xavier ; Nakamura, Junya ; Wada, Koichi ; Yamauchi, Yukiko (Ed.)
    Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph G of maximum degree Δ and an integer k ≥ Δ+1, the goal is to generate a random proper vertex k-coloring of G. Jerrum (1995) proved that the Glauber dynamics has O(nlog{n}) mixing time when k > 2Δ. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in O(log{n}) rounds for k > (2+ε)Δ for any ε > 0. We improve this result to k > (11/6-δ)Δ for a fixed δ > 0. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step. 
    more » « less
  2. ; ; ( , Journal of Applied Probability)
    Abstract We study an example of a hit-and-run random walk on the symmetric group $\mathbf S_n$ . Our starting point is the well-understood top-to-random shuffle. In the hit-and-run version, at each single step , after picking the point of insertion j uniformly at random in $\{1,\ldots,n\}$ , the top card is inserted in the j th position k times in a row, where k is uniform in $\{0,1,\ldots,j-1\}$ . The question is, does this accelerate mixing significantly or not? We show that, in $L^2$ and sup-norm, this accelerates mixing at most by a constant factor (independent of n ). Analyzing this problem in total variation is an interesting open question. We show that, in general, hit-and-run random walks on finite groups have non-negative spectrum. 
    more » « less
  3. ; ; ( , Journal of Survey Statistics and Methodology)
    Abstract

    Entity resolution (record linkage or deduplication) is the process of identifying and linking duplicate records in databases. In this paper, we propose a Bayesian graphical approach for entity resolution that links records to latent entities, where the prior representation on the linkage structure is exchangeable. First, we adopt a flexible and tractable set of priors for the linkage structure, which corresponds to a special class of random partition models. Second, we propose a more realistic distortion model for categorical/discrete record attributes, which corrects a logical inconsistency with the standard hit-miss model. Third, we incorporate hyperpriors to improve flexibility. Fourth, we employ a partially collapsed Gibbs sampler for inferential speedups. Using a selection of private and nonprivate data sets, we investigate the impact of our modeling contributions and compare our model with two alternative Bayesian models. In addition, we conduct a simulation study for household survey data, where we vary distortion, duplication rates and data set size. We find that our model performs more consistently than the alternatives across a variety of scenarios and typically achieves the highest entity resolution accuracy (F1 score). Open source software is available for our proposed methodology, and we provide a discussion regarding our work and future directions.

     
    more » « less
  4. ; ( , Evolutionary Applications)
    Abstract

    Natural selection is inherently a multivariate phenomenon. The selection pressure on size (natural and artificial) and the age at which selection occurs is likely to induce evolutionary changes in growth rates across the entire life history. However, the covariance structure that will determine the path of evolution for size at age has been studied in only a few fish species. We therefore estimated the genetic covariance function for size throughout ontogeny using Atlantic silversides (Menidia menidia) as the model system. Over a 3‐year period, a total of 542 families were used to estimate the genetic covariance in length at age from hatch through maturity. The function‐valued trait approach was employed to estimate the genetic covariance functions. A Bayesian hierarchical model was used to account for the unbalanced design, unequal measurement intervals, unequal sample sizes, and family‐aggregated data. To improve mixing, we developed a two‐stage sampler using a Gibbs sampler to generate the posterior of a well‐mixing approximate model followed by an importance sampler to draw samples from posterior of the completely specified model. We found that heritability of length is age‐specific and there are strong genetic correlations in length across ages that last 30 days or more. We used these estimates in a hypothetical model predicting the evolutionary response to harvesting following a single generation of selection under both sigmoidal and unimodal patterns of gear selectivity to illustrate the potential outcomes of ignoring the genetic correlations. In these scenarios, genetic correlations were found to have a strong effect on both the direction and magnitude of the response to harvest selection.

     
    more » « less
  5. ; ( , Journal of the Royal Statistical Society Series B: Statistical Methodology)
    Abstract

    We propose a very fast approximate Markov chain Monte Carlo sampling framework that is applicable to a large class of sparse Bayesian inference problems. The computational cost per iteration in several regression models is of order O(n(s+J)), where n is the sample size, s is the underlying sparsity of the model, and J is the size of a randomly selected subset of regressors. This cost can be further reduced by data sub-sampling when stochastic gradient Langevin dynamics are employed. The algorithm is an extension of the asynchronous Gibbs sampler of Johnson et al. [(2013). Analyzing Hogwild parallel Gaussian Gibbs sampling. In Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13) (Vol. 2, pp. 2715–2723)], but can be viewed from a statistical perspective as a form of Bayesian iterated sure independent screening [Fan, J., Samworth, R., & Wu, Y. (2009). Ultrahigh dimensional feature selection: Beyond the linear model. Journal of Machine Learning Research, 10, 2013–2038]. We show that in high-dimensional linear regression problems, the Markov chain generated by the proposed algorithm admits an invariant distribution that recovers correctly the main signal with high probability under some statistical assumptions. Furthermore, we show that its mixing time is at most linear in the number of regressors. We illustrate the algorithm with several models.

     
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email