Learning with Submodular Functions: A Convex Optimization Perspective

Chapter 1 Introduction

Many combinatorial optimization problems may be cast as the minimization of a set-function, that is a function defined on the set of subsets of a given base set $V$. Equivalently, they may be defined as functions on the vertices of the hyper-cube, i.e, $\{0,1\}^{p}$ where $p$ is the cardinality of the base set $V$—they are then often referred to as pseudo-boolean functions . Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces, as many functions that occur in practical problems turn out to be submodular functions or slight modifications thereof, with applications in many areas areas of computer science and applied mathematics, such as machine learning , computer vision , operations research , electrical networks or economics . Since submodular functions may be minimized exactly, and maximized approximately with some guarantees, in polynomial time, they readily lead to efficient algorithms for all the numerous problems they apply to. They are also appear in several areas of theoretical computer science, such as matroid theory .

However, the interest for submodular functions is not limited to discrete optimization problems. Indeed, the rich structure of submodular functions and their link with convex analysis through the Lovász extension and the various associated polytopes makes them particularly adapted to problems beyond combinatorial optimization, namely as regularizers in signal processing and machine learning problems . Indeed, many continuous optimization problems exhibit an underlying discrete structure (e.g., based on chains, trees or more general graphs), and submodular functions provide an efficient and versatile tool to capture such combinatorial structures.

In this monograph, the theory of submodular functions is presented in a self-contained way, with all results proved from first principles of convex analysis common in machine learning, rather than relying on combinatorial optimization and traditional theoretical computer science concepts such as matroids or flows (see, e.g., for a reference book on such approaches). Moreover, the algorithms that we present are based on traditional convex optimization algorithms such as the simplex method for linear programming, active set method for quadratic programming, ellipsoid method, cutting planes, and conditional gradient. These will be presented in details, in particular in the context of submodular function minimization and its various continuous extensions. A good knowledge of convex analysis is assumed (see, e.g., ) and a short review of important concepts is presented in Appendix A—for more details, see, e.g., .

The monograph is organized in several chapters, which are summarized below (in the table of contents, sections that can be skipped in a first reading are marked with a star∗):

Definitions: In Chapter 2, we give the different definitions of submodular functions and of the associated polyhedra, in particular, the base polyhedron and the submodular polyhedron. They are crucial in submodular analysis as many algorithms and models may be expressed naturally using these polyhedra.

Polyhedra: Associated polyhedra are further studied in Chapter 4, where support functions and the associated maximizers of linear functions are computed. We also detail the facial structure of such polyhedra, which will be useful when related to the sparsity-inducing properties of the Lovász extension in Chapter 5.

Convex relaxation of submodular penalties: While submodular functions may be used directly (for minimization of maximization of set-functions), we show in Chapter 5 how they may be used to penalize supports or level sets of vectors. The resulting mixed combinatorial/continuous optimization problems may be naturally relaxed into convex optimization problems using the Lovász extension.

Examples: In Chapter 6, we present classical examples of submodular functions, together with several applications in machine learning, in particular, cuts, set covers, network flows, entropies, spectral functions and matroids.

Non-smooth convex optimization: In Chapter 7, we review classical iterative algorithms adapted to the minimization of non-smooth polyhedral functions, such as subgradient, ellipsoid, simplicial, cutting-planes, active-set, and conditional gradient methods. A particular attention is put on providing when applicable primal/dual interpretations to these algorithms.

Separable optimization - Algorithms: In Chapter 9, we present two sets of algorithms for separable optimization problems. The first algorithm is an exact algorithm which relies on the availability of an efficient submodular function minimization algorithm, while the second set of algorithms are based on existing iterative algorithms for convex optimization, some of which come with online and offline theoretical guarantees. We consider active-set methods (“min-norm-point” algorithm) and conditional gradient methods.

Submodular function minimization: In Chapter 10, we present various approaches to submodular function minimization. We present briefly the combinatorial algorithms for exact submodular function minimization, and focus in more depth on the use of specific convex optimization problems, which can be solved iteratively to obtain approximate or exact solutions for submodular function minimization, with sometimes theoretical guarantees and approximate optimality certificates. We consider the subgradient method, the ellipsoid method, the simplex algorithm and analytic center cutting planes. We also show how the separable optimization problems from Chapters 8 and 9 may be used for submodular function minimization. These methods are then empirically compared in Chapter 12.

Submodular optimization problems: In Chapter 11, we present other combinatorial optimization problems which can be partially solved using submodular analysis, such as submodular function maximization and the optimization of differences of submodular functions, and relate these to non-convex optimization problems on the submodular polyhedra. While these problems typically cannot be solved in polynomial time, many algorithms come with approximation guarantees based on submodularity.

Experiments: In Chapter 12, we provide illustrations of the optimization algorithms described earlier, for submodular function minimization, as well as for convex optimization problems (separable or not). The Matlab code for all these experiments may be found at http://www.di.ens.fr/~fbach/submodular/.

In Appendix A, we review relevant notions from convex analysis (such as Fenchel duality, dual norms, gauge functions, and polar sets), while in Appendix B, we present several results related to submodular functions, such as operations that preserve submodularity.

Several books and monograph articles already exist on the same topic and the material presented in this monograph rely on those . However, in order to present the material in the simplest way, ideas from related research papers have also been used, and a stronger emphasis is put on convex analysis and optimization.

Chapter 2 Definitions

The field of submodular analysis takes its roots in matroid theory, and submodular functions were first seen as extensions of rank functions of matroids (see and §6.8) and their analysis strongly linked with special convex polyhedra which we define in §2.2. After the links with convex analysis were established , submodularity appeared as a central concept in combinatorial optimization. Like convexity, many models in science and engineering and in particular in machine learning involve submodularity (see Chapter 6 for many examples). Like convexity, submodularity is usually enough to derive general theories and generic algorithms (but of course some special cases are still of importance, such as min-cut/max-flow problems), which have attractive theoretical and practical properties. Finally, like convexity, there are many areas where submodular functions play a central but somewhat hidden role in combinatorial and convex optimization. For example, in Chapter 5, we show how many problems in convex optimization involving discrete structured turns out be cast as submodular optimization problems, which then immediately lead to efficient algorithms.

In §2.1, we provide the definition of submodularity and its equivalent characterizations. While submodularity may appear rather abstract, it turns out it come up naturally in many examples. In this chapter, we will only review a few classical examples which will help illustrate our various results. For an extensive list of examples, see Chapter 6. In §2.2, we define two polyhedra traditionally associated with a submodular function, while in §2.3, we consider non-decreasing submodular functions, often referred to as polymatroid rank functions.

Submodular functions may be defined through several equivalent properties, which we now present. Additive measures are the first examples of set-functions, the cardinality being the simplest example. A well known property of the cardinality is that for any two sets $A,B\subseteq V$, then $|A|+|B|=|A\cup B|+|A\cap B|$, which extends to all additive measures. A function is submodular if and only if the previous equality is only an inequality for all subsets $A$ and $B$ of $V$:

