Corrected samplers reduce discretization error in discrete flow models without additional computational cost.
problem Discretization error in samplers for discrete flow models.
method Established non-asymptotic error bounds for samplers, proposed time-corrected and location-corrected samplers.
result Location-corrected sampler has lower complexity and better generation quality.
Discrete diffusion samplers improve sampling from unnormalised densities.
problem Sampling from discrete unnormalised densities efficiently.
method Introduce off-policy training techniques and data-to-energy Schrödinger bridge training for discrete diffusion samplers.
result Improved performance on synthetic and new benchmarks.
Unified framework extends adjoint Schrödinger bridge sampler to discrete spaces.
problem Challenges in learning discrete neural samplers due to gradients and combinatorial complexity.
method Introduces discrete ASBS, a unified framework that extends adjoint Schrödinger bridge sampler to discrete spaces.
result Empirically, discrete ASBS achieves competitive sample quality with significant advantages in training efficiency and scalability.
New sampler tackles complex discrete energy landscapes efficiently.
problem Stagnation in gradient-based discrete samplers for non-convex settings.
method DREXEL sampler with Replica Exchange and Adjusted Metropolis.
result Proves samplers satisfy detailed balance and converge to target distribution.
LSD distills high-quality samplers for DDMs with fewer steps.
problem Inefficient sampling in DDMs leads to low quality and high computational cost.
method LSD employs a distillation approach to train fast samplers with learnable coefficients and time schedules.
result LSD+ achieves higher sampling quality with fewer steps compared to existing samplers.
DNFS trains efficient samplers for discrete distributions using locally equivariant Transformers.
problem Sampling from unnormalised discrete distributions.
method DNFS learns a rate matrix to satisfy the Kolmogorov equation, using control variates and locally equivariant Transformers.
result DNFS achieves efficient and effective sampling across various applications.
A new sampler for complex discrete distributions efficiently updates all variables in parallel.
problem Sampling complex high-dimensional discrete distributions efficiently and accurately.
method Discrete Langevin proposal (DLP) for parallel coordinate updates with controlled stepsize.
result DLP efficiently explores high-dimensional and strongly correlated variables with asymptotic bias of zero for log-quadratic distributions.
This note clarifies connections between Föllmer process and DDPM sampler.
problem Understanding the relationship between Föllmer process and DDPM sampler.
method Direct discretization of the Föllmer process and DDPM sampler analysis.
result Discretized Föllmer processes provide optimal hyper-parameters for DDPM samplers.
A new sampling method called Restart improves both speed and quality of generative processes.
problem Balancing speed and quality in generative processes involving differential equations.
method Alternates between adding noise and following ODE, improving both speed and quality.
result Surpasses previous SDE and ODE samplers in both speed and accuracy.
PDHAMS improves sampling for discrete distributions with quadratic potential functions.
problem Sampling discrete distributions efficiently and accurately.
method Integrates a second-order approximation of the potential function and uses Gaussian integral trick.
result PDHAMS yields superior performance compared to other methods.
New methods improve memory efficiency for sampling from complex distributions.
problem Sampling from complex unnormalized distributions over discrete domains.
method Two novel training methods for discrete diffusion samplers.
result Achieve state-of-the-art results in unsupervised combinatorial optimization.
A new first-order sampler improves diffusion probabilistic model sampling quality.
problem The belief that first-order methods are inherently slower for diffusion probabilistic model sampling.
method A novel training-free, first-order sampler that approximates the forward-value evaluation via a one-step lookahead predictor.
result The proposed sampler provably approximates the ideal forward-value trajectory while retaining first-order convergence and can improve sample quality under the same NFE budget.
LSB is a new MCMC method for discrete spaces that reduces target evaluations.
problem Sampling in discrete domains with high efficiency and adaptability.
method Local self-balancing proposals, mutual information objective, self-balancing learning.
result LSB converges with fewer target evaluations compared to existing methods.
The pairwise influence matrix of Dobrushin has long been used as an analytical tool to bound the rate of convergence of Gibbs sampling. In this work, we use Dobrushin influence as the basis of a practical tool to certify and efficiently improve the quality of a discrete Gibbs sampler. Our Dobrushin-optimized Gibbs samp…
Discrete diffusion models improve text and image inference.
problem Challenges in posterior sampling with discrete diffusion models.
method Anchored Posterior Sampling (APS) with quantized expectation and anchored remasking.
result APS achieves state-of-the-art performance on various tasks.
BART improves predictive performance but slows down with more data.
problem Understanding and improving the computational efficiency of BART with large datasets.
method Asymptotic analysis of a modified BART sampler, focusing on hitting time of high posterior density sets.
result The convergence time of the BART sampler increases with the number of training samples due to multi-modality, but can be mitigated by increasing the number of trees or raising the sampler temperature.
Enhances gradient-based discrete samplers with parallel tempering for multimodal distributions.
problem Local minima in high-dimensional, multimodal discrete distributions.
method Combines parallel tempering with discrete Langevin proposal, using Metropolis criterion for swaps.
result Significantly faster mixing and better sampling from complex distributions.
We consider the problem of inference in discrete probabilistic models, that is, distributions over subsets of a finite ground set. These encompass a range of well-known models in machine learning, such as determinantal point processes and Ising models. Locally-moving Markov chain Monte Carlo algorithms, such as the Gib…
The paper analyzes sampling efficiency of discrete diffusion models, providing sharp and adaptive guarantees.
problem Theoretical foundations of discrete diffusion models, especially sampling efficiency.
method Continuous-time Markov chain (CTMC) formulation, τ-leaping-based samplers, effective total correlation. result The τ-leaping algorithm achieves an iteration complexity of order ildeO(d/ε) for uniform discrete diffusion, improving existing bounds by a factor of d. The paper analyzes convergence rates of Langevin dynamics and Proximal Sampler using Φ-divergence.
problem Analyzing convergence rates of Langevin dynamics and Proximal Sampler.
method Extending mixing time analyses to Φ-divergence, using strong data processing inequalities. result Convergence of Φ-divergence to 0 exponentially fast along Unadjusted Langevin Algorithm and Proximal Sampler. MDNS generates samples from complex discrete distributions efficiently.
problem Learning neural samplers for discrete state spaces with multi-modal distributions.
method A novel framework using stochastic optimal control of continuous-time Markov chains.
result MDNS outperforms other methods in generating accurate samples from high-dimensional, multi-modal distributions.
Riemannian Proximal Sampler improves sampling on manifold data.
problem Sampling from densities on Riemannian manifolds.
method Uses MBI and RHK oracles for high-accuracy sampling.
result Sampling with ε-accuracy requires O(log(1/ε)) iterations in KL divergence.
New PDMP samplers tackle variable selection in models.
problem Jointly explore model space and parameter space.
method Develop reversible jump PDMP samplers.
result New samplers mix better and are more efficient.
Paper proposes new Langevin samplers for sampling from log-concave distributions with superlinear gradient growth.
problem Sampling from log-concave distributions with superlinear gradient growth.
method Proposes two novel discretizations of kinetic Langevin SDEs, showing contractivity and log-Sobolev inequality.
result Establishes non-asymptotic bounds in 2-Wasserstein distance between sampled distributions and target measures.
New analysis improves convergence guarantees for diffusion-based samplers in Wasserstein distance.
problem Improving convergence guarantees for diffusion-based generative models.
method Simple framework to analyze discretization, initialization, and score estimation errors.
result First Wasserstein convergence bound for the Heun sampler and improved results for Euler sampler.
Paper develops Bayesian inference for discrete-choice mnp models with Gaussian priors.
problem Estimating parameters of discrete-choice multinomial probit models with Gaussian priors.
method Adapts Fasano and Durante's results to a specific mnp model with zero mean and independent Gaussian priors, simplifying posterior distribution parameters and providing a new variational algorithm.
result Simplified expressions for posterior distribution parameters and a novel variational algorithm.
A fundamental task in machine learning and related fields is to perform inference on Bayesian networks. Since exact inference takes exponential time in general, a variety of approximate methods are used. Gibbs sampling is one of the most accurate approaches and provides unbiased samples from the posterior but it has hi…
Enhanced Markov chain sampler learns network statistics faster.
problem Learning network statistics efficiently.
method Integrates graph Forman curvature into Markov chain transition probabilities and stationary distribution.
result Curved Markov chain Monte Carlo achieves faster convergence.
Paper adapts diffusion sampler training for faster convergence and better sampling.
problem Training limitations in diffusion samplers.
method Decouples generation and destruction variances, learns both as unconstrained Gaussians.
result Training both processes leads to faster convergence and improved sampling quality.
One-step diffusion samplers reduce sampling time and computational costs.
problem Efficient sampling from complex distributions.
method One-step diffusion, self-distillation, deterministic flow.
result Achieves competitive sample quality with fewer evaluations.
Gradient-based MCMC for discrete spaces improves sampling performance.
problem Sampling in discrete spaces using traditional methods is challenging.
method Introduced new discrete Metropolis-Hastings samplers inspired by MALA, with a novel preconditioning technique.
result Demonstrated strong empirical performance across various challenging sampling problems.
A new sampler speeds up Bayesian mixture models.
problem Sampling from Bayesian finite mixture models is slow and hard.
method Introduces a non-reversible sampling scheme for Bayesian finite mixture models.
result The new sampler outperforms classical samplers in many scenarios, especially during convergence.
Improved state estimation in high-dimensional models using Zig-Zag Sampler.
problem Weight degeneracy in particle filtering methods for high-dimensional state space models.
method Discrete Zig-Zag Sampler applied within the Composite MH Kernel of SMCMC framework.
result Improves estimation accuracy and increases acceptance ratio in high-dimensional state estimation.
An infinite parallel tempering bouncy particle sampler improves sampling efficiency for multimodal distributions.
problem Sampling from complex posterior distributions with high accuracy and efficiency.
method Introduced an infinite parallel tempering bouncy particle sampler (BPS-PT) to accelerate convergence.
result Demonstrated improved sampling efficiency for multimodal distributions through numerical simulations.
Paper analyzes convergence of ODE samplers in Wasserstein distances.
problem Limited theoretical understanding of convergence properties of probability flow ODEs.
method Convergence analysis for general probability flow ODEs in 2-Wasserstein distance.
result First non-asymptotic convergence analysis for probability flow ODE samplers.
New sampling method on Lie groups converges quickly.
problem Sampling on non-Euclidean Lie groups.
method Kinetic Langevin dynamics with noise added.
result Exponential convergence rate proved under W2 distance. We present a novel technique for learning the mass matrices in samplers obtained from discretized dynamics that preserve some energy function. Existing adaptive samplers use Riemannian preconditioning techniques, where the mass matrices are functions of the parameters being sampled. This leads to significant complexiti…
Continuous time framework for discrete data denoising models.
problem Efficient training and sampling for discrete data denoising models.
method Formulated as Continuous Time Markov Chains (CTMCs), efficient training using continuous time ELBO, high-dimensional CTMC simulation, novel theoretical error bound.
result Continuous time treatment enables novel theoretical error bound between generated and true data distributions.
EDLP samples flat modes in discrete spaces using entropy.
problem Sampling flat modes in discrete spaces is challenging.
method EDLP uses a continuous auxiliary variable and local entropy to guide sampling.
result EDLP consistently outperforms traditional methods in various tasks.
This work improves the Euler method for masked diffusion models, providing tighter convergence guarantees.
problem Improving the convergence rates of masked diffusion models.
method Developed a direct total-variation (TV) based analysis for the Euler method, relaxing assumptions and improving parameter dependencies.
result Established convergence guarantees for the Euler sampler without requiring surrogate initialization, and provided a tight lower bound.
Paper explores how Rectified Flow adapts to low-dimensional data.
problem Improving sampling efficiency in low-dimensional data.
method Investigates Rectified Flow's adaptation to low-dimensional support and introduces a stochastic version.
result Shows improved sampling efficiency with O(k/ε) complexity. PDNS tackles multimodal sampling challenges using proximal point method.
problem Multimodal distributions with significant barriers between modes.
method Proximal point method on path measures, decomposing into simpler subproblems.
result PDNS effectively promotes thorough exploration across modes.
We convert deterministic flow models to stochastic samplers.
problem Deterministic flow models are sensitive to errors and cannot condition on intermediate states.
method Transform ODEs into SDEs with the same marginal distributions.
result Empirically outperforms deterministic samplers and controls generation diversity.
This work introduces a fair learning method for diverse sensitive attributes.
problem Fairness in supervised learning with complex sensitive attributes.
method Neural network with a simple random sampler for fairness penalties.
result The method improves fairness and utility on benchmark data.
Researchers analyze inverse optimal transport, deriving theoretical and empirical insights.
problem Understanding the inverse problem of inferring cost matrices from optimal couplings.
method Formalized and analyzed using entropy-regularized optimal transport, with theoretical and empirical contributions.
result Characterization of the manifold of cross-ratio equivalent costs and derivation of an MCMC sampler.
UniNet efficiently learns network representations from large graphs.
problem Efficiently learning network representations from large graphs.
method Metropolis-Hastings sampling for efficient edge sampling and random walk model abstraction.
result UniNet outperforms existing NRL models on billion-edge networks.
Paper proposes a new method for sampling from complex distributions.
problem Sampling from unnormalised density functions in complex distributions.
method Combines amortised and particle-based methods with reinforcement learning.
result Improves sampling from complex distributions compared to existing methods.
Bayesian Tensor Ring factorization improved for scalability and handling of discrete data.
problem Scalability issues and handling of discrete data in Bayesian Tensor Ring factorization.
method Proposes a novel Bayesian Tensor Ring model with a nonparametric Multiplicative Gamma Process prior and Pólya-Gamma augmentation for discrete data. Developed efficient Gibbs sampler and online EM algorithm for scalability.
result Significantly improved scalability and handling of discrete data compared to previous methods.