1
$\begingroup$

I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11.

I got stuck on this inequality:

where $f$ is a monotone submodular set function, $S$ and $S^{-1}$ are two sets, $R$ is a random subset of $S$ (sampled from a uniform distribution over subsets of size $k$, where $k$ is some given value.), and $f_{R \setminus \{a\}}(a)$ is the marginal gain by adding an element $a$ to the set $R \setminus \{a\}$.

In particular, how does the second inequality follows from the submodularity of $f$?

$\endgroup$
2
  • $\begingroup$ Okay, submodularity is equivalent to a larger marginal gain if we add $a$ to a superset than the marginal gain to its subset. I can see an intuition that if we assume $a \in R$, then $R\setminus \{a\}$ is a smaller set. Whereas if $a \not\in R$, then $R \setminus \{a\} = R$ which is a large, so $a$ gives a larger marginal gain in the first place. But I don't immediately see that as compatible with conditional probability. It seems to rely on something you haven't told us about $R$, like each element is included with equal independent probability. $\endgroup$
    – usul
    Nov 10, 2022 at 21:01
  • $\begingroup$ @usul $R$ is a random subset of $S$, sampled from a uniform distribution over subsets of size $k$, where $k$ is some given value. $\endgroup$
    – Null_Space
    Nov 10, 2022 at 22:32

1 Answer 1

3
$\begingroup$

The following lemma implies the inequality in question.

Lemma 1. $E[f_{R\setminus \{a\}}(a)] \le E[f_{R\setminus\{a\}}(a) \,|\, a \in R]$

Proof. Consider the following experiment:

  1. Let $R$ be distributed as in the question (uniformly at random from the size-$k$ subsets).

  2. Obtain r.v.'s $R_1$ and $R_2$ from $R$ as follows: if $a\in R$, let $R_1=R_2=R$. Otherwise let $R_1 = R \cup\{a\}$ and let $R_2 = (R \setminus \{x\})\cup\{a\}$ where $x$ is a random element from $R$.

Note the following:

  1. In any outcome $f_{R_1\setminus \{a\}}(a) \le f_{R_2\setminus\{a\}}(a),$ because $f$ is submodular and $R_2 \subseteq R_1$.

  2. $R_2$ is distributed uniformly at random from the size-$k$ sets containing $a$. That is, the distribution of $R_2$ is the distribution of $R$ conditioned on $a\in R$.

Now we have

$\begin{align*} E[f_{R\setminus\{a\}}(a)] & = E[f_{R_1\setminus\{a\}}(a)] && (\text{because } R\setminus\{a\} = R_1\setminus\{a\}) \\ & \le E[f_{R_2\setminus\{a\}}(a)] && (\text{by item 3 above}) \\ & = E[f_{R\setminus\{a\}}(a)\,|\, a\in R] && (\text{by item 4 above})~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\Box \end{align*}$


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.