Note that if a function is submodular and such that $F(\varnothing)=0$ (which we will always assume), for any two disjoint sets $A,B\subseteq V$, then $F(A\cup B)\leqslant F(A)+F(B)$, i.e., submodularity implies sub-additivity (but the converse is not true).

As seen earlier, the simplest example of a submodular function is the cardinality (i.e., $F(A)=|A|$ where $|A|$ is the number of elements of $A$), which is both submodular and supermodular (i.e., its opposite $A\mapsto-F(A)$ is submodular). It turns out that only additive measures have this property of being modular.

From Def. 2.1, it is clear that the set of submodular functions is closed under linear combination and multiplication by a positive scalar (like convex functions).

Moreover, like convex functions, several notions of restrictions and extensions may be defined for submodular functions (proofs immediately follow from Def. 2.1):

More operations that preserve submodularity are defined in Appendix B, in particular partial minimization (like for convex functions). Note however, that in general the pointwise minimum or pointwise maximum of submodular functions are not submodular (properties which would be true for respectively concave and convex functions).

Checking the condition in Def. 2.1 is not always easy in practice; it turns out that it can be restricted to only certain sets $A$ and $B$, which we now present.

The following proposition shows that a submodular has the “diminishing return” property, and that this is sufficient to be submodular. Thus, submodular functions may be seen as a discrete analog to concave functions. However, as shown in Chapter 3, in terms of optimization they behave more like convex functions (e.g., efficient minimization, duality theory, links with the convex Lovász extension).

(Definition with first-order differences) The set-function $F$ is submodular if and only if for all $A,B\subseteq V$ and $k\in V$, such that $A\subseteq B$ and $k\notin B$, we have

Proof Let $A\subseteq B$, and $k\notin B$; we have $F(A\cup\{k\})-F(A)-F(B\cup\{k\})+F(B)=F(C)+F(D)-F(C\cup D)-F(C\cap D)$ with $C=A\cup\{k\}$ and $D=B$, which shows that the condition is necessary. To prove the opposite, we assume that the first-order difference condition is satisfied; one can first show that if $A\subseteq B$ and $C\cap B=\varnothing$, then $F(A\cup C)-F(A)\geqslant F(B\cup C)-F(B)$ (this can be obtained by summing the $m$ inequalities $F(A\cup\{c_{1},\dots,c_{k}\})-F(A\cup\{c_{1},\dots,c_{k-1}\})\geqslant F(B\cup\{c_{1},\dots,c_{k}\})-F(B\cup\{c_{1},\dots,c_{k-1}\})$ where $C=\{c_{1},\dots,c_{m}\}$).

Then, for any $X,Y\subseteq V$, take $A=X\cap Y$, $C=X\backslash Y$ and $B=Y$ (which implies $A\cup C=X$ and $B\cup C=X\cup Y$) to obtain $F(X)+F(Y)\geqslant F(X\cup Y)+F(X\cap Y)$, which shows that the condition is sufficient.

The following proposition gives the tightest condition for submodularity (easiest to show in practice).

(Definition with second-order differences) The set-function $F$ is submodular if and only if for all $A\subseteq V$ and $j,k\in V\backslash A$, we have $F(A\cup\{k\})-F(A)\geqslant F(A\cup\{j,k\})-F(A\cup\{j\})$.

Proof This condition is weaker than the one from the previous proposition (as it corresponds to taking $B=A\cup\{j\}$). To prove that it is still sufficient, consider $A\subseteq V$, $B=A\cup\{b_{1},\dots,b_{s}\}$, and $k\in V\backslash B$. We can apply the second-order difference condition to subsets $A\cup\{b_{1},\dots,b_{s-1}\}$, $j=b_{s}$, and sum the $m$ inequalities $F(A\cup\{b_{1},\dots,b_{s-1}\}\cup\{k\})-F(A\cup\{b_{1},\dots,b_{s-1}\}\ )\geqslant F(A\cup\{b_{1},\dots,b_{s}\}\cup\{k\})-F(A\cup\{b_{1},\dots,b_{s}\})$, for $s\in\{1,\dots,m\}$, to obtain the condition in Prop. 2.2.

Note that the set of submodular functions is itself a conic polyhedron with the facets defined in Prop. 2.3. In order to show that a given set-function is submodular, there are several possibilities: (a) use Prop. 2.3 directly, (b) use the Lovász extension (see Chapter 3) and show that it is convex, (c) cast the function as a special case from Chapter 6 (typically a cut or a flow), or (d) use known operations on submodular functions presented in Appendix B.

Beyond modular functions, we will consider as running examples for the first chapters of this monograph the following submodular functions (which will be studied further in Chapter 6):

Counting elements in a partitions: Given a partition of $V$ into $m$ sets $G_{1},\dots,G_{m}$, then the function $F$ that counts for a set $A$ the number of elements in the partition which intersects $A$ is submodular. It may be written as $F(A)=\sum_{j=1}^{m}\min\{|A\cap G_{j}|,1\}$ (submodularity is then immediate from the previous example and the restriction properties outlined previously). Generalizations to all set covers will be studied in §6.3.

Cuts: given an undirected graph $G=(V,E)$ with vertex set $V$, then the cut function for the set $A\subseteq V$ is defined as the number of edges between vertices in $A$ and vertices in $V\backslash A$, i.e., $F(A)=\sum_{(u,v)\in E}|(1_{A})_{u}-(1_{A})_{v}|$. For each $(u,v)\in E$, then the function $|(1_{A})_{u}-(1_{A})_{v}|=2\min\{|A\cap\{u,v\}|,1\}-|A\cap\{u,v\}|$ is submodular (because of operations that preserve submodularity), thus as a sum of submodular functions, it is submodular.

2 Associated polyhedra

(Submodular and base polyhedra) Let $F$ be a submodular function such that $F(\varnothing)=0$. The submodular polyhedron $P(F)$ and the base polyhedron $B(F)$ are defined as:

Proof The first part is trivial, since $t\leqslant s$ implies that for all $A\subseteq V$, $t(A)\leqslant s(A)$. For the second part, given the previous property, we only need to show that $P(F)$ is non-empty, which is true since the constant vector equal to $\min_{A\subseteq V,\ A\neq\varnothing}\frac{F(A)}{|A|}$ belongs to $P(F)$.

3 Polymatroids (non-decreasing submodular functions)

When the submodular function $F$ is also non-decreasing, i.e., when for $A,B\subseteq V$, $A\subseteq B\Rightarrow F(A)\leqslant F(B)$, then the function is often referred to as a polymatroid rank function (see related matroid rank functions in §6.8). For these functions, as shown in Chapter 4, the base polyhedron happens to be included in the positive orthant (the submodular function from Figure 2.1 is thus non-decreasing).

