Continuous and Stochastic Submodular Maximization

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

Version 1 of 2178 papers187 conceptsfrozen 2026-10-04

Submodularity is often described as the discrete analogue of concavity. It captures the intuitive notion of diminishing returns: the marginal gain of adding an element to a set decreases as the set grows. Formally, a set function $f: 2^V \to \mathbb{R}$ is submodular if for every $A \subseteq B \subseteq V$ and $x \notin B$, $f(A \cup \{x\}) - f(A) \geq f(B \cup \{x\}) - f(B)$.

While classical submodular optimization focused on discrete sets and monotone functions (where adding elements never decreases the value), modern research has shifted toward continuous relaxations and non-monotone objectives. This shift allows researchers to apply the powerful toolkit of stochastic gradient descent to massive, real-world combinatorial problems.

Bridging Discrete and Continuous Worlds

The primary challenge in discrete optimization is that we cannot use gradients. To solve this, researchers use the multilinear extension, which lifts a discrete function $f$ into a continuous function $F: [0, 1]^n \to \mathbb{R}$. This extension allows us to treat subset selection as a continuous problem where we optimize coordinates in a unit cube.

Mohammad Reza Karimi, Hamed Hassani, and Andreas Krause demonstrated in Stochastic Submodular Maximization: The Case of Coverage Functions that large-scale problems like influence maximization can be solved using stochastic gradient methods. By using unbiased estimates of the gradient of the multilinear extension, they achieved massive speedups over traditional greedy algorithms without losing theoretical guarantees.

This continuous perspective is further refined by the concept of DR-submodularity (Diminishing Returns submodularity). A continuous function is DR-submodular if it is coordinate-wise concave, meaning that increasing one variable reduces the marginal gain of increasing it further. Lin Chen and Amin Karbasi have shown that for these functions, algorithms like Meta-Frank-Wolfe can achieve optimal regret bounds in online settings, as detailed in Online Continuous Submodular Maximization.

The Challenge of Non-Monotonicity

In many real-world scenarios, "more" is not always "better." A summary that is too long becomes unreadable; a sensor network with too many nodes may suffer from interference. These are non-monotone submodular functions, where the objective value can decrease as elements are added.

Non-monotonicity breaks the standard greedy algorithm. If adding an element $x$ currently increases the value but eventually leads to a massive decrease, a greedy agent will be "tricked" into a local optimum. To counter this, Christopher Harshaw proposed a "distorted" greedy approach in Submodular Maximization beyond Non-negativity, which weights marginal gains differently to account for potential future losses.

In the continuous domain, Moran Feldman and Amin Karbasi pushed these boundaries in Continuous Submodular Maximization: Beyond DR-Submodularity, providing the first constant-factor approximations for monotone functions that don't even satisfy the DR property. For non-monotone cases, researchers like Yiyang Lu and Vaneet Aggarwal introduced upper-linearizability, a technique that reparameterizes non-monotone DR-submodular problems so they can be solved as if they were linear, as explored in Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization.

Scaling to Streams and Networks

As datasets grow, we can no longer assume that all data fits in memory or resides on a single machine. This has led to the development of streaming and distributed submodular maximization.

  1. Streaming: Algorithms must make one-pass decisions with limited memory. Alina Ene and Huy Nguyen developed primal-dual frameworks for $k$-submodular functions in Streaming Algorithm for Monotone k-Submodular Maximization, matching the performance of much slower offline algorithms.
  2. Distributed: Baharan Mirzasoleiman and Andreas Krause introduced GreeDi in Distributed Submodular Maximization. The intuition is simple: partition the data, run greedy selection locally, and then merge the results. Surprisingly, this "local-to-global" approach maintains strong theoretical guarantees for submodular functions due to their inherent structure.

Learning the Objective

Finally, what if the submodular function itself is unknown? Traditional optimization assumes the function $f$ is given as a black box. Abir De and Soumen Chakrabarti addressed this in Neural Estimation of Submodular Functions by creating FLEXSUBNET, a neural architecture that learns submodular functions from data. By using a recursive structure and differentiable integration, they enable "differentiable subset selection," allowing submodular optimization to be embedded directly into deep learning pipelines.

This evolution—from discrete to continuous, monotone to non-monotone, and fixed to learned—represents a unified effort to make the principle of diminishing returns a first-class citizen in large-scale machine learning.

Papers in this version

Showing 60 of 178 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_non_monotone_submodular_optimization_91061038,
  title = {non-monotone submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-monotone-submodular-optimization/rdr_91061038619f41839fa2b17caa79b297},
  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_continuous_and_stochastic_submodular_max_91061038_v1,
  title = {Continuous and Stochastic Submodular Maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/continuous-and-stochastic-submodular-maximization/rdr_91061038619f41839fa2b17caa79b297/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}