<p>There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled <a href="https://las.inf.ethz.ch/files/gotovos15sampling-long.pdf" rel="nofollow noreferrer">"Sampling from Probabilistic Submodular Models"</a> which describes a MCMC method based on Gibbs sampling. They show that the mixing time <span class="math-container">$t_{\text{mix}}(\epsilon)$</span> is bounded above by 
<span class="math-container">$$ t_{\text{mix}}(\epsilon) \leq 2 n^2 \exp(\zeta_f) \log \left( \frac{1}{\epsilon p_\min} \right) $$</span>
where <span class="math-container">$p_\min = \min_{S} p(S)$</span> and the quantity <span class="math-container">$\zeta_f$</span> is
<span class="math-container">$$\zeta_f =  \max_{A, B \subset V} \left| f(A) + f(B) - f(A \cup B) - f(A \cap B) \right| $$</span>
which I don't know of appearing elsewhere in the literature. There is another paper by Rebeschini and Karbasi (JMLR, 2015) titled <a href="http://proceedings.mlr.press/v40/Rebeschini15.pdf" rel="nofollow noreferrer">"Fast Mixing for Discrete Point Processes"</a> which proposes a different Gibbs sampler whose mixing time is bounded using the so-called "discrete hessian" which I also haven't seen used elsewhere in the literature.</p>

<p>It seems that submodularity of <span class="math-container">$f$</span> alone isn't enough to get fast mixing times for MCMC methods. Current methods certainly need to consider other quantities of <span class="math-container">$f$</span> to ensure fast mixing times.</p>

CC BY-SA 4.0
2019-03-20T13:04:00.100Z
2019-03-20T13:04:00.100Z
Chris Harshaw
<p>Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability
$p_S = \frac{e^{f(S)}}{\sum_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a submodular function?</p>

<p>Thanks!</p>

<ds.algorithms><submodularity>
How to sample from a distribution with submodular weights
Asterix
# How to sample from a distribution with submodular weights

(Asked by: username_0 on 2015-07-05)

Is there a known algorithm for sampling a set $S \subset \{1,...,n\}$ with probability
$p\_S = \frac{e^{f(S)}}{\sum\_{T \subset \{1,...,n\}} e^{f(T)}}$ where $f: 2^{\{1,...,n\}} \to \mathbb{R}$ is a submodular function?

Thanks!

**Tags:** ds.algorithms, submodularity


---

## 1 answers

### Answer by username_1 on 2019-03-20. Score: 1

There is a paper by Gotovos, Hassani, and Krause (NIPS, 2015) titled ["Sampling from Probabilistic Submodular Models"](https://las.inf.ethz.ch/files/gotovos15sampling-long.pdf) which describes a MCMC method based on Gibbs sampling. They show that the mixing time $t\_{\text{mix}}(\epsilon)$ is bounded above by
$$ t\_{\text{mix}}(\epsilon) \leq 2 n^2 \exp(\zeta\_f) \log \left( \frac{1}{\epsilon p\_\min} \right) $$
where $p\_\min = \min\_{S} p(S)$ and the quantity $\zeta\_f$ is
$$\zeta\_f = \max\_{A, B \subset V} \left| f(A) + f(B) - f(A \cup B) - f(A \cap B) \right| $$
which I don't know of appearing elsewhere in the literature. There is another paper by Rebeschini and Karbasi (JMLR, 2015) titled ["Fast Mixing for Discrete Point Processes"](http://proceedings.mlr.press/v40/Rebeschini15.pdf) which proposes a different Gibbs sampler whose mixing time is bounded using the so-called "discrete hessian" which I also haven't seen used elsewhere in the literature.

It seems that submodularity of $f$ alone isn't enough to get fast mixing times for MCMC methods. Current methods certainly need to consider other quantities of $f$ to ensure fast mixing times.


---

