Query Complexity Limits in Submodular Optimization

38 concepts23 papers2 proposals

Submodular functions are often described as the discrete analogues of convex or concave functions. They capture the intuitive economic principle of "diminishing returns": adding an element to a small set yields a greater or equal increase in value than adding the same element to a larger set. Because of this structural mathematical grace, submodular optimization serves as a foundational pillar for machine learning, data streaming, and algorithmic economics.

However, in most real-world applications, we do not possess a neat, closed-form algebraic expression for a submodular function $f(S)$. Instead, we interact with it through a value oracle—a black box that accepts a subset $S$ and returns its evaluation $f(S)$. Because a ground set of size $n$ contains $2^n$ possible subsets, the primary bottleneck in submodular optimization is rarely raw CPU clock cycles. Instead, it is query complexity: how many questions must we ask the oracle to find or approximate the optimal set?

A profound body of research has focused on mapping the exact information-theoretic boundaries of this question, revealing that submodular functions possess hidden structural complexities that strictly limit how fast they can be optimized, parallelized, or learned.

The Value Oracle and the Information Bottleneck

To understand why query complexity dictates the limits of submodular optimization, consider the act of optimization as a game of twenty questions against an adversarial landscape. As noted by Li et al., even with unlimited computational power, an algorithm requires a fundamental minimum number of function evaluations to achieve an approximation better than random selection when the selection budget is a significant fraction of the ground set.

This information bottleneck means that the core challenge of the field is bridging the gap between the lower bounds (the absolute minimum queries mathematically required) and the upper bounds (the queries consumed by our best algorithms).

The Super-Linear Hardness of Minimization

Submodular function minimization (SFM) is highly celebrated because, like continuous convex minimization, it can be solved exactly in polynomial time. Yet, determining its exact query complexity has proved surprisingly elusive.

For over a decade, the theoretical baseline lower bound for general SFM stood at a mere $n$ queries. This bound felt unsatisfyingly weak given the practical difficulty of the problem. Graur et al. broke through this barrier by proving a tighter lower bound of $2n$ queries, demonstrating that general SFM is inherently more complex than a simple linear scan of the ground set elements.

Query Complexity Landscape for Deterministic SFM
|
|   O(n³) — Current Best Cutting-Plane Methods (Lee et al.)
|
|   Ω(n log n) — Proven Deterministic Lower Bound (Graur et al.)
|
|   2n — General Oracle Lower Bound (Graur et al.)
+------------------------------------------------------- Size of Ground Set (n)

When we restrict our focus to deterministic algorithms, the floor rises even higher. Graur et al. established that deterministic SFM requires a super-linear number of queries, specifically at least $\Omega(n \log n)$. This logarithmic overhead proves that deterministic approaches cannot seamlessly navigate the combinatorial landscape without paying an informational penalty.

Meanwhile, our fastest exact algorithms still consume significantly more queries than these lower bounds. For example, the cutting-plane method developed by Lee et al. brought the query complexity of combinatorial optimization down to $O(n^3)$, leaving a persistent gap between cubic upper bounds and the quadratic limits suggested by mathematical duality. Similarly, popular practical heuristics like Wolfe's algorithm have historically lacked strongly polynomial complexity bounds independent of the function's maximum values, as detailed by Chakrabarty et al..

The Price of Parallelism: Adaptivity vs. Query Count

In modern computing, we often try to bypass time bottlenecks by running queries in parallel. In the context of oracle queries, this is measured by adaptivity: the number of sequential rounds an algorithm requires, where each round can launch many parallel queries.

If you want to minimize a submodular function using very few queries, you are forced to behave highly adaptively—meaning your next query must depend heavily on the results of the last. Assadi et al. exposed a strict trade-off in this mechanism, proving that SFM requires a high degree of query adaptivity to achieve sub-quadratic query complexity. Without a polynomial number of sequential rounds, the total number of queries needed to find a minimum remains stuck near $\Omega(n^2)$.

This creates an algorithmic catch-22: you cannot radically parallelize your queries to save time without causing an explosion in the total number of queries required. As Kenneth-Mordoch observes, identifying which specific subclasses of submodular functions can bypass this restriction and be optimized in a constant or near-constant number of rounds remains a major open challenge. Even when moving to entirely different computational paradigms, such as the quantum oracle model analyzed by Rebentrost et al., it remains unproven whether quantum multi-sampling can fundamentally break past linear scaling limits for approximate minimization.

The Fragility of Submodular Maximization

Unlike minimization, submodular maximization is NP-hard, meaning we must content ourselves with approximation algorithms (such as the classic greedy algorithm which guarantees a $(1-1/e)$ approximation). But even when we lower our sights from perfection to approximation, information-theoretic walls block our path.

A recurring hope in sublinear algorithm design is that if we only want to find a small target subset of size $k$, we might be able to query a sublinear fraction of the items. Peng et al. shattered this hope by proving that for general monotone submodular functions, merely estimating the value of the optimal subset requires a near-linear number of queries relative to the total number of items. Truly sublinear shortcuts are fundamentally impossible for general submodular optimization, regardless of how small your target subset is.

   Noisy Function f̃(S)               True Submodular f(S)
 [ Modest Noise > 1/k ]  =======>  [ Mathematical Structure ]
                                       |
                                       v
                                 Shattered!
                       (Requires Exponential Queries)

Worse still, this optimization structure is incredibly fragile. In practice, we rarely optimize a pristine submodular function; instead, we optimize an approximately submodular function corrupted by noise or learning errors. Horel et al. proved a striking "spoiler" result: if the approximation error exceeds a tiny threshold ($1/k$), achieving a constant-factor approximation suddenly requires an exponential number of value queries. The mathematical tractability of submodularity vanishes instantly in the face of even modest objective uncertainty.

Structural Compressibility and Learning Limits

The query bottlenecks encountered during optimization are a direct symptom of how difficult submodular functions are to compress or learn. Because general submodular functions can be wildly unstructured, they resist being simplified into concise representations.

According to the information-theoretic limits detailed in Submodular Functions: Learnability, Structure, and Optimization, there is a hard limit on our ability to "sketch" or compress submodular functions under general distributions, resulting in a lower bound of approximately $n^{1/3}$ for approximation error. You cannot reduce a general submodular function to a compact summary without suffering a massive loss of information.

This structural complexity places severe constraints on machine learning algorithms:

  • General Intractability: As shown by Raskhodnikova et al., learning general submodular functions requires an exponential number of queries, meaning efficient PAC-learning is impossible unless we restrict the function's range or structure (such as focusing on pseudo-Boolean DNF formulas).
  • The High-Precision Barrier: Even when submodular functions possess an underlying simplicity—such as being closely approximable by low-rank decision trees, as proven by Feldman et al.—establishing the exact boundary between what can be learned with high precision and what remains inherently intractable remains a central challenge.

Ultimately, whether we are trying to minimize, maximize, or learn a submodular function, we are bound by the same physical reality: submodularity provides a powerful mathematical toolkit, but the value oracle model imposes strict, unyielding limits on how much information we can extract, and how fast we can extract it.

Key Foundational Work

Learning pseudo-Boolean k-DNF and Submodular Functions (2012) — contributed 1 concept elements to this direction.
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees (2013) — 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_submodular_function_minimization_complex_b3b4a7bc,
  title = {submodular function minimization complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-function-minimization-complexity/rdr_b3b4a7bcfe294c4698cdf3474ab70bd5},
  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_submodular_function_minimization_complex_b3b4a7bc_v1,
  title = {submodular function minimization complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-function-minimization-complexity/rdr_b3b4a7bcfe294c4698cdf3474ab70bd5/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