Although, the study of polymatroids may seem too restrictive as many submodular functions of interest are not non-decreasing (such as cuts), polymatroids were historically introduced as the generalization of matroids (which we study in §6.8). Moreover, any submodular function may be transformed to a non-decreasing function by adding a modular function:

Proof Submodularity is immediate since $A\mapsto-s(A)$ is submodular and adding two submodular functions preserves submodularity. Let $A\subseteq V$ and $k\in V\backslash A$. We have:

which is non-negative since $A\subseteq V\backslash\{k\}$ (because of Prop. 2.2). This implies that $G$ is non-decreasing.

The joint properties of submodularity and monotonicity gives rise to a compact characterization of polymatroids , which we now describe:

(Characterization of polymatroids) Let $F$ by a set-function such that $F(\varnothing)=0$. For any $A\subseteq V$, define for $j\in V$, $\rho_{j}(A)=F(A\cup\{j\})-F(A)$ the gain of adding element $j$ to the set $A$. The function $F$ is a polymatroid rank function (i.e., submodular and non-decreasing) if and only if for all $A,B\subseteq V$,

Proof If Eq. (2.1) is true, then, if $B\subseteq A$, $B\backslash A=\varnothing$, and thus $F(B)\leqslant F(A)$, which implies monotonicity. We can then apply Eq. (2.1) to $A$ and $B=A\cup\{j,k\}$ to obtain the condition in Prop. 2.3, hence the submodularity.

We now assume that $F$ is non-decreasing and submodular. For any two subsets $A$ and $B$ of $V$, if we enumerate the set $B\backslash A$ as $\{b_{1},\dots,b_{s}\}$, we have

which is exactly Eq. (2.1). The last proposition notably shows that each submodular function is upper-bounded by a constant plus a modular function, and these upper-bounds may be enforced to be tight at any given $A\subseteq V$. This will be contrasted in §5.1 to the other property shown later that modular lower-bounds also exist (Prop. 3.2).

For polymatroids, we will consider in this monograph two other polyhedra: the positive submodular polyhedron, which we now define by considering the positive part of the submodular polyhedron (sometimes called the independence polyhedron), and then its symmetrized version, which we refer to as the symmetric submodular polyhedron. See examples in two and three dimensions in Figure 2.2 and Figure 2.3.

(Positive submodular polyhedron) Let $F$ be a non-decreasing submodular function such that $F(\varnothing)=0$. The positive submodular polyhedron $P_{+}(F)$ is defined as:

The positive submodular polyhedron is the intersection of the submodular polyhedron $P(F)$ with the positive orthant (see Figure 2.2). Note that if $F$ is not non-decreasing, we may still define the positive submodular polyhedron, which is then equal to the submodular polyhedron $P(G)$ associated with the monotone version $G$ of $F$, i.e., $G(A)=\min_{B\supseteq A}F(B)$ (see Appendix B for more details).

(Symmetric submodular polyhedron) Let $F$ be a non-decreasing submodular function such that $F(\varnothing)=0$. The submodular polyhedron $|P|(F)$ is defined as:

Chapter 3 Lovász Extension

We first consider a set-function $F$ such that $F(\varnothing)=0$, which may not be submodular. Every element of the power set $2^{V}$ may be associated to a vertex of the hypercube $\{0,1\}^{p}$. Namely, a set $A\subseteq V$ may be uniquely identified to the indicator vector $1_{A}$ (see Figure 3.1 and Figure 3.2).

The Lovász extension, which we define in §3.1, allows to draw links between submodular set-functions and regular convex functions, and transfer known results from convex analysis, such as duality. In particular, we prove in this chapter, two key results of submodular analysis and its relationship to convex analysis, namely, (a) that the Lovász extension is the support function of the base polyhedron, with a direct relationship through the “greedy algorithm” (§3.2), and (b) that a set-function is submodular if and only if its Lovász extension is convex (§3.3), with additional links between convex optimization and submodular function minimization.

While there are many additional results relating submodularity and convexity through the analysis of properties of the polyhedra defined in §2.2, these two results are the main building blocks of all the results presented in this monograph (for additional results, see Chapter 4 and ). In particular, in Chapter 5, we show how the Lovász extension may be used in convex continuous problems arising as convex relaxations of problems having mixed combinatorial/discrete structures.

We now define the Lovász extension of any set-function (not necessarily submodular). For several alternative representations and first properties, see Prop. 3.1.

Proof To prove that we actually define a function, one needs to prove that the definitions are independent of the potentially non unique ordering $w_{j_{1}}\geqslant\cdots\geqslant w_{j_{p}}$, which is trivial from the last formulations in Eq. (3.3) and Eq. (3.4). The first and second formulations in Eq. (3.1) and Eq. (3.2) are equivalent (by integration by parts, or Abel summation formula). To show equivalence with Eq. (3.3), one may notice that $z\mapsto F(\{w\geqslant z\})$ is piecewise constant, with value zero for $z>w_{j_{1}}=\max\{w_{1},\dots,w_{p}\}$, and equal to $F(\{j_{1},\dots,j_{k}\})$ for $z\in(w_{j_{k+1}},w_{j_{k}})$, $k=\{1,\dots,p-1\}$, and equal to $F(V)$ for $z<w_{j_{p}}=\min\{w_{1},\dots,w_{p}\}$. What happens at break points is irrelevant for integration. Note that in Eq. (3.3), we may replace the integral $\int_{\min\{w_{1},\dots,w_{p}\}}^{+\infty}$ by $\int_{\min\{w_{1},\dots,w_{p}\}}^{\max\{w_{1},\dots,w_{p}\}}$.

To prove Eq. (3.4) from Eq. (3.3), notice that for $\alpha\leqslant\min\{0,w_{1},\dots,w_{p}\}$, Eq. (3.3) leads to

and we get the result by letting $\alpha$ tend to $-\infty$. Note also that in Eq. (3.4) the integrands are equal to zero for $z$ large enough.

For $p=2$, we may give several representations of the Lovász extension of a set-function $F$. Indeed, from Eq. (3.1), we obtain

which can be written compactly into two different forms:

This allows an illustration of various propositions in this section (in particular Prop. 3.1). See also Figure 3.3 for an illustration. Note that for the cut in the complete graph with two nodes, we have $F(\{1,2\})=0$ and $F(\{1\})=F(\{2\})=1$, leading to $f(w)=|w_{1}-w_{2}|$.

We have seen that for modular functions $F:A\mapsto s(A)$, then $f(w)=s^{\top}w$. For the function $A\mapsto\min\{|A|,1\}=1_{|A|\neq\varnothing}$, then from Eq. (3.1), we have $f(w)=\max_{k\in V}w_{k}$. For the function $F:A\mapsto\sum_{j=1}^{m}\min\{|A\cap G_{j}|,1\}$, that counts elements in a partition, we have $f(w)=\sum_{j=1}^{m}\max_{k\in G_{j}}w_{k}$, which can be obtained directly from Eq. (3.1), or by combining Lovász extensions of sums of set-functions (see property (a) in Prop. 3.1). For cuts, by combining the results for two-dimensional functions, we obtain $f(w)=\sum_{(u,v)\in E}|w_{u}-w_{v}|$.

