Local,Dynamic And Fast Algorithms For Sampling From Gibbs Distributions

The Gibbs distribution is an important probabilistic model,which is widely-used in Probability Theory,Statistical Physics and Computer Science.Sampling is a cen-ter computational task for Gibbs distributions,which asks the algorithm to generate random samples from the target distribution.Sampling from Gibbs distributions is an important research topic in Theoretical Computer Science.The research aims to give algorithms with provable guarantees and study its computational complexity.In recent decades,sampling techniques such as the rejection sampling and the Markov chain Monte Carlo method,were developed,and they solved many problems successfully.Although previous studies have answered several fundamental questions about sampling,currently,there are only few sampling algorithms,the analysis tools need to be strengthened,and and many important problems are not well addressed.For exam-ple,for the problem of sampling uniform Boolean formula solutions,it lacks efficient algorithms for a long time because many classic ones are not applicable;for the problem of sampling uniform proper graph colorings,the current best-known convergence con-dition is still far from the conjecture due to the lack of powerful analysis tools.These classic open problems actually represent the essential barriers to current technique,and solving them requires innovation at the principle level.On the other hand,many new sampling problems arise in the Big Data Era.Many classic sampling algorithms are highly sequential and only work for static data.But in today’s applications,parallel and dynamic sampling algorithms attract considerably more attentions.The classic sampling theory encounters challenges in these new problems.We need to develop new sampling theory in the Big Data Era.This thesis studies sampling algorithms for Gibbs distributions.For new problems in the Big Data Era,we focus on two specific ones:distributed sampling and dynamic sampling.We give algorithms with provable guarantees and also study their compu-tational complexity.For classic open problems,we give new algorithm design and analysis techniques to bypass old barriers,so that we can obtain faster algorithms.The first topic is the distributed sampling problem.We consider the problem of sampling from Gibbs distributions in the LOCAL model.In this model,each node col-lects the local information and computes a random output.All output values should jointly follow the law of the target Gibbs distribution.We give novel algorithms and prove lower bounds.We also find that many classic results still hold in the distributed computing model,for example,the computational equivalence between sampling and counting,and the computational phase transitions of the sampling problems.Previ-ously,these results were only established in the Turing machine model.The second topic is the dynamic sampling problem.Suppose we have a Gibbs dis-tribution and a random sample that follows it.Given an update that modifies the current distribution into a new distribution,the algorithm needs to maintain the random sample with a small incremental cost.Specifically,the algorithm modifies the random sample to make it follow the new distribution.We give two techniques for dynamic sampling.The first one is the conditional Gibbs technique.It not only solves dynamic sampling problems,but also designs perfect sampling algorithms and has a close relation with the spatial mixing property of Gibbs distributions.The second one is the dynamic Markov chain technique.It can dynamize some Markov chain Monte Carlo methods,so that some classic static sampling results can be directly used in dynamic sampling.The last topic is fast sampling algorithms.Before our work,some Gibbs distribu-tions only have sampling algorithms with n~f(~θ)running time,where n is the number of variables;θis some parameter such as the maximum degree of the variable;and f(θ)is a polynomial or exponential function inθ.These algorithms requireθ=O(1),and the running time is a huge polynomial.Our work improves the running time to poly(nθ),for some problems,the dependency to n is close to linear.Technique-wise,we give new algorithm design and analysis techniques so that we can obtain faster algorithms.