Discrete Sampling using Semigradient-based Product Mixtures

Alkis Gotovos, Hamed Hassani, Andreas Krause, Stefanie Jegelka
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:228-236, 2018.

Abstract

We consider the problem of inference in dis- crete 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 Gibbs sampler, are commonly used for inference in such models, but their conver- gence is, at times, prohibitively slow. This is often caused by state-space bottlenecks that greatly hinder the movement of such samplers. We propose a novel sampling strategy that uses a specific mixture of product distributions to propose global moves and, thus, acceler- ate convergence. Furthermore, we show how to construct such a mixture using semigradi- ent information. We illustrate the effective- ness of combining our sampler with existing ones, both theoretically on an example model, as well as practically on three models learned from real-world data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-gotovos18a, title = {Discrete Sampling using Semigradient-based Product Mixtures}, author = {Gotovos, Alkis and Hassani, Hamed and Krause, Andreas and Jegelka, Stefanie}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {228--236}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/gotovos18a/gotovos18a.pdf}, url = {https://proceedings.mlr.press/r16/gotovos18a.html}, abstract = {We consider the problem of inference in dis- crete 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 Gibbs sampler, are commonly used for inference in such models, but their conver- gence is, at times, prohibitively slow. This is often caused by state-space bottlenecks that greatly hinder the movement of such samplers. We propose a novel sampling strategy that uses a specific mixture of product distributions to propose global moves and, thus, acceler- ate convergence. Furthermore, we show how to construct such a mixture using semigradi- ent information. We illustrate the effective- ness of combining our sampler with existing ones, both theoretically on an example model, as well as practically on three models learned from real-world data sets.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Discrete Sampling using Semigradient-based Product Mixtures %A Alkis Gotovos %A Hamed Hassani %A Andreas Krause %A Stefanie Jegelka %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-gotovos18a %I PMLR %P 228--236 %U https://proceedings.mlr.press/r16/gotovos18a.html %V R16 %X We consider the problem of inference in dis- crete 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 Gibbs sampler, are commonly used for inference in such models, but their conver- gence is, at times, prohibitively slow. This is often caused by state-space bottlenecks that greatly hinder the movement of such samplers. We propose a novel sampling strategy that uses a specific mixture of product distributions to propose global moves and, thus, acceler- ate convergence. Furthermore, we show how to construct such a mixture using semigradi- ent information. We illustrate the effective- ness of combining our sampler with existing ones, both theoretically on an example model, as well as practically on three models learned from real-world data sets. %Z Reissued by PMLR on 04 October 2026.
APA
Gotovos, A., Hassani, H., Krause, A. & Jegelka, S.. (2018). Discrete Sampling using Semigradient-based Product Mixtures. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:228-236 Available from https://proceedings.mlr.press/r16/gotovos18a.html. Reissued by PMLR on 04 October 2026.

Related Material