Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Liu, Kuikui"'
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can
Externí odkaz:
http://arxiv.org/abs/2405.20849
Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random intera
Externí odkaz:
http://arxiv.org/abs/2405.06616
We optimize pipeline parallelism for deep neural network (DNN) inference by partitioning model graphs into $k$ stages and minimizing the running time of the bottleneck stage, including communication. We give practical and effective algorithms for thi
Externí odkaz:
http://arxiv.org/abs/2311.03703
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribut
Externí odkaz:
http://arxiv.org/abs/2304.01954
We show that the natural Glauber dynamics mixes rapidly and generates a random proper edge-coloring of a graph with maximum degree $\Delta$ whenever the number of colors is at least $q\geq (\frac{10}{3} + \epsilon)\Delta$, where $\epsilon>0$ is arbit
Externí odkaz:
http://arxiv.org/abs/2106.03845
Publikováno v:
TheoretiCS, Volume 3 (July 12, 2024) theoretics:10055
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then spe
Externí odkaz:
http://arxiv.org/abs/2106.03366
Autor:
Liu, Kuikui
We show that the existence of a "good"' coupling w.r.t. Hamming distance for any local Markov chain on a discrete product space implies rapid mixing of the Glauber dynamics in a blackbox fashion. More specifically, we only require the expected distan
Externí odkaz:
http://arxiv.org/abs/2103.11609
We prove an optimal mixing time bound on the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling in a variety of settings. Our work presents an improved version of the spectral independence approach of Anari et al. (2020)
Externí odkaz:
http://arxiv.org/abs/2011.02075
For general antiferromagnetic 2-spin systems, including the hardcore model and the antiferromagnetic Ising model, there is an $\mathsf{FPTAS}$ for the partition function on graphs of maximum degree $\Delta$ when the infinite regular tree lies in the
Externí odkaz:
http://arxiv.org/abs/2004.09083
We prove tight mixing time bounds for natural random walks on bases of matroids, determinantal distributions, and more generally distributions associated with log-concave polynomials. For a matroid of rank $k$ on a ground set of $n$ elements, or more
Externí odkaz:
http://arxiv.org/abs/2004.07220