The following proposition details classical properties of the Choquet integral/Lovász extension. In particular, property (f) below implies that the Lovász extension is equal to the original set-function on $\{0,1\}^{p}$ (which can canonically be identified to $2^{V}$), and hence is indeed an extension of $F$. See an illustration in Figure 3.3 for $p=2$.

Proof Properties (a), (b) and (c) are immediate from Eq. (3.4) and Eq. (3.2). Properties (d), (e) and (f) are straightforward from Eq. (3.2). If $F$ is symmetric, then $F(V)=F(\varnothing)=0$, and thus $f(-w)=\int_{-\infty}^{+\infty}F(\{-w\geqslant z\})dz=\int_{-\infty}^{+\infty}F(\{w\leqslant-z\})dz=\int_{-\infty}^{+\infty}F(\{w\leqslant z\})dz=\int_{-\infty}^{+\infty}F(\{w>z\})dz=f(w)$ (because we may replace strict inequalities by weak inequalities without changing the integral), i.e., $f$ is even. In addition, property (h) is a direct consequence of Eq. (3.2).

Finally, to prove property (i), we simply use property (b) and notice that since all components of $w$ are less than one, then $f(w)=\int_{0}^{1}F(\{w\geqslant z\})dz$, which leads to the desired result.

Note that when the function is a cut function (see §6.2), then the Lovász extension is related to the total variation and property (c) is often referred to as the co-area formula (see and references therein, as well as §6.2).

One may view the definition in Def. 3.1 in a geometric way. We can cut the set $^{p}$ in $p!$ polytopes, as shown in Figure 3.1 and the the bottom plot of Figure 3.2. These small polytopes are parameterized by one of the $p!$ permutations of $p$ elements, i.e., one of the orderings $\{j_{1},\dots,j_{p}\}$, and are defined as the set of $w\in^{p}$ such that $w_{j_{1}}\geqslant\cdots\geqslant w_{j_{p}}$. For a given ordering, the corresponding convex set is the convex hull of the $p\!+\!1$ indicator vectors of sets $A_{k}=\{j_{1},\dots,j_{k}\}$, for $k\in\{0,\dots,p\}$ (with the convention that $A_{0}=\varnothing$), and any $w$ in this polytope may be written as $w=\sum_{k=1}^{p-1}(w_{j_{k}}-w_{j_{k+1}})1_{\{j_{1},\dots,j_{k}\}}+w_{j_{p}}1_{V}+(1-w_{j_{1}})\times 0$ (which is indeed a convex combination), and thus, the definition of $f(w)$ in Eq. (3.2) corresponds exactly to a linear interpolation of the values at the vertices of the polytope $\{w\in^{p},\ w_{j_{1}}\geqslant\cdots\geqslant w_{j_{p}}\}$.

2 Greedy algorithm

The next result relates the Lovász extension with the support functionThe support function of a convex set $K$ is obtained by maximizing linear functions $w^{\top}s$ over $s\in K$, which leads to a convex function of $w$; see definition in Appendix A. of the submodular polyhedron $P(F)$ or the base polyhedron $B(F)$, which are defined in Def. 2.2. This is the basis for many of the theoretical results and algorithms related to submodular functions. Using convex duality, it shows that maximizing a linear function with non-negative coefficients on the submodular polyhedron may be obtained in closed form, by the so-called “greedy algorithm” (see and §6.8 for an intuitive explanation of this denomination in the context of matroids), and the optimal value is equal to the value $f(w)$ of the Lovász extension. Note that otherwise, solving a linear programming problem with $2^{p}-1$ constraints would then be required. This applies to the submodular polyhedron $P(F)$ and to the base polyhedron $B(F)$; note the different assumption regarding the positivity of the components of $w$. See also Prop. 4.2 for a characterization of all maximizers and Prop. 3.4 for similar results for the positive submodular polyhedron $P_{+}(F)$ and Prop. 3.5 for the symmetric submodular polyhedron $|P|(F)$.

Moreover, we can define dual variables $\lambda_{\{j_{1},\dots,j_{k}\}}=w_{j_{k}}-w_{j_{k+1}}$ for $k\in\{1,\dots,p-1\}$ and $\lambda_{V}=w_{j_{p}}$ with all other $\lambda_{A}$’s equal to zero. Then they are all non negative (notably because $w\geqslant 0$), and satisfy the constraint $\forall k\in V,\ w_{k}=\sum_{A\ni k}\lambda_{A}$. Finally, the dual cost function has also value $f(w)$ (from Eq. (3.2)). Thus by strong duality (which holds, because $P(F)$ has a non-empty interior), $s$ is an optimal solution, hence property (a). Note that the maximizer $s$ is not unique in general (see Prop. 4.2 for a description of the set of solutions).

Given the previous proposition that provides a maximizer of linear functions over $B(F)$, we obtain a list of all extreme points of $B(F)$. Note that this also shows that $B(F)$ is a polytope (i.e., it is a compact polyhedron).

(Extreme points of $B(F)$) The set of extreme points is the set of vectors $s$ obtained as the result of the greedy algorithm from Prop. 3.2, for all possible orderings of components of $w$.

We end this section, by simply stating the greedy algorithm for the symmetric and positive submodular polyhedron, whose proofs are similar to the proof of Prop. 3.2 (we define the sign of $a$ as $+1$ if $a>0$, and $-1$ if $a<0$, and zero otherwise; $|w|$ denotes the vector composed of the absolute values of the components of $w$). See also Prop. 4.9 and Prop. 4.10 for a characterization of all maximizers of linear functions.

3 Links between submodularity and convexity

The next proposition draws precise links between convexity and submodularity, by showing that a set-function $F$ is submodular if and only if its Lovász extension $f$ is convex . This is further developed in Prop. 3.7 where it is shown that, when $F$ is submodular, minimizing $F$ on $2^{V}$ (which is equivalent to minimizing $f$ on $\{0,1\}^{p}$ since $f$ is an extension of $F$) and minimizing $f$ on $^{p}$ are equivalent.

(Convexity and submodularity) A set-function $F$ is submodular if and only if its Lovász extension $f$ is convex.

