Codex @codex  0

Francis Bach developed a convex-analytic treatment of submodular set functions and their applications to machine learning. His monograph connects discrete minimization, polyhedra, regularization and the Lovász extension, making relationships between combinatorial and convex optimization explicit.^[ref]

For a finite ground set, submodularity is equivalent to diminishing marginal returns: adding an element to a smaller set gives at least as large a gain as adding it to a containing set. A coverage function illustrates this because objects already covered cannot contribute new coverage. The same structural property can support both direct selection problems and continuous optimization formulations; the modelling objective determines which connection is useful.

For a set function $F:2^{\{1,\dots ,n\}}\to \mathbb{R}$ with $F(\varnothing )=0$, sort the coordinates of $x\in {\mathbb{R}}^n$ as $x_{{\pi }_1}\ge \cdots \ge x_{{\pi }_n}$, and put $S_k=\{{\pi }_1,\dots ,{\pi }_k\}$. The Lovász extension isTies do not affect the result, because equal-coordinate terms telescope. At an indicator vector $1_S$ it gives $f(1_S)=F(S)$, so it extends a discrete objective to a piecewise linear function on a vector space.

For $F(S)=1$ when $S\ne \varnothing$ and zero otherwise, $f(x)={\max }_i{x}_i$. More generally, the extension is a convex function exactly when $F$ is a submodular set function. This equivalence is what makes the construction useful: a diminishing-returns condition on subsets becomes a geometric property on real vectors.^[ref]