Rejection sampling from shape-constrained distributions in sublinear time

2021-05-29 · Sinho Chewi, Patrik Gerber, Chen Lu, Thibaut Le Gouic, Philippe Rigollet

We consider the task of generating exact samples from a target distribution, known up to normalization, over a finite alphabet. The classical algorithm for this task is rejection sampling, and although it has been used in practice for decades, there is surprisingly little study of its fundamental limitations. In this work, we study the query complexity of rejection sampling in a minimax framework for various classes of discrete distributions. Our results provide new algorithms for sampling whose complexity scales sublinearly with the alphabet size. When applied to adversarial bandits, we show that a slight modification of the Exp3 algorithm reduces the per-iteration complexity from $\mathcal O(K)$ to $\mathcal O(\log^2 K)$, where $K$ is the number of arms.

📄 PDF Abstract BibTeX arXiv:2105.14166

Code (0)

등록된 구현이 없습니다.

Pliable rejection sampling

2026-04-24 · Akram Erraqabi, Michal Valko, Alexandra Carpentier, Odalric-Ambrym Maillard arxiv

Rejection sampling is a technique for sampling from difficult distributions. However, its use is limited due to a high rejection rate. Common adaptive rejection sampling methods either work only for very specific distrib…

Implicit Variational Rejection Sampling

2026-06-12 · Jian Xu, Shigui Li, Wei Chen, Jiacheng Li 외 arxiv

Variational Inference (VI) is a fundamental inference technique in Bayesian machine learning for approximating complex posterior distributions. Traditional VI often relies on the mean-field factorization, which can inade…

Isoperimetry is All We Need: Langevin Posterior Sampling for RL with Sublinear Regret

2024-12-30 · Emilio Jorge, Christos Dimitrakakis, Debabrota Basu

In Reinforcement Learning (RL) theory, we impose restrictive assumptions to design an algorithm with provably sublinear regret. Common assumptions, like linear or RKHS models, and Gaussian or log-concave posteriors over …

All Reinforcement Learning (RL)

Delayed rejection Hamiltonian Monte Carlo for sampling multiscale distributions

2021-10-01 · Chirag Modi, Alex Barnett, Bob Carpenter

The efficiency of Hamiltonian Monte Carlo (HMC) can suffer when sampling a distribution with a wide range of length scales, because the small step sizes needed for stability in high-curvature regions are inefficient else…

Flexible Mixture Modeling on Constrained Spaces

2018-09-24 · Putu Ayu Sudyanti, Vinayak Rao

This paper addresses challenges in flexibly modeling multimodal data that lie on constrained spaces. Such data are commonly found in spatial applications, such as climatology and criminology, where measurements are restr…

Bayesian Inference Data Augmentation