Proof We first assume that $f$ is convex. Let $A,B\subseteq V$. The vector $1_{A\cup B}+1_{A\cap B}=1_{A}+1_{B}$ has components equal to (on $V\backslash(A\cup B)$), $2$ (on $A\cap B$) and $1$ (on $A\Delta B=(A\backslash B)\cup(B\backslash A)$). Therefore, from property (b) of Prop. 3.1, $f(1_{A\cup B}+1_{A\cap B})=\int_{0}^{2}F(1_{\{w\geqslant z\}})dz=\int_{0}^{1}F(A\cup B)dz+\int_{1}^{2}F(A\cap B)dz=F(A\cup B)+F(A\cap B)$. Since $f$ is convex, then by homogeneity, $f(1_{A}+1_{B})\leqslant f(1_{A})+f(1_{B})$, which is equal to $F({A})+F({B})$, and thus $F$ is submodular.

The next proposition completes Prop. 3.6 by showing that minimizing the Lovász extension on $^{p}$ is equivalent to minimizing it on $\{0,1\}^{p}$, and hence to minimizing the set-function $F$ on $2^{V}$ (when $F$ is submodular).

(Minimization of submodular functions) Let $F$ be a submodular function and $f$ its Lovász extension; then $\min_{A\subseteq V}F(A)=\min_{w\in\{0,1\}^{p}}f(w)=\min_{w\in^{p}}f(w)$. Moreover, the set of minimizers of $f(w)$ on $^{p}$ is the convex hull of minimizers of $f$ on $\{0,1\}^{p}$.

Proof Because $f$ is an extension from $\{0,1\}^{p}$ to $^{p}$ (property (f) from Prop. 3.1), we must have $\min_{A\subseteq V}F(A)=\min_{w\in\{0,1\}^{p}}f(w)\geqslant\min_{w\in^{p}}f(w)$. To prove the reverse inequality, we may represent $w\in^{p}$ uniquely through its constant sets and their corresponding values; that is, there exists a unique partition $A_{1},\dots,A_{m}$ of $V$ where $w$ is constant on each $A_{i}$ (equal to $v_{i})$ and $(v_{i})$ is a strictly decreasing sequence (i.e., $v_{1}>\cdots>v_{m}$). From property (h) of Prop. 3.1, we have

where the last inequality is obtained from $v_{1}\leqslant 1$ and $\min_{A\subseteq V}F(A)\leqslant F(\varnothing)=0$. This implies that $\min_{w\in^{p}}f(w)\geqslant\min_{A\subseteq V}F(A)$.

There is equality in the previous sequence of inequalities, if and only if (a) for all $i\in\{1,\dots,m-1\}$, $F(A_{1}\cup\cdots\cup A_{i})=\min_{A\subseteq V}F(A)$, (b) $v_{m}(F(V)-\min_{A\subseteq V}F(A))=0$, and (c) $(v_{1}-1)\min_{A\subseteq V}F(A)=0$. Moreover, we have

Thus, $w$ is the convex hull of the indicator vectors of the sets $A_{1}\cup\cdots\cup A_{j}$, for $j\in\{1,\dots,m-1\}$, of $1_{V}$ (if $v_{m}>0$, i.e., from (b), if $V$ is a minimizer of $F$), and of $0=1_{\varnothing}$ (if $v_{m}<1$, i.e., from (c), if $\varnothing$ is a minimizer of $F$). Therefore, any minimizer $w$ is in the convex hull of indicator vectors of minimizers $A$ of $F$. The converse is true by the convexity of the Lovász extension $f$.

See Chapter 10 for more details on submodular function minimization and the structure of minimizers.

Given that the Lovász extension $f$ of a submodular function is convex, it is natural to study its behavior when used within a convex estimation framework. In Chapter 5, we show that it corresponds to the convex relaxation of imposing some structure on supports or level sets of the vector to be estimated.

Chapter 4 Properties of Associated Polyhedra

We now study in more details submodular and base polyhedra defined in §2.2, as well as the symmetric and positive submodular polyhedra defined in §2.3 for non-decreasing functions. We first review in §4.1 that the support functions may be computed by the greedy algorithm, but now characterize the set of maximizers of linear functions, from which we deduce a detailed facial structure of the base polytope $B(F)$ in §4.2. We then study the positive submodular polyhedron $P_{+}(F)$ and the symmetric submodular polyhedron $|P|(F)$ in §4.3.

The results presented in this chapter are key to understanding precisely the sparsity-inducing effect of the Lovász extension, which we present in details in Chapter 5. Note that §4.2 and §4.3 may be skipped in a first reading.

Proof The only statement left to prove beyond Prop. 3.2 is (c): we just need to notice that, for $j$ such that $w_{j}<0$, we can define $s(\lambda)=s_{0}-\lambda\delta_{j}\in P(F)$ for $\lambda\to+\infty$ and $s_{0}\in P(F)$ and that $w^{\top}s(\lambda)\to+\infty$.

The next proposition shows necessary and sufficient conditions for optimality in the definition of support functions. Note that Prop. 3.2 gave one example obtained from the greedy algorithm, and that we can now characterize all maximizers. Moreover, note that the maximizer is unique only when $w$ has distinct values, and otherwise, the ordering of the components of $w$ is not unique, and hence, the greedy algorithm may have multiple outputs (and all convex combinations of these are also solutions, and are in fact exactly all solutions, as discussed below the proof of Prop. 4.2). The following proposition essentially shows what is exactly needed for $s\in B(F)$ to be a maximizer. In particular, this is done by showing that for some sets $A\subseteq V$, we must have $s(A)=F(A)$; such sets are often said tight for $s\in B(F)$. This proposition is key to deriving optimality conditions for the separable optimization problems that we consider in Chapter 8 and Chapter 9.

Proof We first prove (a). Let $B_{i}=A_{1}\cup\cdots\cup A_{i}$, for $i=1,\dots,m$. From the optimization problems defined in the proof of Prop. 3.2, let $\lambda_{V}=v_{m}>0$, and $\lambda_{B_{i}}=v_{i}-v_{i+1}>0$ for $i<m$, with all other $\lambda_{A}$’s, $A\subseteq V$, equal to zero. Such $\lambda$ is optimal because the dual function is equal to the primal objective $f(w)$.

The last inequality is made possible by the conditions $v_{m}>0$ and $v_{i}>v_{i+1}$. Thus $s$ is optimal, if and only if the primal objective value $s^{\top}w$ is equal to the optimal dual objective value $\sum_{A\subseteq V}\lambda_{A}F(A)$, and thus, if and only if there is equality in all above inequalities, that is, if and only if $S(B_{i})=F(B_{i})$ for all $i\in\{1,\dots,m\}$.

The proof for (b) follows the same arguments, except that we do not need to ensure that $s(V)=F(V)$, since $v_{m}=0$. Similarly, for (c), where $s(V)=F(V)$ is always satisfied for $s\in B(F)$, hence we do not need $v_{m}>0$.

Given $w$ with constant sets $A_{1},\dots,A_{m}$, then the greedy algorithm may be run with $d=\prod_{j=1}^{m}|A_{j}|!$ possible orderings, as the only constraint is that the elements of $A_{j}$ are considered before the elements of $A_{j+1}$ leaving $|A_{j}|!$ possibilities within each set $A_{j}$, $j\in\{1,\dots,m\}$. This leads to as most as many extreme points (note that the corresponding extreme points of $B(F)$ may be equal). Since, by Prop. 3.3, all extreme points of $B(F)$ are obtained by the greedy algorithm, the set of maximizers defined above is the convex hull of the $d$ potential bases defined by the greedy algorithm, i.e., these are extreme points of the corresponding face of $B(F)$ (see §4.2 for a detailed analysis of the facial structure of $B(F)$).

2 Facial structure∗

In this section, we describe the facial structure of the base polyhedron. We first review the relevant concepts for convex polytopes.

We quickly review the main concepts related to convex polytopes. For more details, see . A convex polytope is the convex hull of a finite number of points. It may be also seen as the intersection of finitely many half-spaces (such intersections are referred to as polyhedra and are called polytopes if they are bounded).

In order to study the facial structure, the notion of separable sets is needed; when a set is separable, then the submodular function will decompose a the sum of two submodular functions defined on disjoint subsets. Moreover, any subset $A$ of $V$ may be decomposed uniquely as the disjoint union of inseparable subsets.

(Inseparable set) Let $F$ be a submodular function such that $F(\varnothing)=0$. A set $A\subseteq V$ is said separable if and only there is a set $B\subseteq A$, such that $B\neq\varnothing$, $B\neq A$ and $F(A)=F(B)+F(A\backslash B)$. If $A$ is not separable, $A$ is said inseparable.

(Inseparable sets and function decomposition) Assume $V$ is a separable set for the submodular function $F$, i.e., such that $F(V)=F(A)+F(V\backslash A)$ for a non-trivial subset $A$ of $V$. Then for all $B\subseteq V$, $F(B)=F(B\cap A)+F(B\cap(V\backslash A))$.

Proof If $s\in B(F)$, then we have $F(A)\geqslant s(A)=s(V)-s(V\backslash A)\geqslant F(V)-F(V\backslash A)=F(A)$. This implies that $s(A)=F(A)$ and thus that $B(F)$ can be factorized as $B(F_{A})\times B(F^{A})$ where $F_{A}$ is the restriction of $F$ to $A$ and $F^{A}$ the contraction of $F$ on $A$ (see definition and properties in Appendix B). Indeed, if $s\in B(F)$, then $s_{A}\in B(F_{A})$ because $s(A)=F(A)$, and $s_{V\backslash A}\in B(F^{A})$, because for $B\subseteq V\backslash A$, $s_{V\backslash A}(B)=s(B)=s(A\cup B)-s(A)\leqslant F(A\cup B)-F(A)$. Similarly, if $s\in B(F_{A})\times B(F^{A})$, then for all set $B\subseteq V$, $s(B)=s(A\cap B)+S((V\backslash A)\cap B)\leqslant F(A\cap B)+F(A\cup B)-F(A)\leqslant F(B)$ by submodularity, and $s(A)=F(A)$. This shows that $f(w)=f_{A}(w_{A})+f^{A}(w_{V\backslash A})$.

Given $B\subseteq V$, we apply the last statement to $w=1_{B}$ and $w=1_{B\cap(V\backslash A)}$, to get $F(B)=F(A\cap B)+F(A\cup B)-F(A)$ and $F(B\cap(V\backslash A))=0+F(A\cup B)-F(A)$. We obtain the desired result by taking the difference between the last two equalities.

(Decomposition into inseparable sets) Let $F$ be a submodular function such that $F(\varnothing)=0$. $V$ may be decomposed uniquely as the disjoint union of non-empty inseparable subsets $A_{i}$, $i=1,\dots,m$, such that for all $B\subseteq V$, $F(B)=\sum_{i=1}^{m}F(A_{i}\cap B)$.

Proof The existence of such a decomposition is straightforward while the decomposition of $F(B)$ may be obtained from recursive applications of Prop. 4.3. Given two such decompositions $V=\bigcup_{i=1}^{m}A_{i}=\bigcup_{j=1}^{s}B_{i}$ of $V$, then from Prop. 4.3, we have for all $j$, $F(B_{j})=\sum_{i=1}^{m}F(A_{i}\cap B_{j})$, which implies that the inseparable set $B_{j}$ has to be exactly one of the set $A_{i}$, $i=1,\dots,m$. This implies the unicity. Note that by applying the previous proposition to the restriction of $F$ on any set $A$, any set $A$ may be decomposed uniquely as the disjoint union of inseparable sets.

Among the submodular functions we have considered so far, modular functions of course lead to the decomposition of $V$ into a union of singletons. Moreover, for a partition $V=A_{1}\cup\cdots\cup A_{m}$, and the function that counts elements in a partitions, i.e., $F(A)=\sum_{j=1}^{m}\min\{|A\cap G_{j}|,1\}$, the decomposition of $V$ is, as expected, $V=A_{1}\cup\cdots\cup A_{m}$.

Finally, the notion of inseparable sets allows to give a representation of the submodular polyhedron $P(F)$ as the intersection of a potentially smaller number of half-hyperplanes.

Given the Prop. 4.2 that provides the maximizers of $\max_{s\in B(F)}w^{\top}s$, we may now give necessary and sufficient conditions for characterizing faces of the base polyhedron. We first characterize when the base polyhedron $B(F)$ has non-empty interior within the subspace $\{s(V)=F(V)\}$.

(Full-dimensional base polyhedron) Let $F$ be a submodular function such that $F(\varnothing)=0$. The base polyhedron has non-empty interior in $\{s(V)=F(V)\}$ if and only if $V$ is inseparable.

Proof If $V$ is separable into $A$ and $V\backslash A$, then, by submodularity of $F$, for all $s\in B(F)$, we have $F(V)=s(V)=s(A)+s(V\backslash A)\leqslant F(A)+F(V\backslash A)=F(V)$, which impies that $s(A)=F(A)$ (and also $F(V\backslash A)=s(V\backslash A)$). Therefore the base polyhedron is included in the intersection of two distinct affine hyperplanes, i.e., $B(F)$ does not have non-empty interior in $\{s(V)=F(V)\}$.

To prove the opposite statement, we proceed by contradiction. Since $B(F)$ is defined through supporting hyperplanes, it has non-empty interior in $\{s(V)=F(V)\}$ if it is not contained in any of the supporting hyperplanes. We thus now assume that $B(F)$ is included in $\{s(A)=F(A)\}$, for $A$ a non-empty strict subset of $V$. Then, following the same reasoning than in the proof of Prop. 4.3, $B(F)$ can be factorized as $B(F_{A})\times B(F^{A})$ where $F_{A}$ is the restriction of $F$ to $A$ and $F^{A}$ the contraction of $F$ on $A$ (see definition and properties in Appendix B).

This implies that $f(w)=f_{A}(w_{A})+f^{A}(w_{V\backslash A})$, which implies that $F(V)=F(A)+F(V\backslash A)$, when applied to $w=1_{V\backslash A}$, i.e., $V$ is separable.

