Properties of submodular functions

Question

I was working on submodular set functions, and I came across a property on Wikipedia, that I was not able to prove/find any reference for. On the Wikipedia article on submodular set functions, Under the section Properties, The third property states that :

More generally, $g(S) = h(f(S))$ is submodular, for any non decreasing concave function $h$.

They claim that this is true for all submodular $f(S)$. Is there a reference for this property where I will be able to find a proof? Alternatively, is there is a simple proof for this that I may be missing?

Answer 1

Please note that in the previous sentence, they mention the fact that it has to be a Monotone submodular function. Indeed, if you use $f$ as a graph cut function, which is non-monotone, and a concave mapping for example $\sqrt{.}$ then it will no longer be submodular. (This is also pointed out as a comment by Chris Harshaw in this post).

Let $\phi: \mathfrak{D} \to \mathbb{R}$ be a concave mapping where $\mathfrak{D}$ is the domain of $\phi$. Let s, t, and u be such that $s < t < u $, then we can show the following for concave functions.

$$ \frac{\phi(t)- \phi(s)}{t - s} \geq \frac{\phi(u)-\phi(s)}{u - s} \geq \frac{\phi(u)-\phi(t)}{u - t}$$

Now consider a, b, c, and d such that $a < b < c < d$. Then we have the following using the above-mentioned property.

$$ \frac{\phi(c)- \phi(a)}{c - a} \geq \frac{\phi(d)-\phi(b)}{d - b} $$

Moreover, we also have

$$ \frac{\phi(b)- \phi(a)}{b - a} \geq \frac{\phi(d)-\phi(c)}{d - c} $$

Let $A \subset B \subset V$ and $ e \in V \setminus B$. From monotonicity of $f$, we have $ f(A) \lt f(A \cup \{e\}) $ and $ f(B) \lt f(B \cup \{e\}) $. Moreover, $f(A) \lt f(B)$ and $f(A \cup \{e\}) \lt f(B \cup \{e\})$. Thus, we have two possible scenarios

$$f(A) \lt f(B) \lt f(A \cup \{e\}) \lt f(B \cup \{e\})$$ and $$f(A) \lt f(A \cup \{e\}) \lt f(B) \lt f(B \cup \{e\})$$

Denote $g(S) = \phi(f(S))$ and the corresponding "gain" as $g(e | A) = g(A \cup \{e\}) - g(A) $. With these notations, and the property of concave functions, we can show that

$$ \frac{g(e|A)}{f(e|A)} \geq \frac{g(e|B)}{f(e|B)} $$ Therefore, $$ g(e|A) \geq g(e|B)\frac{f(e|A)}{f(e|B)} $$

Due to submodularity, we have $\frac{f(e|A)}{f(e|B)} \geq 1$.

Therefore we have diminishing return property for g as well. That is, $\frac{g(e|A)}{g(e|B)} \geq 1$

Answer 2

Gantavya's answer is good, but I prefer my notation :-).

Suppose $f$ is monotone non decreasing & submodular, and $h$ is concave and non decreasing.

We prove that $h \circ f$ is submodular using the equivalent law of diminishing returns.

Suppose that $A \subset B $ and $i \notin B$. Let $x_1 = f(A), x_2=f(A \cup \{i\}), y_1 = f(B), y_2 = f(B \cup \{i\})$. Then we have (since $f$ is submodular) $x_2-x_1 \ge y_2 -y_1$. Also note that since $f$ is monotone non decreasing, $x_1 \le y_1$.

Let $\delta = y_2 - y_1$ , then we have $h(x_1+\delta) -h(x_1) \ge h(y_1+\delta) -h(y_1) = h(y_2)-h(y_1)$ from https://en.wikipedia.org/wiki/Convex_function#Functions_of_one_variable (noting that $-h$ is convex and $R(x_1+\delta,x_1) \ge R(y_1+\delta,y_1)$.)

Since $x_2 \ge x_1+\delta$ and $h$ is nondecreasing, $h(x_2) \ge h(x_1+\delta)$ and so we have $(h \circ f)(A \cup \{i\}) - (h \circ f)(A) \ge (h \circ f)(B \cup \{i\}) - (h \circ f)(B \cup \{i\}) $ and so $h \circ f$ is submodular.