In machine learning and combinatorial optimization, we frequently encounter problems defined over discrete sets. We might want to select a optimal subset of features, segment an image by choosing a subset of pixels, or find a dense community within a social network.
Many of these set functions exhibit a natural property known as submodularity, often described as the discrete analogue of convexity. A set function $F: 2^V \to \mathbb{R}$ is submodular if it satisfies the law of diminishing returns: adding an element to a small set provides a greater or equal incremental benefit than adding that same element to a larger superset.
While submodular functions are discrete, we often want to optimize them using the powerful tools of continuous mathematics—such as gradient descent, proximal operators, or backpropagation. The Lovász extension serves as the definitive mathematical bridge between these two worlds. It transforms a discrete function defined on the vertices of a hypercube into a continuous, piecewise-linear function defined over the entire solid hypercube, preserving convexity in the process.
The Intuition Behind the Extension
To understand why the Lovász extension works, let us first visualize the discrete domain. If we have a ground set of $n$ elements, every subset can be represented as a binary vector in $\{0,1\}^n$. A set function $F$ simply assigns a value to each of these $n$-dimensional corners.
The goal of a continuous relaxation is to extend this function to fractional vectors $x \in [0,1]^n$. A naive interpolation might destroy the structural properties of $F$. The Lovász extension succeeds because it interpolates by sorting the coordinates of $x$.
Suppose we have a vector $x = (0.8, 0.3, 0.5)$. To evaluate its Lovász extension $f(x)$, we perform the following steps:
- Sort the components in descending order: $x_1 (0.8) \ge x_3 (0.5) \ge x_2 (0.3)$.
- Generate a nested chain of sets based on this ordering, starting from the empty set and adding elements one by one:
- $S_0 = \emptyset$
- $S_1 = \{1\}$
- $S_2 = \{1, 3\}$
- $S_3 = \{1, 3, 2\}$
- Compute a weighted sum of the discrete function values on these sets, where the weights correspond to the differences between consecutive sorted coordinates: $$f(x) = (0.8 - 0.5)F(S_1) + (0.5 - 0.3)F(S_2) + 0.3F(S_3)$$
More formally, for any sorted vector where $x_{\pi(1)} \ge x_{\pi(2)} \ge \dots \ge x_{\pi(n)}$, the Lovász extension is defined as:
$$f(x) = \sum_{i=1}^{n-1} (x_{\pi(i)} - x_{\pi(i+1)}) F(S_i) + x_{\pi(n)} F(S_n)$$
The profound insight of this construction is its relationship with convexity: a discrete set function $F$ is submodular if and only if its Lovász extension $f(x)$ is convex. This equivalence means that minimizing a discrete submodular function is mathematically identical to minimizing its continuous Lovász extension over the unit hypercube.
Designing Structured Sparsity Norms
One of the earliest major applications of this bridge in machine learning was in regularized regression. While the standard $\ell_1$-norm (Lasso) induces unstructured sparsity, we often possess prior knowledge dictating that features should be selected in groups, hierarchies, or grids.
Bach et al. demonstrated that if we define a submodular function $F$ that penalizes unwanted combinations of features, its Lovász extension acts as a continuous, convex regularization penalty. For example, if $F$ measures the "boundary" of selected features on a grid, its extension penalizes scattered, noisy feature selection, enforcing spatial cohesion.
Furthermore, the authors showed that computing the proximal operator for these structured sparsity norms is equivalent to solving a discrete submodular function minimization problem. This allows continuous optimization frameworks to seamlessly leverage discrete algorithms like the minimum-norm-point algorithm.
Online Learning and Subgradient Descent
In online optimization, a decision-maker must repeatedly choose subsets of items under changing cost functions. Doing this purely in a discrete space often leads to intractable computational overhead or poor theoretical guarantees.
By lifting the problem to a continuous domain, Hazan et al. and Jegelka et al. developed efficient algorithms for Online Submodular Minimization. Because the Lovász extension is convex and piecewise-linear, its subgradients can be computed efficiently by sorting the vector coordinates.
The online learner can run standard continuous subgradient descent on the Lovász extension within the continuous hypercube $[0,1]^n$. At each step, the fractional vector is mapped back to a discrete set via randomized rounding or thresholding. This continuous detour yields polynomial regret bounds that are otherwise incredibly difficult to prove in purely combinatorial settings.
Even when the evaluations are corrupted by noise, Ito demonstrated that stochastic subgradient descent on the Lovász extension achieves optimal error rates, proving that exact gradient computations are not required for robust combinatorial optimization.
Direct Optimization of Discrete Metrics in Deep Learning
Modern deep neural networks are typically trained using smooth, pixel-wise loss functions like cross-entropy. However, computer vision tasks are ultimately evaluated using discrete, scale-invariant set metrics such as the Jaccard Index or Intersection-over-Union (IoU). Because these metrics require thresholding predictions into discrete sets, they are non-differentiable and cannot be optimized directly via backpropagation.
The authors of The Lovász-Softmax Loss resolved this mismatch by framing the alignment error of a segmentation mask as a submodular set function. By deriving its Lovász extension, they created a continuous, convex surrogate—the Lovász-Softmax loss. This loss matches the true discrete IoU metric perfectly at the vertices of the hypercube while remaining fully differentiable everywhere inside it, allowing neural networks to optimize for IoU directly during training.
Beyond Pure Submodularity: Difference of Submodular Functions
Many real-world problems do not fit perfectly into the mold of pure submodularity. Instead, they involve a mixture of cooperative benefits and competitive costs, which can be modeled as the Difference of Submodular (DS) functions.
To optimize these highly non-convex discrete functions, El Halabi et al. extended the continuous relaxation paradigm. By applying the Lovász extension to each submodular component independently, they transformed a discrete DS problem into a continuous Difference of Convex (DC) program:
$$\min_{S \subseteq V} [F(S) - G(S)] \implies \min_{x \in [0,1]^n} [f(x) - g(x)]$$
This mapping allows practitioners to deploy powerful continuous optimization tools, such as the Difference of Convex Functions Algorithm (DCA), to find high-quality local minima for complex combinatorial tasks like speech feature selection and network structure discovery.
By translating discrete combinatorial structures into continuous geometric landscapes, the Lovász extension enables a unified approach to optimization, bridging the gap between discrete algorithms and continuous gradient-based learning.
Key Foundational Work
Continuous limits of discrete perimeters (2009) — contributed 3 concept elements to this direction.
Structured sparsity-inducing norms through submodular functions (2010) — contributed 3 concept elements to this direction.
Convex Analysis and Optimization with Submodular Functions: a Tutorial (2010) — contributed 2 concept elements to this direction.