Adaptive Submodular Optimization

44 concepts32 papers1 proposal

Imagine you are a doctor diagnosing a patient, a robot mapping an unknown environment, or an active learning algorithm selecting images to label for a deep neural network. In each case, you face a sequential decision-making problem under uncertainty. You cannot simply select a fixed batch of actions at the start; the most informative next step depends entirely on the outcomes of your previous observations.

To find the absolute optimal sequence of actions, you would theoretically need to construct a massive decision tree that explores every possible action and every subsequent observation outcome. Because this tree grows exponentially, finding the exact optimal policy is computationally intractable.

Faced with this complexity, practitioners often resort to a greedy policy: simply select the single action that looks best right now. While greedy strategies can fail spectacularly on arbitrary sequential problems by falling into short-sighted traps, a powerful mathematical framework known as adaptive submodularity guarantees that a simple greedy policy will perform near-optimally.

The Intuition of Diminishing Returns

To understand why a greedy policy can succeed sequentially, we must first look at the static concept of submodularity, which formalizes the law of diminishing returns. In a static setting, a set function is submodular if adding an item to a small set provides a larger marginal benefit than adding that same item to a larger, more comprehensive set.

In sequential decision-making, however, we do not just accumulate items; we accumulate a history of observations (actions paired with their observed outcomes). As formalized by Krause et al. in their foundational paper, Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization, an objective function satisfies adaptive submodularity if the expected marginal gain of an action decreases as the history of observations grows.

Crucially, the authors demonstrate that this diminishing returns property must hold in expectation over the posterior distribution of outcomes given the current history, rather than just in individual, isolated states. When this condition is met, information gathered early on can only reduce or maintain—but never increase—the expected utility of future actions. This prevents the greedy algorithm from making choices that seem mediocre now but suddenly become hyper-valuable later, ensuring that short-sighted choices align robustly with global optimization goals.

Why the Greedy Policy Works

When an objective function is both adaptively submodular and monotonically increasing (meaning that making more observations never hurts), the theoretical guarantees are remarkably strong. Krause et al. proved that a greedy policy—which iteratively selects the action maximizing the immediate expected utility gain—is guaranteed to achieve at least a $(1 - 1/e) \approx 63.2\%$ approximation of the optimal sequential policy's value.

As highlighted by the authors in the context of environmental planning (Sequential Decision Making in Computational Sustainability via Adaptive Submodularity), this guarantee bypasses the exponential computational cost of traditional sequential planning methods. It ensures that simple, locally optimal choices lead to near-optimal global outcomes in partially observable environments.

Crafting Submodular Surrogates

A major challenge in real-world applications is that many natural objectives, such as Shannon entropy or the direct Value of Information (VoI), do not satisfy adaptive submodularity. As noted by Fern et al. in Adaptive Submodularity with Varying Query Sets: An Application to Active Multi-label Learning, maximum entropy heuristics can fail to be submodular, causing greedy selection to get stuck in myopic dead ends.

To circumvent this, researchers construct clever submodular surrogates—alternative objective functions that mimic the true goal but are mathematically guaranteed to be adaptively submodular:

Scaling to Batches and Streams

As the field has matured, researchers have extended adaptive submodularity to accommodate modern machine learning workflows, such as batch processing and streaming data.

Batch Mode Active Learning

In deep active learning, evaluating and labeling data points one by one is highly inefficient because it requires retraining the model after every single sample. Instead, systems must select batches of data. Krause et al. proved in Near-optimal Batch Mode Active Learning and Adaptive Submodular Optimization that a greedy selection strategy within batches remains highly competitive with the optimal batch policy, meaning the "price of parallelism" is remarkably low.

However, a naive greedy strategy might select a batch of highly informative but redundant samples (e.g., ten nearly identical images of the same dog). To enforce diversity, Kirsch developed BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning. By greedily maximizing the joint mutual information of an entire batch with the model parameters, BatchBALD leverages submodularity to ensure that the acquired batch is both highly informative and diverse, avoiding combinatorial search.

Data Streams and Real-Time Constraints

When data arrives continuously rather than sitting in a static pool, Kashima et al. showed in Budgeted stream-based active learning via adaptive submodular maximization how to maintain these guarantees. By introducing "policy-adaptive submodularity," the authors proved that sequential decision-making under a fixed budget over a data stream can reliably recover a significant portion of the utility available in static data pools.

Broadening the Boundaries

Recent work has focused on relaxing the strict mathematical assumptions of adaptive submodularity to make it applicable to an even wider array of problems.

The Adaptive Submodularity Ratio

Many real-world problems violate strict adaptive submodularity, yet greedy algorithms still perform exceptionally well on them in practice. To explain this gap between theory and practice, Fujii et al. introduced the adaptive submodularity ratio in Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio. This ratio quantifies exactly how close a function is to being submodular, providing weaker but still rigorous performance bounds for complex tasks like feature selection and influence maximization.

Worst-Case Robustness

Traditional adaptive submodularity optimizes for average-case expected utility. However, in safety-critical domains, average performance is not enough. Tang addressed this in Robust Adaptive Submodular Maximization by defining worst-case submodular functions. This framework allows an adaptive greedy policy to select items that maximize marginal utility in the worst possible scenario, ensuring a strict lower bound on performance regardless of how the environment responds.

Diverse Applications in AI

The mathematical elegance of adaptive submodularity has made it a core tool across a wide range of research areas:

By formalizing the intuitive concept of diminishing returns for sequential observations, adaptive submodularity provides the theoretical bedrock that justifies using simple, fast, greedy choices to solve some of the most complex, uncertain problems in artificial intelligence.

Key Foundational Work

Near-Optimal Bayesian Active Learning with Noisy Observations (2010) — contributed 2 concept elements to this direction.
Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization (2010) — contributed 2 concept elements to this direction.
Optimal Order of Decoding for Max-Min Fairness in K-User Memoryless Interference Channels (2007) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_submodular_optimization_f2a45712,
  title = {adaptive submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-submodular-optimization/rdr_f2a45712e22e43e99f6cc8f65121ebf6},
  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_adaptive_submodular_optimization_f2a45712_v1,
  title = {adaptive submodular optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-submodular-optimization/rdr_f2a45712e22e43e99f6cc8f65121ebf6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake