Continuous Convex Relaxations for Discrete Submodular Optimization

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2163 papers221 conceptsfrozen 2026-10-04

In the landscape of optimization, there is a long-standing divide between the continuous and the discrete. Continuous optimization enjoys the luxury of gradients, duality, and smooth landscapes, while discrete optimization often feels like a combinatorial maze where a single step can lead to an exponential explosion of possibilities.

However, a specific class of discrete functions—submodular functions—possesses a property known as "diminishing returns" that mirrors the geometry of convexity. This shared DNA allows us to build a mathematical bridge called the Lovász extension, which transforms discrete set problems into continuous convex ones. This bridge enables researchers to solve notoriously difficult combinatorial tasks using the robust toolkit of continuous calculus.

The Discrete Analog of Convexity

Submodularity is often described as the "convex functions of the discrete world" Francis Bach. To understand why, consider a set function $f$ that assigns a value to every possible subset of a collection of items. If adding an item to a small set provides more value than adding that same item to a larger set, the function is submodular.

This property of diminishing returns is the discrete equivalent of a non-increasing derivative in continuous functions. As Jeff Bilmes notes, this structure is what makes massive discrete tasks—like data summarization and feature selection—computationally tractable.

The Lovász Extension: A Geometric Bridge

The core mechanism connecting these two worlds is the Lovász extension. Imagine a discrete set function defined only at the corners of a unit hypercube (where each dimension represents the presence or absence of an element). The Lovász extension "fills in" the interior of the hypercube, creating a continuous interpolation Learning with Submodular Functions: A Convex Optimization Perspective.

The magic of this transformation lies in a fundamental theorem: a discrete set function is submodular if and only if its Lovász extension is convex Convex Analysis and Optimization with Submodular Functions: a Tutorial.

This equivalence changes the rules of the game. Instead of searching through $2^n$ possible subsets, we can now minimize a continuous, convex function over a solid cube. Because the extension is convex, any local minimum we find is guaranteed to be a global minimum, and that minimum will correspond to an optimal discrete set.

Why the Continuous Perspective Works

By mapping discrete sets to a continuous domain, we unlock several powerful optimization strategies that were previously unavailable:

Once a discrete problem is relaxed into the continuous domain, we can use subgradients to navigate the landscape. Tianyi Lin and Michael Jordan demonstrate that even approximate subgradients derived from the Lovász extension are sufficient for achieving "no-regret" performance in online learning settings Online Nonsubmodular Minimization with Delayed Costs.

2. Smoothing for Speed

The Lovász extension is typically non-smooth (piecewise linear), which can slow down optimization. However, by applying smoothing techniques to the extension, researchers like Peter Stobbe and Andreas Krause have shown that we can use accelerated gradient methods to achieve linear convergence rates, making submodular minimization practical for large-scale machine learning Efficient Minimization of Decomposable Submodular Functions.

3. Differentiable Discrete Layers

Perhaps the most modern application of this idea is the integration of discrete optimization directly into neural networks. By treating a submodular minimization problem as a differentiable layer, Josip Djolonga and Andreas Krause enable end-to-end training of models that learn to pick the best "set" of features or data points as part of their internal logic Differentiable Learning of Submodular Functions.

Beyond Simple Submodularity

The power of continuous relaxations extends even to problems that aren't perfectly submodular.

  • Nonsubmodular Functions: In cases where the "diminishing returns" property is absent, the Lovász extension still provides a differentiable bridge, allowing for iterative gradient descent in online settings Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting.
  • L-natural Convexity: For problems defined on integer lattices rather than binary sets, the Lovász extension can be applied within each unit hypercube to create a piecewise linear convex extension, generalizing submodular minimization to broader domains Online L♮-Convex Minimization.
  • Difference of Submodular (DS) Functions: Just as any continuous function can be expressed as the difference of two convex functions, many discrete functions are the difference of two submodular ones. Marwa El Halabi shows that the Lovász extension allows us to apply "Difference of Convex" (DC) programming to these complex discrete objectives Difference of submodular minimization via DC programming.

Summary

The research direction across these 129 papers suggests that the boundary between discrete and continuous optimization is more of a permeable membrane than a wall. By using the Lovász extension to lift discrete sets into continuous space, we don't just find a way to approximate solutions—we inherit the entire theoretical and algorithmic infrastructure of convex analysis to solve combinatorial problems with provable guarantees.

Papers in this version

Showing 60 of 163 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 93 papers
  2. Version 1 · 2026-10-04 · 163 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_lovasz_extension_d793c336,
  title = {Lovász extension},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lovasz-extension/rdr_d793c336a28c4e31909f17f3b26533bb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_continuous_convex_relaxations_for_discre_d793c336_v1,
  title = {Continuous Convex Relaxations for Discrete Submodular Optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-convex-relaxations-for-discrete-submodular-optimization/rdr_d793c336a28c4e31909f17f3b26533bb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}