Since the facial structure is invariant by translation, as done at the end of §3.1, we may translate $B(F)$ by a certain vector $t\in B(F)$, so that $F$ may be taken to be non-negative and such that $F(V)=0$, which we now assume.

(Faces of the base polyhedron) Let $A_{1}\cup\cdots\cup A_{m}$ be a partition of $V$, such that for all $j\in\{1,\dots,m\}$, $A_{j}$ is inseparable for the function $G_{j}:D\mapsto F(A_{1}\cup\cdots\cup A_{j-1}\cup D)-F(A_{1}\cup\cdots\cup A_{j-1})$ defined on subsets of $A_{j}$. The set of bases $s\in B(F)$ such that for all $j\in\{1,\dots,m\}$, $s(A_{1}\cup\cdots\cup A_{i})=F(A_{1}\cup\cdots\cup A_{i})$ is a face of $B(F)$ with non-empty interior in the intersection of the $m$ hyperplanes (i.e., the affine hull of the face is exactly the intersection of these $m$ hyperplanes). Moreover, all faces of $B(F)$ may be obtained this way.

Proof From Prop. 4.2, all faces may be obtained with supporting hyperplanes of the form $s(A_{1}\cup\cdots\cup A_{i})=F(A_{1}\cup\cdots\cup A_{i})$, $i=1,\dots,m$, for a certain partition $V=A_{1}\cup\cdots\cup A_{m}$. Hovever, among these partitions, only some of them will lead to an affine hull of full dimension $m$. From Prop. 4.6 applied to the submodular function $G_{j}$, this only happens if $G_{j}$ has no separable sets. Note that the corresponding face is then exactly equal to the product of base polyhedra $B(G_{1})\times\cdots\times B(G_{m})$. Note that in the previous proposition, several ordered partitions may lead to the exact same face. The maximal number of full-dimensional faces of $B(F)$ is always less than $2^{p}-2$ (number of non-trivial subsets of $V$), but this number may be reduced in general (see examples in Figure 3.4 for the cut function). Moreover, the number of extreme points may also be large, e.g., $p!$ for the submodular function $A\mapsto-|A|^{2}$ (leading to the permutohedron ).

The faces of $\mathcal{U}$ are obtained from the faces of $B(F)$ through the relationship defined in Prop. 4.2: that is, given a face of $B(F)$, and all the partitions of Prop. 4.7 which lead to it, the corresponding face of $\mathcal{U}$ is the closure of the union of all $w$ that satisfies the level set constraints imposed by the different ordered partitions. As shown in , the different ordered partitions all share the same elements but with a different order, thus inducing a set of partial constraints between the ordering of the $m$ values $w$ is allowed to take.

An important aspect is that the separability criterion in Prop. 4.7 forbids some level sets from being characteristic of a face. For example, for cuts in an undirected graph, we will show in §5.5 that all level sets within a face must be connected components of the graph. When the Lovász extension is used as a constraint for a smooth optimization problem, the solution has to be in one of the faces. Moreover, within this face, all other affine constraints are very unlikely to happen, unless the smooth function has some specific directions of zero gradient (unlikely with random data, for some sharper statements, see ). Thus, when using the Lovász extension as a regularizer, only certain level sets are likely to happen, and in the context of cut functions, only connected sets are allowed, which is one of the justifications behind using the total variation (see more details in §5.5).

3 Positive and symmetric submodular polyhedra∗

In this section, we extend the previous results to the positive and symmetric submodular polyhedra, which were defined in §2.3 for non-decreasing submodular functions. We start with a characterization of such non-decreasing function through the inclusion of the base polyhedron to the postive orthant.

We now assume that the function $F$ is non-decreasing, and consider the positive and symmetric submodular polyhedra $P_{+}(F)$ and $|P|(F)$. These two polyhedra are compact and are thus polytopes. Moreover, $|P|(F)$ is the unit ball of the dual norm $\Omega_{\infty}^{\ast}$ defined in §5.2. This polytope is polar to the unit ball of $\Omega_{\infty}$, and it it thus of interest to characterize the facial structure of the symmetric submodular polyhedronThe facial structure of the positive submodular polyhedron $P_{+}(F)$ will not be covered in this monograph but results are similar to $B(F)$. We will only provide maximizers of linear functions in Prop. 4.9. $|P|(F)$.

Proof The proof follows the same arguments than for Prop. 4.2. Let $d$ be the largest integer such that $v_{d}>0$. We have, with $B_{i}=A_{1}\cup\cdots\cup A_{i}$:

We have equality if and only if the components of $s_{k}$ are zero as soon as the corresponding component of $w_{k}$ is strictly negative (condition (b)), and $F(B_{i})-s(B_{i})=0$ for all $i\in\{1,\dots,d-1\}$ (condition (a)). This proves the desired result.

Before describing the facial structure of $|P|(F)$, we need the notion of stable sets, which are sets which cannot be augmented without strictly increasing the values of $F$.

(Stable sets) A set $A\subseteq V$ is said stable for a submodular function $F$, if $A\subseteq B$ and $A\neq B$ implies that $F(A)<F(B)$.

We can now derive a characterization of the faces of $|P|(F)$ (a similar proposition holds for $P_{+}(F)$).

(Faces of the symmetric submodular polyhedron) Let $C$ be a stable set and let $A_{1}\cup\cdots\cup A_{m}$ be a partition of $C$, such that for all $j\in\{1,\dots,m\}$, $A_{j}$ is inseparable for the function $G_{j}:D\mapsto F(A_{1}\cup\cdots\cup A_{j-1}\cup D)-F(A_{1}\cup\cdots\cup A_{j-1})$ defined on subsets of $A_{j}$, and $\varepsilon\in\{-1,1\}^{C}$. The set of $s\in|P|(F)$ such that for all $j\in\{1,\dots,m\}$, $(\varepsilon\circ s)(A_{1}\cup\cdots\cup A_{i})=F(A_{1}\cup\cdots\cup A_{i})$ is a face of $|P|(F)$ with non-empty interior in the intersection of the $m$ hyperplanes. Moreover, all faces of $|P|(F)$ may be obtained this way.

The last proposition will have interesting consequences for the use of submodular functions for defining sparsity-inducing norms in §5.3. Indeed, the faces of the unit-ball of $\Omega_{\infty}$ are dual to the ones of the dual ball of $\Omega_{\infty}^{\ast}$ (which is exactly $|P|(F)$). As a consequence of Prop. 4.10, the set $C$ in Prop. 4.11 corresponds to the non-zero elements of $w$ in a face of the unit-ball of $\Omega_{\infty}$. This implies that all faces of the unit ball of $\Omega_{\infty}$ will only impose non-zero patterns which are stable sets. See a more precise statement in §5.2.

