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 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 Gibbs sampler, are commonly used for inference in such models, but their convergence 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, accelerate convergence. Furthermore, we show how to construct such a mixture using semigradient information. We illustrate the effectiveness 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 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 Gibbs sampler, are commonly used for inference in such models, but their convergence 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, accelerate convergence. Furthermore, we show how to construct such a mixture using semigradient information. We illustrate the effectiveness 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 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 Gibbs sampler, are commonly used for inference in such models, but their convergence 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, accelerate convergence. Furthermore, we show how to construct such a mixture using semigradient information. We illustrate the effectiveness 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