Many foundational problems in machine learning—such as data summarization, feature selection, and cluster initialization—rely on choosing a high-quality subset of items from a massive dataset. To solve these problems, we frequently turn to greedy algorithms. The classic greedy algorithm builds a solution step-by-step: it evaluates all remaining candidates, selects the single best item according to an objective function, adds it to the solution set, and repeats.
While simple and mathematically powerful, this process contains a fundamental flaw for modern computing: it is inherently sequential. To select the $k$-th item, you must know the exact state of the first $k-1$ items. This sequential dependency means that traditional greedy algorithms cannot exploit parallel computing architectures or distributed systems, creating a massive computational bottleneck when scaling to millions of data points.
To bypass this bottleneck, researchers have developed parallel and distributed frameworks that drastically reduce the number of sequential rounds required—a property known as adaptivity—while maintaining strict mathematical guarantees on the quality of the final solution.
The Core Problem: High Adaptivity
In parallel computation, the complexity of an algorithm is often measured by its adaptivity, which is the number of sequential rounds of queries it must make to the objective function. In each round, we are allowed to make many queries in parallel.
A traditional greedy algorithm has an adaptivity that scales linearly with the size of the desired subset ($O(k)$) or the dataset itself ($O(n)$). For example, in feature selection, choosing 1,000 features requires 1,000 sequential iterations, where each iteration waits for the previous one to finish. As shown by Alexandros Psomas et al. in Fairly Allocating Goods in Parallel, certain greedy heuristics are so deeply tied to their execution order that they cannot be accelerated without completely changing the underlying selection mechanism.
The reason greedy algorithms are so stubbornly sequential lies in the mathematical property of submodularity (or diminishing returns). The marginal value of adding an item to a set depends heavily on what has already been chosen:
$$\Delta(e \mid S) = f(S \cup \{e\}) - f(S)$$
Because $\Delta(e \mid S)$ changes every time an item is added, independent parallel evaluations can easily become invalid if multiple processors select items simultaneously based on outdated states.
Mechanism 1: Distributed Partitioning and Local Selection
One of the earliest intuitive breakthroughs for scaling submodular maximization to massive datasets was to decouple the global dependency through a two-stage "divide-and-conquer" approach.
In Distributed Submodular Maximization: Identifying Representative Elements in Massive Data, Baharan Mirzasoleiman et al. introduced GreeDi (also detailed by Amin Karbasi et al. in Distributed Submodular Maximization). Instead of running a single sequential pass over the entire dataset, the data is partitioned randomly across multiple machines. Each machine runs the standard sequential greedy algorithm locally and independently to select a small set of representative elements. Finally, these local summaries are merged onto a single coordinator machine, which runs a final global greedy pass to select the ultimate subset.
Massive Dataset ──> Partition 1 ──> Local Greedy ──┐
──> Partition 2 ──> Local Greedy ──┼─> Merge ──> Global Greedy ──> Final Subset
──> Partition 3 ──> Local Greedy ──┘
Why does this work without losing global optimization guarantees? The answer lies in submodularity. The property of diminishing returns ensures that if an item is highly representative within a random local fraction of the data, it likely contains core features that remain valuable when evaluated globally. By reducing the problem to a series of parallel maximization tasks, frameworks like DISCOVER, proposed by Baharan Mirzasoleiman et al. in Distributed Submodular Cover: Succinctly Summarizing Massive Data, allow systems to summarize graphs with billions of edges using only a fraction of the memory of a single machine.
Mechanism 2: Thresholding and the "Pool of Good Elements"
While distributed partitioning works well for MapReduce architectures, it doesn't fundamentally change the sequential nature of the underlying algorithm; it just applies it to smaller pieces. To truly parallelize subset selection, algorithms must be able to select batches of items simultaneously.
To achieve this, researchers introduced the concept of adaptive sequencing via thresholding. Instead of searching for the absolute best single element in each round, the algorithm identifies a pool of good elements whose marginal gains exceed a specific value threshold, adding them all at once.
As developed by Alina Ene et al. in A New Framework for Distributed Submodular Maximization, the intuition works as follows:
- Estimate the maximum possible marginal gain an element can offer.
- Set a high threshold $\tau$.
- Scan the dataset in parallel and immediately select all elements that provide a marginal gain $\ge \tau$.
- Once no more elements meet this threshold, lower $\tau$ by a factor of $(1-\epsilon)$ and repeat.
Because of submodularity, adding elements in parallel can only decrease the marginal gains of the remaining elements; it can never increase them. This means that elements selected simultaneously in a single round will never accidentally over-inflate each other's values.
Using this thresholding mechanism, Matthew Fahrbach et al. demonstrated in Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity that it is possible to maximize complex functions in only $O(\log n)$ adaptive rounds, collapsing an inherently linear process into a logarithmic one. For non-monotone functions (where adding items can sometimes decrease the total value), Adam Breuer et al. designed the BLITS algorithm in Non-monotone Submodular Maximization in Exponentially Fewer Iterations, proving that an exponential speedup in parallel runtime can be achieved with nearly no loss in practical performance.
This theoretical boundary was pushed to its limit by Huy L. Nguyên in Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time, providing an algorithm that simultaneously achieves an optimal approximation ratio and exceptionally low sequential complexity.
Mechanism 3: Parallel Oversampling
The sequential selection bottleneck extends beyond submodular functions into geometric clustering. Consider the popular $k$-means++ algorithm, which initializes cluster centers by choosing one center at a time via distance-weighted probability sampling. To pick $k$ centers, $k$-means++ requires $k$ sequential passes over the entire dataset—a massive bottleneck when $k$ scales into the thousands.
To break this dependency, Bahman Bahmani et al. proposed $k$-means|| (k-means parallel) in Scalable K-Means++. Instead of sampling a single center per round, the algorithm oversamples by selecting multiple centers in parallel during each pass.
k-means++: [Pass 1: Center 1] ──> [Pass 2: Center 2] ──> [Pass 3: Center 3] (Slow)
k-means||: [Pass 1: Sample O(k) Centers in Parallel] ──> [Pass 2: Sample O(k) Centers] (Fast)
By aggressively sampling a larger pool of candidate centers in parallel, the algorithm reduces the required number of communication passes from $k$ to a small fraction ($O(\log n)$). In Simple and sharp analysis of k-means||, Václav Rozhon proved that this oversampling strategy concentrates the probability space so effectively that the number of required rounds can be tightly bounded to $O(\log n / \log \log n)$, matching the clustering quality of $k$-means++ while unlocking massive parallel speedups.
Summary
The sequential selection bottleneck arises because greedy choices are conditionally dependent on previous steps. By leveraging the mathematical structure of diminishing returns (submodularity) or geometric probability spaces, modern parallel algorithms break this chain. Whether through distributed partitioning, dynamic thresholding, or parallel oversampling, these techniques allow us to process massive datasets across thousands of cores simultaneously, transforming slow, linear workflows into highly scalable, low-adaptivity operations.
Key Foundational Work
New fast QR decomposition least squares adaptive algorithms (1998) — contributed 1 concept elements to this direction.