Submodular functions formalize the intuitive notion of "diminishing returns": adding an item to a small set yields a larger marginal benefit than adding that same item to a larger set. This mathematical property makes submodularity a natural fit for real-world machine learning tasks that value diversity and coverage, such as data summarization, sensor placement, and active learning, as detailed by Kai Wei et al. in Submodularity in Data Subset Selection and Active Learning.
However, as datasets grow into millions of elements, traditional optimization algorithms hit a severe computational wall. To understand why, we must look at how these algorithms interact with the objective function and how researchers are redesigning them to scale.
The Core Bottleneck: Value Oracle Queries
In submodular optimization, we typically do not have an explicit algebraic formula for the function $f(S)$ we want to maximize. Instead, we treat it as a black box—a value oracle—that we query to find the utility of a given subset $S$.
The classic solution is the Greedy Algorithm. To select a subset of size $k$ from a ground set of $n$ items, the greedy algorithm proceeds in $k$ sequential steps. At each step, it evaluates the marginal gain of every single remaining item and selects the one that maximizes the increase.
$$\text{Marginal Gain: } \Delta(e \mid S) = f(S \cup \{e\}) - f(S)$$
This requires evaluating the function for every remaining item at every step, leading to a total query complexity of $O(n \cdot k)$. If you are selecting a summary of $k = 100$ images from a dataset of $n = 1,000,000$ images, you must evaluate your submodular function 100 million times. When evaluating $f(S)$ requires running an expensive machine learning model or calculating complex pairwise distances, this quadratic overhead becomes completely prohibitive, as noted by Shinsaku Sakaue in Guarantees of Stochastic Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraint.
The Dual Challenges of Scalability
To scale submodular optimization, researchers focus on optimizing along two primary axes:
- Query Complexity: The total number of times the algorithm evaluates the function $f(S)$.
- Adaptivity: The number of sequential rounds of computation the algorithm must perform. High adaptivity means the algorithm is inherently serial; low adaptivity means it can be heavily parallelized.
A major challenge in this field is a persistent tension between these two metrics. As Chandra Chekuri et al. observe in Parallelizing greedy for submodular set function maximization in matroids and beyond, attempts to parallelize the greedy algorithm by evaluating many items simultaneously often trigger an explosion in the total number of queries. Conversely, reducing the number of queries can sometimes degrade the quality of the final solution, creating a fundamental trade-off between efficiency and the theoretical approximation ratio.
Decoupling the Ground Set from Constraints
The first major breakthrough in scaling these algorithms involves breaking the $O(n \cdot k)$ product. Ideally, an algorithm's dependence on the massive ground set size $n$ should be strictly linear, while any higher-order computational costs should be confined to the much smaller constraint size $k$.
Stochastic Shortcuts
Instead of scanning all $n$ items at each step, what if we only look at a small, randomly sampled subset? The diminishing returns property ensures that a small random sample is highly likely to contain at least one element that provides a good approximation of the global maximum marginal gain.
Shinsaku Sakaue demonstrates that a modified stochastic greedy approach can achieve a provable $1/4$-approximation ratio in strictly linear time. By sampling a subset of items at each step, the algorithm completely decouples the search space from the total dataset size.
Achieving $O(n + \text{poly}(k))$ Complexity
Building on this intuition, Murad Tukan et al. show in Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint that it is possible to achieve an $O(n + k^2)$ query complexity.
Traditional Greedy: [====== n ======] × [=== k ===] = O(nk)
Decoupled Greedy: [====== n ======] + [= k² =] = O(n + k²)
By isolating $n$ to a linear term, the size of the dataset only impacts the runtime as a baseline pass, making the algorithm highly scalable for web-scale graphs and massive data streams where $n \gg k$.
Thresholding: Replacing Comparison with Acceptance
Another powerful paradigm shifts the core question of the algorithm. Instead of asking "Which element is the absolute best?" (which requires comparing all elements against each other), the algorithm asks "Does this element meet our quality standard?"
This is known as thresholding. If we can estimate the total value of the optimal solution ($OPT$), we know that on average, each item in the optimal set must contribute roughly $OPT/k$ to the total utility.
- Set a Threshold: Choose a threshold $\tau$ based on an estimate of $OPT/k$.
- Scan and Accept: Iterate through the items. The moment an item's marginal gain exceeds $\tau$, immediately add it to the solution set.
- Decay: If a full pass yields no items, lower the threshold $\tau$ by a factor of $(1-\epsilon)$ and repeat.
Streaming and Parallelization
This thresholding mechanism is what enables both streaming and parallel submodular optimization:
- In Streaming: Elements arrive one by one. Because we do not need to compare them to other elements in the stream, we can make an immediate, single-pass decision to keep or discard them. Baharan Mirzasoleiman et al. leverage this in Streaming Non-Monotone Submodular Maximization: Personalized Video Summarization on the Fly to achieve massive speedups by recycling discarded elements on the fly.
- In Parallelization: Because the acceptance criterion depends only on the current state of the solution set and the fixed threshold $\tau$, many elements can be evaluated simultaneously across different processors. Canh V. Pham et al. utilize this concept in Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint to design an Alternate Thresholding (AST) algorithm that achieves near-optimal parallel adaptivity ($O(\log n)$ rounds) while keeping total query complexity low.
Managing Non-Monotonicity
The problem becomes significantly more complex when the submodular function is non-monotone—meaning that adding an item can sometimes decrease the total value of the set. This is common in pure diversity applications, where adding a redundant or irrelevant item actively harms the quality of a summary.
When a function is non-monotone, a standard greedy algorithm can easily trap itself in a local optimum by picking elements early on that block better combinations later. To prevent this, algorithms must balance greedy selection with randomized or deterministic pruning.
To maintain scalability in these harder settings, Matthew Fahrbach et al. developed algorithms detailed in Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity that run in just $O(\log n)$ sequential rounds while keeping total work bounded to $O(n \log k)$ queries.
Similarly, for complex knapsack constraints (where items have varying costs rather than a simple uniform size), Dung T. K. Ha et al. introduced deterministic algorithms in Robust Approximation Algorithms for Non-monotone k-Submodular Maximization under a Knapsack Constraint that match state-of-the-art approximation ratios while reducing the required query overhead by a factor of $\Omega(\log n)$.
By combining stochastic sampling (to decouple dataset size from constraints) and thresholding (to replace expensive global comparisons with immediate acceptance checks), modern submodular optimization bypasses the classical quadratic bottlenecks, allowing provably near-optimal discrete optimization to run on web-scale data.