Robust Submodular Maximization under Stochastic Noise

This direction is split into other directions: noise-robust submodular optimization. Its last version stays readable and citable here.

Version 1 of 196 papers162 conceptsfrozen 2026-10-04

Submodular optimization is the mathematical backbone of "diminishing returns." It powers everything from selecting the most diverse set of images to placing sensors in a city or identifying influential nodes in a social network. In an ideal world, we have a perfect "oracle" that tells us exactly how much value a new item adds to our current set. In reality, this oracle is often a noisy simulation, a finite sample, or a messy human estimate.

Standard greedy algorithms, which are famously near-optimal for submodular functions, are surprisingly fragile. A single noisy evaluation early in the process can lead to a catastrophic choice that ruins the entire solution. Recent research has focused on making these algorithms robust, proving that we can recover near-optimal performance even when our data is corrupted.

The Fragility of Sequential Selection

The classic greedy algorithm works by repeatedly picking the item that provides the largest marginal gain. As Yaron Singer points out in Submodular Optimization under Noise, this sequential nature is a liability. If the noise is adversarial—meaning it specifically tries to trick the algorithm—the approximation ratio can drop from the optimal $1 - 1/e$ to zero.

The problem is that greedy algorithms are "myopic." They cannot backtrack. If a noisy oracle overestimates the value of a mediocre item, the algorithm commits to it, and the submodular property of diminishing returns ensures that this mistake haunts every subsequent choice. This sensitivity is particularly acute in fields like Influence Maximization, where Edith Cohen and Haim Kaplan note that evaluating the reach of a seed set is #P-hard, forcing us to rely on noisy random simulations Influence Maximization with Few Simulations.

Smoothing the Oracle

To combat random noise, researchers have introduced the concept of smoothing. Instead of trusting a single noisy query $f(S)$, algorithms like SMOOTH-GREEDY optimize a surrogate function. This surrogate averages evaluations over a "neighborhood" of related sets.

As Yaron Singer demonstrates in Submodular Optimization under Noise, this averaging filters out stochastic errors, allowing the underlying submodular structure to emerge. By optimizing this smoothed surrogate, we can recover the $1 - 1/e$ approximation ratio even under generalized exponential tail noise. Essentially, smoothing transforms a jagged, noisy landscape into a manageable, approximately submodular one.

Quantifying "Almost" Submodular

In many real-world applications, the objective function isn't just noisy—it isn't perfectly submodular to begin with. Researchers have developed structural relaxations to bridge this gap:

Algorithmic Resilience: Beyond Simple Greedy

If the standard greedy approach is too fragile, what are the alternatives?

  1. Local Search: Lingxiao Huang and Yuyi Wang prove in Efficient Submodular Optimization under Noise: Local Search is Robust that local search is inherently more robust than greedy selection. Because local search can swap items in and out of the set, it can "correct" for earlier mistakes caused by noisy evaluations.
  2. Bandit Feedback: When we only learn the value of a set after picking it, we face a "bandit" problem. Artin Tajdini and Lalit K Jain introduced Sub-UCB in Minimax Optimal Submodular Optimization with Bandit Feedback. This algorithm balances greedy exploration with combinatorial search, explicitly accounting for cumulative noise during the selection process.
  3. Stochastic Gradients: For continuous versions of these problems, Aryan Mokhtari and Hamed Hassani show that combining gradient averaging with Frank-Wolfe methods can achieve tight approximation ratios even when only noisy, stochastic gradients are available Stochastic Conditional Gradient Methods.

Why It Works: The Power of Diminishing Returns

The recurring theme across these 84 papers is that the structure of diminishing returns is fundamentally robust. While noise can obscure the exact marginal gain of an item, it rarely flips the overall trend of the function.

As Andreas Krause and Daniel Golovin established in their work on adaptive submodularity Adaptive Submodular Optimization under Matroid Constraints, as long as our selection is "approximately" good at each step, the global error remains bounded. Whether through smoothing, local search, or concentration-based surrogates Benjamin Doerr, the goal is the same: to prevent noise from masking the core mathematical property that makes these problems solvable in the first place.

Papers in this version

Showing 60 of 96 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_robust_submodular_maximization_under_sto_e0269579,
  title = {Robust Submodular Maximization under Stochastic Noise},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-submodular-maximization-under-stochastic-noise/rdr_e0269579181a4191b2285c4245b804a6},
  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_robust_submodular_maximization_under_sto_e0269579_v1,
  title = {Robust Submodular Maximization under Stochastic Noise},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-submodular-maximization-under-stochastic-noise/rdr_e0269579181a4191b2285c4245b804a6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}