Are the submodularity the same as the convexity?

Question

I want to prove that a function $Q$ is convex, but a friend of mine says that if $Q$ is discrete, I need to prove that Q is submodular rather than convex. So I'm wondering, are submodularity and convexity interchangeable? Is submodularity only for discrete and convexity only for continuous functions?

Answer 1

No, Submodularity and Convexity are NOT interchangeable in the discrete domains. Although submodular set functions do share properties that are similar to a convex function, they also have properties that are similar to concave functions.

Convex Aspects:

• Submodular functions exhibit polynomial-time unconstrained minimization. For example, the Fujishige-Wolfe Min norm point algorithm (see this paper).
• Another property could be the existence of tight linear (Modular in set function paradigm) lower bounds. (See this paper)

Concave Aspects:

• The diminishing returns property $ \forall A, B \subseteq V : A \subset B$ and $ e \in V \setminus (A \cup B) $ $$ f(A \cup \{e\}) - f(A) \geq f(B \cup \{e\}) - f(B) $$
• We can associate tight modular Upper bounds.
• Since submodular functions are set functions, we can associate continuous extension(s), one of them being the multi-linear extension, which can be shown to be concave in certain directions.

For continuous domains, there exists a property called as DR-Submodularity. Consider $G : \mathscr{X} \to \mathbb{R}$ where $\mathscr{X}$ is any arbitrary subset of $\mathbb{R}^d$. If $\{e_i\}_{i=1}^d$ denote the standard basis, and ordering is defined coordinate wise, then $$G\left(\mathbf{a}+k \mathbf{e}_{i}\right)-G(\mathbf{a}) \geq G\left(\mathbf{b}+k \mathbf{e}_{i}\right)-G(\mathbf{b})$$ where $\mathbf{a} \leq \mathbf{b}$ and $\mathbf{a}+k \mathbf{e}_{i} \in \mathscr{X}$, $\mathbf{b}+k \mathbf{e}_{i} \in \mathscr{X}$

The two mentioned references are great to read more about convex/concave aspects of Submodular functions. For DR-Submodularity, please have a look at this paper