Multilinear Extensions for Submodular Maximization

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

Version 1 of 2113 papers138 conceptsfrozen 2026-10-04

In combinatorial optimization, we often face a "discrete bottleneck." When choosing a set of items—whether they are sensors to place in a city, influencers for a marketing campaign, or products for a recommendation list—the search space is massive and jagged. Traditional algorithms like the "greedy" approach work well for simple cases, but they struggle with complex constraints, massive parallelism, or when the objective function is hidden inside a machine learning pipeline.

To solve this, researchers have developed a powerful strategy: lifting discrete problems into a continuous space, solving them with calculus, and then rounding the results back to a discrete set. The mathematical bridge that makes this possible is the multilinear extension.

The Bridge Between Discrete and Continuous

A submodular function $f(S)$ is a set function that captures the law of diminishing returns: adding an element to a small set helps more than adding it to a large one. While $f(S)$ is only defined for discrete sets, the multilinear extension $F(x)$ extends this function to the entire continuous hypercube $[0, 1]^n$.

As Lin Chen, Hamed Hassani, and Amin Karbasi describe in Black Box Submodular Maximization: Discrete and Continuous Settings, the multilinear extension represents the expected value of the function if we were to pick each element $i$ independently with probability $x_i$.

This transformation is transformative because $F(x)$ is smooth and differentiable. It turns a combinatorial search into a landscape where we can follow gradients. Even when the function is a "black box," we can estimate these gradients through sampling, as shown by Lin Chen and colleagues in their 2019 work.

Optimization via Continuous Greedy

Once we have a continuous surface, we can use the Continuous Greedy algorithm. Instead of making a hard choice to pick an item, we move a small distance in the direction of the gradient—the direction that increases our expected value the most.

This approach is particularly powerful for handling complex constraints. For example, in Parallelizing greedy for submodular set function maximization in matroids and beyond, Chandra Chekuri and Kent Quanrud show that by lifting the problem, we can update multiple elements simultaneously. This unlocks massive parallelism that is impossible with sequential greedy selection.

Furthermore, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi demonstrated in Stochastic Conditional Gradient Methods that we can use stochastic gradient methods (like Frank-Wolfe) to achieve the optimal $(1-1/e)$ approximation guarantee even for massive, high-dimensional problems.

Rounding Without Loss

The final challenge is the "return trip": converting a fractional vector $x$ (where an item might be "0.7 chosen") back into a discrete set $S$ (where it is either 0 or 1).

Simple rounding often breaks constraints or destroys the objective value. To prevent this, researchers use specialized techniques:

Expanding the Frontier

The multilinear framework has proven remarkably flexible, extending far beyond simple set selection:

  1. Decision-Focused Learning: Bryan Wilder, Bistra Dilkina, and Milind Tambe show in Melding the Data-Decisions Pipeline that because the multilinear extension is differentiable, we can backpropagate through the optimization step. This allows neural networks to be trained specifically to produce better combinatorial decisions.
  2. $k$-Submodularity: For problems where items can have multiple states (not just "in" or "out"), Huanjian Zhou and Baoxiang Wang developed a novel multilinear extension that achieves asymptotically optimal ratios for these multi-state problems.
  3. Fairness and Privacy: By operating in a continuous domain, researchers like L. Elisa Celis and Nisheeth Vishnoi can incorporate fairness constraints or differential privacy mechanisms more smoothly than in discrete spaces.

By treating discrete sets as probabilistic expectations, the multilinear extension allows us to navigate the "all-or-nothing" world of combinatorial optimization with the precision and scalability of continuous calculus.

Papers in this version

Showing 60 of 113 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_multilinear_extension_77d87df3,
  title = {multilinear extension},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multilinear-extension/rdr_77d87df3cdb14c1ab0d90da80d9f2bb9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_multilinear_extensions_for_submodular_ma_77d87df3_v1,
  title = {Multilinear Extensions for Submodular Maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multilinear-extensions-for-submodular-maximization/rdr_77d87df3cdb14c1ab0d90da80d9f2bb9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}