Greedy algorithms are the workhorses of discrete optimization. To select a subset of items that maximizes an objective function, a standard greedy algorithm evaluates every remaining candidate and picks the one with the highest marginal gain. While intuitive, this exhaustive search becomes a massive computational bottleneck when dealing with large datasets.
If you need to select a subset of size $k$ from a ground set of size $n$, an exhaustive greedy search requires $O(nk)$ function evaluations. When $n$ is in the millions, evaluating a complex objective function millions of times per step is completely prohibitive.
Randomized candidate sampling (also known as stochastic greedy selection) bypasses this bottleneck with a deceptively simple modification: instead of scanning the entire remaining ground set at each step, the algorithm randomly samples a small subset of candidates and picks the best item within that subset.
The Intuition: The Power of "Good Enough"
Why does picking the best item from a small random subset yield a globally competitive solution? The answer lies in basic probability.
Suppose you want to find an item that ranks in the top 5% of a large population. If you sample a small random subset of size $s = 60$, the probability that none of those 60 items fall into the top 5% is:
$$(1 - 0.05)^{60} \approx 0.046$$
This means there is a greater than 95% chance that your random subset contains at least one item from the top 5%. By choosing the best item within this subset, you are guaranteed to pick an exceptionally strong candidate, even though you completely ignored 95% of the population.
Crucially, the sample size $s$ required to hit a specific percentile with high confidence depends only on the percentile and the desired confidence level—it is entirely independent of the total population size $n$. This insight decouples the cost of a single greedy step from the total size of the dataset, transforming a linear-time search into a constant-time search per step.
Exhaustive Greedy Step:
[ Candidate 1, Candidate 2, Candidate 3, ... , Candidate N ] --> Evaluate ALL N candidates
(Costly: O(N))
Stochastic Greedy Step:
[ Candidate 1, Candidate 2, Candidate 3, ... , Candidate N ]
│ │ │
▼ ▼ ▼
[ Sample A , Sample B, Sample C ] --> Evaluate only s candidates
(Efficient: O(s))
Theoretical Backing in Submodular Maximization
This probabilistic intuition is formalized beautifully in the context of submodular maximization. Submodular functions exhibit a "diminishing returns" property, where the marginal benefit of adding an item decreases as the selected set grows. Because of this structural regularity, making a series of "good enough" local choices accumulates into a high-quality global solution.
Sakaue demonstrated that for non-monotone submodular functions, a stochastic greedy algorithm can reduce function evaluations by two orders of magnitude without significant loss in objective value, achieving a provable $1/4$-approximation ratio in linear time. Similarly, Ohsaka and Yoshida showed that incorporating random sampling into greedy selection enables near-linear time complexity for $k$-submodular maximization while maintaining strong approximation guarantees.
By adjusting the sample size dynamically, algorithms can optimize the trade-off between runtime and accuracy:
- Linearizing Runtime: Harshaw et al. used random sub-sampling to reduce the runtime of greedy selection from a product of the ground set size and constraint limit to a near-linear complexity relative to the ground set size.
- Poly-logarithmic Sampling: Nguyên proved that evaluating a poly-logarithmic number of random samples is sufficient to achieve nearly-optimal approximation ratios in nearly-linear total running time.
Broad Applications in Machine Learning
The power of randomized candidate sampling extends far beyond pure combinatorial optimization. It serves as a general-purpose meta-heuristic for scaling up selection processes across machine learning.
Active Learning and Data Selection
In active learning, selecting the most informative batch of samples to label typically requires evaluating the entire unlabeled pool. Kong and Jeon bypassed this combinatorial complexity by using a randomized search strategy that evaluates the spectral properties of multiple randomly sampled candidate batches. Similarly, in sparse Gaussian Processes, Lawrence et al. utilized a randomized greedy strategy to select informative data points from a small, randomly sampled subset, matching the performance of exhaustive search at a fraction of the cost.
Streaming and Sequential Decision Making
When data arrives in a continuous stream, looking at every item is often impossible. Feldman et al. introduced a streaming mechanism that uses a biased coin flip to discard a portion of incoming data points before evaluation, achieving state-of-the-art approximation guarantees while running up to 50 times faster. In sequential decision-making under uncertainty, the authors of Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time showed that selecting candidates from a randomized subset reduces query complexity from quadratic to linear while maintaining high approximation accuracy.
Information-Theoretic Search
In complex dialog systems, calculating the expected information gain for every possible question is computationally intractable. Lee and Yang demonstrated that approximating information gain by evaluating only a small subset of the most likely candidates makes these information-theoretic calculations tractable without sacrificing task performance.