Generating from Discrete Distributions Using Diffusions: Insights from Random Constraint Satisfaction Problems
Generating data from discrete distributions is important for a number of application domains including text, tabular data, and genomic data. Several groups have recently used random $k$-satisfiability ($k$-SAT) as a synthetic benchmark for new generative techniques. In this paper, we show that fundamental insights from the theory of random constraint satisfaction problems have observable implications (sometime contradicting intuition) on the behavior of generative techniques on such benchmarks. More precisely, we study the problem of generating a uniformly random solution of a given (random) $k$-SAT or $k$-XORSAT formula. Among other findings, we observe that: $(i)$~Continuous diffusions outperform masked discrete diffusions; $(ii)$~Learned diffusions can match the theoretical `ideal' accuracy; $(iii)$~Smart ordering of the variables can significantly improve accuracy, although not following popular heuristics.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
The randomized midpoint method, proposed by [SL19], has emerged as an optimal discretization procedure for simulating the continuous time Langevin diffusions. Focusing on the case of strong-convex and smooth potentials, …
Numerical IntegrationSampling, Diffusions, and Stochastic Localization
Diffusions are a successful technique to sample from high-dimensional distributions can be either explicitly given or learnt from a collection of samples. They implement a diffusion process whose endpoint is a sample fro…
DenoisingGame-Theoretic Optimal Portfolios for Jump Diffusions
This paper studies a two-person trading game in continuous time that generalizes Garivaltis (2018) to allow for stock prices that both jump and diffuse. Analogous to Bell and Cover (1988) in discrete time, the players st…
Fast Score-Based Sampling via Log-Concave Reductions
Sampling based on score diffusions has led to striking empirical results, and has attracted considerable attention from various research communities. It depends on availability of (approximate) Stein score functions for …
Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models
We study general coordinate-wise MCMC schemes (such as Metropolis-within-Gibbs samplers), which are commonly used to fit Bayesian non-conjugate hierarchical models. We relate their convergence properties to the ones of t…