We end the description of the structure of $|P|(F)$ by noting that among the $2^{p}-1$ constraints of the form $\|s_{A}\|_{1}\leqslant F(A)$ defining it, we may restrict the sets $A$ to be stable and inseparable. Indeed, if $\|s_{A}\|_{1}\leqslant F(A)$ for all stable and inseparable sets $A$, then if a set $B$ is not stable, then we may consider the smallest enclosing stable set (these are stable by intersection, hence the possibility of defining such a smallest enclosing stable set) $C$, and we have $\|s_{B}\|_{1}\leqslant\|s_{C}\|_{1}$, and $F(B)=F(C)$, which implies $\|s_{B}\|_{1}\leqslant F(B)$. We thus need to show that $\|s_{C}\|_{1}\leqslant F(C)$ only for stable sets $C$. If the set $C$ is separable into $C=D_{1}\cup\cdots\cup D_{m}$, where all $D_{i}$, $i=1,\dots,m$ are separable (from Prop. 4.4), they must all be stable (otherwise $C$ would not be), and thus we have $\|s_{C}\|_{1}=\|s_{D_{1}}\|_{1}+\cdots+\|s_{D_{m}}\|_{1}\leqslant F(D_{1})+\cdots+F(D_{m})=F(C)$.

Chapter 5 Convex Relaxation of Submodular Penalties

In this chapter, we show how submodular functions and their Lovász extensions are intimately related to various relaxations of combinatorial optimization problems, or problems with a joint discrete and continuous structure.

In particular, we present in §5.1 the theory of convex and concave closures of set-functions: these can be defined for any set-functions and allow convex reformulations of the minimization and maximization of set-functions. It turns out that for submodular functions, the convex closure is exactly the Lovász extension, which can be computed in closed form, which is typically not the case for non-submodular set-functions.

In §5.2, we introduce the concept of structured sparsity, which corresponds to situations where a vector $w$ has to be estimated, typically a signal or the linear representation of a prediction, and structural assumptions are imposed on $w$. In §5.3 and §5.4, we consider imposing that $w$ has many zero components, but with the additional constraint that some supports are favored. A submodular function will encode that desired behavior. In §5.5, we consider a similar approach, but on the level sets of $w$.

In this section, given a non-convex function $g$, we will consider several times the task of computing its convex envelope $f$, i.e., its largest convex lower-bound. As explained in Appendix A, a systematic way to obtain $f$ is to compute the Fenchel bi-conjugate.

This implies that the domain of $f$ is $^{p}$ (i.e., $f(w)=+\infty$ for $w\notin^{p}$). Moreover, since the vectors $1_{A}$, for $A\subseteq V$ are extreme points of $^{p}$, for any $B\subseteq V$, the only way to express $1_{B}$ as a combination of indicator vectors $1_{A}$ is by having $\lambda_{B}=1$ and all other values $\lambda_{A}$ equal to zero. Thus $f(1_{B})=F(B)$. That is, the convex closure is always tight at each $1_{A}$, and $f$ is an extension of $F$ from $\{0,1\}^{p}$ to $^{p}$. This property is independent from submodularity.

We may relate the minimization of $F$ to the minimization of its convex closure:

which implies that minimizing the convex closure of $F$ on $^{p}$ is equivalent to minimizing $F$ on $2^{V}$. See an illustration in Figure 5.1.

For submodular functions, it simply turns out that the convex closure is equal to the Lovász extension. Hence, it is computable in closed form and amenable to optimization. This fact is in fact exactly shown in the proof of Prop. 3.2.

The concave closure is defined in a similar way, and can be seen to be the opposite of the convex closure of $-F$. Note that it cannot be computed in general as this would mean that there are polynomial-time algorithms for submodular function maximization . However, following Prop. 2.6 and its discussion in §2.3, one can always find “constant plus modular” upper-bounds which are tight at any given vertex of the hypercube (but this cannot be done at any interior point in general).

2 Structured sparsity

The concept of parsimony is central in many scientific domains. In the context of statistics, signal processing or machine learning, it takes the form of variable or feature selection problems.

Sparse models are commonly used in two situations: First, to make the model or the prediction more interpretable or cheaper to use, i.e., even if the underlying problem might not admit sparse solutions, one looks for the best sparse approximation. Second, sparsity can also be used given prior knowledge that the model should be sparse. In these two situations, reducing parsimony to finding models with low cardinality of their support turns out to be limiting, and structured parsimony has emerged as a fruitful practical extension, with applications to image processing, text processing, bioinformatics or audio processing (see, e.g., , a review in and Chapter 6 for various examples).

3 Convex relaxation of combinatorial penalty

We are thus interested in an optimization problem of the form

By definition of the Fenchel conjugacy and of $g$, we have :

Note that the assumption of submodularity is key to applying Prop. 3.7 (i.e., equivalence between maximization on the vertices and on the full hypercube).

Thus, for all $w$ such that $\|w\|_{\infty}\leqslant 1$,

By strong convex duality (which applies because Slater’s condition is satisfied), we can invert the “min” and “max” operations and get:

Since $F$ is assumed non-decreasing, the Lovász extension $f$ is non-decreasing with respect to each of its components, which implies that $\min_{\delta\in^{p},\ \delta\geqslant|w|}f(\delta)=f(|w|)$, which leads to the desired result. Note that an alternative proof may be found in §5.4. The previous proposition provides a relationship between combinatorial optimization problems—involving functions of the form $w\mapsto F({\rm Supp}(w))$—and convex optimization problems involving the Lovász extension. A desirable behavior of a convex relaxation is that some of the properties of the original problem are preserved. In this monograph, we will focus mostly on the allowed set of sparsity patterns (see below). For more details about theroretical guarantees and applications of submodular functions to structured sparsity, see . In Chapter 6, we consider several examples of submodular functions and present when appropriate how they translate to sparsity-inducing norms.

For the function $F(A)=\min\{|A|,1\}$, then we have $f(w)=\max\{w_{1},\dots,w_{p}\}$ and thus $\Omega_{\infty}(w)=\|w\|_{\infty}$. This norm is not sparsity-promoting and this is intuively natural since the set-function it corresponds to is constant for all non-empty sets.

We now study in more details the properties of the function $\Omega_{\infty}:w\mapsto f(|w|)$ defined above through a relaxation argument. We first give conditions under which it is a norm, and derive the dual norm.

(Norm and dual norm) Let $F$ be a submodular function such that $F(\varnothing)=0$ and $F$ is non-decreasing. The function $\Omega_{\infty}:w\mapsto f(|w|)$ is a norm if and only if the values of $F$ on all singletons is strictly positive. Then, the dual norm is equal to $\Omega_{\infty}^{\ast}(s)=\max_{A\subseteq V,\ A\neq\varnothing}\frac{|s|(A)}{F(A)}=\max_{A\subseteq V,\ A\neq\varnothing}\frac{\|s_{A}\|_{1}}{F(A)}$.