Submodular Functions and Their Optimization
Preface
Submodular functions are an important concept in combinatorial optimization and discrete mathematics, with wide-ranging applications across computer science, economics, and systems engineering.
In machine learning and data mining, for example, submodular functions are used for feature selection, clustering, and influence maximization. Choosing the subset of features that best represents a dataset is a submodular optimization problem: the diminishing-returns property guarantees that each newly selected feature contributes less information than the last, which helps avoid overfitting.
Submodular functions are also used in graph theory to solve minimum cut and maximum flow problems. The influence maximization problem in network analysis is another classic application — maximizing the spread of information through a social network, say.
From Concavity to Submodularity
Before getting into submodularity, let us first look at what concavity means.
As the figure above shows, a function $f:\mathbb{R}\to\mathbb{R}$ is concave if $f^{\prime}(\mathbf{x})$ is non-increasing.
Analogously, as the figure above shows, $f:{0,1}^n\to\mathbb{R}$ is submodular if $\partial_if(x)=f(x+e_i)-f(x)$ is non-increasing for every $i$. Note that the domain of a submodular function is discrete.
As shown in the figure above, let $S\subset T,j\notin T$. If $f$ satisfies $$ f(S \cup \{j\}) - f(S) \geq f(T \cup \{j\}) - f(T) $$ then $f$ is said to be submodular.
If $f:2^{[n]}\to\mathbb{R}$ satisfies the following for all $S$ and $T$, then $f$ is submodular. $$ f(S\cup T)+f(S\cap T)\leq f(S)+f(T). $$ That is, for any two nested subsets (say $A\subset B$), adding the same new element to $A$ and to $B$ yields a gain for $A$ that is at least as large as the gain for $B$. This is a form of “diminishing returns.”
Submodular functions can describe phenomena such as “the more you buy, the cheaper it gets,” or economies of scale. Consider a shopping trip: the first item may bring considerable satisfaction, but as the number of items grows, each additional one adds less and less.
Optimizing Submodular Functions
Given a submodular function, how do we find its maximum and its minimum?
Lovász extension
Earlier work (Grötschel-Lovász-Schrijver, 1981; Iwata-Fleischer-Fujishige / Schrijver, 2000) showed that the Lovász extension solves the minimization problem for any submodular function $f:{0,1}^n\to\mathbb{R}$ in polynomial time.
The Lovász extension turns a submodular function ( f ) into a convex function $ f^L $. $$ f^L(x) = \mathbb{E}_{\lambda\in[0,1]}[f(\{i : x_i > \lambda\})] $$ Because the resulting $f^L$ lives on a continuous domain, its minimum is easy to compute, and the minimizer of $f^L(x) $ can be converted back into the minimizer of $f(S) $.
Minimizing a submodular function thus reduces to a convex optimization problem, and is solved as one.
Greedy
Recall the definition of a submodular function given above. Intuitively it resembles a concave function, yet maximizing a submodular function is in fact a classic NP-hard problem! (Max Cut and Max Coverage are concrete examples.)
Analogously, as the figure above shows, $f:\{0,1\}^n\to\mathbb{R}$ is submodular if the discrete derivative $\partial_if(x)=f(x+e_i)-f(x)$ is non-increasing for every $i$. For background on P, NP, NPC, and NP-hard, see http://www.matrix67.com/blog/archives/105
Does that mean the problem is hopeless? Not at all. Even if we cannot obtain the exact maximum of a submodular function, an approximation to the optimum is perfectly acceptable.
Let us first state the problem: $$ \max_{S\subseteq\mathcal{V},S\in\mathcal{I}}f(S),S\subset T\Rightarrow f(S)\leq f(T) $$ Here $f(\cdot)$ is a submodular function defined on the dataset $\nu$, and $\mathcal{I}$ is a constraint that depends on the specific setting (often the full set cannot be chosen). Note that this time we require $f$ to be monotonically increasing.
This problem can be tackled with a greedy strategy: at each step, add to $S$ the element that maximizes the gain. That is, pick the element $i$ that maximizes $ f(S+i)-f(S)$, while keeping $S$ within the feasible region $\mathcal{I}$.
A 1978 theorem of Nemhauser, Wolsey, and Fisher states that if $f$ is monotone and submodular, the solution found by the greedy algorithm is at least $ (1 - 1/e) $ times the optimum of the problem $\max_{S\subseteq\mathcal{V},S\in\mathcal{I}}:|S| ≤ k$.
Nemhauser, Wolsey, Fisher ’78: https://www.cs.toronto.edu/%7Eeidan/papers/submod-max.pdf
For the proof see https://zhuanlan.zhihu.com/p/560699106
We now have a basic grasp of how to solve submodular problems, but the scheme above still leaves several questions open:
- For the problem formulated as maximizing $f(S)$, what is the best achievable approximation when $f$ is monotone submodular and $I$ forms a matroid?
- How should non-monotone submodular functions be optimized?
- What about more general constraints, or combinations of several simple ones?
Later work has proposed further greedy-based methods for submodular optimization.
Multilinear Relaxation
Calinescu, Chekuri, Pál, and Vondrák (’07) turned the discrete optimization problem into a continuous one with the multilinear relaxation of a submodular function.
The multilinear extension $F(x) $ is defined as follows: $$ F(x) = \mathbb{E}[f(\hat{x})] $$ where $\hat{x}$ is obtained by randomly rounding each $x_i$ to 0 or 1 with probability $x_i$.
The multilinear relaxation has the following properties:
- $F(x)$ is neither globally concave nor globally convex.
- The second derivative $\frac{\partial^2 F}{\partial x_i^2}$ of $F$ is zero.
- If $\vec{d}$ is non-negative, then $F(x + \lambda \vec{d})$ is a concave function of $\lambda$.
Once the discrete problem has been made continuous, we can find an approximate solution by continuous optimization and then round it to the nearest integer solution of the discrete problem.
Continuous Greedy
We seek the maximum of $F(x)$, that is $\max{F(x):x\in P)}$, where $F$ is the multilinear extension of a monotone submodular function.
For each $x \in P$, define $v(x)$ as $$ v(x) = argmax_{v \in P}(v \cdot \nabla F(x)) $$ Define $x(t)$ by:
- $x(0) = 0$
- $\frac{dx}{dt} = v(x)$
with $t$ ranging over $[0, 1]$, and return $x(1)$.
This method guarantees $x(1) \in P$, with $F(x(1))$ at least $(1-\frac1e)$ times the optimum (OPT).
By the chain rule, $$ \frac{dF}{dt}=\frac{dx}{dt}\cdot\nabla F(x(t))=v(x)\cdot\nabla F(x(t))\geq OPT-F(x(t)). $$ from which we obtain $$ F(x(t))\geq(1-e^{-t})\cdot OPT. $$
References
[1] https://theory.stanford.edu/~jvondrak/data/SIDMA-plenary-talk.pdf
[2] https://zhuanlan.zhihu.com/p/560699106
[3] https://www.cs.toronto.edu/%7Eeidan/papers/submod-max.pdf
